SETTLED POLYNOMIALS OVER FINITE FIELDSRAFE JONES AND NIGEL BOSTON

Abstract. We study the factorization into irreducibles of iterates of a quadratic polynomial f over a finite field. We call f settled when the factorizationof its nth iterate for large n is dominated by “stable” polynomials, namely
those that are irreducible under post-composition by any iterate of f . We
prove that stable polynomials may be detected by their action on the criticalorbit of f , and that the the critical orbit also gives information about the splitting of non-stable polynomials under post-composition by iterates of f . We
then define a Markov process based on the critical orbit of f and conjecturethat its limiting distribution describes the full factorization of large iterates
of f . This conjecture implies that almost all quadratic f defined over a finite
field are settled. We give several types of evidence for our conjecture.

Let Fq be the finite field with q elements, and consider a polynomial f ∈ Fq [x]of degree d. In this paper we consider the iterates of f , namely the polynomials
f n := f ◦ f ◦ · · · ◦ f .
|
{z
}
n

Our particular interest is in understanding the factorization of these polynomials
into irreducibles. We give some general results on these factorizations, and explore
connections to number theory. While in general f n has many irreducible factors, wecall f settled if, loosely, the number of factors remains small as n grows; see Section 1
for a precise definition. A complete understanding of the factorizations, and indeed
merely of settledness, appears difficult to obtain even in the case d = 2. However,
we develop a conjectural theory in this case and give computational evidence forit. Previous work on the irreducibility of polynomial iterates (also called stability;
see Section 2) has focused principally on the case of polynomials with coefficientsin number fields. See for instance [1], [2], [3], [6], [7], [9], and [10]. Settledness was
mentioned briefly in Sections 3 and 5 of [4]. The current paper is a thorough studyof the phenomenon.
The organization of the paper is as follows. In Section 1 we discuss the connections to number theory, which were our original motivation. In Section 2 we give
results on the factorizations of f n in the case where f has degree 2, in particularconnecting them to the presence of squares in the forward orbit of the critical pointof f . Results from this section play a role in recent work of Ostafe and Shparlinski[11]. In Section 3 we develop a conjectural theory of factorizations of f n , where
irreducible factors behave in accordance with a certain Markov process, implyingthat essentially all quadratic polynomials are settled. Section 4 gives examples andDate: February 2, 2011.
1991 Mathematics Subject Classification. 11C20, 37P25, 11R32.
The first author was partially supported by NSF DMS-0852826.
The second author was partially supported by NSA H98230-09-1-0116.
1

2

JONES AND BOSTON

evidence for this conjecture, whilst Section 5 shows that the Markov process does
not directly yield the Galois groups of the iterates.
1. Motivation and backgroundWe motivate our work with some background on arboreal Galois representations.
Say f is a polynomial with coefficients in a number field K. If α ∈ K is a root of
its nth iterate, f n , then f (α) is a root of f n−1 . It follows that the set of roots of
all iterates of f form a tree where edges are assigned between elements if f maps
one to the other. We denote this tree T . For general f , T is the complete deg(f )ary rooted tree. In this case, since elements of Gal (K/K) commute with f , weobtain a continuous map τ : Gal (K/K) → Aut(T ) that we call an arboreal Galois
representation. See [4] for further discussion. In order to define L-functions as in thecase of linear Galois representations, one requires a conjugacy invariant quantitythat encodes essential information about the images of the Frobenius elements
Frobp .
The image of τ may be alternately described as the inverse limit of the groups
Gal (Kn /K), where Kn is the splitting field over K of f n . We may thus describeτ (Frobp ) by describing its images in Gal (Kn /K) as n grows. Let g ∈ K[x] be
any monic irreducible polynomial, and for a prime p in the ring of integers OK of
K we recall that the residue field OK /p := Fp is a finite field. By reducing thecoefficients of g modulo p, one obtains a polynomial g ∈ Fp [x]. It is well-known thatthe cycle structure of the action of Frobp on the roots of g is given by the degreesof the irreducible factors of the polynomial g ∈ Fp [x]. Hence understanding thefactorization of iterates of f ∈ Fq [x] yields information on τ (Frobp ) in Gal (Kn /K)
for all n.
2. Settledness
Definition 2.1. Let K be a field and f, g ∈ K[x]. We say g is f -stable if g ◦ f n
is irreducible over K for n = 0, 1, 2, . . .. We say f is stable if f is f -stable, i.e., alliterates of f are irreducible. We say f is eventually stable if some iterate of f is the
product of f -stable polynomials. Finally, for fixed n, let g1 , . . . , gr be the f -stable
polynomials dividing f n (repeated according to their multiplicity as factors of f n ),and denote by sn the sum of their degrees. We call f settled if lim sn /deg f n = 1.
n→∞

The stability and settledness of polynomials in general has not been much studied. There are some results in special cases, such as f quadratic ([1], [2], [3], [10],[9]) and f (x) = xm − b [6]. In [9] the first author conjectures that all quadraticf ∈ Z[x] with 0 not periodic are eventually stable (considered as polynomials over
Q). Our main purpose here is to investigate settledness for polynomials over finite
fields. In particular, we give evidence for the following conjecture:
Conjecture 2.2. Let q be an odd prime power and let f ∈ Fq [x] be quadratic with
f 6= x2 . Then f is settled.
In this section we give some results on settledness extending those in [4] and [9].
A consequence of Conjecture 2.2 is that to each quadratic f ∈ Z[x] and odd prime
q we can associate a particular (possibly infinite) partition of unity as follows. If
g1 , . . . gr are the (not necessarily distinct) stable divisors of f n , arranged in nonincreasing order by degree, then write (deg g1 )/2n + · · · + (deg gr )/2n . Taking the

