Completely uniformly distributed sequences based on de Bruijn sequences

By Emilio Almansi and Verónica Becher

Abstract

We study a construction published by Donald Knuth in 1965 yielding a completely uniformly distributed sequence of real numbers. Knuth’s work is based on de Bruijn sequences of increasing orders and alphabet sizes, which grow exponentially in each of the successive segments composing the generated sequence. In this work we present a similar, albeit simpler, construction using linearly increasing alphabet sizes, and we give an elementary proof showing that the generated sequence is also completely uniformly distributed. In addition, we present an alternative proof of the same result based on Weyl’s criterion.

1. Introduction

Let left-parenthesis x overbar Subscript i Baseline right-parenthesis Subscript i greater-than-or-equal-to 1 be an infinite sequence of k -dimensional vectors of real numbers. For a given set upper I subset-of-or-equal-to left-bracket 0 comma 1 right-parenthesis Superscript k , we denote by script upper A left-parenthesis x overbar Subscript 1 Baseline comma ellipsis comma x overbar Subscript upper N Baseline semicolon upper I right-parenthesis the number of indexes i in left-bracket 1 comma upper N right-bracket such that x overbar Subscript i lies in  upper I . A sequence left-parenthesis x overbar Subscript i Baseline right-parenthesis Subscript i greater-than-or-equal-to 1 of k -dimensional vectors in the unit cube is uniformly distributed if for every set upper I included in left-bracket 0 comma 1 right-parenthesis Superscript k ,

limit Underscript upper N right-arrow normal infinity Endscripts StartFraction 1 Over upper N EndFraction script upper A left-parenthesis x overbar Subscript 1 Baseline comma ellipsis comma x overbar Subscript upper N Baseline semicolon upper I right-parenthesis equals StartAbsoluteValue upper I EndAbsoluteValue comma

where StartAbsoluteValue upper I EndAbsoluteValue is the measure of upper I .

For the theory of uniform distribution see the monograph of Kuipers and Niederreiter Reference 15. Starting with a sequence left-parenthesis x Subscript i Baseline right-parenthesis Subscript i greater-than-or-equal-to 1 of real numbers in the unit interval, we define for every integer k greater-than-or-equal-to 1 the k -dimensional sequence left-parenthesis x overbar Subscript i Superscript left-parenthesis k right-parenthesis Baseline right-parenthesis Subscript i greater-than-or-equal-to 1 where x overbar Subscript i Superscript left-parenthesis k right-parenthesis Baseline equals left-parenthesis x Subscript i Baseline comma ellipsis comma x Subscript i plus k minus 1 Baseline right-parenthesis for i greater-than-or-equal-to 1 . The sequence left-parenthesis x Subscript i Baseline right-parenthesis Subscript i greater-than-or-equal-to 1 is said to be completely uniformly distributed if for every integer k greater-than-or-equal-to 1 , the sequence left-parenthesis x overbar Superscript left-parenthesis k right-parenthesis Baseline right-parenthesis Subscript i greater-than-or-equal-to 1 is uniformly distributed in the k -dimensional unit cube.

If a sequence is completely uniformly distributed, then it also satisfies many other statistical properties common to all random sequences; see the work of Franklin Reference 5. For example, for every fixed integer k , the probability of  k consecutive terms having any specific relative order is 1 slash k factorial .

The first reference to the concept of complete uniform distribution is the work of Korobov in 1948 Reference 8Reference 12Reference 13Reference 14, where he proves that the sequence left-parenthesis f Subscript alpha Baseline left-parenthesis n right-parenthesis mod 1 right-parenthesis Subscript n greater-than-or-equal-to 1 with

f Subscript alpha Baseline left-parenthesis z right-parenthesis equals sigma-summation Underscript k greater-than-or-equal-to 1 Endscripts e Superscript minus k Super Superscript alpha Superscript Baseline z Superscript k Baseline comma with alpha element-of left-parenthesis 1 comma 3 right-parenthesis

is completely uniformly distributed. Since then, there have been many constructions of completely uniformly distributed sequences; see Reference 15Reference 19Reference 21 and the references cited there. In Reference 16 Levin gives a lower bound of decay of discrepancy of completely uniformly distributed sequences and gives constructions, using nets obtained with Sobol matrices and using Halton sequences, which achieve this low discrepancy bound.

Independently of the school of Korobov, in 1965 Knuth Reference 7 gives a construction of a completely uniformly distributed sequence left-parenthesis x Subscript i Baseline right-parenthesis Subscript i greater-than-or-equal-to 1 of real numbers based on de Bruijn sequences of increasing orders and alphabet sizes. In each of the successive segments composing the sequence, the alphabet sizes of the underlying de Bruijn sequences increase exponentially. Knuth gives an elementary proof that the sequence left-parenthesis x Subscript i Baseline right-parenthesis Subscript i greater-than-or-equal-to 1 is completely uniformly distributed by reasoning about the binary representation of the rational numbers x Subscript i . These binary representations are immediate because the alphabet size is always a power of  2 .

In the present work we give a similar, albeit simpler, construction than the one given by Knuth in Reference 7 while preserving the property of complete uniform distribution. Our construction is based on de Bruijn sequences of linearly increasing orders and linearly increasing alphabet sizes. The argument used by Knuth to prove that his sequence is completely uniformly distributed does not hold in our case. We give two proofs: one is elementary, and the other is based on Weyl’s criterion. The construction and the proofs we present here can be generalized in a straightforward manner to other growths of alphabet sizes. A first version of this work appears in Reference 1.

It may be possible to construct completely uniformly distributed sequences with low discrepancy by using variants of de Bruijn sequences such as those considered by Becher and Carton in Reference 2 (nested perfect necklaces). In that work, they show that the binary expansion of the real number defined by Levin in Reference 17 using Pascal matrices is indeed the concatenation of such variants of de Bruijn sequences.

We finish this section with a short presentation of de Bruijn sequences. In Section 2 we present Knuth’s sequence, and we devote Section 3 to our construction.

As usual we write double-struck upper N double-struck comma double-struck upper Z double-struck comma double-struck upper R double-struck comma double-struck upper C to denote the sets of positive integers, integers, real numbers, and complex numbers, respectively.

1.1. de Bruijn sequences

A b -ary de Bruijn sequence of order  k is a sequence of length  b Superscript k which, when viewed as a cycle, contains every possible b -ary sequence of length  k exactly once as a contiguous subsequence. For example, listed next are two distinct binary de Bruijn sequences of order  3 :

StartLayout 1st Row 0 comma 0 comma 0 comma 1 comma 0 comma 1 comma 1 comma 1 semicolon 2nd Row 0 comma 0 comma 0 comma 1 comma 1 comma 1 comma 0 comma 1 period EndLayout

Every binary sequence of length 3 appears exactly once as a contiguous subsequence in each example. This includes those instances such as 1 comma 0 comma 0 which wrap around the right-hand end of the sequences.

Each b -ary de Bruijn sequence of order  k is the label of a Hamiltonian cycle in the directed graph upper G Subscript b comma k Baseline equals left-parenthesis upper V comma upper E right-parenthesis , where upper V is the set of all b -ary sequences of length  k and upper E equals left-brace left-parenthesis u comma v right-parenthesis colon u equals a 1 comma ellipsis comma a Subscript k Baseline comma v equals a 2 comma ellipsis comma a Subscript k Baseline comma c comma c in StartSet 0 comma ellipsis comma b minus 1 EndSet right-brace . Due to good properties of de Bruijn graphs, each b -ary de Bruijn sequence of order  k can also be identified with the label of an Eulerian cycle in upper G Subscript b comma k minus 1 . By the BEST theorem there are exactly left-parenthesis b factorial right-parenthesis Superscript b Super Superscript k minus 1 Baseline slash b Superscript k different b -ary de Bruijn sequences of order  k .

A b -ary Ford sequence of order k , denoted by upper F Superscript left-parenthesis b comma k right-parenthesis , is the lexicographically least b -ary de Bruijn sequence of order  k . In the example above, the first sequence is the binary Ford sequence of order 3 , or upper F Superscript left-parenthesis 2 comma 3 right-parenthesis Baseline equals 0 comma 0 comma 0 comma 1 comma 0 comma 1 comma 1 comma 1 . In Reference 6, Fredricksen and Maiorana introduce an algorithm for generating the b -ary Ford sequence of order  k , which has constant amortized running time; see Reference 20.

The name de Bruijn sequence came after the work of the Dutch mathematician N. G. de Bruijn Reference 4. A historical background can be read from Reference 3. Korobov made significant contributions in this area and constructed uniformly distributed sequences based on de Bruijn sequences Reference 9Reference 10Reference 11.

2. Knuth’s sequence

We follow Knuth’s presentation in Reference 7. Knuth’s sequence can be defined from any given family of de Bruijn sequences. Here, we use Ford sequences because they are conveniently defined and because they can be efficiently generated.

Definition.

Given n in double-struck upper N , let upper F Superscript left-parenthesis 2 Super Superscript n Superscript comma n right-parenthesis Baseline equals f 1 comma ellipsis comma f Subscript 2 Sub Superscript n squared Baseline denote the 2 Superscript n -ary Ford sequence of order  n . An upper A -sequence of order n , denoted by upper A Superscript left-parenthesis n right-parenthesis , is the finite sequence of rational numbers obtained by dividing every term in upper F Superscript left-parenthesis 2 Super Superscript n Superscript comma n right-parenthesis by 2 Superscript n :

upper A Superscript left-parenthesis n right-parenthesis Baseline equals StartFraction f 1 Over 2 Superscript n Baseline EndFraction comma StartFraction f 2 Over 2 Superscript n Baseline EndFraction comma ellipsis comma StartFraction f Subscript 2 Sub Superscript n squared Subscript Baseline Over 2 Superscript n Baseline EndFraction equals left-parenthesis StartFraction f Subscript i Baseline Over 2 Superscript n Baseline EndFraction right-parenthesis Subscript i equals 1 comma period period comma 2 Sub Superscript n squared Subscript Baseline period

A upper B -sequence of order n , denoted by upper B Superscript left-parenthesis n right-parenthesis , is the sequence obtained from the concatenation of n 2 Superscript 2 n copies of upper A Superscript left-parenthesis n right-parenthesis :

