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