## Read an Excerpt

#### Uniform Distribution of Sequences

**By L. Kuipers, H. Niederreiter**

**Dover Publications, Inc.**

**Copyright © 2002 H. Niederreiter**

All rights reserved.

ISBN: 978-0-486-14999-8

All rights reserved.

ISBN: 978-0-486-14999-8

CHAPTER 1

*UNIFORM DISTRIBUTION MOD 1*

In this chapter, we develop the classical part of the theory of uniform distribution. We disregard quantitative aspects, which will be considered separately in Chapter 2.

**1. DEFINITION**

**Uniform Distribution Modulo 1**

For a real number *x,* let [*x*] denote the *integral part* of *x,* that is, the greatest integer ≤ *x;* let {*x* } = *x* - [*x*] be the *fractional part* of *x,* or the residue of *x* modulo 1. We note that the fractional part of any real number is contained in the *unit interval I* = [0, 1).

Let ω = (*xn*), *n* = 1, 2, ..., be a given sequence of real numbers. For a positive integer N and a subset *E* of *I,* let the counting function *A* (*E;**N;* ω) be defined as the number of terms *xn,* 1 ≤ *n* ≤ *N,* for which {*xn*} [member of] *E.* If there is no risk of confusion, we shall often write A(E; N) instead of *A* (*E;**N;* ω). Here is our basic definition.

DEFINITION 1.1. The sequence ω = (*xn*), *n* = 1, 2, ..., of real numbers is said to be *uniformly distributed modulo 1* (abbreviated u.d. mod 1) if for every pair *a, b* of real numbers with 0 ≤ *a* ≤ *b* ≤ 1 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(1.1)*

Thus, in simple terms, the sequence (*xn*) is u.d. mod 1 if every half-open subinterval of *I* eventually gets its "proper share" of fractional parts. In the course of developing the theory of uniform distribution modulo 1 (abbreviated u.d. mod 1), we shall encounter many examples of sequences that enjoy this property (for an easy example, see Exercise 1.13).

Let now *c*[*a,b*) be the characteristic function of the interval [*a, b*) [subset or equal to] *I.* Then (1.1) can be written in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(1.2)*

This observation, together with an important approximation technique, leads to the following criterion.

**THEOREM 1.1.** The sequence (*xn*), *n* = 1, 2, ..., of real numbers is u.d. mod 1 if and only if for every real-valued continuous function *f* defined on the closed unit interval [I.bar] = [0, 1] we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(1.3)*

PROOF. Let (*xn*) be u.d. mod 1, and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a step function on [I.bar], where 0 = *a*0< *a*1< ··· < *ak* = 1. Then it follows from (1.2) that for every such *f* equation (1.3) holds. We assume now that *f* is a real-valued continuous function defined on [I.bar]. Given any ε > 0, there exist, by the definition of the Riemann integral, two step functions, *f*1 and *f*2 say, such that *f*1(x) ≤ *f* (*x*) ≤ *f*2(*x*) for all *x* [member of] [I.bar] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then we have the following chain of inequalities:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that in the case of a continuous function *f* the relation (1.3) holds.

