MARKOFF SURFACES AND STRONG APPROXIMATION: 1

arXiv:1607.01530v1 [math.NT] 6 Jul 2016

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

1. Introduction
This is the first of three papers giving detailed proofs of the results announced in
[BGS16]. The main result here is strong approximation for Markoff triples for prime
moduli. In paper two this is extended to more general moduli and applied to seiving in
Markoff numbers. In the third paper, we formulate a strong approximation conjecture
for more general affine Markoff surfaces and develop the techniques to obtain similar
results in these cases.
We review briefly the notation and setup from [BGS16] where background and
references can be found. The Markoff surface X is the affine surface in A3 given by
(1)

X : x21 + x22 + x23 − 3x1 x2 x3 = 0.

The Markoff triples M are the positive integer solutions to (1). Let Γ be a group
of affine integral morphisms of A3 generated by the permutations of the coordiantes
and the Vieta involutions R1 , R2 , , R3 , where
R3 (x1 , x2 , x3 ) = (x1 , x2 , 3x1 x2 − x3 )
and R2 , R3 are defined similarly. The orbit of (1, 1, 1) under Γ yields all of M [Mar79],
[Mar80]. If ∆ is the group of integral morphisms generated by Γ and the involutions
which replace two of the coordinates of x by their negatives, then X(Z) consists of
two ∆ orbits, namely of (0, 0, 0) and (1, 1, 1).
For p a prime number the action of Γ and ∆ on X descends to a permutation action
on the finite set X(Z/pZ) of solutions to (1) in Z/pZ. Our interest is in the orbits of
this action which we often refer to as the components.
Conjecture 1 (Strong Approximation Conjecture). For any prime p, X(Z/pZ) consists of two Γ orbits, namely {(0, 0, 0)} and X ∗ (Z/pZ) = X(Z/pZ)\{(0, 0, 0)}
Clearly the above conjecture implies strong approximation for M and X(Z) in the
form that their reductions mod p
M → X ∗ (p)
1

2

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

and
X(Z) → X(Z/pZ)
are onto.
In particular, one of the consequences is that the only prime congruence obstruction
for a Markoff number m (that is a number which is a coordinate of an x ∈ M) is the
one noted in [Fro13]: m 6= 23 , 0 mod p if p = 3 mod 4, p 6= 3.
Our first result asserts that there is a very large orbit.
Theorem 1. Fix ε > 0. Then for p large there is a Γ orbit C(p) in X ∗ (p) for which
|X ∗ (p)\C(p)| ≤ pε
(note that |X ∗ (p)| ∼ p2 ), and any Γ orbit D(p) satisfies
1

|D(p)| ≫ (log p) 3 .
The proof of Theorem (1) establishes the strong approximation conjecture unless
p − 1 is a very smooth number. In particular, the set of primes for which the strong
approximation conjecture fails is very small.
2

Theorem 2. Let E be the set of primes for which the strong approximation conjecture
fails. For ε > 0, the number of primes p ≤ T with p ∈ E is at most T ε , for T large.
We end the introduction by outlining the rest of the paper. In Section 2 we define
the fundamental rotations in Γ that are associated to an x ∈ X ∗ (p) and one of
its coordinates. These act on the conic sections gotten by intersecting X ∗ (p) with
the plane corresponding to the particular coordinate. Some basic properties of the
incidence graph of the intersections of the conic sections are established.
In Section 3, which we call the endgame, we define the cage C(p) which is shown
to be a large component of X ∗ (p). Specifically any x ∈ X ∗ (p) for which the rotation
associated to one of its coordinates (see Section 2 for definitions) has order at least
1
p 2 +δ0 (δ0 > 0) is shown to be in C(p).
In Section 4 , the middle game, the last statement is extended to x’s for which the
corresponding rotation has order pε0 (ε0 > 0 any fixed small number).
The methods used in Sections 3 and 4 rely on nontrivial upper bounds for the
number of points lying on curves over finite fields. In Section 3 Weil’s Riemann
Hypothesis [Wei41] is a key tool, but this is not strong enough when the order is less
1
than p 2 +δ0 . In its stead we use Stepanov’s auxiliary polynomial method [Ste69] in the
Appendix, or the recent gcd(u − 1, v − 1) bounds of Corvaja-Zannier [CS13], or the

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

3

combinatorial method based on the projective Szemeredi-Trotter Theorem [Bou12]
developed in section 4.
Section 5, the opening, deals with x’s for which the orders of the associated rotations
are very small (for example, being uniformly bounded). This is done by lifting the
equations to characteristic zero which leads to an equation in (Q̄)3 in roots of unity.
In general (that is, in the setting of Paper III) we invoke Lang’s Gm conjecture at this
point (proven in [Lau83] for example), however for the special case at hand one can
show directly that X∗ (Q̄) has no finite Γ orbits (the last is a necessary condition for
strong approximation, in the form of Conjecture 1, to hold). This Q̄ analysis leads to
to part 2 of Theorem 1.
In Section 6 we assemble the various stages of our argument, explicated in Sections
3, 4, 5 and give a proof of Theorem 1 in a form from which strong approximation
follows if p2 − 1 is not very smooth: see (70). To prove Theorem 2 we combine the
above with a variant of the results in [CKSZ14] concerning the multiplicative orders
of coordinates of points of curves on A2 over Fp .
2. Preliminaries
2.1. Analysis of the conic sections. Theorem 1 in the weaker form that |C(p)| ∼
|X ∗ (p)| as p → ∞, can be viewed as the finite field analogue of [Gol03], where it is
shown that the action of Γ on the compact real components of the character variety
of the mapping class group of the once punctured torus is ergodic. As in [Gol03], our
proof makes use of the rotations τij ◦ Ri , i 6= j where τij permutes xi and xj . For
example,
τ2,3 ◦ R2 (x1 , x2 , x3 ) = (x1 , x3 , 3x1 x3 − x2 ),
so the action on (x2 , x3 ) for fixed x1 is given by the rotation rot(3x1 )
!
!
!
!
x2
x3
0
1
x2
(2)
rot(3x1 )
=
=
.
x3
3x1 x3 − x2
−1 3x1
x3
This rotation preserves the conic section obtained by intersecting X ∗ (p) with the
plane defined by the first coordinate being equal to the value of x1 ; in general, we
define the conic section Cj (a) as follows:
(3)

Cj (a) = {xj = a} ∩ X ∗ (p).

We give an explicit description of this action, depending
 2on whether x = 3x1
is parabolic (x2 − 4 = 0, that is x = ±2), hyperbolic ( x p−4 = 1) or elliptic
 2 

( x p−4 = −1) with ·· being the Legendre symbol.

4

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

 
= −1, that is if p ≡ −1 mod 4, then C1 (x) is
Lemma 3. Let x = ±2. If −1
p
 