SETTLED POLYNOMIALS

3

limit as n → ∞ yields a partition of unity by settledness. This partition encodes
S
information about the Frobenius conjugacy class at q in the Galois group of Kn
over Q, and may be viewed as an analogue of the trace of Frobenius in the case of
linear Galois representations. See [4] for more details.
Note that if g is f -stable, then in particular g is irreducible. The basis formany of our results on stability and settledness is a simple criterion for f -stability
in characteristic not equal to two, which becomes a characterization of f -stability
in the case that K is a finite field of odd characteristic. To state this criterion,
we need some terminology: the critical orbit of a quadratic f ∈ K[x] is the set{f i (γ) : i = 2, 3, . . .}, where γ is the critical point of f , while the adjusted criticalorbit of f is {−f (γ)} ∪ {f i (γ) : i = 2, 3, . . .}.
Proposition 2.3. Let K have characteristic not equal to two. A quadratic polynomial f ∈ K[x] is stable if its adjusted critical orbit contains no squares. In the casewhere K is a finite field, f is stable if and only if its adjusted critical orbit contains
no squares.
To prove Proposition 2.3 we need two preliminary results. The first is a wellknown lemma:
Lemma 2.4 (Capelli’s Lemma). Let K be a field, f (x), g(x) ∈ K[x], and let β ∈ K
be any root of g(x). Then g(f (x)) is irreducible over K if and only if both g isirreducible over K and f (x) − β is irreducible over K(β).
Our second preliminary result is similar to one appearing in [2], but we give herea slightly different statement and a more direct proof.
Lemma 2.5. Let K be a field of odd characteristic, f (x) = ax2 + bx + c ∈ K[x],and γ = −b/2a be the unique critical point of f . Suppose that g ∈ K[x] is suchthat g ◦ f n−1 has degree d and is irreducible over K for some n ≥ 1. Then g ◦ f n
is irreducible over K if (−a)d g(f n (γ)) is not a square in K. If K is finite then we
may replace “if” with “if and only if.”
Proof. (cf [8, Lemma 4.13]) By Capelli’s Lemma and the irreducibility of g ◦ f n−1 ,we have g◦f n irreducible if for any root β of g◦f n−1 , Disc (f (x)−β) = b2 −4ac+4aβ
is not a square in K(β). Now
 2

Y
b
NK(β)/K (b2 − 4ac + 4aβ) = (−4a)d− +c−β4an−1
β root of g ◦ f=d(−4a) g ◦ f n−1 (−b2 /4a + c) = (−4a)d g ◦ f n−1 (f (γ)).

This proves the Lemma in the case of a general field K. Note that NK(β)/K is amultiplicative homomorphism, thus mapping squares to squares. If K = Fq thensince 1/2 of the elements of Fq (β)∗ are squares, it follows that α ∈ Fq (β) is a square
if and only if NFq (β)/Fq (α) is a square in Fq .

Note that Proposition 2.3 follows by taking g(x) = x in Lemma 2.5. The following is a new result that will help in the analysis of several examples in Section
3
Proposition 2.6. Let f (x) = ax2 + bx + c ∈ K[x] and let γ = −b/2a be the unique
finite critical point of f . Suppose that g ∈ K[x] is such that g ◦ f n−1 is irreducible

4

JONES AND BOSTON

over K for some n ≥ 1. Then either g ◦ f n is irreducible or there exists a monich ∈ K[x] such thatg ◦ f n (x) = kh(x − γ)h(−(x − γ))
for some k ∈ K.
Proof. Suppose that g ◦ f n is reducible, and let deg g ◦ f n = d. Consider theaction of Gn := Gal (K(g ◦ f n )/K) on the roots of g ◦ f n , where K(g ◦ f n ) denotes
the splitting field of g ◦ f n over K. Since g ◦ f n is reducible, this action has atleast two orbits. However, since g ◦ f n−1 is irreducible, each orbit has at leastdeg g ◦ f n−1 = d/2 elements. Thus there are precisely two orbits.
By Capelli’s Lemma, f (x) − β is reducible over K(β) for every root β of g ◦ f n−1 .
Note thatf (x) − β = ax2 − bx + c − β = a((x − γ)2 − (b2 − 4ac − 4aβ)/4a2 ).
Let ±αβ be the square roots of (b2 − 4ac − 4aβ)/4a2 , and choose the signs so that{αβ : β a root of g ◦ f n−1 } is one Galois orbit and {−αβ : β a root of g ◦ f n−1 } isthe other. We then haveYYg ◦ f n = ad((x − γ) − αβ )((x − γ) + αβ ) .
β

β
n−1

Since n ≥ 2,Qthe degree of g ◦ f
is even. Thus
Q the second product may be
rewritten as β (−(x − γ) − αβ ). Taking h(x) = β (x − αβ ) ∈ K[x] completes theproof.

