On uniformly distributed dilates of finite integer sequences

Given N nonzero real numbers a(1) <. . .< a(N), we consider the problem of finding a real number alpha so that alpha a(1),..., alpha a(N) are close to be uniformly distributed module one (this question is attributed to Komlos ). First, it turns out that it suffices to consider integers a(1),...,a(N). Given various quantities that measure how close a sequence is to being uni formly distributed, e.g., the size of the largest gap between consecutive p oints on the circle, discrepancy, or the number of points falling into any interval of size 1/N ("concentration"), we provide upper bounds for the opt imal dilate. These bounds depend only on N and they are attained by typical alpha, i.e., up to alpha belonging to some set of small measure. We also p rovide lower bounds For these quantities. Some of our examples are construc ted for this purpose by means of probabilistic methods. In case of the disc repancy, the lower and upper bounds match up to logarithms (root N/log N vs root N log N). However, in case of the largest gap (log N/N vs N-1/2) and the concentration (exp(c log N/log log(2) N) vs N1/3+epsilon) the lower and upper bounds do not match and the question about the correct asymptotic be havior in terms of N remains open. Finally, we improve on a recent result o f Noga Alon and the second author by showing that every set of N integers c ontains a non-averaging subset of size at least N-1/5. (C) 2000 Academic Pr ess.