upper B Superscript left-parenthesis n right-parenthesis Baseline equals mathematical left-angle ModifyingBelow upper A Superscript left-parenthesis n right-parenthesis Baseline semicolon upper A Superscript left-parenthesis n right-parenthesis Baseline semicolon ellipsis semicolon upper A Superscript left-parenthesis n right-parenthesis Baseline With bottom-brace Underscript n 2 Superscript 2 n Baseline times Endscripts mathematical right-angle period

By construction, the size of upper A Superscript left-parenthesis n right-parenthesis is

StartAbsoluteValue upper A Superscript left-parenthesis n right-parenthesis Baseline EndAbsoluteValue equals StartAbsoluteValue upper F Superscript left-parenthesis 2 Super Superscript n Superscript comma n right-parenthesis Baseline EndAbsoluteValue equals 2 Superscript n squared

and the size of upper B Superscript left-parenthesis n right-parenthesis is

StartAbsoluteValue upper B Superscript left-parenthesis n right-parenthesis Baseline EndAbsoluteValue equals n 2 Superscript 2 n Baseline StartAbsoluteValue upper A Superscript left-parenthesis n right-parenthesis Baseline EndAbsoluteValue equals n 2 Superscript 2 n Baseline 2 Superscript n squared Baseline period

Notice that, for any given n , all terms in upper A Superscript left-parenthesis n right-parenthesis and in upper B Superscript left-parenthesis n right-parenthesis are numbers in the set StartSet 0 comma StartFraction 1 Over 2 Superscript n Baseline EndFraction comma StartFraction 2 Over 2 Superscript n Baseline EndFraction comma ellipsis comma StartFraction 2 Superscript n Baseline minus 1 Over 2 Superscript n Baseline EndFraction EndSet subset-of left-bracket 0 comma 1 right-parenthesis . For example, when n equals 2 ,

StartLayout 1st Row 1st Column Blank 2nd Column upper F Superscript left-parenthesis 4 comma 2 right-parenthesis Baseline equals 0 comma 0 comma 1 comma 0 comma 2 comma 0 comma 3 comma 1 comma 1 comma 2 comma 1 comma 3 comma 2 comma 2 comma 3 comma 3 comma 2nd Row 1st Column Blank 2nd Column upper A Superscript left-parenthesis 2 right-parenthesis Baseline equals StartFraction 0 Over 4 EndFraction comma StartFraction 0 Over 4 EndFraction comma one fourth comma StartFraction 0 Over 4 EndFraction comma two fourths comma StartFraction 0 Over 4 EndFraction comma three fourths comma one fourth comma one fourth comma two fourths comma one fourth comma three fourths comma two fourths comma two fourths comma three fourths comma three fourths comma 3rd Row 1st Column Blank 2nd Column upper B Superscript left-parenthesis 2 right-parenthesis Baseline equals mathematical left-angle ModifyingBelow upper A Superscript left-parenthesis 2 right-parenthesis Baseline semicolon ellipsis semicolon upper A Superscript left-parenthesis 2 right-parenthesis Baseline With bottom-brace Underscript 32 times Endscripts mathematical right-angle equals ModifyingBelow StartFraction 0 Over 4 EndFraction comma StartFraction 0 Over 4 EndFraction comma ellipsis comma three fourths comma three fourths With bottom-brace Underscript upper A Superscript left-parenthesis 2 right-parenthesis Baseline Endscripts comma ellipsis comma ModifyingBelow StartFraction 0 Over 4 EndFraction comma StartFraction 0 Over 4 EndFraction comma ellipsis comma three fourths comma three fourths With bottom-brace Underscript upper A Superscript left-parenthesis 2 right-parenthesis Baseline Endscripts comma EndLayout

and StartAbsoluteValue upper A Superscript left-parenthesis 2 right-parenthesis Baseline EndAbsoluteValue equals 16 , StartAbsoluteValue upper B Superscript left-parenthesis 2 right-parenthesis Baseline EndAbsoluteValue equals 512 .

Definition.

Knuth’s sequence, denoted by upper K , is the infinite sequence of rational numbers resulting from the concatenation of the sequences upper B Superscript left-parenthesis n right-parenthesis for n equals 1 comma 2 comma ellipsis :

upper K equals mathematical left-angle upper B Superscript left-parenthesis 1 right-parenthesis Baseline semicolon upper B Superscript left-parenthesis 2 right-parenthesis Baseline semicolon upper B Superscript left-parenthesis 3 right-parenthesis Baseline semicolon ellipsis mathematical right-angle period

Theorem (Knuth 1965, Reference 7, page 268).

The sequence upper K is completely uniformly distributed.

Knuth provides an elementary proof of this theorem. Two choices play an important role in his proof. One is that the number of repetitions of each upper A -sequence within a upper B -sequence is n 2 Superscript 2 n . To ensure complete uniform distribution it is sufficient that the number of repetitions of each upper A -sequence within a upper B -sequence grows faster than  2 Superscript 2 n . For instance, left ceiling log n right ceiling 2 Superscript 2 n suffices.

The other choice in Knuth’s construction is that the alphabet sizes of the Ford sequences grow exponentially as  2 Superscript n . This allows us to reason about the rational numbers comprised in the sequence upper K in terms of their binary representations. Knuth considers the distribution of the m most-significant bits of each of the terms in a 2 Superscript n -ary Ford sequence, where m less-than-or-equal-to n , see Reference 7, Lemma 2.

3. Main result

We now present the main contribution of this work, which is a variant of Knuth’s construction based on Ford sequences with linearly increasing alphabet sizes.

Definition.

Given n in double-struck upper N and a function t colon double-struck upper N right-arrow from bar double-struck upper N , let upper F Superscript left-parenthesis n comma n right-parenthesis Baseline equals f 1 comma ellipsis comma f Subscript n Sub Superscript n Baseline denote an n -ary Ford sequence of order  n . A upper C -sequence of order n , denoted by upper C Superscript left-parenthesis n right-parenthesis , is the finite sequence of rational numbers obtained by dividing each of the terms in upper F Superscript left-parenthesis n comma n right-parenthesis by n :

upper C Superscript left-parenthesis n right-parenthesis Baseline equals StartFraction f 1 Over n EndFraction comma StartFraction f 2 Over n EndFraction comma ellipsis comma StartFraction f Subscript n Sub Superscript n Subscript Baseline Over n EndFraction equals left-parenthesis StartFraction f Subscript i Baseline Over n EndFraction right-parenthesis Subscript i equals 1 comma period period comma n Sub Superscript n Subscript Baseline comma

and a upper D -sequence of order n , denoted by upper D Superscript left-parenthesis n comma t right-parenthesis , is the sequence obtained from the concatenation of t left-parenthesis n right-parenthesis consecutive copies of upper C Superscript left-parenthesis n right-parenthesis :

upper D Superscript left-parenthesis n comma t right-parenthesis Baseline equals mathematical left-angle ModifyingBelow upper C Superscript left-parenthesis n right-parenthesis Baseline semicolon upper C Superscript left-parenthesis n right-parenthesis Baseline semicolon ellipsis semicolon upper C Superscript left-parenthesis n right-parenthesis Baseline With bottom-brace Underscript t left-parenthesis n right-parenthesis times Endscripts mathematical right-angle period

The size of upper C Superscript left-parenthesis n right-parenthesis is

StartAbsoluteValue upper C Superscript left-parenthesis n right-parenthesis Baseline EndAbsoluteValue equals StartAbsoluteValue upper F Superscript left-parenthesis n comma n right-parenthesis Baseline EndAbsoluteValue equals n Superscript n Baseline comma

and the size of upper D Superscript left-parenthesis n comma t right-parenthesis is

StartAbsoluteValue upper D Superscript left-parenthesis n comma t right-parenthesis Baseline EndAbsoluteValue equals t left-parenthesis n right-parenthesis StartAbsoluteValue upper C Superscript left-parenthesis n right-parenthesis Baseline EndAbsoluteValue equals t left-parenthesis n right-parenthesis n Superscript n Baseline period

For any given n , all terms in upper C Superscript left-parenthesis n right-parenthesis and upper D Superscript left-parenthesis n comma t right-parenthesis are numbers in the set StartSet 0 comma StartFraction 1 Over n EndFraction comma StartFraction 2 Over n EndFraction comma ellipsis comma StartFraction n minus 1 Over n EndFraction EndSet subset-of left-bracket 0 comma 1 right-parenthesis . The key difference between the way upper C -sequences are constructed when compared to upper A -sequences from the previous section is that, as the order of the sequence grows, the alphabet size for the underlying Ford sequence grows linearly ( 1 comma 2 comma 3 comma 4 comma ellipsis ) rather than exponentially ( 2 comma 4 comma 8 comma 16 comma ellipsis ). For example, when n equals 3 and t left-parenthesis n right-parenthesis equals n :

StartLayout 1st Row 1st Column Blank 2nd Column upper F Superscript left-parenthesis 3 comma 3 right-parenthesis Baseline equals 0 comma 0 comma 0 comma 1 comma 0 comma 0 comma 2 comma 0 comma 1 comma 1 comma 0 comma 1 comma 2 comma 0 comma 2 comma 1 comma 0 comma 2 comma 2 comma 1 comma 1 comma 1 comma 2 comma 1 comma 2 comma 2 comma 2 comma 2nd Row 1st Column Blank 2nd Column upper C Superscript left-parenthesis 3 right-parenthesis Baseline equals StartFraction 0 Over 3 EndFraction comma StartFraction 0 Over 3 EndFraction comma StartFraction 0 Over 3 EndFraction comma one third comma StartFraction 0 Over 3 EndFraction comma StartFraction 0 Over 3 EndFraction comma two thirds comma StartFraction 0 Over 3 EndFraction comma one third comma one third comma StartFraction 0 Over 3 EndFraction comma one third comma two thirds comma StartFraction 0 Over 3 EndFraction comma two thirds comma one third comma StartFraction 0 Over 3 EndFraction comma two thirds comma two thirds comma one third comma one third comma one third comma two thirds comma one third comma two thirds comma two thirds comma two thirds comma 3rd Row 1st Column Blank 2nd Column upper D Superscript left-parenthesis 3 comma i d right-parenthesis Baseline equals mathematical left-angle upper C Superscript left-parenthesis 3 right-parenthesis Baseline semicolon upper C Superscript left-parenthesis 3 right-parenthesis Baseline semicolon upper C Superscript left-parenthesis 3 right-parenthesis Baseline mathematical right-angle equals ModifyingBelow StartFraction 0 Over 3 EndFraction comma StartFraction 0 Over 3 EndFraction comma ellipsis comma two thirds comma two thirds With bottom-brace Underscript upper C Superscript left-parenthesis 3 right-parenthesis Baseline Endscripts comma ModifyingBelow StartFraction 0 Over 3 EndFraction comma StartFraction 0 Over 3 EndFraction comma ellipsis comma two thirds comma two thirds With bottom-brace Underscript upper C Superscript left-parenthesis 3 right-parenthesis Baseline Endscripts comma ModifyingBelow StartFraction 0 Over 3 EndFraction comma StartFraction 0 Over 3 EndFraction comma ellipsis comma two thirds comma two thirds With bottom-brace Underscript upper C Superscript left-parenthesis 3 right-parenthesis Baseline Endscripts comma EndLayout

