THE ACTION OF THE MODULAR GROUP ON CHARACTERS OF SL(2, q)-REPRESENTATIONS OF F_{2}

DARRYL MCCULLOUGH AND MARCUS WANDERLEY

Abstract. We present a general conjectural picture of Nielsen equivalence classes and T -systems of generating pairs for the groups SL(2, q) and PSL(2, q), and the closely related Markoff equivalence classes of triples of elements of the coefficient field 𝔽_{q}, viewed as characters of the F_{2}-representations corresponding to the generating pairs. The trace of the commutator of the elements of a generating pair is an invariant of its Nielsen class, and the orbit of this trace under the action of Aut(𝔽_{q}) on 𝔽_{q} is an invariant of the T -system of the pair. We show that as long as q ≥ 13, these invariants assume all field values except for 2, which is never the trace of a generating pair. This and other results verify parts of the general conjectural picture. We also describe computer calculations that have verified the conjectures for all q ≤ 101. Finally, we prove that all the conjectures hold for one highly restricted but possibly infinite class of values of q.

Introduction

In this paper we will study Nielsen equivalence and T -equivalence of generating pairs of SL(2, q) (and PSL(2, q)), and the closely related action of the extended modular group PGL(2, ℤ) on the characters of SL(2, q)- representations of F_{2}, the free group on two generators. In some respects, the latter is analogous to W. Goldman’s [10] study of the corresponding action on characters of SL(2, ℝ)-representations of F_{2}. We will give a general conjectural picture of these related structures. Besides obtaining general information about the conjectures, and proving portions of them for various cases, we will prove the full set of conjectures for a very restricted (but conceivably infinite) class of examples. Also, we will describe our computer calculations that have verified the conjectures for all q ≤ 101.

Part of our work extends a result of R. Guralnick and I. Pak [11], which states that as primes p → ∞, the number of T -systems of generating pairs of SL(2, p) goes to ∞. We will show that for q = p^{s} ≥ 13, the number of

Date: February 26, 2006. 1991 Mathematics Subject Classification. Primary 20G40; Secondary 20H10 57M60. Key words and phrases. free, group, special linear, Nielsen equivalence, T-system,

Markoff, Higman invariant, modular group, representation, character, GAP. The first author was supported in part by NSF grant DMS-0102463.

T -systems of SL(2, q) is bounded below by Ψ_{q} − 1, where

Ψ_{q} = \frac{1}{s} ∑_{r|s}φ(s/r) p^{r} .

This is just the number of orbits of the Aut(𝔽_{q})-action on the field of q elements 𝔽_{q}. Among our conjectures is that for q ≥ 13, the number of T -systems of generating pairs of SL(2, q) is exactly Ψ_{q} − 1.

Information about Nielsen equivalence classes and T -systems has applications in algebra and topology. For example, they classify two kinds of group actions on low-dimensional manifolds, which happen to be our original motivation. The first kind are free actions on 3-dimensional handlebodies, for which we refer the reader to [18] and [4]. The second kind we call almost free actions on 2-manifolds. These are actions that are not free, but are close to being free in the sense that the group acts transitively on the union of the fixed-point sets of its nontrivial elements. Since we are not aware of any treatment of this class of actions in the literature, we include an exposition of their basic theory, which shows how they can be classified by means of Nielsen equivalence and T -systems.

We have already mentioned that our work is somewhat analogous to W. Goldman’s work on characters of F_{2}-representations into SL(2, ℝ) [10]. We should also note a connection to some work B. Bowditch [2, 3], who obtained striking results on Markoff equivalence for real and complex triples. Our study of Markoff equivalence in 𝔽_{q}^{3} is a rudimentary extension of this viewpoint into the finite field setting.

The authors gratefully acknowledge the support of many sources in the course of this work. Travel of the first author was supported by National Science Foundation grant DMS-0102463, by the University of Oklahoma College of Arts and Sciences, and by the University of Oklahoma Office of Research Administration. The work of both authors was supported by the Universidade Federal de Pernambuco Summer in Recife program. We also owe a special thanks to Gareth Jones, who provided us with an elegant proof of the formula for Ψ_{q}.

1. A conjectural picture of F_{2}-representations in SL(2, q)

In this section we first present the conjectural picture of Nielsen equivalence in SL(2, q) and of the action of the modular group on the (essential) characters. The unsupported assertions in the discussion will be verified or referenced in later parts of the paper. As we present the conjectures, we mention several of our results and explain which parts of the overall picture they verify or support. Finally, we outline the sections of the paper.

CHARACTERS OF SL(2, q)-REPRESENTATIONS OF F_{2} 3

Fixing a basis of F_{2}, we identify the set Hom(F_{2}, G) of G-representations of F_{2} with the set of pairs of elements of the group G. We call such a representation essential when it is surjective, that is, when the corresponding pair of elements generates G; thus we may identify the set of essential representations with the set G_{2}(G) of generating pairs of G. The group Aut(F_{2}) acts on the left on the set of essential representations, by ϕ · ρ = ρ ∘ ϕ^{−1}. Its orbits are called Nielsen equivalence classes, or just Nielsen classes. We denote by N the set of Nielsen classes of a group under discussion.

For an element (A, B) ∈ G_{2}(G), the union of the conjugacy classes of the commutator [A, B] = ABA^{−1}B^{−1} and its inverse is a well-known invariant of the Nielsen class of (A, B), called the Higman invariant. Since [A, B] and [B, A] are usually conjugate for elements of SL(2, q), our Higman invariants will usually consist of a single conjugacy class.

We now specialize to the case when G is SL(2, q). The field with q elements will be denoted by 𝔽_{q}, and throughout this paper p will denote the prime such that q = p^{s}. As will be discussed in section 14 below, each of the conjectures that we will state here implies a corresponding assertion for the case of PSL(2, q), while the corresponding assertion implies a weak form of the conjecture.

Five conjectures called A, B, B′, C, and W will be stated here. For easy reference, we collect here the logical relationships that either are immediate or are ensured by the results in this paper:

A ⇔ B
B ⇔ (B′ ∧ C)
B ⇒ W

We will see below that Conjecture B′ is known in characteristic 2, so in that case Conjectures A, B, and C are equivalent, and imply Conjecture W.

Our first conjecture says that the Higman invariant is a complete invariant of Nielsen equivalence:

Conjecture A (Higman invariant classifies Nielsen classes). Two generating pairs (A, B) and (A′, B′) of SL(2, q) are Nielsen equivalent if and only if [A, B] is conjugate to [A′, B′] or to [B′, A′].

The conjugacy classes of SL(2, q) are very well-known, and corollary 6.2 below shows that for q ≥ 13, every conjugacy class except {−I} and those of trace 2 occurs as a Higman invariant. Thus Conjecture A would give a complete classification of the Nielsen classes.

The Higman invariant shows that the trace of the commutator [A, B] is a well-defined invariant of the Nielsen class of (A, B), which we call the trace invariant. The conjectural picture is that the trace invariant tr: N → 𝔽_{q} is very close to a bijection. Indeed, theorem 5.1 below implies that tr has image 𝔽_{q}−{2} for all q ≥ 13 (it is an easy fact that tr([A, B]) can never equal 2 for a generating pair), and our second conjecture completes the picture from this viewpoint:

Conjecture B (Trace invariant is nearly injective). The trace invariant tr: N → 𝔽_{q} − {2} is injective except that it is two-to-one on the preimage of −2 when q ≡ 1 mod 4.

As we will detail in section 6, well-known facts about conjugacy in SL(2, q) show that Conjectures A and B are equivalent.

We turn now to characters. Regarding an SL(2, q)-representation of F_{2} as a pair of elements (A, B), we define the character of the representation to be the element (tr(A), tr(B), tr(AB)) of 𝔽_{q}^{3}. For notational simplicity, we denote (tr(A), tr(B), tr(AB)) by Tr(A, B) and call it the Fricke trace, or often just the trace, of the pair (A, B). A character is called essential when it is the character of an essential representation, that is, when it is the trace of a generating pair.

The action of Aut(F_{2}) on the essential representations induces an action of the extended modular group PGL(2, ℤ) on the essential characters, whose orbits we call Markoff classes. Explicitly, Markoff equivalence is generated by permutations of the three coordinates, together with the relation that (α, β, γ) ∼ (α, β, αβ − γ). Since this action is induced from the action on representations, there is a well-defined Fricke trace function Tr from N to the set M of Markoff classes of essential characters.

The Fricke polynomial Q(α, β, γ) = α^{2} + β^{2} + γ^{2} − αβγ − 2 has the property that Q(Tr(A, B)) = tr([A, B]), and consequently the value of Q is an invariant of Markoff equivalence. For q ≥ 13, our result that tr: N → 𝔽_{q} − {2} is surjective implies that Q: M → 𝔽_{q} − {2} is surjective. This brings us to our main conjecture on essential characters:

Conjecture C (Q classifies Markoff classes). Two essential characters are Markoff equivalent if and only if they have the same Q-value.

In summary, Conjectures C and B say respectively that for q ≥ 13, in the diagram

N  ⟶^{Tr} M
tr↓  ↓^{Q}
𝔽_{q} − {2}  𝔽_{q} − {2} ,

Q is a bijection, and tr is a bijection except that it is two-to-one on the preimage of −2 when q ≡ 1 mod 4.

At the end of section 8, we will see that if Conjecture B holds, then in the case when q ≡ 1 mod 4, the Fricke traces of the two elements in tr^{−1}(−2) are in the same Markoff class in M. It follows that Conjecture B implies Conjecture C, as well as the following assertion:

Conjecture B′ (Fricke trace is nearly injective). The Fricke trace map Tr: N → M is injective except that it is two-to-one on the preimage of Q^{−1}(−2) when q ≡ 1 mod 4.

On the other hand, Conjectures B′ and C together immediately imply Conjecture B.

Results of A. M. Macbeath, that we will present in section 4, show that if M is a Markoff class then Tr^{−1}(M) consists of at most two Nielsen classes, and moreover that Tr is a bijection from N to M when q is even. This leads to the following:

1) When q is even, Conjecture B′ holds, so Conjecture C is equivalent to Conjectures A and B.

2) When q is odd, Macbeath’s results and proposition 10.5 show that if 2 − ℓ is not a square in 𝔽_{q} (where ℓ ≠ 2), then Tr is injective on the preimage of Q^{−1}(ℓ). That is, Conjecture B′ always holds over at least half of the level surfaces of Q.

For many applications, Nielsen equivalence is too strong an invariant. More natural is to extend the action of Aut(F_{2}) on representations to an action of Aut(G) × Aut(F_{2}) by letting (α, ϕ) · ρ = α ∘ ρ ∘ ϕ^{−1}. The resulting equivalence classes are called T -systems. It is known that Aut(SL(2, q)) is generated by conjugations by elements of GL(2, q), which do not change tr([A, B]), together with field automorphisms of 𝔽_{q} acting on the entries of the elements of SL(2, q), whose effect is to apply the same field automorphism to tr([A, B]). Thus the orbit of tr([A, B]) in 𝔽_{q} is an invariant of the T -system of (A, B), called the weak trace invariant. The number of orbits of Aut(𝔽_{q}) acting on 𝔽_{q} is the number Ψ_{q} stated in the second paragraph of the paper, and discussed more fully in section 7 below. Theorem 5.1 shows that for q ≥ 13, Ψ_{q} − 1 is a lower bound for the number of T -systems of SL(2, q), and the next conjecture implies that this is the exact number. Denote the set of T -systems by T and the set of orbits of Aut(𝔽_{q}) acting on 𝔽_{q} by O_{q}.

Conjecture W (Weak trace invariant classifies T -systems). For q ≥ 13 the weak trace invariant tr: T → O_{q} − {2} is a bijection.

In section 7, we will see that Conjecture B implies Conjecture W.

As we mentioned above and will discuss in section 9, all of these conjectures have been verified computationally for all q ≤ 101, and the minor exceptions that occur when q ≤ 11 are also completely calculated. We will also verify all conjectures for the (almost laughably restrictive, but conceivably infinite) class of all q such that q − 1 is prime and q + 1 has the form 3p_{1} for some prime p_{1}.

Here is a brief outline of the exposition. Section 2 reviews Nielsen equivalence and T -systems, section 3 introduces the Fricke polynomial Q, and section 4 recalls results from Macbeath’s elegant paper [15]. In section 5 we prove theorem 5.1 that realizes elements of 𝔽_{q} as trace invariants, and we have already mentioned the work in section 6 relating the Higman and Nielsen invariants. Section 7 introduces the weak trace invariant and gives a proof of the formula for Ψ_{q}. Markoff equivalence in the character variety is introduced in section 8, at which point we can present the discussion of our computer calculations in section 9.

In section 10, we review the concepts of elliptic, parabolic, and hyperbolic elements of 𝔽_{q}. This has a significant application in odd characteristic, proposition 10.5 that appeared above in the discussion of Conjecture B′.

Apart from the final two sections, which contains the aforementioned treatments of PSL(2, q) and of almost free actions, the last few sections of the paper are directed toward the proof of Conjecture C, and hence all the conjectures, in the highly restricted case when one of q + 1 or q − 1 is prime and the other is 3 times a prime. This proof of Conjecture C requires quite a bit of work, which we hope will someday be justified by further progress at least when p = 2. The restriction to p = 2 arises initially because of a characterization of the hyperbolic elements, for which no analogue is apparent in odd characteristic: the inverses of the hyperbolic elements, together with 0, are exactly the kernel of the trace map from 𝔽_{q} to 𝔽_{2} (lemma 10.2).

Sections 11 and 12 are presented for arbitrary q, although only used later for even q. In section 11, we examine more closely how the level surfaces of Q meet the “slices” of 𝔽_{q} with fixed values of the first coordinate α, detailing how the pattern of their Q-values is governed by whether α is elliptic, parabolic, or hyperbolic. The action of Aut(F_{2}) on these individual slices is analyzed. Concrete examples of slices are given in section 12, to illustrate and help with understanding of section 11.

Section 13 is fully specialized to even q. A number of further simplifications occur, which allow us to obtain a workable description of the action within a fixed slice. Even with all this information, it is difficult enough to understand the full action that we require the further strong assumptions on q −1 and q +1 to force the level surface of Q into one big orbit. The need for such assumptions is rather frustrating, since in numerical calculations the orbit of a point seems to enlarge very rapidly to fill up the level surface as automorphisms are applied, but we have not been able to discern a key property that enables us to control this; it just seems random.

