Uniform Distribution of Sequences

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 ...
See more details below
Paperback
$19.21
BN.com price
(Save 16%)$22.95 List Price
Other sellers (Paperback)
  • All (11) from $7.00   
  • New (7) from $7.00   
  • Used (4) from $7.00   
Uniform Distribution of Sequences

Available on NOOK devices and apps  
  • NOOK Devices
  • Samsung Galaxy Tab 4 NOOK 7.0
  • Samsung Galaxy Tab 4 NOOK 10.1
  • NOOK HD Tablet
  • NOOK HD+ Tablet
  • NOOK eReaders
  • NOOK Color
  • NOOK Tablet
  • Tablet/Phone
  • NOOK for Windows 8 Tablet
  • NOOK for iOS
  • NOOK for Android
  • NOOK Kids for iPad
  • PC/Mac
  • NOOK for Windows 8
  • NOOK for PC
  • NOOK for Mac
  • NOOK for Web

Want a NOOK? Explore Now

NOOK Book (eBook)
$12.99
BN.com price
(Save 43%)$22.95 List Price

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 Show Less

Product Details

  • ISBN-13: 9780486450193
  • Publisher: Dover Publications
  • Publication date: 5/12/2006
  • Series: Dover Books on Mathematics Series
  • Pages: 416
  • Sales rank: 1,471,499
  • Product dimensions: 5.70 (w) x 8.60 (h) x 1.10 (d)

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 Show Less

Table of Contents

1. Uniform Distribution Mod 1
2. Discrepancy
3. Uniform Distribution in Compact Spaces
4. Uniform Distribution in Topological Groups
5. Sequences of Integers and Polynomials
Bibliography
List of Symbols and Abbreviations
Author Index
Subject Index
Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously

    If you find inappropriate content, please report it to Barnes & Noble
    Why is this product inappropriate?
    Comments (optional)