On Uniform Exponential Growth for Linear Groups

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

August 6, 2004

1 Introduction

Let Γ be a finitely generated group. Given a finite set of generators S of Γ, the word length l_{S}(γ) for an element γ ∈ Γ is defined to be the smallest positive integer for which there exist s_{1}, ⋯, s_{n} ∈ S ∪ S^{−1} such that γ = s_{1} ⋯ s_{n}.

For each n ∈ ℕ, denote by B_{S}(n) the set of elements in Γ whose word length with respect to S is at most n. It follows from the subadditive property of l_{S}(·) that lim_{n→∞} |B_{S}(n)|^{1/n} exists, which we denote by ω_{S}(Γ).

A finitely generated group Γ is said to be of exponential growth if ω_{S}(Γ) > 1, of polynomial growth if for some c > 0 and d ∈ ℕ, |B_{S}(n)| ≤ c · n^{d} for all n ≥ 1 and of intermediate growth otherwise, for some finite generating set S of Γ. Observe that the growth type of Γ does not depend on the choice of generating set S.

If a finitely generated group Γ is linear, it is known that Γ is either of polynomial growth in which case Γ is virtually nilpotent, or of exponential growth otherwise ([Tit72], [Mil68], [Wol68]).

Definition 1.1. A finitely generated group Γ is said to have uniform exponential growth if

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

where the infimum is taken over all finite generating sets S of Γ.

∗Research partially supported by the Packard Foundation and the BSF.

†Research partially supported by the BSF.

‡Research partially supported by NSF grant DMS0070544 and 0333397.

A main open problem concerning the growth property of a group is whether a group Γ of exponential growth is necessarily of uniform exponential growth, as first asked by Gromov (Remark 5.12 of [Gro81]).

This was answered affirmatively in the case when Γ is hyperbolic by M. Koubi [Kou98] (see also [Del96]) and in the case when Γ is solvable independently by D. Osin [Osi03] and J. Wilson [Wil00]. Recently R. Alperin and G. Noskov [AN] have announced an affirmative answer for certain subgroups of SL_{2}(ℂ). For a general discussion of these questions see the survey [GdlH97].

While writing the final version of the paper we have learned from J. Wilson that he has recently constructed groups having exponential growth but not uniform exponential growth [Wil02].

Our main result is the following:

Theorem 1.2. Let Γ be a finitely generated group which is linear over a field of characteristic 0 and not virtually solvable. Then there exists a positive integer n depending only on Γ such that for any finite generating set S of Γ, B_{S}(n) contains two elements generating free semi subgroup.

This immediately implies:

Theorem 1.3. Let Γ be as above. Then Γ has uniform exponential growth.

Combined with the results of Osin and Wilson mentioned above, our theorem implies the following:

Corollary 1.4. Let Γ be a finitely generated subgroup of GL_{n}(ℂ). The following are equivalent:

• Γ is not virtually nilpotent

• Γ is of uniform exponential growth.

• Γ is of exponential growth.

Recall that for a compact Riemannian manifold M, the volume entropy h_{vol}(M) is given by

h_{vol}(M) = lim_{r→∞} \frac{log V_{x}(r)}{r}

where V_{x}(r) denotes the volume of the ball of radius r centered at (any) x in the universal cover M̃ with the induced metric.

One motivation for studying the notion of uniform exponential growth is the observation that if the fundamental group of a compact manifold M has uniform exponential growth then one has a positive lower bound on the volume entropy for any Riemannian metric on M of normalized diameter.

On the other hand, Manning showed that the topological entropy h_{top}(M) (see [Ma79] for definition) of the geodesic flow on the unit tangent bundle of a compact Riemannian manifold M is bounded below by the volume entropy h_{vol}(M) of M [Ma79].

Thus, we have the following:

Corollary 1.5. Let M be a compact manifold such that π_{1}(M) is linear over a field of characteristic 0 and not virtually nilpotent. Then

inf h_{top}(g) ≥ inf h_{vol}(g) > 0

where the infimum is taken over all Riemannian metric g on M with normalized diameter.

An announcement of our result has appeared in [EMO] with an account for a main strategy. The approach is outlined in §2. Sections §3-§7 are preparation for the proof of the main Theorem 1.3, which is given in §8. With the exception of Lemma 4.2, only the results labelled propositions are used in the sequel.

2 A version of the ping-pong lemma.

To show that a non virtually solvable subgroup Γ < GL_{n}(ℂ) 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 (with respect to the word metric corresponding to the generating set S) B_{S}(m) generating a free non-abelian semigroup. We recall the well-known result of J. Tits [Tit72] which states that any non-virtually-solvable linear group contains two elements A and B which generate a free non-abelian subgroup; the proof is based on the so called “ping-pong lemma”. Theorem 1.2 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.1 (Ping-Pong Pair). Let V be a finite dimensional vector space. A pair of matrices A, B ∈ SL(V) is a ping-pong pair if there exists a nonempty subset U ⊂ ℙ(V) such that

• BU ∩ U = ∅;

• ABU ⊂ U and A^{2}BU ⊂ U.

Lemma 2.2. If a pair A, B ∈ SL(V) is a ping-pong pair then AB and A^{2}B generate a free semigroup.

Proof. Suppose that the semigroup generated by AB and A^{2}B is not free. Then (after some cancellation) we could find a relation of the form w_{1} = w_{2}, where w_{1} and w_{2} are words in AB and A^{2}B with w_{1} starting with A^{2}B and w_{2} starting with AB. But this is a contradiction since we have A^{−1}w_{1}U ⊂ U and A^{−1}w_{2}U ∩ U = ∅, and hence A^{−1}w_{1} ≠ A^{−1}w_{2}.

The above lemma clearly yields:

Proposition 2.3. Let Γ be a finitely generated subgroup of SL(V). Suppose that there exists an integer N ∈ ℕ such that for any finite generating subset S of Γ, B_{S}(N) contains a ping-pong pair A and B. Then Γ has the uniform exponential growth property.

Notation: Let k be a local field (with char k = 0) endowed with an absolute value | · | and V a k-vector space of dimension n. By fixing a basis, we identify V with k^{n}. We fix a norm ∥ · ∥ on V by

∥(x_{1}, ⋯, x_{n})∥ = max{|x_{i}| | 1 ≤ i ≤ n}.

Define a distance d on the projective space ℙ(V) = ℙ(k^{n}) by

d(x_{1}, x_{2}) = {inf ∥v_{1} − v_{2}∥ | v_{i} ∈ x_{i}, ∥v_{i}∥ = 1 for each i = 1, 2}.

If X_{1} and X_{2} are closed subsets of ℙ(V), we set d(X_{1}, X_{2}) to be the Hausdorff distance between X_{1} and X_{2}, that is,

d(X_{1}, X_{2}) = sup{d(x_{i}, X_{j}) | x_{i} ∈ X_{i}, {i, j} = {1, 2}}

where d(x_{i}, X_{j}) = inf{d(x_{i}, x_{j}) | x_{j} ∈ X_{j}}. We also set a norm on the space M_{n}(k) of n × n matrices by

∥A∥ = max{|A_{ij}| | 1 ≤ i, j ≤ n}.

Before we state an effective way of showing that a pair of matrices is a ping-pong pair, we need the following simple lemma:

Lemma 2.4. There exist a constant C > 0 and a positive integer l, depending only on n, such that

d(Bx, By) ≤ C · ∥B∥^{l} · d(x, y)

for any B ∈ SL(V) and for any x, y ∈ ℙ(V).

Proof: We first claim that there exists a positive constant C′ and a positive integer m such that for any B ∈ SL(V),

C′ · ∥B∥^{−m} ≤ inf{∥Bv∥ | v ∈ V, ∥v∥ = 1}.

Since any matrix in SL(V) can be brought into a diagonal form by multiplying orthogonal matrices from both sides, we may assume that B is a diagonal matrix; and then the claim is clear since detB = 1.

Now let v and w be unit vectors in V such that v ∈ x and w ∈ y. Then

∥\frac{Bv}{∥Bv∥} − \frac{Bw}{∥Bw∥}∥ ≤ \frac{∥B∥ · ∥v − w∥}{inf\{∥Bv∥ | v ∈ V, ∥v∥ = 1\}} ≤ \frac{1}{C′} ∥B∥^{m+1} · ∥v − w∥.

Hence,

d(Bx, By) ≤ \frac{1}{C′} · ∥B∥^{m+1} · d(x, y).

Let e_{1}, … e_{n} ∈ k^{n} denote the standard basis, and let ē_{1}, …, ē_{n} ∈ ℙ(k^{n}) denote the corresponding points in projective space.

Proposition 2.5. Let c_{1}, c_{2}, c_{3}, κ_{1}, κ_{2}, and κ_{3} be fixed positive constants. Suppose that A, B ∈ SL_{n}(k) are matrices such that

(L1) A = diag(a_{1}, ⋯, a_{n}) with |a_{1}| ≥ |a_{2}| ≥ ⋯ ≥ |a_{n}| and

\frac{|a_{1}|}{|a_{2}|} ≥ max(2, c_{1}∥A∥^{κ_{1}})

for some constants c_{1} > 0 and κ_{1} > 0;

(L2) ∥A∥ ≥ c_{2}∥B∥^{1/κ_{2}} for some constants c_{2} > 0 and κ_{2} ≥ 1.

(L3) |B_{11}| ≥ c_{3}∥A∥^{−κ_{3}} and Be_{1} ∉ ke_{1} for some constants c_{3} > 0 and κ_{3} ≥ 0;

Then there exists a constant m ∈ ℕ (depending only on n, c_{1}, c_{2}, c_{3}, κ_{1}, κ_{2}, κ_{3} and the field k) such that A^{m} and B form a ping-pong pair.

Proof: Denote by W the projective hyperplane spanned by e_{2}, ⋯, e_{n}. Let c_{B} = C · ∥B∥^{l} be as in Lemma 2.4.

Case 1: d(ē_{1}, Bē_{1}) ≤ \frac{1}{2} · d(ē_{1}, W) = \frac{1}{2}.

Set

δ = \frac{d(ē_{1}, Bē_{1})}{4(c_{B} + 1)}

and U = 𝔹(ē_{1}, δ), i.e., the open ball of radius δ with the center ē_{1} in ℙ(k^{n}). To show that BU ∩ U = ∅, assume the contrary, i.e., there exists v ∈ BU ∩ U. Let u ∈ U such that Bu = v. Then

d(Bē_{1}, ē_{1}) ≤ d(Bē_{1}, Bu) + d(v, ē_{1}) ≤ c_{B}d(ē_{1}, u) + d(v, ē_{1}) < δ(c_{B} + 1) < d(Bē_{1}, ē_{1}).

This contradiction proves the claim that BU ∩ U = ∅.

Note that for any z ∈ BU,

d(ē_{1}, z) ≤ d(ē_{1}, Bē_{1}) + d(Bē_{1}, B(B^{−1}z)) ≤ d(ē_{1}, Bē_{1}) + c_{B} · δ ≤ \frac{5}{4}d(ē_{1}, Bē_{1}), (1)

and hence BU ⊂ 𝔹(ē_{1}, \frac{5}{4}d(ē_{1}, Bē_{1})) ⊂ 𝔹(ē_{1}, \frac{5}{8}). Now consider the “stereographic projection” map

π : 𝔹(ē_{1}, \frac{5}{8}) → \{x ∈ k^{n} | x_{1} = 1\}

defined by (x_{1}, ⋯, x_{n}) ↦ (1, \frac{x_{2}}{x_{1}} , ⋯, \frac{x_{n}}{x_{1}} ). Clearly π(A^{m}x) = A^{m}π(x). Note that there is a constant L ≥ 1 depending only on n, such that for all x ∈ 𝔹(ē_{1}, \frac{5}{8}),