3. A Markov model for factorizations of iterates
In this section we specialize to the case K = Fq , still taking q to be an odd prime
power and f to be quadratic. We develop a conjectural model for the factorizationof f n into irreducibles as n grows.
For f ∈ Fq [x], define cf to be the number of distinct elements of the criticalorbit of f , i.e., one less than the smallest integer k such that f k (γ) = f j (γ) withk > j ≥ 1. It follows from Proposition 2.5 that the factorization of iterates of f isdetermined by the presence of squares in the finite sequence consisting of the firstcf + 1 terms of the adjusted critical orbit, i.e., −f (γ), f 2 (γ), . . . , f cf +1 (γ). Indeed,
if the first element of this sequence that is a square is the ith one, then f i is thefirst reducible iterate of f . More generally, if h ∈ Fq [x] is irreducible, then by
Proposition 2.5 we have that when deg h is odd, then h is f -stable if and only if thesequence −h(f (γ)), h(f 2 (γ)), . . . , h(f cf +1 (γ)) contains no squares. When deg h iseven, as is the case when h = f i for some i ≥ 1, we need only consider the sequenceh(f (γ)), h(f 2 (γ)), . . . , h(f (cf γ)). Moreover, in either case if the first element of theappropriate sequence that is a square is the ith one, then h ◦ f i is reducible andh ◦ f j is irreducible for j < i.
Example 3.1. Let f = x2 +1 and K = Fq . When q = 3, we have f (γ) = 1, f 2 (γ) =2, and f 3 (γ) = 2. Here cf = 2, and the sequence −f (γ), f 2 (γ), f 3 (γ), f 4 (γ) is just
2, 2, 2, 2. This contains no squares, and thus f is stable. When q = 7, the criticalorbit is 1 → 2 → 5 → 5 → · · · . The relevant sequence is 6, 2, 5, 5. Since the second
element is a square, we conclude that f is irreducible but f 2 factors. Note also thath = x2 + x + 4 divides f 3 , and since deg h is even and h(f (γ)), h(f 2 (γ)), h(f 3 (γ)) =6, 3, 6 contains no squares, we conclude that h is f -stable.

SETTLED POLYNOMIALS

5

Let f ∈ Fq [x] be quadratic, and suppose that all iterates of f are separable overFq (equivalently, 0 is not in the forward orbit of the critical point of f ). Consider
the tree V defined as follows. The vertices consist of all irreducible h ∈ Fq [x] suchthat h | f n for some n ≥ 0, where we take f 0 = x. There is an edge connecting h1
and h2 precisely if h2 divides h1 ◦ f . We call the factor(s) of h ◦ f the immediate
descendant(s) of h (there may be one or two). Denote by Vn the vertices of distancen from f0 , so that Vn = {h ∈ Fq [x] : h irreducible and h | f n }. The graph furnishes
a natural map Vn+1 → Vn , and we take L = lim Vn to be the inverse limit of this←directed system. We refer to the elements of L as ends of the tree V . If we assign
the discrete topology to each Vn , then L becomes a profinite topological space.
Moreover, we assign a probability measure to each Vn by taking µn (h) = 2−n deg h.
These measures are compatible with the maps Vn+1 → Vn , and it follows that wehave a measure µ on L that restricts to µn for each n. We thus have a probability
space L, µ, B, where B denotes the Borel σ-algebra on L.
We now wish to label almost all vertices of the aforementioned graph with atype, which is a string of letters taken from the alphabet {n, s}. Let g ∈ Fq [x]be irreducible of even degree. Recall that the critical orbit of f has cf elements.
The type of g is a string of length cf consisting of the letters n and s according towhether each element of the set {h(f (γ)), h(f 2 (γ)), . . . , h(f cf (γ))} is a non-squareor a square. We sometimes wish to multiply types, which we do by identifying nwith −1 and s with 1. Clearly the type of an even-degree irreducible factor h of f n
encodes certain splitting information about the portion of the graph V emanatingfrom h. In the case where deg h is odd, or equivalently deg h = 1, we must assign astring of length cf +1 to encode the same information. For simplicity we leave these
vertices unlabeled. Note that an end of V whose projections in Vn have degree 1 forevery n yields a sequence α1 , α2 , . . . of elements of Fq with f (αn ) = αn−1 for n ≥ 2
and f (α1 ) = 0. Thus αn = αm for some n ≥ m, implying that 0 = f m (αn ) = αn−m .
Therefore 0 is periodic under iteration of f , whence αn = 0 for infinitely many n,i.e., the polynomial x occurs for infinitely many projections (powers of x cannot
occur since all iterates of f are separable). It follows that there can be at mostone such end. Thus for any end belonging to a cofinite subset of L, only a finite
number of the associated vertices are unlabeled.
We denote by πn the natural restrictions L → Vn . Consider random variables
Xn : L → {n, s}cf defined by Xn (l) = φ(πn (l)). Thus Xn simply returns thelabeling of the nth vertex associated to the end l. By the remarks in the second
paragraph of this section, we have that the stochastic process X1 , X2 , . . . completely
determines the factorizations of the iterates of f . Moreover, we have the following
characterization: f is settled if and only if(3.1)

lim µ(Xn = (n · · · n)) = 1.

n→∞

We call the process X1 , X2 , . . . the factorization process of f .
In the factorization process, some types cannot occur as immediate descendantsof certain other types, because of Proposition 2.6. The next proposition gives theprecise constraints.
Proposition 3.2. Suppose that Fq is a finite field of odd characteristic, and f ∈Fq [x] is quadratic with critical orbit of length m and all iterates separable. Let g ∈Fq [x] be irreducible of even degree. Suppose that h1 h2 is a non-trivial factorizationof g ◦ f , and let di (resp. ei ) be the ith digit of the type of h1 (resp. h2 ). Then

6

JONES AND BOSTON

there is some k, 1 ≤ k ≤ m, with dm = ek and em = dk . Moreover, k = m if andonly if γ is periodic.
Remark 3.3. When γ is not periodic, the value of k is the length of the tail ofthe orbit of γ under f . In other words, k is the smallest positive integer withf k (γ) 6= f i (γ) for all i, but f k+1 (γ) = f i (γ) for some i.
Proof. By Proposition 2.6, there is h ∈ Fq [x] with h1 = h(x−γ) and h2 = h(−x+γ).
A straightforward calculation shows that h1 (−x+2γ) = h2 (x) and h1 (x) = h2 (−x+2γ). Hence a relation among elements of the form h1 (f i (γ)) and those of the formh2 (f j (γ)) occurs when
(3.2)

