Uniform Distribution of Sequences

Uniform Distribution of Sequences

by L. Kuipers, H. Niederreiter
     
 

View All Available Formats & Editions

The theory of uniform distribution began with Hermann Weyl's celebrated paper of 1916. In later decades, the theory moved beyond its roots in diophantine approximations to provide common ground for topics as diverse as number theory, probability theory, functional analysis, and topological algebra. This book summarizes the theory's development from its beginnings to…  See more details below

Overview

The theory of uniform distribution began with Hermann Weyl's celebrated paper of 1916. In later decades, the theory moved beyond its roots in diophantine approximations to provide common ground for topics as diverse as number theory, probability theory, functional analysis, and topological algebra. This book summarizes the theory's development from its beginnings to the mid-1970s, with comprehensive coverage of both methods and their underlying principles.
A practical introduction for students of number theory and analysis as well as a reference for researchers in the field, this book covers uniform distribution in compact spaces and in topological groups, in addition to examinations of sequences of integers and polynomials. Notes at the end of each section contain pertinent bibliographical references and a brief survey of additional results. Exercises range from simple applications of theorems to proofs of propositions that expand upon results stated in the text.

Read More

Product Details

ISBN-13:
9780486149998
Publisher:
Dover Publications
Publication date:
05/24/2012
Series:
Dover Books on Mathematics
Sold by:
Barnes & Noble
Format:
NOOK Book
Pages:
416
File size:
18 MB
Note:
This product may take a few minutes to download.

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



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 ≤ nN, 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 ≤ ab ≤ 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 = a0< a1< ··· < 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, f1 and f2 say, such that f1(x) ≤ f (x) ≤ f2(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, g1 and g2 say, such that g1(x) ≤ c[a,b)(x) ≤ g2(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 g1 and g2 can be chosen in such a way that they satisfy the additional requirements g1(0) = g1(1) and g2(0) =g2(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 limn-> ∞(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 N0 = N0(ε) such that -ε ≤ εn ≤ ε for nN0. Let nN0, 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 =z0< z1< z2< ··· be a subdivision of the interval [0, ∞) with limk-∞zk = ∞. For zk-1x< 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 limn->∞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 limN->∞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 limN>∞A ([a, b]; N)/N = b - a for all a, b with 0 ≤ ab ≤ 1.

1.5. A sequence (xn) is u.d. mod 1 if and only if limN>∞A ((a, b); N)/N = b - a for all a, b with 0 ≤ ab ≤ 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 limN->∞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 x1, y1, x2, y2,..., 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 x1, x2, ..., 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) = eihx, 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 eihi, 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 from Uniform Distribution of Sequences by L. 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.

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >