THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM
OVER FINITE FIELDS

arXiv:1610.07077v2 [math.NT] 15 Mar 2018

ALOIS CERBU, ELIJAH GUNTHER, MICHAEL MAGEE, LUKE PEILEN
Abstract. We begin an investigation of the action of pseudo-Anosov elements
of Out(F2 ) on the Markoff-type varieties
Xκ : x2 + y 2 + z 2 = xyz + 2 + κ
over finite fields Fp with p prime. We first make a precise conjecture about
the permutation group generated by Out(F2 ) on X−2 (Fp ) that shows there is
no obstruction at the level of the permutation group to a pseudo-Anosov acting ‘generically’. We prove that this conjecture is sharp. We show that for
a fixed pseudo-Anosov g ∈ Out(F2 ), there is always an orbit of g of length
≥ C log p + O(1) on Xκ (Fp ) where C > 0 is given in terms of the eigenvalues of
g viewed as an element of GL2 (Z). This improves on a result of Silverman from
[24] that applies to general morphisms of quasi-projective varieties. We have
discovered that the asymptotic (p → ∞) behavior of the longest orbit of a fixed
pseudo-Anosov g acting on X−2 (Fp ) is dictated by a dichotomy that we describe
both in combinatorial terms and in algebraic terms related to Gauss’s ambiguous
binary quadratic forms, following Sarnak [21]. This dichotomy is illustrated with
numerics, based on which we formulate a precise conjecture in Conjecture 1.10.

1. Introduction
For κ ∈ Z, let Xκ denote the affine surface
(1.1)

Xκ : x2 + y 2 + z 2 = xyz + 2 + κ.

When κ = −2, X−2 is Markoff’s surface. A theorem of Markoff [16] relates the
integer points on X−2 to the Diophantine properties of Q; in particular to the
Markoff spectrum. In a different vein, the real and complex points of Xκ are related
to moduli spaces of SL2 (C)-local systems on a torus with one puncture [11]. Due
to this connection, letting F2 denote the free group on 2 generators, the group
Out(F2 ) ∼
= GL2 (Z) acts by automorphisms of Xκ , viewed as a scheme of finite
type over Z. The group Out(F2 ) is the mapping class group of the torus with one
puncture, and the free group F2 is the fundamental group of this surface. As such,
Out(F2 ) is subject to Thurston’s classification of mapping class group elements
[25] into periodic, reducible, or pseudo-Anosov (p-A.) elements. From the point of
view of GL2 (Z), an element is p-A. if it is hyperbolic, that is, has two distinct real
eigenvalues. The current paper aims to investigate how p-A. elements of Out(F2 )
act on Xκ (Fp ) for prime p.
M. Magee was supported in part by N.S.F. award DMS-1701357. All authors were supported
in part by Sam Payne’s N.S.F. CAREER award DMS–1149054.
1

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

2

The study of p-A. elements of Out(F2 ) acting on Xκ (R) and Xκ (C) has been ongoing since the early 1980s, instigated by a paper of Kohmoto, Kadanoff and Tang
[14] where the spectrum of a 1D lattice Schrödinger operator with a quasiperiodic
potential was related to the dynamics of a particular p-A. automorphism (the Fibonacci substitution) on Xκ (R). In [4], Cantat resolved a conjecture of Kadanoff
relating the topological entropy of a p-A. element acting on Xκ (R) to the largest
eigenvalue of the corresponding matrix in GL2 (Z). See also Bowditch [3] for some
related questions.
Here, we begin a parallel study for the action of p-A. elements on Xκ (Fp ). Any pA. element Φ of Out(F2 ) gives for each prime p a permutation Φp of Xκ (Fp ). In this
paper we propose that in the study of p-A. Φ acting on Xκ (Fp ), one should replace
topological entropy by the asymptotic complexity of the family of permutations
{Φp }. In particular, we ask the following question.
Problem 1.1. For fixed p-A. Φ, what is the asymptotic behavior of
log( longest cycle of Φp on Xκ (Fp ) )
log p
as p → ∞?
Empirically, the answer to this question is quite surprising (see Conjecture 1.10
below). We also obtain a theoretical result towards this question in Theorem 1.5
below. We will be primarily interested in the case of κ = −2, although we prove
some of our results for general κ.
Before tacking Problem 1.1, a preliminary question intervenes. It could a priori
be the case that the permutation group generated by Out(F2 ) on Xκ (Fp ) is highly
restricted and this would of course affect how a single element can behave.
Let X∗−2 (Fp ) = X−2 (Fp ) − (0, 0, 0). Bourgain, Gamburd, and Sarnak prove in [2,
Theorem 2] that for all primes outside a very small exceptional set, the action of
Out(F2 ) on X∗−2 (Fp ) is transitive, which was a conjecture of McCullough and Wanderley from [17]. Sarnak has raised more generally the question of what permutation
group is generated by the action of Out(F2 ) on X∗−2 (Fp ).
It follows from work of Horowitz [13] (see also Goldman [11]) that
Aut(Xκ ) ∼
= PGL2 (Z) n N
where the PGL2 (Z) factor is induced by Out(F2 ) and N is the Klein four-group
generated by even sign changes
n1 : (x, y, z) 7−→ (x, −y, −z)
(similarly n2 , n3 ). For p odd, each N -orbit on X∗−2 (Fp ) contains four distinct points
(see Lemma 2.1 below). Thus Out(F2 ) cannot act 2-transitively on X∗−2 (Fp ) for any
prime, since it must permute orbits of N . In light of this observation, we should
examine instead the action of Out(F2 ) on the set of N -orbits in X∗−2 (Fp ), which we
denote by Y−2 (Fp ).
Let H(p) denote the permutation group generated by Out(F2 ) acting on Y−2 (Fp ).
We write An for the alternating group on n letters and Sn for the symmetric group.
We prove the following.

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

3

Theorem 1.2. Let n = |Y−2 (Fp )| and let p > 3. Then, H(p) ≤ An if and only if
p ≡ 3 (mod 16).
The above theorem, alongside computations of H(p) for p ≤ 47, lead us to conjecture the following:
Conjecture 1.3. Let H(p) denote the permutation group induced by the action of
Out(F2 ) on Y−2 (Fp ), and let n = |Y−2 (Fp )|. Then when p > 3
• H(p) ∼
= Sn if p 6≡ 3 (mod 16),
∼
• H(p) = An if p ≡ 3 (mod 16).
Meiri and Puder have proved in [18] that H(p) contains An whenever p ≡ 1 (mod 4)
and p is outside the Bourgain-Gamburd-Sarnak exceptional set, and also for a density 1 set of primes without any congruence condition. In these cases, Theorem 1.2
describes exactly what H(p) is. This shows there is no obstruction at the level of
the group H(p) to a p-A. element behaving ‘generically’ on Y−2 (Fp ).
We now describe our theoretical result towards Problem 1.1. In [24] Silverman
studied a more general version of this problem and obtained as a consequence the
following result.
Theorem 1.4 (Silverman [24, Theorem 3(a)]). Let K be a number field with ring
of integers OK and V a quasi-projective variety defined over K. Let ϕ : V → V
be a morphism defined over K. If p ∈ Spec(OK ) is such that V and ϕ have good
reduction at p, then write ϕp and V (Fp ) for these reductions and N (p) for the norm
of this prime. For any  > 0, the set of p ∈ Spec(OK ) such that there is good
reduction of ϕ and V at p, and an orbit of ϕp on V (Fp ) of length ≥ (log N (p))1−
has analytic density 1.
This result applies directly to Problem 1.1. Silverman’s result actually provides
many orbits of length ≥ (log N (p))1− .
What we can achieve in the current context is the removal of the  from Theorem 1.4, and get a statement for all primes p instead of just analytic density 1.
Furthermore, our bounds are independent of κ.
Theorem 1.5. Given a pseudo-Anosov g ∈ Out(F2 ), let λ denote the eigenvalue of
largest modulus of the corresponding matrix in GL2 (Z). For any κ ∈ Z, as p → ∞,
g has an orbit of length at least
log p
+ Og (1)
log |λ|
on Xκ (Fp ). The implied constant depends on g, but not on κ.
Now we describe our numerical results which show what the answer to Problem
1.1 should be, at least for Y−2 (Fp ). First we give two natural guesses, that turn out
to both be wrong.
Guess 1: a p-A. g acts as a random map on Y−2 (Fp ). A random map from
√
a set of size N to itself has with high probability its longest orbit of size  N .
Since |Y−2 (Fp )|  p2 this predicts the longest orbit of g acting on Y−2 (Fp ) will have
size  p. This fact comes from a collision heuristic based on the ‘Birthday paradox’.

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

