arXiv:1312.1261v3 [math.GR] 12 Nov 2016

Decision problems, complexity, traces, and representations

1

Decision problems, complexity,
traces, and representations
Sean Lawton, Larsen Louder, D. B. McReynolds
November 15, 2016

Abstract
In this article, we study connections between representation theory and efficient solutions to the
conjugacy problem on finitely generated groups. The main focus is on the conjugacy problem
in conjugacy separable groups, where we measure efficiency in terms of the size of the quotients
required to distinguish a distinct pair of conjugacy classes.

1

Introduction

Given an infinite, finitely presented group Γ, two basic decision problems posed by Dehn [21] in 1911
are the word and conjugacy problems. In 1927, in solving the word problem for free groups, Schreier
[61] proved that free groups are residual finite. That seems to be the first connection between decision
problems and residual properties. In 1940, Mal’cev [47] proved that finitely presented, residually finite
groups have a solution to the word problem, and noted a similar connection between the conjugacy
problem and conjugacy separability in [48].
Once an algorithm to solve the word or conjugacy problem is given, one can study the efficiency of
the algorithm. For free groups, it is straightforward to see that both problems have algorithms that
terminate in linear steps as a function of word length via cyclic reduction. Bou-Rabee [8] introduced
a function FΓ (n) that quantified the efficiency of the solution to the word problem on Γ given by
residual finiteness. We say a group Γ is residually finite if for each γ ∈ Γ with γ 6= 1, there exists
a homomorphism ϕ : Γ → Q with |Q| < ∞ and ϕ (γ ) 6= 1. The function introduced by Bou-Rabee
measures the efficiency by the size of the groups Q needed over all the elements of length at most n
in the verification of residual finiteness. Several papers have addressed the growth rate of this function
for various classes of groups; [8], [9], [10], [11], [13], [14], [15], [17], [19], [35], [36], [37], [38], [51],
[52], [59], and [67]. By work of Mal’cev [47], a finitely generated linear group Γ is residually finite. In
[15], using an effective proof of [47], it was shown that FΓ (n)  nd where d depends only on a linear
realization of Γ.
We say that Γ is conjugacy separable if for any non-conjugate γ , η ∈ Γ, there exists a homomorphism
ϕ : Γ → Q with ϕ (γ ), ϕ (η ) not conjugate in Q and |Q| < ∞. One of the goals of this article is to extend
some of the above results with conjugacy separability in place of residual finiteness. Unfortunately,
issues arise immediately. Stebe [65] proved that the linear groups SL(n, Z) are not conjugacy separable
for n > 2. More generally, the groups of integer points of a semi-simple Q–algebraic group with the

Decision problems, complexity, traces, and representations

2

congruence subgroup property are never conjugacy separability; see [54, Ch 8]. However, free and
surface groups [65, 46] (see also [50] and [69]), virtual polycyclic groups [23, 58], fundamental groups
of compact, orientable 3–manifolds [31], and right-angled Artin groups [66] are conjugacy separable;
see also [20] for more examples.
A faithful linear representation reduces the verification of the non-triviality of an element to showing
some matrix coefficient is non-zero. We want a similar solution to the conjugacy problem through
representation theory and must replace the coefficients of the matrix by conjugacy invariants. We use
traces and the following properties to effectively distinguish conjugacy classes:
(A) There exists an integer n and ρ ∈ Hom(Γ, SL(n, C)) such that Tr(ρ (γ )) 6= Tr(ρ (η )) for any
non-conjugate γ , η ∈ Γ.
(B) For each γ ∈ Γ, there exists ργ ∈ Hom(Γ, SL(nγ , C)) such that Tr(ργ (γ )) 6= Tr(ργ (η )) for every
non-conjugate η ∈ Γ.
(C) For any finite set S = {γi }si=1 of conjugacy classes in Γ, there exists ρS ∈ Hom(Γ, SL(nS , C))
such that Tr(ρS (γi )) 6= Tr(ρS (γ j )) for γi , γ j ∈ S and i 6= j.
(D) For each non-conjugate γ , η ∈ Γ, there exists ργ ,η ∈ Hom(Γ, SL(nγ ,η , C)) such that Tr(ργ ,η (γ )) 6=
Tr(ργ ,η (η )).
+3 (D) ks
+3 (C). All of these implications are immediate from the defini+3 (B)
We have (A)
tions except for the equivalence of (C) and (D), which is elementary. We thank Greg Kuperberg for
pointing that out to us. We say one of the above (B), (C), or (D) is uniformly satisfied if nγ , nγ ,η , or
nS is bounded over all choices of γ , {γ , η }, or S. That is, the dimension of the representations do not
depend on γ , {γ , η }, or S. In those cases, we say Γ uniformly has (B), (C), or (D). Note, it is less clear
if uniform (C) and uniform (D) are equivalent.

Remark 1. Since SLn and consequently Hom(Γ, SLn ) are Z-schemes, the above properties (A)-(D)
can be restated with C replaced by any algebraically closed field F. When we are not working over C
we will refer to these properties as (A′ )-(D′ ). For example, with respect to a fixed algebraically closed
field F, (A′ ) states there exists an integer n, and ρ ∈ Hom(Γ, SL(n, F)) such that Tr(ρ (γ )) 6= Tr(ρ (η ))
for any non-conjugate γ , η ∈ Γ. Properties (B′ )-(D′ ) are similarly written.
Theorem 1.1. If Γ uniformly has (C), then Γ has (A). In fact, if Γ uniformly has (D) for some n0 and
Hom(Γ, SL(n0 , C)) is irreducible, then Γ has (A).
Throughout, by a surface group, we mean the fundamental group of a closed, orientable surface of
genus g ≥ 2. We have the following corollary:
Corollary 1.2. If Γ is either a finitely generated free group or a surface group, then Γ uniformly has (D)
if and only if Γ has (A). Moreover, for any connected algebraic subgroup G < SL(n, C), the following
are equivalent for a free group Fr of rank r:
(a) For each ρ ∈ Hom(Fr , G), there exist non-conjugate γ , η ∈ Fr with Tr(ρ (γ )) = Tr(ρ (η )).
(b) There exist non-conjugate γ , η ∈ Γ such that Tr(ρ (γ )) = Tr(ρ (η )) for each ρ ∈ Hom(Fr , G).

Decision problems, complexity, traces, and representations

3

We also record the following result which first appeared in Bass–Lubotzky [2, Prop. 3.1] where they
also prove the converse.
Proposition 1.3 (Bass–Lubotzky). If Γ satisfies (D), then Γ is conjugacy separable.
Similar to the function FΓ (n) associated to the word problem using residual finiteness, we define a
function ConjΓ (n) for the conjugacy problem using conjugacy separability (see §2 for the definition).
Theorem 1.4. If Γ has (A), then ConjΓ (n)  nd for some d ∈ N. Moreover, for some n0 ∈ N, the finite
quotients used in proving conjugacy separability of Γ are subgroups of the finite groups SL(n0 , F p )
where F p denotes a field of prime order p.
We define a relative version of the function ConjΓ (n) by fixing a conjugacy class [γ ] in Γ and denote
this function by ConjΓ,γ (n). The analog of Theorem 1.4 holds with (B) and ConjΓ,γ (n) in place of (A)
and ConjΓ (n).
Theorem 1.5. If Γ has (B), then for each γ ∈ Γ, there exists dγ ∈ N such that ConjΓ,γ (n)  ndγ .
Property (A). We now address the likelihood a group satisfies (A) or (B). We begin with (A). The
obvious test case to begin investigating with regard to property (A) is finitely generated free groups. For
n = 2, Horowitz [32] proved that there exist non-conjugate γ , η ∈ F2 such that for any representation
ρ : F2 → SL(2, C), we have Tr(ρ (γ )) = Tr(ρ (η )). We say such elements are SL2 –trace equivalent. It
seems to have been, for some time now, a folklore question as to whether or not there exists SLn –trace
equivalent elements in F2 for n > 2. In Section 4, we discuss whether or not the elements constructed
by Horowitz can be SLn –trace equivalent, and see that if they are, an unexpected trace relation must
hold. Ginzburg–Rudnick [25] investigated when a given element has a SL2 –trace companion and gave
a conjectural condition on the element to ensure that it does not have such a companion. Anderson [1]
provided a broader context for the construction of Horowitz and a conjectural picture for what such
pairs of SL2 –trace equivalent elements should look like. Additionally, Leininger [43] and Kapovich–
Levitt–Schupp–Shpilrain [34] gave a more geometric/topological take (see also [25], [40], [41], [42]).
Of course, we have trivially that any SL3 –trace equivalent pair is also an SL2 –trace equivalent pair.
The failure of Anderson’s general construction to produce SL3 –trace equivalent pairs would provide
some evidence that free groups have (A).
The most compelling evidence against free groups having (A) is Theorem 1.4. By [67] and [8], the
function FFr (n) satisfies n(log log(n))9/2 /(log(n))2  FFr (n)  n3 . We believe that the growth rate of
ConjFr (n) should be much greater since conjugacy separability requires separating a fixed element γ
from an infinite set while residual finiteness requires only separating γ from the trivial element. It
is this reason why many linear groups are not conjugacy separable. However, if Fr has (A), then
by Theorem 1.4, we would have, for some fixed d, the asymptotic inequalities ConjFr (n)  nd . In
particular, ConjFr (n)  (FFr (n))3d . For any finitely generated abelian group, these two functions are
the same, and the best setting to hope for a power relationship like ConjΓ (n)  (FΓ (n))d is the class of
torsion free, finitely generated nilpotent groups where conjugacy classes are relatively small. However,
by [8] and [53], a torsion free, finitely generated nilpotent group satisfies such a power relationship if
and only if the group is virtually abelian.