f i (γ) = −f j (γ) + 2γ

for some i, j. If f i (γ) = f j (γ) then 2f i (γ) = 2γ, and γ is periodic, with m being thesmallest positive integer satisfying f m (γ) = γ. Then h1 (γ) = h(0) = h2 (γ) implies
that dm = em . If f i (γ) 6= f j (γ), then writing f (x) = (x − γ)2 + δ and applying it
to both sides of (3.2) shows that f i+1 (γ) = f j+1 (γ). Thus γ is not periodic underf , and k = min{i, j} is the smallest positive integer such that f k (γ) is not periodic.
Note that k ≤ m − 1 in this case.
Consider now a time-homogeneous Markov process Y1 , Y2 , . . . related to f , which
we call the f -Markov process and define as follows. The state space is the type spaceof f , namely {n, s}cf . We define the f -Markov process by giving its transition
matrix M = (P(Yn = tj |Yn−1 = ti )), where ti and tj vary over all types, and thiscompletely determines the process. Note that the columns of M must sum to 1
(we remark that many authors take the transition matrix to be the transpose of
M ). We define M by assuming that all allowable types of immediate descendants
have equal probability. To define allowable types, note that f naturally acts on its
critical orbit, and thus also on the set of types. Indeed, if t is a type, then f (t) is
obtained by shifting each entry one position to the left and using the former nth
entry as the new final entry, where n is such that f cf +1 (γ) = f n (γ). If g ∈ V has
type t and t begins with n, then there is only one immediate descendant of g, andit will have type f (t). This is the only allowable type in this case. If t begins withs, then g has two descendants whose types must multiply to f (t). Among pairsof types t1 , t2 with t1 t2 = f (t), we call allowable those that satisfy the conclusionof Proposition 3.2, namely dk = em and ek = dm with k = m if γ is periodic,
and k the length of the tail of the orbit of γ if γ is not periodic. See Examples
4.1 and 4.2 for examples of f -Markov processes. The following proposition gives acharacterization of allowable types.
Proposition 3.4. Let f ∈ Fq [x] be quadratic with critical point γ, critical orbit oflength m, and all iterates separable. Let k be the length of the tail of the orbit of γ
under f , with k = m if γ is periodic, and let a1 · · · am be a type with a1 = s. Thenthe type d1 · · · dm is an allowable type of immediate descendant of a1 · · · am if andonly if k = m or k < m and dk dm = ak+1 .
Proof. Let g ∈ Fq [x] be irreducible with even degree and type a1 · · · am , where
a1 = s. Then g ◦ f = h1 h2 , and the types d1 · · · dm , e1 · · · em of h1 , h2 must multiply
to f (a1 · · · am ), which is a2 · · · am a1 if k = m and a2 · · · am ak+1 if k < m. In
particular we have dm em = a1 if k = m and dk ek = dm em = ak+1 if k < m.
If k = m, then by Proposition 3.2 we must have dm = em . But this is equivalent
to dm em = s, which is already assured since dm em = a1 = s. Therefore d1 · · · dm is

SETTLED POLYNOMIALS

7

allowable. Suppose that k < m. If d1 · · · dm is allowable, then by Proposition 3.2 wehave ek = dm . From dk ek = ak+1 we thus have dk dm = ak+1 . If dk dm = ak+1 , thenwe have dk ek = dk dm and dk dm = dm em , implying that d1 · · · dm is allowable. 
From the definition of allowable types, we see that the type n · · · n is fixed under
the action of f and has only one descendant and hence is an absorbing state of
the f -Markov process (that is, P(Yn = n · · · n | Yn−1 = n · · · n) = 1). We wish toshow that the f -Markov process is in fact an irreducible absorbing Markov process,namely that every non-absorbing state transitions to every other state with nonzero probability after a finite number of steps.
Corollary 3.5. Let f ∈ Fq [x] be quadratic with all iterates separable. Then thef -Markov process is an irreducible absorbing Markov process.
Proof. Let γ be the critical point of f , and m the length of the critical orbit.
Suppose that a1 · · · am is a type with a1 = s. We show that every type is anallowable descendant of an allowable descendant of a1 · · · am . This is enough toestablish the corollary since each non-absorbing type with first entry n transitions
to a type with first entry s with probability one after a finite number of steps.
Let k be the length of the tail of the critical orbit of f , with k = m if the criticalpoint is periodic. If k = m, the corollary follows immediately from Proposition 3.4.
If k < m, then a1 · · · am has at least one descendant d1 · · · dm with dk+1 = n andat least one with dk+1 = s. The corollary now follows from Proposition 3.4.
Absorbing Markov processes are well-studied, and we recall some of their properties; see [12, page 236] for details. Most saliently, any initial state lands on anabsorbing state after finitely steps with probability 1. Hence for the f -Markov
process Y1 , Y2 , . . .,(3.3)

lim P(Yi = n · · · n) = 1.

i→∞

