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.

Answer

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, 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,
xn=αn=αn(mod1),n=1,2,3,...

It turns out that only certain values of α produce low discrepancy sequences. For number theoretic reasons, these special values of α 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 α is, the better (‘more even’) the low discrepancy sequence will be. Thus, the golden ratio φ=1+52 produces the optimal low discrepancy sequence.

Two things worth mentioning.
First, is that any value of α related via the moebius transformation,
α=a+bφc+dφfor integersa,b,c,dwhere|adbc|=1.
will also be optimal.

And secondly, α=1+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 α=110(9+221 is the third-most badly approximable number.

Interestingly the continued fraction for these three values are:
φ=1+11+11+11+...=[1,1,1,1,...]
1+2=2+12+12+12+...=[2,2,2,2,2,2]
110(9+221)=2+12+11+11+...=[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 αα=(α1,α2,...,αd), the infinite sequence of d-dimensional vectors xxnU[0,1]d defined as follows:

xxn=nαα(mod1),n=1,2,3,...

is equidistributed if αi are all independently irrational numbers. Furthermore, in many cases if α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, αα=(2,3) is not great, but as seen in the diagram above αα=(3,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 αα is based on a special value ϕd that is a d-dimensional generalisation of the golden ratio, ϕ=1+52.

That is,

ttn=nϕϕ(mod1),n=1,2,3,...
where
ϕϕ=(1ϕ1d,1ϕ2d,1ϕ3d,...1ϕdd),

andϕd is the smallest value of x>0such that

xd+1=x+1.

For d=1ϕ1=1.618033989…, which is the canonical golden ratio.

For d=2, ϕ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, ϕ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!

Attribution
Source : Link , Question Author : Robin Saunders , Answer Author : Martin Roberts

Leave a Comment