empty. If −1
= 1, that is if p ≡ 1 mod 4, then
p
(4)

C1 (2) = (2, t, t ± 2i),

where i2 ≡ −1 mod p;
(5)

C1 (−2) = (−2, t, −t ± 2i),

which are pairs of disjoint lines. The action of ρ1 = rot(x) is
(6)

ρ1 (2, t, t ± 2i) = (2, t ± 2i, t ± 4i),

(7)

ρ1 (−2, t, −t ± 2i) = (−2, −t ± 2i, −t ∓ 4i),

so rot(2) preserves each line and rot(−2)interchanges them.
Now when x 6= ±2 we write

x = χ + χ−1 ,
 2 
 2 
where χ ∈ Fp if x p−4 = 1 and χ ∈ Fp2 if x p−4 = −1.
Note that
!
!
!
!
!
!−1
1
−1
1
−1
1
1
χ 0
χ
0
1
1
1 1
χ
−χ
=
rot(x) ==
χ
χ χ1
0 χ1
0 χ1
χ χ1
χ χ1
−χ 1

and consequently
!
1
1
χℓ
rot(x)ℓ =
χ χ1
0
and

hrot(x)i =

0
1
χℓ

1

χ

!

1 1
χ χ1

−1
−χ

!−1

(

=

χ1
χ

−
χ1 −

Consequently C1 (x) contains all elements


1 1
χ χ1
χ
χ1
1
χ1

!

χℓ
0

1
− χ1
χ1
1
− χχ1
χ1

0
1
χℓ

!

!

!
−1
−1  1
−χ
χ
−χ 1
1
χ

)

; χ1 ∈ hχi .


 


1 −1 
x2 
1
1 −1 
x3  1 
χ−
x3 −
χ1 + (χx2 − x3 )
, χ−
(χx3 − x2 )χ1 + x2 −
χ
χ
χ1
χ
χ χ1

with χ1 ∈ hχi.
Note that

where

o
n
b
Projx2 (Cx ) ⊃ aχ1 + ; χ1 ∈ hχi
χ1



x2 
1 −1
1 −1 
x3 −
and b = χ −
a= χ−
(χx2 − x3 )
χ
χ
χ

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

satisfy
σ = ab =



5

1
x 2  χ + χ 2
=
6 1.
=
χ − χ1
χ − χ1

Denoting by ρ a primitive root of Fp , a hyperbolic element x can be written in the
form
x = ρj + ρ−j .

(8)

For a hyperbolic element we let ord(x) = p−1
.
j
An elliptic element x can be written in the form
x = ξ j + ξ −j ,

(9)

where ξ is an element in Fp2 , ξ = (ρ̃)p+1 , where ρ̃ is a generator or the multiplicative
group of Fp2 . For an elliptic element we let ord(x) = p+1
.
j
Lemma 4. Let x be hyperbolic; write
x = w + w −1,

(10)

where w = ρj ∈ Fp . Then C1 (x) is a hyperbola with p − 1 points. Set
(11)

κ(x) =

Let
(12)



x2
.
x2 − 4

κ(x)
H(x) = { t,
t



| t ∈ Fp ∗ }.

Then we have the following map from H(x) to C1 (x):




κ(x)
κ(x)
κ(x)
→ x, t +
.
, tw +
(13)
t,
t
t
tw

In these coordinates
(14)

 


κ(x)
κ(x)
= tw,
.
ρ1 t,
t
tw

Lemma 5. Let x be elliptic; write
(15)

x = v + vp,

where v ∈ Fp2 − Fp , v p+1 = 1. Then C1 (x) is an ellipse with p + 1 points. Set
(16)
Let
(17)

κ(x) =

x2
.
x2 − 4

E(x) = {(t, tp ) | t ∈ Fp2 , tp+1 = κ(x)}.

6

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

Then we have the following map from E(x) to C1 (x):


κ(x)
κ(x)
p
.
, tv +
(18)
(t, t ) → x, t +
t
tv

In these coordinates
(19)

ρ1



κ(x)
t,
t





κ(x)
= tv,
.
tv

2.2. Incidence graph for the conic sections. We treat the case of p ≡ 3(mod4)
(the case of p ≡ 1(mod4) is simpler because of the special point in Lemma 3). Let
X ∗ (p) be the Markoff triples mod p; ξ any coordinate of a triple, ξ 6= 0, ± 23 .
For j 6= k and ξ, η
(20)

|Cj (ξ) ∩ Ck (η)| = 0, 1, 2.

To determine which it is, the intersection consists of all z’s such that
ξ 2 + η 2 + z 2 = 3ξηz,

(21)
which has a solution if

is a square in Fp .
In terms of Legendre’s symbol
(22)

9ξ 2 η 2 − 4(ξ 2 + η 2 )

|Cj (ξ) ∩ Ck (η)| = 1 +



9ξ 2 η 2 − 4(ξ 2 + η 2 )
p



.

So each Cj (ξ) meets p−1
Ck (η)’s. Define the incidence graph I(p) of X ∗ (p) to have
2
vertices Cj (ξ)’s with the number of edges between Cj (ξ) and Ck (η) being |Cj (ξ) ∩
Ck (η)|.
Proposition 6. For p large (p > 10) the incidence graph I(p) is connected and in
fact diam(I(p)) = 2.
Proof. Fix ξ1 , ξ2 and i, j, say i, j ∈ {1, 2}. We seek y ∈ Fp such that C3 (y)∩Ci (ξ1 ) 6= φ
and C3 (y) ∩ Cj (ξ2 ) 6= φ. This leads to solving the pair of equations:
(23)

