Uniform Exponential Growth for Linear Groups

Alex Eskin^{∗}, Shahar Mozes^{†}and Hee Oh^{‡}

August 23, 2001

1 Introduction

Let Γ be a finitely generated group. Given a finite set of generators S one has the corresponding Cayley graph C(Γ, S) and a word metric d_{S} on Γ. Let us denote by

B_{S}(n) = {γ ∈ Γ : d_{S}(γ, e) ≤ n},

the ball of radius n in the Cayley graph C(Γ, S).

Definition 1.1. We shall say that Γ has exponential growth if

ω_{S}(Γ) ≡ lim_{n→∞} |B_{S}(n)|^{1/n} > 1,

or equivalently, lim_{n→∞} \frac{1}{n} log |B_{S}(n)| > 0.

Note that if Γ has this property with respect to some generating set S, it has it with respect to an arbitrary set of generators.

Definition 1.2. We shall say that Γ has uniform exponential growth if

inf_{S} ω_{S}(Γ) > 1,

where the infimum is taken over all finite generating sets S of Γ. Equivalently Γ has uniform exponential growth if and only if there is some c > 1 so that for any generating set S and all n ≥ 0 we have |B_{S}(n)| ≥ c^{n}.

∗Research partially supported by the Packard Foundation.

†Research partially supported by the BSF.

‡Research partially supported by NSF grant DMS0070544.

A central question concerning groups of exponential growth which goes back to the book [4] is whether a group Γ of exponential growth is necessarily also of uniform exponential growth. This was shown to be the case when the group Γ is hyperbolic by M. Koubi [5] (see also [2]) and in the case when Γ is solvable independently by D. Osin [8] and J. Wilson [11]. Recently R. Alperin and G. Noskov [1] have announced an affirmative answer for certain subgroups of SL_{2}(ℂ). For a general discussion of these questions see the survey [3]. Our main result is the following:

Theorem 1.3. Let Γ be a finitely generated group which is linear over a field of characteristic 0. Then Γ has exponential growth if and only if it has uniform exponential growth.

Recalling that a linear group is of exponential growth if and only if it is not virtually nilpotent (see [10], [7], [12]) we have an equivalent formulation:

Corollary 1.4. If Γ is a finitely generated group which is linear over a field of characteristic 0, then either Γ has uniform exponential growth or it is virtually nilpotent.

2 Basic Observations

Note that if a homomorphic image of a group has uniform exponential growth then so does the original group. Also if a finite index subgroup has uniform exponential growth, then so does the original group. Thus in view of the theorem of Osin and Wilson mentioned above, we may assume that the Zariski closure of Γ is connected and simple, both in the algebraic sense.

Specialization. Let E be the field of coefficients of Γ. Note that since Γ is finitely generated it follows that E is finitely generated. Using the fact (see [6]) that if a finitely generated subgroup Λ of GL_{n}(ℂ) is virtually solvable then there is a bound on the index of a solvable subgroup in Λ depending only on n, we deduce that there exists a “specialization” i.e. a field homomorphism σ : E → K inducing a homomorphism ρ : GL_{n}(E) → GL_{n}(K) where K is a finite extension of ℚ so that ρ(Γ) is not virtually solvable. Hence we may assume that we have a finitely generated group Γ contained in SL_{n}(K) with K a number field and having a simple connected Zariski closure. Since Γ is finitely generated, we may, after possibly replacing Γ by a finite index subgroup, assume that there is some finite set of places S of the field K (which includes all the archimedean ones) so that Γ ⊂ SL_{n}(O_{K}(S)), where O_{K}(S) denotes the ring of Sintegers in K. Thus the diagonal embedding of Γ in ∏_{ν∈S} SL_{n}(K_{ν}) is discrete, where K_{ν} denotes the completion of K with respect to the absolute value | · |_{ν} associated with the place ν ∈ S. We choose, for each ν, an extension of the absolute value | · |_{ν} to the algebraic closure of K.

Notation and terminology. Let us set the following convention of terminology which makes some of the statements in the sequel more transparent. We shall use the term “bounded” to mean “bounded with a bound depending only on the dimension of the linear representation, the number field K and the set of places S. We shall use the notation x ≺ y or equivalently y ≻ x to mean that there exist bounded positive constants c_{1} and c_{2} such that x < c_{1}y^{c_{2}}. This is used only when y ≥ 1. For a matrix A ∈ SL_{n}(K̄), we define ∥A∥_{ν} = max_{ij} |A_{ij}|_{ν}, and ∥A∥ = max_{ν∈S} ∥A∥_{ν}.