and StartAbsoluteValue upper C Superscript left-parenthesis 3 right-parenthesis Baseline EndAbsoluteValue equals 27 , StartAbsoluteValue upper D Superscript left-parenthesis 3 comma i d right-parenthesis Baseline EndAbsoluteValue equals 81 .

Definition.

Given t colon double-struck upper N right-arrow from bar double-struck upper N , the sequence upper L Superscript left-parenthesis t right-parenthesis is the infinite sequence of real numbers obtained from the concatenation of the sequences upper D Superscript left-parenthesis n comma t right-parenthesis for n equals 1 comma 2 comma ellipsis :

upper L Superscript left-parenthesis t right-parenthesis Baseline equals mathematical left-angle upper D Superscript left-parenthesis 1 comma t right-parenthesis Baseline semicolon upper D Superscript left-parenthesis 2 comma t right-parenthesis Baseline semicolon upper D Superscript left-parenthesis 3 comma t right-parenthesis Baseline semicolon ellipsis mathematical right-angle period

Theorem 1.

If t colon double-struck upper N right-arrow from bar double-struck upper N is a nondecreasing function and limit Underscript n right-arrow normal infinity Endscripts n slash t left-parenthesis n right-parenthesis equals 0 , then the sequence upper L Superscript left-parenthesis t right-parenthesis is completely uniformly distributed.

Example.

If t left-parenthesis n right-parenthesis equals s q left-parenthesis n right-parenthesis equals n squared , then

upper L Superscript left-parenthesis s q right-parenthesis Baseline equals mathematical left-angle upper C Superscript left-parenthesis 1 right-parenthesis Baseline semicolon ModifyingBelow upper C Superscript left-parenthesis 2 right-parenthesis Baseline semicolon ellipsis semicolon upper C Superscript left-parenthesis 2 right-parenthesis Baseline With bottom-brace Underscript 4 copies Endscripts semicolon ModifyingBelow upper C Superscript left-parenthesis 3 right-parenthesis Baseline semicolon ellipsis semicolon upper C Superscript left-parenthesis 3 right-parenthesis Baseline With bottom-brace Underscript 9 copies Endscripts semicolon ellipsis mathematical right-angle comma

and upper L Superscript left-parenthesis s q right-parenthesis is completely uniformly distributed.

3.1. Proof of Theorem 1

Within the current section, let t colon double-struck upper N right-arrow from bar double-struck upper N be an arbitrary but fixed function. For convenience we write upper D Superscript left-parenthesis n right-parenthesis and upper L in place of upper D Superscript left-parenthesis n comma t right-parenthesis and upper L Superscript left-parenthesis t right-parenthesis . Consider a prefix of upper L of length upper N , denoted by upper L Subscript 1 colon upper N . Let p comma q comma r be the integers determined by upper N such that

upper L Subscript 1 colon upper N Baseline equals mathematical left-angle upper D Superscript left-parenthesis 1 right-parenthesis Baseline semicolon ellipsis semicolon upper D Superscript left-parenthesis r minus 1 right-parenthesis Baseline semicolon ModifyingBelow upper C Superscript left-parenthesis r right-parenthesis Baseline semicolon ellipsis semicolon upper C Superscript left-parenthesis r right-parenthesis Baseline With bottom-brace Underscript q times Endscripts semicolon upper C Subscript 1 colon p Superscript left-parenthesis r right-parenthesis Baseline mathematical right-angle comma

where 0 less-than-or-equal-to q less-than t left-parenthesis r right-parenthesis and 1 less-than-or-equal-to p less-than-or-equal-to r Superscript r . Here, r is the order of the rightmost, possibly incomplete upper D -sequence present in upper L Subscript 1 colon upper N . The number q is the amount of complete upper C -sequences of order r appearing before the rightmost, possibly incomplete upper C -sequence, while p is the amount of terms in it. Thus,

StartLayout 1st Row with Label left-parenthesis 1 right-parenthesis EndLabel StartLayout 1st Row 1st Column upper N 2nd Column equals sigma-summation Underscript s equals 1 Overscript r minus 1 Endscripts StartAbsoluteValue upper D Superscript left-parenthesis s right-parenthesis Baseline EndAbsoluteValue plus q StartAbsoluteValue upper C Superscript left-parenthesis r right-parenthesis Baseline EndAbsoluteValue plus p equals sigma-summation Underscript s equals 1 Overscript r minus 1 Endscripts t left-parenthesis s right-parenthesis s Superscript s Baseline plus q r Superscript r Baseline plus p period EndLayout EndLayout

Let k be a positive integer, and let upper I equals left-bracket u 1 comma v 1 right-parenthesis times midline-horizontal-ellipsis times left-bracket u Subscript k Baseline comma v Subscript k Baseline right-parenthesis be a set such that upper I subset-of-or-equal-to left-bracket 0 comma 1 right-parenthesis Superscript k . Let upper N range freely over the natural numbers, and let the quantity nu Subscript upper N denote the number of windows of upper L of size k starting at indices i equals 1 comma ellipsis comma upper N that belong to the set upper I :

nu Subscript upper N Baseline equals script upper A left-parenthesis w overbar Subscript 1 Baseline comma ellipsis comma w overbar Subscript upper N Baseline semicolon upper I right-parenthesis comma

where w overbar Subscript i Baseline equals left-parenthesis upper L Subscript i Baseline comma ellipsis comma upper L Subscript i plus k minus 1 Baseline right-parenthesis for i equals 1 comma ellipsis comma upper N .

Consider sufficiently large values of upper N such that k less-than r . This is always possible since r is an unbounded, nondecreasing function of upper N . We can decompose upper L Subscript 1 colon upper N into four consecutive sections; namely, sequences upper S Superscript left-parenthesis 1 right-parenthesis , upper S Superscript left-parenthesis 2 right-parenthesis , upper S Superscript left-parenthesis 3 right-parenthesis , and upper S Superscript left-parenthesis 4 right-parenthesis :

StartLayout 1st Row 1st Column upper L Subscript 1 colon upper N 2nd Column equals mathematical left-angle upper S Superscript left-parenthesis 1 right-parenthesis Baseline semicolon upper S Superscript left-parenthesis 2 right-parenthesis Baseline semicolon upper S Superscript left-parenthesis 3 right-parenthesis Baseline semicolon upper S Superscript left-parenthesis 4 right-parenthesis Baseline mathematical right-angle comma where 2nd Row 1st Column upper S Superscript left-parenthesis 1 right-parenthesis 2nd Column equals mathematical left-angle upper D Superscript left-parenthesis 1 right-parenthesis Baseline semicolon upper D Superscript left-parenthesis 2 right-parenthesis Baseline semicolon ellipsis semicolon upper D Superscript left-parenthesis k minus 1 right-parenthesis Baseline mathematical right-angle comma 3rd Row 1st Column upper S Superscript left-parenthesis 2 right-parenthesis 2nd Column equals mathematical left-angle upper D Superscript left-parenthesis k right-parenthesis Baseline semicolon upper D Superscript left-parenthesis k plus 1 right-parenthesis Baseline semicolon ellipsis semicolon upper D Superscript left-parenthesis r minus 1 right-parenthesis Baseline mathematical right-angle comma 4th Row 1st Column upper S Superscript left-parenthesis 3 right-parenthesis 2nd Column equals mathematical left-angle ModifyingBelow upper C Superscript left-parenthesis r right-parenthesis Baseline semicolon ellipsis semicolon upper C Superscript left-parenthesis r right-parenthesis Baseline With bottom-brace Underscript q times Endscripts mathematical right-angle comma 5th Row 1st Column upper S Superscript left-parenthesis 4 right-parenthesis 2nd Column equals upper C Subscript 1 colon p Superscript left-parenthesis r right-parenthesis Baseline period EndLayout

Notice that upper S Superscript left-parenthesis 1 right-parenthesis and upper S Superscript left-parenthesis 3 right-parenthesis can potentially be empty, such as when k equals 1 or q equals 0 , respectively.

We denote the cumulative sums of the sizes of the sequences defined above as n 0 equals 0 , and n Subscript j Baseline equals n Subscript j minus 1 Baseline plus StartAbsoluteValue upper S Superscript left-parenthesis j right-parenthesis Baseline EndAbsoluteValue for j equals 1 comma 2 comma 3 comma 4 . Now, we can similarly decompose nu Subscript upper N into five parts. If we let

w overbar Subscript i Baseline equals left-parenthesis upper L Subscript i Baseline comma ellipsis comma upper L Subscript i plus k minus 1 Baseline right-parenthesis

for i equals 1 ellipsis upper N , then

StartLayout 1st Row 1st Column nu Subscript upper N 2nd Column equals nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis Baseline plus nu Subscript upper N Superscript left-parenthesis 2 right-parenthesis Baseline plus nu Subscript upper N Superscript left-parenthesis 3 right-parenthesis Baseline plus nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline plus epsilon Subscript b Baseline comma where 2nd Row 1st Column nu Subscript upper N Superscript left-parenthesis j right-parenthesis 2nd Column equals script upper A left-parenthesis w overbar Subscript 1 plus n Sub Subscript j minus 1 Subscript Baseline comma ellipsis comma w overbar Subscript n Sub Subscript j Subscript minus k plus 1 Baseline semicolon upper I right-parenthesis EndLayout

for some epsilon Subscript b Baseline less-than-or-equal-to 3 left-parenthesis k minus 1 right-parenthesis .