In the case where the process is irreducible, the probability of being in a nonabsorbing state decreases by a factor of λ each time, where λ is the largest eigenvalueof M less than 1. Moreover, if we denote by M ∗ the sub-matrix of M obtained bydeleting the rows and columns corresponding to absorbing states, then M ∗ has λas an eigenvalue of multiplicity one and the entries of any non-trivial corresponding
right eigenvector give the asymptotic relative frequencies of each non-absorbing
state, known as the quasi-stationary distribution. See examples 4.1 and 4.2.
We will give evidence that, when n is large, the factorization process of f behavesquite similarly to the f -Markov process. One such similarity is that for quadraticf ∈ Fq [x] with all iterates separable, the only absorbing state of the factorization
process is n · · · n (see the second paragraph of this section). We make the following
far more expansive conjecture. The first part immediately implies Conjecture 2.2
in the case where all iterates of f are separable, by equations (3.1) and (3.3).
Conjecture 3.6. Let f ∈ Fq [x] be quadratic with all iterates separable.
(1) The distribution of the factorization process of f converges to that of the
f -Markov process, namely the distribution having all its mass on n · · · n.
(2) Suppose f is not eventually stable, i.e., no iterate of f factors as a productof f -stable polynomials. Let X1 , X2 , . . . be the factorization process for fand λ be the largest eigenvalue less than 1 of the transition matrix M of

8

JONES AND BOSTON

the f -Markov process. Then we havePt P(Xn = t)
P
lim
= λ,
n→∞
t P(Xn−1 = t)where the sums are taken over all states except n · · · n.
(3) Under the hypotheses of part (2), the relative frequencies of all non-n · · · nstates in the factorization process for f converge to those of the f -Markov
process.
4. Examples and evidence
We first treat the few cases where the factorization process can be completely
described, and then give computational evidence for Conjecture 3.6 in more complicated cases (Examples 4.1 and 4.2). The simplest possible case is when the criticalorbit of f ∈ Fq [x] consists of a single point, i.e., the critical point is a fixed point.
This occurs precisely when f is conjugate to x2 , i.e. f = (x + u)2 − u for someu ∈ Fq . In this case one can choose a lift of f to a polynomial f˜ ∈ OL [x], where L issome number field. In this case the Galois groups of iterates of f˜ can be explicitly
computed (they are subgroups of the affine group AGL1 (Z2 ), which is isomorphic
to Z2 o Z∗2 ). One can thus write down the cycle types of all Frobenius conjugacy
classes, and hence in particular the factorizations of f n ∈ Fq [x] (see [4, Section 4]
for a discussion of the case where q is prime and ũ ∈ Z is chosen to be prime).
The next simplest case is when the critical orbit contains two points. Every
quadratic polynomial in odd characteristic is conjugate to one of the form fc (x) =x2 + c, and solving for c with fc3 (0) = fc (0) and fc3 (0) = fc2 (0) shows that a twoelement critical orbit occurs only when f is conjugate to x2 − 2 or x2 − 1. Inthese cases, we have critical orbits that are translates of −2 → 2 → 2 → · · · and−1 → 0 → −1 → · · · , respectively. In the former case, the Galois groups of lifts
are also subgroups of AGL1 (Z2 ), and the analysis is similar to that of the previous
paragraph.
Hence the simplest case where the factorization of iterates cannot be determined
explicitly via a finite amount of data occurs when f is of the form (x + u)2 − u − 1.
In order to have f irreducible over Z, we take u = 1. We note that the Galois
groups over Q of the iterates of f have been studied in [4, Section 4]. Their inverse
limit is conjecturally large enough to have nonzero Hausdorff dimension in Aut(T )and is related to the well-known Basilica group. The splitting fields over Q of
the iterates of f are 2-extensions unramified outside 2 and ∞. Understanding theimages of Frobenius in this arboreal Galois representation, and thus understanding
the factorization process of f ∈ Fp [x] for various primes p, is the next step inanalyzing this situation.
Example 4.1. Let f = (x + 1)2 − 2 ∈ Fq [x], where q is a prime power. In thiscase f has finite critical orbit even over Z, so the critical orbit is the same for all q,
namely −2 → −1 → −2 → · · · . We have f (nn) = nn, f (ns) = sn, f (sn) = ns, andf (ss) = ss. Because the critical point −1 is periodic, by Proposition 3.4 all typesof immediate descendants are allowable from the states sn and ss, giving:nn 7→ nn,

ns 7→ sn,

sn 7→ sn/nn or ss/ns,
ss 7→ nn/nn or ns/ns or sn/sn or ss/ss

SETTLED POLYNOMIALS

9Ordering lexicographically (here nn, ns, sn, ss), the two matrices
1 0 0.25 0.25
0 0.25 0.25
0 0 0.25 0.25M1∗ = 1 0.25 0.25
M1 = 
0 1 0.25 0.25
0 0.25 0.25
0 0 0.25 0.25
are, respectively, the transition matrix of the f -Markov process and its submatrix
corresponding to the non-absorbing states. √The matrix M1 has eigenvalues approximately −0.3090, 0, 0.8090, 1, where λ =√( 5 + 1)/4 ≈ 0.8090 is half the golden
ratio. A right λ-eigenvector of M1∗ is (1, 5, 1). Hence the masses in states ns andss are ultimately about√the same, say αk for the value at time k. The mass in state
sn at time k is about 5αk , and αk+1 ≈ 0.8090αk .
According to Conjecture 3.6, this behavior should be reflected in the factorization
process for f . In this case, the critical orbit of f is the same for all q, and in Table
1 we give the masses for all states in the factorization process at large iterates forseveral prime values of q.
prime
3
3
3
3
3
5
5
5
5
5
7
7
7
7
7
11
11
11
11
11

iterate
24
25
26
27
28
24
25
26
27
28
24
25
26
27
28
24
25
26
27
28