A possible reason for caution about the conjectures arises from section 13, where a very important role is played by the “transitive” elements of 𝔽_{q}−{0}, which are the traces of matrices of large orders q−1 or q+1. For very large q, the proportion of such elements may become arbitrarily small, much smaller than in the cases q ≤ 101 that we have checked computationally or the cases where q − 1 and q + 1 satisfy the very strong primeness assumptions. So in this possibly relevant sense the cases for which the conjectures are known are not representative of the general case. While this does not suggest that the conjectures are likely to fail, it does say that the accumulated evidence for them may not be as strong as it appears.

2. Nielsen equivalence and T -equivalence

The material in this section is very well-known. For simplicity we will restrict attention to two-generator groups G, but it can be adapted without difficulty to n-generator groups (see for example [4]).

We have defined Nielsen equivalence in the set of generating pairs G_{2}(G) as equivalence under the left action of Aut(F_{2}), and T -equivalence as equivalence under the left action of Aut(G) × Aut(F_{2}). Nielsen [20] found generators for Aut(F_{2}), which show that Aut(F_{2}) is generated by the three involutions r: (x_{1}, x_{2}) ↦ (x_{1}^{−1}, x_{1}x_{2}), s: (x_{1}, x_{2}) ↦ (x_{2}, x_{1}), and t: (x_{1}, x_{2}) ↦ (x_{1}^{−1}, x_{2}), These act as follows on G_{2}(G):

r(g_{1}, g_{2}) = (g_{1}^{−1}, g_{1}g_{2})
s(g_{1}, g_{2}) = (g_{2}, g_{1})
t(g_{1}, g_{2}) = (g_{1}^{−1}, g_{2}) .

These “basic moves” or simple compositions of them allow one to perform all product replacement moves, which replace one generator by the result of pre- or post-multiplying it by another generator or its inverse, together with the moves of replacing either generator by its inverse, or interchanging the two generators. From this viewpoint, T -equivalence just adds the additional basic moves of

α(g_{1}, g_{2}) = (α(g_{1}), α(g_{2}))

for any α ∈ Aut(G). When α is inner, this resulting pair is Nielsen equivalent to (g_{1}, g_{2}). So the action of Aut(G) on G_{2}(G) induces an action of Out(G) on the set N of Nielsen classes, whose quotient is the set T of T -systems.

3. The Fricke polynomial and the trace map on pairs

Fixing a basis of F_{2}, we regard representations F_{2} → G for G = SL(2, q) or G = PSL(2, q) as pairs (A, B), where A, B ∈ SL(2, q). In the case G = PSL(2, q), we keep in mind that A and B are defined only up to sign. As in the introduction, we call a representation F_{2} → G essential when it is surjective, that is, when (A, B) is a generating pair of G.

The Fricke trace map is the function Tr: Hom(F_{2}, SL(2, q)) → 𝔽_{q}^{3} defined by Tr(A, B) = (tr(A), tr(B), tr(AB)). The Fricke polynomial Q: 𝔽_{q}^{3} → 𝔽_{q} is defined by

Q(α, β, γ) = α^{2} + β^{2} + γ^{2} − αβγ − 2 .

The well-known identity

tr([A, B]) = Q(Tr(A, B)) ,

can be obtained by repeatedly simplifying tr(ABA^{−1}B^{−1}) using the fundamental identity tr(X) tr(Y) = tr(XY) + tr(XY^{−1}) for X, Y ∈ SL(2, F) (which follows from the Cayley-Hamilton identity Y^{2} − tr(Y)Y + I = 0 by multiplying on the left by XY^{−1} and taking traces). Since the expression Q(Tr(A, B)) appears quite often in our work, we will abbreviate it to Q(A, B). Since Q(A, B) = Q(−A, B) = Q(A, −B) = Q(−A, −B), this Q is well-defined on PSL(2, q) × PSL(2, q).

4. G_{0}, G_{1}, G, and Macbeath’s theorems

In this section we follow Macbeath [15]. For a fixed value of q define G_{0} to be SL(2, q). There is a natural homomorphism π: G_{0} → PSL(2, q).

Let G_{1} be the subgroup of SL(2, q^{2}) consisting of the matrices of the form

(\begin{matrix}a & b \\ b^{q} & a^{q} \end{matrix}). The subgroups G_{0} and G_{1} are conjugate in SL(2, \overline{𝔽_{q}}), where \overline{𝔽_{q}}

is the algebraic closure of 𝔽_{q}. From now on, when we write G_{i}, we mean either one of G_{0} or G_{1}. We write G for PSL(2, q).

Theorem 1 of [15] says that every triple is a character:

Theorem 4.1 (Macbeath). Tr: G_{i} × G_{i} → 𝔽_{q}^{3} is surjective.

In section 10 below, we will give a computational proof of theorem 4.1. Also, a slight modification of Macbeath’s more elegant approach is used to prove proposition 9.1.

Following [15], a subgroup of G is called affine if its premiage in SL(2, q) is conjugate, in either G_{0} or G_{1}, into the subgroup of upper triangular matrices. Theorem 2 of [15] identifies the affine subgroups of PSL(2, q) in terms of Q.

Theorem 4.2 (Macbeath). A G_{i}-pair (A, B) generates an affine subgroup of G if and only if Q(A, B) = 2.

Here, as in many places in our work, we speak of the subgroup of G generated by a G_{i}-pair. This means the subgroup generated by the images of A and B in G.

An 𝔽_{q}-triple is called singular or nonsingular according as Q does or does not assign it the value 2. Theorem 4.2 shows that a pair with singular trace can never generate G.

Theorem 3 of [15] describes the conjugacy classes of G_{i}-pairs with nonsingular trace.

Theorem 4.3 (Macbeath). Let (α, β, γ) be a nonsingular 𝔽_{q}-triple. If p = 2, then there is exactly one conjugacy class of G_{i}-pairs whose trace equals (α, β, γ). If p > 2, then there are exactly two conjugacy classes. These classes are conjugate in SL(2, \overline{𝔽_{q}}), where \overline{𝔽_{q}} is the algebraic closure of 𝔽_{q}, and consequently generate isomorphic subgroups of G_{i}.

5. Trace invariants

An element of 𝔽_{q} is called a trace invariant if it equals tr([A, B]) (and hence equals Q(A, B)) for some generating pair (A, B) of SL(2, q). By theorem 4.2, the field element 2 is never a trace invariant. The main result of this section tells which elements of 𝔽_{q} do occur as trace invariants:

Theorem 5.1. For q = 2, q = 4, q = 8, and all q ≥ 13, the trace invariants are the elements of 𝔽_{q} − {2}. For the remaining cases, the trace invariants are as follows:

1) For q = 3, q = 9, and q = 11, all elements except 1 and 2.

2) For q = 5, only 1 and 3.

3) For q = 7, all elements except 0, 1, and 2.

For q ≤ 11, theorem 5.1 can be proven in a few pages of elementary arguments of varying degrees of complication, and we omit these details. Also, we have checked those cases using GAP; these and other calculations are discussed in section 9 below. In the remainder of this section, we will prove theorem 5.1 for q ≥ 13.

We first review some well-known facts about PSL(2, q). The subgroups of PSL(2, q) were determined by L. E. Dickson [5]. The following statement, in which d denotes gcd(2, q − 1), is from Theorem 3(6.25) of Suzuki [24].

Theorem 5.2. Every subgroup of PSL(2, q) is isomorphic to (at least) one of the following.

(a) The dihedral groups of orders 2(q ± 1)/d and their subgroups.

(b) A group H of order q(q −1)/d and its subgroups. A Sylow p-subgroup H_{0} of H is elementary abelian, normal in H, and the factor group H/H_{0} is a cyclic group of order (q − 1)/d.

(c) A_{4}, S_{4}, or A_{5}.

(d) PSL(2, p^{r}) or PGL(2, p^{r}) where r divides s.

The last statement in (d) is from 3(6.18) of [24]. The subgroups H_{0} in (b) are also p-Sylow subgroups of PSL(2, q), so are conjugate to the subgroup of upper triangular elements.

We use the following terminology to refer to the subgroups described in theorem 5.2: subgroups as in (a) are called small, as in (c) are called exceptional, and as in (d) are called linear. The affine subgroups (defined in section 4) include the subgroups in (b) and the cyclic subgroups in (a) that are subgroups of a maximal cyclic subgroup of order (q ± 1)/d. The groups in (d) coincide when p = 2, and will be examined quite a bit more closely in section 9.

An element of PSL(2, q) is called parabolic if its trace if ±2. Parabolic elements have order p. For nonparabolic elements, we have the following information from (2.3) and (2.4) of [9].

Lemma 5.3. The orders of nonparabolic elements of PSL(2, q) are exactly the divisors of (q + 1)/d and (q − 1)/d. In particular, the maximum order of a nonparabolic element of PSL(2, q) is (q + 1)/d.

For x, y ∈ 𝔽_{q} with x ≠ 0, put H_{x} = (\begin{matrix}x & 0 \\ 0 & x^{−1} \end{matrix}) and J_{y} = (\begin{matrix}y + 1 & 1 \\ y & 1 \end{matrix}).

The next lemma is a straightforward calculation.

Lemma 5.4. Put D = x − x^{−1}. Then [H_{x}, J_{y}] = (\begin{matrix}1 − Dxy & Dx(y + 1) \\ −Dx^{−1}y & 1 + Dx^{−1}y \end{matrix}).

Consequently, the trace of [H_{x}, J_{y}] is 2 − D^{2}y.

The next lemma will ensure that H_{x} and J_{y} do not generate a small or affine subgroup.

Lemma 5.5. Assume that y ≠ 0, and that x^{4} ≠ 1 and x^{6} ≠ 1. Then [H_{x}, J_{y}] and [H_{x}^{−1}, J_{y}] do not commute in PSL(2, q).

Proof. Again write D = x − x^{−1}, which is nonzero since x^{2} ≠ 1. Now [H_{x}^{−1}, J_{y}] = [H_{x^{−1}}, J_{y}], so [H_{x}^{−1}, J_{y}] is obtained from the expression in lemma 5.4 by replacing each appearance of x with x^{−1} (hence each D with −D). One then calculates

[H_{x}, J_{y}] [H_{x}^{−1}, J_{y}] = (\begin{matrix}1 + D^{3}xy(y + 1) & D^{2}(y + 1) − D^{3}xy(y + 1) \\ D^{2}y + D^{3}x^{−1}y^{2} & 1 − D^{3}x^{−1}y(y + 1) \end{matrix}) .

Again, by replacing each x by x^{−1}, we obtain

[H_{x}^{−1}, J_{y}] [H_{x}, J_{y}] = (\begin{matrix}1 − D^{3}x^{−1}y(y + 1) & D^{2}(y + 1) + D^{3}x^{−1}y(y + 1) \\ D^{2}y − D^{3}xy^{2} & 1 + D^{3}xy(y + 1) \end{matrix}) .

If these matrices are equal, their (2, 1) entries show that x = −x^{−1}, in contradiction to the assumption that x^{4} ≠ 1. So assume that p ≠ 2 and the matrices differ by multiplication by −I. From the (2, 1) entries, we have y − Dxy^{2} = −y − Dx^{−1}y^{2}, or D^{2}y = 2. From the (1, 1) entries, we find that 1−D^{3}x^{−1}y(y +1) = −1−D^{3}xy(y +1), which implies that D^{4}y(y +1) = −2, and using D^{2}y = 2 this leads to D^{2} = −3. But the equation D^{2} = −3 says that x^{2} − 2 + x^{−2} = −3, that is, x^{4} + x^{2} + 1 = 0. Multiplying by x^{2} − 1 shows that x^{6} = 1, in contradiction to the hypothesis. □

Proposition 5.6. Assume that q ≥ 13. Suppose that x generates 𝔽_{q} − {0} and that y ≠ 0. Then H_{x} and J_{y} generate SL(2, q).

Proof. Since q > 7, we have x^{4} ≠ 1 and x^{6} ≠ 1. Let S be the image in PSL(2, q) of the subgroup generated by {H_{x}, J_{y}}. Note that the order of H_{x} is (q − 1)/d. We assume that S ≠ PSL(2, q), and consider the four possibilities given in theorem 5.2. Lemma 5.5 shows that S is not small or affine. Since (q − 1)/2 is at least 6, H_{x} has order more than 5, so S cannot be exceptional.

Assume that S is linear, and consider first the case that S is isomorphic to PSL(2, p^{r}), where r is a proper divisor of s. By lemma 5.3 the order of H_{x} is no more than (p^{r} + 1)/d. Since r < s, this is less than (p^{s} − 1)/d, the known order of H_{x}.

The remaining possibility is that p > 2 and S is isomorphic to PGL(2, p^{r}). Since H_{x}^{2} is contained in a subgroup isomorphic to PSL(2, p^{r}), lemma 5.3 shows that (p^{s} − 1)/2, the order of H_{x}, is no more than p^{r} + 1. This can hold only when p = 3 and s = 2, that is, q = 9. □

To see that proposition 5.6 implies theorem 5.1 in the case q ≥ 13, let x be a generator of 𝔽_{q} − {0}, and put D = x − x^{−1}. By proposition 5.6 and lemma 5.4, all traces of the form 2−D^{2}y with y ≠ 0 arise as trace invariants of generating pairs for PSL(2, q).

6. Comparison of the Higman invariant and trace invariant

In this section, we will see that each trace invariant determines a unique Higman invariant for SL(2, q) or PSL(2, q), except when the trace invariant is −2 and q ≡ 1 mod 4. In that case, there are two Higman invariants, except when q = 9, when there are none. Using that information, we will verify that Conjectures A and B stated in section 1 are equivalent.

The conjugacy classes in SL(2, q) are very well-known:

Proposition 6.1. If A, B ∈ SL(2, q) and tr(A) ≠ ±2, then A is conjugate to B if and only tr(A) = tr(B). For each of the traces 2 and −2, there are two conjugacy classes when q is even and three when q is odd.

We will verify the second part, since we need the notation anyway. Consider an element X of SL(2, q) having trace 2ϵ where ϵ = ±1. It is conjugate