(

(9ξ12 − 4)y 2 − λ2 = 4ξ12

(9ξ22 − 4)y 2 − µ2 = 4ξ22

for y, λ, µ ∈ Fp . In ξ12 = ξ22 then (23) reduces to the first equation (take λ = µ) and
since 9ξ12 − 4 6= 0 and ξ12 6= 0, it defines a conic section. Thus for p large it has a
solution and provides us with our y. If ξ12 6= ξ22 then (23) defines an irreducible curve
in A3 . Thus again for p large it has solutions over Fp providing us with our desired

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

7

y. It follows that the distance in I(p) between any two points is at most 2. On the
other hand, Ci (ξ) and Ci (η) are not joined if ξ 6= η nor is Ci (ξ) joined to half of the
Cj (η)’s for j 6= i. Hence diam(I(p)) = 2.

3. Endgame
3.1. Use of Weil’s bound. We begin with the following
Proposition 7. If x = (x1 , x2 , x3 ) is in X ∗ (p) and for some j ∈ {1, 2, 3} the order of
1
the induced rotation rot(xj ) is at least p 2 +δ (δ > 0 fixed) then x is joined to a point
y in X ∗ (p) one of whose induced rotations is of maximal order.
Proof. Consider first the case that x1 (say j = 1) is hyperbolic. In light of the
discussion in section 2, x = (x1 , x2 , x3 ) is connected to the points in X ∗ (p) of the
form
(24)

(x1 , α1 t + α2 t−1 , α3 t + α4 t−1 )

with t ∈ H, a cyclic subgroup of Fp ∗ . Here |H| | (p − 1); we set eH = p−1
. Our aim
|H|
∗
is to produce t’s in H for which there is a primitive root y ∈ Fp satisfying
(25)

α1 t + α2 t−1 = y + y −1.

Let P (H)(= Pα1 ,α2 (H)) denote the number of such solutions.
A subgroup K of Fp ∗ is determined by its order |K| which divides p−1; let dK =
Let fH (K) = fH (dK ) be the number of solutions to
(26)

p−1
.
|K|

α1 t + α2 t−1 = y + y −1 , t ∈ H , y ∈ K

(note that the traces of the matrices that we produce, namely the common values of
the left- and right-hand side of (26), are hit with multiplicity 2 in both t and y in our
counting). Clearly
(27)

fH (K) ≤ 2 min(|K|, |H|).
1

We can estimate fH (K), at least if |H| ≥ p 2 +δ , using Weil’s Riemann Hypothesis for
curves over finite fields. The map
ξ → ξ dK , η → η eH
sends solutions of
(28)

Cα1 ,α2 : α1 η eH + α2 η −eH = ξ dK + ξ −dK

8

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

to solutions of (26) and it is eH dK to 1. Hence if N(Cα1 ,α2 ) is the number of solutions
to (28) then
(29)

fH (K) =

N(Cα1 ,α2 )
.
eH dK

As we prove below (see Lemma 8) the curve Cα1 ,α2 i is absolutely irreducible. Since
its genus is O(eH dK ), applying Weil bound yields
√
(30)
N(Cα1 ,α2 ) = p + O( peH dK ).
Hence
(31)

fH (K) =

p
√
+ O( p).
eH dK

By inclusion/exclusion
(32)

X

P (H) =

µ(d)fH (Kd ),

d|(p−1)

where µ is the Mobius function. Hence
(33)


X µ(d)
X
1
1
√
ϕ(p − 1)
|H|
+ O( p) = |H|
+Oε (p 2 +ε ) = |H|
+Oε (p 2 +ε ).
P (H) =
µ(d)
d
d
p−1
d|(p−1)

d|(p−1)

Here ϕ is the Euler function and it satisfies ϕ(n) ≫ε n1−ε and hence from (33)
1
we deduce that P (H) > 1 under the assumption that |H| ≥ p 2 +δ . This proves
Proposition 7 in the hyperbolic case.
Now consider the case of x elliptic. Let D be a non-square element in Fp . Then
√
Fp2 = Fp [ D] and we can parametrize the subgroup H1 as follows
√
(34)
{(ξ + Dη)d1 ; ξ, η ∈ Fp ; ξ 2 − Dη 2 = 1},
where d1 =

p+1
.
|H1 |

The conic section C1 (x) is an ellipse which can be parametrized as
α2 − Dβ 2 = κ(x),

(35)
where κ(x) =
root in Fp ∗ .
Now
(36)

x2
.
x2 −4

We seek α which can be written as α = u + u−1 with u a primitive

(ξ +

√

√
D)n = gn (ξ) + hn (ξ) D,

where gn , hn are integral polynomials
(37)

gn (ξ) =

⌊n/2⌋ 

X
i=0


n
D i ξ n−2i ,
2i

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

(38)

hn (ξ) =

⌊n/2⌋ 

X
i=0

9


n
D i ξ n−2i+1 .
2i + 1

Let
(39)

gn (ξ, η) =

⌊n/2⌋ 

X
i=0

(40)

hn (ξ, η) =


n
D i ξ n−2i η 2i ,
2i


n
D i ξ n−2i+1 η 2i−1 .
2i + 1

⌊n/2⌋ 

X
i=0

Then we have

(41)

(ξ +

√

√
Dη)n = gn (ξ, η) + hn (ξ, η) D.

Now we seek to bound f (H1 , K) with K subgroup of Fp ∗ with d2 =

p−1
.
|K|

As in the

hyperbolic case this is given by M d(d11d,d2 2 ) where M(d1 , d2) now counts the number of
points on the following curve in Fp 3 :
(

(42)

ξ 2 − Dη 2 = 1

gd1 (ξ, η) = µd2 + µ−d2

This is a curve of genus O(d1 d2 ) and we can apply Weil bound and inclusionexclusion as in the hyperbolic case to produce the primitive u. This completes the
proof of Proposition 7.

Lemma 8. Suppose α1 α2 6= 1 mod p . Then the curve
α1 y e + α2 y −e = xd + x−d
is absolutely irreducible.
Proof. Consider
P (x, y) = α1 xd y 2e + α2 xd − x2d − y e ∈ Fp [X, Y ].
For d = 1 P is clearly irreducible. Let d > 1 and assume that P is not irreducible
P
and f (x, y) =
ajk xj y k ∈ Fp [X, Y ] an irreducible factor. Assume d ≥ e and u a d-th
root of unity. Since for 0 ≤ s ≤ d, P (x, y) = P (us x, y), also
X
fs (x, y) = f (us x, y) =
ajk usj xj y k

10

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

is an irreducible component of P . Thus either fs and fs′ are coprime or fs ∼ fs′ .
Since a0k 6= 0 for some k (otherwise x would be a factor of f (x, y)), it follows that
fs = fs′ if fs ∼ fs′ .
Case 1 The fs are not pairwise coprime.
The f (x, y) = fs (x, y) for some 0 < s < d, implying that usj = 1, i.e. sj ≡ 0(
mod d) if ajk 6= 0. It follows that d has a divisor d1 > 1 such that d1 |j if ajk 6= 0
and hence f (x, y) has form f (x, y) = g(xd1 , y). The polynomial g(x, y) is therefore a
factor of Q(x, y) = α1 xd2 y 2e + α2 xd2 − x2d2 y e − y e with d2 = dd1 and we lowered d.
Case 2 The fs (0 ≤ s ≤ d) are mutualy coprime. Define
P1 (x, y) =

d−1
Y

fs (x, y),

s=0

which divides P . Degree considerations show that
2d ≥ d degx f, 2e ≥ d degy f, 2d + e ≥ d deg f.
Case 2.1 degx f > 1, degy f > 1.
It follows that degx f = 2, degy f = 2, e = d, deg f = 3, and P (x, y) = P1 (x, y).
With u as above, ϕ(x, y) = f (x, uy) is an irreducible factor of P (x, y). Therefore for
some 0 ≤ s ≤ d
X
X
ajk uk xj y k ∼ fs (x, y) =
ajk usj xj y k .
ϕ(x, y) =
j,k≤2

Consequently, there is some 0 ≤ l ≤ d such that k − sj ≡ l( mod d) if ajk 6= 0. Since
Y
fs (x, y),
α1 xd y 2d + α2 xd − x2d y d − y d =
0≤s≤d

clearly a0,1 =
6 0, a1,0 6= 0, and therefore 1 ≡ l ≡ −s( mod d), i.e. k + j = 1( mod d)
if ajk 6= 0. Since deg f = 3, 2 ≡ 0( mod d), hence d = 2 and a1,1 = a2,0 = a0,2 = 0.
Thus
α1 x2 y 4 + ga1 x2 − x4 y 2 − y 2 ∼ (a21 x2 y + a12 xy 2 + a10 x + a01 y)(a21 x2 y − a12 xy 2 − a10 x + a01 y)
∼ y 2(a21 x2 + a01 )2 − x2 (a12 y 2 + a10 )2 .

Setting a0,1 = 1 gives −y 2 (a21 x2 +1)2 +x2 (a12 y 2 +a10 )2 and a221 = 1, a21 −a12 a10 = 0,
a212 = α1 , a210 = α2 . But this contradicts the assumption α1 α2 6= 1.
Case 2.2 degx f = 1 or degy f = 1.
Assume degy f = 1, say. Then there are coprime a(x), b(x) ∈ Fp [X] such that
P (x, a(x)
) = 0, that is
b(x)
α1 xd a(x)2e + α2 xd b(x)2e − x2d a(x)e b(x)e − a(x)e b(x)e = 0.

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

11

Since a(x), b(x) are coprime, it follows that a(x)e |xd , b(x)e |xd , hence a(x) or b(x) is
constant. If, say, b(x) is constant, previous equation implies xd |a(x)e , hence a(x)e =
γxd and
α1 γ 2 x2d + α2 b2e − γb2 x2d − γb2 = 0.

It follows that α1 γ = b2 , α2 b2 = γ, hence α1 α2 = 1, contradicting the assumptions
that α1 α2 6= 1.

3.2. The Cage. A point x = (x1 , x2 , x3 ) ∈ X ∗ (p) is called maximal if ord(rot(xj )) is
maximal for some j. Note that the condition that the order of rot(3xj ) be maximal
depends only on xj and not on the other coordinates of x (since it depends on the
order of λ, where λ + λ−1 = 3x1 in F∗p of F∗p2 ). We call ξ ∈ Fp maximal if it is of
maximal order.
By the cage we mean a set of maximal elements in X ∗ (p). We claim that the cage
is connected, that is to say if x̂ and ŷ are in the cage then x̂ is connected to ŷ. Let ξ
be the coordinate of maximal order of x̂ and η be the coordinate of maximal order of
ŷ, so that x̂ is connected to all points in Cj (ξ) and similarly ŷ is connected to all the
points in Ck (η).
Now according to Proposition 6, which when extended with and inclusion/exclusion
argument as in Proposition 7 gives a y of maximal order such that
P ∈ Cj (ξ) ∩ Cl (y);
Q ∈ Ck (η) ∩ Cl (y).
Since y is maximal, P and Q are connected by Γ and P is Γ- connected to x̂ and Q
to ŷ. Thus x̂ is Γ connected to ŷ.
Denote by C(p) the connected component of X ∗ (p) (under the Γ action) that contains the cage, then C(p) is our large component.
4. Middle Game

In the endgame (section 3) we connected any x ∈ X ∗ (p) of order (that is max(ord(rot(xj ))))
1
l ≥ p 2 +δ0 (δ0 > 0) to the cage in one step. In this section we allow any number of
moves to do the connecting. In particular any x of order at least pε is shown to be
in the giant component. As in section 3 the y’s which are joined to a given x whose
order is l1 via the corresponding rotation and which have orders l2 (here l1 and l2
divide p − 1 or p + 1) correspond to solutions of an equation (with σ ∈ Fp , σ 6= 1):

1
σ

= h2 + , σ 6= 1
h1 +
h1
h2
(43)

with h1 ∈ H1 , h2 ∈ H2 with H1 , H2 subgroups of Fp ∗ or Fp2 ∗ .

12

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

In (43) we have |H1 | = l1 , |H2 | = l2 .
If we have an upper bound on the number of solutions to (43) so that on summing
over all l2 ≤ l1 with l2 dividing p − 1 or p + 1, yields a quantitiy which is less than l1 ,
then there is at least one h1 for which the corresponding y will have order bigger than
l1 . We then repeat this procedure replacing x by this y and so on, until the order of
1
the element is at least p 2 +δ0 . At that point we are in the endgame and can finish.
The key therefore is a suitable upper bound to the number of solutions to (43).
Our original treatment used Stepanov’s technique of auxiliary polynomials in his
elementary proof of this Riemann Hypothesis for curves. This yields explicit and
reasonably sharp estimates which are ample for our application. We carry this out in
the Appendix partly to illustrate the flexibility of this method.
Subsequently the recent powerful technique for estimating from above the g.c.d. of
(u − 1, v − 1), of Corvaja and Zannier [CS13] yields sharper bounds. This is relevant
for the purpose of giving efffective bounds on p after which Theorem 1 takes effect.
The precise upper bound to (43) established by [CS13] is
n
|H1 |.|H2 | o
20 max (|H1|.|H2 |)1/3 ,
.
p
The third treatment, and the one which we develop in this section, while special
to (43), is robust in that the upper bound requires little further structure and it
is suitable for generalisation for more general moduli as demonstrated in Paper II.
It is based on the following projective Szemeredi-Trotter theorem (Proposition 2 in
[Bou12]).

Theorem 9. Let Φ : Fp → Mat2 (Fp ) such that det Φ does not vanish identically and
ImΦ ∩ PGL2 (Fp ) is not contained in a set of the form F∗p · gH for some g ∈ SL2 (Fp )
and H a proper subgroup of SL2 (Fp ). Then the following holds.
Given ε > 0, r > 1, there is δ > 0 such that if A ⊂ P 1 (Fp ) and L ⊂ Fp satisfy
(44)

1 ≪ |A| < p1−ε

(45)

log |A| < r log |L|.

Then
(46)
where for g =

|{(x, y, t) ∈ A × A × L; y = τΦ(t) (x)}| < |A|1−δ |L|,
!
a b
ax+b
.
, τg (x) = cx+d
c d

Using Theorem 9 we prove the following:

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

13

Proposition 10. Given δ > 0 there is τ < 1 and Cτ depending on δ such that if
pδ < |H1 | < p1−δ then the number of solutions to (43) is at most Cτ |H1 |τ .
Proof. For h ∈ H, a subgroup of F∗p or F∗p2 , denote by h̃ = h + h−1 . Similarly we
e = {h̃ | h ∈ H}.
denote by H
Suppose that (43) has T solutions. Then


σ
=u 

h1
σ

= v,
h1 t +
h1 t

h1 +
(47)

f2 , has at least T 2 solutions.
where h1 , t ∈ H1 and u, v ∈ H
Elimination of h1 in (47) yields
(48)



1 2
1
uv + σ t −
=0
u2 + v 2 − t +
t
t

f2 × H
f2 .
which, by assumption, has at least T 2 solutions in (t, u, v) ∈ H1 × H
Next, let u = f˜1 , v = f˜2 with f1 and f2 ∈ H2 and define the following elements
f2 :
x, y ∈ H
1
^
,
x = (f
1 f2 ) = f1 f2 +
f1 f2
f1 f2
−1
y = (f^
+ .
1 f2 ) =
f2 f1
Thus uv = x + y, u2 + v 2 = xy + 4 and equation (48) gets transformed into

(49)

xy − t̃(x + y) + σ(t̃)2 + 4(1 − σ) = 0.

Denoting
(50)

α = t̃ and β = σ(t̃)2 + 4(1 − σ)

we obtain
(51)

y=

with
g=

αx − β
= τg (x)
x−α
α β
1 −α

!

= g(t̃)

and τg the Mobius transformation.
e2 × H
e2 × H
e1.
Equation (51) has at least T 2 solutions in (x, y, t̃) ∈ H

14

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

We apply Theorem 9 taking Φ(t)
(52)

Φ(t) =

t −σt2 − 4(1 − σ)
1
−t

!

e2, L = H
e1.
and A = H
We verify the assumption on Φ. Since σ 6= 1, det Φ(t) = (1 − σ)(4 − t2 ) does not
vanish identically. It remains to show that
n
det Φ(s)
Φ(s)−1 Φ(t)
; s, t ∈ Fp }
det Φ(t)

is not contained in a proper subgroup H of SL2 (p).
By (52)
!
!
2
2
−s
σs
+
4(1
−
σ)
t
−σt
−
4(1
−
σ)
Φ(s)−1 Φ(t) =
−1
s
1
−t
=

−st + σs2 + 4(1 − σ)
s−t

(s − t)(4(1 − σ) − σst)
−st + σt2 + 4(1 − σ))