L^{−1}∥π(x) − e_{1}∥ ≤ d(x, ē_{1}) ≤ L∥π(x) − e_{1}∥.  (2)

Also note that for any x ∈ ℙ \ W and any m ∈ ℕ,

∥A^{m}π(x) − e_{1}∥ ≤ |\frac{a_{2}}{a_{1}} |^{m} ∥π(x) − e_{1}∥.  (3)

In view of (L1) and (L2), since ∥A∥ = |a_{1}|, and c_{B} ≤ c·∥A∥^{κ} for c, κ > 0 depending only on n, c_{1}, c_{2}, κ_{1}, κ_{2}, there exists r_{0} ≥ 1 (depending only on n, c_{1}, c_{2}, κ_{1}, κ_{2}) such that for any m ≥ r_{0},

|\frac{a_{2}}{a_{1}} |^{m} ≤ \frac{1}{20L^{2} max(c_{B}, 2)}.  (4)

Hence for any z ∈ BU and any m ≥ r_{0},

d(A^{m}z, ē_{1}) ≤ L∥A^{m}π(z) − ē_{1}∥ ≤ L |\frac{a_{2}}{a_{1}} |^{m} ∥π(z) − ē_{1}∥ ≤ L^{2} |\frac{a_{2}}{a_{1}} |^{m} d(z, ē_{1})

≤ L^{2} \frac{5|a_{2}|^{m}}{4|a_{1}|^{m}} d(ē_{1}, Bē_{1}) ≤ \frac{1}{4} · \frac{c_{B} + 1}{max(c_{B}, 2)}δ ≤ \frac{1}{2}δ,

using (1), (4), and the definition of δ. Hence for any m ≥ r_{0}, A^{m}(B(U)) ⊂ U.

Case 2: d(ē_{1}, Bē_{1}) > \frac{1}{2} · d(ē_{1}, W) = \frac{1}{2}.

From (L2) and (L3), we have

\frac{|B_{11}|}{∥B∥} ≥ c_{2}c_{3}^{−κ_{3}}∥A∥^{−κ_{2}−κ_{3}}

and hence there exist constants c_{4} > 0 and κ_{4} > 0 (depending only on n, c_{2}, c_{3}, κ_{2} and κ_{3}) such that d(Bē_{1}, W) ≥ c_{4}∥A∥^{−κ_{4}}. Clearly we may assume c_{4} < 1. Set

δ = \frac{c_{4}}{4 · ∥A∥^{κ_{4}} · (c_{B} + 1)}

and U = 𝔹(ē_{1}, δ). Assume that there exists v ∈ BU ∩ U and let u ∈ U such that Bu = v. Then

d(Bē_{1}, ē_{1}) ≤ d(Bē_{1}, Bu) + d(v, ē_{1}) ≤ c_{B} · d(ē_{1}, u) + d(v, ē_{1})

< δ(c_{B} + 1) = \frac{c_{4}}{4∥A∥^{κ_{4}}} < d(Bē_{1}, ē_{1}),

since c_{4} < 1, κ_{4} ≥ 0, ∥A∥ ≥ 1, and d(ē_{1}, Bē_{1}) ≥ \frac{1}{2}. This contradiction proves that BU ∩ U = ∅.

Note that for any z ∈ BU,

d(z, W) ≥ d(Bē_{1}, W) − c_{B}δ ≥ \frac{c_{4}}{∥A∥^{κ_{4}}} − \frac{c_{B}c_{4}}{4∥A∥^{κ_{4}} · (c_{B} + 1)} ≥ \frac{3c_{4}}{4∥A∥^{κ_{4}}}

Hence

BU ⊂ X := \{z ∈ ℙ(k^{n}) : d(z, ē_{1}) ≤ 1 − \frac{3c_{4}}{4∥A∥^{κ_{4}}} \}.

Let π be the stereographic projection from X to {x ∈ V | x_{1} = 1} defined in the same way as in Case 1. Note that (2) holds with L ≤ 4d · \frac{∥A∥^{κ_{4}}}{3c_{4}} for some constant d > 0 depending only on n.

Hence for any z ∈ BU ⊂ X and any m ∈ ℕ,

d(A^{m}z, ē_{1}) ≤ L^{2} |\frac{a_{2}}{a_{1}} |^{m} d(z, ē_{1})

≤ L^{2} |\frac{a_{2}}{a_{1}} |^{m} ≤ d^{2} (\frac{4∥A∥^{κ_{4}}}{3c_{4}} )^{2} |\frac{a_{2}}{a_{1}} |^{m} = d^{2} (\frac{4∥A∥^{κ_{4}}}{3c_{4}} )^{2} (\frac{4∥A∥^{κ_{4}}(c_{B} + 1)}{c_{4}}) |\frac{a_{2}}{a_{1}} |^{m} δ.

Hence using (L2), there exist constants c_{5} > 0 and κ_{5} > 0 depending only on n, c_{1}, c_{2}, c_{3}, κ_{1}, κ_{2}, κ_{3} such that for any m ∈ ℕ

d(A^{m}z, ē_{1}) ≤ c_{5}∥A∥^{κ_{5}} |\frac{a_{2}}{a_{1}} |^{m} δ.

Thus, for some integer r_{0} ∈ ℕ (depending only on n, c_{1}, c_{2}, c_{3}, κ_{1}, κ_{2}, κ_{3}), A^{m}(BU) ⊂ U for all m ≥ r_{0}.

Remark: The strategy of the proof of Theorem 1.2 is to try to find words W_{1} and W_{2} of a length which is bounded independently of the generating set, and a matrix g such that A = gW_{1}g^{−1} and B = gW_{2}g^{−1} satisfy the conditions of Proposition 2.5.

3 Getting out of Zariski closed subsets

Theorem 3.1 (Generalized Bezout Theorem). Let X_{1}, …, X_{s} be pure-dimensional varieties over ℂ and let Z_{1}, …, Z_{t} be the irreducible components of X_{1} ∩ ⋯ ∩ X_{s}. Then

∑_{i=1}^{t} deg Z_{i} ≤ ∏_{j=1}^{s} deg X_{j}

(see: [Sch00, p. 519])

The aim of this section is to show the following proposition using the generalized Bezout theorem:

Proposition 3.2. Let Γ ⊂ GL_{n}(ℂ) be any finitely generated subgroup and let H denote the Zariski closure of Γ, which is assumed to be Zariski-connected. For any proper subvariety X of H, there exists N ≥ 1 (depending on X) such that for any finite generating set S of Γ, we have

B_{S}(N) ⊄ X.

The rest of this section is devoted to the proof of Proposition 3.2. Let Y = ∪_{i=1}^{n}Y_{i} ⊂ H be an algebraic variety where Y_{i}, 1 ≤ i ≤ n are the irreducible components of Y. Set d(Y) = max_{i} dim(Y_{i}). Denote by irr(Y) the number of irreducible components of Y, by irr_{md}(Y) the number of irreducible components of Y of the maximal dimension d(Y) and by mdeg(Y) the maximal degree of an irreducible component of Y.

Let S be any given finite generating set of Γ in what follows.

Lemma 3.3. If irr_{md}(Y) = 1 then there exists an element s ∈ S such that the variety Z = Y ∩ sY satisfies d(Z) < d(Y).

Proof. Without loss of generality we may assume that Y_{1} is the unique irreducible component of maximal dimension. If for every s ∈ S we have sY_{1} = Y_{1} then it would follow that Y_{1} is invariant under the group generated by S. However as this subgroup is Zariski dense and Y_{1} is a proper closed subvariety it follows that this is impossible; hence there is some s ∈ S such that sY_{1} ≠ Y_{1}. It follows that d(sY ∩ Y) < d(Y).

Lemma 3.4. Given Y as above there exists an s ∈ S such that for Z = Y ∩sY either d(Z) < d(Y) or irr_{md}(Z) < irr_{md}(Y).

Proof. Consider the set M of all maximal dimension irreducible components of Y. If every element of S would have mapped this set into itself it would have been ⟨S⟩-invariant and this would contradict the assumption that Γ = ⟨S⟩ is Zariski dense whereas Y is a Zariski closed proper subset. Hence there is some s ∈ S so that for some element Y_{i} ∈ M sY_{i} ∉ M and it follows that for Z = Y ∩sY either d(Z) < d(Y) or irr_{md}(Z) < irr_{md}(Y).

Lemma 3.5. Let Y be a proper subvariety of H. Then there exists an integer m ∈ ℕ (depending only on irr(Y) and mdeg(Y)) and a sequence of m elements s_{0}, s_{1}, ⋯, s_{m−1} of S so that if we define the following sequence of varieties V_{0} = Y, V_{i+1} = V_{i} ∩ s_{i}V_{i}, 0 ≤ i ≤ m − 1, then V_{m} satisfies d(V_{m}) < d(Y). Moreover irr(V_{m}) as well as mdeg(V_{m}) are also bounded above by constants depending only on irr(Y) and mdeg(Y).

Proof. We shall be applying Theorem 3.1 to the intersections of pairs of irreducible varieties. Namely, let W = ∪_{i=1}^{n}W_{i} be the decomposition of a Zariski closed variety W into irreducible components. Then we have W̃ = W ∩ sW = ∪_{i,j=1}^{n}W_{i} ∩ W_{j}. Thus given n = irr(W) and mdeg(W) we have an estimate both on irr(W̃) as well as on mdeg(W̃). Combining this observation with Lemmas 3.3 and 3.4 one can deduce Lemma 3.5.

Proof of Proposition 3.2. By repeated application of Lemma 3.5 at most d(X)+1 times we find elements w_{1}, w_{2}, …, w_{t} ∈ B_{S}(n), where n ≥ 2 is bounded above by some bound depending only on irr(X) and mdeg(X), so that ∩_{i=1}^{t}w_{i}X = ∅.

Observe that this implies that B_{S}(n) ⊄ X. Indeed if B_{S}(n) were contained in X, then it would follow that e ∈ ∩_{i=1}^{t}w_{i}X, as B_{S}(n) = B_{S}(n)^{−1} and hence w_{i}^{−1} ∈ B_{S}(n) for each 1 ≤ i ≤ t.

4 Specialization

Note that if a homomorphic image of a finitely generated group has uniform exponential growth then so does the original group. Also if Γ′ is a subgroup of Γ with index d, then for any finite generating set S of Γ, B_{S}(2d − 1) contains a generating set for Γ′ (see [ShaWa92]).

Thus in view of the theorem of Osin and Wilson mentioned in the introduction, we may assume in proving Theorem 1.2 that the Zariski closure of Γ is connected and simple, both in the algebraic sense.

Specialization. Let E be the ring generated by the coefficients of Γ. Note that since Γ is finitely generated it follows that E is finitely generated. Using the fact (see [LM91]) that if a finitely generated subgroup Λ of GL_{n}(ℂ) is virtually solvable then there is an upper bound (say M) on the index of a solvable subgroup in Λ depending only on n, we deduce that there exists a “specialization” i.e. there exists an appropriate number field K and a ring homomorphism σ : E → K inducing a homomorphism ρ : GL_{n}(E) → GL_{n}(K) so that ρ(Γ) is not virtually solvable. Indeed let Γ_{0} = ⋂_{|Γ/Λ|≤M} Λ and choose a number field K and a ring homomorphism σ : E → K so that the image of the finite index subgroup Γ_{0} under the induced homomorphism ρ is not solvable. The existence of such K and σ can be deduced as follows: For a solvable subgroup H of SL(n, ℂ) one has that the commutator group H′ = [H, H] is nilpotent of degree at most n − 1. On the other hand, since the group Γ_{0} is not solvable, its n-th commutator subgroup Γ_{n} is not trivial. Choose a non-trivial element g ∈ Γ_{n} and observe that there is a number field K and a ring homomorphism σ : E → K so that under the induced homomorphism ρ, the image of g is non-trivial (see [GS79] where a much stronger assertion is proved). It follows that the image of Γ_{0} under ρ is not solvable. The image ρ(Γ) < GL_{n}(K) cannot be virtually solvable since if it were it would follow that the image of Γ_{0} would be 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 connected Zariski closure which is simple.