to a matrix of the form (\begin{matrix}ϵ & μ \\ 0 & ϵ \end{matrix}), so the nonempty set M(X) of elements μ

that appear in such conjugates is a complete invariant of the conjugacy class

of X. Conjugation by an element P of SL(2, q) takes (\begin{matrix}ϵ & μ \\ 0 & ϵ \end{matrix}) to (\begin{matrix}ϵ & μ′ \\ 0 & ϵ \end{matrix})

if and only if P is upper triangular. In this case, writing P = (\begin{matrix}x & b \\ 0 & x^{−1} \end{matrix}),

the effect of conjugation by P is to multiply μ by x^{2}. So M(X) is either 0 (when X = ±I), or is the set of nonzero elements that are squares, or is the set of non-squares.

Using theorem 5.1, we can now determine the relation between Higman invariants and trace invariants.

Corollary 6.2. Let (A, B) be a generating pair for SL(2, q) or PSL(2, q). If q ≢ 1 mod 4, or tr([A, B]) is not −2, then the trace invariant determines the Higman invariant of (A, B). For q ≡ 1 mod 4 and trace −2, there are two Higman invariants when q = 5 or q ≥ 13, while for q = 9 there are none.

Proof. For q ≤ 11 the theorem can be checked by direct computation, as described in section 9 below, and we assume that q ≥ 13. Theorem 5.1 shows that 2 never occurs as a trace invariant, but that all other traces do. So proposition 6.1 shows that each trace other than −2 is the trace of a unique Higman invariant.

Suppose from now on that the trace invariant of the generating pair (A, B) equals −2; in particular, q is odd. Since A and B cannot commute in PSL(2, q), [A, B] ≠ −I.

Suppose that q ≡ 3 mod 4. Then −1 is not a square in 𝔽_{q}, so M([B, A]) = −M([A, B]) ≠ M([A, B]). Thus the conjugacy classes of [A, B] and [B, A] are distinct and are the two conjugacy classes of matrices of trace −2 other than −I, so there is only one Higman invariant possible in this case.

Suppose now that q ≡ 1 mod 4. Then −1 is a square, so M([B, A]) = −M([A, B]) = M([A, B]), and the Higman invariant is a single conjugacy class. By theorem 5.1, at least one of the conjugacy classes of matrices of trace −2 is a Higman invariant; by conjugation we may choose a generating pair (A, B) having [A, B] = (\begin{matrix}−1 & t \\ 0 & −1 \end{matrix}) for some nonzero t ∈ 𝔽_{q}. Con-

jugating by a matrix in SL(2, q^{2}) of the form (\begin{matrix}π & 0 \\ 0 & π^{−1} \end{matrix}), where π^{2} ∈ 𝔽_{q}

but π ∉ 𝔽_{q}, changes (A, B) to a generating pair (A′, B′) of SL(2, q) hav-

ing commutator (\begin{matrix}−1 & tπ^{2} \\ 0 & −1 \end{matrix}), realizing the other Higman invariant with

trace −2. □

Corollary 6.2 implies that Conjecture A is equivalent to Conjecture B. For if H denotes the set of Higman invariants, then the trace map factors as N → H → 𝔽_{q} − {2}, with the first function surjective. Conjecture A is that the first function is injective, as well. Corollary 6.2 shows that the first map is injective if and only if Conjecture B holds.

The pair of Nielsen classes in corollary 6.2 having trace invariant −2 but distinguished by their Higman invariants are always T -equivalent. For as seen in the proof, an automorphism SL(2, q) which is conjugation by a

matrix (\begin{matrix}π & 0 \\ 0 & π^{−1} \end{matrix}) in SL(2, q^{2}) with π^{2} ∈ 𝔽_{q} but π ∉ 𝔽_{q} interchanges their

Higman invariants. Therefore Conjecture B implies Conjecture W.

7. Weak trace invariants

We turn now to T -equivalence. The automorphisms of SL(2, q) are wellunderstood, by the following result due to Schreier and van der Waerden [23] (see also [6] and the appendix to [12]).

Theorem. Every automorphism of SL(2, q) or of PSL(2, q) has the form A ↦ P A^{ϕ}P^{−1}, where P is an element of GL(2, q), and A^{ϕ} is the matrix obtained by applying an automorphism ϕ of 𝔽_{q} to each entry of A.

Conjugation has no effect on the trace invariant, while applying a field automorphism to the coefficients of A and B changes the trace of [A, B] by the field automorphism itself. Therefore the orbit of the trace invariant under Aut(𝔽_{q}) is an invariant of the T -system, which we call the weak trace invariant.

We saw at the end of section 6 that when q ≡ 1 mod 4, there are two distinct Nielsen classes which are T -equivalent. It follows that Conjecture B implies Conjecture W.

Denoting by Ψ_{q} the number of orbits of the action of Aut(𝔽_{q}) on 𝔽_{q}, theorem 5.1 tells us immediately which orbits occur as weak trace invariants:

Corollary 7.1. The numbers of orbits of the Frobenius automorphism that occur as weak trace invariants of generating pairs of SL(2, q) or PSL(2, q) are as follows:

i) If q = 2, q = 4, q = 8, or q ≥ 13, then Ψ_{q} − 1 orbits occur.

ii) If q = 3, q = 9, or q = 11, then Ψ_{q} − 2 orbits occur. iii) If q = 5 or q = 7, then Ψ_{q} − 3 orbits occur.

Recall that Aut(𝔽_{q}) is a cyclic group generated by the Frobenius automorphism Φ that sends each x to x^{p}. Since Φ has order s, the ceiling ⌈\frac{q}{s}⌉ is trivially a lower bound for the number Ψ_{q} of orbits of Aut(𝔽_{q}), and since Φ fixes each element of the subfield 𝔽_{p}, ⌈\frac{q−p}{s}⌉ + p is an obvious lower bound. The exact number of orbits of Aut(𝔽_{q}) is given by the closed formula that we stated in the introduction:

Ψ_{q} = \frac{1}{s} ∑_{r|s}φ(s/r) p^{r} ,

where φ is the Euler totient function. This formula for Ψ_{q} is surely wellknown, although we have not found an explicit statement in the literature. Experts in finite fields (we thank, in particular, H. Niederreiter) observe that the number of orbits is the same as the number of monic irreducible polynomials over 𝔽_{p} of degree dividing s, each orbit being the set of roots of one such polynomial. Consequently, the number e(r) of orbits with r elements (which equals the number of monic irreducible polynomials of degree r) satisfies q = ∑_{r|s} re(r), and a formula for e(s) can be obtained using Möbius inversion (see for example [13, Ch. III.2]). In fact the formula for e(s) is the same as our formula for Ψ_{q} but with φ replaced by the Möbius function μ. Summing these for r dividing s and then manipulating using the fact (also a consequence of Möbius inversion) that \frac{φ(s)}{s} = ∑_{r|s} \frac{μ(r)}{r} gives the formula for Ψ_{q}. Rather than writing out the details of that, or worse yet, leaving them to the reader, we will present here an elegant proof shown to us by Gareth Jones, that deduces the formula for Ψ_{q} in a few lines using Burnside’s Lemma and a few of the most elementary properties of 𝔽_{q}.

Burnside’s Lemma says that the number of orbits of a finite group acting on a finite set equals the average number of fixed points of the elements of the group:

Lemma 7.2 (Burnside’s Lemma). If a finite group G acts on a finite set Ω, then the number of orbits is given by

\frac{1}{|G|} ∑_{g∈G} π(g)

where π(g) is the number of points fixed by g.

Burnside’s Lemma can be proven by elementary counting arguments (see for example [1]), and a better name for it is the Burnside-Cauchy-Frobenius formula (see [19]).

To obtain the formula for Ψ_{q}, we will apply Burnside’s Lemma with Ω = 𝔽_{p^{s}} and G = Aut(𝔽_{p^{s}}). Recall that 𝔽_{p^{r}} occurs as a subfield of 𝔽_{p^{s}} if and only if r|s, and that it is the unique subfield of this order. Each element Φ^{m} of G has order s/r, where r = gcd(m, s), and there are φ(s/r) elements of this order for each divisor r of s. Such an element has the same fixed points as Φ^{r}, since each is a power of the other, and the fixed points of Φ^{r} are the roots of the polynomial x^{p^{r}} − x. These roots form the subfield F_{p^{r}}, so π(Φ^{m}) = p^{r}. Burnside’s Lemma now yields the formula for Ψ_{q}.

The same argument, with q in the role of p, shows that for any prime power q, the number of orbits of the action of the Galois group Aut_{𝔽_{q}} 𝔽_{q^{s}}

on 𝔽_{q^{s}} is \frac{1}{s} ∑_{r|s} φ(s/r) q^{r}.

The obvious lower bound ⌈\frac{q−p}{s}⌉ + p gives the exact count whenever s is prime (or s = 1), since then all orbits contain s elements except those in the subfield 𝔽_{p}. But even for composite s this bound is very accurate, apart from a few small values of q, because the vast majority of elements of 𝔽_{q} do not lie in any proper subfield and consequently almost all orbits have s elements. For example, using GAP [7] we find that for Ψ_{2^{30}} = 35, 792, 568, the bound of 35, 791, 397 is approximately 99.9967% of the exact value, while the bound of 29, 484, 565, 267, 122, 446 is approximately 99.99999984% of Ψ_{29^{16}} = 29, 484, 565, 316, 813, 125.

8. Markoff equivalence in the character variety

We saw in section 2 that for any group H, the action of Aut(F_{2}) on G_{2}(H) is generated by the action of three involutions r, s and t. It will be convenient to use a fourth element of Aut(F_{2}):

4. m = tr, which acts on G_{2}(H) by m(A, B) = (A, AB). As an automorphism of the set H × H, the order of m is the least common multiple of the orders of the elements of H.

For any field F, the elements r, s, t, and m act on the set of F -triples as follows:

1) r(α, β, γ) = (α, γ, β)

2) s(α, β, γ) = (β, α, γ)

3) t(α, β, γ) = (α, β, αβ − γ)

4) m(α, β, γ) = (α, γ, αγ − β) Specializing to H = SL(2, F) for some field F, this action is induced from the action on H × H via Tr, that is, if (A, B) is a G_{i}-pair with Tr(A, B) = (α, β, γ), then r ∘ Tr = Tr ∘r, s ∘ Tr = Tr ∘s, and t ∘ Tr = Tr ∘t. For r and s this is obvious, and for t it is simply the identity tr(A^{−1}B) = tr(A) tr(B) − tr(AB). We call the equivalence relation on F^{3} generated by r, s, and t Markoff equivalence.

Since Tr ∘μ = Tr for any inner automorphism μ of F_{2}, the Aut(F_{2})-action on F^{3} induces an action of the extended modular group Aut(F_{2})/ Inn(F_{2}) = GL(2, ℤ) on F^{3}. Since the element −I of GL(2, ℤ) is represented by the automorphism that sends x_{i} to x_{i}^{−1} for both basis elements of F_{2}, it also acts trivially on F^{3} and there is an induced action of PGL(2, ℤ). Thus Markoff equivalence in F^{3} coincides with the orbits of this action of the extended modular group PGL(2, ℤ) that was used for F = ℝ in [10].

Theorem 4.3 shows immediately that Tr: N → M is a bijection when p = 2 and is (≤ 2)-to-1 when p > 2, where the latter terminology means that the preimage of each element of M contains at most two elements of N. Moreover, we will prove in proposition 10.5 below that the Markoff class of (α, β, γ) has only one preimage Nielsen class whenever 2 − Q(α, β, γ) is not a square in 𝔽_{q}.

For the case q ≡ 1 mod 4, we saw that the two Nielsen-inequivalent generating pairs found at the end of the argument in section 6 differ by conjugation, so their Fricke traces are identical. Under the Fricke trace map N → M, their Nielsen classes go to the same Markoff class, and consequently Conjecture B implies Conjecture C.

9. Numerical calculations

Using GAP [7], we have verified the conjectures for all q ≤ 101. The source files for that work are available at [17]. In this section we will describe the methodology used.

From section 1, Conjecture C implies the other conjectures when q is even, and when q is odd, Conjectures C and B′ together imply the other conjectures.

The first step is to identify the essential characters. Denote by P (A, B) the subgroup of PSL(2, q) generated by {A, B}. Clearly (A, B) generates a proper subgroup of SL(2, q) if and only if P (A, B) is a proper subgroup. The cases for which this occurs were described in theorem 5.2, and can be identified from Tr(A, B) = (α, β, γ) as follows.

1) By theorem 4.2, P (A, B) is affine (which includes all cases when it is cyclic) if and only if Q(α, β, γ) = 2.

2) Since a matrix has order 2 in PSL(2, q) if and only if its trace is 0, P (A, B) is dihedral if and only if at least two of α, β, and γ are 0.

3) The cases when P (A, B) is one of the exceptional subgroups A_{4}, S_{4}, or A_{5} can be characterized by conditions on Tr(A, B) = (α, β, γ) which are stated and verified in [16]. It is A_{4} exactly when α, β, γ ∈ {0, ±1} and Q(α, β, γ) = 0, and is S_{4} exactly when α, β, γ ∈ \{0, ±1, ±\sqrt{2}\}, where \sqrt{2} denotes a root of x^{2} − 2, and Q(α, β, γ) = 1. For A_{5} the conditions are quite a bit more complicated, so we do not detail them here.

4) When all three of α, β, and γ lie in a proper subfield 𝔽_{p^{r}}, either P (A, B) is affine or P (A, B) is isomorphic to a subgroup of PSL(2, p^{r}). For by theorem 4.1, there must be a pair (A′, B′) of elements of PSL(2, p^{r}) such that Tr(A′, B′) = (α, β, γ). If Q(α, β, γ) = 2, then P (A, B) is affine, and if not, then by theorem 4.3, the subgroups P (A, B) and P (A′, B′) are isomorphic.

The remaining proper subgroups of SL(2, q) will be a bit of a nuisance. They are included in case (d) in theorem 5.2, and are described explicitly in (6.18) of [24] (also on p. 28 of [15]) as follows. Assume that q is odd, and observe that there is an element of 𝔽_{q} − 𝔽_{p^{r}} whose square lies in 𝔽_{p^{r}} if and only if 𝔽_{p^{2r}} ⊆ 𝔽_{q}, in which case all such elements lie in 𝔽_{p^{2r}}. If π is such an element, and x ∈ 𝔽_{q} − 𝔽_{p^{r}}, then x^{2} ∈ 𝔽_{p^{r}} if and only if