!

Taking
s = σt +

4(1 − σ)
t

gives
 σ(1 + σ)t +
(53) (1 − σ) − t
t
1
4

4(1−σ)
t

−σ 2 t2 + 4(1 − σ)2
0

!

= (1 − σ)

4
t


− t gt .

As the proper subgroups of SL(2, Fp ) have trivial second commutator [Suz82], it
suffices to show that
(54)

)(gt2 gt1 gt−1
gt−1
)(gt4 gt3 gt−1
gt−1
)
gt−1
)(gt3 gt4 gt−1
gt−1
(gt1 gt2 gt−1
4
3
1
2
3
4
2
1

is not identically one for t1 , t2 , t3 , t4 ∈ F∗p . If this were the case, the same would be
true for t1 , t2 , t3 , t4 taken in an extension field of Fp so as to make
t2 =

(55)

4(1 − σ)2 − ε
(ε = ±1)
σ2

solvable.
Taking t = ±κ satisfying (55), we get
2 −ε

(56)

g±κ =

± σκ [(1 + σ) 4(1−σ)
σ2
1

!
+ 4(1 − σ)] ε
.
0

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

15

We choose ε = ±1 as to ensure that
(1 + σ)(4(1 − σ)2 − ε) + 4σ 2 (1 − σ) 6= 0
and obtain matrices
(57)

g± =

±η ε
1 0

!

that clearly generate SL2 (p).
Consequently, Theorem 9 is applicable, yielding the bound T 2 ≪ |H2|1−τ |H1 |.



5. Opening
The analysis of the previous sections shows that we can connect x ∈ X ∗ (p) whose
order is at least pε (or smaller if the divisors of p2 − 1 are not too numerous) to the
cage. To deal with all x’s and in particular ones whose orders are uniformly bounded
(indepndent of p) we lift to characteristic zero. In this connection we observe first
that if the action of Γ on X ∗ (Q̄) has a finite orbit F then the strong approximation
conjecture cannot hold. To see this consider more generally any finite orbit F of the
Γ action on A3 (C). The coordinate of any ξ in such an F must lie in a cyclotomic
field Ln = Q(ζn ), where ζn is a primitive n-th root of 1. For if ξ = (ξ1 , ξ2, ξ3 ) then
ord(rot(ξj )) must be finite and hence
3ξj = tj + t−1
j

(58)

with tj a root of unity. If n is the least common multiple of all the orders of all the
tj ’s corresponding to the ξ’s in F then ξj ∈ Ln and hence F ⊂ A3 (Ln ). In fact the ξj ’s
(3)
are all integral except possibly for denominators powers of 3, so that F ⊂ A3 (OLn )
(3)
where OLn is the ring of S-integers in Ln , with S consisting of the primes dividing
3. If p is a rational prime (p 6= 3) which splits completely in Ln and P is a prime of
(3)
(3)
Ln with P |(p) then OLn /P ∼
= Z/pZ). The Γ action of A3 (OLn ) factors through
= Fp (∼
the reduction π mod P
(3)

A3 (OLn )

π
y
(3)

Γ

−−−→
Γ̄

(3)

A3 (OLn )

π
y
(3)

A3 (OL /P ) −−−→ A3 (OL /P )
and hence
(59)

F̄ = π(F ) ⊂ A3 (Fp ), is Γ̄ − invariant.

16

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

Since Γ preserves the level sets Xk :
x21 + x22 + x23 − 3x1 x2 x3 = k,

(60)

(3)

any such F is contained in Xk (OL ) for a suitable k. Thus for any such F , there is a
positive density of p’s which split completely in Ln , and hence for which F̄ ⊂ Xk (Fp )
is a fixed size Γ̄ -orbit (|F̄ | ≤ |F |). That is, the finite Γ-orbits in A3 (Q̄) must be part
of any description of the Γ̄-orbits on A3 (Fp ), for p large.
In our setting of this paper, k = 0 and we have (we thank E. Bombieri for this
simple proof)
Proposition 11. X ∗ (Q̄) has no finite Γ-orbit.
Proof. As in the discussion above, if F is such an orbit and ξ ∈ F then the ξj satisfy
(58) with tj an lj -th root of one. The Markoff equation for t1 , t2 , t3 becomes
(61)

−1
−1
−1
−1 2
2
−1 2
(t1 + t−1
1 ) + (t2 + t2 ) + (t3 + t3 ) − (t1 + t1 )(t2 + t2 )(t3 + t3 ) = 0.

Now (61) has no solutions with |tj | = 1 (let alone being roots of unity) except for
tj = ±i, j = 1, 2, 3. To see this note that if
−1
−1
¯
a = t1 + t−1
1 (= t1 + t1 ), b = t2 + t2 , c = t3 + t3

then a, b, c, lie in [−2, 2] and by the inequality of the geometric and arithmetic means
2
|a|3 + |b|3 + |c|3
≤ (a2 + b2 + c2 ).
(62)
0 ≤ a + b + c = |abc| ≤
3
3
Hence the only solutions to (61) correspond to a = b = c = 0 or tj = ±i. In terms
of ξj this gives ξ = (0, 0, 0), which is the only invariant set for the action of Γ on
X(Q̄).

We remark that in the context of the general surfaces that are studied in Paper III,
for example the surfaces Xk in (60) with k 6= 0, there can be a continuum of solutions
to the analogue of equation (61) with |tj | = 1. However the solutions with tj a root of
unity (with unspecified order) are still restricted to a finite number of nondegenerate
solutions. This follows from Lang’s Gm conjecture, see [Lau83] and [SA94] for proofs
which give the solutions effectively. In various special cases these finite Q̄ orbits for
the Γ-action correspond to the determination of the algebraic Painleve VI solutions
([DM00], [LT14]); we leave the details to paper III .
Returning to the Markoff surface X, let ξ = (ξ1 , ξ2 , ξ3) ∈ X ∗ (p) with ord(rot(ξj )) =
lj for j = 1, 2, 3. Let n = lcm(l1 , l2 , l3 ) and Ln = Q(ζn ) and let ζl1 , ζl2 , ζl3 be primitive
roots of one respectively. Let
2

2

2

(63) η = (ζl1 +ζl−1
)2 +(ζl2 +ζl−1
)2 +(ζl3 +ζl−1
)2 −(ζl1 +ζl−1
)(ζl2 +ζl−1
)(ζl3 +ζl−1
) ∈ OLn .
2
2
3
2
2
3

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

17

According to Proposition 11 unless l1 = l2 = l3 = 2 (i.e. ζlj = ±i), η 6= 0.
Now |η| ≤ 20 and hence
(64)

Norm(η) ≤ 20φ(n) ≤ 20n .

If P is a prime in OLn and η ∈ P , then P |(η) and hence
(65)

N(P ) ≤ Norm(η) ≤ 20n .

Put differently, if
log20 N(P ) > n
then
(66)

η 6= 0( mod P ).

For our point ξ in X ∗ (p), 3ξj = λj + λ−1
j with λj in Fp or Fp2 and λj an lj -th root
of 1, and (l1 , l2 , l3 ) 6= (2, 2, 2) since ξ 6= (0, 0, 0). If all the λj ’s are in Fp then Q(ζn )
splits completely at p, that is there is a prime P dividing (p) such that
OLn /P ∼
= Fp , N(P ) = p
and π(ζlj ) = λj in OLn /P and η ≡ 0( mod P ). Hence from (66) we conclude that
(67)

log20 p ≤ n.

If the field generated by λj ’s (over Fp ) is Fp2 then there is a prime P of OLn dividing
(p) such that
OL /P ∼
= Fp2 , N(P ) = p2
n

and π(ζlj ) = λj in OLn /P and η ≡ 0( mod P ). Hence again from (66) we conclude
that
(68)

2 log20 p ≤ n.

Hence in either case n ≥ log20 p where n = lcm(l1 , l2 , l3 ), and hence
(69)

1

max(l1 , l2 , l3 ) ≥ (log20 p) 3 .

We have proven
Proposition 12. Let ξ ∈ X ∗ (p) have maximal order l, i.e. max(l1 , l2 , l3 ) = l with
1
lj = ord(rot(ξj )), then l ≥ (log20 p) 3 . In particular, any component F of X ∗ (p)
satisfies
1

|F | ≥ (log20 p) 3 .

18

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

6. Proofs of Theorems 1 and 2
Proposition 12 establishes the second part of Theorem 1 and combined with the
analysis in sections 3 and 4 yields a proof of the strong approximation conjecture if
p2 − 1 is not very smooth. For example, the strong approximation conjecture is true
for X ∗ (p) if the prime p satisfies
(70)

X

2

d 3 < y; for any y.

1

(log p) 3 ≤d≤y
d|(p2 −1)

We do this by using the arguments and results in [Cha13] and [CKSZ14] concerning
points (x, y) on irreducible curves over Fp for which ord(x) + ord(y) is small (here
ord(x) is the order of x in F∗p ).
Theorem 13. Fix d ∈ Z+ and δ > 0. There is an ε > 0, ε = ε(d, δ), such that for
all primes p ≤ z (z sufficiently large) with the exception of at most z δ of them, the
following property holds. Let f (x, y) ∈ Fp [x, y] be of degree at most d and not divisible
by any polynomial of the form ρxα y β − 1 or ρy β − xα for any ρ ∈ F¯p and integers α
and β. Then all solutions (x, y) ∈ (F¯p × F¯p )∗ of f (x, y) = 0 satisfy
(71)

ord(x) + ord(y) ≥ pε

except for at most 11d3 + d of them.

Proof. Theorem 1.2 in [CKSZ14] establishes what we want except that pε in (71) is
replaced by the stronger bound pα(d) , with
α(d) =

2
,
89d2 + 3d + 14

while the exceptional set of primes is of zero density. For our purpose the exponent
in (71) is allowed to be small and in exchange we want the exceptional set to be much
smaller. To this end we follow verbatum the discussion in Section 4 of [CKSZ14]. For
d fixed and T a large parameter they show that there is a U = U(d, T ) which has at
1
most O(T α(d) ) prime factors (their log T in the denominator is irrelevant for us) with
the property: If p does not divide U and f as in Theorem 13 and f (x, y) = 0 in Fp ,
then
(72)

ord(x) + ord(y) ≥ T

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

19

except for at most 11d3 + d such (x, y) in Fp ∗ × Fp ∗ . For our given δ > 0 and large
parameter z choose T to be
T = z δα(d) .

(73)

Then the number of primes p with p|U is O(z δ ) , and if p does not divide U then
Theorem 13 holds with (72) and (73), that is with ε = δα(d).

To prove Theorem 2 we apply Theorem 13 to the curves fσ (x, y) given by equation
x+

1
σ
=y+
x
y

1

with σ 6= 1. If (log20 p) 3 > 1000, then according to Proposition 12, for any ξ ∈ X ∗ (p)
we have ord(rot(ξj0 )) is at least 1000 for j0 one of the j’s in {1, 2, 3}. Hence if p is
not in the exceptional set in Theorem 13 with d = 4, then in the typical equation
x + σx = y + y1 corresponding to the orders of the rotations in the rot(ξj0 ) orbit, there
is (x, y) which is not one of the exceptional 11d3 + d < 1000 possible points. For such
(x, y) the induced rotation has order at least pε and hence ξ is joined to the cage by
the middle game.
Our methods fall short of dealing with all p, specifically for those rare p’s for which
p −1 is very smooth. The following hypothesis which is a strong variant of conjectures
of M.C. Chang and B. Poonen [Cha13, Vol10] would suffice to deal with all large p’s.
2

Hypothesis: Given d ∈ N, there is δ > 0 and K = K(d) such that for p large
and f (x, y) absolutely irreducible over Fp and of degree d and f (x, y) = 0 is not a
translate of a subtorus of (F̄∗p )2 , the set of (x, y) ∈ (F∗p )2 for which f (x, y) = 0 and
max(ordx, ordy) ≤ pδ , is at most K.
Appendix A.
Stepanov’s auxiliary polynomial method [Ste69] for bounding the number of solutons to equations like (43) is quite flexible. We demonstrate this for some special cases
(the general case can be handled similarly). The proposition below is an extension of
the approach and bounds in [HK00] (where S(x) = x, T (x) = 1 − x and t1 = t2 ).
In what follows S(x) and T (x) are rational functions in Fp (x) of total degree d1
and d2 respectively and with disjoint divisors; e = d1 + d2 is fixed.
Proposition 14. For p a large prime, t1 , t2 dividing p − 1, t1 ≥ t2 , let
Y = {y ∈ Fp : S(y)t1 = T (y)t2 = 1}.

20

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

1

Then if t1 ≪e p1− 2e ,

−

1

|Y | ≪e min{t2 , t1 t2 4e }.
Remarks:
(1) The trivial bound is O(t2) so the Proposition gives an improvement (power
4e

saving) if t2 ≥ t14e−1 .
(2) If h(ξ, η) = 0 is a plane curve of genus 0 over Fp , then the Proposition gives
an upper bound on the number of solutions with ξ t1 = η t2 = 1 (cf. [CS13]).
Applying Proposition 14 with t1 = t2 , S(y) = y, T (y) =

ay+b
cy+d

yields

3

Corollary 15. For p large prime, t|(p − 1), t ≤ p 4 and Ut = {y ∈ Fp : y t = 1} the
t-th roots of 1,
3

|σ(Ut ) ∩ Ut | ≪ t 4
for σ ∈ PGL2 (Fp ), σ 6= 1.
3

Corollary 16. For t|(p − 1), t ≤ p 4 , b ∈ Fp , b 6= 1,
3

|{w, ρ ∈ Fp : w + w −1 = ρ + bρ−1 , w t = ρt = 1}| ≪ t 4 .
Proof. Put ρw = ξ, wρ = η, then ξ t = η t = 1 and each such solution with ξ = bη−1
η−1
corresponds to at most two solutions (w, ρ) above. Applying Corollary 15 yields
Corollary 16.

Proof of Proposition 14: First we need a generalization of Proposition 3.2 in
[VS12] where their common t is replaced by t0 , t1 , . . . , tn . The result is the following
Lemma, whose proof is the same
Lemma 17. Let t0 , t1 , . . . , tn , as well as B and J be integers, p a large prime, and
α1 , . . . , αn distinct elements in Fp ∗ . Assume that
1
min(t0 , . . . , tn ) ≥ (n − 1)B 2n + JB
2
and that
p ≥ (2nB + 2) max(t0 , t1 , . . . , tn ).
Then
xai xt0 b0,i (x − α1 )t1 b1,i . . . (x − αn )tn bn,i
with aj ≤ J and b0,i , . . . bn,i ≤ B are linearly independent in Fp [x].

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

21

Let α1 , . . . , αk ∈ Fp be distinct and ν1 , ν2 , . . . νk ∈ Z; set
Rν (x) = (x − α1 )ν1 . . . (x − αk )νk .
For m ≥ 1,

X m dj1
dj k
dm
ν1
[R
(x)]
=
[(x
−
α
)
]
.
.
.
[(x − α1 )νk ] =
ν
1
j1
jk
dxm
dx
dx
j
j1 +...jk =m
X
Bm,j (x − α1 )ν1 −j1 . . . (x − αk )νk −jk .
j1 +j2 +...jk =m

Hence
dm
(74)
[(x − α1 )(x − α2 ) . . . (x − αk ]
Rν (x) = Rν (x)Pm,ν (x),
dxm
where Pm,ν is a polynomial of degree at most km.
Stepanov’s polynomial method is based on constructing a polynomial which vanishes to high order on Y . Let λa,b1 ,b2 be in Fp with 0 ≤ a ≤ J and 0 ≤ bj ≤ B and
form
X
(75)
φ(x) =
λa,b1 ,b2 xa (S(x))t1 b1 (T (x))t2 b2 .
m

Write S(x), T (x) in the form (we assume that both factor into linear factors Fp [x]):
A(x − α1 ) . . . (x − αt )
,
(x − β1 ) . . . (x − βτ )
B(x − γ1 ) . . . (x − γµ )
T (x) =
.
(x − δ1 ) . . . (x − δν )

S(x) =
(76)

For simplicity we assume that S(x) and T (x) are square-free and we are assuming
that the α, β, γ, δ’s are all distinct. The constants A and B can be absorbed into the
λ’s, so without loss of generality we can take A = B = 1. For m ≥ 0
(77)
[(x − α1 ) . . . (x − αt )(x − β1 ) . . . (x − βτ ) . . . (x − δν )]m


dm  a
t1 b1
t2 b2
x
(S(x))
(T
(x))
=
dxm
xa S(x)t1 b1 T (x)t2 b2 Pm,a,b1 ,b2 (x)

with Pm of degree at most em. Hence for x = y ∈ Y and m ≤ M
(78)
X
X

dm
dm  a
t1 b1
t2 b2
λa,b1 ,b2 y a Pm,a,b1 ,b2 (y),
φ(x)|
=
λ
x
S(x)
T
(x)
=
x=y
a,b1 ,b2
x=y
dxm
dxm
a,b ,b
1

2

by the definition of Y . We can make (78) equal to 0 for all y in Y by noting that
y a Pm (y) is a polynomial of degree J + em. So (78) can be made 0 with not all of the

22

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

λa,b1 ,b2 ’s equal to 0 and for all m ≤ M as long as
(J + eM)M < B 2 J.

(79)

Assuming that this is satisfied, we have φ(x) which is not identically zero and has
degree (as a rational function) at most J + eBt1 .
Hence if φ(x) is not identically zero, then its order of vanishing on Y is at least M
and hence
M|Y | ≤ J + eBt1
or
(80)

|Y | ≤

J + eBt1
.
M

We now check that under suitable constraints on the sizes of parameters, φ(x) does
not vanish identically. We have
φ(x) =
consequently

X

λa,b1 ,b2 xa

(x − α1 )t1 b1 . . . (x − αt )t1 b1 (x − γ1 )t2 b2 . . . (x − γµ )t2 b2
,
(x − β1 )t1 b1 . . . (x − βτ )t1 b1 (x − δ1 )t2 b2 . . . (x − δν )t2 b2

(x − β1 )B . . . (x − βτ )B (x − δ1 )B . . . (x − δν )B φ(x) =
X
λa,b1 ,b2 xa (x − α1 )t1 b1 . . . (x − αt )t1 b1 (x − β1 )(B−b1 )t1 . . . (x − βτ )(B−b1 )t1 ·
· (x − γ1 )t2 b2 . . . (x − γµ )t2 b2 (x − δ1 )(B−b2 )t2 . . . (x − δν )(B−b2 )t2 .

Now the monomials appearing in the last expression are linearly independent over
Fp [x] according to Lemma 17 as long as
(81)

p ≥ (2eB + 2)t1

1
t2 ≥ eB 2e + JB e .
2

Thus, if (81) and (79) hold, so does (80).
Choose J ≤ M and

M 2 = Ce B 2 J.

Then
M=

p

√
Ce B J
1

1

and M ≥ J iff J ≪e B 2 . Now choose B + t12e and if t1 ≪ p1− 2e then (81) and (79)
hold and
−

1

|Y | ≪e t1 t2 4e .
This completes the proof of Proposition 14.

MARKOFF SURFACES AND STRONG APPROXIMATION: 1

23

Acknowledgements: While working on this paper, the authors were supported, in
part, by the following NSF DMS awards: 1301619 (Bourgain), 1603715 (Gamburd),
1302952 (Sarnak).
References
[BS02]

F. Beukers and C. J. Smyth, Cyclotomic points on curves, Number theory for the

[Bom07]

millenium (Urbana, Illinois, 2000), I, A.K. Peters, (2002), 67-85.
E. Bombieri, Continued fractions and the Markoff tree, Expo. Math. 25 (2007), no

[Bou12]

3, 187–213.
J. Bourgain, A modular Szemeredi-Trotter theorem for hyperbolas, C.R. Acad. Sci.
Paris Ser 1, 350 (2012), 793–796.

[BG08]

J. Bourgain and A. Gamburd, Uniform expansion bounds for Cayley graphs of
SL2 (Fp ), Ann. Math. 167 (2008), 625–642.

[BGS10]

J. Bourgain, A. Gamburd and P. Sarnak, Affine linear sieve, expanders and sum
product, Invent. Math. 179 (2010), 559–644.

[BGS16]

J. Bourgain, A. Gamburd, P. Sarnak, Markoff triples and strong approximation, C.
R. Math. Acad. Sci. Paris 354 (2016), no. 2, 131-135.

[Cas78]
[Cha13]

J. W. S. Cassels, Rational Quadratic Forms, Academic Press, 1978.
Chang, Mei-Chu Elements of large order in prime finite fields. Bull. Aust. Math.

[CKSZ14]

Soc. 88 (2013) 169-176.
M-C. Chang, B. Kerr, I. Shparlinski and U. Zannier, Elements of large orders on

[CS13]

varieties over prime finite fields, J. Theor. Nombres Bordeaux 26 (2014) 579-594.
P. Corvaja, U. Zannier, Greatest common divisors of u − 1, v − 1 in positive charac-

teristic and rational points on curves over finite fields, J. Eur. Math. Soc. (JEMS)
15 (2013) 1927-1942.
[DKS13]

C. D’Andrea, T. Krick and M. Sombra, Heights of varieties in multiprojective spaces

[DM00]

and arithmetic Nullstellensatz, Annales Sci. de l’ENS, 46, (2013),549-627.
B. Dubrovin, M. Mazzocco, Monodromy of certain Painleve-VI transcendents and

[Fro13]

reflection groups, Invent. Math. 141 (2000) 55-147.
G. Frobenius, Über die Markoffschen Zahlen, Akad. Wiss. Berlin, (1913), 458–487.

[Gol03]

W. Goldman, The modular group action on real SL(2)-characters of a one-holed
torus, Geom. and Top. Vol. 7 (2003), 443–486.

[HK00]

R. Heath-Brown and S. Konyagin, New bounds for Gauss sums derived from k-th
powers and for Heilbronn’s exponential sum, QUAR. J MATH (2000), 221–235.

[Lau83]
[Mar79]

M. Laurent, Exponential diophantine equations, CR Acad Sc. 296 (1983), 945–947.
A. Markoff, Sur les formes quadratiques binaires indéfinies, Math. Ann. 15 (1879)

[Mar80]

381–409.
A. Markoff, Sur les formes quadratiques binaires indéfinies, Math. Ann. 17 (1880)

[LT14]

379–399.
O. Lisovyy and Y. Tykhyy, Algebraic solutions of the sixth Painleve equation,
Journal of Geometry and Physics, 85 (2014) 124-163.

24

JEAN BOURGAIN, ALEXANDER GAMBURD, AND PETER SARNAK

[MW13]

D. McCullough and M. Wanderley, Nielsen equivalence of generating pairs in

[SA94]

SL(2, q), Glasgow Math. J. 55 (2013), 481–509.
P. Sarnak and S. Adams, Betti numbers of congruence groups, with an appendix

[Sch04]

by Z. Rudnick, Israel J. Math, 88, 1994, 31-72.
Schmidt, W. M Equations over finite fields: an Elementary approach, Kendrick

[Ste69]

Press 2004.
S.A. Stepanov, The number of points of a hyperelliptic curve over a prime field,

[Suz82]

MATH USSR-IZV 3:5 (1969), 1103–1114.
M. Suzuki, Group Theory I, Springer-Verlag, Berlin-Heidelberg-New York, 1982.

[Vol10]

Voloch, Elements of high order on finite fields from elliptic curves, Bull. Aust. Math.
Soc. 81 (2010), 425-429.

[VS12]
[Wei41]

Vyugin, I. V., Shkredov, I. D., Sb. Math. 203(2012), 844-863.
A. Weil, On the Riemann Hypothesis in function fields, Proc. Nat. Acad. Sci. USA
27 (1941), 345–347.

IAS
E-mail address: bourgain@math.ias.edu
The Graduate Center, CUNY
E-mail address: agamburd@gc.cuny.edu
IAS and Princeton University
E-mail address: sarnak@math.princeton.edu