Notational Conventions. Let K be a number field. Denote by V_{K} the equivalence classes of all valuations of K. For each ν ∈ V_{K}, we denote by K_{ν} the local field which is a completion of K with respect to ν and | · |_{ν} be the absolute value on K_{ν} given by ν. For any finite set of valuations S containing all the archimedean valuations, we denote by O_{K}(S) the ring of S-integral elements in K, that is,

O_{K}(S) = {x ∈ K | |x|_{ν} ≤ 1 for each ν ∉ S}

Since Γ is finitely generated, we may, after possibly replacing Γ by a finite index subgroup, assume that Γ ⊂ SL_{n}(O_{K}(S)), where S ⊂ V_{K} consists of all archimedean valuations as well as the valuations ν such that Γ is unbounded in GL_{n}(K_{ν}). Thus the diagonal embedding of Γ in ∏_{ν∈S} SL_{n}(K_{ν}) is discrete.

It follows that if Γ is infinite, then the image of Γ in ∏_{ν∈S} SL_{n}(K_{ν}) is unbounded under the diagonal embedding.

Summarizing the above discussion we have:

Proposition 4.1. It suffices to prove Theorem 1.2 for any finitely generated subgroup Γ ⊂ SL_{n}(O_{K}(S)) whose image in ∏_{ν∈S} SL_{n}(K_{ν}) is unbounded under the diagonal embedding, where K is a number field, S a finite set of valuations containing all archimedean valuations and the Zariski closure H of Γ is connected and simple.

Notational Convention. A positive constant depending only on n, K, H and S will be referred to in the rest of the paper as a bounded constant.

Remark. For any group Γ as in Proposition 4.1 the lower bound on the rate of exponential growth actually depends only on n, K, H and S.

We choose, for each ν ∈ S, an extension of the absolute value | · |_{ν} to the algebraic closure K̄ of K and denote by K̄_{ν} the completion of K̄ with respect to the valuation ν. For any A ∈ SL_{n}(O_{K}(S)), we set

Λ(A) := max{|λ|_{ν} | λ : an eigenvalue of A, ν ∈ S}.

For x = (x_{ν})_{ν∈S} ∈ ∏_{ν∈S} K̄_{ν} and A = (A_{ν})_{ν∈S} ∈ ∏_{ν∈S} SL_{n}(K̄_{ν}), we set

|x| = max_{ν∈S} |x_{ν}|_{ν} and ∥A∥ = max_{ν∈S} ∥A_{ν}∥_{ν}.

For A ∈ SL_{n}(O_{K}(S)), the notation ∥A∥ is understood via the identification of SL_{n}(O_{K}(S)) with its diagonal embedding into ∏_{ν∈S} SL_{n}(K̄_{ν}),

The following simple lemma plays a key role in the proof. It is the main reason we specialize so that Γ ⊂ SL_{n}(O_{K}(S)).

Lemma 4.2. Suppose A ∈ SL_{n}(O_{K}(S))). Then

(a) If λ_{1}, ⋯, λ_{m} is the set of all distinct eigenvalues of A, then

∏_{ν∈S} ∏_{1≤i<j≤m} |λ_{i} − λ_{j}|_{ν} ≥ 1.

(b) For each ν ∈ S,

∏_{1≤i<j≤m} |λ_{i} − λ_{j}|_{ν} ≥ C · Λ(A)^{−N},

for some positive constants C and N depending only on n and S.

Proof: First note that x := ∏_{1≤i<j≤m}(λ_{i}−λ_{j}) ∈ K, since ∏_{1≤i<j≤m}(λ_{i}−λ_{j}) is stable under the Galois group Gal (K̂/K) where K̂ is the splitting field of the characteristic polynomial of A. If ν ∉ S, A ∈ SL_{n}(O_{ν}) where O_{ν} denotes the valuation ring of K_{ν}; hence |λ_{i} − λ_{j}|_{ν} ≤ 1 for each 1 ≤ i ≠ j ≤ m. It follows that ∏_{ν∉S} |x|_{ν} ≤ 1. On the other hand, by the product formula, we have ∏_{ν∈V_{K}} |x|_{ν} = 1. Hence ∏_{ν∈S} |x|_{ν} ≥ 1.

To show (b), in view of (a) it suffices to note that

|λ_{i} − λ_{j}|_{ν} ≤ 2Λ(A)

for each 1 ≤ i < j ≤ n.

5 The Main Proposition

Motivation. In the sequel we would like given two matrices to produce words of bounded length whose entries satisfy certain conditions. Fix a valuation ν ∈ V_{K} and rescale the given matrices so that their norms are less than 1. Given N and ϵ, there always exists a subspace V = V (N, ϵ, ν) ⊂ M_{n}(K_{ν}) of minimal dimension such that every word of length at most N, is within ϵ of V. (It is possible that V = M_{n}(K_{ν})). Roughly, the assertion of the main proposition (see Proposition 5.1 below) is that with the appropriate choice of constants we can choose V to be an algebra (i.e. is closed under matrix multiplication). This implies strong restrictions on V, some of which we will discuss in §6.

The group T (A, ν). Let A = diag(λ_{1}, λ_{2}, …, λ_{n}) be a diagonal matrix, and let K′ ⊃ K be the field generated by the elements of A over K. We assume n! ≥ [K′ : K]. Let ν ∈ S be a valuation. Let T = T (A, ν) < SL_{n}(K′_{ν}) to be the subgroup of the diagonal defined by T = {diag(t_{1}, t_{2}, …, t_{n}) ∈ SL_{n}(K′_{ν}) : t_{i} = t_{j} whenever λ_{i} = λ_{j}}. Note that any element which commutes with A commutes with all of T as well. We remark that since there are only finitely many extension fields of degree at most n! of K_{ν} (cf. [Kob84] chapter III) there are only finitely many possibilities for T independent of the specific element A.

The T -blocks of B. Let W_{ij} be the eigenspaces for both right and left action of T on M_{n}(K′_{ν}), so that for C_{ij} ∈ W_{ij}, S^{k}C_{ij}S^{l} = λ_{i}^{k}λ_{j}^{l}C_{ij} for any S = diag(λ_{1}, ⋯, λ_{n}) in T. In particular, if T is the whole diagonal subgroup of SL_{n}, then each W_{ij} is spanned by the elementary matrix E_{ij}. As another example if T = {diag(t, t, t^{−2}) : t ∈ K′_{ν}} then

W_{11} = (\begin{matrix}∗ & ∗ & 0 \\ ∗ & ∗ & 0 \\ 0 & 0 & 0 \end{matrix}) W_{12} = (\begin{matrix}0 & 0 & ∗ \\ 0 & 0 & ∗ \\ 0 & 0 & 0 \end{matrix}) W_{21} = (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ ∗ & ∗ & 0 \end{matrix}) and W_{22} = (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & ∗ \end{matrix})

Note that by the choice of T, W_{ij} with respect to T is the same as those with respect to the single element A.

For a matrix B ∈ SL_{n}(K′_{ν}), define B_{ij} = pr_{W_{ij}}(B)/∥B∥_{ν}, where pr denotes orthogonal projection of M_{n}(K′_{ν}) onto W_{ij}. We call the B_{ij} the blocks of B with respect to the torus T. Observe that B_{ij}B_{st} = 0 unless j = s; hence any nonzero word in the T -blocks of B is of the form B_{i_{1}i_{2}}B_{i_{2}i_{3}} ⋯ B_{i_{r}i_{r+1}} for some 1 ≤ i_{1}, ⋯, i_{r+1} ≤ m (here m is equal to the number of different eigen-values of A and in particular m ≤ n). In the rest of this paper the notation B_{ij} always denotes the blocks of B with respect to some torus of the diagonal subgroup which will be specified whenever used. For an n × n matrix X, the notation X^{T} means its transpose as usual.

We can now state

Proposition 5.1 (Main Proposition). Let K′ ⊃ K be a field extension with [K′ : K] ≤ n!. Let A ∈ SL_{n}(K′) be a diagonal element which is conjugate to an element of SL_{n}(O_{K}(S)) and let T = T (A, ν). For each ν ∈ S, let B ∈ SL_{n}(K′_{ν}). For any ϵ > 0, there exists a subalgebra E_{ν}(ϵ) ⊂ M_{n}(K′_{ν}) normalized by T such that

(a) for any word w in the blocks of B (with respect to ν) of length at most 2^{2n^{2}},

d_{ν}(w, E_{ν}(ϵ)) < ϵ,

where d_{ν}(w, V) = inf_{v∈V} ∥w − v∥_{ν}.

(b) for any θ ∈ M_{n}(K′_{ν}), there exists a word W_{ν}(ϵ) in A and B of length at most 2^{2n^{2}} such that

|⟨θ, W_{ν}(ϵ)⟩|_{ν} ≥ c · Λ(A)^{−r_{1}} · ∥B∥_{ν} · ( sup_{X∈E_{ν}(ϵ)\\{0\}} \frac{|⟨θ, X⟩|_{ν}}{∥X∥_{ν}} − 2ϵ∥θ∥_{ν}) ,

where the inner product ⟨·, ·⟩ is given by ⟨X, Y ⟩ = Tr XY^{T}, r_{1} is a positive constant depending only on n, K and S, and c is a positive constant depending only on n, K, S and ϵ.

Remarks. If θ is almost orthogonal to E_{ν}(ϵ) the statement (b) is vacuous.

In the course of the proof we will first prove an alternative version of assertion (b), namely,

(b’) for any θ ∈ M_{n}(K′_{ν}), there exists a word W_{ν}(ϵ) in the blocks of B of length at most 2^{n^{2}+2} such that

|⟨θ, W_{ν}(ϵ)⟩|_{ν} ≥ c · Λ(A)^{−r_{1}} · ∥B∥_{ν} · ( sup_{X∈E_{ν}(ϵ)\\{0\}} \frac{|⟨θ, X⟩|_{ν}}{∥X∥_{ν}} − 2ϵ∥θ∥) ,

where r_{1} is a positive constant depending only on n, K and S, and c is a positive constant depending only on n, K, S and ϵ.

The assertion (b’) is essentially the statement that E_{ν}(ϵ) viewed as a subspace is of minimal dimension among all subspaces satisfying (a). Indeed, if there is an element v ∈ E_{ν}(ϵ) which is almost orthogonal to all the words in the blocks of B of length at most 2^{n^{2}+2}, then we can choose θ = v (and X = v), contradicting (b’).

The rest of this section consists of the proof of Proposition 5.1. The proof relies on a concept of an almost-algebra. Roughly, an almost-algebra is a subspace of M_{n}(K′_{ν}) which is “almost” closed under matrix multiplication. In §5.1 we make a precise definition and show that any almost-algebra is close to an algebra. In §5.2 we show how to obtain an almost-algebra which will lie close to the words generated by any given finite collection of elements (which in our case will be the blocks of B). This almost-algebra will then be close to an algebra V which will satisfy the conditions (a) and (b’) of Proposition 5.1. It will also be normalized by T, since all the blocks of B are normalized by T. Finally, in §5.3, we show how to get the condition (b) from (b’). This is done by a direct argument using the Vandermonde determinant.

5.1 Almost algebras