4

107

longest orbit of g on Y−2 (Fp )

106

U 2V U V
U 2V 2U V

105

104

103

102
102

102.2

102.4

102.6

102.8
103
p, prime

103.2

103.4

103.6

Figure 1.1. This shows the longest orbits of two p-A. elements
U 2 V U V (blue) and U 2 V 2 U V (green) on Y−2 (Fp ). The black line is
y = p2 /4, which is asymptotic to |Y−2 (Fp )|. The red line is y = 10p.
The plots are in log vs log scale axes with p on the horizontal axis
and longest orbit on the vertical.

However, this heuristic is not convincing, since g is invertible, so should really be
viewed as a random permutation (for some notion of random, see next guess). Also,
this guess doesn’t give the right answer in general (see below).
Guess 2: a p-A. g acts as a random permutation on Y−2 (Fp ). Perhaps
we should model the action of g on Y−2 (Fp ) by a permutation chosen uniformly
at random from An or Sn , where n = |Y−2 (Fp )|, according to Conjecture 1.3. To
simplify things, let us just consider Sn , the case of An being similar. Then it
is known that a permutation drawn uniformly at random from Sn has a cycle of
length at least n/2 in its cycle decomposition with positive probability. This fact
1
is closely related to the well-known ‘100 Prisoners
Problem’ posed in [9]. So this
would predict for fixed p-A. g that as p varies we should often (in fact being more
careful with the statistics, with high probability) see an orbit of length  p2 of g
on Y−2 (Fp ). This guess also turns out not to be correct in general.
To describe our numerics, we introduce special elements of PGL2 (Z). We first
note, if g has determinant −1, then the qualitative behavior of the longest orbit of
g will be governed by that of g 2 , which has determinant 1. So it is sufficient (at

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

5

least for the phenomena we show) to consider only elements of PSL2 (Z). Let




1 1
1 0
U=
, V =
.
1 1
0 1
Lemma 1.6. Every hyperbolic element of PSL2 (Z) is conjugate to an element
U n1 V m1 . . . U nk V mk
with k > 0 and all ni , mi > 0. We call this a reduced U V -word.
This is well-known, but for completeness we prove Lemma 1.6 in Section 4 below.
Since the orbit lengths of g on Xκ (Fp ) are the same after conjugation, we may simply
consider reduced U V -words in what follows. Our conjectural answer to Problem
1.1 is based on a dichotomy for hyperbolic g ∈ PSL2 (Z).
Definition 1.7. A reduced U V -word U n1 V m1 . . . U nk V mk is a cyclic palindrome if
its reverse can be cyclically rotated to obtain the original word. For example:
reverse

rotate

rotate

rotate

U 2 V U V −−−−→ V U V U 2 −−−→ U V U 2 V −−−→ V U 2 V U −−−→ U 2 V U V.
Then U 2 V U V is a cyclic palindrome, whereas U 2 V 2 U V is not. Following Sarnak
[21] (who follows terminology of Gauss) we make the following definition.
Definition 1.8. Say g ∈ PSL2 (Z) is ambiguous if the conjugacy class of g in
PSL2 (Z) is conjugated to the conjugacy class of g −1 in PSL2 (Z) by an element of
PGL2 (Z) of determinant −1.
Our two definitions actually coincide.
Proposition 1.9. Let hyperbolic g ∈ PSL2 (Z) be given by a reduced U V -word.
Then the U V -word is a cyclic palindrome if and only if g is ambiguous.
We prove Proposition 1.9 in Section 4. In Figure 1.1 we show the longest orbits
of U 2 V U V and U 2 V 2 U V on Y−2 (Fp ). They evidently have strikingly different
behaviors. Note that




2 3
3 5
U 2V U V =
, U 2V 2U V =
,
5 8
7 12
so they are both hyperbolic. However, Figure 1.1 shows that the longest orbit of
U 2 V U V is on the order of p and that of U 2 V 2 U V is on the order of p2 . Based on further evidence (see Table 1 and Figure 1.2), we are led to conjecture that the crucial
difference between these words is that U 2 V U V is a cyclic palindrome/ambiguous.
Write L(g; p) for the longest orbit of g on Y−2 (Fp ). We make the following conjecture:

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

6

Conjecture 1.10. Let g ∈ PSL2 (Z) be hyperbolic. If g is ambiguous then
(1) There are constants C1 = C1 (g) > 0 and C2 = C2 (g) > C1 such that
C1 p ≤ L(g; p) ≤ C2 p for all primes p.
(2) The discrete probability measures


X
1

δ L(g;p) 
#{primes p ≤X}
p
p≤X

converge as X → ∞ to a compactly supported Borel probability measure on
R.
If g is not ambiguous then
(1) There is a constant c = c(g) such that L(g; p) ≥ cp2 for all primes p.
(2) The discrete probability measures


X
1

δ L(g;p) 
#{primes p ≤X}
p2
p≤X