For each j equals 1 comma 2 comma 3 comma 4 , the quantity nu Subscript upper N Superscript left-parenthesis j right-parenthesis accounts for windows contained entirely within the sequence upper S Superscript left-parenthesis j right-parenthesis , and epsilon Subscript b accounts for all windows crossing any of the three borders between the four sections. This is enough to account for all possible windows, since any given window is either entirely contained in some section or it starts at a given section and ends at a subsequent one, thereby crossing a border.

We can rewrite the value of each nu Subscript upper N Superscript left-parenthesis j right-parenthesis in terms of windows over each sequence  upper S Superscript left-parenthesis j right-parenthesis . If we let

s overbar Subscript i Superscript left-parenthesis j right-parenthesis Baseline equals left-parenthesis upper S Subscript i Superscript left-parenthesis j right-parenthesis Baseline comma ellipsis comma upper S Subscript i plus k minus 1 Superscript left-parenthesis j right-parenthesis Baseline right-parenthesis

for j equals 1 comma 2 comma 3 comma 4 and i equals 1 comma ellipsis comma StartAbsoluteValue upper S Superscript left-parenthesis j right-parenthesis Baseline EndAbsoluteValue minus k plus 1 , then

StartLayout 1st Row with Label left-parenthesis 2 right-parenthesis EndLabel nu Subscript upper N Superscript left-parenthesis j right-parenthesis Baseline equals script upper A left-parenthesis s overbar Subscript 1 Superscript left-parenthesis j right-parenthesis Baseline comma ellipsis comma s overbar Subscript StartAbsoluteValue upper S Sub Superscript left-parenthesis j right-parenthesis Subscript EndAbsoluteValue minus k plus 1 Superscript left-parenthesis j right-parenthesis Baseline semicolon upper I right-parenthesis period EndLayout

Before obtaining more precise expressions for these quantities, we state the following three technical propositions.

Proposition 2.

If n is in double-struck upper N and x comma y are in double-struck upper R such that left-bracket x comma y right-parenthesis subset-of-or-equal-to left-bracket 0 comma n right-parenthesis , then the number of integers from the set StartSet 0 comma 1 comma ellipsis comma n minus 1 EndSet contained in left-bracket x comma y right-parenthesis is equal to y minus x plus epsilon for some epsilon in  left-parenthesis negative 1 comma 1 right-parenthesis .

Proof.

Since 0 less-than-or-equal-to y , there are exactly left ceiling y right ceiling equals y plus epsilon Subscript y nonnegative integers in the set left-bracket 0 comma y right-parenthesis for some epsilon Subscript y in left-bracket 0 comma 1 right-parenthesis . Similarly for x , there are exactly left ceiling x right ceiling equals x plus epsilon Subscript x nonnegative integers in the set left-bracket 0 comma x right-parenthesis for some epsilon Subscript x in left-bracket 0 comma 1 right-parenthesis . The difference between these two quantities is equal to the number of nonnegative integers contained in the set left-bracket x comma y right-parenthesis , which is y minus x plus left-parenthesis epsilon Subscript y Baseline minus epsilon Subscript x Baseline right-parenthesis . Observing that left-parenthesis epsilon Subscript y Baseline minus epsilon Subscript x Baseline right-parenthesis in left-parenthesis negative 1 comma 1 right-parenthesis and that all nonnegative integers between x and y belong to the set StartSet 0 comma 1 comma ellipsis comma n minus 1 EndSet , the proof is complete.

Proposition 3.

If k is a positive integer and a 1 comma a 2 comma ellipsis comma a Subscript k Baseline and b 1 comma b 2 comma ellipsis comma b Subscript k Baseline are two sequences of real numbers of length  k , then the product of their element-by-element sums can be expressed as follows:

product Underscript d equals 1 Overscript k Endscripts a Subscript d Baseline plus b Subscript d Baseline equals product Underscript d equals 1 Overscript k Endscripts a Subscript d Baseline plus sigma-summation Underscript j equals 1 Overscript 2 Superscript k Baseline minus 1 Endscripts left-bracket product Underscript d equals 1 Overscript k Endscripts Start 2 By 2 Matrix 1st Row 1st Column a Subscript d Baseline 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column b Subscript d Baseline 2nd Column otherwise EndMatrix right-bracket period

Proof.

By induction on k . First, notice that the property holds for  k equals 1 :

StartLayout 1st Row 1st Column Blank 2nd Column product Underscript d equals 1 Overscript 1 Endscripts a Subscript d Baseline plus b Subscript d Baseline equals a 1 plus b 1 and 2nd Row 1st Column Blank 2nd Column product Underscript d equals 1 Overscript 1 Endscripts a Subscript d Baseline plus sigma-summation Underscript j equals 1 Overscript 1 Endscripts left-bracket product Underscript d equals 1 Overscript 1 Endscripts Start 2 By 2 Matrix 1st Row 1st Column a Subscript d Baseline 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column b Subscript d Baseline 2nd Column otherwise EndMatrix right-bracket equals a 1 plus b 1 period EndLayout

Next, we see that the inductive step holds for any k . First,

StartLayout 1st Row 1st Column product Underscript d equals 1 Overscript k plus 1 Endscripts a Subscript d plus b Subscript d 2nd Column equals left-parenthesis a Subscript k plus 1 Baseline plus b Subscript k plus 1 Baseline right-parenthesis product Underscript d equals 1 Overscript k Endscripts a Subscript d Baseline plus b Subscript d Baseline comma and by upper I period upper H period 2nd Row 1st Column Blank 2nd Column equals left-parenthesis a Subscript k plus 1 Baseline plus b Subscript k plus 1 Baseline right-parenthesis left-bracket product Underscript d equals 1 Overscript k Endscripts a Subscript d Baseline plus sigma-summation Underscript j equals 1 Overscript 2 Superscript k Baseline minus 1 Endscripts left-bracket product Underscript d equals 1 Overscript k Endscripts Start 2 By 2 Matrix 1st Row 1st Column a Subscript d Baseline 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column b Subscript d Baseline 2nd Column otherwise EndMatrix right-bracket right-bracket 3rd Row 1st Column Blank 2nd Column equals product Underscript d equals 1 Overscript k plus 1 Endscripts a Subscript d Baseline plus a Subscript k plus 1 Baseline sigma-summation Underscript j equals 1 Overscript 2 Superscript k Baseline minus 1 Endscripts left-bracket product Underscript d equals 1 Overscript k Endscripts Start 2 By 2 Matrix 1st Row 1st Column a Subscript d Baseline 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column b Subscript d Baseline 2nd Column otherwise EndMatrix right-bracket 4th Row 1st Column Blank 2nd Column plus b Subscript k plus 1 Baseline product Underscript d equals 1 Overscript k Endscripts a Subscript d Baseline plus b Subscript k plus 1 Baseline sigma-summation Underscript j equals 1 Overscript 2 Superscript k Baseline minus 1 Endscripts left-bracket product Underscript d equals 1 Overscript k Endscripts Start 2 By 2 Matrix 1st Row 1st Column a Subscript d Baseline 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column b Subscript d Baseline 2nd Column otherwise EndMatrix right-bracket period EndLayout

Since for every j equals 1 comma ellipsis comma 2 Superscript k Baseline minus 1 the value left floor StartFraction j Over 2 Superscript k Baseline EndFraction right floor equals 0 and is therefore even, we can add the factor a Subscript k plus 1 to the product in the second term simply by raising the upper limit to k plus 1 . Similarly, in the fourth term we can add the factor b Subscript k plus 1 to the product by raising the upper limit to k plus 1 and changing the limits in the sum to j equals left-parenthesis 2 Superscript k Baseline plus 1 right-parenthesis ellipsis left-parenthesis 2 Superscript k Baseline plus 2 Superscript k Baseline minus 1 right-parenthesis . This is true because adding 2 Superscript k to j does not change the value of left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor for any d less-than-or-equal-to k , but when d equals k plus 1 the value left floor StartFraction j Over 2 Superscript k Baseline EndFraction right floor equals 1 and is therefore odd. The third term can be rewritten as a similar product for a value of j equals 2 Superscript k , and by substituting it into the equation above,

StartLayout 1st Row 1st Column product Underscript d equals 1 Overscript k plus 1 Endscripts a Subscript d plus b Subscript d 2nd Column equals product Underscript d equals 1 Overscript k plus 1 Endscripts a Subscript d Baseline plus sigma-summation Underscript j equals 1 Overscript 2 Superscript k Baseline minus 1 Endscripts left-bracket product Underscript d equals 1 Overscript k plus 1 Endscripts Start 2 By 2 Matrix 1st Row 1st Column a Subscript d Baseline 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column b Subscript d Baseline 2nd Column otherwise EndMatrix right-bracket 2nd Row 1st Column Blank 2nd Column plus sigma-summation Underscript j equals 2 Superscript k Baseline Overscript 2 Superscript k Endscripts left-bracket product Underscript d equals 1 Overscript k plus 1 Endscripts Start 2 By 2 Matrix 1st Row 1st Column a Subscript d Baseline 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column b Subscript d Baseline 2nd Column otherwise EndMatrix right-bracket 3rd Row 1st Column Blank 2nd Column plus sigma-summation Underscript j equals 2 Superscript k Baseline plus 1 Overscript 2 Superscript k Baseline plus 2 Superscript k minus 1 Endscripts left-bracket product Underscript d equals 1 Overscript k Endscripts Start 2 By 2 Matrix 1st Row 1st Column a Subscript d Baseline 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column b Subscript d Baseline 2nd Column otherwise EndMatrix right-bracket 4th Row 1st Column Blank 2nd Column equals product Underscript d equals 1 Overscript k plus 1 Endscripts a Subscript d Baseline plus sigma-summation Underscript j equals 1 Overscript 2 Superscript k plus 1 Baseline minus 1 Endscripts left-bracket product Underscript d equals 1 Overscript k plus 1 Endscripts Start 2 By 2 Matrix 1st Row 1st Column a Subscript d Baseline 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column b Subscript d Baseline 2nd Column otherwise EndMatrix right-bracket comma EndLayout

which completes the proof.

Proposition 4.

Given n in double-struck upper N , the following holds:

sigma-summation Underscript i equals 1 Overscript n Endscripts i Superscript i minus 1 Baseline less-than-or-equal-to 2 n Superscript n minus 1 Baseline period

