# 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

Part 1. Equidistribution.

As mentioned in the comments, the equidistribution theorem states that any irrational value will produce an equidistributed sequence. That is, in the limit as $n \rightarrow \infty$, all finite subintervals of $(0,1)$ are equally likely.

However, as you have mentioned, equidistribution is quite a weak criterion and does not necessarily imply that for finite $n$ the sequence will fill the interval 'evenly' without large gaps or clusters.

Part 2. The Kronecker low discrepancy sequence in 1-dimension

Sequences that satisfy this stronger criterion of 'evenness' are called low discrepancy sequences. There are many ways to construct low discrepancy sequences, including the van der Corput / Halton sequences, Niederreiter and Sobol sequences to name a few. However, by far the most simple to construct are the Kronecker (sometimes called Weyl) additive recurrence sequences, which are defined exactly as you describe in your question. That is, $$x_n = \lfloor \alpha n\rfloor = \alpha n \; (\textrm{mod} \; 1), \quad n=1,2,3,...$$

It turns out that only certain values of $\alpha$ produce low discrepancy sequences. For number theoretic reasons, these special values of $\alpha$ are also correspond to numbers that are badly approximable (by the rationals). Intuitively one can say that the more badly approximable a number is by the rationals, the 'more irrational' it is. This is why the golden ratio, which is the most badly approximable number, is often described as the most irrational number. The more irrational the value of $\alpha$ is, the better ('more even') the low discrepancy sequence will be. Thus, the golden ratio $\varphi = \frac{1+\sqrt{5}}{2}$ produces the optimal low discrepancy sequence.

Two things worth mentioning. First, is that any value of $\alpha$ related via the moebius transformation, $$\alpha = \frac{a+b\varphi}{c+d\varphi} \quad \textrm{for integers} \;\;a,b,c,d \;\; \textrm{where} \; |ad-bc|=1.$$ will also be optimal.

And secondly, $\alpha = 1+\sqrt{2}$ turns out to be the next most badly approximable number -- and therefore the next most optimal value for the construction of a low discrepancy sequence.

