One-dimensional quasi-uniform Kronecker sequences
Takashi Goda


An Improved Graph Pooling Network for Skeleton-Based 
Action Recognition
    Josef Kittler
    April 29, 2024
========================================================================




    In this short note, we prove that the one-dimensional Kronecker sequence iα 1, i=0,1,2,…, is quasi-uniform if and only if α is a badly approximable number. Our elementary proof relies on a result on the three-gap theorem for Kronecker sequences due to Halton (1965).



11K36, 11J71, 65D12


§ INTRODUCTION AND THE MAIN RESULT

Motivated primarily by applications to scattered data approximation <cit.>, we are concerned with the quasi-uniformity of infinite sequences of points. Let  be a compact subset of ^d for a dimension d with vol()>0. For an infinite sequence of points =(_i)_i=0,1,2,… in , we say that  is quasi-uniform over  if there exists a constant C>1 such that

    ρ_n():=h_n()/q_n()≤ C

for all positive integers n, where h_n() and q_n() denote the fill distance and the separation radius of the first n points of , respectively, i.e.,

    h_n():=sup_∈min_0≤ i<n-_i  and   q_n():=1/2min_0≤ i<j<n_i-_j,

with · representing the Euclidean norm on ^d. Note that ρ_n() is known as the mesh ratio of the first n points of . From the definition, it is evident that h_n()≥ q_n(), and thus ρ_n()≥ 1. Quasi-uniformity refers to the property of infinite sequences in which successive points fill the domain  evenly while keeping some distances from each other. This property is desirable for sampling nodes for function evaluation in scattered data approximation <cit.>. 

Another popular measure of uniformity is the discrepancy, which has been widely studied in the field of quasi-Monte Carlo (QMC) methods <cit.>. In fact, the fill distance h_n() has also been studied in this context, often referred to as “dispersion” instead of “fill distance”. A sequence  in the unit cube [0,1]^d is said to be a low-dispersion sequence if lim sup_n→∞n^1/dh_n()<∞. Many explicit constructions of low-discrepancy sequences have already been proven to exhibit low dispersion as well <cit.>. However, it remains largely unknown whether low-discrepancy or low-dispersion sequences are also quasi-uniform. While a recent paper by the author <cit.> has proven that the Sobol' sequence <cit.>, one of the best-known low-discrepancy sequences, is not quasi-uniform in dimension 2 over the unit square [0,1]^2, it is far from trivial whether higher-dimensional Sobol' sequences or other common low discrepancy sequences are quasi-uniform over the d-dimensional unit cube [0,1]^d. 

In this short note, we focus on the simplest one-dimensional case and investigate the quasi-uniformity of one of the well-known sequences, the Kronecker sequence, over the unit interval [0,1]. The Kronecker sequence is defined as

    x_i=iα 1,   i=0,1,2,…,

for a real number α>0. It is known that this sequence achieves the star discrepancy of O((log n)/n) if and only if α is irrational and its continued fraction expansion [a_0;a_1,a_2,…] satisfies (1/m)∑_j=1^ma_j being uniformly bounded above for all m≥ 1 <cit.>. This order is best possible from a general lower bound on the star discrepancy by Schmidt <cit.>. Additionally, it has been shown in <cit.> that the Kronecker sequence is also a low-dispersion sequence if and only if α is a badly approximable number, i.e., α=[a_0;a_1,a_2,…] is irrational and a_m is uniformly bounded above for all m≥ 1. Beyond that, Kronecker sequences have recently been studied in terms of (week) Poissonian pair correlations <cit.>.

In this note, we prove the following result on the quasi-uniformity of Kronecker sequences. It turns out that the “if and only if” condition coincides with the one for the Kronecker sequence to be a low-dispersion sequence. As we will see, our elementary proof relies on a result on the three-gap theorem for Kronecker sequences due to Halton (1965).


    The Kronecker sequence =(x_i)_i=0,1,2,…, defined by (<ref>), is quasi-uniform over [0,1] if and only if α is a badly approximable number. 



    The van der Corput sequence, another well-known low-discrepancy sequence in dimension 1, can be easily proven to be quasi-uniform in any base b ≥ 2. In fact, the greedy packing algorithm from <cit.> reproduces the van der Corput sequence in base 2 by placing the first point at 1/2, and the mesh ratio ρ_n is bounded above by 2 for any n.




§ PROOF

As introduced already, let us denote the continued fraction of α>0 by [a_0;a_1,a_2,…], i.e.,

    α=a_0+1/ a_1+1/ a_2+1/⋱.

This continued fraction is finite if and only if α is rational. In such cases, the corresponding Kronecker sequence becomes periodic, with only finitely many distinct values appearing infinitely often. Consequently, there exists n_0≥ 1 such that the separation radius q_n equals 0 for all n≥ n_0, making the mesh ratio ρ_n unbounded. We will now proceed under the assumption that α is irrational, indicating an infinite continued fraction.

Let us introduce the following notation:

    α_0=α 1   and  α_m+1= 1/α_m 1,    m=0,1,2,….

In fact, it is easy to check that α_m=[0;a_m+1,a_m+2,…] for all m. Furthermore, let

    η_-1=1  and  η_m=∏_j=0^mα_m,    m=0,1,2,… ,


    s_0=1,   s_1=a_1,   and   s_m+2=a_m+2s_m+1+s_m,   m=0,1,2,… ,

and

    n_0=1,  and   n_m=s_m+s_m-1,   m=1,2,3,… .

Then the following result was proven by Halton <cit.> about the famous three-gap theorem for Kronecker sequences <cit.>.


    Let n_m≤ n< n_m+1 for some m≥ 0, and consider the first n points of the Kronecker sequence (<ref>) with an irrational α. Rearrange these points in ascending order and denote them by x^(0)≤ x^(1)≤⋯≤ x^(n-1) with x^(0)=0 and x^(n-1)<1=x^(n). Let n=n_m+hs_m+k with 0≤ h≤ a_m+1-1 and 0≤ k≤ s_m-1. Then, among the n gap lengths x^(1)-x^(0),x^(2)-x^(1),…,x^(n)-x^(n-1), there exist at most three distinct values. In particular, s_m-1+hs_m+k lengths are equal to η_m, s_m-k lengths are equal to η_m-1-hη_m, and k lengths are equal to η_m-1-(h+1)η_m.


Now we are ready to prove Theorem <ref>.

    First, we prove that the Kronecker sequence is quasi-uniform for any α being a badly approximable number. For some m≥ 0, let n=n_m+hs_m+k with 0≤ h≤ a_m+1-1 and 0≤ k≤ s_m-1. For the three gap lengths given in Lemma <ref>, we have η_m-1-hη_m=η_m+( η_m-1-(h+1)η_m), i.e., one length is the sum of the other two. Therefore, for the separation radius, we have
    
    q_n()     =1/2min_0≤ i<j<n|x_i-x_j| = 1/2min_0≤ i<n-1|x^(i+1)-x^(i)| ≥1/2min_0≤ i<n|x^(i+1)-x^(i)|
        = 1/2min{η_m, η_m-1-hη_m, η_m-1-(h+1)η_m}=1/2min{η_m, η_m-1-(h+1)η_m}.

    Similarly, for the fill distance, we have
    
    h_n()     =sup_x∈ [0,1]min_0≤ i<n|x-x_i|=max{1/2max_0≤ i<n-1|x^(i+1)-x^(i)|, |x^(n)-x^(n-1)|}
       ≤max_0≤ i<n|x^(i+1)-x^(i)|=max{η_m, η_m-1-hη_m, η_m-1-(h+1)η_m}=η_m-1-hη_m.

    These lead to an upper bound on the mesh ratio as
    
    ρ_n()     =h_n()/q_n()≤2(η_m-1-hη_m)/min{η_m, η_m-1-(h+1)η_m}= 2(1-hα_m)/min(α_m,1-(h+1)α_m).

    Since it immediately follows from the definition of α_m's that
    
    1/a_m+1+1<α_m<1/a_m+1+1/a_m+2,

    the mesh ratio is further bounded above by
    
    ρ_n()    ≤ 2max{1-hα_m/α_m, 1-hα_m/1-(h+1)α_m} = 2max{1/α_m-h, 1/ 1-1/1/α_m-h}
       ≤ 2max{ a_m+1+1-h, 1/ 1-1/ a_m+1+1/a_m+2-h}
       ≤ 2max{ a_m+1+1, a_m+2+1}≤ 2+2sup_j≥ 1a_j.

    Thus, if α is a badly approximable number, the mesh ratio is bounded by a constant C≤ 2+2sup_j≥ 1a_j for all n, showing that the corresponding Kronecker sequence is quasi-uniform.

    Next, we prove that the Kronecker sequence is not quasi-uniform if α is not a badly approximable number. For this, let us consider the case where n=n_m for m≥ 3, i.e., n=n_m+hs_m+k with h=k=0. Then, it follows from Lemma <ref> that there exist exactly two distinct values among the n gap lengths, which are η_m for s_m-1 gaps and η_m-1 for s_m gaps. Since we assume m≥ 3, we have s_m>s_m-1≥ 2. Therefore, for the separation radius, we have
    
    q_n()     =1/2min_0≤ i<j<n|x_i-x_j| = 1/2min_0≤ i<n-1|x^(i+1)-x^(i)| = 1/2min_0≤ i<n|x^(i+1)-x^(i)|
        = 1/2min{η_m, η_m-1}=1/2η_m.

    Similarly, for the fill distance, we have
    
    h_n()     =sup_x∈ [0,1]min_0≤ i<n|x-x_i|=max{1/2max_0≤ i<n-1|x^(i+1)-x^(i)|, |x^(n)-x^(n-1)|}
       ≥1/2max_0≤ i<n|x^(i+1)-x^(i)|=1/2max{η_m, η_m-1}=1/2η_m-1.

    This leads to a lower bound on the mesh ratio as
    
    ρ_n()     =h_n()/q_n()≥η_m-1/η_m= 1/α_m≥ a_m+1+1/a_m+2.

    Thus, we have shown that the mesh ratio cannot be uniformly bounded above in all n if a_m's are not uniformly bounded above, indicating that the corresponding Kronecker sequence is not quasi-uniform.




§ ACKNOWLEDGMENT

The author would like to thank Kosuke Suzuki for discussions and comments.

plain


