Everand Logo

Welcome to Everand!

  • Discover millions of ebooks, audiobooks, and so much more with a free trial

    Only €10,99/month after trial. Cancel anytime.

    Uniform Distribution of Sequences
    Uniform Distribution of Sequences
    Uniform Distribution of Sequences
    Ebook758 pages6 hours

    Uniform Distribution of Sequences

    By L. Kuipers and H. Niederreiter

    4/5

    ()

    Read preview

    About this ebook

    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.
    LanguageEnglish
    PublisherDover Publications
    Release dateMay 24, 2012
    ISBN9780486149998
    Uniform Distribution of Sequences

    Related to Uniform Distribution of Sequences

    Titles in the series (100)

    View More
    View More

    Related ebooks

    Mathematics For You

    View More
    View More

    Related podcast episodes

    Related articles

    • Article

      Why Mathematicians Should Stop Naming Things After Each Other

      Sep 2, 2020

      Any student of modern math must know what it feels like to drown in a well of telescoping terminology. For a high-profile example, let’s take the Calabi-Yau manifold, made famous by string theory. A Calabi-Yau manifold is a compact, complex Kähler ma

      6 min read

    • Article

      A Supermassive Lens On The Constants Of Nature

      Nov 25, 2020

      The 2020 Nobel Prize in Physics went to three researchers who confirmed that Einstein’s general relativity predicts black holes, and established that the center of our own galaxy houses a supermassive black hole with the equivalent of 4 million suns

      9 min read

    • Article

      The Deepest Uncertainty: When a hypothesis is neither true nor false.

      Jun 6, 2013

      Georg Cantor died in 1918 in a sanatorium in Halle, Germany. A pre-eminent mathematician, he had laid the foundation for the theory of infinite numbers in the 1870s. At the time, his ideas received hostile opposition from prominent mathematicians in

      4 min read

    • Article

      The Twin Prime Hero: Rags, riches, and fame in mathematics.

      Dec 29, 2016

      Yitang “Tom” Zhang spent the seven years following the completion of his Ph.D. in mathematics floating between Kentucky and Queens, working for a chain of Subway restaurants, and doing odd accounting work. Now he is on a lecture tour that includes st

      8 min read

    • Article

      The Math That Takes Newton Into the Quantum World

      Feb 28, 2019

      In my 50s, too old to become a real expert, I have finally fallen in love with algebraic geometry. As the name suggests, this is the study of geometry using algebra. Around 1637, René Descartes laid the groundwork for this subject by taking a plane,

      9 min read

    • Article

      Physicists Attack Math’s $1,000,000 Question

      Apr 4, 2017

      Physicists are attempting to map the distribution of the prime numbers to the energy levels of a particular quantum system.

      4 min read

    • Article

      Pine Bookcase

      Mar 5, 2024

      Pine Bookcase
      6 min read

    • Article

      Graph Theory In A Nutshell

      May 5, 2020

      A graph G(V,E) is a finite, non-empty set of vertices V (or nodes) and a set of edges E. If the edges E that have the form of (a,b) are an ordered pairs of vertices, then we have a directed graph. In contrast, if the edges E are unordered pairs of ve

      1 min read

    • Article

      The Explainer What Is Light?

      Sep 8, 2021

      The Explainer What Is Light?
      3 min read

    • Article

      Euclid as Founding Father: We hold this mathematics to be self evident.

      Oct 13, 2016

      Despite the man’s awkward gestures, unkempt hair, and ill-fitting suit, it was one of the most extraordinary speeches that Reverend John Gulliver had ever heard. It was March 1860, and the venue was Norwich, Connecticut. The following morning Gullive

      8 min read

    • Article

      In Mathematics, Mistakes Aren’t What They Used To Be: Computers can’t invent, but they’re changing the field anyway.

      May 7, 2015

      Vladimir Voevodsky had no sooner sat himself down at the sparkling table, set for a dinner party at the illustrious Institute for Advanced Study in Princeton, New Jersey, than he overturned his empty wine glass, flipping bowl over stem and standing t

      9 min read

    • Article

      The Rhythm of Sculpture

      Jun 28, 2018

      This article is part of Nautilus’ month-long exploration of the science and art of time. Read the introduction here. In the studio, time does not pass—there is only an “eternal now.” The art coming from the studio is a crystallized form of the artist

      3 min read

    Related categories

    Reviews for Uniform Distribution of Sequences

    4/5

    1 rating0 reviews

    What did you think?

    Tap to rate

    Review must be at least 10 words

      Book preview

      Uniform Distribution of Sequences - L. Kuipers

      Copyright

      Copyright © 1974 by L. Kuipers and H. Niederreiter

      Copyright © renewed 2002 by H. Niederreiter.

      All rights reserved.

      Bibliographical Note

      This Dover edition, first published in 2006, is an unabridged republication of the work originally published by John Wiley & Sons, Inc., New York, in 1974. The preface to the Dover Edition and Corrigenda were specially prepared for this edition by H. Niederreiter.

      International Standard Book Number: 0-486-45019-8

      9780486149998

      Manufactured in the United States of America

      Dover Publications, Inc., 31 East 2nd Street, Mineola, N.Y 11501

      To Francina and Gerlinde

      PREFACE TO THE DOVER EDITION

      When Dover Publications approached me with the proposal of bringing out a reprint edition of Uniform Distribution of Sequences, I gladly grasped the opportunity of making this book, which has been out of print for a long time, available again. It seems that this book, although over 30 years old, can still serve a useful purpose for students and researchers by providing a systematic introduction to the subject as well as a comprehensive coverage of the literature up to the early 1970s.

      The development of the field of uniform and asymptotic distribution of sequences from 1974, the year of publication of the original version of the book, to the present has been marked by a tendency to move from the abstract to the concrete, which is in line with a general trend in mathematics during this period. In the context of the material in this book, this is reflected by the fact that comparatively little further work has been done on those parts of the theory that correspond to Chapters 3 and 4. On the other hand, research on the down-to-earth aspects of the area covered by Chapters 1 and 2 has flourished and exciting progress was achieved in the intervening years. These dynamic research activities on uniform distribution in concrete settings, and in particular on discrepancy theory, are driven by demands from applications. It is well known, and can be gleaned also from Chapter 2, Section 5, of the book, that the study of the discrepancy of sequences in unit cubes plays an important role in quasi-Monte Carlo methods for scientific computing. Other areas where discrepancy theory has made an impact are pseudorandom number generation, computer graphics, cryptology, and various parts of number theory.

      A reprint edition does not allow adding new material, so I had to be content with listing misprints and updates for references. The reader who wants to gain access to research in the area since 1974 may want to consult the following works. Many aspects of the theory of uniform distribution of sequences are covered in the monograph of M. Drmota and R.F. Tichy, Sequences, Discrepancies and Applications, Lecture Notes in Mathematics, Vol. 1651, Springer-Verlag, Berlin, 1997. Uniformly distributed sequences are treated in the context of probabilistic number theory in G. Harman, Metric Number Theory, Oxford University Press, Oxford, 1998. The books of J. Beck and W.W.L. Chen, Irregularities of Distribution, Cambridge University Press, Cambridge, 1987, and J. Ma-toušek, Geometric Discrepancy: An Illustrated Guide, Springer-Verlag, Berlin, 1999, are devoted to discrepancy theory. A treatment of discrepancy theory from the perspective of theoretical computer science is provided in B. Chazelle, The Discrepancy Method: Randomness and Complexity, Cambridge University Press, Cambridge, 2000. Applications of discrepancy theory to quasi-Monte Carlo methods and pseudorandom number generation are discussed in the survey article by H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84, 957-1041 (1978), as well as in the books of H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992, and S. Tezuka, Uniform Random Numbers: Theory and Practice, Kluwer Academic Publishers, Boston, 1995. A series of biennial conferences on Monte Carlo and quasi-Monte Carlo methods was begun in 1994 and is still going strong. The proceedings of these conferences were all published by Springer-Verlag, with the first volume being Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (H. Niederreiter and P.J.-S. Shiue, eds.), Lecture Notes in Statistics, Vol. 106, Springer-Verlag, New York, 1995, and the most recent one being Monte Carlo and Quasi-Monte Carlo Methods 2004 (H. Niederreiter and D. Talay, eds.), Springer-Verlag, Berlin, 2006. A monograph updating the material in Chapter 5 of the book is that of W. Narkiewicz, Uniform Distribution of Sequences of Integers in Residue Classes, Lecture Notes in Mathematics, Vol. 1087, Springer-Verlag, Berlin, 1984.

      I am dedicating this reprint edition to the memory of my coauthor Lauwerens Kuipers who passed away many years ago. Finally, I want to express my gratitude to John Grafton of Dover Publications for initiating the project of publishing this reprint edition.

      Singapore, November 2005

      Harald Niederreiter

      PREFACE

      The theory of uniform distribution modulo one (Gleichverteilung modulo Eins, équirépartition modulo un) is concerned, at least in its classical setting, with the distribution of fractional parts of real numbers in the unit interval (0, 1). The development of this theory started with Hermann Weyl’s celebrated paper of 1916 titled: Über die Gleichverteilung von Zahlen mod. Eins. Weyl’s work was primarily intended as a refinement of Kronecker’s approximation theorem, and, therefore, in its initial stage, the theory was deeply rooted in diophantine approximations. During the last decades the theory has unfolded beyond that framework. Today, the subject presents itself as a meeting ground for topics as diverse as number theory, probability theory, functional analysis, topological algebra, and so on. However, it must be said that the germs of various later developments can be found in Weyl’s 1916 paper.

      This book attempts to summarize the results of these investigations from the beginning to the present, with emphasis on the work done during the last 20 years. Because the literature on the subject is vast, it was inevitable that now and then choices had to be made and selection criteria had to be applied that reflect the personal taste of the authors. As a rule, we have endeavored to produce a comprehensive coverage of the methods used in the theory of uniform distribution. In some instances, we did not present a result in its most general version, but rather tried to describe the underlying principles and ideas, which might otherwise be shrouded in technicalities. The title we have chosen indicates that we have resolved the dilemma of asymptotic distribution versus uniform distribution in favor of the latter, since it is this aspect to which most of our exposition is devoted. We believe that this book should prove a useful introduction to the subject for students in number theory and analysis and a reference source for researchers in the field.

      An important role in our presentation is played by the notes at the end of each section. These not only contain the pertinent bibliographical references, but also provide the reader with a brief survey of additional results relating to the material of that section. The exercises we include range from simple applications of theorems to proofs of propositions more general than, or shedding further light on, results in the text. The reader is encouraged to try his hand at many of these problems in order to increase his understanding of the theory.

      The following is a brief outline of the contents of the book. The first chapter deals with the classical part of the theory. It assumes that the reader has a good background in real analysis. Important properties of uniformly distributed sequences of real numbers are developed in the early sections and specific examples of uniformly distributed sequences are described throughout. A central position in the theory is taken by the so-called Weyl criterion. As a means for investigating sequences with respect to uniform distribution, it caused in the early years of the development of the theory of uniform distribution a strong interest in exponential sums. One of the equivalents of the definition of a uniformly distributed sequence modulo 1 of real numbers is the functional definition. This form of the notion of uniform distribution reveals the measure-theoretic and topological character of the definition. To avoid repetition, we have, in the first chapter, concentrated on techniques and results that depend on the special structure of the real number system. Results that have analogues in a general setting (such as van der Corput’s difference theorem and various metric theorems) will often be found in stronger versions in the more abstract Chapters 3 and 4. Some extensions of the theory are already touched on in Chapter 1, such as the multidimensional case in Section 6 and distribution functions and asymptotic distribution with respect to summation methods in Section 7. A study of normal numbers and their relation to uniform distribution is carried out in Section 8. Uniform distribution modulo 1 of measurable functions appears in Section 9.

      In Chapter 2, the results of the preceding chapter are studied and complemented from a quantitative point of view. Here a modest background in number theory would be helpful. Many of the results presented here are current. The important results of K. F. Roth and W. M. Schmidt on irregularities of distribution, as well as the celebrated inequalities of Erdös-Turan and LeVeque, are proved in Section 2. The next section is concerned mainly with the sequences (nθ), n = 1, 2 ..., with θ irrational. This leads one back to the number-theoretic origins of the theory. Number-theoretic integration methods which derive from the theory of uniform distribution are treated in Section 5. This part of the book should be of interest to numerical analysts.

      In Chapters 3 and 4, we develop in greater detail the theory of uniform distribution in compact Hausdorff spaces and in topological groups, respectively. A background in topology and measure theory is required. Furthermore, for Chapter 4 a knowledge of topological groups is desirable, but all the required results from structure theory and duality theory are stated. Many interesting relations to probability theory, ergodic theory, summability theory, and topological algebra emerge in these portions of the book. In Section 2 of Chapter 4 a detailed treatment of the method of correlation functions is given. Section 4 of Chapter 4 contains an in-depth discussion of the theory of monothetic groups.

      The most recent branch of the theory is based on the notion of a uniformly distributed sequence of rational integers. It is not surprising that, subsequently, attention has been paid to the distribution of sequences of a more general type of integers, such as the p-adic ones, and of sequences of elements of the ring of polynomials over a finite field. These developments are described in Chapter 5. The reader should be familiar with the rudiments of p-adic number theory and the theory of finite fields.

      Because of space limitations a number of topics could not be covered as fully as we wished or had to be omitted completely in our presentation. Topics in the latter category include metric quantitative results, relations between uniform distribution and harmonic analysis, and the theory of weak convergence of probability measures. However, the notes in the appropriate sections contain a survey of the literature on these aspects.

      A graduate course in uniform distribution emphasizing the number-theoretic connections could be based on Chapters 1, 2, and 5 of the book and may be complemented by selections from the remaining chapters. The prerequisites for each chapter have been mentioned above.

      It is with great pleasure and gratitude that we acknowledge helpful conversations and/or correspondence with I. D. Berg, D. L. Carlson, J. Cigler, S. Haber, J. H. Halton, W. J. LeVeque, H. G. Meijer, L. A. Rubel, W. M. Schmidt, R. Tijdeman, and S. K. Zaremba. Special thanks are due Professor Walter Philipp, who read drafts of the manuscript and made a number of valuable suggestions. The second author would like to express his indebtedness to Professor Edmund Hlawka, who guided his first steps into the theory of uniform distribution and whose supreme mastery of the subject was a constant source of enlightenment for his students. He also wants to thank the University of Illinois for its hospitality during a crucial period of the writing.

      The enormous task of converting our drafts into a typewritten manuscript was mastered by Miss Pat Coombs, whose skill and unfailing patience we learned to admire. We extend our sincere gratitude to the staff of Wiley-Interscience for its care and professionalism in the production of the book.

      October 1973

      L. KUIPERS

      H. NIEDERREITER

      Table of Contents

      Title Page

      Copyright Page

      Dedication

      PREFACE TO THE DOVER EDITION

      PREFACE

      CORRIGENDA

      1 - UNIFORM DISTRIBUTION MOD 1

      2 - DISCREPANCY

      3 - UNIFORM DISTRIBUTION IN COMPACT SPACES

      4 - UNIFORM DISTRIBUTION IN TOPOLOGICAL GROUPS

      5 - SEQUENCES OF INTEGERS AND POLYNOMIAL

      BIBLIOGRAPHY

      LIST OF SYMBOLS AND ABBREVIATIONS

      AUTHOR INDEX

      SUBJECT INDEX

      CORRIGENDA

      Note. p. ab, respectively p. ab, means page a, line b from above, respectively from below.

      p. vii⁵: read [0,1)

      p. xiii¹²: read "sequences 197,"

      p. xiv¹³: read "distributed sequences"

      p. 9¹⁶: replace "0 ≤ θ(k) ≤ 1 by |θ(k)| ≤ 1"

      p. 154-2: replace these lines by: and therefore an application of integration by parts for Stieltjes integrals yields

      p. 17²: replace the second mean value theorem by integration by parts

      p. 3922: read Cassels [3]

      b"

      p. 75⁷: read is a nonconstant polynomial

      p. 85⁹: replace I. S. Kac [1] by Kac [3a]

      k

      p. 128⁵-⁶: read DN(ω) = O(|f(N)|/N + 1/|Nf‘(N)|).

      p. 132, Exercise 3.20: read DN(ω) = O(N-1/3(log N)²/³).

      p. 132, Exercise 3.21: read DN(ω) = O(N-1/3(log N)¹-³(loglog N)²/³).

      p. 152, equation (5.23): replace "f(xn) by f(xn)"

      p. 159¹⁷: read Bass and Guilloud

      p. 2247,3: read Gel‘fand-Raikov

      delete ∞ (three times)

      p. 262, Theorem 3.2, condition 3: replace "(yn) * (xn) by (xn") * (yn)"

      p. 266, above Exercise 3.1: insert headline Exercises

      p. 2811: replace 2c by 2‘

      p. 2971: delete continuous

      p. 298⁴: delete continuous

      p. 334²⁰: read Bass, J., and Guilloud, J.

      p. 334, Bauer [1]: replace to appear by 78, 289-296 (1974)

      p. 341, Erdös-Koksma [2]: read "On the uniform distribution modulo 1 of sequences (f(n,θ))"

      p. 347: replace Kac, I. S.: [1] by Kac, M.: [3a]

      p. 3491: read inequalities (Russian)

      p. 351²: read "numbers, Fibonacci"

      p. 354, Mück-Philipp [1]: replace to appear by "Math. Z. 142, 195-202 (1975)"

      p. 355, Niederreiter [17]: replace to appear by "Proc. Amer. Math. Soc. 47, 305-310 (1975)"

      p. 355, Niederreiter [18]: replace to appear by "Math. Comp. 28, 1117-1132 (1974)"

      p. 355, Niederreiter [19]: replace to appear by "Acta Arith. 28, 321-339 (1975)"

      p. 356, Philipp [10]: replace to appear by "Acta Arith. 26, 241-251 (1975)"

      p. 360, Schmidt [15]: replace to appear by "Trans. Amer. Math. Soc. 198, 1-22 (1974)"

      p. 362, Stoneham [3]: read "Acta Arith. 16, 221-237 (1970)."

      p. 362, Stoneham [4]: read "Acta Arith. 16, 239-253 (1970)."

      p. 366, Zaremba [9]: read La méthode des bons treillis pour le calcul des intégrales multiples

      p. 366, Zaremba [11]: replace to appear by "78, 446-460 (1974)"

      p. 376, second column: read Guilloud, J.

      p. 377, first column: delete Kac, I. S., 85, 347

      p. 377, first column: under Kac, M. insert 85 after 75

      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} ∈ 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

      (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) ⊆ I. Then (1.1) can be written in the form

      (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 = [0, 1] we have

      (1.3)

      PROOF. Let (xn, 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 . 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 Then we have the following chain of inequalities:

      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 . 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 Then we have

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

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

      (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

      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.

      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

      There exists an N0 = N0(ε) such that -ε ≤ εn ≤ ε for n ≥ N0. Let n ≥ N0, 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

      Since ε can be taken arbitrarily small, the sequence ω satisfies (1.1) for all a and b with 0 < a < b

      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-1 ≤ x < zk put

      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α∈(0, 1),

      (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

      (1.6)

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

      we have

      (1.7)

      as k → ∞, according to (1.5) and the assumption about the sequence (xnas k → ∞. Hence, (1.7) implies

      (1.8)

      In a similar way, it can be shown that

      (1.9)

      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

      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 [1]. Similarly, the limit relation (1.3) cannot hold for all Lebesgue-integrable functions f . 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 exists for every (xn) u.d. mod 1, then f . 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) ⊆ 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 ≤ a ≤ b ≤ 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 ≤ a ≤ b ≤ 1.

      1.6. If (xn) is u.d. mod 1, then the sequence ({xn.

      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 .

      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

      for all subintervals [a, b) of I.

      2. THE WEYL CRITERION

      The Criterion

      The functions f of the form f(x) = e²π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

      (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 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²πihi, h , with complex coefficients, such that

      (2.2)

      Now we have

      The first and the third terms on the right are both≤εwhatever the value of N, because of (2.2). By taking N

      Applications to Special Sequences

      EXAMPLE 2.1. Let θ be an irrational number. Then the sequence (nθ), n = 1, 2, ... , is u.d. mod 1. This follows from Theorem 2.1 and the inequality

      for integers h ≠

      EXAMPLE 2.2. Let θ = 0.1234567891011121314 ··· in decimal notation. Then 0 is irrational. Therefore, the sequence (nθ) is u.d. mod 1 by Example 2.1. It follows that the sequence ({n(see Exercise 1.6). One can even show that the subsequence ({10n. For let α = 0 . a1a2 ··· ak be a decimal fraction in I. One chooses n such that {10nθ} begins with the digits a1, a2,..., ak followed by r zeros. Then we have 0 < {10nθ) - α < 10-k-r

      EXAMPLE 2.3. The sequence ({ne}), n = 1, 2,..., is u.d. mod 1 according to Example 2.1. However, the subsequence ({n!e}) has 0 as the only limit point. We have

      so that n!e = k + eα/(n + 1), where k is a positive integer. Hence, for n ≥ 2 we get {n!e} = eα/(n + 1) < e/(n

      EXAMPLE 2.4. The sequence (log n), n = 1, 2, ... , is not u.d. mod 1. In order to show this we use the Euler summation formula. If F(t) is a complex-valued function with a continuous derivative on 1 ≤ t ≤ N, where N ≥ 1 is an integer, then

      (2.3)

      Let F(t) = e²π i log t, and divide both sides of (2.3) by N. Then the first term on the right of (2.3) is equal to

      and this expression does not converge as N → ∞. The second term on the right of (2.3), divided by N, tends to zero as N → ∞, as does the third term on the right of (2.3) divided by N, as follows from

      Hence, (2.1) with xn = log n and h = 1 is not satisfied.

      EXAMPLE 2.5. In the previous example it was shown that (log n) is not u.d. mod 1. This general statement, however, does not describe the behavior of (log n) mod 1 with regard to a particular interval [a, b) ⊆ I. In the following we show in an elementary way that for every proper nonempty subinterval [a, b) of I the sequence (log n) fails to satisfy (1.1). Consider first an interval [a, b) with 0 ≤ a < b < 1. Choose a sequence of integers (Nm), m ≥ m0, such that em+b < Nm < em+1 for m ≥ m0. Now the number of indices n = 1, 2,..., Nm for which a ≤ {log n} < b, or k + a ≤ log n < k + b, or ek+a ≤ n < ek+b, k = 0, 1,..., m, is given by the expression

      Now it is clear that the fraction obtained by dividing this expression by Nm, which was chosen between em+b and em+1, is not convergent as m → oo for every choice of the sequence (Nm). If 0 < a < b = 1, one works in a similar way with a sequence (Nm) satisfying em < Nm < em+a for m ≥ m0. With a slight modification of the calculation, one may show the same with respect to the sequence (c log n), c , n = 1, 2, ....

      EXAMPLE 2.6. Suppose we are given an infinitely large table of the Brigg logarithms (¹⁰log n), n = 1 , 2, ... , in decimal representation, and consider the sequence of the consecutive digits in the kth column after the decimal point for some fixed k ≥ 1. Let c = 10k-1 (log 10)-1; then

      If for some n we have {¹⁰log n} = 0.b1b2 ··· bk ···, then {c log n} = 0.bkbk+1 ··· . Thus, we observe that the digit bk at the kth decimal place of ¹⁰log n is equal to g, g = 0, 1, ... , 9, if and only if g/10 ≤ {c log n} < (g + 1)/10. Now the sequence (c log n) has the property described in Example 2.5. This implies that the relative frequency with which the digit g appears in the kth column of the table is not equal to 1/10.

      Applications to Power Series

      In the following, some interesting results in the theory of power series are deduced from the fact that the sequences (nα) with irrational α are u.d. mod 1 (see Example 2.1).

      THEOREM 2.2. Let α be a real number, and let g of positive degree. Define

      Then G(x) is a rational function if and only if α is a rational number.

      PROOF. The proof is based on the following auxiliary result: Let α be an irrational number, and let S be a finite set of nonintegral real numbers. Then there are infinitely many positive integers m such that

      (2.4)

      and also infinitely many positive integers n such that

      (2.5)

      Observe that (2.4) is equivalent to

      and that (2.5) is equivalent to

      and also that these relations follow easily from the fact that the sequence (nα), n = 1, 2, ... , is u.d. mod 1—or in fact from the property that the sequence ({nα}) is everywhere dense in I.

      Now we turn to the proof of the theorem. Let α be irrational. If G(x) were rational, then polynomials A(x) and B(x), of degrees a ≥ 1 and b, respectively, would exist such that G(x) = B(x)/A(x). Assume that

      From A(x)G(x) = B(x) it follows, by equating corresponding coefficients, that

      (2.6)

      Since g is a polynomial of degree p ≥ 1, we have

      so that (2.6) implies

      (2.7)

      Moreover, (2.6) and (2.7) imply

      (2.8)

      We have [nα + rα] = [{nα} + rα] + [nα], and so

      Therefore, after multiplying both sides of this last equality by cr and summing from r = 1 to r = a, for large n one obtains using (2.8),

      (2.9)

      For p = 1 the last sum on the left of (2.9) is empty, and if p ≥ 2, we have

      So we arrive at

      (2.10)

      The numbers rot in (2.10) are not integers. Thus, according to the auxiliary result and (2.10) we can find integers m and n such that the expressions

      and

      differ from 0 as little as we please, which contradicts (2.7). In this way, it is shown that if α is irrational, G(x) is not a rational function.

      Now assume that α is rational. Set α = c/d, where c and d are integers with d > 0. Applying the division algorithm, we have n = md + r with 0 ≤ r ≤ d - 1, and so

      Then Now

      is rational, and so it is shown that G(x) is rational.

      THEOREM 2.3. Let α be a positive number and let

      Then F(x) is a rational function if and only if α is rational.

      PROOF. Suppose that α is irrational. Let X(n) be the number of solutions of n = [tα] in positive integers t. Then

      Now X(n) is the number of integers t satisfying n < tα < n + 1 ; hence,

      According to Theorem 2.2, F(x) is not a rational function.

      Suppose that α is rational. Write α = c/d with positive integers c and d. Then, using t = md + r with 0 ≤ r ≤ d - 1, we have

      so that F(x) is rational.

      THEOREM 2.4. Let f for all but finitely many positive integers m. Let α be irrational. Then the power series

      cannot be analytically extended across the unit circle {z : |z| = 1}.

      PROOF. We recall the following theorem of Frobenius (see Knopp [1, pp. 507-508] and G. M. Petersen [2, pp. 48-49]). Let (cn), n = 1, 2, ... , be a sequence of complex numbers with the property that

      exists and equals c. then we have limr→1-0 (1 - r)Φ(r) = c.

      Now we turn to the proof of our theorem. We have, according to the definition of G(z),

      Since (nα) is u.d. mod 1, one obtains from Corollary 1.1 the relation

      Using the theorem of Frobenius, we get

      (2.11)

      For m ≥ m0 we have dm ≠ 0. So (2.11) implies that if z → e²πimα along the radius, the function value G(z) tends to oo, and therefore, G has singularities on an everywhere dense subset of {z : |z| = 1}.

      Fejér’s Theorem

      As another consequence of the Weyl criterion, we obtain a theorem that will provide many more examples of sequences that are u.d. mod 1.

      THEOREM 2.5. Let (f(n)), n = 1, 2, ... , be a sequence of real numbers such that Δf(n) = f(n + 1) - f(n) is monotone as n increases. Let, furthermore,

      (2.12)

      Then the sequence (f(n)) is u.d. mod 1.

      PROOF. For every pair of real numbers u and v we have

      (2.13)

      Now set u = hf (n + 1) and v = hf(n), where h is a nonzero integer. Then, according to (2.13),

      hence,

      (2.14)

      Then,

      where we used (2.14) in the last step. Because of the monotonicity of Δf (n), we get

      and therefore, in view of (2.12),

      COROLLARY 2.1: Fejér’s Theorem. Let f(x) be a function defined for x ≥ 1 that is differentiable for x ≥ x0. If f‘(x) tends monotonically to 0 as x → ∞ and if limx→∞ x|f’(x)| = oo, then the sequence (f(n)), n = 1, 2, ... , is u.d. mod 1.

      PROOF. The mean value theorem shows that Δf(n) satisfies the conditions of Theorem 2.5, at least for sufficiently large n. The finitely many exceptional terms do not influence the u.d. mod 1 of the sequence.

      EXAMPLE 2.7. Fejér’s theorem immediately implies the u.d. mod 1 of the following types of sequences: (i) (αnσlogτ n), n = 2, 3, ... , with α ≠ 0, 0 < σ < 1, and arbitrary τ; (ii) (α logτ n), n = 1, 2, ... , with α ≠ 0 and τ > 1; (iii) (αn logτ n), n

      The following simple result shows that the second condition in (2.12) cannot be relaxed too much.

      THEOREM 2.6. If a sequence (f(n)), n

      PROOF. Suppose that (f(nFor any two real numbers u and v, we have

      (2.15)

      and so,

      On the other hand,

      By a well-known Tauberian theorem (Hardy [2, p. 121], G. M. Petersen [2, p. 51]) it follows that limn→∞ e²πif(n) = 0, an obvious absurdity.

      An Estimate for Exponential Sums

      Although Corollary 2.1 is a very powerful result, there are various interesting sequences to which it does not apply. For instance, the question whether (n log n), n = 1, 2, ... , is u.d. mod 1 cannot be settled by appealing to Fejér’s theorem. In such cases, the following estimate may prove to be useful. We first need some technical lemmas. The values of the absolute constants will not be important in these estimates.

      LEMMA 2.1. Suppose the real-valued function f has a monotone derivative f‘ on [a, b] with f’(x) ≥ λ > 0 or f‘(x) ≤ -λ < 0 for x ∈ [a, bwe have |J| < 1/λ.

      PROOF. We have

      and therefore, an application of the second mean value theorem yields, with some x0 ∈ [a, b],

      LEMMA 2.2. Let f be twice differentiable on [a, b] with f"(x) ≥ ρ > 0 or f"(x) ≤ -ρ < 0 for x ∈ [a, b]. Then the integral J

      PROOF. We may suppose that f"(x) ≥ ρ for x e [a, b]; otherwise, we replace f by -f. We note that f‘ is increasing. Suppose for the moment that f’ is of constant sign in [a, b], say f‘ ≥ 0. If a < c < b, then f’(x) ≥ (c - a)ρ for c ≤ x ≤ b by the mean value theorem. Therefore, by Lemma 2.1,

      and choosing c so as to make the last sum a minimum, we obtain |JIn the general case, [a, b] is the union of two intervals in each of which f‘ is of constant sign, and the desired inequality follows by adding the inequalities for these two intervals.

      LEMMA 2.3. Let f‘ be monotone on [a, bfor x ∈ [a, bwe have

      (2.16)

      PROOF. We start from the Fourier-series expansion

      valid for all x . For m (sin 2πhx)/πh, x , be the mth partial sum. The functions χm, m = 1, 2, ... , are uniformly bounded as is seen easily after summation by parts. Therefore,

      (2.17)

      Now for m ≥ 1 we have

      Since the functions f‘/(f’ ± han application of the second mean value theorem shows that

      and so

      (2.18)

      Equations (2.17) and (2.18) imply (2.16).

      THEOREM 2.7. Let a and b be integers with a < b, and let f be twice differentiable on [a, b] with f"(x) ≥ p > 0 or f"(x) ≤ -ρ < 0 for x ∈ [a, b]. Then,

      (2.19)

      PROOF. We write

      (2.20)

      with

      (2.21)

      The sum over p in (2.20) is in reality just a finite sum. Let p be an integer for which the sum in (2.21) is nonvoid. Since f‘ is monotone, this sum is over consecutive values of n, say from n = ap to n = bp. With Fp(x) = f(x) - px, we get

      Enjoying the preview?
      Page 1 of 1