The following lemma plays a basic role and is one of the reasons why we need to specialize so that the field of coefficients of Γ is a number field.

Lemma 2.1. For every A ∈ SL_{n}(O_{K}(S)), let λ_{1}, …, λ_{r} be the distinct eigenvalues of A. Then

∏_{ν∈S} ∏_{i≠j} |λ_{i} − λ_{j}|_{ν} ≥ 1  (1)

Hence for any i ≠ j and any ν ∈ S we have \frac{1}{|λ_{i}−λ_{j}|_{ν}} ≺ ∥A∥.

Proof. The left hand side of (1) is the absolute value of a non-zero (rational) integer, and is therefore at least 1.

In the course of the argument we shall need certain words of bounded length with respect to any generating set of the group Γ to be as regular as possible. We shall use the following:

Lemma 2.2. Let H be the connected Zariski closure of Γ and let Z ⊊ H be any Zariski closed proper subset of H. Then there exists N = N(Z, H) ≥ 1 such that for any finite generating set S of Γ, B_{S}(N) ⊄ Z.

Lemma 2.2 is proved using the generalized Bezout theorem.

To show that our group Γ has uniform exponential growth we shall show that there is some bounded constant m so that given any finite generating set S there exists a pair of elements in the ball B_{S}(m) generating a free semigroup. We recall the well-known result of J. Tits [10] which states that any non-virtually-solvable linear group contains two elements A and B which generate a free subgroup; the proof is based on the so called “ping-pong lemma”. Our result may be viewed as a sort of quantitative version of Tits’ theorem, in the sense that we obtain a uniform bound on the word length of the elements A and B; however our elements are only guaranteed to generate a free semigroup.

Showing that a pair of elements generates a free semigroup is based on the following version of the ping-pong lemma which is due to G. A. Margulis.

Definition 2.3 (Ping-Pong Pair). Let k be a local field. A pair of matrices A, B ∈ SL_{n}(k) is a ping-pong pair if there exists a nonempty set U ⊂ ℙ(k^{n}) such that:

BU ∩ U = ∅
ABU ⊂ U, A^{2}BU ⊂ U

Lemma 2.4 (Margulis). If A, B are a ping-pong pair then AB and A^{2}B generate a free semigroup.

To apply this lemma we need an effective way of showing that certain elements form a ping-pong pair.

Lemma 2.5. Let k be a local field with an absolute value | · |_{ν}. Suppose that A, B ∈ SL_{n}(k) are matrices such that after conjugation of both by a common matrix we have:

(L1) A = (\begin{matrix}a_{1} \\ & a_{2} \\ & & . & . & . \\ & & & & & a_{n} \end{matrix}) with |a_{1}|_{ν} ≥ |a_{2}|_{ν} ≥ · ≥ |a_{n}|_{ν} and |a_{1}|_{ν} ≥ max(2, 2|a_{2}|_{ν}).

(L2) There exist constants c_{2} > 0, d_{2} > 0 such that \frac{1}{|B_{11}|_{ν}} ≤ c_{2}∥A∥_{ν}^{d_{2}}, and Be_{1} ∉ ke_{1}.

(L3) There exist constants c_{3} > 0, d_{3} > 0 such that ∥B∥_{ν} ≤ c_{3}∥A∥_{ν}^{d_{3}}.

Then there exists a constant m, depending only on n, c_{2}, c_{3}, d_{2} and d_{3}, such that A^{m} and B form a ping-pong pair.

3 The steps of the proof

Step 1. Using Lemma 2.2 one deduces that given any finite generating set S of Γ there is a pair of elements A, B of Γ belonging to a ball of bounded diameter in the Cayley graph C(Γ, S) so that any word of a certain very large but bounded length in A and B yields an H-regular element, where H denotes the Zariski closure of Γ. (By an H-regular element we mean a semisimple element the dimension of whose centralizer is equal to the rank of H. Such elements exist in H by [9].) Moreover (using Lemma 2.2 for Γ × Γ < H × H) we may require also that no two of these bounded length words lie in a common parabolic subgroup of H. We shall actually require these regularity and genericity conditions also for all the corresponding words in ρ_{m}(A) and ρ_{m}(B) where ρ_{m} denotes the m’th wedge representation of SL_{n}, 1 ≤ m ≤ n.

