Real Numbers and Infinite Games, Part II

In my last post, I wrote about two infinite games whose analysis leads to interesting questions about subsets of the real numbers. In this post, I will talk about two more infinite games, one related to the Baire Category Theorem and one to Diophantine approximation. I’ll then talk about the role which such Diophantine approximation questions play in the theory of dynamical systems.

The Choquet game and the Baire Category Theorem

The Cantor game from Part I of this post can be used to prove that every perfect subset of ${\mathbf R}$ is uncountable. There is a similar game which can be used to prove the Baire Category Theorem. Let $X$ be a metric space. In Choquet’s game, Alice moves first by choosing a non-empty open set $U_1$ in $X$ . Then Bob moves by choosing a non-empty open set $V_1 \subseteq U_1$ . Alice then chooses a non-empty open set $U_2 \subseteq V_1$ , and so on, yielding two decreasing sequences $U_n$ and $V_n$ of non-empty open sets with $U_n \supseteq V_n \supseteq U_{n+1}$ for all $n$ . Note that $\bigcap U_n = \bigcap V_n$ ; we denote this set by $U$ . Alice wins if $U$ is empty, and Bob wins if $U$ is non-empty.

Exercise 1: Show that if $X$ is complete (i.e., every Cauchy sequence converges) then Bob has a winning strategy. [Hint: If $F_n$ is a decreasing sequence of closed sets in $X$ whose diameter tends to zero then $\bigcap F_n \neq \emptyset$ .]

Exercise 2: Show that if $X$ contains a non-empty open set $O$ which is meager (i.e., $O$ is a countable union of closed sets with empty interior), then Alice has a winning strategy. [Hint: Alice starts with $U_1 = O$ and responds to each choice $V_n$ of Bob’s with $V_n \backslash F_n$ .]

Combining these two observations, we obtain the Baire Category Theorem:

A non-empty complete metric space cannot be meager.

The Baire Category Theorem is used in functional analysis to prove the Open Mapping Theorem, Closed Graph Theorem, and Uniform Boundedness Principle. See this page for some other interesting applications (my personal favorite being the fact that the field $\bar{\mathbf Q}_p$ is not complete). The Baire Category Theorem will make a guest appearance below in our discussion of Cremer points for complex dynamical systems.

Diophantine numbers

An irrational number $\xi$ is said to be Diophantine (of order at most $\kappa > 0$ ) if there exists $\epsilon > 0$ so that $|\xi-\frac{p}{q}| > \frac{\epsilon}{q^\kappa}$ for every rational number $\frac{p}{q}$ . By a theorem of Liouville, an algebraic number of degree $d$ is Diophantine of order at most $d$ . Non-Diophantine irrational numbers, which are therefore transcendental, are often called Liouville numbers. The first proof of the existence of transcendental numbers, by Liouville in 1844, combined the above theorem with the observation that well-approximated numbers such as $\sum_{k=0}^\infty 10^{-k!}$ are non-Diophantine. (Cantor later gave a simple non-constructive proof of the existence of transcendental numbers using his theorem that ${\mathbf R}$ is uncountable.) While Liouville numbers are dense in the real line, they are rare in the sense that the Hausdorff dimension of the set of all Liouville numbers is zero.

By a famous 1955 theorem of Klaus Roth (for which he won a Fields Medal), every algebraic irrational number is Diophantine of order $2 + \epsilon$ for every $\epsilon > 0$ . This result and its subsequent generalizations (such as Schmidt’s Subspace Theorem) are incredibly important in the modern subject of Diophantine Geometry; see for example this survey paper by Corvaja and Zannier.

Schmidt’s Game and Badly Approximable Numbers

It is an exercise using the pigeonhole principle to see that there are no Diophantine numbers of order less than 2. Diophantine numbers of order exactly 2 are called badly approximable; another name for them is bounded type, since being Diophantine of order 2 is equivalent to having bounded continued fraction coefficients. These are the ‘most Diophantine’ numbers. Although the set of badly approximable numbers is small in the sense that it has Lebesgue measure zero, it is also rather large in the sense that it has Hausdorff dimension 1. The latter fact was proved by Wolfgang Schmidt via an infinite two-player game played on the real number line.

