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

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.

-
Reminds me of Weyl's Equidistribution theorem. en.wikipedia.org/wiki/Equidistribution_theorem –  Tony Huynh Sep 2 '10 at 14:02
Yes, but this property is stronger than the sequence being uniformly distributed. –  Robin Saunders Sep 2 '10 at 14:19
Do you mean a result like front.math.ucdavis.edu/0906.0045 ? –  Helge Sep 2 '10 at 15:34
Robin, your question is unclear. I think the "stronger property" you attribute to multiples of $\phi$ has to do with uniformity of spacing between adjacent points (after ordering), but something like this happens for any irrational (look for The Three Gap Theorem). And you're interested in higher dimensions, but how do you propose to order a bunch of points up there? The usual way to measure how even a distribution is is via discrepancy, and there is a lot of work on low discrepancy sequences in high dimension, and the Kuiper-Niederreiter book will get you started. –  Gerry Myerson Sep 2 '10 at 23:13
That's not what I meant, but, yes, those are meaningful questions. I think the Niederreiter paper looks at dispersion for $n\theta$ and finds it minimized for the golden mean. I don't know if he looks at dispersion for u. d. sequences, and I don't know if he looks at the minmax problem. But you now have several papers you can look at to see what results and what ideas you can try to apply to your questions. The Schilling paper is on Schilling's website. –  Gerry Myerson Sep 8 '10 at 5:52

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).

-
Yes, that book certainly does discuss the higher-dimensional problem, in detail, and even though it was published over 35 years ago it's still a good place to start learning about these things. But the original question is unclear to me.... –  Gerry Myerson Sep 2 '10 at 22:58

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.

-
You are computing something very closely related to the "discrepancy" of the sequence. You'll find much information on discrepancy in the Kuiper-Niederreiter book and elsewhere. –  Gerry Myerson Sep 3 '10 at 0:02

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.

-