x = πδ for some some δ ∈ 𝔽_{p^{r}}. Write d_{π} for the matrix (\begin{matrix}π & 0 \\ 0 & π^{−1} \end{matrix}). Then

SL(2, p^{r}) has index 2 in the subgroup ŜL(2, p^{r}) = ⟨SL(2, p^{r}), d_{π}⟩. All that is going on is that d_{π}^{2} ∈ SL(2, p^{r}) and d_{π} normalizes SL(2, p^{r}), so any element in ŜL(2, p^{r}) = ⟨SL(2, p^{r}), d_{π}⟩ can be written as d_{π}^{ϵ}A where A ∈ SL(2, p^{r}) and ϵ is 0 or 1. Note that the trace of d_{π}^{ϵ}A is of the form π^{ϵ}δ for some δ ∈ 𝔽_{p^{r}}. Consequently, if (A, B) is a pair of elements of ŜL(2, p^{r}), then Tr(A, B) = (π^{ϵ_{1}}α, π^{ϵ_{2}}β, π^{ϵ_{3}}γ) with α, β, γ ∈ 𝔽_{p^{r}} and ϵ_{1} + ϵ_{2} + ϵ_{3} ≡ 0 mod 2. Equivalently, Tr^{2}(A), Tr^{2}(B), Tr^{2}(AB), and Tr(A) Tr(B) Tr(AB) all lie in 𝔽_{p^{r}}. We are prepared for the following variation on theorem 4.1:

Proposition 9.1. Let (α̂, β̂, γ̂) be a triple of elements of 𝔽_{q} such that α̂^{2}, β̂^{2}, γ̂^{2}, and α̂ β̂γ̂ all lie in a proper subfield 𝔽_{p^{r}} of 𝔽_{q}. Then either α̂, β̂, and γ̂ all lie in 𝔽_{p^{r}}, or 𝔽_{p^{2r}} ⊆ 𝔽_{q} and there exists a pair (A, B) ∈ ŜL(2, p^{r}) such that Tr(A, B) = (α̂, β̂, γ̂).

Proof. Our argument is a very slight modification of the proof of theorem 4.1, given as Theorem 1 in [15]. If all three coordinates lie in 𝔽_{p^{r}}, in particular if q is even, then there is nothing to prove. Of the remaining possibilities, we need only consider the case when the triple is of the form (πα, πβ, γ), with α, β, γ ∈ 𝔽_{p^{r}}, since the other cases can then be achieved by applying Nielsen moves to a pair (A, B) that we will obtain for this case.

We will seek a pair of the form

(A, B) = ((\begin{matrix}0 & π \\ −π^{−1} & π^{−1}(π^{2}α) \end{matrix}) , (\begin{matrix}πx & πy \\ π^{−1}z & π^{−1}w \end{matrix}))

for which

πx + π^{−1}w = tr(B) = πβ
z − y + αw = tr(AB) = γ
xw − yz = det(B) = 1 .

Eliminating x and then y from these equations reduces them to the condition

1 + z^{2} + π^{−2}w^{2} + αzw + β(−1)w + γ(−1)z = 0 .

If (X, Y, Z) is a solution of

C(X, Y, Z) = X^{2} + Y^{2} + π^{−2}Z^{2} + αY Z + βXZ + γXY = 0

with X ≠ 0, then putting (−1, z, w) = (−1, −Y/X, −Z/X) satisfies the condition. Since every quadratic form over a finite field has nonzero solutions, we need only consider the case of a nonzero solution of the form (0, Y_{0}, Z_{0}). A line through this point and not tangent to the conic C(X, Y, Z) = 0 will intersect the conic in a point with X ≠ 0, giving the desired solution. Such a line exists unless (0, Y_{0}, Z_{0}) is a singular point of the conic. But the singularity condition is 0 = γY_{0} + βZ_{0}, 0 = 2Y_{0} + αZ_{0}, and 0 = αY_{0} + 2π^{−2}Z_{0}, and the latter two equations imply that π^{2} = (2α^{−1})^{2}, in contradiction to the fact that π ∉ 𝔽_{p^{r}}. □

Equipped with proposition 9.1, we now consider the remaining kind of proper subgroup.

5) If p is odd and α^{2}, β^{2}, γ^{2}, and αβγ lie in a proper subfield 𝔽_{p^{r}} of 𝔽_{q}, but at least one of α, β, and γ does not lie in 𝔽_{p^{r}}, then either P (A, B) is affine or P (A, B) is isomorphic to a subgroup of the image of ŜL(2, p^{r}) in PSL(2, q). For by proposition 9.1, there exists a pair (A′, B′) of elements of ŜL(2, p^{r}) such that Tr(A′, B′) = (α̂, β̂, γ̂). If Q(α, β, γ) = 2, then P (A, B) is affine, and if not, then by theorem 4.3 the subgroups P (A, B) and P (A′, B′) are isomorphic.

Conditions 1) through 5) make it easy to check when a triple in 𝔽_{q}^{3} is essential. In particular, a computational proof of theorem 5.1 for the cases when q ≤ 11 can be carried out simply by removing from 𝔽_{q}^{3} all the triples satisfying one of the five conditions, then finding the values that Q assumes on the remaining subset.

Here is how our program verifies Conjecture C for q ≤ 101. For a fixed q and a fixed value ℓ other than 2, it finds the essential triples of 𝔽_{q}^{3} with Q-value equal to ℓ, and forms singleton lists each containing one of these triples. Then it combines any two of these lists whenever an element of one is equivalent to an element of the other under one of r, s, or t. In all cases it finishes with only a single list for each of the possible trace invariants listed in theorem 5.1.

To verify Conjecture B′ by carrying out the same procedure at the level of generating pairs requires a great deal more computing capacity, and on typical desktop machines such as our is only feasible for q ≤ 9. To overcome this, we use a different approach, which assumes that Conjecture C has already been verified for the value of q. We may assume that q is odd, since all conjectures follow from Conjecture C when q is even. Assuming that q satisfies Conjecture C, we exploit the fact (theorem 4.3) that each nonsingular triple is the trace of only two conjugacy classes of pairs. For the Q-value −2, there is nothing to prove since Conjecture C together with corollary 6.2 show that there are exactly two Nielsen classes with trace −2. For the other values of Q, we seek two pairs that have the same Fricke trace— a triple with this particular Q-value— that are Nielsen equivalent but not conjugate. Finding such pairs shows that there is only one Nielsen class mapping to the Markoff class of that triple. Since Conjecture C tells us there is only one Markoff class with the given Q-value, this establishes Conjecture B′ for that Q-value.

Here is the actual algorithm. Fixing a q with 13 ≤ q and an ℓ ∈ 𝔽_{q} − {2, −2}, consider the graph with vertices the set of generating pairs with Q-value ℓ, with edges labeled by r running from each (A, B) to r(A, B), and similar edges labeled s and t. The program chooses a pair (A_{0}, B_{0}) for which Q(A_{0}, B_{0}) = ℓ, then takes random walks in the graph, starting from (A_{0}, B_{0}). Traveling along an edge corresponds to applying a basic Nielsen move. If some walk returns to a pair with Fricke trace Tr(A_{0}, B_{0}), but not conjugate to (A_{0}, B_{0}), then the two conjugacy classes of pairs with that Fricke trace are Nielsen equivalent. Corollary 6.2 shows that such a walk cannot exist when q ≡ 1 mod 4 and tr([A, B]) = −2, but in all other cases we found many such walks. In the cases when 2−ℓ was not a square, lemma 10.6 below shows that the Nielsen equivalent pairs (A_{0}, B_{0}) and (A_{0}^{−1}, B_{0}^{−1}) are nonconjugate, and the program immediately found very short walks taking (A_{0}, B_{0}) to a conjugate of (A_{0}^{−1}, B_{0}^{−1}). When 2 − ℓ was not a square, the shortest walks varied considerably in length, with a few cases as short as one step, and most cases in the range of 10 to 50 steps. The longest walks needed were around 200 steps, with repeated program runs sometimes giving other walks of length in the low 100’s for those cases, but with these “difficult” cases always among the longest walks needed.

10. Parabolic, elliptic, and hyperbolic elements

In our remaining work, we will need more information about the fields 𝔽_{q} and their elements. To set notation, we denote by u a generator of C_{q−1} = 𝔽_{q} −{0}. In the software for the computer-assisted calculations that we discussed in section 9, we used for u the primitive element denoted by Z(q) in the GAP computer algebra system [7]. For the unique quadratic extension 𝔽_{q^{2}} of 𝔽_{q}, the group of nonzero elements is C_{q^{2}−1} = 𝔽_{q^{2}} − {0} and is generated by Z(q^{2}). The element u is Z(q^{2})^{q+1}, and we denote by v the element Z(q^{2})^{q−1}. The latter generates a subgroup C_{q+1} ⊂ C_{q^{2}−1}, and its powers are exactly the elements of 𝔽_{q^{2}} that satisfy x^{q+1} = 1, that is, the elements of norm 1. For p odd, C_{q−1} ∩ C_{q+1} = C_{2}, generated by u^{(q−1)/2} = v^{(q+1)/2} = −1. For p = 2, C_{q−1} ∩ C_{q+1} = {1}. The subgroup of C_{q^{2}−1} generated by C_{q−1} ∪ C_{q+1} is the set of squares, so is all of C_{q^{2}−1} when p = 2 and has index 2 when p > 2.

An element α of 𝔽_{q} is called elliptic, parabolic or hyperbolic according as the equation λ^{2} − αλ + 1 = 0 has zero, one, or two distinct roots in 𝔽_{q}. An element of 𝔽_{q} is hyperbolic if and only if it can be written as u^{i} + u^{−i} with u^{i} ≠ ±1. The elements v^{j} + v^{−j} lie in 𝔽_{q}, and for v^{j} ≠ ±1 are exactly the elliptic elements. We denote the sets of elliptic and hyperbolic elements of a field under discussion by E and H respectively. If q is even, then E contains \frac{1}{2}q elements, H contains \frac{1}{2}(q − 2) hyperbolic elements, and 0 is the unique parabolic element. If q is odd, then E contains \frac{1}{2}(q − 1) elliptic elements, H contains \frac{1}{2}(q − 3) hyperbolic elements, and 2 and −2 are the parabolic elements.

The following lemma gives a simple criterion to identify the type of an element in fields of odd characteristic. By 𝔽_{q}^{2} we denote the set of elements of 𝔽_{q} that are squares.

Lemma 10.1. Let α ∈ 𝔽_{q}, with p > 2.

1) α is parabolic if and only if α^{2} − 4 = 0.

2) α is hyperbolic if and only if α^{2} − 4 ∈ 𝔽_{q}^{2} − {0}.

3) α is elliptic if and only if α^{2} − 4 ∉ 𝔽_{q}^{2}.

Proof. It suffices to prove the only if direction of all three statements. The parabolic case is immediate. If α is hyperbolic, then writing α = u^{i} + u^{−i} gives α^{2} − 4 = (u^{i} − u^{−i})^{2} ∈ 𝔽_{q}^{2} − {0}. If α is elliptic, then α = v^{j} + v^{−j} produces α^{2} − 4 = (v^{j} − v^{−j})^{2}. If this is the square of an element in 𝔽_{q}, then v^{j} − v^{−j} ∈ 𝔽_{q}, so 2v^{j} ∈ 𝔽_{q}. Since p > 2, this implies that v^{j} ∈ 𝔽_{q}, a contradiction. □

Recall that if r = p^{m} is a prime power and n > 1, the trace map Tr: 𝔽_{r^{n}} → 𝔽_{r} is the 𝔽_{r}-linear transformation defined by Tr(x) = x + x^{p^{m}} + x^{p^{2m}} + ⋯ + x^{p^{(n−1)m}}. The trace map has many well-known properties which can be found in any text on finite fields, such as [13]. In particular, Tr(xy) defines a nondegenerate symmetric 𝔽_{r}-valued bilinear form on 𝔽_{r^{n}} × 𝔽_{r^{n}}, making 𝔽_{r^{n}} an inner product space over 𝔽_{r}. Consequently, every subspace W determines an orthogonal subspace W^{⊥} of complementary dimension. Since the characteristic is nonzero, W and W^{⊥} may have nontrivial intersection. The kernel of Tr is exactly 𝔽_{r}^{⊥}.

In characteristic 2, the trace map leads to an elegant and useful description of the hyperbolic and elliptic elements. Let q be even, and for S ⊆ 𝔽_{q} − {0}, denote by S^{−1} the set consisting of the inverses of the elements of S. Since 0 is the unique parabolic element when q is even, both H^{−1} and E^{−1} are defined.

Lemma 10.2. Assume that 𝔽_{q} has characteristic 2, and let Tr: 𝔽_{q} → 𝔽_{2} be the trace map to 𝔽_{2}. Then Tr^{−1}(0) = H^{−1} ∪ {0} and Tr^{−1}(1) = E^{−1}.

Proof. Let α ∈ H. Then x^{2} + αx + 1 = 0 for some x ∈ 𝔽_{q}, so (xα^{−1})^{2} + (xα^{−1})+α^{−2} = 0. Since the traces of conjugate elements are equal, applying Tr to this equation gives Tr(α^{−2}) = 0 and hence Tr(α^{−1}) = 0. Conversely, if α ≠ 0 and Tr(α^{−1}) and hence Tr(α^{−2}) are 0, then we can write α^{−2} = β^{2} + β for some element β of 𝔽_{q} (see for example Theorem 2.25 of [13]), and multiplying by α^{2} shows that x^{2} + αx + 1 = 0 has a solution. We conclude that H^{−1} = Tr^{−1}(0) − {0}. Since 𝔽_{q} = {0} ∪ H ∪ E and E has q/2 elements, it follows that E^{−1} = Tr^{−1}(1). □

For odd characteristic, we do not know a result analogous to lemma 10.2. Lemma 10.2 has the following consequences.

Corollary 10.3. Let q be even and let W denote the subspace of 𝔽_{q} spanned by the subset {κ_{1}, …, κ_{r}} of 𝔽_{q}. Then (κ_{1}H ∩ ⋯ ∩ κ_{r}H)^{−1} ∪ {0} = W^{⊥}.