Schmidt’s game goes as follows. Fix real numbers $\alpha, \beta \in (0,1)$ and a subset $S$ of the real line. First Bob picks a closed interval $B_1$ . Then Alice picks a closed interval $A_1 \subset B_1$ whose length is $\alpha$ times the length of $B_1$ . Next Bob chooses a closed interval $B_2 \subset A_1$ whose length is $\beta$ times the length of $A_1$ . Alice then picks a closed interval $A_2 \subset B_2$ whose length is $\alpha$ times the length of $B_2$ , and so on. Alice wins the game if $\bigcap A_i \in S$ , and Bob wins the game if $\bigcap A_i \not\in S$ .

Winning sets

We say that $S$ is a winning set if there exists an $\alpha > 0$ such that Alice has a winning strategy for all $0 < \beta < 1$ . Schmidt proved that the set of badly approximable numbers has Hausdorff dimension 1 by establishing the following two facts:

Every winning set has Hausdorff dimension 1.
The set of all badly approximable real numbers is winning.

Schmidt also describes various other winning sets, e.g. the set of real numbers with infinitely many zeros in their base 10 representation.

Interlude: Complex dynamical systems

Much of the theory of dynamical systems centers around the problem of determining whether a periodic orbit is stable or unstable. Such questions originally arose in celestial mechanics, and are known to be extremely difficult. There is a model of this situation in complex dynamics which is much simpler than the case of planetary motion, yet still rich enough to hold subtle and interesting surprises.

In the theory of dynamics of one complex variable, as pioneered by Fatou and Julia, one starts with a rational function $f \in {\mathbf C}(z)$ of degree at least 2 and studies the behavior of points of ${\mathbf C}$ under iteration. The “stable” locus, consisting of points whose nearby neighbors stay close together under iteration, is called the Fatou set. (More precisely, the Fatou set consists of all points with an open neighborhood on which the iterates of $f$ form an equicontinuous family.) Its complement, the Julia set, consists of the “unstable” points for which the orbits of even very small neighborhoods eventually get very big. (For a wealth of information about Fatou and Julia sets, the reader should consult Milnor’s excellent book “Dynamics in One Complex Variable”.) One of the key problems in the theory is to determine under what conditions a periodic point belongs to the Fatou set (resp. Julia set).

For this, one associates to every periodic point a complex number $\lambda$ called its multiplier. (For a fixed point, the multiplier is just the derivative of $f$ ; for the general case see for example this blog post of mine.) If $|\lambda| > 1$ , the periodic point is called repelling and belongs to the Julia set. If $|\lambda| < 1$ , the periodic point is called attracting and belongs to the Fatou set. These results are easy, but the case where $|\lambda|=1$ (where the periodic point is called indifferent) is much more delicate. In this case, write $\lambda = e^{2 \pi i \xi}$ with $\xi \in {\mathbf R} /{\mathbf Z}$ ; the number $\xi$ is called the rotation number. If $\lambda$ is a root of unity, i.e., $\xi$ is rational, then the periodic point belongs to the Julia set. (This is also an easy result, though understanding what iteration near such a point looks like can be quite subtle.) Much harder to understand is the case where $\lambda$ is not a root of unity, i.e., $\xi$ is irrational; such a periodic point is called irrationally indifferent. In this case, whether the periodic point belongs to the Fatou set or the Julia set turns out to depend on how well $\xi$ can be approximated by rational numbers.

Let us assume for simplicity that the periodic point in question is a fixed point at the origin, so that $f(z) = \lambda z + a_2 z^2 + a_3 z^3 + \cdots$ near the origin. The key lemma in this situation is that an indifferent fixed point lies in the Fatou set if and only if $f$ is locally linearizable, meaning that there is a local holomorphic change of coordinates $z = h(w)$ which conjugates $f$ to the rotation $w \mapsto \lambda w$ , i.e., $f(h(w))=h(\lambda w)$ in a neighborhood of the origin. In 1927, Hubert Cremer proved that for a generic choice of $\xi$ , a rational function $f$ of degree at least 2 having the origin as an (irrationally) indifferent fixed point of rotation number $\xi$ is not locally linearizable, hence the origin belongs to the Julia set. Here generic means that it holds for a set $G$ containing a countable intersection of dense open subsets of ${\mathbf R} /{\mathbf Z}$ ; by the Baire Category Theorem, such a set $G$ must be dense and uncountable.

Diophantine approximation and Siegel discs

A Siegel disc.

It was an open problem whether Cremer’s theorem could be extended to all $\xi$ until Carl Ludwig Siegel proved in 1942 that if the irrational number $\xi$ is Diophantine then $f$ is locally linearizable, hence the origin belongs to the Fatou set. The corresponding component of the Fatou set, on which $f$ is conformally conjugate to an irrational rotation of the unit disc, is called a Siegel disc. Siegel’s proof of the existence of such irrational rotation domains, and the appearance of Diophantine approximation in this context, was a major milestone in the theory of dynamical systems.