Proof.

By induction on n . The property holds for n equals 1 and n equals 2 :

sigma-summation Underscript i equals 1 Overscript 1 Endscripts i Superscript i minus 1 Baseline less-than-or-equal-to 2 comma sigma-summation Underscript i equals 1 Overscript 2 Endscripts i Superscript i minus 1 Baseline less-than-or-equal-to 4

and the inductive step holds for n greater-than-or-equal-to 2 :

sigma-summation Underscript i equals 1 Overscript n plus 1 Endscripts i Superscript i minus 1 Baseline equals ModifyingBelow sigma-summation Underscript i equals 1 Overscript n Endscripts i Superscript i minus 1 Baseline With bottom-brace Underscript StartLayout 1st Row 1st Column Blank 2nd Column less-than-or-equal-to 2 n Superscript n minus 1 Baseline 2nd Row 1st Column Blank 2nd Column by upper I period upper H period EndLayout Endscripts plus left-parenthesis n plus 1 right-parenthesis Superscript n Baseline less-than-or-equal-to n n Superscript n minus 1 Baseline plus left-parenthesis n plus 1 right-parenthesis Superscript n Baseline less-than-or-equal-to 2 left-parenthesis n plus 1 right-parenthesis Superscript n

Therefore, the property holds for all n in double-struck upper N .

We now obtain an expression for the number of windows of a upper C -sequence which are contained in the set upper I . This is useful for evaluating nu Subscript upper N .

Lemma 5.

Given a positive integer k and a set upper I equals left-bracket u 1 comma v 1 right-parenthesis times midline-horizontal-ellipsis times left-bracket u Subscript k Baseline comma v Subscript k Baseline right-parenthesis where upper I subset-of-or-equal-to left-bracket 0 comma 1 right-parenthesis Superscript k , let n in double-struck upper N such that k less-than-or-equal-to n and consider the sequence upper C Superscript left-parenthesis n right-parenthesis as a cyclic sequence. If we let c overbar Subscript i Baseline equals left-parenthesis upper C Subscript i Superscript left-parenthesis n right-parenthesis Baseline comma ellipsis comma upper C Subscript i plus k minus 1 Superscript left-parenthesis n right-parenthesis Baseline right-parenthesis for i equals 1 comma ellipsis comma n Superscript n , then the number of windows of size k from the sequence upper C Superscript left-parenthesis n right-parenthesis that lie in upper I is

script upper A left-parenthesis c overbar Subscript 1 Baseline comma ellipsis comma c overbar Subscript n Sub Superscript n Subscript Baseline semicolon upper I right-parenthesis equals n Superscript n Baseline StartAbsoluteValue upper I EndAbsoluteValue plus n Superscript n minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon

for some epsilon in left-parenthesis negative 1 comma 1 right-parenthesis .

Proof.

First, notice that any given window is contained in the set upper I if and only if the following is true:

StartLayout 1st Row StartLayout 1st Row 1st Column c overbar Subscript i Baseline element-of upper I long left right double arrow 2nd Column u 1 less-than-or-equal-to 3rd Column upper C Subscript i Superscript left-parenthesis n right-parenthesis 4th Column less-than v 1 2nd Row 1st Column Blank 2nd Column Blank 3rd Column vertical-ellipsis 4th Column Blank 3rd Row 1st Column Blank 2nd Column u Subscript k Baseline less-than-or-equal-to 3rd Column upper C Subscript i plus k minus 1 Superscript left-parenthesis n right-parenthesis 4th Column less-than v Subscript k Baseline comma EndLayout EndLayout

where i equals 1 comma ellipsis comma n Superscript n and indices are taken modulo n Superscript n .

Since all terms in upper C Superscript left-parenthesis n right-parenthesis are numbers in the set StartSet 0 comma StartFraction 1 Over n EndFraction comma ellipsis comma StartFraction n minus 1 Over n EndFraction EndSet , we multiply both sides of each inequality by n , allowing us to reason about integers belonging to a Ford sequence instead of rational numbers. We obtain the following:

StartLayout 1st Row StartLayout 1st Row 1st Column c overbar Subscript i Baseline element-of upper I long left right double arrow 2nd Column n u 1 less-than-or-equal-to 3rd Column upper F Subscript i Superscript left-parenthesis n comma n right-parenthesis 4th Column less-than n v 1 2nd Row 1st Column Blank 2nd Column Blank 3rd Column vertical-ellipsis 4th Column Blank 3rd Row 1st Column Blank 2nd Column n u Subscript k Baseline less-than-or-equal-to 3rd Column upper F Subscript i plus k minus 1 Superscript left-parenthesis n comma n right-parenthesis 4th Column less-than n v Subscript k Baseline period EndLayout EndLayout

According to Proposition 2, for each inequality above with d equals 1 comma ellipsis comma k there are exactly n v Subscript d minus n u Subscript d plus epsilon Subscript d possible solutions in the set StartSet 0 comma 1 comma ellipsis comma n minus 1 EndSet for some value epsilon Subscript d in left-parenthesis negative 1 comma 1 right-parenthesis . This yields a total of

product Underscript d equals 1 Overscript k Endscripts left-bracket n left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis plus epsilon Subscript d Baseline right-bracket

possible solutions to the system of inequalities. Each solution, when seen as an n -ary sequence of length  k , appears exactly n Superscript n minus k times as a contiguous subsequence in upper F Superscript left-parenthesis n comma n right-parenthesis . This is true because there are n Superscript n minus k ways of extending an n -ary sequence of length k to one of length n and, by construction, each of these appears exactly once in upper F Superscript left-parenthesis n comma n right-parenthesis when viewed as a cycle. Since i ranges exactly once over each possible window of upper F Superscript left-parenthesis n comma n right-parenthesis , then

StartLayout 1st Row with Label left-parenthesis 3 right-parenthesis EndLabel StartLayout 1st Row 1st Column script upper A left-parenthesis c overbar Subscript 1 Baseline comma ellipsis comma c overbar Subscript n Sub Superscript n Subscript Baseline semicolon upper I right-parenthesis 2nd Column equals n Superscript n minus k Baseline product Underscript d equals 1 Overscript k Endscripts left-bracket n left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis plus epsilon Subscript d Baseline right-bracket equals n Superscript n Baseline product Underscript d equals 1 Overscript k Endscripts left-bracket left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis plus epsilon Subscript d Baseline slash n right-bracket period EndLayout EndLayout Using Proposition 3, we can expand this into the following:

StartLayout 1st Row with Label left-parenthesis 4 right-parenthesis EndLabel StartLayout 1st Row 1st Column n Superscript n Baseline product Underscript d equals 1 Overscript k Endscripts left-bracket left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis plus epsilon Subscript d Baseline slash n right-bracket 2nd Column equals n Superscript n Baseline product Underscript d equals 1 Overscript k Endscripts left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis 2nd Row 1st Column Blank 2nd Column plus n Superscript n Baseline sigma-summation Underscript j equals 1 Overscript 2 Superscript k Baseline minus 1 Endscripts left-bracket product Underscript d equals 1 Overscript k Endscripts Start 2 By 2 Matrix 1st Row 1st Column left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column epsilon Subscript d Baseline slash n 2nd Column otherwise EndMatrix right-bracket period EndLayout EndLayout

If we define epsilon prime Subscript j for j equals 1 comma ellipsis comma 2 Superscript k Baseline minus 1 as

epsilon prime Subscript j Baseline slash n equals product Underscript d equals 1 Overscript k Endscripts Start 2 By 2 Matrix 1st Row 1st Column left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis 2nd Column left floor StartFraction j Over 2 Superscript d minus 1 Baseline EndFraction right floor is even 2nd Row 1st Column epsilon Subscript d Baseline slash n 2nd Column otherwise EndMatrix comma then, for each j , the value epsilon prime Subscript j is in left-parenthesis negative 1 comma 1 right-parenthesis . This is true because the product on the right-hand side is composed of terms left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis in left-parenthesis negative 1 comma 1 right-parenthesis and epsilon Subscript d Baseline slash n in left-parenthesis negative 1 slash n comma 1 slash n right-parenthesis and, since j greater-than 0 , there is always at least one term of the second kind. Given that

StartAbsoluteValue upper I EndAbsoluteValue equals product Underscript d equals 1 Overscript k Endscripts left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis comma

we can further simplify equation Equation 4 to get

StartLayout 1st Row with Label left-parenthesis 5 right-parenthesis EndLabel n Superscript n Baseline product Underscript d equals 1 Overscript k Endscripts left-bracket left-parenthesis v Subscript d Baseline minus u Subscript d Baseline right-parenthesis plus epsilon Subscript d Baseline slash n right-bracket equals n Superscript n Baseline StartAbsoluteValue upper I EndAbsoluteValue plus n Superscript n Baseline sigma-summation Underscript j equals 1 Overscript 2 Superscript k Baseline minus 1 Endscripts epsilon Subscript j Superscript prime Baseline slash n period EndLayout Finally, since minus left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis less-than sigma-summation Underscript j equals 1 Overscript 2 Superscript k Baseline minus 1 Endscripts epsilon Subscript j Superscript prime Baseline less-than left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis , there exist some epsilon in left-parenthesis negative 1 comma 1 right-parenthesis such that

sigma-summation Underscript j equals 1 Overscript 2 Superscript k Baseline minus 1 Endscripts epsilon Subscript j Superscript prime Baseline equals left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon comma

and hence, by Equation 3 and Equation 5,

script upper A left-parenthesis c overbar Subscript 1 Baseline comma ellipsis comma c overbar Subscript n Sub Superscript n Subscript Baseline semicolon upper I right-parenthesis equals n Superscript n Baseline StartAbsoluteValue upper I EndAbsoluteValue plus n Superscript n minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon period

We can now give the proof of our main result.

Proof of Theorem 1 .

Let k be a positive integer, and let upper I equals left-bracket u 1 comma v 1 right-parenthesis times midline-horizontal-ellipsis times left-bracket u Subscript k Baseline comma v Subscript k Baseline right-parenthesis be a set such that upper I subset-of-or-equal-to left-bracket 0 comma 1 right-parenthesis Superscript k . Let upper N range freely over the natural numbers. We now obtain an expression for nu Subscript upper N Baseline slash upper N and compute its limit when upper N right-arrow normal infinity .