Decision problems, complexity, traces, and representations

4

Property (B). Following a construction of Wehrfritz [68] for free groups, we can prove that finitely
generated free groups and surface groups have (B).
Theorem 1.6. If Γ is a finitely generated free group or surface group, then Γ has (B).
From Theorem 1.5 and Theorem 1.6, we obtain:
Corollary 1.7. If Γ is a finitely generated free group or surface group and γ ∈ Γ, then there exists
2
dγ ∈ N such that ConjΓ,γ (n)  ndγ . Moreover, one can take dγ ≈ ||γ ||2 and thus ConjΓ (n)  nn .
The degree dγ in Corollary 1.7 is directly related to the smallest index of a finite index subgroup Γ of
Fr where γ ∈ Γ is primitive. In the case of surface groups, it is directly related to the smallest degree
of a cover where the curve associated to γ has a lift to a simple closed curve. Patel [51] and Gupta–
Kapovich [28] have given upper bounds in the case of surface groups and free groups, respectively, on
order ||γ ||. Gaster [24], improving on work of Gupta–Kapovich [28], has shown that there exist γ that
require a cover of degree on the order of ||γ ||. We conjecture that there is no polynomial upper bound
for ConjFr (n), and coupled with Theorem 1.4, that would imply that free groups do not have (A).
Conjecture 1. Finitely generated free groups do not have (A).
Finally, we prove a result that shows that for fully residually free groups, one can recover the profinite
topology via the topology generated by the Zariski topologies for faithful representations into SL(n, C)
as we vary over all n ∈ N. Recall that Γ is fully residually free if for each finite subset S ⊂ Γ of
non-trivial elements, there exists rS ∈ N and a homomorphism ψS : Γ → FrS such that the restriction of
ψS to S is injective. Examples of fully residually free groups are free groups and surface groups.
Theorem 1.8. Let Γ be a fully residually free group, ∆ a finite index, normal subgroup of Γ, and p ∈ N
a prime. Then there exists an integral domain R ⊂ C, an ideal m ⊂ R with R/m = F p , and a faithful
homomorphism ρ : Γ → SL(n∆ , R) such that ∆ = ker(rm ◦ ρ ) where rm : SL(n∆ , R) → SL(n∆ , F p ) is the
reduction modulo m homomorphism and n∆ = 2[Γ : ∆].
The ring R can be taken to be finitely generated over Z (see Remark 2), and when Γ is a free group,
we can take R = Z (see Remark 3). When Γ is an arithmetic lattice in a Q–algebraic group G, the
congruence subgroup property asserts that every finite index subgroup Λ < Γ contains ker(rm ) for
some integer m ∈ N. Every non-abelian free group Fr can be realized as a finite index subgroup of
SL(2, Z) and it is well-known that SL(2, Z) does not have the congruence subgroup property. The
above result provides a weaker property than the congruence subgroup property when Γ is a limit
group. As we mentioned above, lattices in semi-simple Lie groups with the congruence subgroup
property are not conjugacy separable and so do not have (D). These groups are super-rigid and the
Zariski topology associated to the standard representation, which is the congruence topology, is too
coarse for separating conjugacy classes. That free groups and surface groups are conjugacy separable
is due to their much richer representation theory. We believe conjugacy separability requires linear
representations of arbitrarily large dimension or finite quotients with arbitrarily large representation
dimension. If Conjecture 1 is false, then free groups would be conjugacy separable via the Zariski
topology associated to a fixed finite dimensional representation. In fact, for sufficiently large n and a
generic (in the Baire Category sense) ρ ∈ Hom(Fr , SL(n, C)), every conjugacy class in Fr would be
closed in the Zariski topology associated to ρ .

Decision problems, complexity, traces, and representations

5

Acknowledgements. The authors would like to thank Nigel Boston, Khalid Bou-Rabee, Frank Calegari, Ted Chinburg, Kelly Delp, Nathan Dunfield, Patrick Eberlin, Carolyn Gordon, Adrian Ioana,
Mike Jablonski, Ilya Kapovich, Greg Kuperberg, Chris Leininger, Darren Long, Alex Lubotzky, Dave
Morris, Alan Reid, Mark Sapir, Juan Souto, and Pete Storm for stimulating conversations on the topics
of this article. Special thanks is given to Dunfield who many years ago posed the question to the third
author on the possibility of generalizing Horowitz’s construction. The first author was partially supported by NSF grant 1309376 and Simons grant 245642. The third author was partially supported by
NSF grant 1105710. Lastly, we want to thank an anonymous referee for very good remarks that helped
improve the paper.

2
2.1

Preliminaries
Quantitative separability functions

