Sequences of evenly-distributed points in a product of intervals - MathOverflow

Sequences of evenly-distributed points in a product of intervals

2010-09-02T13:51:01Z

Let φ be the golden ratio, (1+√5)/2. Taking the fractional parts of its integer multiples, we obtain a sequence of values in (0,1) which are in some sense "evenly distributed" in a way which is due to the continued fraction form of φ, making the constant "as difficult as possible" to approximate using rational values (otherwise, the values in the sequence would cluster around multiples of such rational approximations). If one takes the first n values, especially if n is a Fibonacci number, they will be very evenly spaced; in fact, if n is a Fibonacci number, then the difference between two consecutive values (after ordering) is always one of two adjacent powers of φ, in correspondence with the fact that the Fibonacci numbers themselves are roughly of the form φ^k/√5.

Is there any related (or otherwise?) sequence of values in (0,1)^d, where d > 1, which are similarly "evenly distributed"?

Edit: I've been a bit unclear about the way in which φ is "special", so I'll try to elucidate. My motivation was that, as drvitek says, φ has no "better-than-expected" rational convergents. So when nφ (mod 1) is plotted against n, not only is the entire set of residues uniformly distributed on (0,1) but also "locally" we have a roughly-uniform distribution on (0,1) × N. This property marks φ out as "special" compared with most irrational numbers. I'm afraid I'm not sure how to phrase it more precisely than that.

Answer by Benoît Kloeckner for Sequences of evenly-distributed points in a product of intervals

2010-09-02T15:30:04Z

It should be possible to do the same with a carefully chosen tuple of rationaly independent numbers $(\varphi_1,\ldots,\varphi_d)$, no ? But the precise equidistribution you want is not very clear to me.

Note that the sequence that is conjectured to be the most evenly distributed on $(0,1)$ is the dyadic one : $1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8,\ldots$, see Kuipers & Niederreiter Uniform distribution of sequences (which might discuss the higher-dimensional problem as well).

Answer by drvitek for Sequences of evenly-distributed points in a product of intervals

2010-09-02T16:31:26Z

One way to interpret this result is that it comes from the periodicity of the continued fraction expansion of $\phi = 1 + \frac{1}{1+\frac{1}{\cdots}}$ in the sense that it has no "better-than-expected" rational convergents, whereas for example with $\pi = (3;7,15,1,292,\cdots)$ we may stop at the 292 to get a good approximation (355/113 I believe).

So one may look at numbers of the form $x_n = (n;n,n,n,\cdots)$, which satisfy $x_n^2 -nx_n - 1 = 0$, or $$x_n = \frac{n+\sqrt{n^2+4}}{2}.$$ So a few good sequences may be for example $\left\{nx_2\right\}$ where $x_2 = 1+\sqrt{2}$, the so-called "silver ratio", or the same for $x_3 = (3+\sqrt{13})/2.$

EDIT: These are in some cases pretty good approximations; one way to measure the "well-distribution" of such a sequence is to take the fractional parts $\{\lfloor nx_n \rfloor: n = 1, \cdots, M\}$, sort them, compute the maximum difference between consecutive terms, and multiply this by $M$ to get some number in the range $[1,M)$. This can be accomplished in one line in Mathematica as follows:

WellDistribution[x_,M_]:=
Max[Differences[Sort[Table[N[FractionalPart[x*m]], {m, 1, M}]]]]*M;

Some interesting things happen with this when we vary $n$; perhaps I'll make a new post out of it.

Answer by Gerry Myerson for Sequences of evenly-distributed points in a product of intervals

2010-09-03T04:06:37Z

How evenly a sequence is distributed is often measured by its $\it discrepancy$. Let $u(1),u(2),\dots$ be a sequence of numbers in $[0,1)$. We define the discrepancy $D(n)$ of the first $n$ terms of the sequence by $nD(n)=\sup\vert A(a;n)-na\vert$, where $A(a;n)$ counts the number of terms with $k\le n$ and $u(k)\lt a$, and the supremum is over all $a$ with $0\lt a\le1$. Technically, what I've just defined is the $\it star-discrepancy$, but the distinction need not detain us here.

Sequences are known with $nD(n)=O(\log n)$. This is best possible, in the sense that there is an absolute constant $c$ such that for every sequence we have $nD(n)\gt c\log n$ for infinitely many $n$.

Now for higher dimensions. Let $\bf x$ be a point in $I=[0,1]^d$. Let $B({\bf x})$ be the box (that is, parallelipiped aligned with the coordinate axes) with diagonally opposite corners at the origin and $\bf x$. Let $V({\bf x})$ be the volume of this box (so it's just the product of the components of $\bf x$). Given a sequence ${\bf u}(1),{\bf u}(2),\dots$ of points in $[0,1)^d$, define the discrepancy $D(n)$ of the first $n$ terms of the sequence by $nD(n)=\sup\vert A({\bf x};n)-nV({\bf x})\vert$, where $A({\bf x};n)$ counts the number of terms with $k\le n$ and ${\bf u}(k)$ in $B({\bf x})$, and the supremum is over all $\bf x$ in $I$. Various and sundry results are known about upper and lower bounds for $nD(n)$. As mentioned elsewhere, the Kuipers (which I have incorrectly given as Kuiper in some of the comments) and Niederreiter book is a good place to start. The website http://www-rocq.inria.fr/mathfi/Premia/free-version/doc/premia-doc/pdf_html/mc_quasi_doc/index.html discusses some low discrepancy sequences.