Recall the following definitions:

StartLayout 1st Row 1st Column nu Subscript upper N Superscript left-parenthesis 2 right-parenthesis 2nd Column equals script upper A left-parenthesis s overbar Subscript 1 Superscript left-parenthesis 2 right-parenthesis Baseline comma ellipsis comma s overbar Subscript StartAbsoluteValue upper S Sub Superscript left-parenthesis 2 right-parenthesis Subscript EndAbsoluteValue minus k plus 1 Superscript left-parenthesis 2 right-parenthesis Baseline semicolon upper I right-parenthesis comma 2nd Row 1st Column nu Subscript upper N Superscript left-parenthesis 3 right-parenthesis 2nd Column equals script upper A left-parenthesis s overbar Subscript 1 Superscript left-parenthesis 3 right-parenthesis Baseline comma ellipsis comma s overbar Subscript StartAbsoluteValue upper S Sub Superscript left-parenthesis 3 right-parenthesis Subscript EndAbsoluteValue minus k plus 1 Superscript left-parenthesis 3 right-parenthesis Baseline semicolon upper I right-parenthesis comma 3rd Row 1st Column upper S Superscript left-parenthesis 2 right-parenthesis 2nd Column equals mathematical left-angle upper D Superscript left-parenthesis k right-parenthesis Baseline semicolon upper D Superscript left-parenthesis k plus 1 right-parenthesis Baseline semicolon ellipsis semicolon upper D Superscript left-parenthesis r minus 1 right-parenthesis Baseline mathematical right-angle comma 4th Row 1st Column upper S Superscript left-parenthesis 3 right-parenthesis 2nd Column equals mathematical left-angle ModifyingBelow upper C Superscript left-parenthesis r right-parenthesis Baseline semicolon ellipsis semicolon upper C Superscript left-parenthesis r right-parenthesis Baseline With bottom-brace Underscript q times Endscripts mathematical right-angle comma EndLayout

where

s overbar Subscript i Superscript left-parenthesis j right-parenthesis Baseline equals left-parenthesis upper S Subscript i Superscript left-parenthesis j right-parenthesis Baseline comma ellipsis comma upper S Subscript i plus k minus 1 Superscript left-parenthesis j right-parenthesis Baseline right-parenthesis

for j equals 2 comma 3 and i equals 1 comma ellipsis comma StartAbsoluteValue upper S Superscript left-parenthesis j right-parenthesis Baseline EndAbsoluteValue minus k plus 1 .

The sequences upper S Superscript left-parenthesis 2 right-parenthesis and upper S Superscript left-parenthesis 3 right-parenthesis are entirely composed of complete upper C -sequences of increasing order which are larger than or equal to  k . Moreover, with the exception of the last, rightmost instance in each of upper S Superscript left-parenthesis 2 right-parenthesis and upper S Superscript left-parenthesis 3 right-parenthesis , every single upper C -sequence is immediately succeeded by another upper C -sequence of the same or the following order, including those which are part of a upper D -sequence. Additionally, any window starting at the right-hand end of a upper C -sequence necessarily finishes within the first k minus 1 elements of the following upper C -sequence, all of which are guaranteed to be  0 .

Therefore, the amount of windows of size k contained in upper I ranging over upper S Superscript left-parenthesis 2 right-parenthesis and upper S Superscript left-parenthesis 3 right-parenthesis is equal to the sum over each composing upper C -sequence viewed as a cycle, with an error of at most k minus 1 due to the fact that we are counting only windows entirely contained within each sequence. If we let

c overbar Subscript i Superscript left-parenthesis s right-parenthesis Baseline equals left-parenthesis upper C Subscript i Superscript left-parenthesis s right-parenthesis Baseline comma ellipsis comma upper C Subscript i plus k minus 1 Superscript left-parenthesis s right-parenthesis Baseline right-parenthesis

for s equals k comma ellipsis comma r and i equals 1 comma ellipsis comma s Superscript s , then

StartLayout 1st Row 1st Column nu Subscript upper N Superscript left-parenthesis 2 right-parenthesis 2nd Column equals sigma-summation Underscript s equals k Overscript r minus 1 Endscripts ModifyingBelow left-bracket t left-parenthesis s right-parenthesis script upper A left-parenthesis c overbar Subscript 1 Superscript left-parenthesis s right-parenthesis Baseline comma ellipsis comma c overbar Subscript s Sub Superscript s Subscript Superscript left-parenthesis s right-parenthesis Baseline semicolon upper I right-parenthesis right-bracket With bottom-brace Underscript upper C hyphen sequences contained in upper D Superscript left-parenthesis s right-parenthesis Baseline Endscripts plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis Subscript Baseline comma 2nd Row 1st Column nu Subscript upper N Superscript left-parenthesis 3 right-parenthesis 2nd Column equals q script upper A left-parenthesis c overbar Subscript 1 Superscript left-parenthesis r right-parenthesis Baseline comma ellipsis comma c overbar Subscript r Sub Superscript r Subscript Superscript left-parenthesis r right-parenthesis Baseline semicolon upper I right-parenthesis plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis EndLayout

for some values epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis Baseline less-than-or-equal-to k minus 1 , and epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis Baseline less-than-or-equal-to k minus 1 . From Lemma 5

StartLayout 1st Row 1st Column nu Subscript upper N Superscript left-parenthesis 2 right-parenthesis 2nd Column equals sigma-summation Underscript s equals k Overscript r minus 1 Endscripts left-bracket t left-parenthesis s right-parenthesis left-parenthesis s Superscript s Baseline StartAbsoluteValue upper I EndAbsoluteValue plus s Superscript s minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon Subscript s Baseline right-parenthesis right-bracket plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis Subscript Baseline comma 2nd Row 1st Column nu Subscript upper N Superscript left-parenthesis 3 right-parenthesis 2nd Column equals q left-parenthesis r Superscript r Baseline StartAbsoluteValue upper I EndAbsoluteValue plus r Superscript r minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon Subscript r Baseline right-parenthesis plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis EndLayout

for some values of epsilon Subscript i in left-parenthesis negative 1 comma 1 right-parenthesis , i equals k comma ellipsis comma r . Substituting back into nu Subscript upper N from equation Equation 2,

StartLayout 1st Row 1st Column nu Subscript upper N 2nd Column equals nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis Baseline 2nd Row 1st Column Blank 2nd Column plus sigma-summation Underscript s equals k Overscript r minus 1 Endscripts left-bracket t left-parenthesis s right-parenthesis left-parenthesis s Superscript s Baseline StartAbsoluteValue upper I EndAbsoluteValue plus s Superscript s minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon Subscript s Baseline right-parenthesis right-bracket plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis 3rd Row 1st Column Blank 2nd Column plus q left-parenthesis r Superscript r Baseline StartAbsoluteValue upper I EndAbsoluteValue plus r Superscript r minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon Subscript r Baseline right-parenthesis plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis 4th Row 1st Column Blank 2nd Column plus nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline plus epsilon Subscript b Baseline comma EndLayout

and factoring out terms multiplied by StartAbsoluteValue upper I EndAbsoluteValue , we get

StartLayout 1st Row 1st Column nu Subscript upper N 2nd Column equals StartAbsoluteValue upper I EndAbsoluteValue left-bracket sigma-summation Underscript s equals k Overscript r minus 1 Endscripts t left-parenthesis s right-parenthesis s Superscript s Baseline plus q r Superscript r Baseline right-bracket 2nd Row 1st Column Blank 2nd Column plus nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis 3rd Row 1st Column Blank 2nd Column plus sigma-summation Underscript s equals k Overscript r minus 1 Endscripts left-bracket t left-parenthesis s right-parenthesis s Superscript s minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon Subscript s Baseline right-bracket plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis 4th Row 1st Column Blank 2nd Column plus q r Superscript r minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon Subscript r plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis 5th Row 1st Column Blank 2nd Column plus nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline plus epsilon Subscript b Baseline period EndLayout We now rewrite the first term using the relationship between p , r , q , and upper N from equation Equation 1:

StartLayout 1st Row 1st Column nu Subscript upper N 2nd Column equals StartAbsoluteValue upper I EndAbsoluteValue left-bracket upper N minus sigma-summation Underscript s equals 1 Overscript k minus 1 Endscripts t left-parenthesis s right-parenthesis s Superscript s Baseline minus p right-bracket 2nd Row 1st Column Blank 2nd Column plus nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis 3rd Row 1st Column Blank 2nd Column plus sigma-summation Underscript s equals k Overscript r minus 1 Endscripts left-bracket t left-parenthesis s right-parenthesis s Superscript s minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon Subscript s Baseline right-bracket plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis 4th Row 1st Column Blank 2nd Column plus q r Superscript r minus 1 Baseline left-parenthesis 2 Superscript k Baseline minus 1 right-parenthesis epsilon Subscript r plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis 5th Row 1st Column Blank 2nd Column plus nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline plus epsilon Subscript b Baseline period EndLayout

After dividing both sides by upper N and rearranging terms we obtain

StartLayout 1st Row 1st Column StartFraction nu Subscript upper N Baseline Over upper N EndFraction minus StartAbsoluteValue upper I EndAbsoluteValue 2nd Column equals StartFraction p Over upper N EndFraction left-bracket StartFraction nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline Over p EndFraction minus StartAbsoluteValue upper I EndAbsoluteValue right-bracket 2nd Row 1st Column Blank 2nd Column plus StartFraction 2 Superscript k Baseline minus 1 Over upper N EndFraction left-bracket sigma-summation Underscript s equals k Overscript r minus 1 Endscripts t left-parenthesis s right-parenthesis s Superscript s minus 1 Baseline epsilon Subscript s Baseline plus q r Superscript r minus 1 Baseline epsilon Subscript r Baseline right-bracket 3rd Row 1st Column Blank 2nd Column plus StartFraction 1 Over upper N EndFraction left-bracket nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis Baseline minus StartAbsoluteValue upper I EndAbsoluteValue sigma-summation Underscript s equals 1 Overscript k minus 1 Endscripts t left-parenthesis s right-parenthesis s Superscript s Baseline plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis Subscript Baseline plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis Subscript Baseline plus epsilon Subscript b Baseline right-bracket period EndLayout