For the next two steps, it is convenient to use the diagonal embedding and consider A and B as elements of G = ∏_{ν∈S} SL_{n}(K̄_{ν}). Also for a matrix C = ∏_{ν∈S} C_{ν} ∈ G, we write ∥C∥_{ν} = max_{ij} |(C_{ν})_{ij}|_{ν}, and ∥C∥ = max_{ν∈S} ∥C∥_{ν}.

Step 2. As A is semisimple we may conjugate both A and B by the same matrix in G so that A becomes diagonal. Conjugating by an appropriate element from the centralizer of A and possibly replacing B by some word of bounded length in A and B we may ensure that either:

∥B∥ ≺ ∥A∥,  (2)

or, for some bounded m,

∥A∥^{m} max_{ν∈S} | Tr B|_{ν} ≻ ∥B∥.  (3)

Step 3. We claim we can modify our choice of A and B and conjugate by a common matrix in G so that (2) holds and A is diagonal.

Indeed, suppose (2) does not hold. Then, in view of Step 2, (3) holds. Also since (2) does not hold, we may assume

∥A∥^{m} ≤ ∥B∥^{1/2},  (4)

where m is as in (3). (Recall that A is diagonal and has determinant 1, hence ∥A∥ ≥ 1.) Hence, in view of Lemma 2.1 and the semisimplicity of B, we can diagonalize B ∈ G using a matrix C ∈ G such that max{∥C∥, ∥C^{−1}∥} ≺ ∥B∥. Hence in view of (4),

∥CAC^{−1}∥ ≤ ∥C∥∥A∥∥C^{−1}∥ ≺ ∥B∥.  (5)

Since CBC^{−1} is diagonal, and in view of (3) and (4),

∥CBC^{−1}∥ ≻ max_{ν∈S} | Tr B|_{ν} ≻ ∥A∥^{−m}∥B∥ ≥ ∥B∥^{1/2}  (6)

Hence in view of (5) and (6), ∥CBC^{−1}∥ ≻ ∥CAC^{−1}∥. Hence if (2) fails we can conjugate A and B by C and interchange the roles of A and B.

Step 4. Let ν ∈ S be such that ∥A∥_{ν} is maximal. Let ρ_{m} be as in Step 1. From the discreteness of SL_{n}(O_{K}(S)), there exists m, 1 ≤ m ≤ n/2 such that ρ_{m}(A_{ν}) satisfies (L1). Note that in view of (2) we have (L3) for the elements ρ_{m}(A_{ν}) and ρ_{m}(B_{ν}). Next we claim that by replacing ρ_{m}(B_{ν}) by a bounded word in ρ_{m}(A_{ν}) and ρ_{m}(B_{ν}) we can ensure that (L2) is satisfied. Thus we produced a ping-pong pair using words of bounded length in the given set of generators.

4 Construction of words with nice properties

Observe that in steps 2 and 4 above we need to produce words of bounded length so that the coefficients of the corresponding matrices satisfy certain properties. Let us describe first how this is achieved in the case where the Zariski closure of our group Γ is SL_{n}. The reason for this case being simpler than the general one is that in this case we may assume that the diagonalized matrix ρ_{m}(A) has distinct eigenvalues. For the following, we fix ν ∈ S. Also let us for simplicity of notation speak about A and B rather than about ρ_{m}(A) and ρ_{m}(B), and write | · | and ∥ · ∥ rather than | · |_{ν} and ∥ · ∥_{ν}. For a constant c > 0 define an entry B_{ij} of B to be large when |B_{ij}| > c∥B∥. Let E(c) denote the algebra generated by all the elementary matrices E_{ij} corresponding to large entries of B. The following lemma is used twice, once in the proof of Step 2, with c being a small absolute constant, and once in the proof of Step 4, with c = ∥A∥^{−m}, with m a large but bounded positive constant.

Lemma 4.1. If E_{ij} ∈ E(c) then there exists a bounded word C in A and B so that |C_{ij}| > p∥A∥^{−k}∥B∥^{l} where p, k and l are bounded positive constants.

Rather than giving here the proof of the lemma let us give an example explaining the main idea. Assume that B_{12} and B_{21} are big entries. Then we claim that some word of the form BA^{k}B with 0 ≤ k ≤ n − 1 has big (1, 1) entry. Indeed we have

(BA^{k}B)_{11} = ∑_{i} B_{1i}B_{i1}a_{i}^{k}.  (7)

Note that B_{12}B_{21} is a large term, but a priori, it may cancel with other terms. However, it may not happen for all 0 ≤ k ≤ n − 1, in view of Lemma 2.1. More formally, we may argue as follows: Written vectorially, (7) is