converge as X → ∞ to a compactly supported Borel probability measure on
R.
As a particular consequence, we conjecture that the answer to Problem 1.1 for κ =
−2 is
(
1 if g is ambiguous.
log(L(g; p))
lim
=
p→∞
log p
2 if g is not ambiguous.
The issue of whether elements of SL2 (Z) are conjugate to their inverses shows
up in several different areas of mathematics including connect sum problems for
manifolds [7], the dynamics of kicked toral automorphisms [20], and the classification
of foliations of torus bundles over the circle [10]. This issue is explored in depth
in the article of Sarnak [21] where it is related to the theory of binary quadratic
forms. A conjugacy class in PSL2 (Z) is called primitive if a representative is not a
power of another element. To each conjugacy class [g] in PSL2 (Z) one can attach
a number t([g]) = |trace(g)|. Let Π denote the collection of primitive hyperbolic
conjugacy classes in PSL2 (Z). It is a result of Hejhal [12], after Selberg [23], that
one has the asymptotic formula
X
X2
.
1≈
2 log X
p∈Π, t(p)≤X

On the other hand, Sarnak shows in [21] that if we write ΠA for the collection of
primitive hyperbolic ambiguous conjugacy classes in PSL2 (Z), then
X
97
1 ≈ 2 X(log X)2 .
8π
p∈ΠA , t(p)≤X

So the ambiguous classes are rare, with those having t(p) ≤ X taking up about a
square root of the number of all primitive hyperbolic classes with t(p) ≤ X.

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

7

100
80

U 2V 2U V

U 2V U V
80

60
60
40

40

20

20

0

0
0

0.2

0.4

0.6

4L(g;p)
p2

0.8

1

0

0.2

0.4

L(g;p)
10p

0.6

0.8

Figure 1.2. Histograms showing the distributions that feature in
Conjecture 1.10. Here p ranges between 1009 and 3761. For
U 2 V 2 U V the histogram shows the distribution of L(g; p)(p2 /4)−1 .
Note |Y−2 (Fp )| is asymptotic to p2 /4. For U 2 V U V the distribution
is of L(g; p)(10p)−1 . The 10 is not significant and has just been chosen to scale the data. One outlier (p = 3079, L(g; p) = 35585) has
been removed from the U 2 V U V chart.
Acknowledgments. We would like to thank Alex Gamburd, Alexei Entin, José
Gonzalez, Sam Payne, Doron Puder, Dhruv Ranganathan, Peter Sarnak, and Joseph
Silverman for enlightening discussions about this work. The first version of this
paper was written during the Summer Undergraduate Research at Yale program,
funded in part by Sam Payne’s N.S.F. CAREER award DMS–1149054.
2. Proof of Theorem 1.2
In this section we prove Theorem 1.2. Let mi denote the Markoff moves on
X−2 (Fp ), defined for i = 1, 2, 3 by
m1 (x, y, z) = (yz − x, y, z), m2 (x, y, z) = (x, xz − y, z), m3 (x, y, z) = (x, y, xy − z)
These moves together with permutations in S3 , permuting the coordinates, generate
all of PGL2 (Z) ≤ Aut(Xκ ). We will prove Theorem 1.2 by calculating the sign of
the mi and elements of S3 as permutations of Y−2 (Fp ).
We begin by examining the subgroup N of Aut(Xκ ) as it plays a special role in
the action of Out(F2 ) on X∗−2 (Fp ). Recall from the Introduction the elements ni
and the fact that Out(F2 ) permutes the N -orbits of X∗−2 (Fp ).
Lemma 2.1. There are no points in X∗−2 (Fp ) with zeroes in exactly two coordinate
entries. Hence for p > 2 all orbits of N in X∗−2 (Fp ) are of size 4.
1

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

g not ambiguous
g
L(g; 727)
1
1
3
1
2
2
V U V U V U
87928
3
2
1
2
2
2
V U V U V U
77996
1
1
2
1
2
3
V U V U V U
75289
V 2U 1V 1U 2V 1U 2
95183
2
1
1
1
3
1
V U V U V U
42238
2
1
1
2
2
3
V U V U V U
62702
1
1
1
3
2
1
V U V U V U
51981
1
1
3
4
1
1
V U V U V U
75716
1
4
2
1
1
1
V U V U V U
79495
1
3
2
2
3
1
V U V U V U
86897
3
1
1
2
1
3
V U V U V U
108710
2
3
1
1
3
1
V U V U V U
61549
V 1U 1V 2U 4V 3U 1
87870
1
1
2
1
3
2
V U V U V U
82633
2
4
1
1
1
1
V U V U V U
79495
4
1
1
1
1
4
V U V U V U
130737
3
4
1
1
2
1
V U V U V U
72046

8

g ambiguous
g
L(g; 727)
1
1
1
1
1
2
V U V U V U
3193
1
1
3
1
1
2
V U V U V U
2018
2
1
2
3
2
1
V U V U V U
2780
V 4U 1V 1U 2V 1U 1
3748
1
2
1
2
3
2
V U V U V U
2780
1
1
1
1
1
4
V U V U V U
2894
1
1
1
2
1
2
V U V U V U
4591
1
3
1
1
1
1
V U V U V U
3285
1
2
1
2
1
2
V U V U V U
3331
2
2
2
1
2
2
V U V U V U
3350
1
4
1
1
4
1
V U V U V U
1756
2
1
2
4
2
1
V U V U V U
2022
V 2U 1V 1U 1V 2U 4
2937
1
2
1
1
1
1
V U V U V U
3193
1
2
2
2
1
1
V U V U V U
3680
1
2
3
2
1
2
V U V U V U
2780
1
2
1
1
4
1
V U V U V U
3748

Table 1. This table gives evidence for Conjecture 1.10. The data
is for p = 727. We have |Y−2 (F727 )| = 131587. Recall L(g; 727) is
the longest orbit of g on Y−2 (F727 ).
Proof. By symmetry, it suffices to check that we can have no (0, 0, z) ∈ X∗−2 (Fp ),
with z 6= 0. If x, y = 0, substituting into (1.1) with κ = −2 we obtain 0 + 0 + z 2 = 0
which implies z = 0. Given the first statement of the lemma, the second follows
since no points of X∗−2 (Fp ) are fixed by any ni .

Due to a result of Carlitz [5], |X∗−2 (Fp )| = p(p + 3) when p ≡ 1 (mod 4) and
= p(p − 3) when p ≡ 3 (mod 4). Thus,
(
1
p(p + 3), if p ≡ 1 (mod 4)
(2.1)
|Y−2 (Fp )| = 41
4 p(p − 3), if p ≡ 3 (mod 4)
|X∗−2 (Fp )|

The following fact will be useful later.
Fact 2.2. In Fp , the number of distinct pairs of consecutive quadratic residues, both
nonzero, is exactly:
(
1
4 (p − 5), when p ≡ 1 (mod 4)
(2.2)
1
4 (p − 3), when p ≡ 3 (mod 4) .

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

9

The total number of consecutive quadratic residues is found in [1, Theorem 10-2]1.
We discount the pair (0, 1) in both cases, and (−1, 0) when p ≡ 1 (mod 4).
Lemma 2.3. Let p be an odd prime. For a given i ∈ {1, 2, 3}
(
p − 5, p ≡ 1 (mod 4)
#{(x, y, z) ∈ X∗−2 (Fp ) | mi (x, y, z) = (x, y, z)} =
p − 3, p ≡ 3 (mod 4) .
Proof. We will prove this formula for m1 , and it follows for m2 , m3 by symmetry.
We have that m1 (x, y, z) = (x, y, z) exactly when
(2.3)

2x = yz.

Lemma 2.1, equation (2.3), and our assumption that (x, y, z) 6= (0, 0, 0) imply
that x, y, z 6= 0. Substituting x = yz/2 into (1.1) we have
y2z2
= 0.
4
As x is uniquely determined given y, z by (2.3) we count the solutions to (2.4) over
Fp .
Letting Y = y 2 , Z = z 2 we have
(2.4)

(2.5)

y2 + z2 −

Z(Y − 4) = 4Y .

As y, z 6= 0 there are exactly as many y, z satisfying (2.4) as four times the number
of solutions to (2.5).
By (2.5), as Y 6= 0, Z is determined uniquely by Y , so we just need to count
possible values of Y 6= 0 that can satisfy (2.5). As Y and Z are quadratic residues,
Y − 4 must also be. Thus to count the possible solutions to (2.5), we just need to
count the possible values of Y such that both Y and Y − 4 are nonzero quadratic
residues. This is the case if and only if Y /4 and (Y − 4)/4 are consecutive nonzero
quadratic residues. By (2.2), for p ≡ 1 (mod 4) (resp. p ≡ 3 (mod 4)), there are
(p − 5)/4 (resp. (p − 3)/4) of these. This gives us our result.

Lemma 2.4. Suppose p is an odd prime. For a given i ∈ {1, 2, 3}, the Markoff
move mi acts as an even permutation on Y−2 (Fp ) exactly when p ≡ 3 (mod 8).
Proof. We will show this result for m1 and it follows by symmetry for m2 , m3 .
Because it is an involution, the permutation induced by m1 on Y−2 (Fp ) is a product
of
|Y−2 (Fp )| − |F |
(2.6)
r :=
2
disjoint transpositions, where F is the set of fixed points of m1 in Y−2 (Fp ). Each
of the ni commute with m1 , so x ∈ X−2 (Fp ) is fixed by m1 if and only if all the
elements of N ·x are fixed by m1 . Consequently |F | is exactly one fourth the number
of fixed points of m1 in X∗−2 (Fp ) which we have calculated in Lemma 2.3. We also
1Count the number of the solutions (a, b) to a2 − b2 = 1 in F . To do this, count unordered
p

pairs α := a + b, β := a − b such that αβ = 1, then discount ones that result in the same values of
a2 , b2 .

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

10

recall from (2.1) the size of Y−2 (Fp ). We calculate the parity of m1 by calculating
r case by case:
If p = 4k + 1


1 p2 + 3p p − 5
= 2(k 2 + k) + 1 ≡ 1 (mod 2),
r=
−
2
4
4
so m1 acts as an odd permutation. If p = 8k + 7


1 p2 − 3p p − 3
r=
= 8k 2 + 10k + 3 ≡ 1
−
2
4
4
so m1 acts as an odd permutation. If p = 8k + 3


1 p2 − 3p p − 3
r=
= 8k 2 + 2k ≡ 0
−
2
4
4

(mod 2),

(mod 2),

so m1 acts as an even permutation.



Proposition 2.5. The permutation group generated by the action of hm1 , m2 , m3 i
on Y−2 (Fp ) is contained in the alternating group on Y−2 (Fp ) if and only if p ≡ 3
(mod 8).
Proof. This follows directly from Lemma 2.4.



In order to complete our proof of Theorem 1.2, we must check the parity of the
other generators of PGL2 (Z) (through which Out(F2 ) acts). The only remaining
generators to check, aside from the Markoff moves, are those of S3 . By Proposition
2.5, we know there always will be odd permutations for p 6≡ 3 (mod 8), so we only
need to examine the remaining case, when p ≡ 3 (mod 8).
Lemma 2.6. The action of S3 on Y−2 (Fp ) consists of even permutations when p ≡ 3
(mod 16). When p ≡ 11 (mod 16), it consists of both even and odd permutations.
Proof. The group S3 is generated by transpositions, and by symmetry they all have
the same parity, so it suffices to check the parity of the action of the transposition
(1 2) in the cases we consider.
Our strategy is to count the points in X∗−2 (Fp ) whose N -orbits are fixed by (1 2).
We start by counting how many possible values x can take on, then for each of those
values we will count how many points with fixed orbits there are.
The N -orbit of (x, y, z) is fixed by (1 2) if and only if
(2.7)

(x, y, z) ∈ {(y, x, z), (y, −x, −z), (−y, x, −z), (−y, −x, z)},

which is if and only if x = ±y. Note that by Lemma 2.1 this rules out x = 0.
Substituting x = ±y into (1.1) with κ = −2 we reduce to two cases:
(2.8)
(2.9)

x 6= 0,
x 6= 0,

y = x,

2x2 + z 2 = x2 z, or

y = −x,

2x2 + z 2 = −x2 z .

For fixed x, in both cases we obtain quadratic equations in z with discriminant
∆ = x2 (x2 − 8). Note that ∆ 6= 0 as x 6= 0 and 8 is not a quadratic residue of Fp

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

11

because p ≡ 3 (mod 8) in the cases we consider. Thus (2.8) and (2.9) have solutions
over Fp if and only if ∆ is a square, which happens if and only if x2 − 8 is a square.
As we assume p ≡ 3 (mod 8), there exists2 some α such that α2 = −8. Setting
w := x/α we want to count how many values w can take such that x2 − 8 =
−8(w2 + 1) is a square, which we do by counting the number of nonzero consecutive
quadratic residues w2 and w2 + 1. From Fact 2.2 we have that there are (p − 3)/4
such pairs of the form (w2 , w2 + 1) where w2 6= 0 (as in both cases p ≡ 3 (mod 4)).
Each pair of residues, (w2 , w2 + 1), can be made by both w and −w, which gives us
(p − 3)/2 possible values of w and hence of x.
For each valid x, those such that ∆ is a square, we have exactly four solutions
total to (2.8) and (2.9) for (x, y, z) that correspond to four points which satisfy both
(1.1) and (2.7) and thus four points whose N -orbits are fixed by (1 2):
(x, x, z1 ), (x, x, z2 ), (x, −x, −z1 ), (x, −x, −z2 )
√
√
x2 − ∆
x2 + ∆
, z2 =
.
where z1 =
2
2
Recall that as ∆ 6= 0, we have that z1 6= z2 , so these four points are distinct. This
gives us 2(p − 3) points of X∗−2 (Fp ) in total whose N -orbits are fixed by (1 2). As
each N -orbit in X∗−2 (Fp ) has exactly 4 points, there are p−3
2 fixed N -orbits of (1 2).
To determine the parity of (1 2), we use the same method of counting disjoint
transpositions as we did for m1 in the proof of Lemma 2.4. Letting F denote the
fixed N -orbits of (1 2), we examine the two cases:
If p = 16k + 3


|Y−2 (Fp )| − |F |
1 p(p − 3) p − 3
=
−
= 2k(16k + 1) ≡ 0 (mod 2),
2
2
4
2
so (1 2) acts as an even permutation.
If p = 16k + 11


|Y−2 (Fp )| − |F |
1 p(p − 3) p − 3
=
−
= 32k 2 + 34k + 9 ≡ 1
2
2
4
2

(mod 2),

so (1 2) acts as an odd permutation. The lemma follows directly from this result.



Theorem 1.2 now follows directly from Lemma 2.6 and Proposition 2.5.
3. Lower bound on the longest orbit
3.1. Background on the free group. Here we give necessary background about
the free group F2 and its automorphisms. We write X and Y for the generators of
F2 . Firstly, we always assume words in F2 are reduced, meaning positive powers
of X do not appear beside negative powers, and similarly for Y . Following [19] we
make the following definition.
2As p ≡ 3 (mod 4) we have that

This implies that



−2
p



=



−8
p





= 1.

−1
p



= −1 and as p ≡ 3 (mod 8) we have that

 
2
p

= −1.

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

12

Definition 3.1. A word w ∈ F2 is monotone if for each letter X or Y , all the
exponents of this letter in w have the same sign.
We need the following proposition that appears in Parzanchevski and Puder [19,
Prop. 3.5].
Proposition 3.2. Any element Φ of Out(F2 ) has a representative in Aut(F2 ) of
the form
(3.1)

Φ̂ : (X, Y ) 7→ (w1 , w2 )

where w1 and w2 are monotone words in F2 .
In the setting of Proposition 3.2 we say that Φ̂ is monotone. Suppose Φ̂ ∈ Aut(F2 )
as in (3.1) is monotone, with
i

i

i

i

i

i

wi = X α1 Y β1 X α2 Y β2 . . . X αti Y βti
for some αji , βji , ti ∈ Z. We identify Z2 ∼
= F2 /[F2 , F2 ] by the basis induced by X, Y .
2
Then Φ̂ acts on Z by the matrix
!
a1 a2
∈ GL2 (Z)
b1 b2
P
P
where ai = j αji and bi = j βji . Moreover the values ai and bi are uniquely determined by Φ ∈ Out(F2 ) and vice versa. We pass freely between these representations
of Φ in the rest of the paper.
3.2. Algebraic setup. We consider the affine scheme over Z[κ]
X := Spec(R)
where
I := (x2 + y 2 + z 2 − xyz − 2 − κ).

R := Z[κ, x, y, z]/I,

For particular choice of κ ∈ Z we obtain a scheme over Z that we denote by
Xκ := Spec(Rκ ),
where
Rκ := Z[x, y, z]/Iκ ,

Iκ := (x2 + y 2 + z 2 − xyz − κ).

In the case of κ = −2 one obtains the Markoff surface. The group Out(F2 ) ∼
=
GL2 (Z) acts on X by automorphisms of schemes over Z[κ] and for each κ, GL2 (Z)
acts on Xκ by automorphisms.

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

13

3.3. The Cayley Cubic. When κ = 2, X2 is Cayley’s cubic surface [6]. In fact X2
is closely related to the split torus G2m ; we heavily exploit this fact in the sequel.
To see this, let X̃2 := Spec(R̃2 ) where
R̃2 := Z[x, y, z, δ, η]/J2 ,

J2 := (x2 + y 2 + z 2 − xyz − 4, δ 2 − xδ + 1, η 2 − yη + 1).

The mapping
R̃2 → OG2m := Z[δ, δ ∗ , η, η ∗ ]/(δδ ∗ − 1, ηη ∗ − 1)
(3.2)
(3.3)
(3.4)

x →
7
δ + δ∗
y →
7
η + η∗
z 7→ δη + δ ∗ η ∗

and δ, η 7→ δ, η induces an isomorphism X̃2 ∼
= G2m . The inclusion of R2 → R̃2
induces a map
G2m ∼
= X̃2 → X2 .
There is an action of GL2 (Z) on G2m by
g(δ) = δ a η c ,
(3.5)

g(δ ∗ ) = (δ ∗ )a (η ∗ )c ,

g(η) = δ b η d ,
g(η ∗ ) = (δ ∗ )b (η ∗ )d ,

!
a b
for g =
∈ GL2 (Z). We interpret δ −n = (δ ∗ )n for n ∈ Z and similarly
c d
η −n = (η ∗ )n .
Let ι be the map ι : R2 → OG2m defined by the inclusion R2 → R̃2 followed by
the map R̃2 → OG2m given by (3.2), (3.3), (3.4). This induces a map
ι∗ : G2m → X2 .
Lemma 3.3. The map ι∗ : G2m → X2 is GL2 (Z)-equivariant.
Proof. Recall U, V from our Introduction. The lemma can be checked by noting
that GL2 (Z) is generated by U , V and (1 2), and these act on R2 by
U (x, y, z) = (z, y, zy − x),

V (x, y, z) = (x, z, xz − y), (1 2)(x, y, z) = (y, x, z).
!
1 1
Then taking V as an example, V =
, and therefore using (3.2), (3.3), (3.4)
0 1
and (3.5) gives
V ◦ ι(x, y, z) = V (δ + δ ∗ , η + η ∗ , δη + δ ∗ η ∗ )
= (δ + δ ∗ , δη + δ ∗ η ∗ , δ 2 η + (δ ∗ )2 η ∗ ) = ι(x, z, xz − y) = ιV (x, y, z).
The calculations for U and (1 2) are similar.



Our current goal is to calculate the action of a given g ∈ GL2 (Z) on X2 . We will
do this by exploiting the embedding ι : R2 → OG2m . It is convenient for our analysis
to exclude certain edge cases, so we make the following definition.

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

Definition 3.4 (Good matrices). Let g =

a b
c d

14

!
∈ GL2 (Z). We say g is good

if a, b, c, d ≥ 2.
We use the notation Ox (xn ) for the class of polynomials containing terms with
x-degree ≤ n, that is, with no monomial summand containing a power of x greater
than n.
Proposition 3.5. For each coprime a, c ∈ Z with a ≥ 2, c ≥ 2 there are!polynomials
a b
pa,c , qa,c ∈ Z[x, y] with the following properties. Assume g =
∈ GL2 (Z)
c d
and that g is good.
(1) We have
g(x) = pa,c + qa,c z mod I2 ,

g(y) = pb,d + qb,d z mod I2

where x, y ∈ R2 are the first two coordinate functions on X2 . Here when we
make statements that relate elements of Z[x, y] to elements of Rκ we always
use the natural inclusion Z[x, y] → Rκ .
(2) We have
!
pa,c − x qa,c
D := det
= xa+b−1 D0 + Ox (xa+b−2 )
pb,d − y qb,d
with D0 ∈ Z[y], with D0 6= 0 and monic, up to a sign, and deg(D0 ) =
|d − c| − 1 ≥ 0.
Proof. Working in R̃2 , write
(x, y, z) = (δ + δ ∗ , η + η ∗ , δη + δ ∗ η ∗ ).
It will be useful to use the notations3 c(δ n η m ) := δ n η m +(δ ∗ )n (η ∗ )m , and s(δ n η m ) :=
δ n η m − (δ ∗ )n (η ∗ )m , interpreting δ −1 as δ ∗ as before to extend the definitions of c
and s to include negative powers of δ and η. Note that analogs of trigonometric
formulas hold also for these functions.
Now, g(x, y) is given by the expression
(g(x), g(y)) = (c(δ a η c ), c(δ b η d ))
1
(3.6)
=
(c(δ a )c(η c ) + s(δ a )s(η c ), c(δ b )c(η d ) + s(δ b )s(η d )).
2
We have
x
y 
(3.7)
c(δ a ) = 2Ta
, c(η c ) = 2Tc
,
2
2
where for a ≥ 0, Ta ∈ Z[t] is the Chebyshev polynomial of the first kind. Although
we work in Z[ 12 ]⊗R̃2 throughout the proof, our final results will hold in R2 . Similarly
for a, c ≥ 2
x
y 
s(δ a ) = Ua−1
(3.8)
s(δ), s(η c ) = Uc−1
s(η),
2
2
3c(δ) should be thought of as 2 cos(θ) for abstract θ such that δ = exp(iθ).

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

15

where Ua ∈ Z[t] is the Chebyshev polynomial of the second kind.
Using this we obtain from (3.6) and (3.7), (3.8) the expression
(g(x), g(y)) = (Pa,c (x, y, z), Pb,d (x, y, z)),
where
x

x
y 
1
+ Ua−1
Uc−1
(2z − xy).
2
2
2
2
2
To obtain this expression, we used that s(δ)s(η) = 2z − xy. The key point is that
Pa,c (x, y, z) is linear in z, and we obtain Part 1 of the proposition with
x
y 
x y  1
Tc
− xyUa−1
Uc−1
,
pa,c (x, y) := 2Ta
2
2
2 x  2  y 2
Uc−1
.
qa,c (x, y) := Ua−1
2
2


Using that 2Ta 2t and Ua−1 2t are monic in t for a ≥ 1 of degrees a and a − 1
respectively, we get that the leading x-degree contribution to pa,c is xa uc where
y  y
y 
y 
uc (y) : = Tc
(3.9)
− Uc−1
= −Uc−2
.
2
2
2
2
The last equality uses the sum of angle formula for sine together with the connection
between Chebyshev polynomials and trigonometric functions. The leading x-degree
contribution to qa,c is more easily seen to be xa−1 vc where
y 
.
vc (y) := Uc−1
2
This concludes our calculations for the pair a, c. Since g is good, we have b, d ≥ 2 and
so the calculation of Pb,d and pb,d , qb,d is analogous to the preceding one, replacing
a, c 7→ b, d.
Calculation of D and D0 . Note that since g is good, we must have c 6= d.
Indeed, if c = d then from the determinant of g being ±1, one sees that c and d are
coprime, which cannot happen since c = d ≥ 2. Since a ≥ 2, the −x term in the
determinant does not contribute to the largest x-degree term. We get
Pa,c (x, y, z) := 2Ta

Tc

y 

D = xa+b−1 (uc vd − vc ud )
y 
y 

y 
 y 
= xa+b−1 −Uc−2
Ud−1
+ Ud−2
Uc−1
+ Ox (xa+b−2 )
2
2
2
2
y 
= xa+b−1 sign(d − c)U|d−c|−1
+ Ox (xa+b−2 ),
2
where one can use sum of angle formulas for sine to get the final identity.



3.4. The deformation from κ = 2. It is well known since work of Fricke [8] that
to each w ∈ F2 the induced word map w : SL2 (C) × SL2 (C) → SL2 (C) has
tr(w(A, B)) = Pw (x, y, z)
for unique Pw ∈ Z[x, y, z], where x = tr(A), y = tr(B), z = tr(AB). Indeed this
follows from repeated applications of the identity
(3.10)

tr(uv) = tr(u)tr(v) − tr(u−1 v),

u, v ∈ SL2 (C).

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

16

If θ ∈ Aut(F2 ) acts by θ(X, Y ) = (w1 (X, Y ), w2 (X, Y )) then θ acts on the coordinate functions x, y ∈ R by
θ(x) = Pw1 (x, y, z),

θ(y) = Pw2 (x, y, z),

Pwi ∈ Z[x, y, z].

Define the (x, z)-degree of a monomial xα y β z γ κδ to be α+γ, and define the (x, z)degree of a polynomial f in Z[κ, x, y, z] to be the maximum of the (x, z)-degrees of
the monomials with nonzero coefficients in f . We write f (N ) for the (x, z)-degree
N piece of f , that is, the part comprised of monomials of (x, z)-degree N .
Lemma 3.6. Write X, Y for fixed generators of F2 . Let
w = X α1 Y β1 X α2 Y β2 . . . X αt Y βt
P
P
be a monotone word, with every αi , βi 6= 0. Let a = ti=1 αi and b = ti=1 βi . The
(x, z)-degree of Pw is ≤ |a|.
Proof. Assume for ease of exposition that all αi , βi are positive, so a, b > 0. This
will be the case for words arising from good elements of GL2 (Z). The proof is by
induction on the partial order  defined by the following moves:
• If any αi has αi ≥ 2 then w0 , w00  w for either w0 , w00 obtained by replacing
αi 7→ αi − 1 or αi 7→ αi − 2. Then (3.10) yields
Pw (x, y, z) = xPw0 (x, y, z) − Pw00 (x, y, z).
Note if the lemma holds for Pw0 and Pw00 , it holds for Pw .
• If any βi has βi ≥ 2 then we perform the replacements βi 7→ βi − 1 or
βi 7→ βi − 2 to form w0 , w00 and declare w0 , w00  w. By the same logic as
before, Pw (x, y, z) = yPw0 (x, y, z) − Pw00 (x, y, z) so if the lemma holds for w0
and w00 it holds for w.
• We identify all words with their cyclically reduced conjugates. This doesn’t
change Pw .
To put this all together, note that any minimal cyclically reduced word with respect
to  has all the αi = βi = 1. If all the αi and βi are 1, and w is cyclically reduced,
then w is a power of XY or Y X and e.g. if w = (XY )n then a = n. On the other
hand, P(XY )n (x, y, z) = 2Tn z2 has (x, z)-degree n as required (this also shows the
statement of the lemma is sharp).

Our next goal is to show, in the present context, that Pw are equal in R to
functions that are linear in z and such that certain terms have no dependence on κ.
Lemma 3.7. If θ ∈ Aut(F2 ) satisfies θ(X, Y ) = (w1 (X, Y ), w2 (X, Y )), then
Pw1 (x, y, z) = Uw1 + Vw1 z mod I,

Pw2 (x, y, z) = Uw2 + Vw2 z mod I

where Uwi , Vwi ∈ Z[κ, x, y] have the following property. If Ni is at least the (x, z)degree of Pwi then
(1) Uwi = xNi Uw0 i + Ox (xNi −1 ) with Uw0 i ∈ Z[y].
(2) Vwi = xNi −1 Vw0i + Ox (xNi −2 ) with Vw0i ∈ Z[y].
In particular, Uw0 i and Vw0i do not depend on κ.

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

17

Proof. Transform Pw1 (x, y, z) by replacing each monomial of the form xα y β z γ with
γ ≥ 2 by
xα y β z γ 7→ xα y β z γ−2 (xyz − x2 − y 2 + 2 + κ),

(3.11)

these two terms are equal mod I. Moreover this replacement has the following properties: if p, q ∈ Z[κ, x, y, z] and p 7→ q in this manner then
• The (x, z)-degree of q is at most the (x, z)-degree of p.
• Let N1 be at least the (x, z)-degree of p and let p(N1 ) be the (x, z)-degree
N1 component of p and similarly define q (N1 ) . If N1 is larger than the (x, z)degree of p then p(N1 ) is zero. If p(N1 ) ∈ Z[x, y, z] then q (N1 ) ∈ Z[x, y, z]
(so doesn’t depend on κ). This follows since q (N1 ) is obtained from p(N1 ) by
replacement of all monomials of the form xα y β z γ with γ ≥ 2 by
xα y β z γ 7→ xα y β z γ−2 (xyz − x2 ) = xα+1 y β z γ−2 (yz − x).
Monomials xα y β z γ with γ ≤ 1 are left unaltered.
The effect of iterating this reduction, beginning with the fact that Pw1 ∈ Z[x, y, z],
yields polynomials Uw1 , Vw1 ∈ Z[κ, x, y] such that Pw1 = Uw1 + Vw1 z mod I, the
(x, z)-degree of Uw1 + Vw1 z is ≤ N1 , and (Uw1 + Vw1 z)(N1 ) ∈ Z[x, y, z]. This means
(N )
that the x-degree of Uw1 is ≤ N1 and Uw1 1 ∈ Z[x, y]. Similarly the x-degree of Vw1
(N1 −1)
is ≤ N1 − 1 and Vw1
∈ Z[x, y]. Performing this reduction also for Pw2 with N2
in place of N1 establishes the result.

Proposition 3.8. For each coprime a, c ∈ Z with a ≥ 2, c ≥ 2 there are!polynomials
a b
p̃a,c , q̃a,c ∈ Z[x, y] with the following properties. Assume g =
∈ GL2 (Z)
c d
and that g is good.
(1) We have
g(x) = p̃a,c + q̃a,c z mod I,

g(y) = p̃b,d + q̃b,d z mod I.

(2) Moreover,
D̃ := det

p̃a,c − x q̃a,c
p̃b,d − y q̃b,d

!
∈ Z[κ, x, y]

is given by
D̃ = xa+b−1 D0 + Ox (xa+b−2 )
where D0 ∈ Z[y] is the same quantity as in Proposition 3.5, for the same g.
Proof. Let Φ̂ ∈ Aut(F2 ) be a monotone automorphism representing g, given by
Proposition 3.2. We consider Φ(x) = g(x), the calculation of Φ(y) is similar. Let
w1 and w2 be the monotone words appearing in the expression (3.1) for Φ̂. We have
Φ(x) = Pw1 (x, y, z). This has (x, z)-degree ≤ a by Lemma 3.6. Note that since
we know w1 is monotone, we can conjugate w1 to be of the form as in Lemma 3.6
without changing a or Pw1 (x, y, z).

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

18

Applying Lemma 3.7 with N1 = a we can write
Φ(x) = Uw0 1 xa + Uw0 1 + (Vw01 xa−1 + Vw0 1 )z,
where Uw0 1 , Vw01 ∈ Z[y], Uw0 1 ∈ Z[κ, x, y] has x-degree ≤ a − 1 and Vw0 1 ∈ Z[κ, x, y]
has x-degree ≤ a − 2. We obtain the first part of the proposition with
(3.12)

p̃a,c := Uw0 1 xa + Uw0 1 ,

q̃a,c := Vw01 xa−1 + Vw0 1 .

Similarly p̃c,d and q̃c,d are obtained by replacing w1 by w2 and a, c 7→ b, d. Note at
this moment we do not know that Uw0 1 and Uw0 2 are non-zero.
Let π be the evaluation map Z[κ, x, y, z] → Z[x, y, z] sending κ 7→ 2. We must
have in R2
(3.13)

π (p̃a,c + q̃a,c z) ≡ π(p̃a,c ) + π(q̃a,c )z ≡ pa,c + qa,c z mod I2

where pa,b and qa,b are the polynomials from Proposition 3.5. This is because they
both describe how g maps the coordinate function x. In the other hand, since the left
and right hand sides of (3.13) differ by a function that is linear in z, this difference
must be zero since 0 is the only element of I2 that is linear in z. So the identity
(3.13) actually holds in Z[x, y, z]. This means π(p̃a,c ) = pa,c , π(q̃a,c ) = π(qa,c ) and
the same replacing a, c 7→ b, d.
This implies, if D is the quantity obtained in Proposition 3.5, that
π(D̃) = D.
From (3.12) we have
D̃ = xa+b−1 (Uw0 1 Vw02 − Uw0 2 Vw01 ) + Ox (xa+b−2 ).
Since the xa+b−1 coefficient of D̃ doesn’t depend on κ, and equals D0 when evaluated
at κ = 2, it must be equal to D0 . This completes the proof.

3.5. Proof of Theorem 1.5. Fix κ ∈ Z. Our proof relies on proving that reasonably small powers of g have few fixed points. The following lemma combines our
previous estimates with a variant of the Schwartz-Zippel Lemma [22, 26].
!
a b
Lemma 3.9. Let g =
∈ GL2 (Z) with |a|, |b|, |c|, |d| ≥ 2, then for any
c d
κ ∈ Z, g has fewer than 2p(||d| − |c|| + |a| + |b|) fixed points in Xκ (Fp ).
!
1 0
Proof. First if ab < 0 then conjugating by
gives a new matrix which
0 −1
has ab > 0. Now if a < 0, multiplying by −I gives a new matrix with a, b, c, d ≥ 2,
i.e. the resulting matrix is good. These operations do not change the conjugacy
class of the matrix in PGL2 (Z), therefore the number of fixed points on Xκ (Fp ),
and neither do they change the quantity 2p(||d| − |c|| + |a| + |b|). So we may assume
without loss of generality that g is good.

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

19

In this proof we distinguish a specific fixed value κ0 from the generic parameter
0 ,
κ of Z[κ, x, y]. Let p̃a,c , q̃a,c be the polynomials from Proposition 3.8, and let pκa,c
κ
0
qa,c be the images of p̃a,c , q̃a,c under the evaluation map
πκ0 : Z[κ, x, y] → Z[x, y],

κ 7→ κ0 .

If (X, Y, Z) ∈ Xκ0 (Fp ) is a fixed point of g, then from Proposition 3.8 we know
0 (X, Y ) + q κ0 (X, Y )Z = X and pκ0 (X, Y ) + q κ0 (X, Y )Z = Y so
pκa,c
a,c
b,d
b,d
!
!
!
κ0 (X, Y )
0 (X, Y ) − X
pκa,c
qa,c
1
0
≡
mod p.
(3.14)
κ0
(X, Y )
pκb,d0 (X, Y ) − Y qb,d
Z
0
In particular, the determinant Dκ0 ∈ Z[x, y] of this matrix must be zero when
evaluated at (X, Y ) ∈ F2p . But, recalling Proposition 3.8 and its notation,


Dκ0 = πκ0 (D) = πκ0 xa+b−1 D0 + Ox (xa+b−2 ) = xa+b−1 D0 + Ox (xa+b−2 )
by using that D0 ∈ Z[y].
Proposition 3.8 tells us that for Y ∈ Fp with D0 (Y ) 6= 0, the polynomial in
Fp [x] obtained by evaluating Dκ0 at y = Y has degree a + b + 1. So recalling from
Proposition 3.5 that D0 is monic up to a sign with degree |d − c| − 1, there are at
most
p.(||d| − |c|| − 1) + p(a + b + 1) = p(||d| − |b|| + |a| + |c|)
pairs (X, Y ) ∈ F2p for which (3.14) can hold. On the other hand, since X 2 +Y 2 +Z 2 =
XY Z + 2 + κ0 , given X, Y for which (3.14) holds, there are at most two possible Z
with (X, Y, Z) ∈ Xκ0 (Fp ).

Proof of Theorem 1.5. Given hyperbolic g in GL2 (Z), we consider powers g n of this
element. Let λ be the eigenvalue of g of largest modulus. Diagonalizing g we have
!
Q11 (λn , λ−n ) Q12 (λn , λ−n )
n
g =
Q21 (λn , λ−n ) Q22 (λn , λ−n )
where the Qij are quadratic forms depending on g. It is possible to check that since
g is hyperbolic, all the coefficients of g n are unbounded as n → ∞ in the sense
that for all M > 0, there is N (M ) such that when n > N (M ), |(g n )ij | > M for all
1 ≤ i, j ≤ 2.
Indeed, if g is hyperbolic it cannot fix [1; 0] or [0; 1] in the action of GL2 (Z)
on P 1 (R). So g has an attracting fixed point z+ in P 1 (R) that is distinct from
than [1; 0] and [0; 1]. Of course the same is true for the transpose g T . This means,
projectively, g n converges to a matrix with all entries nonzero. Since GL2 (Z) is
discrete, at least one entry of g n is unbounded, hence all the entries are.
Note this implies that for n ≥ n0 (g), g n satisfies the hypothesis of Lemma 3.9.
Noting that there is C = C(g) such that all coefficients of g n are ≤ Cλn , Lemma
3.9 gives that g n has fewer than 8Cp|λ|n fixed points on Xκ (Fp ) when n ≥ n0 (g).
We also need a bound on the number of fixed points of g n when n < n0 (g). In
this case, we have that g ndn0 (g)/ne satisfies the hypothesis of Lemma 3.9, so it has

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

20

fewer than M p fixed points, where
M = 8 max{ |(g ndn0 (g)/ne )i,j | : 1 ≤ i, j ≤ 2, , 1 ≤ n < n0 (g) }.
But any fixed point of g n gives rise to a fixed point of g ndn0 (g)/ne so this means g n
has fewer than M p fixed points.
For given N , this implies that the number of points in Xκ (Fp ) fixed by any g n
with n ≤ N is
X
X
Mp +
8Cp|λ|n ≤ n0 M p + C 0 p|λ|N .
≤
n<n0

n0 ≤n≤N

for C 0 = C 0 (g) > 0. We have |Xκ (Fp )| ≤ cp2 with c depending only on the complexity of Xκ viewed as a variety over Fp , hence independent of κ. This follows from
the Lang-Weil bound [15, Lemma 1], and also from direct consideration of (1.1).
Therefore if n0 M p + C 0 p|λ|N < cp2 then there exists a point in Xκ (Fp ) not fixed by
g n for any n ≤ N . Hence there is a cycle of g of length ≥ N where

cp
n0 M
log 2C
log p
0 − C0
N≈
=
+ Og (1).
log |λ|
log |λ|

4. Algebraic Characterization of Cyclic Palindromes
In this section, we use that PSL2 (Z) ∼
= Z/2Z ∗ Z/3Z with the generators of the
cyclic factors given by
!
!
0 1
0
1
S=
, R=
.
−1 0
−1 −1
!
1 1
Here R = ST where T =
. With this presentation, every conjugacy class
0 1
in S has a representative of the form either g = Ry , g = S, or
(4.1)

g = SRy1 . . . SRyk

with yi ∈ {1, 2} for 1 ≤ i ≤ k. However, powers of S and R are not hyperbolic,
so every hyperbolic conjugacy class has a representative as in (4.1). Moreover, a
representative of this form has unique sequence y1 , . . . , yk , up to cyclic rotation. We
write [y1 , . . . , yk ] for the cyclic equivalence class of this sequence.
Proof of Lemma 1.6. Note that in PSL2 (Z),
!
−1 −1
(4.2)
SR =
= V, SR2 =
0 −1
and substituting this into (4.1) proves Lemma 1.6.

1 0
1 1

!
= U,


THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

21

Proof of Proposition 1.9. Suppose g = U n1 V m1 . . . U nl V ml is a hyperbolic reduced
U V -word. Also suppose g is given by (4.1). Then g −1 is conjugate in PSL2 (Z) to
(4.3)

SR(1−yk ) SR(1−yk−1 ) . . . SR(1−y1 ) .

The action of PGL2 (Z) on conjugacy classes in PSL2 (Z) is generated by
!
0 1
w=
.
1 0
We calculate
wSw−1 = S,
Therefore with g as in (4.1), we have
(4.4)

wRw−1 = R2 .

wgw−1 = SR(1−y1 ) S . . . SR(1−yk ) .

which is conjugate in PSL2 (Z) to g −1 . Then comparing (4.3) and (4.4) we have
that g is ambiguous if and only if [(1 − y1 ), (1 − y2 ), . . . , (1 − yk )] = [(1 − yk ), (1 −
yk−1 ) . . . (1 − y1 )] which is if and only if [y1 , y2 , . . . , yk ] = [yk , . . . , y1 ], and it is easy
to see, using the substitutions (4.2), that this happens if and only if the reduced
U V -word giving g is a cyclic palindrome.

References
[1] George E. Andrews. Number theory. Dover Publications, Inc., New York, 1994. Corrected
reprint of the 1971 original [Dover, New York; MR0309838 (46 #8943)].
[2] J. Bourgain, A. Gamburd, and P. Sarnak. Markoff Surfaces and Strong Approximation: 1.
arXiv:1607.01530, July 2016.
[3] BH Bowditch. Markoff triples and quasifuchsian groups. Proceedings of the London Mathematical Society, 77(3):697–736, 1998.
[4] Serge Cantat. Bers and Hénon, Painlevé and Schrödinger. Duke Math. J., 149(3):411–460,
2009.
[5] Leonard Carlitz. The number of solutions of some special equations in a finite field. Pacific
Journal of Mathematics, 4:207–217, 1954.
[6] A. Cayley. A memoir on cubic surfaces. Philosophical Transactions of the Royal Society of
London, 159:231–326, 1869.
[7] Francis X Connolly and James F Davis. The surgery obstruction groups of the infinite dihedral
group. Geom. Topol., 8(3):1043–1078, 2004.
[8] Robert Fricke and Felix Klein. Vorlesungen über die Theorie der automorphen Funktionen. Band 1: Die gruppentheoretischen Grundlagen. Band II: Die funktionentheoretischen
Ausführungen und die Andwendungen, volume 4 of Bibliotheca Mathematica Teubneriana,
Bände 3. Johnson Reprint Corp., New York; B. G. Teubner Verlagsgesellschaft, Stuttg art,
1965.
[9] Anna Gál and Peter Bro Miltersen. The cell probe complexity of succinct data structures.
Theoretical computer science, 379(3):405–417, 2007.
[10] E. Ghys and V. Sergiescu. Stabilite et conjugaison differentiable pour certains feuilletages.
Topology, 19(2):179 – 197, 1980.
[11] William Goldman. The modular group action on real SL(2)-characters of a one-holed torus.
Geometry & Topology, 7:443–486, 2003.
[12] Dennis A. Hejhal. The Selberg Trace Formula for PSL(2, R), Volume 2. Springer-Verlag Berlin
Heidelberg, 1983.
[13] Robert Horowitz. Induced automorphisms on Fricke characters of free groups. Transactions of
the American Mathematical Society, 208:41–50, 1975.

THE CYCLE STRUCTURE OF A MARKOFF AUTOMORPHISM OVER FINITE FIELDS

22

[14] Mahito Kohmoto, Leo P. Kadanoff, and Chao Tang. Localization problem in one dimension:
mapping and escape. Phys. Rev. Lett., 50(23):1870–1872, 1983.
[15] Serge Lang and Andre Weil. Number of points of varieties in finite fields. American Journal
of Mathematics, 76(4):819–827, 1954.
[16] Andrey Markoff. Sur les formes quadratiques binaires indéfinies. Mathematische Annalen,
15:381–406, 1880.
[17] Darryl McCullough and Marcus Wanderley. Nielsen equivalence of generating pairs of SL(2, q).
Glasg. Math. J., 55(3):481–509, 2013.
[18] C. Meiri, D. Puder, and D. Carmon. The Markoff Group of Transformations in Prime and
Composite Moduli. arXiv:1702.08358, February 2017.
[19] Ori Parzanchevski and Doron Puder. Stallings graphs, algebraic extensions and primitive elements in F2 . Math. Proc. Cambridge Philos. Soc., 157(1):1–11, 2014.
[20] Leonid Polterovich and Zeev Rudnick. Kick stability in groups and dynamical systems. Nonlinearity, 14(5):1331, 2001.
[21] Peter Sarnak. Reciprocal geodesics. Clay Math Proceedings, 7:217–237, 2007.
[22] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. Assoc.
Comput. Mach., 27(4):701–717, 1980.
[23] A. Selberg. Harmonic analysis and discontinuous groups in weakly symmetric Riemannian
spaces with applications to Dirichlet series. J. Indian Math. Soc. (N.S.), 20:47–87, 1956.
[24] Joseph H. Silverman. Variation of periods modulo p in arithmetic dynamics. New York Journal
of Mathematics, 14, 07 2007.
[25] William P. Thurston. On the geometry and dynamics of diffeomorphisms of surfaces. Bull.
Amer. Math. Soc. (N.S.), 19(2):417–431, 1988.
[26] Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and algebraic
computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979), volume 72 of Lecture Notes
in Comput. Sci., pages 216–226. Springer, Berlin-New York, 1979.

Alois Cerbu,
Department of Mathematics,
Yale University,
New Haven CT 06511, U.S.A.
alois.cerbu@yale.edu

Michael Magee,
Department of Mathematical Sciences,
Durham University,
Durham DH1 3LE, U.K.
michael.r.magee@durham.ac.uk

Elijah Gunther,
Department of Mathematics,
Yale University,
New Haven CT 06511, U.S.A.
elijah.gunther@yale.edu

Luke Peilen,
Department of Mathematics,
Yale University,
New Haven CT 06511, U.S.A.
luke.peilen@yale.edu