Taking limits on both sides as upper N right-arrow normal infinity , the third term on the right-hand side approaches 0 since the contents of the brackets are dependent on k and bounded as a function of upper N . For the second term, using the fact that t is nondecreasing together with Proposition 4, we can see that

StartFraction sigma-summation Underscript s equals k Overscript r minus 1 Endscripts t left-parenthesis s right-parenthesis s Superscript s minus 1 Baseline epsilon Subscript s Baseline Over upper N EndFraction less-than-or-equal-to StartFraction t left-parenthesis r minus 1 right-parenthesis sigma-summation Underscript s equals 1 Overscript r minus 1 Endscripts s Superscript s minus 1 Baseline Over t left-parenthesis r minus 1 right-parenthesis left-parenthesis r minus 1 right-parenthesis Superscript left-parenthesis r minus 1 right-parenthesis Baseline EndFraction less-than-or-equal-to StartFraction 2 left-parenthesis r minus 1 right-parenthesis Superscript left-parenthesis r minus 2 right-parenthesis Baseline Over left-parenthesis r minus 1 right-parenthesis Superscript left-parenthesis r minus 1 right-parenthesis Baseline EndFraction equals StartFraction 2 Over r minus 1 EndFraction

and

StartFraction q r Superscript r minus 1 Baseline epsilon Subscript r Baseline Over upper N EndFraction less-than-or-equal-to StartFraction q r Superscript r minus 1 Baseline Over q r Superscript r Baseline EndFraction equals StartFraction 1 Over r EndFraction period

Since r is an unbounded, nondecreasing function of upper N , this term approaches  0 as well.

Finally, consider the first term on the right-hand side. Since both StartFraction nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline Over p EndFraction and StartAbsoluteValue upper I EndAbsoluteValue are values between 0 and 1 , then left-parenthesis StartFraction nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline Over p EndFraction minus StartAbsoluteValue upper I EndAbsoluteValue right-parenthesis in left-bracket negative 1 comma 1 right-bracket . Moreover, using the identity

StartFraction left-parenthesis x plus 1 right-parenthesis Superscript left-parenthesis x plus 1 right-parenthesis Baseline Over x Superscript x Baseline EndFraction equals left-parenthesis x plus 1 right-parenthesis left-parenthesis 1 plus StartFraction 1 Over x EndFraction right-parenthesis Superscript x

with x equals r minus 1 , and using that p less-than-or-equal-to r Superscript r , we can see that for large values of r ,

StartFraction p Over upper N EndFraction less-than-or-equal-to StartFraction r Superscript r Baseline Over t left-parenthesis r minus 1 right-parenthesis left-parenthesis r minus 1 right-parenthesis Superscript left-parenthesis r minus 1 right-parenthesis Baseline EndFraction equals StartFraction r Over t left-parenthesis r minus 1 right-parenthesis EndFraction left-parenthesis 1 plus StartFraction 1 Over r minus 1 EndFraction right-parenthesis Superscript r minus 1 Baseline less-than-or-equal-to StartFraction r Over t left-parenthesis r minus 1 right-parenthesis EndFraction e comma

which by hypothesis also approaches 0 as upper N right-arrow normal infinity . Hence,

limit Underscript upper N right-arrow normal infinity Endscripts StartFraction nu Subscript upper N Baseline Over upper N EndFraction equals StartAbsoluteValue upper I EndAbsoluteValue period

Since k and upper I were chosen arbitrarily, the sequence upper L is completely uniformly distributed and the proof of Theorem 1 is complete.

3.2. Alternative Proof of Theorem 1

Weyl’s criterion for the multidimensional case states that if upper X overbar equals x overbar Subscript 1 Baseline comma x overbar Subscript 2 Baseline comma ellipsis is a sequence of k -dimensional vectors of real numbers, then upper X overbar is uniformly distributed in the unit cube if and only if for all nonzero k -dimensional vectors of integers script l overbar equals left-parenthesis l 1 comma ellipsis comma l Subscript k Baseline right-parenthesis ,

limit Underscript upper N right-arrow normal infinity Endscripts StartFraction 1 Over upper N EndFraction sigma-summation Underscript n equals 1 Overscript upper N Endscripts e Superscript 2 pi i script l overbar dot x overbar Super Subscript n Superscript Baseline equals 0 comma

where script l overbar dot x overbar Subscript n denotes the dot product of script l overbar and x overbar Subscript n ; see Reference 15. Before applying Weyl’s criterion to the sequence upper L Superscript left-parenthesis t right-parenthesis , we first prove the following lemma based on a well-known fact about the roots of unity.

Lemma 6.

Given a positive integer k and a nonzero k -dimensional vector of integers script l overbar equals left-parenthesis l 1 comma ellipsis comma l Subscript k Baseline right-parenthesis , let n be in double-struck upper N such that n greater-than max left-parenthesis k comma min left-parenthesis StartAbsoluteValue l 1 EndAbsoluteValue comma ellipsis comma StartAbsoluteValue l Subscript k Baseline EndAbsoluteValue right-parenthesis right-parenthesis and consider the sequence upper C Superscript left-parenthesis n right-parenthesis as a cyclic sequence. If we let c overbar Subscript j Baseline equals left-parenthesis upper C Subscript j Superscript left-parenthesis n right-parenthesis Baseline comma ellipsis comma upper C Subscript j plus k minus 1 Superscript left-parenthesis n right-parenthesis Baseline right-parenthesis for j equals 1 comma ellipsis comma n Superscript n , then

StartLayout 1st Row with Label left-parenthesis 6 right-parenthesis EndLabel sigma-summation Underscript j equals 1 Overscript n Superscript n Baseline Endscripts e Superscript 2 pi i script l overbar dot c overbar Super Subscript j Baseline equals 0 period EndLayout

Proof.

If we view upper F Superscript left-parenthesis n comma n right-parenthesis as a cyclic sequence and let

f overbar Subscript j Baseline equals left-parenthesis upper F Subscript j Superscript left-parenthesis n comma n right-parenthesis Baseline comma ellipsis comma upper F Subscript j plus k minus 1 Superscript left-parenthesis n comma n right-parenthesis Baseline right-parenthesis

for j equals 1 comma ellipsis comma n Superscript n , then from the definition of a upper C -sequence it follows that c overbar Subscript j Baseline equals StartFraction 1 Over n EndFraction f overbar Subscript j . Then, if we define normal upper Gamma equals StartSet 0 comma 1 comma ellipsis comma n minus 1 EndSet , every gamma overbar in normal upper Gamma Superscript k appears exactly n Superscript n minus k times as a contiguous subsequence of upper F Superscript left-parenthesis n comma n right-parenthesis . This is true because there are n Superscript n minus k ways of extending an n -ary sequence of length k to one of length n and, by construction, each of these appears exactly once in upper F Superscript left-parenthesis n comma n right-parenthesis when viewed as a cycle. Substituting into the left-hand side of equation Equation 6,

sigma-summation Underscript j equals 1 Overscript n Superscript n Baseline Endscripts e Superscript 2 pi i script l overbar dot left-parenthesis StartFraction 1 Over n EndFraction f overbar Super Subscript j Superscript right-parenthesis Baseline equals sigma-summation Underscript j equals 1 Overscript n Superscript n Baseline Endscripts e Superscript StartFraction 2 pi i Over n EndFraction script l overbar dot f overbar Super Subscript j Superscript Baseline equals n Superscript n minus k Baseline sigma-summation Underscript gamma overbar element-of normal upper Gamma Superscript k Baseline Endscripts e Superscript StartFraction 2 pi i Over n EndFraction script l overbar dot gamma overbar Baseline period

Since script l overbar dot gamma overbar in double-struck upper Z and the function e x p colon double-struck upper Z right-arrow double-struck upper C , e x p left-parenthesis m right-parenthesis equals e Superscript StartFraction 2 pi i Over n EndFraction m is periodic with a period equal to n , then

sigma-summation Underscript gamma overbar element-of normal upper Gamma Superscript k Baseline Endscripts e Superscript StartFraction 2 pi i Over n EndFraction script l overbar dot gamma overbar Baseline equals sigma-summation Underscript r equals 0 Overscript n minus 1 Endscripts sigma-summation Underscript StartLayout 1st Row gamma overbar element-of normal upper Gamma Superscript k Baseline 2nd Row script l overbar dot gamma overbar identical-to r EndLayout Endscripts e Superscript StartFraction 2 pi i Over n EndFraction r Baseline comma

where the congruence script l overbar dot gamma overbar identical-to r is taken modulo n . The conditions for the existence of solutions to equations of the form

script l overbar dot gamma overbar identical-to r left-parenthesis mod n right-parenthesis where gamma overbar element-of normal upper Gamma Superscript k

are well understood (see Reference 18, page 114). In particular, this equation only has solutions when g equals normal g normal c normal d left-parenthesis l 1 comma ellipsis comma l Subscript k Baseline comma n right-parenthesis divides r and, in such a case, the total number of solutions is equal to g n Superscript k minus 1 . Therefore,

StartLayout 1st Row 1st Column sigma-summation Underscript r equals 0 Overscript n minus 1 Endscripts sigma-summation Underscript StartLayout 1st Row gamma overbar element-of normal upper Gamma Superscript k 2nd Row script l overbar dot gamma overbar identical-to r EndLayout Endscripts e Superscript StartFraction 2 pi i Over n EndFraction r 2nd Column equals sigma-summation Underscript StartLayout 1st Row r equals 0 2nd Row g vertical-bar r EndLayout Overscript n minus 1 Endscripts g n Superscript k minus 1 Baseline e Superscript StartFraction 2 pi i Over n EndFraction r Baseline 2nd Row 1st Column Blank 2nd Column equals g n Superscript k minus 1 Baseline sigma-summation Underscript StartLayout 1st Row r prime equals 0 EndLayout Overscript left floor StartFraction n minus 1 Over g EndFraction right floor Endscripts e Superscript StartFraction 2 pi i Over n EndFraction g r Super Superscript prime Superscript Baseline comma EndLayout

where the last step comes from substituting r equals g r prime . If we also substitute n equals g n prime and observe that left floor StartFraction n minus 1 Over g EndFraction right floor equals n prime minus 1 , then