Conversely, let a sequence (*xn*) be given, and suppose that (1.3) holds for every real-valued continuous function *f* on [I.bar]. Let [*a, b*) be an arbitrary subinterval of *I.* Given any ε > 0, there exist two continuous functions, *g*1 and *g*2 say, such that *g*1(*x*) ≤ *c*[*a,b*)(x) ≤ *g*2(*x*) for *x* [member of] [I.bar] and at the same time [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since e is arbitrarily small, we have (1.1).

COROLLARY 1.1. The sequence (*xn*) is u.d. mod 1 if and only if for every Riemann-integrable function *f* on [I.bar] equation (1.3) holds.

PROOF. The sufficiency is obvious, and the necessity follows as in the first part of the proof of Theorem 1.1.

COROLLARY 1.2. The sequence (*xn*) is u.d. mod 1 if and only if for every complex-valued continuous function *f* on R with period 1 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(1.4)*

PROOF. By applying Theorem 1.1 to the real and imaginary part of *f,* one shows first that (1.3) also holds for complex-valued *f.* But the periodicity condition implies *f*({*xn*}) = *f*(*xn*), and so we arrive at (1.4). As to the sufficiency of (1.4), we need only note that in the second part of the proof of Theorem 1.1 the functions *g*1 and *g*2 can be chosen in such a way that they satisfy the additional requirements *g*1(0) = *g*1(1) and *g*2(0) =*g*2(1), so that (1.4) can be applied to the periodic extensions of g1 and *g2* to R.

Some simple but useful properties may be deduced easily from Definition 1.1. We mention the following results.

**LEMMA 1.1.** If the sequence (*xn*), *n* = 1, 2, ..., is u.d. mod 1, then the sequence (*xn* + α), *n* = 1, 2, ..., where α is a real constant, is u.d. mod 1.

PROOF. This follows immediately from Definition 1.1.

**THEOREM 1.2.** If the sequence (*xn*), *n* = 1, 2, ..., is u.d. mod 1, and if (*yn*) is a sequence with the property lim*n*-> ∞(*xn* - *yn*) = α, a real constant, then (*yn*) is u.d. mod 1.

PROOF. Because of Lemma 1.1 it suffices to consider the case α = 0. Set ε*n* = *xn* - *yn* for *n* ≥ 1. Let 0 < *a*< *b*< 1, and choose ε such that

0 < ε < min (a, 1 - b, b - a/2).

There exists an *N*0 = *N*0(ε) such that -ε ≤ ε*n* ≤ ε for *n* ≥ *N*0. Let *n* ≥ *N*0, then *a* + ε ≤ {*xn*} < *b* - ε implies *a* ≤ {*yn*} < *b,* and on the other hand *a* ≤ {*yn*} < *b* implies *a* - ε ≤ {*xn*} < *b* + ε. Hence, if σ = (*xn*) and ω = (*yn*), then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since ε can be taken arbitrarily small, the sequence ω satisfies (1.1) for all *a* and *b* with 0 < *a*< *b*< 1. To complete the proof, one uses the result in Exercise 1.2.

**Uniform Distribution Modulo a Subdivision**

We mention briefly one of the many variants of the definition of u.d. mod 1. Let Δ: 0 =*z*0< *z*1< *z*2< ··· be a subdivision of the interval [0, ∞) with limk-∞*zk* = ∞. For *zk-1* ≤ *x*< *zk* put

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that 0 ≤ {*x*}Δ< 1.

DEFINITION 1.2. The sequence (*xn*), *n* = 1, 2, ..., of nonnegative real numbers is said to be *uniformly distributed modulo* Δ (abbreviated u.d. mod Δ) if the sequence ({*xn*}Δ), *n* = 1, 2, ..., is u.d. mod 1.

If Δ is the subdivision Δ0 for which *zk* = *k,* this concept reduces to that of u.d. mod 1. An interesting case occurs if (*xn*) is an increasing sequence of nonnegative numbers with limn->∞*xn* = ∞. Then we let *A* (*x, a*) be the number of *xn*< *x* with {*xn*}Δ< α, and we set *A* (*x*) = *A* (*x,* 1). Clearly, the sequence (*xn*) is u.d. mod Δ if and only if for each α[member of] (0, 1),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(1.5)*

The following remarkable result can be shown.

**THEOREM 1.3.** Let (*xn*) be an increasing sequence of nonnegative numbers with lim*n*->∞*xn* = ∞. A necessary condition for (*xn*) to be u.d. mod Δ is that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(1.6)*

PROOF. Suppose (*xn*) is u.d. mod Δ. Since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(1.7)*

Now the extreme left member of (1.7) goes to as *k* -> ∞, according to (1.5) and the assumption about the sequence (*xn*). Similarly, the second factor of the second term of the extreme right member of (1.7) goes to as *k* -> ∞. Hence, (1.7) implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(1.8)*

In a similar way, it can be shown that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(1.9)*

From (1.8) and (1.9) we obtain (1.6).

**Notes**

The formal definition of u.d. mod 1 was given by Weyl [2, 4]. The distribution mod 1 of special sequences was already investigated earlier (see the notes in Section 2). Theorem 1.1 and its corollaries also come from Weyl [2, 4]. The notion of u.d. mod Δ was introduced by LeVeque [4] and was studied further by Cigler [1], Davenport and LeVeque [1], Erdös and Davenport [1], W. M. Schmidt [10], and Burkard [1, 2].

A detailed survey of the results on u.d. mod 1 prior to 1936 can be found in Koksma [4, Kap. 8, 9]. The period from 1936 to 1961 is covered in the survey article of Cigler and Helmberg [1]. An expository treatment of some of the classical results is given in Cassels [9, Chapter 4]. The survey article of Koksma [16] touches upon some of the interesting aspects of the theory.

Let λ be the Lebesgue measure in *I.* If (*xn*) is u.d. mod 1, the limit relation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

will still hold for all Jordan-measurable (or λ-continuity) sets *E* in *I* (see Chapter 3, Theorem 1.2) but not for all Lebesgue-measurable sets *E* in *I* (see Exercise 1.9). See also Section 1 of Chapter 3 and Rimkeviciute [1]. Similarly, the limit relation (1.3) cannot hold for all Lebesgue-integrable functions *f* on [I.bar]. See Koksma and Salem [1] for strong negative, results. The following converse of Theorem 1.1 was shown by de Bruijn and Post [1]: if *f* is defined on [I.bar] and if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] exists for every (*xn*) u.d. mod 1, then *f* is Riemann-integrable on . Binder [1] gives an alternative proof and a generalization. See also Bass and Couot [1]. Rudin [2] discusses a related question.

Elementary criteria for u.d. mod 1 have been given by O'Neil [1] (see also the notes in Section 3 of Chapter 2) and Niederreiter [15]. Sequences of rationals of the type considered in Exercise 1.13 were studied by Knapowski [1] using elementary methods.

