The Lumenary · First-year graduate

Ergodic theory

Name: ______________________

Date: ______________________

You will learn to

Define measure-preserving systems, ergodicity and mixing, and verify invariance of Lebesgue measure for rotations and the doubling map and of the Gauss measure for the Gauss map
Prove the Poincaré recurrence theorem
Prove von Neumann's mean ergodic theorem and Birkhoff's pointwise ergodic theorem (via the maximal ergodic theorem), and interpret "time average equals space average"
Decide ergodicity and mixing for circle rotations, the doubling map and Bernoulli shifts
Use the Gauss map and the ergodic theorem to derive the statistics of continued fraction digits

1.
Which maps of $[0, 1)$ preserve Lebesgue measure $\lambda$ (that is, $\lambda(T^{-1}A) = \lambda(A)$ for all Borel $A$ )? Select all that apply.
- A. $T(x) = 2x \bmod 1$
- B. $T(x) = x^2$
- C. $T(x) = x + \sqrt 2 \bmod 1$
- D. $T(x) = 1 - x$ (for $x \ne 0$ ), $T(0) = 0$
2.
Iterate the Gauss map $G(x) = 1/x - \lfloor 1/x \rfloor$ on $x_0 = \frac{7}{30}$ until you reach $0$ , recording the digits $a_{n+1} = \lfloor 1/x_n \rfloor$ . What is the sum of the digits?
3.
The translation $T(x) = x + 1$ on $\R$ preserves Lebesgue measure, yet no point of $[0, 1)$ ever returns to $[0, 1)$ . Which hypothesis of the Poincaré recurrence theorem fails?
- A.The measure of the whole space is finite.
- B. $T$ is measure-preserving.
- C. $T$ is invertible.
- D. $[0, 1)$ has positive measure.
4.
Which of these measure-preserving maps of $([0, 1), \lambda)$ is ergodic but not mixing?
- A. $x \mapsto x + \frac{\sqrt 5 - 1}{2} \bmod 1$
- B. $x \mapsto 2x \bmod 1$
- C. $x \mapsto x + \frac25 \bmod 1$
- D. $x \mapsto x$
5.
The doubling map $D$ is ergodic for Lebesgue measure. Let $f = \mathbf 1_{[0, 1/2)}$ . Which statement is correct?
- A.For Lebesgue-almost every $x$ , $\frac1N\sum_{n<N} f(D^n x) \to \frac12$ , but there are points (for example $x = 0$ ) where the average is $1$ .
- B.For every $x$ , the average tends to $\frac12$ , because $D$ is ergodic.
- C.The average converges to $\frac12$ only at rational $x$ .
- D.The averages need not converge anywhere, since $D$ is not invertible.
6.
Which Lean statement formalises "rotation of the circle $\R/\Z$ by $\alpha$ is ergodic exactly when $\alpha$ is irrational"? (AddCircle (1 : ℝ) is $\R/\Z$ with Haar measure, and Ergodic f includes measure preservation.)
- A.theorem t (α : ℝ) : Ergodic (fun y : AddCircle (1 : ℝ) => (α : AddCircle (1 : ℝ)) + y) ↔ Irrational α
- B.theorem t (α : ℝ) : Ergodic (fun y : AddCircle (1 : ℝ) => (α : AddCircle (1 : ℝ)) + y)
- C.theorem t (α : ℝ) (h : Irrational α) : Ergodic (fun y : AddCircle (1 : ℝ) => 2 • y + α)
- D.theorem t (α : ℝ) : Ergodic (fun y : AddCircle (1 : ℝ) => (α : AddCircle (1 : ℝ)) + y) ↔ α ≠ 0
7.
In the proof of von Neumann's mean ergodic theorem, why do the averages $\frac1N\sum_{n<N} U^n h$ tend to $0$ for $h = Ug - g$ ?
- A.The sum telescopes to $\frac1N(U^N g - g)$ , whose norm is at most $\frac{2\|g\|}{N}$ because $\|U\| \le 1$ .
- B.Because $U^n h \to 0$ for every $h$ .
- C.Because $Ug - g$ is orthogonal to itself.
- D.By Birkhoff's pointwise ergodic theorem.
8.
Write cf_digits(p, q) returning the list of continued fraction digits $[a_1, a_2, \ldots]$ of the rational $p/q \in (0, 1)$ (with $0 < p < q$ ), by iterating the Gauss map with exact integer arithmetic (Euclid's algorithm). Then digit_frequency(digits, k) should return the fraction of the digits equal to k.
Computational — Practice

Answer key — Ergodic theory

1.
(a), (c) and (d) preserve $\lambda$ ; (b) does not, since $\lambda(T^{-1}[0, \frac14)) = \lambda([0, \frac12)) = \frac12$ . For (a), $T^{-1}[a, b) = [\frac a2, \frac b2) \cup [\frac{1 + a}2, \frac{1 + b}2)$ . Note that $T(A)$ is irrelevant: $2x \bmod 1$ maps $[0, \frac12)$ onto $[0, 1)$ .
2.
$x_0 = 7/30$ : $30/7 = 4 + 2/7$ , so $a_1 = 4$ , $x_1 = 2/7$ . Then $7/2 = 3 + 1/2$ , so $a_2 = 3$ , $x_2 = 1/2$ . Then $2 = 2 + 0$ , so $a_3 = 2$ , $x_3 = 0$ . Thus $\frac{7}{30} = [0; 4, 3, 2] = \cfrac{1}{4 + \cfrac{1}{3 + \cfrac12}}$ , and the digits sum to $9$ . Rational numbers have finite Gauss orbits; they form a null set, so they do not affect almost-everywhere statements such as the Gauss–Kuzmin law.
3.
The theorem requires $\mu(X) < \infty$ . Here $B = [0, 1)$ (no point returns) and $T^{-n}B = [-n, -n + 1)$ are disjoint intervals of measure $1$ ; their union has infinite measure, which is no contradiction on $\R$ . In a finite measure space it would be, which is the whole proof.
4.
(a). Rotation by an irrational angle is ergodic: an invariant $L^2$ function has $\hat f(n)(e^{2\pi in\alpha} - 1) = 0$ , so $\hat f(n) = 0$ for $n \ne 0$ . It is not mixing, since $\lambda(A \cap R^{-n}A) = \frac12 - \|n\alpha\|$ does not converge to $\frac14$ (Dirichlet's theorem gives infinitely many $n$ with $\|n\alpha\| < 1/n$ ). The doubling map is mixing; the rational rotation and the identity are not ergodic.
5.
(a). By Birkhoff, the averages tend to $\int f \, d\lambda = \frac12$ for almost every $x$ ; via binary expansions this is Borel's normal number theorem for the digit $0$ . But $D(0) = 0$ , so the average at $0$ is $1$ , and $x = \frac17 = 0.\overline{001}_2$ has average $\frac23$ (the orbit reads off the digits $0, 0, 1, 0, 0, 1, \ldots$ ). The exceptional set is null but non-empty — indeed uncountable.
6.
Option (a). For $\alpha = \frac12$ , (b) and (d) claim ergodicity of a rotation of order $2$ , which is false. (c) concerns the map $y \mapsto 2y + \alpha$ rather than a rotation. The Lean proof chains Mathlib's results: a rotation is ergodic iff its angle has infinite additive order, iff its multiples are dense, iff $\alpha$ is irrational.
7.
$\sum_{n<N} U^n(Ug - g) = \sum_{n<N}(U^{n+1}g - U^n g) = U^N g - g$ , so the average has norm $\frac1N\|U^N g - g\| \le \frac{2\|g\|}{N} \to 0$ . Since the averaging operators have norm at most $1$ , the same holds on the closure of the coboundaries, which is the orthogonal complement of the invariant vectors; on invariant vectors the averages are constant. Together: $\frac1N\sum U^n h \to Ph$ .
8.
```
def cf_digits(p, q):
    digits = []
    while p != 0:
        digits.append(q // p)
        p, q = q % p, p
    return digits

def digit_frequency(digits, k):
    if not digits:
        return 0.0
    return digits.count(k) / len(digits)
```
One step of the Gauss map on $p/q$ is one step of Euclid's algorithm on $(q, p)$ : $G(p/q) = (q \bmod p)/p$ , and the digit is the quotient. For rationals the orbit ends at $0$ after $O(\log q)$ steps, so their digits are not 'typical'; for Lebesgue-almost every real number, Birkhoff's theorem for the Gauss measure says the frequency of the digit $k$ tends to $\log_2(1 + \frac{1}{k(k+2)})$ , which for $k = 1$ is about $0.415$ .