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. Continue reading

Lucas sequences and Chebyshev polynomials

This is a sequel to last week’s blog post “Two applications of finite fields to computational number theory“.  The main reason I decided to write a follow-up is that I’ve learned a lot about Concluding Observations #1 and #6 from that post during the last week.   LucasBookIn Observation #1, I mentioned without further comment a recursive procedure for computing square roots modulo a prime; it turns out that this procedure is essentially equivalent to Cipolla’s algorithm, but was discovered independently by Lehmer (who it seems did not know about Cipolla’s work).  I learned this from the wonderful book “Édouard Lucas and Primality Testing” by Hugh C. Williams, which I highly recommend to anyone interested in the history of mathematics.  In explaining the connection between the algorithms of Cipolla and Lehmer, I’ll make a digression into the general theory of Lucas sequences, which I had some vague knowledge of before but which I’ve learned a lot about in the last week from reading Williams’ book.  In Observation #6, I asked if there was a conceptual explanation for the fact that the Chebyshev polynomial x^2 - 2 shows up in the Lucas-Lehmer test; Greg Kuperberg sent me just such an explanation and I will expand on his comments below. Continue reading

Attracting cycles and post-critically finite maps

A theme which I hope to pursue in multiple posts on this blog is that even if one is interested mainly in complex dynamics, it is often useful to employ p-adic (or more generally non-Archimedean) methods.  There are a number of relatively recent research papers which illustrate and support this thesis.  The one I want to talk about today is this beautiful paper of Benedetto, Ingram, Jones, and Levy, henceforth referred to as [BIJL].

From a complex dynamicist’s point of view, the main result of [BIJL] is the following theorem:

Theorem 1: For any fixed integers d ≥ 2 and B ≥ 1, there are only finitely many conjugacy classes of post-critically finite rational maps of degree d which can be defined over a number field of degree at most B, except (when d is a perfect square) for the infinite family of flexible Lattès maps.

To explain the terms used in the statement, suppose f is a rational map of degree d with complex coefficients.  We say that f is post-critically finite (henceforth denoted PCF) if the orbit of the critical points of f under iteration is finite.  PCF maps play a fundamental role in complex dynamics, roughly speaking because many dynamical features of f can be read off from the behavior of the critical points under iteration.  One source of examples are the flexible Lattès maps, which can be defined whenever d=m2 is a perfect square: these consist of all degree m rational maps obtained as the map on x-coordinates induced by multiplication-by-m on some elliptic curve.  (McMullen calls such maps affine in the paper cited below.)

As an illustration of the theorem, the only quadratic polynomials of the form z2 + c with c a rational number which are PCF are z2, z2-1, and z2-2, and every quadratic polynomial is conjugate to a polynomial of this form. Continue reading