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. In 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 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

# Tag Archives: Arithmetic dynamics

# 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=m^{2} 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 z^{2} + c with c a rational number which are PCF are z^{2}, z^{2}-1, and z^{2}-2, and every quadratic polynomial is conjugate to a polynomial of this form. Continue reading