Proof. Using lemma 10.2, x ∈ (κH)^{−1} ∪ {0} = κ^{−1}(H^{−1} ∪ {0}) if and only if Tr(κx) = 0, that is, x ∈ (κ𝔽_{2})^{⊥}. So (∩κ_{i}H)^{−1} ∪ {0} = ∩(κ_{i}𝔽_{2})^{⊥} = W^{⊥}. □

Corollary 10.4. Let q be even and suppose that the elements κ_{1}, …, κ_{n} of 𝔽_{q} are linearly independent over 𝔽_{2}. Then

(a) ∩_{j=1}^{n}κ_{j}E contains q/2^{n} elements.

(b) For 1 ≤ m ≤ n, (∩_{i=1}^{m}κ_{i}H)∩(∩_{j=m+1}^{n}κ_{j}E) contains q/2^{n}−1 elements.

Proof. Corollary 10.3 shows that ∩_{i=1}^{n}κ_{i}H has q/2^{n} − 1 elements, which is part (b) for m = n. Now, let K_{i} = κ_{i}H ∪ {0}, so that ∩_{i=1}^{n}K_{i} = {0} ∪ (∩_{i=1}^{n}κ_{i}H) has 1/2^{n} elements. Write L_{i} for 𝔽_{q} − K_{i}, which is κ_{i}E. Inducting on n − m, we have 1 + |(∩_{i=1}^{m}κ_{i}H) ∩ (∩_{j=m+1}^{n}κ_{j}E)| = |(∩_{i=1}^{m}K_{i}) ∩ (∩_{j=m+1}^{n}L_{j})| = |(∩_{i=1}^{m}K_{i}) ∩ (∩_{j=m+2}^{n}L_{j})| − |(∩_{i=1}^{m+1}K_{i}) ∩ (∩_{j=m+2}^{n}L_{j})| = q/2^{n−1} − q/2^{n} = q/2^{n}, establishing the rest of (b). Part (a) follows from induction and part (b) since |(∩_{j=1}^{n}L_{j})| = |(∩_{j=2}^{n}L_{j})| − |K_{1} ∩ (∩_{j=2}^{n}L_{i})| = q/2^{n−1} − q/2^{n}. □

The type of an element of G_{i}— that is, parabolic, elliptic, or hyperbolic— is defined to be the type of its trace.

Consider an 𝔽_{q}^{3}-triple (α, β, γ) with α either hyperbolic or elliptic. Write α = x + x^{−1}, with x of the form u^{i} or v^{j} according as α is hyperbolic or elliptic. Since x ≠ x^{−1}, there is a unique pair (a, d) of elements of 𝔽_{q^{2}} such that a + d = β and ax + dx^{−1} = γ. Explicitly, a = (γ − βx^{−1})/(x − x^{−1}) and d = (βx − γ)/(x − x^{−1}). In the hyperbolic case, a and d lie in 𝔽_{q}, and we may select any b and c in 𝔽_{q} with bc = ad − 1. In the elliptic case, we compute that d = a^{q}. Since ad − 1 ∈ 𝔽_{q}, we may select any b ∈ 𝔽_{q^{2}} with b^{q+1} = ad − 1, and we may choose c = b^{q} for this b. Thus (α, β, γ) is the trace of a G_{i}-pair— a G_{0}-pair when A is hyperbolic, and a G_{1}-pair when it is elliptic— of the form

(A, B) = ((\begin{matrix}x & 0 \\ 0 & x^{−1} \end{matrix}) , (\begin{matrix}a & b \\ c & d \end{matrix})) ,

with a and d uniquely determined by Tr(A, B) and the choice of which of x and x^{−1} is considered to be x. We say that such pairs are in normal form. We note that this gives a computational proof of theorem 4.1, but more importantly, for a pair in normal form, it is straightforward to compute the following formula, which we call the Fundamental Equation:

Q(α, β, γ) = 2 − bc(α^{2} − 4)

The Fundamental Equation helps establish the following proposition that was mentioned in section 1.

Proposition 10.5. Let (α, β, γ) be an essential character. If 2 − Q(α, β, γ) is not a square in 𝔽_{q}, then the Markoff class of (α, β, γ) is the Fricke trace of a unique Nielsen class.

Since (A, B) is always Nielsen equivalent to (A^{−1}, B^{−1}), proposition 10.5 follows directly from theorem 4.3 and the following computational lemma.

Lemma 10.6. Let (A, B) be a G_{i}-pair with Q(A, B) ≠ 2. Then (A, B) is conjugate to (A^{−1}, B^{−1}) if and only if 2 − Q(A, B) is a square in 𝔽_{q}.

It seems interesting to compare lemma 10.6 with Lemma 3.4.5 of [10], which says that in SL(2, ℝ), A and B are hyperbolic elements whose axes cross if and only if tr([A, B]) < 2. Since tr([A, B]) = Q(A, B), this condition is equivalent (when Q(A, B) ≠ 0) to 2 − Q(A, B) being a square in ℝ. Of course, the isometry of ℍ^{2} that rotates through an angle of π fixing the intersection point of the axes conjugates (A, B) to (A^{−1}, B^{−1}).

Proof of lemma 10.6. When q is even, 2 − Tr(A, B) is always a square. On the other hand, Tr(A, B) = Tr(A^{−1}, B^{−1}), so theorem 4.3 shows that (A, B) is conjugate to (A^{−1}, B^{−1}), establishing the lemma. So we will assume that q is odd.

Assume first that at least one of A, B, or AB is not parabolic. By Nielsen moves we may assume that A is not parabolic. Conjugate to put (A, B) into normal form.

Suppose that A is hyperbolic. We have β = a + d and γ = tr(AB) = ax+dx^{−1}. If (A, B) is conjugate to (A^{−1}, B^{−1}), then the conjugating matrix

X must be of the form (\begin{matrix}0 & s \\ s^{−1} & 0 \end{matrix}), and XBX^{−1} = B^{−1} forces b = cs^{2}. Con-

versely, the condition b = cs^{2}, which allows the conjugation to be carried out, is equivalent to bc = (cs)^{2}, that is, bc is a square in 𝔽_{q}. By the Fundamental Equation, bc = (2 − Q(A, B))/(α^{2} − 4). Since α^{2} − 4 = (x − x^{−1})^{2}, bc is a square in 𝔽_{q} if and only if 2 − Q(A, B) is a square.

Suppose now that A is elliptic, and B = (\begin{matrix}a & b \\ b^{q} & a^{q} \end{matrix}). By lemma 10.1,

α^{2} − 4 is not a square in 𝔽_{q}, and the Fundamental Equation shows that 2 − Q(A, B) = b^{q+1}(α^{2} − 4), so we must show that (A, B) is conjugate to (A^{−1}, B^{−1}) if and only if b^{q+1} is not the square of an element of 𝔽_{q}.

The condition that XAX^{−1} = A^{−1} in G_{1} is equivalent to X being of

the form (\begin{matrix}0 & s \\ s^{q} & 0 \end{matrix}) where s^{q+1} = −1, and then XBX^{−1} = B^{−1} exactly when

s^{−2} = b^{q−1}. So we must show that these two equations hold for some s ∈ 𝔽_{q^{2}} if and only if b^{q+1} is not a square in 𝔽_{q}.

If they hold, then raising both sides of the second equation to the power −(q + 1)/2 gives s^{q+1} = (b^{q+1})^{(1−q)/2}. If b^{q+1} were a square in 𝔽_{q}, say b^{q+1} = c^{2}, then we would have −1 = (c^{2})^{(1−q)/2} = c^{1−q} = 1.

Suppose that b^{q+1} is not a square in 𝔽_{q}. Let s = b^{(1−q)/2}. Then s^{q+1} = (s^{2})^{(q+1)/2} = (b^{1−q})^{(q+1)/2} = (b^{q+1})^{(1−q)/2} = −1.

We may now assume that A and B (and AB, although that is not needed here) are parabolic. We work in G_{0}, and by conjugating we may assume

that A is of the form (\begin{matrix}ϵ & x \\ 0 & ϵ \end{matrix}), with ϵ = ±1 and x ≠ 0. It is straightforward

to check that A is conjugate to A^{−1} if and only if −1 is a square in 𝔽_{q}, say,

r^{2} = −1. In this case, any matrix of the form X = (\begin{matrix}r & s \\ 0 & −r \end{matrix}) conjugates A to A^{−1}. Writing B as (\begin{matrix}a & b \\ c & d \end{matrix}), the condition that XBX^{−1} = B^{−1} is equivalent

to r(d − a) = sc. If c ≠ 0, this can be satisfied, while if c = 0, then since B is parabolic we have a = d and again it can be satisfied. So (A, B) is conjugate to (A^{−1}, B^{−1}) exactly when −1 is a square in 𝔽_{q}. On the other hand, for γ = tr(AB) we have Q(A, B) = 4 + 4 + γ^{2} ± 4γ − 2 = 2 + (γ ± 2)^{2}, so 2 − Q(A, B) is a square if and only if −1 is a square. Again, the criterion holds. □

11. The geometry of the Q-levels

For each ℓ ∈ 𝔽_{q}, we denote Q^{−1}(ℓ) by Q_{ℓ}, and call it a level surface of Q, or a Q-level. We will examine intersections of the Q-levels with the “slices” of 𝔽_{q}^{3} having a fixed value for one of the coordinates. Since there are Nielsen automorphisms that interchange the coordinates, it is sufficient to focus initially on a single coordinate. The discussion is necessarily rather notation-intensive, so it may be helpful to read this section in tandem with the concrete examples presented in section 12.

For α ∈ 𝔽_{q}, define U_{α} to be the set of 𝔽_{q}-triples whose first entry is equal to α, and for ℓ ∈ 𝔽_{q}, define U_{α,ℓ} = Q_{ℓ} ∩ U_{α}. Denote by 𝔻 the subgroup of Aut(F_{2}) generated by {t, m} (where t and m were defined in sections 2 and 8 respectively). It is an infinite dihedral group, whose action on 𝔽_{q}^{3} preserves each U_{α,ℓ}. Any action of 𝔻 on a finite set induces an effective action of a finite quotient of 𝔻 that is a dihedral group (allowing the possibilities D_{2} = C_{2} × C_{2}, D_{1} = C_{2}, and D_{0} = {1}).

Finally, we define another quantity that will play an important role in our work. For α, ℓ ∈ 𝔽_{q} with α ≠ ±2, define

k(α, ℓ) = 1 − (ℓ − 2)(α^{2} − 4)^{−1} .

When the values of α and ℓ are fixed, as in the next proposition, we often just write k for k(α, ℓ).

Proposition 11.1. Let α ∈ 𝔽_{q} be hyperbolic, and write α = x + x^{−1} for some x ∈ 𝔽_{q}.

1) When k ≠ 0, that is, when ℓ ≠ α^{2} − 2, U_{α,ℓ} is a “hyperbola” with q − 1 points. Explicitly, if C_{α,ℓ} is the set of pairs (a, k/a) with a ∈ 𝔽_{q}−{0}, then sending (a, k/a) to (α, a+k/a, ax+k/(ax)) is a bijection from C_{α,ℓ} to U_{α,ℓ}. In these C_{α,ℓ}-coordinates, the action of 𝔻 on U_{α,ℓ} becomes m(a, k/a) = (ax, k/(ax)) and t(a, k/a) = (k/a, a).

2) When k = 0, that is, when ℓ = α^{2} − 2, U_{α,ℓ} is a “degenerate hyperbola” with 2q − 1 points, consisting of the two straight lines γ = xβ and γ = x^{−1}β. The action of 𝔻 fixes their intersection point (α, 0, 0), and on the other points it acts by m(α, β, xβ) = (α, xβ, x^{2}β), m(α, β, x^{−1}β) = (α, x^{−1}β, x^{−2}β), and t(α, β, xβ) = (α, β, x^{−1}β).

Proof. Assume first that k ≠ 0. Using the normal form and Fundamental Equation from section 10, we find that U_{α,ℓ} consists of the (α, β, γ) = (x + x^{−1}, a + d, ax + dx^{−1}) such that ad = k (with the ordered pair (a, d) uniquely determined by (α, β, γ) and the ordered pair (x, x^{−1})). The map ϕ: C_{α,ℓ} → U_{α,ℓ} defined by ϕ(a, k/a) = (α, a + k/a, ax + k/(ax)) is easily seen to be a bijection. Using the formulas t(α, β, γ) = (α, β, αβ − γ) and m(α, β, γ) = (α, γ, αγ −β) given near the beginning of section 8, one verifies that t ϕ(a, k/a) = ϕ(k/a, a) and m ϕ(a, k/a) = ϕ(ax, k/(ax)). Changing the choice of which member of the pair {x, x^{−1}} is considered to be x interchanges a and d, and the resulting formulas for the actions of m and t define the same effect.

When k = 0, the equation ℓ = Q(α, β, γ) works out to 0 = β^{2}−αβγ+γ^{2} = (β − xγ)(β − x^{−1}γ), giving the two intersecting straight lines for U_{α,ℓ}. Since α = x + x^{−1}, the action of m on the line γ = xβ is

m(α, β, xβ) = (α, xβ, (αx − 1)β) = (α, xβ, x^{2}β)

and similarly for the line γ = x^{−1}β. The action of t is

t(α, β, xβ) = (α, β, (α − x)β) = (α, β, x^{−1}β) .
□

Proposition 11.2. Let α ∈ 𝔽_{q} be elliptic, and write α = x + x^{q} with x ∈ 𝔽_{q^{2}} − 𝔽_{q} and x^{q+1} = 1.

1) When k ≠ 0, that is, when ℓ ≠ α^{2} − 2, U_{α,ℓ} is an “ellipse” with q + 1 points. Explicitly, if C_{α,ℓ} is the set of pairs (a, a^{q}) with a ∈ 𝔽_{q^{2}} and a^{q+1} = k, then sending (a, a^{q}) to (α, a + k/a, ax + k/(ax)) is a bijection from C_{α,ℓ} to U_{α,ℓ}. In these C_{α,ℓ}-coordinates, the action of 𝔻 on U_{α,ℓ} becomes m(a, k/a) = (ax, k/(ax)) and t(a, k/a) = (k/a, a).

2) When k = 0, that is, when ℓ = α^{2} − 2, U_{α,ℓ} is a “degenerate ellipse” consisting only of (α, 0, 0).