Let k be a local field (with char k = 0) endowed with an absolute value | · |. For A ∈ M_{n}(k), we set ∥A∥ = |⟨A, A⟩|^{1/2}, where the inner product ⟨·, ·⟩ was defined in Proposition 5.1. Since this norm is equivalent to the one defined in Section 2 (in fact they coincide when k is non-archimedean), we do not need to distinguish them for our purpose. Let d(A, B) = ∥A − B∥ denote the associated distance function on M_{n}(k). Considering the canonical projection π : M_{n}(k) − {0} → ℙ(M_{n}(k)), for subspaces V_{1} and V_{2} of M_{n}(k), we define d(V_{1}, V_{2}) to be the Hausdorff distance between π(V_{1} −{0}) and π(V_{2} − {0}).

For a subset Λ ⊂ GL_{n}(k), we say that a subspace V of M_{n}(k) is normalized by Λ if AV A^{−1} = V for all A ∈ Λ.

For ϵ > 0, we say that a subspace V of M_{n}(k) is an ϵ-almost subalgebra if

sup_{X,Y ∈V \\{0\}} \frac{d(XY, V)}{∥X∥ · ∥Y ∥} < ϵ,

where, as usual, the distance between a vector z and a subspace V is given as inf_{v∈V} ∥z − v∥.

Lemma 5.2. If there exists an orthonormal basis {A_{1}, …, A_{m}} of a subspace V ⊂ M_{n}(k) such that d(A_{i}A_{j}, V) < ϵ for all 1 ≤ i, j ≤ m, then V is an n^{4} · ϵ-almost subalgebra of M_{n}(k).

Proof. Consider arbitrary elements X, Y ∈ V. Then for some x_{i}, y_{i} ∈ k, we have X = ∑_{i=1}^{m} x_{i}A_{i} and Y = ∑_{i=1}^{m} y_{i}A_{i}. Let C_{ij} ∈ V such that d(A_{i}A_{j}, V) = d(A_{i}A_{j}, C_{ij}). Note that ∥XY −∑_{ij} x_{i}y_{j}C_{ij}∥ ≤ ∑_{1≤i,j≤m} |x_{i}y_{j}|·∥A_{i}A_{j} −C_{ij}∥ ≤ m^{2}∥X∥·∥Y ∥ϵ. Since m ≤ n^{2}, V is an n^{4} · ϵ-almost subalgebra.

Theorem 5.3 (Almost algebras are close to algebras). There exists an increasing function h : ℝ^{+} → ℝ^{+}, depending only on n, with h(ϵ) → 0 as ϵ → 0 such that for any ϵ-almost-subalgebra V ⊂ M_{n}(k) there exists a subalgebra E_{ϵ} ⊂ M_{n}(k) such that d(V, E_{ϵ}) < h(ϵ). Moreover if V is normalized by a subset T of SL_{n}(k), we may take E_{ϵ} to be normalized by T as well.

Proof. (This proof was suggested to us by G. Margulis.) For a subspace V of M_{n}(k), define η(V) = 1 if there is no subalgebra of M_{n}(k) of dimension same as that of V; otherwise set η(V) to be

inf{d(V, E_{0}) : E_{0} is a subalgebra of M_{n}(k) with dim E_{0} = dim V }.

For any ϵ > 0, define

h(ϵ) = sup{η(V) : V is an ϵ-almost-algebra in M_{n}(k)}.

Clearly h is an increasing function on ℝ^{+}. We only need to show that h(ϵ) → 0 as ϵ → 0. Suppose not. Then there exist δ > 0, a sequence ϵ_{n} → 0 and a sequence V_{n} of ϵ_{n}-almost-subalgebras such that for any n, η(V_{n}) > δ. But by the compactness of the Grassmannian variety of M_{n}(k), there is a subsequence of {V_{n}} which converges to V. It is then easy to see that V must be an algebra and hence η(V_{n}) → 0, which yields a contradiction. In the case when V is normalized by T , we modify the definition of η(V) so that we take the infimum only over those subalgebras which are normalized by T . Then it is easy to see that the resulting subalgebra V is also normalized by T .

5.2 Almost algebras generated by a finite set.

Lemma 5.4. Let T be a torus in SL_{n}(k), i.e., a commutative subgroup consisting of semisimple elements. Consider matrices B_{1}, …, B_{m} ∈ M_{n}(k) such that for each 1 ≤ i ≤ m, ∥B_{i}∥ ≤ 1 and AB_{i}A^{−1} is a scalar multiple of B_{i} for each A ∈ T. Then for any ϵ > 0, there exists a subalgebra E_{ϵ} ⊂ M_{n}(k) normalized by T such that

• for any word w in B_{1}, ⋯, B_{m} of length at most 2^{n^{2}+2},

d(w, E_{ϵ}) ≤ ϵ;

• for any θ ∈ M_{n}(k), there exists a word w in B_{1}, ⋯, B_{m} of length at most 2^{n^{2}+2} such that

|⟨θ, w⟩| ≥ c · ( sup_{X∈E_{ϵ}\\{0\}} \frac{|⟨θ, X⟩|}{∥X∥} − 2ϵ∥θ∥) ,  (5)

where c is a positive constant depending only on n and ϵ.

Proof. Let ϵ_{0} = ϵ. For each 0 ≤ r ≤ n^{2} + 1, let us choose constants ϵ_{r} > 0 as big as possible so that ϵ_{r+1} ≤ ϵϵ_{r}^{2n^{2}}/(3n^{4}2^{2n^{2}}), ϵ_{r+1} ≤ ϵϵ_{r}^{n^{2}}/(n^{2}2^{n^{2}+1}), and h(3n^{4}2^{2n^{2}}ϵ_{r}^{−2n^{2}}ϵ_{r+1}) ≤ ϵ_{r}/(3n^{2}). In the following proof, a word means a word in B_{1}, ⋯, B_{m}. For each 1 ≤ r ≤ n^{2} + 1, let

f(r) = inf{j ∈ ℕ| there exists a subspace V_{r} ⊂ M_{n}(k) of dimension j normalized by T and such that d(V_{r}, w) ≤ ϵ_{r} for any word w of length at most 2^{r}. } If f(1) = 0, then ∥B_{i}∥ < ϵ_{0} for each 1 ≤ i ≤ m, and hence it suffices to take E_{ϵ} = {0} to prove the claim. Suppose that f(1) ≥ 1. By construction, the function f is increasing, and is bounded by n^{2}. Hence there exists a minimal integer 1 ≤ r ≤ n^{2} +1 such that f(r) = f(r + 1). Fix a subspace V_{r+1} ⊂ M_{n}(k) of dimension f(r) such that d(V_{r+1}, w) ≤ ϵ_{r+1} for any word w of length at most 2^{r+1}.

Claim 5.5. The subspace V_{r+1} is an 3n^{4}2^{2n^{2}}ϵ_{r}^{−2n^{2}}ϵ_{r+1}-almost subalgebra of M_{n}(k) normalized by T, and for every θ ∈ M_{n}(k), there exists a word w of length at most 2^{r} such that

|⟨θ, w⟩| ≥ \frac{ϵϵ_{r}^{n^{2}}}{n^{2}2^{n^{2}+1}} · ( sup_{v∈V_{r+1}\\{0\}} \frac{|⟨θ, v⟩|}{∥v∥} − ϵ∥θ∥) .  (6)

Proof of claim. For a subspace W of M_{n}(k), the notation pr_{W} means the projection map of M_{n}(k) to W. For simplicity, let p = pr_{V_{r+1}}. By the definition of f, for any word w of length at most 2^{r+1}, we have

∥p(w) − w∥ < ϵ_{r+1}.

We now pick words w_{1}, … w_{f(r)} of length at most 2^{r} inductively as follows: w_{1} is a word of length at most 2^{r} of maximal norm, and for each 2 ≤ j ≤ f(r), denoting by W_{j−1} the subspace spanned by {w_{1}, …, w_{j−1}}, let w_{j} be a word such that the norm ∥ pr_{W_{j−1}^{⊥}}(w_{j})∥ is maximal among all words of length at most 2^{r}. Clearly each W_{j−1} is normalized by T.

Note that for each 1 ≤ j ≤ f(r), ∥ pr_{W_{j−1}^{⊥}}(w_{j})∥ > ϵ_{r}, since, otherwise, all the words of length at most 2^{r} would be within ϵ_{r}-distance to the subspace W_{j−1} where j − 1 = dim W_{j−1} < f(r), contradicting the definition of f. Let W′_{j} ⊂ V_{r+1} denote the subspace spanned by the projections p(w_{1}), ⋯, p(w_{j}).

Then

∥ pr_{(W′_{j−1})^{⊥}}(p(w_{j}))∥ = d(p(w_{j}), W′_{j−1})

≥ d(w_{j}, W′_{j−1}) − d(w_{j}, p(w_{j})) ≥ ϵ_{r} − ϵ_{r+1} ≥ \frac{ϵ_{r}}{2}

Hence the vectors p(w_{j}), 1 ≤ j ≤ f(r), form a basis for V_{r+1}, and the determinant of the matrix, say Q, whose rows are the vectors p(w_{j}) is at least ϵ_{r}^{n^{2}}/2^{n^{2}} (cf. Lemma 7.5). Thus if X = ∑_{j=1}^{f(r)} x_{j}p(w_{j}) for some x_{j} ∈ k, then

max_{j} |x_{j}| ≤ det(Q)^{−1}∥X∥ ≤ 2^{n^{2}}ϵ_{r}^{−n^{2}}∥X∥,  (7)

using ∥p(w_{j})∥ ≤ ∥w_{j}∥ ≤ 1 for each 1 ≤ j ≤ f(r). On the other hand,

d(w_{i}w_{j}, V_{r+1}) < ϵ_{r+1}; hence d(p(w_{i})p(w_{j}), V_{r+1}) < 3ϵ_{r+1}.

Thus for any X_{1} = ∑_{j} c_{1j}p(w_{j}) and X_{2} = ∑_{j} c_{2j}p(w_{j}) in V_{r+1} of unit norm, we have

d(X_{1}X_{2}, V_{r+1}) ≤ ∑_{1≤i,j≤f(r)} c_{1i}c_{2j}d(p(w_{i})p(w_{j}), V_{r+1})

≤ f(r)^{2}2^{2n^{2}}ϵ_{r}^{−2n^{2}}3ϵ_{r+1} ≤ 3n^{4}2^{2n^{2}}ϵ_{r}^{−2n^{2}}ϵ_{r+1}.

It follows that V_{r+1} is an 3n^{4}2^{2n^{2}}ϵ_{r}^{−2n^{2}}ϵ_{r+1}-almost-subalgebra of M_{n}(k).

Let θ̃ denote the orthogonal projection of θ to V_{r+1}. Then, since θ and θ̃ differ by an element of V_{r+1}^{⊥}, we have ⟨θ, v⟩ = ⟨θ̃, v⟩ for all v ∈ V_{r+1}. Hence

sup_{v∈V_{r+1}\\{0\}} \frac{|⟨θ, v⟩|}{∥v∥} = ∥θ̃∥.

If ∥θ̃∥ ≤ ϵ∥θ∥, then there is nothing to prove. Hence, we may assume that ∥θ̃∥ ≥ ϵ∥θ∥. We may write θ̃ = ∑ x_{j}p(w_{j}). Taking inner product with θ̃ we obtain,

∥θ̃∥^{2} = ∑ x_{j}⟨p(w_{j}), θ̃⟩.

Hence there is a j such that |x_{j}⟨p(w_{j}), θ̃⟩| ≥ \frac{1}{n^{2}} ∥θ̃∥^{2}. Then, in view of (7), we have

|⟨p(w_{j}), θ̃⟩| ≥ \frac{ϵ_{r}^{n^{2}}}{n^{2}2^{n^{2}}} ∥θ̃∥.

Hence