The set of Diophantine numbers is dense in ${\mathbf R} /{\mathbf Z}$ and has full Lebesgue measure and Hausdorff dimension one. This means that, for a different but perfectly reasonable meaning of the word generic, Cremer’s theorem is completely wrong! As we saw from Schmidt’s game, the very special Diophantine numbers of bounded type already have Hausdorff dimension one.

Concluding remarks

1. For much more on infinite games played on the real number line, including a detailed history of the subject, see Telgarsky’s survey paper Topological games: On the 50th anniversary of the Banach-Mazur game. See also this Wikipedia page. My exposition of Choquet’s game is based on an exercise in the book Elements of Functional Analysis by Hirsch and Lacombe (Springer Graduate Texts in Mathematics 192, 1999).

2. Quadratic irrationals are badly approximable; it is unknown whether there are any other algebraic numbers which are badly approximable.

3. Some interesting variants of Schmidt’s Game are discussed in Curt McMullen’s paper Winning sets, quasiconformal maps, and Diophantine approximation. My exposition of Schmidt’s Game was influenced by the discussion in that paper.

4. For an excellent elementary introduction to the role of Diophantine conditions in the theory of dynamical systems, I recommend this article by Fields Medalist Jean-Christophe Yoccoz in the compilation “An Invitation to Mathematics” by Schleicher and Lackmann. (Our picture of a Siegel disc was taken from that article.) In particular, the reader can learn there about Brjuno numbers, which are more general than Diophantine numbers and also imply local linearlizability. Yoccoz proved in 1987 that if $f$ is a quadratic polynomial with irrational rotation number $\xi$ at the origin, then it is locally linearizable if and only if $\xi$ is a Brjuno number. It is unknown whether local linearizability implies that $\xi$ is Brjuno for more general rational (or even polynomial) maps $f$ .

5. Diophantine conditions on rotation numbers come up in the study of all sorts of dynamical systems, not just complex dynamics. For example, Herman and Yoccoz proved that if $f$ is a real-analytic diffeomorphism of ${\mathbf R} /{\mathbf Z}$ whose rotation number $\rho$ is Diophantine, then $f$ is real-analytically conjugate to the rotation $t \mapsto t+1 \pmod{1}$ . If $f$ is $C^\infty$ , they also proved the converse to this statement. Diophantine conditions also show up in celestial mechanics and related dynamical systems, in the context of the vast subject now known as KAM theory.

6. Although quite different in flavor from the games we’ve been considering in this post (since it involves a finite game), I can’t help mentioning this award-winning paper by David Gale which uses the fact that at least one player always wins the game of Hex to give a simple proof of the Brouwer Fixed Point Theorem in topology. In fact, Gale establishes the equivalence of these two results! There is also an exposition of Gale’s results in this blog post. In this post, it is shown that the Brouwer Fixed Point Theorem implies a version of the Jordan Curve Theorem which in turn implies that there is always exactly one winner in Hex.

7. If you know other examples of games which can be used to prove interesting mathematical theorems, please post to the comments section below!

5 thoughts on “Real Numbers and Infinite Games, Part II”

Pingback: Real Numbers and Infinite Games, Part I | Matt Baker's Math Blog
Malkym Lesdrae says:

April 16, 2017 at 2:12 am

Respectfully, there may be an error in the statement of the Baire Category Theorem. For example, \{0,1,2 \} is a non-empty subset of a complete metric space, but is certainly meager.

- Matt Baker says:
  
  April 17, 2017 at 6:48 pm
  
  Thank you, I had left out the word “open”. But in any case the usual formulation of the BCT is just that X itself cannot be meager (if it’s a non-empty complete metric space), so I’ve changed the statement to this.
  
Zong-Hong Cheng says:

April 12, 2019 at 8:45 am

Excuse me, I am a student from Taiwan and wish to use the figure in this post to explain the concept of Siegel disk. I want to know if it is okay to put in on my poster. Thank you.

- Matt Baker says:
  
  April 12, 2019 at 1:11 pm
  
  Sure, though I myself got it from somewhere else. (I wish I remembered from where, I should have documented that…)

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Real Numbers and Infinite Games, Part II

5 thoughts on “Real Numbers and Infinite Games, Part II”

Leave a Reply Cancel reply

Share this:

Like this:

Related

5 thoughts on “Real Numbers and Infinite Games, Part II”

Leave a Reply Cancel reply