Proof. For k ≠ 0, calculating as in proposition 11.1 shows that U_{α,ℓ} consists of the (α, β, γ) = (x + x^{q}, a + a^{q}, ax + (ax)^{q}) such that a^{q+1} = k. In 𝔽_{q^{2}} there are q + 1 choices for a, and the map from C_{α,ℓ} to U_{α,ℓ} is again seen to be bijective, with the action as described. When k = 0, the factorization 0 = (β −xγ)(β −x^{−1}γ) has the unique solution (β, γ) = (0, 0) in 𝔽_{q} ×𝔽_{q}. □

Proposition 11.3. Let α ∈ 𝔽_{q} be parabolic.

1) If p > 2 and α = 2ϵ, then Q_{α,ℓ} is empty if ℓ − 2 is not a square, while if ℓ−2 = s^{2}, Q_{α,ℓ} is the set of triples of the form (2ϵ, β, ϵβ ±s), which is a pair of disjoint lines if ℓ ≠ 2 and a single line if ℓ = 2. The action of m is m(2ϵ, β, ϵβ ± s) = (2ϵ, ϵβ ± s, ϵ(ϵβ ± s) ± ϵs), so for ℓ ≠ 2, m preserves each line if ϵ = 1 and interchanges them if ϵ = −1. The action of t is t(2ϵ, β, ϵβ ± s) = (2ϵ, β, ϵβ ∓ s), so t interchanges the two lines. For ℓ = 2, t acts trivially, and m acts as an involution when ϵ = −1 and trivially when ϵ = 1.

2) For p = 2 and ℓ = s^{2}, Q_{α,ℓ} is the line consisting of the points of the form (0, β, β + s). The action of t is trivial and the action of m is

\begin{matrix}1 & u & 0 & 0 \\ u & u & 0 & 0 \\ 0 & 1 & u & u \\ α=0 & 0 & u & 1 \end{matrix}  \begin{matrix}1 & 0 & 0 & u \\ u & 0 & u & 0 \\ 0 & u & 0 & 0 \\ α=u & 0 & u & 1 \end{matrix}  \begin{matrix}1 & 0 & u & 0 \\ u & 0 & 0 & u \\ 0 & u & 0 & 0 \\ α=1 & 0 & u & 1 \end{matrix}

Figure 1. Slices for q = 3.

m(0, β, β + s) = (0, β + s, β), so m is an involution if ℓ ≠ 0 and acts trivially if ℓ = 0.

Proof. For p > 2 and α = 2ϵ, the equation ℓ = Q(α, β, γ) is ℓ−2 = (γ −ϵβ)^{2}, so Q_{α,ℓ} is empty when ℓ − 2 is not square. When ℓ − 2 = s^{2} ≠ 0, Q_{α,ℓ} consists of the two disjoint lines γ = ϵβ ± s. We have m(2ϵ, β, ϵβ ± s) = (2ϵ, ϵβ ± s, ϵ(ϵβ ± s) ± ϵs), so m preserves each line if ϵ = 1 and interchanges them if ϵ = −1. For t, we have t(2ϵ, β, ϵβ ± s) = (2ϵ, β, ϵβ ∓ s), so t interchanges the two lines. When ℓ − 2 = 0, we have γ = ϵβ, and the remarks about the action are easily checked.

For p = 2 any ℓ can be written uniquely as s^{2}. We find s^{2} = Q(α, β, γ) = (γ + β)^{2}, which says that γ = β + s and Q_{α,ℓ} is a line, and the action works out as stated. □

12. Examples of slices

Figure 1 shows the slices for 𝔽_{3} = {0, u, 1}. For each fixed value of α, the horizontal coordinate is β, the vertical coordinate is γ, and the (β, γ)-entry is Q(α, β, γ). The sixteen triples with Q(α, β, γ) = 0 are the single Aut(F_{2})- orbit of traces of generators. The element 0 is the unique elliptic element of 𝔽_{3}, indeed 0 = Z(9)^{2} + Z(9)^{−2}, where Z(9) is the multiplicative generator of 𝔽_{9} − {0} provided by GAP.

The slice for α = 0 is as described in proposition 11.2. We have k = 1 − (ℓ − 2)(0^{2} − 4) = ℓ − 1, so k = 0 occurs for U_{0,1}, giving the degenerate ellipse (0, 0, 0), while U_{0,0} and U_{0,u} are ellipses each containing four points. The elements α = u and α = 1 are parabolic, and their slices are as described in proposition 11.3.

Figure 2 shows the slices for 𝔽_{4} = {0, u, u^{2}, 1}. The elements u and u^{2} are elliptic. There is one parabolic element, 0, and one hyperbolic element 1. In the slice for α = 1, the degenerate hyperbola is U_{1,1}. The level surface U_{1} consists of the three inessential characters (1, 0, 0), (0, 1, 0), and (0, 0, 1), and one Aut(F_{2})-orbit of length 18.

Finally, figures 3 and 4 show the slices for 𝔽_{8} for α = u and α = u^{3}. Since u is elliptic, U_{u} contains one degenerate ellipse (u, 0, 0) and seven nondegenerate ellipses each containing nine points. The element u^{3} is hyperbolic, and U_{u^{3}} contains one degenerate hyperbola of fifteen points and seven nondegenerate hyperbolas of seven points each. In each figure we have indicated the degenerate conics in boldface.

CHARACTERS OF SL(2, q)-REPRESENTATIONS OF F_{2} 25

\begin{matrix}1 & 1 & u & u^{2} & 0 \\ u^{2} & u & 1 & 0 & u^{2} \\ u & u^{2} & 0 & 1 & u \\ 0 & 0 & u^{2} & u & 1 \\ α=0 & 0 & u & u^{2} & 1 \end{matrix}  \begin{matrix}1 & u & u & 1 & 1 \\ u^{2} & 1 & 0 & 0 & 1 \\ u & 0 & u & 0 & u \\ 0 & u^{2} & 0 & 1 & u \\ α=u & 0 & u & u^{2} & 1 \end{matrix}
\begin{matrix}1 & u^{2} & 1 & u^{2} & 1 \\ u^{2} & 0 & 0 & u^{2} & u^{2} \\ u & 1 & 0 & 0 & 1 \\ 0 & u & 1 & 0 & u^{2} \\ α=u^{2} & 0 & u & u^{2} & 1 \end{matrix}  \begin{matrix}1 & 0 & 1 & 1 & 0 \\ u^{2} & u^{2} & 1 & u^{2} & 1 \\ u & u & u & 1 & 1 \\ 0 & 1 & u & u^{2} & 0 \\ α=1 & 0 & u & u^{2} & 1 \end{matrix}

Figure 2. Slices for q = 4.

\begin{matrix}1 & u^{6} & u^{6} & 0 & u^{4} & 0 & u^{3} & u^{3} & u^{4} \\ u^{6} & u^{3} & u^{6} & 1 & u^{6} & u^{5} & u^{5} & 1 & u^{3} \\ u^{5} & u^{5} & u & u^{3} & u^{4} & u^{4} & u & u^{5} & u^{3} \\ u^{4} & u^{4} & u^{5} & 1 & 1 & 0 & u^{4} & u^{5} & 0 \\ u^{3} & 1 & u & u & u^{6} & 1 & u^{4} & u^{6} & u^{4} \\ u^{2} & u & 0 & u^{3} & u & 1 & u^{3} & 1 & 0 \\ u & 0 & u^{5} & 0 & u & u^{5} & u & u^{6} & u^{6} \\ 0 & u^{2} & 0 & u & 1 & u^{4} & u^{5} & u^{3} & u^{6} \\ α=u & 0 & u & u^{2} & u^{3} & u^{4} & u^{5} & u^{6} & 1 \end{matrix}

Figure 3. Slice for q = 8 and α = u.

1  u^{2} u^{4} u^{6} u^{2} u^{5} u^{6} u^{5} u^{4}
u^{6}  u u^{6} u 0 u^{6} 0 u^{5} u^{5}
u^{5} u^{4} u^{4} u^{3} u^{6} u^{3} 0 0 u^{6}
u^{4} u^{5} 1 u^{6} 1 u^{3} u^{3} u^{6} u^{5}
u^{3}  0 u^{6} u^{2} 1 1 u^{6} 0 u^{2}
u^{2} u^{3} u u^{2} u^{2} u^{6} u^{3} u u^{6}
u  1 u u u^{6} 1 u^{4} u^{6} u^{4}
0 u^{6} 1 u^{3} 0 u^{5} u^{4} u u^{2}
α=u^{3} 0 u u^{2} u^{3} u^{4} u^{5} u^{6} 1

Figure 4. Slice for q = 8 and α = u^{3}.

13. The case of even characteristic

Throughout this section we assume that p = 2, so that q = 2^{s} for some s. For x in 𝔽_{q}, we denote the unique square root x^{q/2} of x by \sqrt{x}. The expression k = 1 − (ℓ − 2)(α^{2} − 4)^{−1} from section 11 becomes k = 1 + ℓα^{−2}, so is 0 exactly when α = \sqrt{ℓ}. We introduce the notation

κ = 1 + \sqrt{ℓ}α^{−1}

for the square root of k.

In characteristic 2, the set of values of the second coordinate β dthat appear in triples in U_{α,ℓ} can be described in a somewhat simpler way. Denote this set by β(U_{α,ℓ}). Suppose first that α = u^{d} + u^{−d} is hyperbolic, so that proposition 11.1 applies. When κ = 0, it shows that β(U_{α,ℓ}) = 𝔽_{q}, while for κ ≠ 0 it gives

β(U_{α,ℓ}) = {a + κ^{2}/a | a ∈ 𝔽_{q}^{∗}} = {κ(a/κ + 1/(a/κ)) | a ∈ 𝔽_{q}^{∗}} = κ (H ∪ {0}) ,

where 𝔽_{q}^{∗} denotes 𝔽_{q} − {0} and as usual H denotes the set of hyperbolic elements of 𝔽_{q}. Similarly, applying proposition 11.2 when α = v^{d} + v^{−d} is elliptic shows that for κ = 0, β(U_{α,ℓ}) = {0} and for κ ≠ 0

β(U_{α,ℓ}) = κ (E ∪ {0})

although one detail should be mentioned. Since κ ∈ 𝔽_{q}, we have (a/κ)^{q+1} = k/κ^{q+1} = κ^{2}/κ^{2} = 1, so a/κ + 1/(a/κ) is indeed elliptic.

We will need to understand the β-coordinates of the 𝔻-orbits of U_{α,ℓ}, where 𝔻 is the subgroup of Aut(F_{2}) generated by {t, m}, as discussed near the beginning of section 11. To simplify notation, write h(i) for the element u^{i} + u^{−i}, noting that h(i) = h(−i) = h(i ± (q − 1)) and h(0) = 0. Now, fix a hyperbolic element α = h(d). Denote gcd(d, q − 1) by d_{0}, so that the order of u^{d} in 𝔽_{q}^{∗} is (q − 1)/d_{0}, which we denote by d_{1}.

For n ∈ ℤ, put

H_{d_{0}}(n) = {h(d_{0}i + n) | i ∈ ℤ} = {h(di + n) | i ∈ ℤ} .

We have H_{d_{0}}(n) = H_{d_{0}}(−n). For odd j, H_{d_{0}}(\frac{d_{0}−j}{2} ) = H_{d_{0}}(\frac{d_{0}+j}{2} ), since h(d_{0}i + \frac{d_{0}−j}{2} ) = h(d_{0}(−i) − \frac{d_{0}−j}{2} ) = h(d_{0}(−i − 1) + \frac{d_{0}+j}{2} ). Also, H_{d}(0) contains (d_{1} + 1)/2 points, while for 1 ≤ n ≤ (d_{0} − 1)/2, H_{d}(n) contains d_{1} points, and \{H_{d_{0}}(0), H_{d_{0}}(1), …, H_{d_{0}}(\frac{d_{0}−1}{2})\} is a partition of H ∪ \{0\}.

Let κh(i) ∈ β(U_{α,ℓ}). From the description of the action of m given in proposition 11.1, the β-coordinate of the image under m of a point with βcoordinate κ h(i) = κu^{i} + κ^{2}(1/(κu^{i})) is κu^{d+i} + κ^{2}(1/(κu^{d+i})) = κ h(d + i). Since t fixes the β-coordinate of each point, the set of β-coordinates of an m-orbit is the same set as the β-coordinates of the 𝔻-orbit that contains it. Thus we have obtained the following description.

Proposition 13.1. Assume that p = 2 and let α = h(d) be a hyperbolic element of 𝔽_{q}. Put d_{0} = gcd(d, q − 1) and d_{1} = (q − 1)/d_{0}. For the q − 1 values of ℓ with κ ≠ 0, β(U_{α,ℓ}) = κ(H ∪ {0}). Moreover,

1) The sets of β-coordinates of the 𝔻-orbits of U_{α,ℓ} are κH_{d_{0}}(0), κH_{d_{0}}(1), …, κH_{d_{0}}((d_{0} − 1)/2).

2) The set κH_{d_{0}}(0) contains (d_{1} + 1)/2 points, and each κH_{d_{0}}(n) for 1 ≤ n ≤ (d_{0} − 1)/2 contains d_{1} points.

By a very similar argument, putting e(d) = v^{d} + v^{−d} and

E_{d_{0}}(n) = {e(d_{0}i + n) | i ∈ ℤ}

we have

Proposition 13.2. Assume that p = 2 and let α = e(d) be an elliptic element of 𝔽_{q}. Put d_{0} = gcd(d, q + 1) and d_{1} = (q + 1)/d_{0}. For the q − 1 values of ℓ with κ ≠ 0, β(U_{α,ℓ}) = κ(E ∪ {0}). Moreover,

1) The sets of β-coordinates of the 𝔻-orbits of U_{α,ℓ} are κE_{d_{0}}(0), κE_{d_{0}}(1), …, κE_{d_{0}}((d_{0} − 1)/2).

2) The set κE_{d_{0}}(0) contains (d_{1} + 1)/2 points, and each κE_{d_{0}}(j) for 1 ≤ j ≤ (d_{0} − 1)/2 contains d_{1} points.