|⟨θ, w_{j}⟩| ≥ |⟨θ, p(w_{j})⟩| − |⟨θ, w_{j} − p(w_{j})⟩| ≥ \frac{ϵ_{r}^{n^{2}}}{n^{2}2^{n^{2}}} ∥θ̃∥ − ϵ_{r+1}∥θ∥

≥ \frac{ϵ_{r}^{n^{2}}}{n^{2}2^{n^{2}}} ∥θ̃∥ − \frac{ϵ_{r+1}}{ϵ} ∥θ̃∥ ≥ \frac{ϵ_{r}^{n^{2}}}{n^{2}2^{n^{2}+1}} ∥θ̃∥

where the last inequality is justified on the choice of ϵ_{r} made in the beginning of the proof.

This proves the claim.

Proof of Lemma 5.4. Note that by the choice of ϵ_{r}, ϵ ≤ 3n^{4}2^{2n^{2}}ϵ_{r}^{−2n^{2}}ϵ_{r+1}. Hence by Theorem 5.3, there exists an algebra E_{ϵ} such that

d(V_{r+1}, E_{ϵ}) < h(3n^{4}2^{2n^{2}}ϵ_{r}^{−2n^{2}}ϵ_{r+1}) < ϵ_{r}/(3n^{2}) ≤ ϵ.

Now, (5) follows from (6).

5.3 Proof of Proposition 5.1

Proposition 5.1 (a) and (b’) follow from Lemma 5.4. To complete the proof we need to show how to deduce (b) from (b’).

Fix ϵ > 0. Consider the subalgebra E_{ϵ} ⊂ M_{n}(K′_{ν}) and N_{ϵ} as in Lemma 5.4. Let θ ∈ M_{n}(k), as observed before we may assume that ∥θ̃∥ ≥ ϵ∥θ∥, where θ̃ denotes the orthogonal projection of θ into E_{ϵ}. (Otherwise (b) is vacuous).

Then for some 2 ≤ r ≤ 2^{n^{2}+2} + 1, there exists an r-tuple (i_{1}, ⋯, i_{r}) of positive integers with 1 ≤ i_{j} ≤ m for each 1 ≤ j ≤ r such that

|⟨θ, B_{i_{1}i_{2}}B_{i_{2}i_{3}} … B_{i_{r−1}i_{r}}⟩| ≥ c · sup_{X∈E_{ϵ}\\{0\}} \frac{|⟨θ, X⟩|_{ν}}{∥X∥_{ν}} .

Note that for any positive integers 0 ≤ k_{1}, ⋯, k_{r} ≤ m − 1,

Tr(θ^{T} A^{k_{1}}BA^{k_{2}}B … BA^{k_{r}}) = ∥B∥_{ν}^{r−1} · ∑_{I=(i_{1},...,i_{r})} λ_{i_{1}}^{k_{1}} … λ_{i_{r}}^{k_{r}} Tr(θ_{i_{r}i_{1}}^{T}B_{i_{1}i_{2}}B_{i_{2}i_{3}} … B_{i_{r−1}i_{r}})

(8)

where the sum is taken over all the r-tuples I = (i_{1}, ⋯, i_{r}) such that 1 ≤ i_{j} ≤ m for all 1 ≤ j ≤ r.

Let (θ^{T} B)_{I} denote Tr(θ_{i_{r}i_{1}}^{T}B_{i_{1}i_{2}}B_{i_{2}i_{3}} … B_{i_{r−1}i_{r}}), that is

(θ^{T} B)_{I} = ⟨θ, B_{i_{1}i_{2}}B_{i_{2}i_{3}} … B_{i_{r−1}i_{r}}⟩.

For each multi-index L = (l_{1}, ⋯, l_{r}) and I = (i_{1}, ⋯, i_{r}) where 0 ≤ l_{j} ≤ m − 1 and 1 ≤ i_{j} ≤ m for each 1 ≤ j ≤ r, let

D_{IL} = λ_{I}^{L} = λ_{i_{1}}^{l_{1}} … λ_{i_{m}}^{l_{m}}

and

C(L) = Tr θ^{T} A^{l_{1}}BA^{l_{2}}B … BA^{l_{m}}.

Thus (8) can be rewritten as

C(L) = ∥B∥_{ν}^{m−1} ∑_{I} D_{IL}(θ^{T} B)_{I}

If we set the m × m-matrix

X = (\begin{matrix}1 & 1 & … & 1 \\ λ_{1} & λ_{2} & … & λ_{m} \\ ⋮ & ⋮ & ... & ⋮ \\ λ_{1}^{m−1} & λ_{2}^{m−1} & … & λ_{m}^{m−1} \end{matrix})

then the m^{r} ×m^{r}-matrix D whose IL entry is D_{IL} = λ_{I}^{L} coincides with the Kronecker tensor product ⊗^{r}X. Since det X = ∏_{1≤i<j≤m}(λ_{i} − λ_{j}), det D = ∏_{1≤i<j≤n}(λ_{i} − λ_{j})^{rm^{r−1}}.

In view of Lemma 4.2, ∥D^{−1}∥_{ν} ≤ CΛ(A)^{M}, where C and M are positive constants depending only on n, m, L and S (note that the dependency on r is resolved to that on N, but N is again dependent only on n, m, L and S.)

Therefore

∥B∥_{ν}^{r−1} · max_{I} |(θ^{T} B)_{I}|_{ν} ≤ C · Λ(A)^{M} · max_{L} |C(L)|_{ν}.

Hence

max_{L} |C(L)|_{ν} ≥ ϵ · \frac{c}{C} · Λ(A)^{−M} · ∥B∥_{ν}^{r−1} · sup_{X∈E_{ϵ}\\{0\}} \frac{|⟨θ, X⟩|}{∥X∥},

where K ranges over the multi indices (l_{1}, ⋯, l_{r}) with 0 ≤ l_{j} ≤ m−1 for all 1 ≤ j ≤ r. Note that r − 1 ≥ 1, since r ≥ 2. Noting that C(L) = Tr(θ^{T} A^{l_{1}}BA^{l_{2}}B ⋯ BA^{l_{r}}) and that the word A^{l_{1}}BA^{l_{2}} ⋯ BA^{l_{r}} is of length less than m(2^{n^{2}+2} + 1) for any L, set E_{ν}(ϵ) = E_{ϵ}. Since m(2^{n^{2}+2} + 1) ≤ 2^{2n^{2}}, the claim is proved.

6 Algebras

In view of §5, we need a result on the subalgebras of M_{n}(k), where k is a local field. Denote by D the diagonal subgroup of SL_{n}(k). In this section, we fix a subtorus T of D.

We say that an algebra is unipotent if it is nilpotent and its exponentiation is a unipotent group. Note that if an algebra is not unipotent, then it contains an element of non-zero trace. On the other hand, for any unipotent algebra, there exists an element α ∈ SL_{n}(k) such that conjugation by α contracts each element in the algebra by a given factor. The following proposition is a quantitative version of the combination of these assertions.

Proposition 6.1. For any 0 < η < 1 there exist constants d_{1} > 0 and d_{2} > 0 (depending only on η and n) such that for any subalgebra E of M_{n}(k) normalized by T, one of the following holds:

(1) There exists X ∈ E with | Tr X| > d_{1}∥X∥.

(2) There exists g ∈ SL_{n}(k) in the centralizer of T with max(∥g∥, ∥g^{−1}∥) ≤ d_{2} such that for all X ∈ E, ∥gXg^{−1}∥ ≤ η∥X∥.

The rest of the section consists of the proof of Proposition 6.1.

Let E be a subalgebra of M_{n}(k) normalized by T and let m = dim E. Let G denote the Grassmanian of m-dimensional subspaces of M_{n}(k). Let R ⊂ G denote the subset consisting of subalgebras which are normalized by T. It is easy to see that R is closed in G. Denote by R^{u} the subset of R consisting of unipotent algebras. Then R^{u} is also a closed subset of G. Note that for a subalgebra E ∈ R, E belongs to R^{u} if and only if Tr X = 0 for all X ∈ E.

Lemma 6.2. Suppose δ > 0. Let E be a subalgebra of M_{n}(k) normalized by T. Then at least one of the following holds:

(a) For some constant d > 0 depending only on T and δ, there exists an element X ∈ E such that | Tr X| > d · ∥X∥.

(b) d(E, R^{u}) < δ.

Proof: Let F ⊂ R denote the complement of the open δ-neighborhood of R^{u} in R. Then F is a compact subset of G. Note that for each E_{0} ∈ F, there exists X ∈ E_{0} with | Tr X| > 0. Then, by compactness of F, there is a constant d > 0 depending on δ and on T such that

inf_{E_{0}∈F} sup_{X∈E_{0}\\{0\}} \frac{| Tr X|}{∥X∥} > d.

Lemma 6.3. For any unipotent subalgebra E_{0} of M_{n}(k) and a diagonal subalgebra T̃ normalizing E_{0}, there exists g ∈ SL_{n}(k) such that ∥g∥, ∥g^{−1}∥ ≤ 1, gE_{0}g^{−1} is contained in the upper triangular subalgebra and gT̃g^{−1} is contained in the diagonal subalgebra of M_{n}(k).

Proof: Let e_{1}, ⋯, e_{n} denote the standard basis in k^{n}. Let 0 = V_{0} ⊂ V_{1} ⊂ ⋯ ⊂ V_{r} = k^{n} be the flag associated with E_{0}. (I.e., E_{0}V_{i} ⊂ V_{i−1} with V_{−1} = 0). Let k^{n} = E_{1} ⊕⋯⊕E_{s} be the decomposition of k^{n} into the eigenspaces of T̃ corresponding to the distinct eigenvalues. Then since T̃ normalizes E_{0} we have

V_{i} = ⊕_{j=1}^{s}(V_{i} ∩ E_{j}) for each i.  (9)

For each 1 ≤ j ≤ s, consider the flag F_{j} in E_{j} given by

0 ⊂ E_{j} ∩ V_{1} ⊂ ⋯ ⊂ E_{j} ∩ V_{r} = E_{j}.

Let L_{j} be a flag in E_{j} of same type as F_{j} compatible with the basis E_{j} ∩ {e_{1}, …, e_{n}}. There exists an element h ∈ SL_{n}(k) such that ∥h∥ ≤ 1, ∥h^{−1}∥ ≤ 1, hE_{j} = E_{j} and hL_{j} = F_{j} for each j. Observe that by (9) the basis he_{1}, he_{2}, …, he_{n} is compatible with the flag 0 = V_{0} ⊂ V_{1} ⊂ ⋯ ⊂ V_{r} = k^{n}. I.e., there is a permutation matrix w such that the basis f_{1} = whe_{1}, f_{2} = whe_{2}, …, f_{n} = whe_{n} is such that for each 1 ≤ i ≤ r V_{i} = Span{f_{1}, f_{2}, …, f_{dim V_{i}}}. With respect to this basis E_{0} is upper triangular and T̃ is diagonal. The element g = wh satisfies the assertions.

Lemma 6.4. For any 0 < η_{1} < 1, there exists a constant d_{3} > 0 (depending only on n and η_{1}) such that for any unipotent algebra E_{0} normalized by T, there exists an element α ∈ SL_{n}(k) which commutes with T such that max(∥α∥, ∥α∥^{−1}) ≤ d_{3} and

∥αXα^{−1}∥ ≤ η_{1}∥X∥ for all X ∈ E_{0}.

Proof: Let T̃ denote the linear span of T over k. Since E_{0} is normalized by T̃, by the previous lemma, for some g ∈ SL_{n}(k) such that ∥g∥ ≤ 1, ∥g^{−1}∥ ≤ 1, gE_{0}g^{−1} is contained in the upper triangular subalgebra and gT g^{−1} ⊂ D. Now we can find an element β ∈ D which contracts each element in the strictly upper triangular subalgebra by the factor of η_{1}, and the norm of β is bounded by a constant depending only on n and η_{1}. Now for all X ∈ E_{0}, ∥g^{−1}βgXg^{−1}β^{−1}g∥ ≤ η_{1} · ∥X∥. Set α = g^{−1}βg. Since gT g^{−1} ⊂ D and D is commutative, g^{−1}Dg centralizes T. Since α ∈ g^{−1}Dg, we finish the proof.

