You are here

Ergodic Theory of Numbers

Karma Dajani and Cor Kraaikamp
Mathematical Association of America
Publication Date: 
Number of Pages: 
Carus Mathematical Monographs 29
[Reviewed by
Jim Walsh
, on

What do √2, π, and e have in common? Well, you're right, each is irrational! Perhaps more surprisingly, they also share the following trait: little is known about the distribution of digits in their decimal expansions. In particular, it is not known if any of these constants (or any other fundamental constant that might leap to mind) is a normal number. The book under review contributes to efforts aimed at analyzing distribution questions for decimal and other types of expansions via a discrete dynamical systems approach [e.g., 1, 4, and references therein]. Briefly, Dajani and Kraaikamp view these expansions as iterations of a corresponding measure-preserving transformation on [0,1) which, it turns out, is ergodic. The ergodic theorem is then applied to, as stated in the preface, "obtain old and new results in an elegant and straightforward manner".

Ergodic Theory of Numbers (ETN) grew out of a summer course given for first-year graduate students and focuses on the interplay between number theory and ergodic theory. (Here, number theory refers to the distribution of digits in various expansions, as well as to Diophantine approximations). Working through ETN is in every way a "discovery-based" learning experience. Written along the lines of [3], each chapter utilizes exercises to present the material. Any potential reader must be prepared with paper and pencil and possess a willingness to tackle challenging problems.

Let me describe the contents of ETN, inserting observations where appropriate. The first chapter begins with an introduction to decimal (base 10) expansions. The dynamical systems connection is provided by the map T(x) = 10x (mod 1) for x in [0,1). Iterates of T, along with appropriate cylinder sets, determine elements from the digit set {0,1,...,9} in the decimal expansion of x. That is, if In=[n/10,(n+1)/10), the jth digit in the decimal expansion of x is the element aj of {0,1,...,9} if Tj-1(x) belongs to Iaj. Thus, if x = 0.a1a2a3..., then T(x) = 0.a2a3a4..., so that

x = a1/10 + T(x)/10 = a1/10 + a2/100 + T(T(x))/100 = ...

The mapping T is called a shift map.

Properties of the dynamical system (T,λ), where λ represents Lebesgue measure, are used to investigate digit distribution questions for decimal expansions. To wit, (T,λ) is ergodic. Let A=[i/10,(i+1)/10). For x in [0,1), let Cn denote the number of times the (j-1)st iterate Tj-1(x) lands in A for j between 1 and n (this equals the number of occurrences of the digit i in the first n digits in the decimal expansion of x). The Ergodic Theorem implies that Cn/n tends to λ(A) = 1/10 as n tends to infinity for λ-almost every x. This in turn implies that each of the digits 0, 1, ..., 9 occurs with frequency 1/10 in the decimal expansion of λ-almost every x. This argument can be augmented to show that any string of digits of length k occurs with frequency 1/10k in the decimal expansion of x, i.e., that λ-almost every x is normal (base 10).

Ergodic theory requires an understanding of measure theory, so the authors jump from decimal expansions to the measure theory apparatus. A heuristic introduction to Lebesgue measure is followed by a more careful treatment of various standard analysis topics (generating sigma- and semi-algebras, complete measure spaces, measurable functions). Of course, many of the basic analysis results needed are assigned as exercises. I found the heuristic introduction to Lebesgue measure insufficient; a more detailed introduction would serve the reader better. Similarly, the introduction to independent identically distributed random variables and probability distributions on page 16 would benefit from the inclusion of at least the definitions of these terms. The authors do show the decimal map T above preserves Lebesgue measure to motivate the definition of measure-preserving transformations.

Included in this second section of ETN are definitions of one- and two-sided Bernoulli shifts, and what it means for two dynamical systems to be isomorphic (one needs a topological conjugacy which preserves the measures). The reader must have some familiarity with measure theory to have a go at this material and hope for any success in completing the exercises.

Continued fraction expansions serve as the second motivating example in chapter 1. Once again the dynamical view is provided by iteration of a transformation, this time the Gauss map defined by T(0) = 0 and T(x) = 1/x (mod 1) for x not equal to 0. Letting In = [1/(n+1),1/n) for each n > 0, the jth "digit" (partial quotient) in the continued fraction expansion of x is the positive integer aj if Tj-1(x) is in Iaj. Thus, if x in [0,1) has continued fraction expansion x = [a1, a2, a3, ...] then T(x) has continued fraction expansion T(x) = [a2, a3, a4, ...], so that

x = 1/(a1 + T(x)) = 1/(a1 + 1/(a2 + T(T(x)))) = ...

In this case, the digit set (containing the ai) is the set of positive integers, a countably infinite set, in contrast to the digit set for decimal expansions. There are also countably many first-order cylinder sets In partitioning [0,1).

Basic properties of continued fractions and nth-order convergents are presented in a sequence of exercises that make clever use of Möbius transformations and matrices. Chapter 1 concludes by introducing the Gauss measure and inviting the reader to show the Gauss map preserves Gauss measure.

The second chapter of ETN presents generalizations of decimal expansions. For an integer n>1, the n-ary expansion of x in [0,1) is its base-n expansion. Such expansions are linked to iterates of T(x) = nx (mod 1), which also preserves Lebesgue measure. Attention is then given to Lüroth series expansions, though the motivation for considering such series is meager. The partition of [0,1) for a Lüroth series expansion is given by the intervals [1/(n+1),1/n), n>0, and the corresponding map T is linear (with positive slope) and bijective with range [0,1) on each atom of the partition. In a procedure similar to that used to generate n-ary expansions (though more computationally intricate), iterates of T determine digits from the set {2,3,...} in the Lüroth series expansion of x. Working through exercises, the reader proves that T preserves Lebesgue measure; that each rational number has a finite or periodic Lüroth series expansion; and that the dynamical system T on [0,1) with Lebesgue measure is isomorphic to a one-sided Bernoulli shift on the sequence space {2,3,...}N with a certain weighted product measure.

At this point the reader is introduced to Generalized Lüroth Series expansions (GLS). To dynamically generate a GLS, begin with a partition of [0,1) given by a finite or countable collection of intervals, with the sum of the lengths of the intervals equaling one. The digit set is correspondingly finite or countably infinite, and the associated map T is linear and bijective onto [0,1) on each subinterval. Thus, GLS include n-ary and Lüroth series expansions, but also include maps such as the tent map. In particular, any result relating to the distribution of digits in a GLS also applies to n-ary expansions. That the GLS map T preserves Lebesgue measure is assigned.

The presentation of one final motivating class of expansions concludes chapter 2. Fix a noninteger β and consider the map Tβ(x) = βx (mod 1). Mimicking the dynamical approach to n-ary expansions, Tβ can be used to generate a β-series expansion of x in [0,1) in powers of 1/β. The digit set for a β-expansion is the set of integers from 0 to the greatest integer not exceeding β. Of note is the fact that Tβ does not preserve Lebesgue measure (you might draw the graph of Tβ for β equaling the golden mean, for example). The authors present a piecewise constant density function which is the Radon-Nikodym derivative of a Tβ-invariant measure in the case β equals the golden mean. Finding such an invariant measure is, in general, a difficult task. In chapter 4 a method is given for obtaining such a Tβ-invariant measure via a connection with, interestingly, GLS expansions.

Chapter 3 presents Birkhoff's Ergodic Theorem. As the statement of this theorem contains integrals, the reader is first introduced to the Lebesgue integral as the limit of integrals of simple functions. Standard analysis questions are presented in exercises (e.g., if the integral of a nonnegative measurable f over the space is zero, then f equals 0 almost everywhere).

The Ergodic Theorem is nicely motivated by the Strong Law of Large Numbers (SLLN). The authors also do a good job explaining why SLLN cannot be used directly to determine normality, and to what extent the Ergodic Theorem generalizes SLLN. I was at first disappointed to find the Ergodic Theorem only proved in ETN in the special case where the L1 function f is a characteristic function. In retrospect, this omission is understandable. Firstly, the case proved in ETN does give a flavor of the general proof. Secondly, if Dajani and Kraaikamp included every detail of all that is presented in ETN, their slim volume (177 pages) would have evolved into a thick tome of a much different nature.

One of the major results in chapter 3 states that a GLS transformation T is ergodic with respect to Lebesgue measure. The Ergodic Theorem is then used to prove that, for a GLS expansion, Lebesgue-almost every point in [0,1) is normal. Borel's Normal Number Theorem for n-ary expansions falls simply out of this general treatment.

The authors consider the ergodic properties of β- and continued fraction expansions in chapter 3. Recall the β-expansion map Tβ does not preserve Lebesgue measure λ when β is a noninteger. The map Tβ is ergodic, however, with respect to λ, a point of confusion at first as λ is not Tβ-invariant. The authors point out that in chapter 4 they prove the existence of a Tβ-invariant measure ν which is equivalent to Lebesgue measure. The reader is left to conclude that (Tβ,ν) is ergodic.

Using the invariant measure ν and the Ergodic Theorem, one can compute the frequency of digits in a β-expansion. For example, for β equaling the golden mean, the frequency of 0's in the β-expansion of λ-almost every point in [0,1) is (5 + √5)/10 = 0.7236...

One other comment concerning this treatment: the authors state the invariant measure ν is unique. To prove ergodicity, they resort to Knopp's Lemma. It may be simpler to prove (Tβ,ν) is ergodic by showing that any unique invariant measure is ergodic.

The Gauss map T preserves the Gauss measure μ. The proof that (T,μ) is ergodic is provided, for the most part, by the authors (the reader must solve one exercise to complete the proof). Once completed, an exercise asks one to show that (Tβ,ν) is not Bernoulli (and so not isomorphic to a GLS expansion), but that it is strong mixing. This book requires a nontrivial level of motivation on the part of the reader!

Chapter 3 concludes with several beautiful results, obtained via the Ergodic Theorem, concerning continued fraction transformations. For x in [0,1), let pn/qn = [a1, a2, a3, ..., an] denote the continued fraction convergents for x. The authors prove or assign, for example, the following results of P. Lévy. Fix a positive integer a, and let Cn denote the number of occurrences of a in the first n entries in the continued fraction expansion of x. Then for almost all x in [0,1), Cn/n tends to log(1 + 1/a(a+2))/log(2) as n tends to infinity. This implies, for instance, that the digit 1 occurs roughly 41.5% of the time in a typical continued fraction expansion. Lévy also proved log(qn)/n tends to π2/(12log2) and log|x-pn/qn|/n tends to -π2/(6log2) as n tends to infinity; the authors provide alternative proofs of these results.

Other intriguing results, due to A. Khintchine, are assigned. These include the fact that (a1 + ... + an)/n tends to infinity with n, while the ratio n/(1/a1 + ... + 1/an) tends to 1.7454...Quite a nice payoff for time invested in invariant measures and the Ergodic Theorem!

The goal of chapter 4 is to forge a connection between β-expansions and GLS expansions. This process begins with an introduction to induced transformations (Poincaré maps), integral transformations (suspensions), and factor maps. The Poincaré Recurrence Theorem is needed to define induced maps and so is presented here rather than with the invariant measure material (as in most texts). Kac's Lemma is assigned as an exercise.

The natural extension of a noninvertible dynamical system is introduced in chapter 4. The main result is that a β-transformation has a natural extension which, in turn, has a suitable GLS map as an induced transformation. Normalized two-dimensional Lebesgue measure is invariant under the extension, and an appropriate projection of this measure yields the Tβ-invariant measure ν encountered in chapter 3. This part of ETN is likely more appropriate for graduate students than advanced undergraduates.

The Ergodic Theorem, coupled with the natural extension machinery applied to the Gauss map, is used in chapter 5 to obtain arithmetical properties of the approximation coefficients for continued fraction expansions. In 1903 Borel proved that at least one of any three consecutive continued fraction convergents pi/qi, i = n-1, n, n+1, to an irrational number x satisfies Hurwitz' inequality:

|x - p/q| < 5-1/2q-2

This of course implies that infinitely many rationals p/q satisfy this inequality for any irrational x.

The authors go on to use dynamics to provide a new proof of a generalization of Borel's theorem and to prove (not assign!) a result due to Barbolosi and Jager (1994), generalizing a result of Legendre's, that states precisely when a given rational is a continued fraction convergent for the irrational x. Chapter 5 concludes with a proof of the Doeblin-Lenstra conjecture and an introduction to other types of continued fraction expansions.

Entropy is a difficult topic to motivate and introduce to a "beginner". The authors tackle entropy in the final chapter of ETN, beginning with the two-sided shift map on {1,2,...,n}Z. The sequence space is endowed with a product measure for which the probability of symbol i is denoted pi, the pi summing to 1. Entropy in this case is defined to be -Σ pilog(pi), though the motivation for this definition is scanty. From this point on I found the treatment of entropy quite readable, appropriate for self-guided investigation. For example, several exercises are included to ensure understanding of the various properties of partitions.

The authors prove entropy is an isomorphism invariant, and that a measure-preserving transformation has the same entropy as its natural extension. Using the latter fact and the Kolmogorov-Sinai and Krieger's Generator theorems, the entropy of a GLS transformation is computed. The entropy of a β-expansion transformation is shown to be log(β).

Computation of the entropy of the continued fraction map is achieved with the help of the Shannon-McMillan-Breiman theorem. In fact, the reader provides the final piece of the proof showing the entropy of the continued fraction map is π2/(6log2). Upon completing chapter 6, I felt the authors had provided a full and comprehensive treatment of GLS, β- and continued fraction expansions.

I should note that ETN does not present a detailed treatment of ergodic theory. Ergodicity and the Ergodic Theorem are used as tools to arrive at results of interest to the authors. Likewise, ETN is neither a measure theory, dynamical systems, nor probability text. That being said, any reader willing to appeal to the references to round out the treatment of any of these topics in ETN will come away with both an increased understanding of the ideas and an appreciation for the usefulness of these topics. This is a good thing.

Though aimed at beginning graduate students, much of ENT is appropriate for advanced undergraduates having some background in measure theory. For example, during this 2002-03 academic year I am supervising a senior "honors" student (Jon Armel) at Oberlin as he works his way through this book. Jon began this project in September 2002, concurrent to his enrolling in my fall semester analysis class (text: Royden). We essentially skipped any measure theory topics in chapter 1 of ETN that Jon had not yet seen in my class, returning to them after acquiring sufficient background. During the fall semester Jon worked up through the full proof of the Ergodic Theorem (as presented in [2]), completing a significant number of exercises along the way. Though we will surely not complete ETN this year, I hope to reach some of the beautiful results in chapter 5.

I enjoyed reading ETN. The mathematics is interesting, there are relatively few typos, and the writing style is engaging. The second author has received a teacher-of-the-year award from his home university, and I think this expository talent is apparent in the presentation style. I enjoyed the "Further Reading" comments at the end of each chapter, providing a guide to the literature, complete with occasional warnings that an indicated book was "not appropriate for beginners." I also like the fact that any reader willing to work hard will be exposed to problems of current research interest. For example, I was surprised to learn that little is known about the set of numbers which have a finite or periodic β-expansion, and that Pisot and Salem numbers are connected with this problem.

I do have a few minor quibbles. Though ETN is generally well-written, the material is presented unevenly at times in terms of the level of difficulty. A prime example is the presentation of measure theory topics following a gentle introduction to decimal expansions in chapter 1.

The authors squeeze an abundance of material into 177 pages. This is achieved partially via the inclusion of numerous exercises (so the reader provides the proof, not the authors; in general, I feel the ratio of exercises to results proved by the authors is too large). Certain topics, though, are shortchanged. The various types of mixing, for example, are presented on essentially one page. This is followed by an exercise asking the reader to show that Bernoullicity implies strong mixing, strong mixing implies weakly mixing, and weakly mixing implies ergodicity. This is not reasonable. The material on variants of continued fraction expansions in chapter 5 was quite technical and did not fit so well with the overall presentation.

Carus Mathematical Monographs are "intended for the wide circle of thoughtful people familiar with basic graduate or advanced undergraduate mathematics encountered in the study of mathematics itself or in the context of related disciplines who wish to extend their knowledge without prolonged and critical study of the mathematical journals and treatises." Ergodic Theory of Numbers is completely in line with this directive and is a welcome addition to the prestigious Carus series.

[1] Bailey, D., Crandall, R., "On the random character of fundamental constant expansions," Experimental Mathematics 10 (2) (2001), 175-190.

[2] Boyarsky, A., Góra, P., Laws of chaos : invariant measures and dynamical systems in one dimension (Birkhäuser, Boston, MA), 1997.

[3] Edgar, E., Measure, topology, and fractal geometry (Springer-Verlag, New York, NY), 1990.

[4] Lagarias, J., "On the normality of arithmetical constants," Experimental Mathematics 10 (2001), 355-368.

Jim Walsh is associate professor of mathematics at Oberlin College. His research area is dynamical systems.