Springborn as well as Spalding give number theoretic reasons why this is the second most badly approximable number, and also why $\alpha = \frac{1}{10} (9+\sqrt{221}$ is the third-most badly approximable number.

Interestingly the continued fraction for these three values are: $$\varphi = 1+\frac{1}{1+\frac{1}{1+\frac{1}{1+...}}} = [1,1,1,1,...]$$ $$1+\sqrt{2} = 2+\frac{1}{2+\frac{1}{2+\frac{1}{2+...}}} = [2,2,2,2,2,2]$$ $$\frac{1}{10}(9+\sqrt{221}) = 2+\frac{1}{2+\frac{1}{1+\frac{1}{1+...}}} = [2,2,1,1,2,2,1,1,2,2,1,1,..]$$

Part 3. Kronecker low discrepancy sequences in higher dimensions

Regarding the main part of your question as to if there is an equivalent process for higher dimensions, the answer is a resounding 'Yes!'.

Some visualizations of various two dimensional low discrepancy sequences can be seen here.

The $d$-dimensional Kronecker sequence is a natural extension of the 1-dimensional case. That is, for a given constant $\pmb{\alpha} = (\alpha_1, \alpha_2,...,\alpha_d)$, the infinite sequence of $d$-dimensional vectors $\pmb{x}_n \in U[0,1]^d$ defined as follows:

$$\pmb{x}_n = n\pmb{\alpha} \; (\textrm{mod} \; 1), \quad n=1,2,3,...$$

is equidistributed if $\alpha_i$ are all independently irrational numbers. Furthermore, in many cases if $\alpha_i$ are the square roots of prime numbers, than the sequence will be a low discrepancy sequence. Unfortunately, it is non-trivial to know in advance if a particular set of prime numbers will result in a low discrepancy sequence. For example, $\pmb{\alpha} = (\sqrt{2}, \sqrt{3})$ is not great, but as seen in the diagram above $\pmb{\alpha} = (\sqrt{3}, \sqrt{7})$ is quite good.

Thankfully, in most applications, for moderately large $d$, the construction of such a $d$-dimensional low discrepancy sequence that is based on the square roots of the first $d$ prime numbers, produces quite good results.

Part 4. Generalizing the Golden ratio

My blog post "The unreasonable effectiveness of quasirandom sequences", describes another method that produces significantly better and more reliable results. In this case, the $d$-dimensional constant vector $\pmb{\alpha}$ is based on a special value $\phi_d$ that is a $d$-dimensional generalisation of the golden ratio, $\phi = \frac{1+\sqrt{5}}{2}$.

That is,

$$\pmb{t}_n = n \pmb{\phi} \; (\textrm{mod} \; 1), \quad n=1,2,3,...$$ where $$\pmb{\phi} =(\frac{1}{\phi_d^1}, \frac{1}{\phi_d^2},\frac{1}{\phi_d^3},...\frac{1}{\phi_d^d}),$$

$$\textrm{and} \; \phi_d\ \textrm{is the smallest value of } \; x>0 \; \textrm{such that}$$

$$x^{d+1}\;=x+1.$$

For $d=1$,  $\phi_1 = 1.618033989...$, which is the canonical golden ratio.

For $d=2$, $\phi_2 = 1.3247179572...$, which  is often called the plastic constant or silver ratio, and has some beautiful properties. This value was conjectured to most likely be the optimal value for a related two-dimensional problem [Hensley, 2002]. Jacob Rus has posted a beautiful interactive/dynamic visualization of this 2-dimensional low discrepancy sequence, which can be found here.

For $d=3$, $\phi_3 = 1.2207440846...$

Summary

Here is some Python code to create the $d$-dimensional generalization of the golden ratio-based Kronecker sequence that you cite in your question.

# Use Newton-Rhapson-Method to calculate \phi_d
def gamma(d):
x=1.0000
for i in range(20):
x = x-(pow(x,d+1)-x-1)/((d+1)*pow(x,d)-1)
return x

d=3
n=100

g = gamma(d)
alpha = np.zeros(d)
for j in range(d):
alpha[j] = pow(1/g,j+1) %1
z = np.zeros((n, d))
seed = 0.5  #Optional seed value.
for i in range(n):
z = (seed + alpha*(i+1)) %1

print(z)


Hope that helps!

• Thank you so much, this is great! Have you proved that this construction is optimal among Kronecker-type sequences? (I can certainly believe that it is.) – Robin Saunders Jul 12 '18 at 17:26
• Unfortunately not yet. This is still very much a work in progress! – Martin Roberts Jul 12 '18 at 23:38
• The first paragraph of this answer is very troubling. To write that, "in the limit as $n\to\infty$, all values of $x$ are equally likely," when what one really means by equidistribution is that, in the limit, all intervals of any given nonzero measure are equally likely, is surely a poor choice of words; almost all values of $x$ have probability zero, while the rest have probability one. Also, the equidistribution theorem says much more than that the range of the sequence is dense in the interval. The sequence where $x_n$ is the fractional part of $\log n$ (continued, next comment) – Gerry Myerson Jul 13 '18 at 0:50
• (continued from previous comment) is far from being uniformly distributed, but its range is dense in the interval. And the theorem than the fractional part of $n\theta$ is uniformly distributed for irrational $\theta$ – I don't think anyone refers to this result as Weyl's criterion, which is something different altogether. – Gerry Myerson Jul 13 '18 at 0:53
• It is worth noting that in the multi-dimensional setting d>1 no specific vector $\alpha$ is known for which $(n \alpha)$ is a low-discrepancy sequence. This is in stark contrast to the one-dimensional case. So the answer above provides some experimental facts, but the corresponding theoretic problem is still completely open. (This is essentially due to the fact that continued fractions are missing/problematic in the multi-dimensional case.) – Kurisuto Asutora Sep 6 '18 at 7:45

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.