Given f , g : N → N, we say f  g, if f (n) ≤ Cg(Cn) for some constant C ∈ N and for all n ∈ N. If
f  g and g  f , we write f ≈ g. Throughout, Γ will denote an infinite, finitely generated group unless
stated otherwise. Given a finite generating set X of Γ and γ ∈ Γ, we denote the word length of γ with
respect to X by ||γ ||X (or simply ||γ ||) and n–ball with respect to the associated word metric by BΓ, X (n).
Given Γ, we define DΓ : Γ − {1} → N ∪ {∞} by
/ ∆, ∆ ⊳ Γ}
DΓ (γ ) = min {[Γ : ∆] : γ ∈
and FΓ,X (n) by
FΓ,X (n) =

max

γ ∈BΓ, X (n)−{1}

DΓ (γ ).

For any two finite generating sets X ,Y , we have FΓ,X ≈ FΓ,Y (see [8, Lem 1.1]). Consequently, we
suppress the dependence on X in our notation. For a finitely generated group Γ and γ ∈ Γ, we denote
the Γ–conjugacy class of γ by [γ ] and denote the set of Γ–conjugacy classes by CΓ . For [γ ] ∈ CΓ , we
define || [γ ] ||X = min {||γ ′ ||X : γ ′ ∈ [γ ]}, and CDΓ : CΓ ×CΓ → N ∪ {∞} by
CDΓ ([γ ], [η ]) = min {|Q| : ϕ : Γ → Q, [ϕ (γ )]Q 6= [ϕ (η )]Q } .
By definition, for γ , η ∈ Γ with [γ ] 6= [η ], we have

CDΓ ([γ ], [η ]) ≥ max DΓ (γ −1 η ′ ) : η ′ ∈ [η ] .

We define BX (CΓ , n) = {[γ ] : || [γ ] ||X ≤ n} and ConjΓ,X : N −→ N ∪ {∞} via
ConjΓ,X (n) =

max

[γ ],[η ]∈BX (CΓ ,n), [γ ]6=[η ]

CDΓ ([γ ], [η ]).

For [γ ] ∈ CΓ , we define CDΓ,γ : CΓ − {[γ ]} → N ∪ {∞} to be CDΓ,γ ([η ]) = CDΓ ([γ ], [η ]) and
ConjΓ,γ ,X (n) =

max

[η ]∈BX (CΓ ,n), [γ ]6=[η ]

CDΓ,γ ([η ]).

For any two finite generating sets X ,Y of Γ, we have ConjΓ,X (n) ≈ ConjΓ,Y (n) and ConjΓ,γ ,X (n) ≈
ConjΓ,γ ,Y (n). The proof is similar to the proof of the comparable statement for the function FΓ (n); see
[8, Lem 1.1]. As a result, we suppress the dependence on the generating set X in our notation.

Decision problems, complexity, traces, and representations

2.2

6

Representation varieties

We refer the reader to [18, §5], [26, §2], and [56, Ch. V] for the material in this subsection. If G
is a Lie (resp. algebraic) group and Γ = Fr , then Hom(Fr , G) = Gr is an analytic (resp. algebraic)
variety. More generally, when Γ is finitely generated, Hom(Γ, G) will be an analytic (resp. algebraic)
subvariety of Hom(Fr , G) for some r; see [18, §5]. For each γ ∈ Γ, we have an analytic (resp. algebraic)
function Hom(Γ, G) → G given by ρ 7→ ρ (γ ). If G < GL(n, C), the function Trγ : Hom(Γ, G) → C
given by Trγ (ρ ) = Tr(ρ (γ )) is analytic (resp. algebraic). When G is a K–algebraic group with K a
characteristic zero field, Hom(Γ, G) is a K–algebraic set (not necessarily irreducible or connected),
and so has finitely many irreducible (and connected) components. In particular, for G = SL(n, C),
the space Hom(Γ, SL(n, C)) is a complex algebraic variety with finitely many irreducible components.
For a connected, reductive algebraic group G, the G–character variety X(Γ, G) is the GIT quotient of
Hom(Γ, G) by the G–conjugation action, and for Γ = Fr , we set Xr (G) = X(Fr , G). Though we do not
require it here, we include the following result on algebraic points of character varieties that we could
not find explicitly in the literature (it is implicit in [56, Prop 6.6]).
Theorem 2.1. If G is a connected, reductive, affine algebraic group, then Hom(Γ, G(Q)) is classically
dense in Hom(Γ, G(C)), and X(Γ, G(Q)) is classically dense in X(Γ, G(C)).
Proof. First note that for any d–dimensional affine variety V defined over Q the Noether normalization
map V → Ad is surjective and defines a finite cover off its branch locus. Since the branch locus is
nowhere dense, the Q–points are both Zariski and classically dense in the C–points of V . According
to [7, p. 220], G(K) is Zariski dense in G for any infinite subfield K ⊂ C. Since G is defined over Q
and the relations in Γ are defined over Z, Hom(Γ, G) is an affine variety defined over Q and
C[Hom(Γ, G)] = Q[Hom(Γ, G)] ⊗Q C.

(1)

Hence, Hom(Γ, G(Q)) is both Zariski and classically dense in Hom(Γ, G(C)). Let f1 , . . . , fN be a set
of generators for C[Hom(Γ, G)]G , and define f : Hom(Γ, G) → CN by
f (g1 , . . . , gr ) = ( f1 (g1 , . . . , gr ), . . . , fN (g1 , . . . , gr )).
Since X(Γ, G) = Spec(C[Hom(Γ, G)]G ), we have X(Γ, G) = f (Hom(Γ, G)); see [62] for example.
As C[Hom(Γ, G)]G ⊂ C[Hom(Γ, G)], Equation (1) implies that f1 , . . . , fN may be chosen to have Q–
coefficients. Thus, f Hom(Γ, G(Q))
⊂ X(Γ, G(Q)). As f is a continuous surjective function, we

conclude that f Hom(Γ, G(Q)) is classically dense in X(Γ, G(C)). Hence, X(Γ, G(Q)) is classically
dense in X(Γ, G(C)) as it contains f Hom(Γ, G(Q)) .
Corollary 2.2. If G = SL(n, C), the integral points are infinite in Xr (G).

Proof. For G = SL(n, C), the group schemes and invariant rings in the above proof are defined over
Z[1/n]. So, the result follows from the above proof noting that Hom(Fr , G) ∼
= Gr .
From the work of Long and Reid [44], one can infer that Corollary 2.2 is false for SL(2, C) when Γ is
a surface group.

Decision problems, complexity, traces, and representations

3

7

Property (C): Proof of Theorem 1.1 and Proposition 1.3

3.1

Proof of Theorem 1.1 and Corollary 1.2

We now prove that either uniform (C), or uniform (D) with the irreducibility of Hom(Γ, SL(n, C))
imply property (A).
Proof of Theorem 1.1. We assume first that Γ uniformly has (C). We enumerate the conjugacy classes
j
of Γ by {[γ1 ], [γ2 ], . . . } and for each j ∈ N, set S j = {[γi ]}i=1 . By assumption, there exists n ∈ N and for
each r, we have a representation ρr : Γ → SL(n, C) such that Tr(ρ (γi )) 6= Tr(ρ (γ j )) for all i 6= j ≤ r.
As Hom(Γ, SL(n, C)) has only finitely many irreducible components, there exists a component that
contains infinitely many of the representations ρr , say V0 ⊂ Hom(Γ, SL(n, C)). By selection, the trace
functions Trγ restricted to V0 are distinct algebraic functions for each conjugacy class [γ ]. In particular,
Trγi − Trγ j 6= 0 is a non-constant algebraic function on V0 for each pair i 6= j. In particular, the sets

Zi, j = ρ ∈ V0 : Trγi (ρ ) − Trγ j (ρ ) = 0
are proper algebraic subvarieties of V0 . By the Baire Category Theorem, V = V0 − i, j Zi, j is dense and
so non-empty. By construction, any ρ ∈ V has the property that Tr(ρ (γ )) = Tr(ρ (η )) if and only if
γ , η are conjugate in Γ. In particular, Γ has property (A).
S

In the case we uniformly have (D) and Hom(Γ, SL(n, C)) is irreducible, we know that by assumption that for each pair of conjugacy classes γ , η ∈ Γ, we have a representation ρ : Γ → SL(n, C)
with Tr(ρ (γ )) 6= Tr(ρ (η )). Since Hom(Γ, SL(n, C)) is irreducible, we can proceed as before with
V0 = Hom(Γ, SL(n, C)).
Before we prove Corollary 1.2, we note that in the special case of the genus 1 surface, the fundamental
group Z2 has (A). Take any two algebraically independent numbers α , β∈ R. Fixing
 a Z–basis v, w,
a
α
0
. By selection of
we have the representation ρ : Z2 → GL(2, R) given by ρ (av + bw) =
0 βb
α , β , distinct elements in Z2 will have distinct traces. The groups Zn also have (A) for any n ∈ N.
Proof of Corollary 1.2. The first part of Corollary 1.2 follows immediately from the irreducibility of
Hom(Fr , G) = Gr for any connected algebraic group over C in the case of free groups. For a closed,
orientable surface Σg of genus g ≥ 2, Hom(π1 (Σg ), SL(n, C)) is irreducible by [57] and [4, Lem, 2.5]
(the same holds for g = 1; see [22, Prop. 5.16]). For the second part, we must prove that the following
two statements are equivalent:
(a) There exists non-conjugate γ , η ∈ Fr that have Tr(ρ (γ )) = Tr(ρ (η )) for every ρ ∈ Hom(Fr , G).
(b) For each ρ ∈ Hom(Fr , G), there exist non-conjugate γ , η ∈ Fr such that Tr(ρ (γ )) = Tr(ρ (η )).
It is clear that (a) implies (b). To prove that (b) implies (a), we assume that (b) holds but not (a) and
derive a contradiction. Since (a) does not hold, then for each non-conjugate pair γ , η ∈ Fr , the function
Trγ − Trη on Hom(Fr , G) is a non-constant algebraic function. Since Hom(Fr , G) is irreducible,

Vγ ,η = ρ ∈ Hom(Fr , G) : Trγ (ρ ) − Trη (ρ ) = 0

Decision problems, complexity, traces, and representations

8

is nowhere dense. Taking V = [γ ]6=[η ] Vγ ,η , by the Baire Category Theorem, V is nowhere dense. Let
ρ ∈ Hom(Fr , G) −V and note that by construction, no two non-conjugate elements have the same trace
under ρ . That contradicts our assumption that (b) holds for every ρ ∈ Hom(Fr , G).
S

3.2

Proof of Proposition 1.3

The proof of Proposition 1.3 is similar to Mal’cev’s proof of residual finiteness for linear groups. As
we will use some of the setup later, we give a proof here. A proof can also be found in [2].
Proof of Proposition 1.3. Given non-conjugate γ , η ∈ Γ, we must find a homomorphism ϕ : Γ → Q
where Q is a finite group such that ϕ (γ ), ϕ (η ) are not conjugate in Q. By assumption, Γ has property
(D) and so there exists ρ ∈ Hom(Γ, SL(n, C)) such that Tr(ρ (γ )) 6= Tr(ρ (η )). Since Γ is finitely
generated, the field L generated over Q by the coefficients of the elements ρ (λ ) as we vary over all
λ ∈ Γ has the form L = K(x1 , . . . , xr ), where K/Q is a finite extension and x1 , . . . , xr are indeterminants.
It follows that ρ (Γ) < SL(n, R), where R = S[1/β1 , . . . , 1/βt ], S = OK [x1 , . . . , xr ], and OK is the ring
of K–integers. We see then that Tr(ρ (λ )) ∈ R for each λ ∈ Γ. We know that Tr(ρ (γ )) − Tr(ρ (η )) =
F(x1 , . . . , xr′ ) ∈ R is a non-zero polynomial in the variables x1 , . . . , xr′ with coefficients in S. Since
F is non-zero, we can find α1 , . . . , αr′ ∈ S such that α = F(α1 , . . . , αr′ ) 6= 0 with α ∈ S. As there
are only finitely many prime ideals p in S such that α = 0 mod p, we select a prime p for which
α 6= 0 mod p. For such a prime, the ring homomorphisms R → S → S/p ∼
= Fq induce homomorphisms
Γ → SL(n, R) → SL(n, S) → SL(n, Fq ). Set ϕ : Γ → SL(n, Fq ) to be the resulting map. By construction
Tr(ϕ (γ )) 6= Tr(ϕ (η )) and so ϕ (γ ), ϕ (η ) are not conjugate in SL(n, Fq ).

3.3

Ultraproducts

For a fixed n ∈ N, we say that a group Γ is n–trace distinguished if for each non-conjugate pair
γ , η ∈ Γ, there exists a finite field Fq and a homomorphism ϕ : Γ → SL(n, Fq ) such that Tr(ϕ (γ )) 6=
s
Tr(ϕ (η )). We say Γ is fully n–trace distinguished if for any finite set S = γ j j=1 ⊂ Γ of pairwise
non-conjugate elements, there exists a finite field Fq and a homomorphism ϕ : Γ → SL(n, Fq ) such that
Tr(ϕ (γi )) 6= Tr(ϕ (γ j )) for all 1 ≤ i < j ≤ s.
Theorem 3.1. If Γ is finitely generated and fully n–trace distinguished for some n ∈ N, then Γ has (A).
In the proof of Theorem 3.1, we employ ultraproducts. We refer the reader to [29] for an introduction
to these methods.
Proof. To begin, we enumerate the conjugacy classes of Γ by {[γ1 ], [γ2 ], . . . } and for each j ∈ N, set
j
. By assumption, for each j ∈ N, there exists a finite field Fq j and a homomorphism
S j = {[γi ]}i=1
ϕ j : Γ → SL(n, Fq j ) such that Tr(ϕ j (γi )) 6= Tr(ϕ j (γi′ )) for all 1 ≤ i < i′ ≤ j. Picking a non-principal
ultrafilter ω on N, the ultraproduct ∏ω Fq j = Kω is a field and we have an induced homomorphism
∏ω ϕ j = Φω , where Φω : Γ → SL(n, Kω ). By selection of the homomorphisms ϕ j , it follows that
Tr(Φω (γi )) 6= Tr(Φω (γi′ ) for all i 6= i′ . Hence, Γ has (A).
The field Kω may have positive characteristic and so in the definition of (A), we must allow for algebraically closed fields of positive characteristic (see Remark 1). Using the methods from the proof of
Proposition 1.3, it is straightforward to see that if Γ has (A′ ), then Γ is fully n–trace distinguished.

Decision problems, complexity, traces, and representations

9

We can also consider a relative version of n–trace distinguished. For γ ∈ Γ and n ∈ N, we say γ is
n–trace distinguished in Γ if for each non-conjugate η ∈ Γ, there exists a finite field Fq and a homomorphism ϕ : Γ → SL(n, Fq )such that Tr(ϕ (γ )) 6= Tr(ϕ (η )). We say γ is fully n–trace distinguished
s
in Γ if for any finite set S = γ j j=1 ⊂ Γ, none of which is conjugate to γ , there exists a finite field Fq
and a homomorphism ϕ : Γ → SL(n, Fq ) such that Tr(ϕ (γ )) 6= Tr(ϕ (γ j )) for all 1 ≤ j ≤ s.
Theorem 3.2. If Γ is finitely generated and for each γ ∈ Γ, there exists nγ ∈ N such that γ is fully
nγ –trace distinguished, then Γ has (B).
Proof. To begin, we enumerate the conjugacy classes of Γ by {[γ1 ] = [γ ], [γ2 ], [γ3 ], . . . } and for each j ∈
j
N, set S j = {[γi ]}i=2 . By assumption, for each j ≥ 2, there exists a finite field Fq j and a homomorphism
ϕ j : Γ → SL(n, Fq j ) such that Tr(ϕ j (γi )) 6= Tr(ϕ j (γ )) for all 2 ≤ i ≤ j. Picking a non-principal ultrafilter
ω on N, the ultraproduct ∏ω Fq j = Kω is a field and we have an induced homomorphism ∏ω ϕ j = Φω ,
where Φω : Γ → SL(n, Kω ). By selection of the homomorphisms ϕ j , it follows that Tr(Φω (γi )) 6=
Tr(Φω (γ )) for all i ≥ 2. Hence, Γ has (B).
As before, allowing for algebraically closed fields of positive characteristic in our definition of (B), the
converse holds assuming (B′ ).

3.4

Proof of Theorem 1.4 and Theorem 1.5

We now prove Theorem 1.4.
Proof of Theorem 1.4. We assume that Γ has (A) for some integer m ∈ N, and so there exists ρ ∈
Hom(Γ, SL(m, C)) such that Tr(ρ (γ )) 6= Tr(ρ (η )) for any non-conjugate γ , η ∈ Γ. For simplicity, we
assume that ρ (Γ) < SL(m, Q), as the alternative ρ (Γ) < SL(m, K[x1 , . . . , xr ]), where K/Q is a finite
extension, is handled similarly (see [15]). We must prove that for any non-conjugate pair γ , η ∈ Γ with
2
||γ || , ||η || ≤ n, that CDΓ (γ , η ) ≤ Cnm −1 for a constant C that is independent of γ , η . To begin, we can
find a finite extensions K/Q and S/OK such that ρ (Γ) < SL(m, S). With this setup, we know for any
non-conjugate γ , η that Tr(ρ (γ )) − Tr(ρ (η )) ∈ S and also is non-zero. We need an ideal a of S such
that Tr(ρ (γ )) − Tr(ρ (η )) 6= 0 mod a and with |S/a| small. We achieve this goal using the methods of
[8] (or [15]). First, we control the size of the coefficients of ρ (γ ), ρ (η ) as a function of word length.
To that end, it follows (see [8] or [15]) that there exists constants α and C0 depending only on the
generators of Γ such that

max (ρ (γ ))i, j : i, j ∈ {1, . . . , m} ≤ α C0 ||γ || .
In particular, given non-conjugate γ , η ∈ Γ with ||γ || , ||η || ≤ n, we see that

|Tr(ρ (γ )) − Tr(ρ (η ))| ≤ |Tr(ρ (γ ))| + |Tr(ρ (η ))| ≤ 2mα C0 n .
By [8, Thm 2.4]), we can find a prime ideal p with
|S/p| ≤ C1 log(C1 2mα C0 n ) ≤ C1C0 n log(C1 2mα )
such that Tr(ρ (γ )) 6= Tr(ρ (η )) mod p. The constant C1 depends only on the ring S. Let rp : SL(n, S) →
SL(n, S/p) be the reduction modulo p homomorphism and set ρp : Γ → SL(n, S/p) by ρp = rp ◦ ρ . By

Decision problems, complexity, traces, and representations

10

selection of p, we see that ρp (γ ), ρp (η ) have distinct traces and hence have non-conjugate images. We
also have
2
2
2
|ρp (Γ)| ≤ |SL(n, S/p)| ≤ |S/p|m −1 ≤ (C1 n log(C1 2mα ))m −1 = Cnm −1
where C is the constant (C1C0 log(C1 2mα ))m −1 . In particular, CDΓ ([γ ], [η ]) ≤ Cnm −1 for some constant C depending only on Γ and ρ . As this holds for all [γ ], [η ] ∈ B(CΓ , n), we see that ConjΓ (n) 
2
nm −1 . The assertion that one only needs subgroups of SL(n0 , F p ) in proving conjugacy separability
for Γ follows from the Čebotarev Density Theorem.
2

2

Proof of Theorem 1.5. We proceed similarly to the proof of Theorem 1.4. By assumption, we have
ρ ∈ Hom(Γ, SL(nγ , C)) such that Tr(ρ (γ )) 6= Tr(ρ (η )) for any η ∈ Γ that is not conjugate to γ . Using
Tr(ρ (γ )) − Tr(ρ (η )), we can employ the same methods used in the proof of Theorem 1.4 to find the
desired homomorphism to a finite group where γ , η have non-conjugate images.

4

Horowitz’s construction

In this section we show that the cyclically reduced words constructed in Example 8.2 in [32] that do
have the same trace over SL(2, C) are not likely to have the same trace over SL(n, C) for n > 2. Since
SL(n − 1, C) embeds into SL(n, C) it suffices to show that this failure occurs for n = 3.

4.1

Reduction to free groups

The following lemma reduces the search for trace equivalent pairs in non-elementary hyperbolic groups
to finding them in Fr
Lemma 4.1. Let n, r ≥ 2 be integers. If there exists a non-conjugate pair w1 , w2 ∈ Fr such that w1 , w2
are SLn –trace equivalent, then for any non-elementary hyperbolic group ∆, there exists non-conjugate
δ1 , δ2 ∈ ∆ that are SLn –trace equivalent.
Proof. By I. Kapovich [33, Thm C], ∆ has a malnormal subgroup ∆0 that is isomorphic to Fr . Fixing
any isomorphism ψ : Fr → ∆0 , we set δ j = ψ (w j ). For any representation ρ : ∆ → SL(n, C), it follows
that Tr(ρ (δ1 )) = Tr(ρ (δ2 )). As δ1 , δ2 are non-conjugate in ∆0 and ∆0 is malnormal in ∆, we see that
δ1 , δ2 are non-conjugate in ∆.
Since free groups are hyperbolic, it follows that for any integers r, s ≥ 2, Fr has a non-conjugate SLn –
trace equivalent pair if and only if Fs has a non-conjugate SLn –trace equivalent pair. In particular,
we need only consider the existence of trace equivalent pairs in F2 . In fact, for any finitely generated
group Γ with a malnormal free subgroup, we see that ConjF2 (n)  ConjΓ (n). Moreover, ConjFr (n) ≈
ConjFs (n) for any integers r, s ≥ 2. We also note that Lemma 4.1 implies that if F2 does not have (A),
then no non-elementary hyperbolic group can have (A). Indeed, no finitely generated group with a
malnormal free subgroup can have (A).

Decision problems, complexity, traces, and representations

4.2

11

Horowitz’s construction

Let F2 = ha, bi. Horowitz’s words are defined recursively by w0 = a and
εm 2m εm
2m−1 −εm 2m εm
wm (ε1 , . . . , εm ) := w−
wm−1 b wm−1
m−1 b wm−1 b

for εi = ±1. Horowitz shows that for (ε1 , . . . , εm ) 6= (ε1∗ , . . . , εm∗ ), the corresponding words will not be
cyclically equivalent for any m > 0 and they are all SL2 –trace equivalent. Hence, there are arbitrarily large collections of SL2 –trace equivalent non-conjugate words. For w1 (1) = a−1 b2 aba−1 b2 a and
w1 (−1) = ab2 a−1 bab2 a−1 , one can find a representation ρ = (A, B) ∈ SL(3, C)2 where Tr(ρ (w1 (1)))−
Tr(ρ (w1 (−1))) 6= 0. In particular, this pair is not SL3 –trace equivalent. Below, we further elaborate
on why it is unlikely that the above SL2 –trace pairs are also SL3 –trace pairs. First, we review in more
detail why these pairs are SL2 –trace equivalent. The first step in showing SL2 –trace equivalence is a
proof that
Tr(wm (ε1 , . . . , ε j−1 , +1, ε j+1 , . . . , εm )) = Tr(wm (ε1 , . . . , ε j−1 , −1, ε j+1 , . . . , εm ))
for 1 ≤ j ≤ m for SL(2, C). By the recursive definition of wm , Horowitz shows that
wm (ε1 , . . . , ε j−1 , +1, ε j+1 , . . . , εm ) = W (u−1 bu, b)
whereas
wm (ε1 , . . . , ε j−1 , −1, ε j+1 , . . . , εm ) = W (ubu−1 , b)
where u = w j−1 (ε1 , . . . , ε j−1 ) and W is a word in two letters. What works for SL(2, C) is that there
exists a polynomial PW in three variable so that Tr(W (u, v)) = PW (Tr(u), Tr(v), Tr(uv)). In the case
above, these three traces are identical when evaluated at (ubu−1 , b) and (u−1 bu, b) respectively since
the trace is invariant under cyclic permutations, and hence their polynomials are equal too. One can
argue inductively to establish the general result.
However, this first step fails for SL(3, C). The comparable statement is that there exists a polynomial
PW in nine variables (see [39]) such that
Tr(W (u, v)) = PW (Tr(u), Tr(u−1 ), Tr(v), Tr(v−1 ), Tr(uv), Tr(u−1 v−1 ), Tr(uv−1 ), Tr(u−1 v), Tr(uvu−1 v−1 )).
Upon checking, one finds that the first 6 variables are equal. However, the seventh variables become
Tr(ubu−1 b−1 ) and Tr(u−1 bub−1 ) = Tr(bub−1 u−1 ) = Tr((ubu−1 b−1 )−1 ). These traces of words are
generically not equal (see [39]); in fact they are equal if and only if the SL(3, C) representations
are transpose fixed. Likewise the eighth variables will differ as well. In fact, we would have an
expression of the form PW (a1 , . . . , a6 , a7 , a8 , Tr(w)) = PW (a1 , . . . , a6 , a8 , a7 , Tr(w−1 )) since the 7th and
8th variables are in fact permuted (switching the roles of u and v) and the first 6 are identical (just by
cyclic permutation), and the 9th is cyclically equivalent to the trace of its inverse. The 9th word is
ubu−1 bub−1 u−1 b−1 . Note also that there is a polynomial P in the 8 algebraically independent variables
so that Tr(w−1 ) = P − Tr(w). If we had equality we would have a non-trivial relation (symmetric in
two variables), which is unlikely for a fixed w.

Decision problems, complexity, traces, and representations

4.3

12

Candidate words

By Lemma 6.8 in [32] any SL2 –trace equivalent pair in F2 must have the same number of each generator
represented in the word, up to plus or minus exponents. Thus, the same result holds for words that are
SLn –trace equivalent for any n. It is easy to see that pairs of the form (w, w−1 ) are SL2 –trace equivalent.
However, by [6] the word map is dominant for non-trivial words, and so (w, w−1 ) are never SLn –trace
equivalent for n ≥ 3 since Tr(A) 6= Tr(A−1 ) for a generic (in the Baire sense) A ∈ SL(3, C). Along the
same lines, we have the following lemma.
Lemma 4.2. Let r(w) be the reverse of the word w, and assume r(w) is not conjugate to w. Then r(w)
and w are always SLn –trace equivalent if and only if n = 2.
Proof. Since Tr(w) = Tr(w−1 ) for n = 2, we obtain Tr(w(a, b)) = Tr(w(a, b)−1 ) = Tr(r(w(a−1 , b−1 ))).
Therefore, Tr(r(w(a, b))) = Tr(w(a−1 , b−1 )). By the Fricke–Vogt Theorem (see for instance [27]),
Hom(F2 , SL(2, C))// SL(2, C) ∼
= C3 parametrized by (Tr(a), Tr(b), Tr(ab)). Thus, there exists a unique
polynomial P ∈ C[x, y, z] such that Tr(w(a, b)) = P(Tr(a), Tr(b), Tr(ab)). We conclude
Tr(r(w(a, b))) = P(Tr(a−1 ), Tr(b−1 ), Tr(a−1 b−1 )) = P(Tr(a), Tr(b), Tr(ab)) = Tr(w(a, b)).
Conversely, Hom(F2 , SL(3, C))// SL(3, C) is a branched double cover of C8 (see [39]). The branch locus is exactly determined by Tr(aba−1 b−1 ) = Tr(b−1 a−1 ba); showing that for r = 2 the pairs (w, r(w))
are not generally SLn –trace equivalent for n ≥ 3.
We expect that non-conjugate reverse pairs are never SL3 –trace equivalent. A more provocative conjecture is the following; in the statement, positive words have only non-negative powers of the generators:
Conjecture 2. Let n ≥ 2. There exists SLn –trace equivalent pairs (u, v) if and only if there exists
positive pairs (u′ , v′ ) that are SLn –trace equivalent.
Before giving a heuristic proof for the above conjecture, we mention two related conjectures. Ginzburg–
Rudnick [25, Conj 1.1] have a conjectural condition to ensure a word does not have an SL2 –trace companion (aside from its inverse); in their terminology, such a word has stable multiplicity one. Anderson
[1, Conj 4.1] gave conjectural picture for all SL2 –trace companions.
We now give a heuristic for the validity of the conjecture. As the reverse implication is obvious, we
discuss only the direct implication. For n = 2, Lemma 4.2 establishes the statement. For n > 2 we
describe an algorithm (that depends on n) that takes a non-conjugate SLn –trace equivalent pair and
produces a pair, that we expect that is positive, SLn –trace equivalent, and not conjugate. We have
implemented the algorithm for n = 2 and it does produce a positive pair (u′ , v′ ) that is SL2 –trace
equivalent but u′ is conjugate to v′ ; we expect this to be a problem only with n = 2.
In what follows, let ρ (a) = A be a n by n matrix. Recall the Cayley–Hamilton formula gives
n

0=

∑ (−1)n−kCkn (A)Ak ,

k=0

where the coefficients Ckn (A) arise from the characteristic equation det(tI−A) = ∑nk=0 (−1)n−kCkn (A)t k .
n (A) = Tr(A) and C n (A) = det(A). By Newton’s trace formulas each
We know that Cnn (A) = 1, Cn−1
0

Decision problems, complexity, traces, and representations

13

Ckn (A) is a polynomial in the traces of non-negative powers of the matrix A. Since det(A) = 1, we
can multiply the Cayley-Hamilton formula by a word UA−1 := ρ (ua−1 ) on the left and another word
V := ρ (v) on the right. This results in
n−1

UAn−1 V + ∑ (−1)n−kCkn (A)UAk−1 V = (−1)n+1 UA−1 V.
k=1

Thus, by taking the trace of both sides, we have:
n−1

Tr(UA−1 V) = (−1)n+1 Tr(UAn−1 V) + ∑ (−1)k−1Ckn (A) Tr(UAk−1 V).
k=1

That shows that given any word w with negative exponents, one can iteratively apply the preceding
formula in the coordinate ring C[Hom(F2 , SL(n, C))// SL(n, C)], which is generated by traces of words
by results of Procesi [55], to obtain an expression for Tr(w) as a polynomial in traces of positive words.
Now, suppose (u, v) is SLn –trace equivalent but are not conjugate. After cyclically reducing u and v,
given results of Horowitz ([32]), we can assume that u and v have the same word length and the same
(signed) multiplicity of each letter. Applying the preceding algorithm to Tr(u), Tr(v) results in polynomial expressions Pu , Pv in terms of traces of only positive words. By inspection of the replacement
formula defining the algorithm, one sees that there will be a monic trace term with a longest word. That
is Pu = Tr(u′ ) + L, and likewise Pv = Tr(v′ ) + L′ where both L, L′ contain terms of products of traces of
shorter positive words. We expect that Tr(u′ ) = Tr(v′ ) since Tr(u) = Tr(v) to begin with. Also, given
that n ≥ 3, we expect that u′ is not conjugate to v′ given that u is not conjugate to v.
It is not presently clear to us how to complete the above argument, that is, to prove that the last two
lines are valid. We thank Greg Kuperberg for conversations about the validity of the above sketch.
We now indicate our interest in this conjecture. For the free group F2 = F2 (a, b), the smallest positive
exponent SL2 –trace equivalent pair is {babbaa, abaabb}. To find examples of SL(3, C) words, if the
conjecture is true, we need only check words with the same number of letters in each word having only
positive exponents. Moreover, since by restricting, the trace equivalence must also hold for SL(2, C),
we need only check words of the above type that work for SL(2, C). We expect that non-conjugate
reverse pairs will never be SL3 –trace equivalent, and so we further wish to only consider positive nonconjugate pairs that are not reverse but are SL2 –trace equivalent; the first examples occurs at length 12
with one explicit pair being {aababbaabbab, aababbabaabb}. We end this section with two questions
about such words.
(1) What is a classification of these words, or generating families?
(2) What is the growth rate as a function the length of these words?
As we expect SLn –trace equivalent words exist, our guess is that the above words are rather plentiful.
However, by computer search, there are no SL3 –trace equivalent pairs of length up to 20.

5

Efficient solutions to the conjugacy problem

In this section, we provide two different approaches to solving the conjugacy problem in free groups
using finite quotients, neither of which are originally due to us.

Decision problems, complexity, traces, and representations

5.1

14

Lower central and derived series

Recall, the lower central and derived series are defined inductively by Γ0 = Γ, Γ j = [Γ, Γ j−1 ], and
Γ j = [Γ j−1 , Γ j−1 ]. We set N j (Γ) = Γ/Γ j and S j (Γ) = Γ/Γ j . By [46, p. 27, Prop. 4.9], we know
that γ , η ∈ Fr are conjugate in Fr if and only if they have conjugate image in S j (Fr ) (or N j (Fr )) for
all j. Since the groups S j (Fr ) and N j (Fr ) are conjugacy separable for all j (see [5], [23], and [58])
and we see that Fr conjugacy separable. In order to implement these methods effectively, we must
first estimate jγ ,η as a function of the word length of γ , η where jγ ,η is the smallest j ∈ N such that
γ , η have non-conjugate images in N j (Fr ) (or S j (Fr )). Second, we must effectivly solve the conjugacy
problem in torsion free nilpotent or polycyclic groups. Malestein–Putman [49] addresses the first
problem. Pengitore [53] addresses the second problem. As our current goal is deciding whether or
not the function ConjFr (n) has a polynomial bound, we note that it is already known that the above
method cannot work. Specifically, neither the lower central or derived series provides a polynomial
upper bound for the function FFr (n); see [8] and [9].

5.2

Proof of Theorem 1.6

In this subsection, we prove Theorem 1.6. The construction of the representation needed to verify
Theorem 1.6 in the case of free groups follows Wehrfritz [68]. The surface group case is similar.
We now produce the representation for the case of free groups. To begin, given a conjugacy class
[γ ] in Fr , we first pass to a finite index subgroup Γ where Γ = hγ i ∗ ∆. That such can be done follows from work of Hall [30]. Since γ is part of a free basis, it follows that there exists a representation ρ0 : Γ → SL(2, R) where γ has a unique, non-zero trace up to conjugation and inverses. As
SL(2, R) < SL(3, C) by the standard inclusion into the upper two by two block, we see that there exists
a representation ρ1 : Γ → SL(3, C) such that ρ1 (γ ) has a unique, non-zero trace up to conjugation and
inverses. Since Tr(ρ (γ −1 )) 6= Tr(ρ (γ )) for a generic SL(3, C) representation ρ (in the Baire Category sense), we can further assume that ρ (γ ) has a unique, non-zero trace up to conjugation. For any
η ∈ Γ that is not conjugate to γ in Γ, we know that Tr(ρ (γ )) − Tr(ρ (η )) is a non-constant function
of ρ . Consequently, by the Baire Category Theorem, we can assume that k1 Tr(ρ1 (γ )) 6= k2 Tr(ρ1 (η ))
for any pair of integers 1 ≤ k1 , k2 ≤ m = [Fr : Γ]. For any such ρ1 ∈ Hom(Γ, SL(3, C)), the induced
representation ρ = IndFΓr (ρ1 ) is the needed representation to verify Theorem 1.6 in the free group case.
Proof of Theorem 1.6: Free Case. If η ∈ Fr is not conjugate in Fr into Γ , then Tr(ρ (η )) = 0 by the
Frobenius formula for traces of induced representations. If η ∈ Fr is conjugate in Fr to some η ′ ∈ Γ,
then Tr(ρ (η )) = kη Tr(ρ1 (η ′ )) for some integer 1 ≤ kη ≤ m. As Tr(ρ (γ )) = kγ Tr(ρ1 (γ )) for some
1 ≤ kγ ≤ m, it follows from our selection of ρ1 that ρ (γ ) has a unique trace up to conjugation, as
needed for Theorem 1.6.
We now produce the representation for the case of surface groups. To begin, given a conjugacy class [γ ]
in π1 (Σg ), we first pass to a cover where a lift of the curve associated to [γ ] is simple. That such can be
done follows from work of Scott [63]. We fix a finite index subgroup of π1 (Σg ) associated to this finite
cover which we denote by Γ. Since the curve associated to [γ ] has a simple lift, it follows that there
exists a representation ρ0 : Γ → SL(2, C) where γ has a unique, non-zero trace up to conjugation and
inverses. The remainder of the construction of ρ is identical to the free case of the proof of Theorem

Decision problems, complexity, traces, and representations

15

1.6. Note that to ensure Tr(ρ (γ )) 6= Tr(ρ (γ −1 )) for a generic ρ ∈ Hom(Γ, SL(3, C) (in the Baire sense),
we can use [12] in place of [6].
In either the free or surface case, we can use the methods from [15] to establish Corollary 1.7. In
particular, the degree of the polynomial in Corollary 1.7 depends only on m and the coefficient ring of
the representation, both of which are constant for a fixed γ . By Patel [51] and Gupta–Kapovich [28],
2
we have m  ||γ ||, and so when ||γ || , ||η || ≤ n, we see that CDΓ (γ , η ) ≤ CnCn .

6

Proof of Theorem 1.8

Given a fully residually free group Γ with a finite index, normal subgroup ∆ and a prime p ∈ Z, we will
construct a faithful homomorphism ρ : Γ → SL(n∆ , Rω ) such that ∆ = ker(rmω ◦ ρ ) where n∆ = 2[Γ : ∆],
Rω is a local domain, mω < Rω is the unique maximal ideal with residue field Rω /mω = F p , the field
of p elements, and rmω : SL(n∆ , Rω ) → SL(n∆ , F p ) is the reduction modulo mω homomorphism. We
enumerate the non-trivial elements of ∆ via {δ1 , δ2 , . . . }. Since subgroups of fully residually free
groups are fully residually free, for each t ∈ N, there exists a homomorphism ψt : ∆ → Frt such that ψt
is injective when restricted to the finite subset {δ1 , . . . , δt }. Recall that the ring of p–adic integers Z p is
a local integral domain with a unique maximal ideal mp . Via the ping pong lemma, the homomorphism
ψ(p) : F2 → SL(2, Z) < SL(2, Z p ) induced by sending a free basis a, b of F2 to the matrices


 

1 p
1 0
a, b 7−→
,
0 1
p 1
is an isomorphism. By the Nielsen–Schreier theorem, we have a faithful homomorphism Frt → F2 for
each rt ∈ N and fix one such homomorphism for each rt ∈ N. Respectfully, we define ρ p,t := ψ(p) ◦ ψt
and note ρ p,t (∆) < ker rm p .
We restrict ψ(p) to the image of Frt < F2 and for notational simplicity denote the resulting homomorphism by ψ . Taking a non-principal ultrafilter ω on N, the ultraproduct Rω = ∏ω Z p is a local
integral domain with unique maximal ideal mω = ∏ω m p (see [60, Ch. 1] for instance). The associated
residue field Rω /mω is given by ∏ω Z p /m p . Since the latter is an ultraproduct of F p , it follows that
Rω /mω is isomorphic to F p (see [29, p. 184] for instance). The ultraproduct ρω of the representations
ρt = ψ ◦ ψt yields a representation ρω : ∆ → SL(2, Rω ). By selection of ψt and ψ , ρω is faithful with
ρω (∆) < ker rmω . Setting ρ = IndΓ∆ (ρ∞ ), we obtain a faithful representation ρ : Γ → SL(2d, Rω ) where
d = [Γ : ∆]. By construction of ρω , the definition of Ind, and the normality of ∆ in Γ, we see that
∆ = ker(rmω ◦ ρ ).
Remark 2. The ring Rω embeds into ∏ω Q p which is a field of characteristic zero. Since fully residually free groups are finitely presentable ([64, 4.4]), the ring R generated over Z by the coefficients of
the matrix entries of ρ (Γ) is finitely generated. Setting m = R ∩ mω , we obtain a maximal ideal in R
with residue field R/m = F p such that ρ (Γ) < SL(2[Γ : ∆], R) and ∆ = ker(rm ◦ ρ ). Moreover, we have
an embedding of R into C; the field of fractions of R embeds into C via the axiom of choice.
Remark 3. If Γ is a free group, we can take ρ = IndΓ∆ (ρ0 ) where ρ0 is the representation given by
∆ → F2 → SL(2, Z). The first homomorphism ∆ → F2 is given by the Nielsen–Schreier theorem and
the second homomorphism F2 → SL(2, Z) is given by ψ(p) . In total, we obtain a faithful representation
ρ : Γ → SL(2[Γ : ∆], Z) such that ∆ = ker(r p ◦ ρ ).

Decision problems, complexity, traces, and representations

16

Theorem 1.8 can also be proven by using work of Barlev–Gelander [3], which followed the work of
Breuillard–Gelander–Souto–Storm [18]. Barlev–Gelander [3, Thm 1.2] proved that if G is a compact
topological group with a non-abelian free subgroup, then G contains an isomorphic copy of every
non-abelian limit group. Since Z p is a compact topological ring, SL(2, Z p ) is a compact topological
group. Moreover, the finite index subgroup ker rm p < SL(2, Z p ) is a compact topological group with
F2 < ker rm p from above. Hence by [3, Thm 1.2], ker rm p contains an isomorphic copy of every nonabelian limit group. Given a non-abelian limit group Γ with a finite index, normal subgroup ∆, we can
apply this observation to obtain a faithful representation ρ0 : ∆ → ker rm p < SL(2, Z p ). It follows then
that ρ = IndΓ∆ (ρ0 ) is a faithful representation into SL(2[Γ : ∆], Z p ) with ∆ = ker(rm p ◦ ρ ).

References
[1] J. W. Anderson, Variations on a theme of Horowitz, Kleinian groups and hyperbolic 3-manifolds (Warwick, 2001), 307–341, London Math. Soc. Lecture Note Ser., 299, Cambridge Univ. Press, Cambridge,
2003.
[2] H. Bass, A. Lubotzky, Automorphism of schemes and of subgroups of finite type, Israel J. of Math. 44
(1983), 1–22.
[3] J. Barlev, T. Gelander, Compactifications and algebraic completions of limit groups, Journal d’Analyse
Mathématique 112 (2010), 261–287.
[4] I. Biswas, S. Lawton, D. Ramras, Fundamental groups of character varieties: surfaces and tori, Math.
Z. 281 (2015), 415–425.
[5] N. Blackburn, Conjugacy in nilpotent groups, Proc. Amer. Math. Soc. 16 (1965), 143–148.
[6] A. Borel, On free subgroups of semisimple groups, Enseign. Math. (2), 29 (1983), 151–164.
[7] A. Borel, Linear algebraic groups, Springer-Verlag, 1991.
[8] K. Bou-Rabee, Quantifying residual finiteness, J. Algebra 323 (2010), 729–737.
[9] K. Bou-Rabee, Approximating a group by its solvable quotients, New York J. Math. 17 (2011), 699–712.
[10] K. Bou-Rabee, M. F. Hagen, P. Patel, Residual finiteness growths of virtually special groups, Math. Z.
279 (2015), 297–310.
[11] K. Bou-Rabee, T. Kaletha, Quantifying residual finiteness of arithmetic groups, Compos. Math. 148
(2012), 907–920.
[12] K. Bou-Rabee, M. Larsen, Linear groups with Borel’s property, ArXiv, to appear in J. Eur. Math. Soc.
[13] K. Bou-Rabee, D. B. McReynolds, Bertrand’s postulate and subgroup growth, J. of Algebra 324 (2010),
793–819.
[14] K. Bou-Rabee, D. B. McReynolds, Asymptotic growth and least common multiples in groups, Bull.
Lond. Math. Soc. 43 (2011), 1059–1068.
[15] K. Bou-Rabee, D. B. McReynolds, Extremal behavior of divisibility functions, Geom. Dedicata. 175
(2015), 407–415.

Decision problems, complexity, traces, and representations

17

[16] K. Bou-Rabee, D. B. McReynolds, Characterizing linear groups in terms of growth properties, ArXiv,
to appear in Michigan Math. J.
[17] K. Bou-Rabee, B. Seward, Arbitrarily large residual finiteness growth, J. Reine Angew. Math. 710
(2016), 199–204.
[18] E. Breuillard, T. Gelander, J. Souto, P. Storm, Dense embeddings of surface groups, Geom. Topol. 10
(2006), 1373–1389.
[19] N. V. Buskin, Efficient separability in free groups, Sibirsk. Mat. Zh. 50 (2009), 765–771.
[20] O. Cotton-Barratt, H. Wilton, Conjugacy separability of 1-acylindrical graphs of free groups Math. Z.
272 (2012), 1103–1114.
[21] M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), 116–144.
[22] C. Florentino, S. Lawton, Topology of character varieties of Abelian groups, Topology Appl. 173
(2014), 32–58.
[23] E. Formanek, Conjugate separability in polycyclic groups, J. Algebra 42 (1976), 1–10.
[24] J. Gaster, Lifting curves simply, ArXiv, to appear in IMRN.
[25] D. Ginzburg, Z. Rudnick, Stable multiplicities in the length spectrum of Riemann surfaces Israel J. of
Math. 104 (1998), 129–144.
[26] W. M. Goldman, Topological components of spaces of representations, Invent. Math. 93 (1988), 557–
607.
[27] W. M. Goldman, Trace coordinates on Fricke spaces of some simple hyperbolic surfaces, EMS Publishing House, Zürich, 2008. Handbook of Teichmüller theory II ( A. Papadopoulos, editor).
[28] N. Gupta, I. Kapovich, The primitivity index function for a free group, and untangling closed curves on
hyperbolic surfaces, ArXiv (2014).
[29] J. I. Hall, Locally finite simple groups of finitary linear transformations, Nato Science Series C 471
(1995), 147–188.
[30] M. Hall, Coset representations of free groups, Trans. Amer. Math. Soc. 67 (1949), 421–432.
[31] E. Hamilton, H. Wilton, P. Zalesskii, Separability of double cosets and conjugacy classes in 3-manifold
groups, J. Lond. Math. Soc. 87 (2013), 269–288.
[32] R. Horowitz, Characters of free groups represented in the two-dimensional special linear group, Comm.
Pure Appl. Math. 25 (1972), 635–649.
[33] I. Kapovich, A non-quasiconvexity embedding theorem for hyperbolic groups Math. Proc. Cambridge
Philos. Soc. 127 (1999), 461–486.
[34] I. Kapovich, G. Levitt, P. Schupp, V. Shpilrain, Translation equivalence in free groups, Trans. Amer.
Math. Soc. 359 (2007), 1527–1546.
[35] M. Kassabov, F. Matucci, Bounding the residual finiteness of free groups, Proc. Amer. Math. Soc. 139
(2011), 2281–2286.
[36] O. Kharlampovich, A. Myasnikov, M. Sapir, Algorithmically complex residually finite groups, ArXiv
(2012).

Decision problems, complexity, traces, and representations

18

[37] G. Kozma, A. Thom, Divisibility and laws in finite simple groups, Math. Ann. 364 (2016), 79–95.
[38] G. Kuperberg, Knottedness is in NP, modulo GRH, Adv. Math. 256 (2014), 493–506
[39] S. Lawton, Generators, relations and symmetries in pairs of 3 × 3 unimodular matrices, J. Algebra 313
(2007), 782–801.
[40] D. Lee, Translation equivalent elements in free groups, J. Group Theory 9 (2006), 809–814.
[41] D. Lee, An algorithm that decides translation equivalence in a free group of rank two, J. Group Theory
10 (2007), 561–569.
[42] D. Lee, E. Ventura, Volume equivalence of subgroups of free groups, J. Algebra 324 (2010), 195–217.
[43] C. J. Leininger, Equivalent curves in surfaces, Geom. Dedicata 102 (2003), 151–177.
[44] D. D. Long, A. W. Reid, Integral points on character varieties, Math. Ann. 325 (2003), 299–321.
[45] L. Louder, D. B. McReynolds, P. Patel, Zariski Closures and Subgroup Separability, ArXiV (2015).
[46] R. C. Lyndon, P. E. Schupp, Combinatorial group theory, Springer–Verlag, 1977.
[47] A. I. Mal’cev, On the faithful representation of infinite groups by matrices, Mat. Sb. 8 (1940), 405–422.
[48] A. I. Mal’cev, On homomorphisms onto finite groups, Uchen. Zap. Ivanovskogo Gos. Ped. Inst. 18
(1958), 49–60.
[49] J. Malestein, A. Putman, On the self-intersections of curves deep in the lower central series of a surface
group, Geom. Dedicata 149 (2010), 73–84.
[50] L. Paris, Residual p properties of mapping class groups and surface groups, Trans. Amer. Math. Soc.
361 (2008), 2487–2507
[51] P. Patel, On a theorem of Peter Scott, Proc. Amer. Math. Soc. 142 (2014), 2891–2906.
[52] P. Patel, On the residual finiteness growths of particular hyperbolic manifold groups, ArXiV, to appear
in Geom. Dedicata.
[53] M. Pengitore, Effective conjugacy separability of finitely generated nilpotent groups, ArXiV (2015).
[54] V. Platonov, A. Rapinchuk, Algebraic groups and number theory, Academic Press, 1994.
[55] C. Procesi, The invariant theory of n × n matrices, Adv. Math. 19 (1976), 306–381.
[56] M. S. Raghunathan, Discrete subgroups of Lie groups, Springer–Verlag, 1972.
[57] A. Rapinchuk, V. Benyash-Krivetz, V. Chernousov, Representation varieties of the fundamental groups
of compact orientable surfaces, Israel J. Math. 93 (1996), 29–71.
[58] V. N. Remeslennikov, Conjugacy in polycyclic groups, Akademiya Nauk SSSR. Sibirskoe Otdelenie.
Institut Matematiki. Algebra i Logika, 8 (1969), 712–725.
[59] I. Rivin, Geodesics with one self-intersection, and other stories, Adv. Math. 231 (2012), 2391–2412.
[60] H. Schoutens, The Use of Ultraproducts in Commutative Algebra, Springer–Verlag, 2010.
[61] O. Schreier, Die Untergruppen der freien Gruppe, Abhandlungen aus dem Mathematischen Seminar
der Universität Hamburg 5 (1927), 161–183.

Decision problems, complexity, traces, and representations

19

[62] G. W. Schwarz, The topology of algebraic quotients, Progr. Math. 80 (1989), 135–151.
[63] G. P. Scott, Subgroups of surface groups are almost geometric, J. London Math. Soc. 17 (1978) 555–
565; J. London Math. Soc. 32 (1985) 217–220.
[64] Z. Sela, Diophantine geometry over groups. I. Makanin-Razborov diagrams, Publ. Math. Inst. Hautes
Études Sci. 93 (2001), 31–105.
[65] P. F. Stebe, Conjugacy separability of groups of integer matrices, Proc. Amer. Math. Soc. 32 (1972),
1–7.
[66] E. Toinet, Conjugacy p–separability of right-angled Artin groups and applications, Groups Geom. Dyn.
7 (2013), 751–790.
[67] A. Thom, About the length of laws for finite groups, ArXiv (2015).
[68] B. A. F. Wehrfritz, Conjugacy separating representations of free groups, Proc. Amer. Math. Soc. 40
(1973), 52–56.
[69] H. Wilton, Virtual retractions, conjugacy separability and omnipotence, J. Algebra 323 (2010), 323–
335.
Lawton: George Mason University, Fairfax, VA 22030. slawton3@gmu.edu
Louder: University College London, London, UK, WC1E 6BT. l.louder@ucl.ac.uk
McReynolds: Purdue University, West Lafayette IN 47907. dmcreyno@purdue.edu