nn
0.99100.99280.99420.99530.9962
0.99410.99520.9961
0.99690.99750.98840.9906
0.99230.99370.99490.98390.98730.98980.99150.9931sn
0.00460.00370.00320.00260.00190.00340.00260.00200.00170.00130.00620.00490.00410.00330.00270.00810.00690.00550.00410.0039ns
0.00190.00180.00130.00100.00100.00130.00110.00090.00070.00060.00280.00230.00180.00150.00120.00370.00290.00240.00210.0015ss
0.00240.00170.00130.00110.00100.00130.00110.00100.00070.00060.00270.00220.00190.00150.00120.00430.00290.00240.00220.0015

Table 1. Masses in each state of the factorization process forf (x) = (x + 1)2 − 2 ∈ Fq [x] for various primes q.
Example 4.2. We turn to an example with critical orbit of length 3. As in Example 3.1, let f = x2 + 1 and K = F7 . The behavior of types beginning withn is determined by noting that f (nnn) = nnn, f (nns) = nss, f (nsn) = snn, andf (nss) = sss. In the notation of Proposition 3.4, we have k = 2, and so the allowable descendants of snn are the types d1 d2 d3 with d2 d3 = n, i.e. nns, nsn, sns, andssn. Performing similar analyses for sns, ssn, sss and using lexicographic ordering

10

JONES AND BOSTON

of types gives the transition matrix

1 0 0 00
0 0 0 0 0.25

0 0 0 0 0.25

0 1 0 00
M2 = 
0 0 1 00
0 0 0 0 0.25

0 0 0 0 0.25
0 0 0 1
0

0.25
0
0
0.25
0.25
0
0
0.25

0
0.25
0.25
0
0
0.25
0.25
0


0.25
0 

0 

0.25
.
0.25

0 

0 
0.25

We remark that there are only three distinct f -Markov processes for f with criticalorbit of length 3, one corresponding to each possible length of the periodic part ofthe critical orbit. The matrix M2 has largest eigenvalue (other than 1) equal toapproximately 0.9010, one quarter of the largest root t ≈ 3.6039 of x3 − 2x2 − 8x +8 = 0. Looking at a suitably normalized corresponding right eigenvector of M2∗ ,we see that nns, nsn, sns, ssn should each account for about the same proportionof the factorization of f k , say αk , that nss, snn should each account for about
Iterate
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

nnn
0.00000.25000.25000.37500.37500.56250.57810.66410.69530.74800.83200.85640.87870.89870.9161
0.92240.92880.93690.94370.95100.9581
0.96290.96770.97210.97600.9790nns
0.00000.00000.12500.06250.06250.03120.0781
0.04690.03910.00980.01070.01370.00460.00680.00590.00690.00510.00410.00450.00470.00330.00250.00260.00180.00180.0016nsn
0.50000.00000.25000.06250.12500.00000.04690.03910.01170.02150.01370.00590.00610.00330.00770.00150.00620.00590.00350.00400.00310.00290.00220.00200.00170.0015nss
0.00000.00000.00000.12500.06250.06250.03120.10940.04690.04100.01370.02150.03960.01290.01880.01790.01050.01310.00790.00770.00850.00580.00530.00530.00400.0036snn
0.00000.75000.00000.37500.06250.18750.01560.10160.03910.01760.03520.01860.01640.01100.01460.01590.01200.01320.01280.00800.00760.00670.00560.00490.00440.0039sns
0.50000.00000.25000.00000.12500.03120.04690.00000.0156
0.03120.00780.00630.01170.00650.00460.00180.00640.00450.00350.00400.00300.00290.00210.00230.00170.0015ssn
0.00000.00000.12500.00000.06250.06250.07810.00780.04300.01950.00490.01420.01030.01000.00280.00720.00540.00280.00440.00470.00330.00260.00250.00210.00170.0015sss
0.00000.00000.00000.00000.12500.06250.12500.03120.10940.11130.08200.06350.03270.05080.0296
0.02640.02560.01950.01960.01600.01310.01370.01210.00970.00860.0074

Table 2. Masses in each state of the factorization process forf (x) = x2 + 1 ∈ F7 [x].

SETTLED POLYNOMIALS

11(t − 1)αk ≈ 2.6039αk , and sss for about (t2 − t − 5)αk ≈ 4.3840αk . Moreover,
αk+1 = (t/4)αk ≈ 0.9010αk . Table 2 contains data for the first 27 iterates of f .
We now return to Example 4.1 and examine some related issues. First, since
the critical orbit of f = (x + 1)2 − 2 ∈ Fq [x] is the same for all q, one can use
Chebotarev’s Density Theorem to study how varying q over prime values changes
the factorization behavior of a given iterate. Note that this is different from thequestion of being settled, which involves fixing the prime and varying the depth.
For example, suppose that q is a prime that is 5 (mod 8), so that f has type sn andso f 2 splits into two factors h1 h2 . Then h1 (−1) = h2 (−1) and both are nonsquares
since h1 (−1)h2 (−1) = f 2 (−1) = −1 and −1 has no 4th root (mod q). Thus sn
always decays to sn/nn at this level. The nn factor is f -stable but what about
the decay of the new sn factor? It turns out that it leads to ss/ns if and only if
g = x16 − 4x12 + 4x8 + 8x4 + 4 has a linear factor (mod q). Looking at the Galois
group of g of order 128, we see that exactly half of the primes that are 5 (mod 8)
have ss/ns at the next level.
Second, we wish to give additional evidence that the factorization process off = (x + 1)2 − 2 mimics a Markov process, beyond the content of Conjecture
3.6. Here we examine at the kth iterate how many irreducible factors of type sn
decay to sn/nn and how many to ss/ns. The Markov model suggests that either
possibility should be equally likely. Likewise, we can perform the same calculation
with irreducible factors of type ss. Table 3 contains the corresponding data. Note

prime
3
3
3
3
3
5
5
5
5
5
7
7
7
7
7
11
11
11
11
11