In the sequel, we shall discuss many variants of the definition of u.d. mod 1. One rather special variant was introduced by Erdös and Lorentz [1] in the context of a problem from probabilistic number theory. A sequence (*xn*) is called *homogeneously equidistributed mod 1* if ((1/*d*)*xnd*), *n* = 1, 2, ..., is u.d. mod 1 for every positive integer *d.* This notion was also studied by Schnabl [1].

For the result in Exercise 1.14, see Pólya and Szegö [1, II. Abschn., Aufg. 163].

**Exercises**

1.1. A definition equivalent to Definition 1.1 is the following: A sequence (*xn*) of real numbers is u.d. mod 1 if lim*N->∞**A* ([0, *c*); *N*)/*N* = *c* for each real number *c* with 0 ≤ *c* ≤ 1.

1.2. If (1.1) holds for all *a,* b with 0 < *a*< *b*< 1, then it holds for all *a, b* with 0 ≤ *a≤ b≤*1.

1.3. A sequence (*xn*) is u.d. mod 1 if and only if (1.1) is satisfied for every interval [*a, b*) [subset or equal to] *I* with rational end points.

1.4. A sequence (*xn*) is u.d. mod 1 if and only if lim*N>∞**A* ([*a, b*]; *N*)/*N* = *b - a* for all *a, b* with 0 ≤ *a* ≤ *b* ≤ 1.

1.5. A sequence (*xn*) is u.d. mod 1 if and only if lim*N>∞**A* ((*a, b*); *N*)/*N* = *b - a* for all *a, b* with 0 ≤ *a* ≤ *b* ≤ 1.

1.6. If (*xn*) is u.d. mod 1, then the sequence ({*xn*)) of fractional parts is everywhere dense in [I.bar].

1.7. If we leave out finitely many terms from a sequence that is u.d. mod 1, the resulting sequence is still u.d. mod 1. What additional condition is needed if "finitely" is replaced by "infinitely"?

1.8. If finitely many terms of a sequence that is u.d. mod 1 are changed in an arbitrary manner, the resulting sequence is still u.d. mod 1. Generalize as in Exercise 1.7.

1.9. Let (*xn*) be an arbitrary sequence of real numbers. Construct a Lebesgue-measurable subset *E* of *I* with λ(*E*) = 1 and lim*N->∞**A* (*E; N*)/*N* = 0. *Hint:* Consider the complement in *I* of the set determined by the range of the sequence ({*xn*}).

1.10. Let (*xn*) be u.d. mod 1. Then the relation (1.3) is not valid for every Lebesgue-integrable function *f* on [I.bar].

1.11. Let (*xn*) and (*yn*) be u.d. mod 1. Then the sequence *x*1, *y*1, *x*2, *y*2,..., *xn, yn, ...* is u.d. mod 1.

1.12. If r is a rational number, then the sequence (*nr*), *n* = 1, 2,..., is not u.d. mod 1. Is there a nonempty proper subinterval [*a,* b) of *I* for which (1.1) holds?

1.13. Prove that the sequence 0/1, 0/2, 1/2, 0/3, 1/3, 2/3, ..., 0/*k,* 1/*k,* ..., (*k* - 1)/*k,* ... is u.d. mod 1.

1.14. Let (*xn*) be a sequence in *I.* For a subinterval [*a, b*) of *I* and *N* ≥ 1, let *S* ([a, b); *N*) be the sum of the elements from *x*1, *x*2, ..., *xN* that are in [*a, b*). Then (*xn*) is u.d. mod 1 if and only if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all subintervals [*a, b*) of *I.*

**2. THE WEYL CRITERION**

**The Criterion**

The functions f of the form *f(x*) = *e*2π*ihx,* where *h* is a nonzero integer, satisfy the conditions of Corollary 1.2. Thus, if (*xn*) is u.d. mod 1, the relation (1.4) will be satisfied for those *f.* It is one of the most important facts of the theory of u.d. mod 1 that these functions already suffice to determine the u.d. mod 1 of a sequence.

**THEOREM 2.1: Weyl Criterion.** The sequence (*xn*), *n* = 1, 2, ..., is u.d. mod 1 if and only if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(2.1)*

PROOF. The necessity follows from Corollary 1.2. Now suppose that (*xn*) possesses property (2.1). Then we shall show that (1.4) is valid for every complex-valued continuous function *f* on r with period 1. Let ε be an arbitrary positive number. By the Weierstrass approximation theorem, there exists a trigonometric polynomial Φ(*x*), that is, a finite linear combination of functions of the type *e*2π*ihi, h* [member of] Z, with complex coefficients, such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] *(2.2)*

Now we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The first and the third terms on the right are both≤εwhatever the value of *N,* because of (2.2). By taking *N* sufficiently large, the second term on the right is ≤ ε because of (2.1).

*(Continues...)*

Excerpted fromUniform Distribution of SequencesbyL. Kuipers, H. Niederreiter. Copyright © 2002 H. Niederreiter. Excerpted by permission of Dover Publications, Inc..

All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.

Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.