A hyperbolic (respectively, elliptic) element α is called transitive exactly when α = h(d) (respectively, α = e(d)) with gcd(d, q − 1) = 1 (respectively, gcd(d, q + 1) = 1). We remark that a matrix A ∈ SL(2, q) has order q − 1 or q + 1 in PSL(2, q) if and only if tr(A) is transitive, but we will not need this fact.

Write V_{α,ℓ} for U_{α,ℓ} − {(α, 0, 0)}. We have V_{α,ℓ} = U_{α,ℓ} except when κ = 0, and propositions 13.1 and 13.2 show that for κ = 0, β(V_{α,ℓ}) is 𝔽_{q}^{∗} when α is hyperbolic and is empty when α is elliptic. Propositions 13.1 and 13.2 show that for all transitive α, 𝔻 acts transitively on V_{α,ℓ}.

For two subsets X, Y ⊂ 𝔽_{q}^{3}, we write X ∼_{M} Y when every element of X is Markoff equivalent to every element of Y.

Proposition 13.3. Suppose that q−1 or q+1 is prime. Then for each ℓ ≠ 0, there is a Markoff equivalence class that contains V_{α,ℓ} for every transitive element α of 𝔽_{q}.

Proof. Fix ℓ. For any transitive element α, the elements of V_{α,ℓ} lie in a single 𝔻-orbit, so are Markoff equivalent.

Suppose for now that q − 1 is prime, so that every hyperbolic element is transitive. We fix a hyperbolic element α_{1}, and will prove that V_{α_{1},ℓ} ∼_{M} V_{α_{2},ℓ} for any transitive element α_{2}.

Write κ_{i} for 1 + \sqrt{ℓ} α_{i}. If α_{2} is elliptic, then we may assume that κ_{2} ≠ 0, since if κ_{2} = 0 then V_{α_{2},ℓ} is empty.

It is sufficient to prove that β(V_{α_{1},ℓ})∩β(V_{α_{2},ℓ}) contains a transitive element α_{3}. For then, each V_{α_{i},ℓ} contains a point of the form (α_{i}, α_{3}, γ_{i}) in V_{α_{i},ℓ}. The points (α_{3}, α_{i}, γ_{i}) lie in V_{α_{3},ℓ}, so are equivalent. Since (α_{i}, α_{3}, γ_{i}) ∼_{M} (α_{3}, α_{i}, γ_{i}), V_{α_{1},ℓ} ∼_{M} V_{α_{3},ℓ} ∼_{M} V_{α_{2},ℓ}.

If one of the κ_{i} is 0, say κ_{1}, then β(V_{α_{1},ℓ}) = 𝔽_{q} and V_{α_{1},ℓ} contains a point of the form (α_{1}, α_{2}, γ), hence α_{1} ∈ β(V_{α_{1},ℓ}) ∩ β(V_{α_{2},ℓ}). So we may assume that both κ_{i} are nonzero. If α_{2} is hyperbolic, then corollary 10.3 shows that κ_{1}H ∩κ_{2}H ∩H is nonempty, and if α_{2} is elliptic, it shows that κ_{1}H ∩κ_{2}E∩H is nonempty, giving the desired transitive element in β(V_{α_{1},ℓ}) ∩ β(V_{α_{2},ℓ}).

If q + 1 is prime, then all elliptics are transitive, and the argument is similar, with α_{1} selected to be elliptic with κ_{1} ≠ 0. □

The proof of theorem 13.5 will use the following easy observation about cyclic groups of prime order:

Lemma 13.4. Let S ⊆ C_{P} where P is prime, and let x ≠ 1. If xS = S, then S is either empty or S = C_{P}. Suppose that S is a nonempty, proper subset and xS ⊂ S ∪ {y}. Then S is of the form {x^{−1}y, x^{−2}y, …, x^{−n}y} for some n.

Proof. The first statement is immediate since x must be a generator of C_{P}. For the second statement, consider the subset S′ = {x^{−1}y, x^{−2}y, …, x^{−n}y}, where n + 1 is the minimal value for which x^{−(n+1)}y ∉ S. Then x(S − S′) = S − S′ so S′ = S. □

We can now prove Conjecture C for a restricted set of q.

Theorem 13.5. Let q = 2^{s} and suppose that one of q + 1 or q − 1 is prime and the other is 3 times a prime. Then there are exactly q − 1 Markoff classes of essential characters, classified by their Q-values.

The only case of theorem 13.5 for q + 1 prime is s = 4. For numbers of the form 2^{2k+1} + 1 are always divisible by 3, while if s = 2k then q − 1 factors as (2^{k} − 1)(2^{k} + 1) and is of the form 3p_{1} only when k = 2. (Actually, the proof of theorem 13.5 adapts, in a rather degenerate manner, to q = 4.) For q − 1 prime, theorem 13.5 applies when s ∈ {3, 5, 7, 13, 17, 19, 31, 61, 127}, and perhaps for other values as well. It might apply to infinitely many cases, of course it is a well-known open problem even to determine whether there are infinitely many primes among the Mersenne numbers 2^{s} − 1.

Proof of theorem 13.5. From theorem 5.1 we know that the Q-values of the Markoff classes are all of 𝔽_{q} − {0}.

Fix ℓ ∈ 𝔽_{q} − {0} and suppose first that q − 1 is prime and q + 1 = 3p_{1} with p_{1} prime. Since q − 1 is prime, all hyperbolic elements are transitive, and proposition 13.3 shows that there is a Markoff class M(ℓ) containing V_{α,ℓ} for all transitive elements α. For transitive α, the only time a triple in any of the slices U_{α,ℓ} is not contained in V_{α,ℓ} is when κ = 0 and the triple is (\sqrt{ℓ}, 0, 0). This triple is the trace of pairs which generate dihedral subgroups and hence is not essential. So it remains to show that M(ℓ) contains the essential characters in U_{α,ℓ} for all nontransitive α with κ ≠ 0. Since every essential triple has at least two nonzero coordinates, we may further assume that α is nonzero.

Using the notation of proposition 13.2, the set of nontransitive elements is E_{3}(0) ∪ E_{p_{1}}(0). Since 1 = v^{p_{1}} + v^{−p_{1}}, E_{p_{1}}(0) = {0, 1}. Therefore the set of nontransitive elements is E_{3}(0) ∪ {1}. It contains (p_{1} + 3)/2 elements, unless q = 8, in which case E_{3}(0) = {0, 1} contains (p_{1} + 1)/2 elements.

Fix an essential character (α, β, γ) ∈ U_{α,ℓ} with α nontransitive. Necessarily its corresponding κ ≠ 0, since as we have seen U_{\sqrt{ℓ},ℓ} contains no essential character.

Since (α, β, γ) is essential, at least two of its coordinates are nonzero, and by Markoff equivalence we may assume that they include α and β. Also, since the coordinates do not all lie in a proper subfield, we may assume that α ≠ 1. That is, α ∈ E_{3}(0) − E_{p_{1}}(0) and β ≠ 0.

By proposition 13.2, the set of β-coordinates for the 𝔻-orbit of (α, β, γ) is κE_{3}(0) ∪ κE_{3}(1), with each of these two sets being the set of β-coordinates for some 𝔻-orbit of U_{α,ℓ}. If β ∈ κE_{3}(1), then since κE_{3}(1) contains p_{1} values, and there are only (p_{1} + 3)/2 nontransitive elements (or (p_{1} + 1)/2, if q = 8), (α, β, γ) is Markoff equivalent to some (α, β′, γ′) with β′ transitive, so (α, β, γ) ∈ M(ℓ). So we may assume that β ∈ κE_{3}(0) ⊂ E_{3}(0) ∪ {1} and κE_{3}(0) ⊆ E_{3}(0) ∪ {1}. If q = 8 this is impossible since κ ≠ 1. Otherwise, lemma 13.4 shows that E_{3}(0) is of the form {0, κ^{−1}, κ^{−2}, …, κ^{−(p_{1}−1)/2}}. But this is a contradiction, since E_{3}(0) is closed under the Frobenius automorphism.

Suppose now that q + 1 is prime and q − 1 = 3p_{1}. We proceed as before, interchanging the roles of elliptic and hyperbolic. The set of nontransitive elements is H_{3}(0)∪{1}, and contains (p_{1}+1)/2 elements, so we may examine an essential triple (α, β, γ) with α a nontransitive hyperbolic other than 1, and β ≠ 0. If α = \sqrt{ℓ} so that κ = 0, then according to proposition 11.1 the β-sets of the 𝔻-orbits in U_{α,ℓ} are of the form {β, u^{3}β, u^{6}β, …, u^{q−4}β}, so contain p_{1} elements. At least one of these must be transitive, so we may assume that κ ≠ 0. The remainder of the proof is then analogous to the case when q − 1 was prime. □

As explained in section 1, Conjecture C implies all of the conjectures for these values of q, so we the following is a consequence of theorem 13.5:

Corollary 13.6. Suppose that one of q −1 or q +1 is prime and the other is 3 times a prime. Then there are exactly q − 1 Nielsen classes of generating pairs, classified by their trace invariants.

As far as extending these results to more values of q, we have little idea how to make headway for odd q, as the even case relied on several major simplifications that do not seem to have analogues in the odd case. For the even case, a roadblock to extending our method is our inability to make some usable statement about the effect of the element m on β-coordinates, specifically about the values of i and j that are obtained when elements of the form κ(a+κ/a) are rewritten in the form u^{i}+u^{−i} or v^{j}+v^{−j}. For the first main step, proposition 13.3, one can weaken the hypotheses a bit by more careful use of corollary 10.3 in the proof. Since this gives some additional information about Markoff equivalence and its proof is fairly short, we give one such result here. It applies to many values of q such as 2^{11}, for which 2^{11} − 1 = 23 · 89.

Proposition 13.7. Suppose that no more than 3q/16−2 hyperbolic elements are nontransitive. Then for each ℓ ≠ 0, there is a Markoff equivalence class M(ℓ) such that for every transitive element α of 𝔽_{q}, U_{α,ℓ} ⊂ M(ℓ).

Proof. Arguing as in the proof of proposition 13.3, it suffices to reach a contradiction assuming that β(V_{α_{1},ℓ})∩β(V_{α_{2},ℓ}) contains no transitive hyperbolic element. Let α_{3} be a transitive hyperbolic element such that κ_{3} is not in the 𝔽_{2}-subspace of 𝔽_{q} spanned by κ_{1} and κ_{2}.

Assume first that α_{2} is hyperbolic. By corollary 10.4, κ_{1}H ∩ κ_{2}H ∩ H has exactly q/8 − 1 elements, which are assumed nontransitive, each κ_{i}H ∩ κ_{3}H ∩ H has q/8 − 1 elements, and κ_{1}H ∩ κ_{2}H ∩ κ_{3}H ∩ H has q/16 − 1 elements. For each i, the q/16 elements of κ_{i}H ∩ κ_{3}H ∩ H that are not in κ_{1}H ∩ κ_{2}H ∩ κ_{3}H ∩ H cannot all be nontransitive, since then the set of nontransitive hyperbolic elements would contain the q/8 − 1 elements of κ_{1}H ∩ κ_{2}H ∩ H, plus these additional q/16.

When α_{2} is elliptic, the argument is exactly the same except that κ_{2}E is used in place of κ_{2}H. □

Of course, there is an analogous result assuming that there is a sufficient density of transitive elliptic elements.

Finally, as remarked in section 1, the key role played by transitive elements, while possibly an artifact of our approach to theorem 13.5, does give some reason for caution. The cases in which the conjectures are known to hold, that is, q ≤ 101 and the cases of theorem 13.5, all have rather high densities of transitive elements, so at least in this sense they are not representative of the general case. For very large q, this density can be arbitrarily close to 0.

14. The case of PSL(2, q)

In this section, we will adapt the conjectures to the case of PSL(2, q). Since PSL(2, q) = SL(2, q) when q is even, we will assume throughout this section that q is odd.

For now, we consider coefficients in an arbitrary field F. We have already noted that even when (A, B) represents a pair in PSL(2, F), so that A and B are only defined up to sign, the trace of [A, B] is well-defined. To make the Fricke trace Tr(A, B) well-defined on Nielsen classes in G_{2}(PSL(2, F)), it is sufficient to extend Markoff equivalence by adding the additional involutions (α, β, γ) → (−α, β, −γ) and (α, β, γ) → (α, −β, −γ). This extends the PGL(2, ℤ)-action on F^{3} to an action of (C_{2} × C_{2}) ∘ PGL(2, ℤ) on F^{3}. We call the resulting relation weak Markoff equivalence.

We will use \overline{N} and \overline{M} to denote the Nielsen classes for PSL(2, F) and the set of weak Markoff classes in F^{3}, so that there are natural surjections N → \overline{N} and M → \overline{M}. For finite F, at least, the following conjecture seems reasonable:

Conjecture P (No essential difference between SL and PSL). N → \overline{N} and M → \overline{M} are bijections.

Specializing to the case F = 𝔽_{q}, Conjecture A implies that N → \overline{N} is bijective, since we have a composition N → \overline{N} → \{Higman invariants\} with the first map surjective. Similarly, Conjecture C implies that M → \overline{M} is bijective. Thus Conjecture A implies Conjecture P. Similarly, Conjecture W implies that T → \overline{T} is a bijection, where \overline{T} denotes the T -systems of PSL(2, q).

On the other hand, versions of the conjectures for PSL(2, q) imply weak forms of the conjectures, by means of the following observation:

Proposition 14.1. The natural maps N → \overline{N} and M → \overline{M} are (≤ 2)-to-1.

Proof. Suppose that (A, B) and (A′, B′) in G_{2}(SL(2, q)) are Nielsen equivalent as elements of G_{2}(PSL(2, q)). A sequence of Nielsen moves changing (A′, B′) to (A, B) up to signs changes (A′, B′) to one of (A, B), (−A, B), (A, −B), or (−A, −B).

If A has odd order k, then (−A)^{k} = −I, so (−A, B) ∼ (−A, −B), where ∼ indicates Nielsen equivalence. On the other hand, if A has even order 2k, then A^{k} = −I so (A, B) ∼ (A, −B). By the same reasoning applied to B, either (A, −B) ∼ (−A, −B) or (A, B) ∼ (−A, B). Each of the four possible combinations lead to (at least) three of (A, B), (−A, B), (A, −B), or (−A, −B) being Nielsen equivalent, showing that N → \overline{N} is (≤ 2)-to-1.