iterate
23
24
25
26
27
23
24
25
26
27
23
24
25
26
27
23
24
25
26
27

sn
sn/nn ss/ns
168
163
221
227
291
321
433
379
657
569
117
122
168
151
235
233
293
293
414
394
182
239
255
234
371
393
527
500
716
710
158
169
209
207
311
281
413
395
506
574

nn/nn
80
132
208
234
306
46
96
108
160
268
90
188
212
270
384
92
136
188
226
310

ss
sn/sn ns/ns
86
92
136
110
184
200
272
222
306
358
78
72
106
80
120
110
172
154
276
218
94
88
182
208
214
216
290
260
462
410
78
78
136
108
182
174
212
228
320
292

ss/ss
106
160
182
278
344
60
82
128
208
240
142
184
194
354
452
96
150
170
236
340

Table 3. Decay data for the factorization process of f (x) = (x +1)2 − 2 ∈ Fq [x] for various primes q.

12

JONES AND BOSTON

that the numbers in each row of the sn/nn and ss/ns columns are approximately
equal, in accordance with the Markov process. The same is true of the numbers ineach row of the last four columns.
As a final check that the factorization process behaves like a Markov process forlarge iterates, we check that there is no bias over two steps. An irreducible factorof type sn can arise from a previous sn, ns, or ss. For each of these we see how
many sn decay to sn/nn and how many to ss/ns. The data can be found in Table
4. Note that the numbers in the sn/nn and ss/ns columns from Table 3 are broken

prime
3
3
3
3
3
3
3
3
5
5
5
5
5
5
7
7
7
7
7
7
11
11
11
11
11

iterate
23
24
25
26
27
28
29
30
23
24
25
26
27
28
23
24
25
26
27
28
23
24
25
26
27

sn from sn
sn/nn ss/ns
63
48
85
83
120
101
156
135
224
209
331
326
356
423
542
510
47
54
60
57
90
78
122
113
140
153
207
207
73
89
98
84
130
125
196
175
264
263
374
342
47
73
84
74
108
101
164
147
192
221

sn from ns
sn/nn ss/ns
65
75
97
97
115
140
174
163
295
226
282
319
455
472
577
668
47
43
62
62
96
98
111
120
172
171
234
213
75
108
108
105
150
177
215
227
304
305
360
400
72
59
90
90
134
113
164
151
207
248

sn from ss
sn/nn ss/ns
40
40
39
47
56
80
103
81
138
134
166
140
241
201
334
300
23
25
46
32
49
57
60
60
102
70
137
139
34
42
49
45
91
91
116
98
148
142
234
228
39
37
35
43
69
67
85
97
107
105

Table 4. Two-step decay data for the factorization process off (x) = (x + 1)2 − 2 ∈ Fq [x] for various primes q.
up according to where the sn entry producing them came from. Once again, in eachrow of each pair of columns the numbers are approximately equal, in accordancewith the Markov process, which would say that what happens at one level should
be independent of the past.
5. The Markov process and Galois groups
Recall that any polynomial conjugate to x2 − 1 yields the same transition matrix
M1 for any prime p. We might then expect that the Markov process determines

SETTLED POLYNOMIALS

13

the density of cycle structures in the Galois groups of iterates and hence the Galois
groups themselves. This turns out to be often but not always true.
Definition 5.1. A level n type sequence is a partition of 2n into powers of 2 together
with a map from each term of the partition to the set of types. If two terms areequal, we do not order them. A level n datum is a level n type sequence together
with a rational number between 0 and 1 (called its probability of occurring). The
level n data is a collection of these for which the sum of the probabilities is 1.
For example, if n = 5 and we consider the partition 25 = 16 + 8 + 4 + 4, thenthe map sending 16 to nn, 8 to sn, and each 4 to ss defines a level 5 type sequencewhich we will write [nn, 16][sn, 8][ss, 4]2 . Associating the rational number 1/128 toit yields a level 5 datum.
Now suppose f (x) = (x + t)2 − (t + 1) and p is a prime. The factorization of f n
modulo p yields a level n type sequence s where the partition is given by the degrees
and the types by the types of the corresponding irreducible factors. Attaching to s
the density of primes p yielding the type sequence s then produces a level n datum.
The advantage of the approach using level n data is that one can both read off
the possible cycle structures with their densities (often allowing determination of
the Galois group) and also apply the Markov process to obtain level n + 1 data.
The goal then is to start with level 1 data and iteratively obtain level n data forevery n and hence the Galois groups. We will assume that f is generic, meaningthat t is not of the form m2 , m2 − 1, 2m2 , or 2m2 − 1. This will ensure that the
Galois groups of its iterates are as large as possible.
The first twist is that the Markov process must be modified depending on whether
p is 1 (mod 4) or 3 (mod 4) because, as noted in Lemma 2.5, linear factors behave
differently under iteration, depending on whether −1 is a square modulo p. For
example, if p is 1 (mod 4), then an [nn, 1] factor will always yield an [nn, 2] factor,
whereas if p is 3 (mod 4), then it will yield [nn, 1][ss, 1] or [ns, 1][sn, 1] equiprobably.
In the first case, the probability of the type sequence will stay the same (unless it hasother factors behaving nondeterministically when it will change accordingly); in thesecond case, the probability of each possibility will be half the original probability(again modified by the behavior of other factors). A datum associated to 1 (mod 4)(respectively 3 (mod 4)) primes will be called even (respectively odd).
The even level one data are then:([[nn, 1], [nn, 1]], 1/32), ([[nn, 1], [sn, 1]], 1/16), ([[nn, 2]], 1/8), ([[ns, 1], [ns, 1]], 1/32),([[ns, 1], [ss, 1]], 1/16), ([[sn, 1], [sn, 1]], 1/32), ([[sn, 2]], 1/8), ([[ss, 1], [ss, 1]], 1/32)
The odd level one data are:([[nn, 1], [ns, 1]], 1/16), ([[nn, 1], [ss, 1]], 1/16), ([[ns, 1], [sn, 1]], 1/16),([[ns, 2]], 1/8), ([[sn, 1], [ss, 1]], 1/16), ([[ss, 2]], 1/8)
Note that the sum of the probabilities associated with the partition 21 = 1 + 1
is 1/2 and likewise for the partition 21 = 2. This illustrates the (trivial) fact thatthe only permutation group of degree 2 with cycle structures with those densities
is the cyclic group of order 2.
Applying the Markov processes to the 8 even and 6 odd data yields 22 even and
14 odd level 2 data. The only permutation group of degree 4 with cycle structureswith densities matching this data is the dihedral group of order 8 and this is indeed
the Galois group of f 2 .