Proof of Proposition 6.1. Let η_{1} = η/2, and let d_{3} be as in Lemma 6.4. Pick δ = η/(3d_{3}^{2}). Let d_{1} > 0 be such that Lemma 6.2 holds with d_{1} instead of d. Now suppose (1) of Proposition 6.1 does not hold. Then (b) of Lemma 6.2 holds, hence there exists a unipotent algebra E_{0} normalized by T such that d(E, E_{0}) < δ. Let α in the centralizer of T be as in Lemma 6.4. Now for any X ∈ E with ∥X∥ = 1, there exists X_{0} ∈ E_{0} with ∥X_{0}∥ = 1 and ∥X − X_{0}∥ ≤ δ. Then,

∥αXα^{−1}∥ ≤ ∥αX_{0}α^{−1}∥ + ∥α(X − X_{0})α^{−1}∥
≤ η_{1}∥X_{0}∥ + ∥α∥∥α∥^{−1}∥X − X_{0}∥
≤ η_{1} + d_{3}^{2}δ
< η.

Thus (2) of Proposition 6.1 holds.

7 Properties of SL_{n}(O_{K}(S))

In this section we prove some simple consequences of Lemma 4.2. We continue to use the same notation K, S, Λ(·) etc. as in §4.

7.1 A lower bound for the maximum eigenvalue of a semisimple element.

The aim of this subsection is to show:

Proposition 7.1. There exists an η > 0 depending only on n, K and S such that Λ(A) ≥ 1 + η for any semisimple element A ∈ SL_{n}(O_{K}(S)) of infinite order.

Set S_{∞} to be the subset of S consisting of all archimedean valuations in S.

Lemma 7.2. Let G = ∏_{ν∈S_{∞}} SL_{n}(K̄_{ν}). Then there exists an ϵ-neighborhood O of the identity in G such that if (h_{ν}Bh_{ν}^{−1})_{ν∈S_{∞}} ∈ O for some h_{ν} ∈ GL_{n}(K̄_{ν}) and the characteristic polynomial of B has coefficients in the set O_{K} of algebraic integers, then B is unipotent.

Proof: Clearly the map ϕ sending (g_{ν}) ∈ G to (f_{ν}(X)) for f_{ν} being the characteristic polynomial of g_{ν} is a continuous map from G to ∏_{ν} K̄_{ν}[X]. Note that the diagonal embedding of O_{K}[X] is discrete in ∏_{ν} K̄_{ν}[X]. Hence there exists a neighborhood V of ϕ(e) such that the only element of V intersecting the diagonal embedding of O_{K}[X] is ϕ(e). Noting that ϕ((g_{ν})) = ϕ(e) implies that each g_{ν} is unipotent, it suffices to set O to be ϕ^{−1}(V).

Lemma 7.3. For any δ > 0, and for any diagonal matrix diag(b_{1}e^{2πθ_{1}i}, ⋯, b_{n}e^{2πθ_{n}i}) ∈ SL_{n}(ℂ) where b_{l} are positive reals and 0 ≤ θ_{l} ≤ 1 for all 1 ≤ l ≤ n, there exists 1 ≤ d ≤ \frac{1}{δ^{2n}} such that for all 1 ≤ l ≤ n, dθ_{l} ≤ δ mod 2π.

Proof: Let R_{m} be the subdivision of [0, 1], identified with ℝ/ℤ, into m = \frac{1}{δ} subintervals of equal length δ. Consider the box [0, 1]^{n} × [0, 1]^{n} and R_{m} × R_{m}, which are m^{2n} subsets of size δ^{2n} in [0, 1]^{2n}. Letting θ = (θ_{1}, ⋯, θ_{n}), consider l ·θ for 1 ≤ l ≤ m^{2n+1}. Then by pigeon-hole principle, for some 1 ≤ l_{1} < l_{2} ≤ m^{2n+1}, l_{1} · θ and l_{2} · θ must be in the same box in R_{m} × R_{m}. Hence the size of (l_{2} − l_{1}) · θ is at most δ. Since 1 ≤ l_{2} − l_{1} ≤ m^{2n}, this proves the claim.

For each ν ∈ S, set Λ_{ν}(A) = max{|λ|_{ν} : λ : an eigenvalue of A}.

Proof of Proposition 7.1: Let ϵ be as in Lemma 7.2 and d be as in Lemma 7.3 with respect to \frac{ϵ}{4}. Let K′ ⊃ K be the splitting field of the characteristic polynomial of A. Since for each ν ∈ S_{∞}, K′_{ν} ⊂ ℂ and S_{∞} is finite, we may assume, after replacing A by a suitable power of A with a bounded exponent depending on d and |S_{∞}|, that the arguments of each eigenvalue of A is at most ϵ mod 2π. Note that since A is of infinite order, any power of A is non-trivial. Suppose that for some non-archimedean ν ∈ S, Λ_{ν}(A) > 1. Then in fact, Λ_{ν}(A) ≥ π^{1/n!} for π being the uniformizer of the field K_{ν}, since [K′_{ν} : K_{ν}] ≤ n!. Now suppose that Λ_{ν}(A) = 1 for all non-archimedean ν ∈ S. It follows that all eigenvalues of A are contained in the maximal compact ring O′_{ν} of K′_{ν}. Let f denote the characteristic polynomial of A. Since the coefficients of f are contained in K ∩ O′_{ν} ⊂ O_{ν} for all non-archimedean ν ∈ S, f in fact belongs to O_{K}[X]. By applying Lemma 7.2, we now have an archimedean valuation ν ∈ S and a constant ϵ > 0 depending only on n, S such that |λ − 1|_{ν} ≥ ϵ for some eigenvalue of A. Since the argument of λ is less than \frac{ϵ}{4}, it follows that |λ − 1|_{ν} ≥ 1 + η for some η depending on ϵ.

7.2 Effective Diagonalization

In this subsection, we prove the following:

Proposition 7.4. Fix ν ∈ S. Let K′_{ν} be a finite extension of K_{ν} and C_{ν} ∈ SL_{n}(K′_{ν}) be a semisimple element which is conjugate to some matrix C ∈ SL_{n}(O_{K}(S)) over GL_{n}(K′_{ν}). Then there exists a matrix X_{ν} whose columns consist of linearly independent unit eigenvectors of C_{ν} (so that X_{ν}^{−1}C_{ν}X_{ν} is diagonal) and

∥X_{ν}^{−1}∥_{ν} ≤ D_{1} · Λ(C)^{M_{1}} · ∥C_{ν}∥_{ν}^{M_{2}}

where D_{1}, M_{1} and M_{2} are positive constants depending only on n and S.

The proof relies on the following standard lemma:

Lemma 7.5. Let k be local field with an absolute value | · |. Let n ≥ 1 and v_{1}, ⋯, v_{n} be linearly independent unit vectors in k^{n}. For any c > 0 and 1 ≤ j ≤ n, consider the following conditions:

1. I(c) : | det(v_{1}, ⋯, v_{n})| ≥ c

2. II_{j}(c): for any 1 ≤ i ≤ j and any permutation σ on {1, ⋯, j},

∥ pr_{(V_{i+1}^{σ})}_{⊥}(v_{σ(i)})∥ ≥ c

where V_{i}^{σ} denotes the subspace spanned by v_{σ(i)}, ⋯, v_{σ(j)} for 1 ≤ i ≤ j and V_{j+1} = {0}.

3. III_{j}(c): for any a_{1}, ⋯, a_{j} ∈ k,

∥ ∑_{i=1}^{j} a_{i}v_{i}∥ ≥ c max_{1≤i≤j} |a_{i}|

Then we have I(c) ⇒ II_{n}(c), II_{j}(c) ⇒ III_{j}(c) and II_{n}(c) ⇒ I(c^{n}).

Proof: Note that det(v_{1}, ⋯, v_{n}) = ∏_{i=1}^{n} ∥ pr_{(V_{i+1}^{σ})}_{⊥}(v_{σ(i)})∥. Since ∥ pr_{(V_{i+1}^{σ})}_{⊥}(v_{σ(i)})∥ ≤ 1 for each 1 ≤ i ≤ n, we obtain that ∥ pr_{(V_{i+1}^{σ})}_{⊥}(v_{σ(i)})∥ ≥ c under assuming I(c). Now assume II_{j}(c). Let W_{i} denotes the subspace of k^{n} spanned by v_{1}, ⋯, v_{i−1}, v_{i+1}, ⋯, v_{j}. Note that for each 1 ≤ i ≤ j,

∥ ∑_{i=1}^{j} a_{i}v_{i}∥^{2} = ∥ pr_{W_{i}}(∑_{i=1}^{j} a_{i}v_{i})∥^{2} + ∥ pr_{W_{i}^{⊥}}(∑_{i=1}^{j} a_{i}v_{i})∥^{2} ≥ |a_{i}|^{2} · ∥ pr_{W_{i}^{⊥}}(v_{i})∥^{2}.

Since ∥ pr_{W_{i}^{⊥}}(v_{i})∥ ≥ c by II_{j}(c) and 1 ≤ i ≤ j is arbitrary, we have

∥ ∑_{i=1}^{j} a_{i}v_{i}∥ ≥ c · max_{1≤i≤j} |a_{i}|.

The implication II_{n}(c) ⇒ I(c^{n}) is clear.

Proof of Proposition 7.4. Let γ_{1}, ⋯, γ_{n} denote the eigenvalues of C_{ν}, and let v_{1}, …, v_{n} denote corresponding unit eigenvectors, so that C_{ν}v_{i} = γ_{i}v_{i}. We assume that if γ_{i} = γ_{j} then v_{i} and v_{j} are orthogonal. Let X_{ν} be a matrix whose columns consist of the v_{i}’s. Note that ∥X_{ν}^{−1}∥_{ν} ≤ \frac{M}{|det (X_{ν})|_{ν}} for some constant M depending only on n.

Then by Lemma 4.2, for each γ_{i} ≠ γ_{j},

|γ_{i} − γ_{j}|_{ν} ≥ d · Λ(C)^{−N}

for some bounded positive constants d and N. We may clearly assume that d ≤ 1. By Lemma 7.5, it suffices to show that

∥ pr_{(V_{i+1}^{I})}_{⊥}(v_{i})∥_{ν} ≥ (\frac{d}{2})^{n−i} · Λ(C)^{−(n−i)N}∥C_{ν}∥_{ν}^{−(n−i)} for each 1 ≤ i ≤ n

(here I denotes the identity permutation). We proceed by induction on i. For i = n, it is clear. Assume that for k + 1 ≤ i ≤ n,

∥ pr_{(V_{i+1}^{I})}_{⊥}(v_{i})∥_{ν} ≥ (\frac{d}{2})^{n−i} · Λ(C)^{−(n−i)N}∥C_{ν}∥_{ν}^{−(n−i)}

≥ (\frac{d}{2})^{n−k−1} · Λ(C)^{−(n−k−1)N}∥C_{ν}∥_{ν}^{−(n−k−1)}.

Hence by Lemma 7.5, for any x_{k+1}, ⋯, x_{n} ∈ K_{ν}, we have

∥( ∑_{i=k+1}^{n} x_{i}v_{i})∥_{ν} ≥ (\frac{d}{2})^{n−k−1} · Λ(C)^{−(n−k−1)N}∥C_{ν}∥_{ν}^{−(n−k−1)} max_{k+1≤i≤n} |x_{i}|_{ν}.