( (BA^{0}B)_{11} ; (BA^{1}B)_{11} ; ⋮ ; (BA^{n−1}B)_{11})) = (1 a_{1} a_{1}^{2} … a_{1}^{n−1} ; 1 a_{2} a_{2}^{2} … a_{2}^{n−1} ; ⋮ ; 1 a_{n} a_{n}^{2} … a_{n}^{n−1}) ( B_{11}^{2} ; B_{12}B_{21} ; ⋮ ; B_{1n}B_{n1})

Hence using the formula for the Vandermonde determinant and Lemma 2.1 we deduce that since we have B_{12}B_{21} big we cannot have (BA^{k}B)_{11} small for all 0 ≤ k ≤ n − 1.

Almost Algebras. In the general case, another technical device is needed. For matrices A and B, let ⟨A, B⟩ = tr AB^{t}, and let ϵ > 0 be a small parameter. We say that matrices A_{1}, … A_{k} form an ϵ-almost-algebra if for each 1 ≤ i, j ≤ k, ⟨A_{i}, A_{j}⟩ = δ_{ij}, and A_{i}A_{j} is within ϵ of a linear combination of A_{1}, …, A_{k}.

For each 1 ≤ m ≤ n^{2} + 2, let us choose constants ϵ_{m} so that ϵ_{m+1} ≪ ϵ_{m}, and ϵ_{1} ≪ ϵ. Now let B_{1}, … B_{m} be matrices of norm at most 1. For each 1 ≤ k ≤ n^{2} + 1, let

f(k) = inf{m ∈ ℕ| there exists a subspace V_{m} of dimension m such that all words

in the B_{i} of length at most 2^{k} are within ϵ_{k} of V_{m}. }

By construction, the function f is increasing, and is bounded by n^{2}. Hence there exists a minimal k, 1 ≤ k ≤ n^{2}+1 such that f(k) = f(k+1). Then an orthonormal basis for V_{f(k)} is an ϵ-almost-algebra. We call it the almost-algebra generated by B_{1}, …, B_{m}.

In the proof we use, as a replacement to E(c), the almost-algebra generated by the “blocks” of B, (i.e. the projections of B onto the eigenspaces of Ad(A)). It is easy to see that the analog of Lemma 4.1 is satisfied. Also, in the appropriate sense, every almost algebra is near an algebra. This allows us to complete the proof.

References

[1] R. Alperin, G. Noskov. “Uniform Growth, Actions on Trees and GL_{2}.” math.GR/0105083.

[2] T. Delzant. “Sous-groupes distingués et quotients des groupes hyperboliques.” Duke Math. J. 83 (1996), pp. 661–682.

[3] R. Grigorchuk, P. de la Harpe. “On problems related to growth, entropy, and spectrum in group theory.” J. Dynam. Control Systems 3 (1997), no. 1, 51–89.

[4] M. Gromov. Structures mtriques pour les varits riemanniennes. (French) [Metric structures for Riemann manifolds] Edited by J. Lafontaine and P. Pansu. Textes Mathmatiques [Mathematical Texts], 1. CEDIC, Paris, 1981.

[5] M. Koubi. “Croissance uniforme dans les groupes hyperboliques.” Ann. Inst. Fourier 48 (1998), 1441-1453.

[6] A. Lubotzky, A. Mann. “On groups of polynomial subgroup growth.” Invent. Math. 104 (1991), no. 3, pp. 521–533.

[7] J. Milnor. “Growth of finitely generated solvable groups.” J. of Diff. Geometry 2 (1968), pp. 447–449.

[8] D. Osin. “The entropy of solvable groups.” Preprint (2000).

[9] G. Prasad. “R-regular elements in Zariski-dense subgroups.” Quart. J. Math. Oxford Ser. (2) 45 (1994), no. 180, 541–545.

[10] J. Tits. “Free subgroups in linear groups.” J. Algebra 20 (1972), pp. 250–270.

[11] J. Wilson. Preprint.

[12] J. Wolf. “Growth of finitely generated solvable groups and curvature of Riemanniann manifolds.” J. of Diff. Geometry 2 (1968), pp 421–446.

Department of Mathematics, University of Chicago, Chicago IL 60637, USA; eskin@math.uchicago.edu

Institute of Mathematics, Hebrew University, Jerusalem 91904, ISRAEL; mozes@math.huji.ac.il

Department of Mathematics, Princeton University, Princeton NJ, USA; heeoh@math.princeton.edu