14

JONES AND BOSTON

The Markov processes applied to the level 2 data yields 120 even and 56 odd
level 3 data. The only permutation group of degree 8 with cycle structures withdensities matching this data is the Sylow 2-subgroup of Sym(8) of order 128 andthis is indeed the Galois group of f 3 . The Markov processes applied to the level3 data yields 1793 even and 577 odd level 4 data. The only permutation group ofdegree 16 with cycle structures with densities matching this data is a certain groupof order 213 and this is indeed the Galois group of f 4 .
This works well at level 5 too, yielding cycle structure densities that match the
known Galois group of f 5 of order 225 . Apparently this is the only such permutation group of degree 32, but checking all 2-subgroups of Sym(32) of that order isprohibitive (see [5] for a database of the approximately 2.8 million transitive groupsof degree 32).
When we apply the Markov processes to obtain level 6 data, however, a second
twist emerges. There are too many data for us to obtain all of them but theanalysis of data corresponding to the cycle structure of the identity element is
simple enough. In particular it corresponds to a group of order 249 . The Galois
group of f 6 , however, has order 247 . In fact, it contains the 6th quotient of theBasilica√group√with quotient the Klein 4-group. This has fixed field the biquadratic
field Q( −1, 2).
The emerging picture appears to be as follows. Let Bn denote the nth quotientof the Basilica group (n ≥ 6). Let Nn denote its normalizer in the Sylow 2subgroup of Sym(2n ). If we can prove, as computation suggests, that Nn /Bn iselementary abelian of order 2n−2 , then it follows that the Galois group Gn of f n over
Q contains
Bn with index 4 and that the quotient is a Klein 4-group corresponding√√to Q( −1, 2).
n−2
On the other hand, the level n data for n ≥ 6 predicts a group of order 23(2 )+1 ,which is (for n > 6) even bigger than Nn . The cycle structure densities still appear
to match well for the level n data corresponding to partitions involving 2n−1 , but
not for the partition 2n = 1 + ... + 1 as indicated above.
References
1. Nidal Ali, Stabilité des polynômes, Acta Arith. 119 (2005), no. 1, 53–63. MR MR2163517(2006h:11125)
2. Mohamed Ayad and Donald L. McQuillan, Irreducibility of the iterates of a quadratic polynomial over a field, Acta Arith. 93 (2000), no. 1, 87–97. MR MR1760091 (2001c:11031)
3.
, Corrections to: “Irreducibility of the iterates of a quadratic polynomial over a field”[Acta Arith. 93 (2000), no. 1, 87–97], Acta Arith. 99 (2001), no. 1, 97. MR MR1845367(2002d:11125)
4. Nigel Boston and Rafe Jones, Arboreal galois representations, Geom. Dedicata 124 (2007),
no. 1, 27–35 (electronic).
5. John J. Cannon and Derek F. Holt, The transitive permutation groups of degree 32, Experiment. Math. 17 (2008), no. 3, 307–314. MR MR2455702 (2009j:20003)
6. Lynda Danielson and Burton Fein, On the irreducibility of the iterates of xn − b, Proc. Amer.
Math. Soc. 130 (2002), no. 6, 1589–1596 (electronic). MR 1887002 (2002m:12001)
7. Burton Fein and Murray Schacher, Properties of iterates and composites of polynomials, J.
London Math. Soc. (2) 54 (1996), no. 3, 489–497. MR MR1413893 (97h:12007)
8. Rafe Jones, Iterated Galois towers, their associated martingales, and the p-adic Mandelbrot
set, Compos. Math. 143 (2007), no. 5, 1108–1126. MR MR2360312 (2008i:11131)
9.
, The density of prime divisors in the arithmetic dynamics of quadratic polynomials,
J. Lond. Math. Soc. (2) 78 (2008), no. 2, 523–544. MR MR2439638
10.
, An iterative construction of irreducible polynomials reducible modulo every prime,
ArXiv e-prints (2010).

SETTLED POLYNOMIALS

15

11. Alina Ostafe and Igor E. Shparlinski, On the length of critical orbits of stable quadratic
polynomials, Proc. Amer. Math. Soc. 138 (2010), no. 8, 2653–2656. MR 2644881
12. E. Seneta, Non-negative matrices and Markov chains, Springer Series in Statistics, Springer,
New York, 2006, Revised reprint of the second (1981) edition [Springer-Verlag, New York;
MR0719544]. MR 2209438
Department of Mathematics and CS, College of the Holy Cross, Worcester, MA
E-mail address: rjones@holycross.edu
Department of Mathematics, University of Wisconsin Madison, WI
E-mail address: boston@math.wisc.edu