Since the four equivalent 𝔽_{q}-triples (α, β, γ), (−α, β, −γ), (α, −β, −γ), and (−α, −β, γ) are the Fricke traces of (A, B), (−A, B), (A, −B), and (−A, −B), the previous argument shows that they lie in at most two Markoff classes. It follows that M → \overline{M} is (≤ 2)-to-1. □

Consider, for example, the following conjecture:

Conjecture PA (Higman invariant classifies Nielsen classes). Two generating pairs (A, B) and (A′, B′) of PSL(2, q) are Nielsen equivalent if and only if [A, B] is conjugate to [A′, B′] or to [B′, A′] in SL(2, q).

Conjecture PA is that the latter map in N → \overline{N} → \{Higman invariants\} is a bijection, and proposition 14.1 then implies that N → {Higman invariants} is (≤ 2)-to-1. The patterns are similar for Conjectures C and W.

The argument in section 6 showing the equivalence of Conjectures A and B applies to the analogous projective versions.

As for Conjecture B′, the Fricke trace Tr: G_{2}(SL(2, q)) → 𝔽_{q}^{3} carries each Nielsen equivalence class onto an entire Markoff class, since the Aut(F_{2})- action on 𝔽_{q}^{3} that produces Markoff equivalence is induced by the Aut(F_{2})- action on G_{2}(SL(2, q)) that produces Nielsen equivalence. So two different elements of M have the same image in \overline{M} if and only if two different elements of N have the same image in \overline{N}. This shows that Conjecture B′ implies the analogous statement for Tr: \overline{N} → \overline{M}.

15. Almost free actions

We call an action of a (nontrivial) finite group G on a compact surface F fixed-point-transitive if G acts transitively on ∪_{1≠g∈G} Fix(g). If in addition, the fixed-point set is nonempty, we say that the action is almost free. These may be regarded as the actions that are as close as possible to being free. For closed F, they correspond exactly to the free actions on bounded surfaces which act transitively with nontrivial stabilizers on the set of boundary components.

From now on, we assume implicitly that all surfaces are closed and orientable, and that all actions preserve orientation. Fix an almost free action of G on a surface F of genus g. The stabilizers of the fixed points are conjugate cyclic subgroups of G of some order n ≥ 2. The quotient orbifold O has one order-n cone point, and underlying manifold |O| an orientable surface of some genus g_{0}. The orbifold fundamental group π_{1}^{orb}(O), that is, the set of lifts of elements of G to the universal cover of F, is an extension 1 → π_{1}(F) → π_{1}^{orb}(O) → G → 1; explicitly, π_{1}^{orb}(O) can be given by a presentation of the form ⟨a_{1}, b_{1}, …, a_{g_{0}}, b_{g_{0}} | ( ∏_{i=1}^{g_{0}}[a_{i}, b_{i}])^{n} = 1⟩.

Since π_{1}(F) is torsionfree, the image of ∏_{i=1}^{g_{0}}[a_{i}, b_{i}] in G must have order n. Therefore G is nonabelian.

Using orbifold Euler characteristic, we have χ_{orb}(O) = χ(|O|)+ \frac{1}{n} −1 and χ(F) = |G| χ_{orb}(O), giving g_{0} = \frac{g−1}{|G|} + \frac{n+1}{2n}. This yields immediately:

1) g ≥ 2.

2) If g ≤ |G|, then g_{0} = 1 and g = 1 + \frac{n−1}{2n}|G|.

When g ≤ |G| we call the almost free action large. Our main result shows that large almost free actions are classified by Nielsen equivalence classes. As usual, G_{2}(G) will denote the set of generating pairs of G. Recall that two actions φ_{i}: G → F_{i}, i = 1, 2 , are weakly equivalent if there are a diffeomorphism h: F_{1} → F_{2} and an automorphism α: G → G so that φ_{1}(g) = h^{−1}φ_{2}(α(g)) h for all g ∈ G, and are called equivalent if this can be achieved with α the identity automorphism.

Theorem 15.1. Let G be a nonabelian group. Then the equivalence classes (respectively, weak equivalence classes) of large almost free actions of G on closed orientable surfaces correspond bijectively to the Nielsen classes (respectively, T -systems) of G_{2}(G). For the action on a surface F corresponding to the equivalence class of a generating pair {A, B}, the order of the stabilizers of the fixed points equals the order n of [A, B] in G. Moreover, n = \frac{|G|}{|G|+χ(F)}, or equivalently the genus of F is 1 + \frac{n−1}{2n} |G|.

In particular, when G_{2}(G) is empty, the theorem implies that G does not act almost freely on any F.

Proof of theorem 15.1. Denote by O_{n} the orbifold with underlying manifold the torus, and one cone point of order n, so that π_{1}^{orb}(O_{n}) = ⟨A, B | [A, B]^{n} = 1⟩. We have observed that the quotient orbifold O of any large almost free action of G is homeomorphic to some O_{n}. The image of the standard generating pair (A, B) of π_{1}^{orb}(O_{n}) in G is an element of G_{2}(G). The Nielsen class of this element is independent of the choice of identification of O with O_{n}. To see this, we note first that any other identification differs from this previous one by an orbifold homeomorphism, which induces an automorphism of π_{1}^{orb}(O_{n}). It is known that all automorphisms of π_{1}^{orb}(O_{n}) are induced by automorphisms of the free group on {A, B}, so different choices produce Nielsen equivalent pairs for (A, B) in π_{1}^{orb}(O_{n}), and hence produce Nielsen equivalent elements of G_{2}(G).

There are two fine points here. The first concerns the fact that automorphisms of π_{1}^{orb}(O_{n}) are induced by automorphisms of F_{2}, or equivalently that any two generating pairs of π_{1}^{orb}(O_{n}) differ by Nielsen moves. The general problem of classifying generating pairs for two-generator Fuchsian groups is quite difficult. As far as we know, the case of the groups ⟨A, B | [A, B]^{n} = 1⟩, which we use here, appears first as Lemma 3 of [21], but much of that paper is incorrect. The later [22] gives a full algebraic solution of the classification and a discussion of the troubled history of the problem, in particular the case we need appears as Theorem 1(2.1) there. See also [8].

The second fine point is that the automorphism of π_{1}^{orb}(O_{n}) preserves π_{1}(F) and induces an inner automorphism on G = π_{1}^{orb}(O_{n})/π_{1}(F), since it is induced by a homeomorphism that is induced by an equivalence of the actions. When it is only a weak equivalence, an outer automorphism of G may be induced, so the generating pairs of G = π_{1}^{orb}(O_{n})/π_{1}(F) may map to elements of G_{2}(G) that differ by an automorphism of G, and the pairs in G_{2}(G) need only be T -equivalent. Thus the assignment is indeed welldefined as a function from equivalence classes (respectively, weak equivalence classes) of actions to Nielsen classes (T -systems) in G_{2}(G).

To see that this assignment is injective, suppose that two actions on surfaces F_{1} and F_{2} are assigned Nielsen equivalent elements (\overline{A_{1}}, \overline{B_{1}}) and (\overline{A_{2}}, \overline{B_{2}}) of G_{2}(G). As we have seen, we may assume that they are actions by orbifold covering transformations of covers of the same quotient orbifold O_{n}. A sequence of Nielsen moves in G taking (\overline{A_{1}}, \overline{B_{1}}) to (\overline{A_{2}}, \overline{B_{2}}) lifts to a sequence of Nielsen moves in G_{2}(π_{1}^{orb}(O_{n})) taking (A, B) to some (A′, B′) which also projects to (\overline{A_{2}}, \overline{B_{2}}). These Nielsen moves are induced by orbifold homeomorphisms of O_{n} (the product replacements by Dehn twists, the inversions and the interchange of generators by orientation-reversing involutions). So there is an orbifold homeomorphism of O_{n} that induces an isomorphism from the extension 1 → π_{1}(F_{1}) → π_{1}^{orb}(O_{n}) → G → 1 to the extension 1 → π_{1}(F_{2}) → π_{1}^{orb}(O_{n}) → G → 1. This isomorphism of extensions is the identity on G, so the lifted homeomorphism is an equivalence of the actions of G as covering transformations. For weak equivalence, the argument is the same except that the isomorphism of extensions may induce a nontrivial isomorphism of the quotient groups G, so the lifted homeomorphism may be only a weak equivalence of the actions of G as covering transformations.

Finally, a generating pair \{\overline{A}, \overline{B}\} of G for which [\overline{A}, \overline{B}] has order n defines a surjective homomorphism π_{1}(O_{n}) → G. In a one-relator group, every torsion element is conjugate to a power of the relator (see for example Theorem IV.5.2 of [14]). Therefore the kernel of the homomorphism is torsionfree, so the covering orbifold of O_{n} corresponding to the kernel is a manifold on which G acts almost freely. The Euler characteristic calculations shown above give its genus to be 1 + \frac{n−1}{2n} |G|. □

Using these results, we can easily classify the orientation-preserving large fixed-point transitive actions on the surface of genus 3. The formula g = 1 + \frac{n−1}{2n}|G| becomes |G| = \frac{4n}{n−1}, and only the values n = 2, 3, and 5 yield integers for |G|, giving respectively 8, 6, and 5. The latter cannot occur since G is nonabelian, so G must be one of D_{3}, D_{4}, or Q_{8}. For D_{3} there is a generating pair with [A, B] of order 3, and for D_{4} and Q_{8} there are generating pairs with [A, B] of order 2, so fixed-point transitive actions of these three groups exist. In all three cases, it is not difficult to check that G_{2}(G) has only one Nielsen class (the dihedral cases appear as theorem 14 of [18]), so these actions are unique up to equivalence.

Another interesting example is G = A_{5}. Regard it as PSL(2, 4). Theorem 15.1 shows that the orientation-preserving large fixed-point-transitive actions of A_{5} are classified by the Nielsen equivalence classes of generating pairs of PSL(2, 4). These are are well-known; in the framework of our theory we know they are classified by their trace invariants 1, u, and u^{2} in 𝔽_{4}. The element 1 = u + u^{−1} is hyperbolic, and is the trace of matrices of order n = 3, the order of u, so the Nielsen class with trace invariant 1 corresponds to a fixed-point transitive action of A_{5} on the surface of genus g = 1+ \frac{3−1}{2·3} ·60 = 21. The elements u = v^{2}+v^{−2} and u^{2} = v+v^{−1} are elliptic (where v = Z(8)^{3} as in section 10) and are the traces of matrices of order n = 5, the orders of v and v^{2}. These correspond to two equivalence classes of fixed-point transitive actions on the surface of genus g = 1+ \frac{5−1}{2·5} ·60 = 25, which are weakly equivalent.

References

1. Kenneth P. Bogart, An obvious proof of Burnside’s lemma, Amer. Math. Monthly 98 (1991), 927–928.

2. B. H. Bowditch, A proof of McShane’s identity via Markoff triples, Bull. London Math. Soc. 28 (1996), 73–78.

3. B. H. Bowditch, Markoff triples and quasi-Fuchsian groups, Proc. London Math. Soc. (3) 77 (1998), 697–736.

4. A. Costa and D. McCullough, Orientation-reversing free actions on handlebodies, J. Pure Appl. Alg. 204 (2006) 155-169.

5. L. E. Dickson, Linear groups: with an exposition of the Galois field theory, Leipzig (1901), reprinted by Dover Publications, Inc., New York (1958).

6. J. Dieudonné, On the automorphisms of the classical groups, with a supplement by Loo-Keng Hua, Mem. Amer. Math. Soc. 2 (1951), 1–122.

7. GAP: Groups, Algorithms, and Programming, available at the St. Andrews GAP

website http://turnbull.mcs.st-and.ac.uk/ gap/ .

8. J. Gilman, Two-generator discrete subgroups of PSL(2, R), Mem. Amer. Math. Soc. 117 (1995), no. 561, x+204 pp.

9. H. Glover and D. Sjerve, The genus of PSL_{2}(q), J. Reine Angew. Math. 380 (1987), 59–86.

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

11. R. Guralnick and I. Pak, On a question of B. H. Neumann, Proc. Amer. Math. Soc. 131 (2003), 2021–2025.

12. Loo-Keng Hua, On the automorphisms of the symplectic group over any field, Ann. of Math. (2) 49, (1948), 739–759.

13. R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, Cambridge, (1986).

14. R. C. Lyndon and P. E. Schupp, Combinatorial group theory, Springer-Verlag, 1977.

15. A. M. Macbeath, Generators of the linear fractional groups, Number Theory (Proc. Sympos. Pure Math., Vol. XII, Houston, Tex., 1967), Amer. Math. Soc., Providence, R.I. (1969) 14–32.

16. D. McCullough, Exceptional subgroups of SL(2, F), preprint available at

www.math.ou.edu/ dmccullough/

17. D. McCullough, GAP programs for The action of the modular group on characters of SL(2, q)-representations of F_{2}, available at www.math.ou.edu/ dmccullough/

18. D. McCullough and M. Wanderley, Free actions on handlebodies, J. Pure Appl. Algebra. 181 (2003), 85–104.

19. P. Neumann, A lemma which is not Burnside’s, Math. Sci. 4 (1979), 133–141

20. J. Nielsen, Die Isomorphismengruppe der allgemeinen unendlichen Gruppe mit zwei Erzeugenden, Math. Ann. 78 (1918), 385–397.

21. N. Purzitsky and G. Rosenberger, Two generator Fuchsian groups of genus one, Math. Z. 128 (1972), 245-251, with correction Math. Z. 132 (1973), 261–262.

22. G. Rosenberger, All generating pairs of all two-generator Fuchsian groups, Arch. Math. 46 (1986), 198–204.

23. O. Schrier and B. L. van der Waerden, Die Automorphismen der projektiven Gruppen, Abh. Math. Sem. Univ. Hamburg 6 (1928), 303–322.

24. M. Suzuki, Group Theory, vol. I, Springer-Verlag, 1982.

Department of Mathematics, University of Oklahoma, Norman, Oklahoma 73019, USA

E-mail address: dmccullough@math.ou.edu
URL: www.math.ou.edu/ dmccullough/

Departmento de Matematica, Universidade Federal de Pernambuco, Av. Prof. Luiz Freire, s/n, Cid. Universitaria-Recife-PE, CEP 50.740-540, Brazil

E-mail address: mvw@dmat.ufpe.br