StartLayout 1st Row 1st Column sigma-summation Underscript StartLayout 1st Row r prime equals 0 EndLayout Overscript left floor StartFraction n minus 1 Over g EndFraction right floor Endscripts e Superscript StartFraction 2 pi i Over n EndFraction g r prime 2nd Column equals sigma-summation Underscript StartLayout 1st Row r prime equals 0 EndLayout Overscript n prime minus 1 Endscripts e Superscript StartFraction 2 pi i Over n Super Superscript prime Superscript EndFraction r Super Superscript prime Superscript Baseline period EndLayout

The term on the right-hand side is the sum of all the roots of unity of order n prime . It is a well-known fact that this sum is equal to 0 whenever n prime greater-than 1 . Finally, since n greater-than min left-parenthesis StartAbsoluteValue l 1 EndAbsoluteValue comma ellipsis comma StartAbsoluteValue l Subscript k Baseline EndAbsoluteValue right-parenthesis greater-than-or-equal-to g , then n prime equals n slash g greater-than 1 , and the proof is complete.

Alternative Proof of Theorem 1 .

Let k be a positive integer, and let script l overbar equals left-parenthesis l 1 comma ellipsis comma l Subscript k Baseline right-parenthesis be a nonzero k -dimensional vector of integers. Let upper N range freely over the natural numbers. As in Section 3.1, we consider a prefix of the sequence upper L of length  upper N , denoted upper L Subscript 1 colon upper N , and we consider the values p , q , and r as functions of upper N . Let w overbar Subscript i Baseline equals left-parenthesis upper L Subscript i Baseline comma ellipsis comma upper L Subscript i plus k minus 1 Baseline right-parenthesis for i equals 1 comma 2 comma ellipsis .

Analogously to the first proof of Theorem 1, we define the complex value nu Subscript upper N as the Weyl sum over the first upper N windows of size  k of  upper L :

nu Subscript upper N Baseline equals sigma-summation Underscript j equals 1 Overscript upper N Endscripts e Superscript 2 pi i script l overbar dot w overbar Super Subscript j Superscript Baseline period

Let m equals max left-parenthesis k comma min left-parenthesis StartAbsoluteValue l 1 EndAbsoluteValue comma ellipsis comma StartAbsoluteValue l Subscript k Baseline EndAbsoluteValue right-parenthesis right-parenthesis and consider sufficiently large values of upper N such that m less-than r . As before, this is always possible since r is an unbounded, nondecreasing function of upper N . We can decompose upper L Subscript 1 colon upper N into four consecutive sections; namely, sequences upper S Superscript left-parenthesis 1 right-parenthesis , upper S Superscript left-parenthesis 2 right-parenthesis , upper S Superscript left-parenthesis 3 right-parenthesis , and upper S Superscript left-parenthesis 4 right-parenthesis :

StartLayout 1st Row 1st Column upper L Subscript 1 colon upper N 2nd Column equals mathematical left-angle upper S Superscript left-parenthesis 1 right-parenthesis Baseline semicolon upper S Superscript left-parenthesis 2 right-parenthesis Baseline semicolon upper S Superscript left-parenthesis 3 right-parenthesis Baseline semicolon upper S Superscript left-parenthesis 4 right-parenthesis Baseline mathematical right-angle comma where 2nd Row 1st Column upper S Superscript left-parenthesis 1 right-parenthesis 2nd Column equals mathematical left-angle upper D Superscript left-parenthesis 1 right-parenthesis Baseline semicolon upper D Superscript left-parenthesis 2 right-parenthesis Baseline semicolon ellipsis semicolon upper D Superscript left-parenthesis m minus 1 right-parenthesis Baseline mathematical right-angle comma 3rd Row 1st Column upper S Superscript left-parenthesis 2 right-parenthesis 2nd Column equals mathematical left-angle upper D Superscript left-parenthesis m right-parenthesis Baseline semicolon upper D Superscript left-parenthesis m plus 1 right-parenthesis Baseline semicolon ellipsis semicolon upper D Superscript left-parenthesis r minus 1 right-parenthesis Baseline mathematical right-angle comma 4th Row 1st Column upper S Superscript left-parenthesis 3 right-parenthesis 2nd Column equals mathematical left-angle ModifyingBelow upper C Superscript left-parenthesis r right-parenthesis Baseline semicolon ellipsis semicolon upper C Superscript left-parenthesis r right-parenthesis Baseline With bottom-brace Underscript q times Endscripts mathematical right-angle comma 5th Row 1st Column upper S Superscript left-parenthesis 4 right-parenthesis 2nd Column equals upper C Subscript 1 colon p Superscript left-parenthesis r right-parenthesis EndLayout

and define nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis , nu Subscript upper N Superscript left-parenthesis 2 right-parenthesis , nu Subscript upper N Superscript left-parenthesis 3 right-parenthesis , and nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis as the Weyl sums over windows entirely contained within each respective section such that

StartLayout 1st Row 1st Column nu Subscript upper N 2nd Column equals nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis Baseline plus nu Subscript upper N Superscript left-parenthesis 2 right-parenthesis Baseline plus nu Subscript upper N Superscript left-parenthesis 3 right-parenthesis Baseline plus nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline plus epsilon Subscript b EndLayout

for some complex number epsilon Subscript b with StartAbsoluteValue epsilon Subscript b Baseline EndAbsoluteValue less-than-or-equal-to 3 left-parenthesis k minus 1 right-parenthesis , which accounts for all windows crossing over any border.

Following the same reasoning as in Section 3.1, the values of nu Subscript upper N Superscript left-parenthesis 2 right-parenthesis and nu Subscript upper N Superscript left-parenthesis 3 right-parenthesis can be computed as the Weyl sums over the upper C -sequences composing upper S Superscript left-parenthesis 2 right-parenthesis and upper S Superscript left-parenthesis 3 right-parenthesis viewed as cycles, plus two error terms accounting for right borders. However, in this case, due to Lemma 6 and the fact that all upper C sequences in upper S Superscript left-parenthesis 2 right-parenthesis and upper S Superscript left-parenthesis 3 right-parenthesis have orders greater than m , these sums vanish to zero. Therefore,

nu Subscript upper N Baseline equals nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis Baseline plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis Baseline plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis Baseline plus nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline plus epsilon Subscript b

for some complex values epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis Subscript Baseline comma epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis Baseline with StartAbsoluteValue epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis Subscript Baseline EndAbsoluteValue comma StartAbsoluteValue epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis Subscript Baseline EndAbsoluteValue less-than-or-equal-to k minus 1 . We now consider the limit of nu Subscript upper N Baseline slash upper N as upper N right-arrow normal infinity . Observe that

StartLayout 1st Row 1st Column StartAbsoluteValue StartFraction nu Subscript upper N Baseline Over upper N EndFraction EndAbsoluteValue 2nd Column less-than-or-equal-to StartFraction 1 Over upper N EndFraction StartAbsoluteValue nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis Baseline plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis Subscript Baseline plus epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis Subscript Baseline plus epsilon Subscript b Baseline EndAbsoluteValue plus StartFraction 1 Over upper N EndFraction StartAbsoluteValue nu Subscript upper N Superscript left-parenthesis 4 right-parenthesis Baseline EndAbsoluteValue 2nd Row 1st Column Blank 2nd Column less-than-or-equal-to StartFraction 1 Over upper N EndFraction left-bracket StartAbsoluteValue nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis Baseline EndAbsoluteValue plus StartAbsoluteValue epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 2 right-parenthesis Subscript Baseline EndAbsoluteValue plus StartAbsoluteValue epsilon Subscript nu Sub Subscript upper N Sub Superscript left-parenthesis 3 right-parenthesis Subscript Baseline EndAbsoluteValue plus StartAbsoluteValue epsilon Subscript b Baseline EndAbsoluteValue right-bracket plus StartFraction p Over upper N EndFraction 3rd Row 1st Column Blank 2nd Column less-than-or-equal-to StartFraction 1 Over upper N EndFraction left-bracket StartAbsoluteValue nu Subscript upper N Superscript left-parenthesis 1 right-parenthesis Baseline EndAbsoluteValue plus left-parenthesis k minus 1 right-parenthesis plus left-parenthesis k minus 1 right-parenthesis plus 3 left-parenthesis k minus 1 right-parenthesis right-bracket plus StartFraction p Over upper N EndFraction period EndLayout

The numerator in the first term is dependent on k and m , and constant as a function of upper N . As shown before, the second term approaches 0 as r right-arrow normal infinity . Therefore, the sum of both terms approaches 0 as upper N right-arrow normal infinity , which in turn implies that nu Subscript upper N Baseline slash upper N vanishes as well.

Given that k and script l overbar were chosen arbitrarily, Weyl’s criterion is satisfied for all values of k and the sequence upper L is completely uniformly distributed.

Mathematical Fragments

Theorem 1.

If t colon double-struck upper N right-arrow from bar double-struck upper N is a nondecreasing function and limit Underscript n right-arrow normal infinity Endscripts n slash t left-parenthesis n right-parenthesis equals 0 , then the sequence upper L Superscript left-parenthesis t right-parenthesis is completely uniformly distributed.

Equation (1)
StartLayout 1st Row with Label left-parenthesis 1 right-parenthesis EndLabel StartLayout 1st Row 1st Column upper N 2nd Column equals sigma-summation Underscript s equals 1 Overscript r minus 1 Endscripts StartAbsoluteValue upper D Superscript left-parenthesis s right-parenthesis Baseline EndAbsoluteValue plus q StartAbsoluteValue upper C Superscript left-parenthesis r right-parenthesis Baseline EndAbsoluteValue plus p equals sigma-summation Underscript s equals 1 Overscript r minus 1 Endscripts t left-parenthesis s right-parenthesis s Superscript s Baseline plus q r Superscript r Baseline plus p period EndLayout EndLayout
Equation (2)
StartLayout 1st Row with Label left-parenthesis 2 right-parenthesis EndLabel nu Subscript upper N Superscript left-parenthesis j right-parenthesis Baseline equals script upper A left-parenthesis s overbar Subscript 1 Superscript left-parenthesis j right-parenthesis Baseline comma ellipsis comma s overbar Subscript StartAbsoluteValue upper S Sub Superscript left-parenthesis j right-parenthesis Subscript EndAbsoluteValue minus k plus 1 Superscript left-parenthesis j right-parenthesis Baseline semicolon upper I right-parenthesis period EndLayout