Write

v_{k} = pr_{(V_{k+1}^{I})}_{⊥}(v_{k}) + ∑_{i=k+1}^{n} a_{i}v_{i},  (10)

where a_{i} ∈ K_{ν}. Now by applying C_{ν} to both sides of (10) we obtain

∥C_{ν}∥_{ν} · ∥ pr_{(V_{k+1}^{I})}_{⊥}(v_{k})∥_{ν} ≥ ∥C_{ν} pr_{(V_{k+1}^{I})}_{⊥}(v_{k})∥_{ν}

= ∥γ_{k} pr_{(V_{k+1}^{I})}_{⊥}(v_{k}) + ∑_{k+1≤i≤n,γ_{i}≠γ_{k}} a_{i}(γ_{k} − γ_{i})v_{i}∥_{ν}

≥ ∥ ∑_{k+1≤i≤n,γ_{i}≠γ_{k}} a_{i}(γ_{k} − γ_{i})v_{i}∥_{ν}

≥ d · (\frac{d}{2})^{n−k−1} · Λ(C)^{−N}Λ(C)^{−(n−k−1)N}∥C_{ν}∥_{ν}^{−(n−k−1)} max_{k+1≤i≤n} |a_{i}|_{ν}.

On the other hand, from (10) we have

n · max_{1≤i≤n} |a_{i}|_{ν} ≥ 1 − ∥ pr_{(V_{k+1}^{I})}_{⊥}(v_{k})∥_{ν}.

Since d ≤ 1, Λ(C) ≥ 1 and ∥C_{ν}∥ ≥ 1, we have

1 + \frac{1}{n} · d · (\frac{d}{2})^{n−k−1} · Λ(C)^{−(n−k)N}∥C_{ν}∥_{ν}^{−(n−k−1)} ≤ 2.

We deduce that

∥ pr_{(V_{k+1}^{I})}_{⊥}(v_{k})∥_{ν} ≥ \frac{1}{2}d · (\frac{d}{2})^{n−k−1} · Λ(C)^{−(n−k)N}∥C_{ν}∥_{ν}^{−(n−k)}
= (\frac{d}{2})^{n−k} · Λ(C)^{−(n−k)N}∥C_{ν}∥_{ν}^{−(n−k)}.

This proves the claim.

8 The steps of the proof

Preliminary Reductions. Let Γ be an infinite finitely generated subgroup of GL_{n}(ℂ) which is not-virtually solvable. By Proposition 4.1 we may assume that Γ ⊂ SL_{n}(O_{K}(S)) where K is a number field, S is a set of valuations containing the archimedean ones, Γ is unbounded in ∏_{ν∈S} SL_{n}(K_{ν}) via the diagonal embedding and the Zariski closure H of Γ in GL_{n}(ℂ) is connected and simple.

Furthermore, in view of the Selberg Lemma [Sel60] we may assume that Γ is torsion free.

An element g ∈ H is called H-regular if the multiplicity of the eigenvalue 1 of Ad(g) is minimum possible in H where Ad denotes the adjoint representation of H.

It is well known that the set of all H-regular elements is a Zariski dense open subset in H and each H-regular element is semisimple and hence diagonalizable over GL_{n}(K′) for some finite extension field K′ of K (cf [Bo, 12.2]).

In the following, let S be an arbitrary finite generating set of Γ.

8.1 Step 1.

For each 1 ≤ i ≤ n − 1, ρ_{i} denotes the i-th wedge product representation of SL_{n} and set l_{i} = dim(ρ_{i}).

The following proposition will provide us with two elements of Γ denoted A and B. In Steps 2-4, will construct long words in A and B.

Proposition 8.1. For any N_{0} ∈ ℕ, there exists a bounded constant M_{1} such that B_{S}(M_{1}) contains H-regular elements A and B with the property that for each 1 ≤ i ≤ n − 1,

1. all words in ρ_{i}(A) and ρ_{i}(B) of length at most N_{0} are ρ_{i}(H)-regular.

2. no pair of the above elements lies in a common parabolic subgroup of SL_{l_{i}} not containing ρ_{i}(H) unless they, as words in a free group, commute.

Proof: Let Q_{i} be the subset of H × H consisting of the pairs (g_{1}, g_{2}) such that all words in ρ_{i}(g_{1}) and ρ_{i}(g_{2}) of length at most N_{0} are ρ_{i}(H)-regular and none of those two words lie in a common parabolic subgroup of SL_{l_{i}} not containing ρ_{i}(H) unless they, as words in a free group, commute. Since each Q_{i} contains a Zariski open subset in H × H, so does Q := ∩_{i=1}^{n−1}Q_{i}.

Since Γ × Γ is Zariski dense in H × H, by Proposition 3.2, there exists a bounded constant M_{1} such that B_{S×S}(M_{1}) ∩ Q ≠ ∅ for any finite generating set S of Γ. Hence B_{S}(M_{1}) contains A, B desired as above.

8.2 Step 2.

In the following sections, we let A, B be elements of Γ as in Proposition 8.1 for N_{0} = 2^{n^{2}+3}.

Our aim in this section is to prove the following proposition:

Proposition 8.2. For some positive bounded constants C_{1}, and r_{1} there exists a word B′ in A and B of length at most 2^{n^{2}+2} which involves B non-trivially, and for each ν ∈ S there exists x_{ν} ∈ SL_{n}(K′_{ν}) (where K′_{ν} is the splitting field of the characteristic polynomial of A) such that x_{ν}Ax_{ν}^{−1} is diagonal, and we have

Λ(B′) ≥ C_{1} · Λ(A)^{−r_{1}} max_{ν∈S} ∥x_{ν}Bx_{ν}^{−1}∥_{ν}.

Remarks. Note that since x_{ν}Ax_{ν}^{−1} is diagonal, ∥x_{ν}Ax_{ν}^{−1}∥ = Λ(A). Hence,

∥x_{ν}B′x_{ν}^{−1}∥_{ν} ≤ Λ(A)^{N_{1}}∥x_{ν}Bx_{ν}^{−1}∥_{ν}^{N_{1}}

for N_{1} = 2^{n^{2}+2}. Hence, the assertion of Proposition 8.2 is roughly that it is possible to replace B by a word B′ in A and B of bounded length such that after common conjugation A becomes diagonal, and B′ has the property that its biggest eigenvalue becomes comparable to the norm.

We now begin the proof of Proposition 8.2. We identify the Weyl group of SL_{n} with the set of permutation matrices.

There exists ĝ ∈ GL_{n}(K′) so that ĝAĝ^{−1} is diagonal. Fix any ν ∈ S. There exists an element g_{ν} ∈ GL_{n}(K′) such that the eigenvalues of the diagonal matrix g_{ν}Ag_{ν}^{−1} are non-increasing, i.e.,

g_{ν}Ag_{ν}^{−1} = diag(λ_{1}I_{n_{1}}, ⋯, λ_{m}I_{n_{m}})

where |λ_{1}|_{ν} ≥ ⋯ ≥ |λ_{m}|_{ν} and ∑_{i} n_{i} = n.

Set

A_{ν} := g_{ν}Ag_{ν}^{−1} and B̂_{ν} := g_{ν}Bg_{ν}^{−1}.

Let T_{ν} = T (A_{ν}, ν). Note that given Γ and ν there are only finitely many possibilities for T_{ν} independently of A and B. Hence any constant which a priori depends on T in fact depends only on Γ (i.e. is bounded in the sense of the introduction to §8).

Definition 8.3. Let A, B ∈ SL_{n}(K′_{ν}) with A diagonal. Let Z(T) ⊂ SL_{n}(K′_{ν}) denote the centralizer of T = T (A, ν). We say that B is balanced with respect to A if

∥B∥_{ν} ≤ 2 inf_{x∈Z(T)} ∥xBx^{−1}∥_{ν}.

Let h_{ν} ∈ Z(T) be such that h_{ν}B̂_{ν}h_{ν}^{−1} is balanced with respect to A_{ν}. Set

B_{ν} := h_{ν}B̂_{ν}h_{ν}^{−1}.

Note that A_{ν} = h_{ν}A_{ν}h_{ν}^{−1} and

Λ(A) = max{|λ_{i}|_{ν} | 1 ≤ i ≤ m, ν ∈ S} ≥ 1

since det A = 1.

Lemma 8.4. There exists a word B̃_{ν} in A_{ν} and B_{ν} of length at most 2^{n^{2}+2} (which involves B_{ν} non-trivially) such that

| Tr(B̃_{ν})|_{ν} ≥ C · ∥A_{ν}∥_{ν}^{−r_{1}}∥B_{ν}∥_{ν}  (11)

where C and r_{1} are bounded positive constants.

Proof: Fix 0 < η < 1/32. Let d_{1} and d_{2} be as in Proposition 6.1 with respect to η. Let 0 < ϵ < d_{1}/2 be such that d_{2}^{2} ϵ < 1/32 and ηϵ < 1/32. Let E_{ν}(ϵ) be a subalgebra of M_{n}(K′_{ν}) as in Proposition 5.1 with A and B replaced by A_{ν} and B_{ν} respectively.

We now claim that alternative (2) of Proposition 6.1 cannot hold for E = E_{ν}(ϵ). Indeed, let g be as in Proposition 6.1 (2). By assertion (a) of Proposition 5.1 there exists B^{∗} ∈ E_{ν}(ϵ) such that ∥B_{ν} − B^{∗}∥_{ν} ≤ ϵ∥B_{ν}∥_{ν}. Then

∥gB_{ν}g^{−1}∥_{ν} ≤ ∥gB^{∗}g^{−1}∥_{ν} + ∥g(B_{ν} − B^{∗})g^{−1}∥_{ν}
≤ η∥B^{∗}∥_{ν} + ∥g∥_{ν}∥g^{−1}∥_{ν}∥B_{ν} − B^{∗}∥_{ν}
≤ η∥B^{∗}∥_{ν} + d_{2}^{2}ϵ∥B_{ν}∥_{ν}
≤ η(1 + ϵ)∥B_{ν}∥_{ν} + d_{2}^{2}ϵ∥B_{ν}∥_{ν}
≤ (1/4)∥B_{ν}∥_{ν}

Since g centralizes A_{ν}, this contradicts the fact that B_{ν} is balanced with respect to A_{ν}. Therefore assertion (1) of Proposition 6.1 holds. Now we apply Proposition 5.1 with θ = I (the identity matrix). Since ϵ < d_{1}/2, (11) follows from part (b) of Proposition 5.1.

In this subsection we have constructed A_{ν} and B_{ν} in SL_{n}(K′_{ν}) for some finite extension field K′_{ν} of K_{ν} for each ν ∈ S such that [K′_{ν} : K_{ν}] is bounded by a constant depending only on n.

Let ν_{1} ∈ S be such that

∥B_{ν_{1}}∥_{ν_{1}} = max_{ν∈S} ∥B_{ν}∥_{ν}.

Let B̃ be as in Lemma 8.4 with respect to the valuation ν_{1}. By construction of B̃, clearly there exists B′ ∈ SL_{n}(O_{K}(S)) such that for each ν ∈ S,

B̃ = x_{ν}B′x_{ν}^{−1}  (12)

where x_{ν} = h_{ν}g_{ν}. Since Λ(B′) ≥ \frac{1}{n}| Tr(B̃_{ν_{1}})|_{ν_{1}}, we have completed the proof of Proposition 8.2.

8.3 Step 3

In this subsection, our goal is the following:

Proposition 8.5. There exist bounded constants m_{1}, c and M such that for any given finite generating set S of Γ ⊂ SL_{n}(O_{K}(S)) there exist two H-regular elements A, B ∈ B_{S}(m_{1}) not lying in a common parabolic, such that for each ν ∈ S, there exists a finite extension field K′_{ν} of K_{ν} and an element y_{ν} ∈ GL_{n}(K′_{ν}) such that each A_{ν} := y_{ν}Ay_{ν}^{−1} is diagonal and

Λ(A) = max_{ν∈S} ∥A_{ν}∥_{ν} ≥ c · max_{ν∈S} ∥B_{ν}∥_{ν}^{1/M}  (13)

Note that B′ is H-regular by Proposition 8.1. Set X_{ν} ∈ GL_{n}(K̄) to be a matrix whose columns are unit eigenvectors of B̃ satisfying

∥X_{ν}^{−1}∥_{ν} ≤ D · Λ(B′)^{M_{1}}∥B̃∥_{ν}^{M_{2}}

for each ν ∈ S as in Proposition 7.4.

Lemma 8.6. We have

max_{ν∈S} ∥A_{ν}∥_{ν} ≥ max_{ν∈S} ∥B_{ν}∥_{ν}^{1/M}, or

max_{ν∈S} ∥X_{ν}^{−1}B̃X_{ν}∥_{ν} ≥ D′ · max_{ν∈S} ∥X_{ν}^{−1}A_{ν}X_{ν}∥_{ν}^{1/M′}

where M, D′ and M′ are bounded constants.

Proof: Set N_{1} = 2^{n^{2}+2}. Let M be a positive integer bigger than r_{1} + 1 where r_{1} is as in Proposition 8.2. If Λ(A) ≥ ∥B_{ν_{1}}∥^{1/M}, then there is nothing to prove. Suppose that Λ(A) ≤ ∥B_{ν_{1}}∥^{1/M}. Consider X_{ν}^{−1}B̃X_{ν} and X_{ν}^{−1}A_{ν}X_{ν}. Note that

max_{ν∈S} ∥X_{ν}^{−1}B̃X_{ν}∥_{ν} = Λ(B′).

By applying Proposition 8.2 and by the assumption, we have

max_{ν∈S} ∥X_{ν}^{−1}B̃X_{ν}∥_{ν} ≥ C_{1} · Λ(A)^{−r_{1}}∥B_{ν_{1}}∥_{ν_{1}} ≥ C_{1} · ∥B_{ν_{1}}∥_{ν_{1}}^{−r_{1}/M+1}.

On the other hand, Proposition 7.4 with notations M_{1}, M_{2} and D_{1} there implies for each ν ∈ S,

max_{ν∈S} ∥X_{ν}^{−1}A_{ν}X_{ν}∥_{ν} ≤ max_{ν∈S} ∥X_{ν}^{−1}∥_{ν} · ∥A_{ν}∥_{ν} ≤ D_{1} · Λ(B′)^{M_{1}}∥B_{ν}∥_{ν}^{M_{2}}Λ(A)

≤ D_{1} · Λ(A)^{M_{1}N_{1}+1} · ∥B_{ν_{1}}∥_{ν_{1}}^{N_{1}M_{1}+M_{2}} ≤ D_{1} · C_{1}^{M_{1}} · ∥B_{ν_{1}}∥_{ν_{1}}^{(M_{1}N_{1}+1)/M+N_{1}M_{1}+M_{2}}

by the assumption. Since −r_{1}/M + 1 > 0, we can find bounded constants M′ and D′ such that

max_{ν∈S} ∥X_{ν}^{−1}B̃_{ν}X_{ν}∥_{ν} ≥ D′ · max_{ν∈S} ∥X_{ν}^{−1}A_{ν}X_{ν}∥_{ν}^{1/M′}.

Proof of Proposition 8.5. If the first inequality in Lemma 8.6 does not hold, we simply need to replace A_{ν} by X_{ν}^{−1}B_{ν}X_{ν} and B_{ν} by X_{ν}^{−1}A_{ν}X_{ν}.

8.4 Step 4.

In this subsection we aim to satisfy the remaining conditions of Proposition 2.5. Note that (L2) is already satisfied in view of Proposition 8.5. It remains to satisfy (L1) and (L3).

Let ν_{0} ∈ S be such that ∥A_{ν_{0}}∥_{ν_{0}} = max_{ν∈S} ∥A_{ν}∥_{ν}, which is equal to Λ(A).

Using Proposition 7.1 (note that Γ is assumed to be torsion-free), we may assume that ∥A_{ν_{0}}∥_{ν_{0}} ≥ 4^{n−1}, after taking a suitable power by a bounded exponent. By conjugating Γ by a Weyl element, we may also assume that the diagonal entries of A_{ν_{0}} are in decreasing order with respect to the absolute value | · |_{ν_{0}}. For the sake of simplicity, we omit the subscript ν_{0} in the notation | · |_{ν_{0}} for the rest of this section.

We now need the following easy lemma:

Lemma 8.7. For any diag(α_{1}, ⋯, α_{n}) ∈ SL_{n}(K′_{ν_{0}}) where |α_{i}| ≥ |α_{i+1}| for each 1 ≤ i ≤ n − 1, we have

(max_{i} \frac{|α_{i}|}{|α_{i+1}|}) ≥ \frac{1}{2}|α_{1}|^{1/(n−1)}.

Proof: Suppose that |α_{i}| ≤ \frac{1}{2}|α_{1}|^{1/(n−1)}|α_{i+1}| for each 1 ≤ i ≤ n − 1. It follows that, using ∏_{i} |α_{i}| = 1, |α_{1}| ∏_{1≤i≤n−1} |α_{i}| ≤ \frac{1}{2^{n−1}} |α_{1}|. Hence ∏_{1≤i≤n−1} |α_{i}| ≤ \frac{1}{2^{n−1}} , or equivalently |α_{n}| ≥ 2^{n−1}, which contradicts the assumption that α_{i} is in norm decreasing order.

Write A_{ν_{0}} := diag(λ_{1}, ⋯, λ_{n}). Let 1 ≤ i ≤ n − 1 be the smallest integer such that

|\frac{λ_{i}}{λ_{i+1}} | ≥ \frac{1}{2}|λ_{1}|^{1/(n−1)} ≥ 2.

By taking the i-th wedge product of ρ_{i}, we obtain that a bounded power of ρ_{i}(A_{ν_{0}}) and ρ_{i}(B_{ν_{0}}) satisfies (L1). Without loss of generality, we may assume that ρ_{i}(A_{ν_{0}}) satisfies (L1). Note that the elements ρ_{i}(A_{ν_{0}}) and ρ_{i}(B_{ν_{0}}) satisfies (L2) by (13) and the choice of ν_{0} and i.

Proposition 8.8. Let k be a local field with an absolute value | · |. Then for any matrix D in SL_{m}(k), the (1, 1)-entry (D^{q})_{11} of the power D^{q} for some 1 ≤ q ≤ m satisfies

|(D^{q})_{11}| ≥ c∥D^{q}∥^{s}

for some constants s > −∞ and c > 0 depending only on n.

Assuming Proposition 8.8, we have ρ_{i}(B̂_{ν_{0}}) and ρ_{i}(A_{ν_{0}}) satisfies (L3). Indeed it is easy to see that they also satisfy (L1) and (L2) from the fact that A_{ν_{0}} and B_{ν_{0}} satisfy those. Hence we produced a ping-pong pair using words of bounded length in the given set of generators. This completes the proof of the main theorem.

Proof of Proposition 8.8. Let χ_{D}(x) = ∑_{i=0}^{m} α_{i}x^{i} be the characteristic polynomial of D. Note that α_{0} = 1. We then have χ_{D}(D) = 0. Hence if we write D^{q} = ((D^{q})_{ij}), then ∑_{i=0}^{m} α_{i}(D^{i})_{11} = 0 and hence ∑_{i=1}^{m} α_{i}(D^{i})_{11} = −1. Hence for some 1 ≤ q ≤ m,

|α_{q}(D^{q})_{11}| ≥ 1/m

which implies that |(D^{q})_{11}| ≥ \frac{1}{m}∥D∥^{−q}. This proves the proposition.

References

[AN] Roger Alperin and Gennady A. Noskov, Uniform growth, actions on trees and GL_{2}, math.GR/0105083.

[Bo] Armand Borel, Linear algebraic groups, 2nd ed. math. Springer-Verlag

[Dan94] Vladimir I. Danilov, Algebraic varieties and schemes, Algebraic geometry, I, Springer, Berlin, 1994, pp. 167–297. MR 95f:14001

[Del96] Thomas Delzant, Sous-groupes distingués et quotients des groupes hyperboliques, Duke Math. J. 83 (1996), no. 3, 661–682. MR 97d:20041

[DeLaH00] Pierre de la Harpe, Topics in Geometric Group Theory, Chicago Lec. Math., 2000

[EMO] Alex Eskin, Shahar Mozes, and Hee Oh, Uniform exponential growth of Linear Groups, IMRN 31 (2002) 1675-1683.

[Ful98] William Fulton, Intersection theory, second ed., Springer-Verlag, Berlin, 1998. MR 99d:14003

[GdlH97] Rostislav I. Grigorchuk and Pierre de la Harpe, On problems related to growth, entropy, and spectrum in group theory, J. Dynam. Control Systems 3 (1997), no. 1, 51–89. MR 98d:20039

[Gro81] Mikhael Gromov, Structures métriques pour les variétés riemanniennes, CEDIC, Paris, 1981, Edited by J. Lafontaine and P. Pansu. MR 85e:53051

[GS79] Firtz Grunewald and Daniel Segal, Remarks on injective specializations, J. Algebra 61 (1979), 538–547.

[Kob84] Neal Koblitz p-adic Numbers, p-adic Analysis and Zeta Functions, GTM 58, Springer-Verlag New York (1984).

[Kou98] Malik Koubi, Croissance uniforme dans les groupes hyperboliques, Ann. Inst. Fourier (Grenoble) 48 (1998), no. 5, 1441–1453. MR 99m:20080

[LM91] Alexander Lubotzky and Avinoam Mann, On groups of polynomial subgroup growth, Invent. Math. 104 (1991), no. 3, 521–533. MR 92d:20038

[Ma79] Anthony Manning, Topological entropy for geodesic flows, Ann. Math. 110 (1979), 567–573.

[Mil68] John Milnor, Growth of finitely generated solvable groups, J. Differential Geometry 2 (1968), 447–449. MR 39 #6212

[Osi03] Dennis Osin, The entropy of solvable groups, Ergodic Theory and Dynamical Systems 23 (2003), 907–918.

[ShaWa92] Peter Shalen and Philip Wagreich, Growth rates, ℤ_{p}-homology, and volumes of hyperbolic 3-manifolds, Trans. Amer. Math. Soc. 331 (1992), 895– 917.

[Sch00] Andrzej Schinzel, Polynomials with special regard to reducibility, Cambridge University Press, Cambridge, 2000, With an appendix by Umberto Zannier.

[Sel60] Atle Selberg, On discontinuous groups in higher-dimensional symmetric spaces, Contributions to function theory (internat. Colloq. Function Theory, Bombay, 1960) pp. 147–164, Tata Institute of Fundamental Research, Bombay.

[Tit72] Jacques Tits, Free subgroups in linear groups, J. Algebra 20 (1972), 250– 270. MR 44 #4105

[Wil00] John Wilson, Preprint, 2000.

[Wil02] John Wilson, On exponential growth and uniformly exponential growth for groups, Inventiones. 155, (2004), 287–303

[Wol68] Joseph A. Wolf, Growth of finitely generated solvable groups and curvature of Riemanniann manifolds, J. Differential Geometry 2 (1968), 421–446. MR 40 #1939

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 Institute for Advanced Study, Einstein Drive, Princeton, NJ, USA Current address: Mathematicc 253-37, Caltech, Pasadena, CA 91125; heeoh@its.caltech.edu