CHEEGER CONSTANT AND ALGEBRAIC ENTROPY OF LINEAR GROUPS

EMMANUEL BREUILLARD AND TSACHIK GELANDER

Abstract. We prove a uniform version of the Tits alternative. As a consequence, we obtain uniform lower bounds for the Cheeger constant of Cayley graphs of finitely generated non virtually solvable linear groups in arbitrary characteristic. Also we show that the algebraic entropy of discrete subgroups of a given Lie group is uniformly bounded away from zero.

In this note, we summarize some results whose full proofs will appear in [5].

1. Free subgroups in linear groups

Let K be an arbitrary field and Γ a subgroup of GL_{d}(K) generated by a finite subset Σ. Assume Σ is symmetric (i.e. s ∈ Σ ⇒ s^{−1} ∈ Σ), contains the identity e, and let G = G(Γ, Σ) be the associated Cayley graph. The set Σ^{n} is the set of all products of at most n elements from Σ, i.e. the ball of radius n centered at the identity in G. We introduce the following definition:

Definition 1.1. Two elements in a group are said to be independent if they generate a non-commutative free subgroup. The independence diameter of a Cayley graph G(Γ, Σ) is the quantity d_{Γ}(Σ) = inf{n ∈ ℕ : Σ^{n} contains two independent elements }. Similarly, we define the independence diameter of the group Γ to be d_{Γ} = sup{d_{Γ}(Σ) : Σ finite symmetric generating set with e ∈ Σ}.

The Tits alternative [11] asserts that either Γ is virtually solvable (i.e. contains a solvable subgroup of finite index) or Γ contains two independent elements, i.e. d_{Γ}(Σ) < +∞ for every generating set Σ. The two events are mutually exclusive. Tits’ proof provides no estimate as to how close to the identity in G the independent elements may be found. We obtain:

Theorem 1.1. (Uniform Tits alternative) Let Γ be a finitely generated subgroup of GL_{n}(K). Assume that Γ is not virtually solvable. Then d_{Γ} < +∞.

This result improves a theorem of A. Eskin, S. Mozes and H. Oh who proved in [7] the analogous statement when free subgroup is replaced by free semigroup. Although only linear groups in characteristic zero where considered in [7], our proof of Theorem 1.1 treats the general case. This relies on a general version of the Eskin-Mozes-Oh theorem which we proved together with Alireza Salehi-Golsefidy and will appear in [6]. As an important corollary and original motivation to their main result, the authors of [7] obtained that finitely generated linear groups in characteristic zero either are virtually nilpotent or have uniform exponential growth. Theorem 1.1 has a similar corollary which implies not just uniform exponential growth but a uniform estimate on the Cheeger constant of the Cayley graph. Before stating it, we recall the following definitions:

1991 Mathematics Subject Classification. Primary 05C38, 15A15; Secondary 05A15, 15A18.

Key words and phrases. Linear groups, growth, free subgroups.

Definition 1.2. For a group Γ generated by a finite symmetric set Σ, we define its uniform ℓ^{2}-Kazhdan constant κ_{Γ}(Σ) to be the largest ε ≥ 0 such that

max_{s∈Σ} ∥s · f − f∥_{2} ≥ ε · ∥f∥_{2}

for all f ∈ ℓ^{2}(Γ). Similarly, we let κ_{Γ} = inf{κ_{Γ}(Σ) : Σ is a finite symmetric generating set}.

It is easy to see that κ_{F_{k}} > 0 for the free group F_{k} (e.g. see [10]). Another related quantity is the uniform Cheeger constant defined as follows:

Definition 1.3. For a group Γ generated by a finite symmetric set Σ, the Cheeger constant of the Cayley graph G(Γ, Σ) is defined by

h_{Γ}(Σ) = inf\{\frac{#∂A}{#A} : A ⊆ G(Γ, Σ)\}

where ∂A = A\ ∩_{s∈Σ} sA is the inner boundary of a subset A. And the uniform Cheeger constant of the group Γ is defined by h_{Γ} = inf{h_{Γ}(Σ) : Σ is a finite symmetric generating set}.

The above quantities are easily seen to satisfy the following relations:

\sqrt{8 · h_{Γ}} ≥ \sqrt{2} · κ_{Γ} ≥ \frac{κ_{F_{2}}}{d_{Γ}} .

In [1] (see also [10]), a finitely generated group is called uniformly nonamenable if h_{Γ} > 0. We thus have:

Corollary 1.2. Let Γ be a finitely generated subgroup of GL_{n}(K). Assume Γ is not amenable. Then κ_{Γ} > 0 and Γ is uniformly non-amenable.

One should compare this result to [8], where it is shown that many arithmetic groups do not have a uniform lower bound for the Kazhdan constant with respect to an arbitrary unitary representation.

Corollary 1.3. Under the same assumptions on Γ, there is a constant ε = ε(Γ) > 0 such that if Σ is a finite symmetric generating subset of Γ, then

#Σ^{n} ≥ #Σ · (1 + ε)^{n}

for all positive integers n.

As in Eskin, Mozes and Oh’s original proof, the proof of Theorem 1.1 makes use of the theory of arithmetic groups. However, when proving Theorem 1.1, we first obtain along the way a clear and short proof of the result of Eskin, Mozes and Oh which is very geometric in nature and does not use arithmetic groups (see Section 3.1 below). Arithmeticity is really required when one wants to find a free group instead of just a free semi-group because it is then crucial to obtain elements of Γ that play ping-pong with good “separation properties”. Several new ingredients are needed in the proof of Theorem 1.1 such as the Borel–Harish-Chandra theorem, the argument behind Kazhdan–Margulis theorem and some facts from the geometry of symmetric spaces and Bruhat-Tits buildings. We shall outline some of these arguments in Section 3.

The general case reduces to the arithmetic one by the following:

Lemma 1.4. For any finitely generated non-virtually solvable linear group Γ there is a global field 𝕂, a finite set of valuations S of 𝕂, a simple 𝕂 algebraic group 𝔾, and a homomorphism f : Γ → 𝔾(𝕂) whose image is Zariski dense and lies in 𝔾(O_{𝕂}(S)).

Note that f is not injective in general. Here O_{𝕂}(S) is the ring of S-integers in the number field 𝕂, and 𝔾(O_{𝕂}(S)) is the set of elements in 𝔾(𝕂) whose matrix elements lie in O_{𝕂}(S) under some fixed faithful 𝕂-representation of 𝔾 in 𝕊𝕃_{n}.

For arithmetic groups we obtain the following stronger result:

Theorem 1.5. Let 𝕂 be a number field, S a finite set of places of 𝕂 containing all Archimedean ones, and let 𝔾 be a simple 𝕂-algebraic group. Then there exists a constant m = m(𝕂, S, 𝔾) ≥ 1 with the following property. For any symmetric set Σ in 𝔾(O_{𝕂}(S)) with e ∈ Σ, which generates a Zariski dense subgroup Γ of 𝔾, d_{Γ}(Σ) ≤ m.

Finally, let us also remark that the main result of [3], i.e. the connected case of the topological Tits alternative, can be deduced easily from 1.5.

2. Algebraic entropy and discrete subgroups

If Γ is a group, let C be the set of all finite (not necessarily symmetric) subsets Σ containing e and generating Γ.

Definition 2.1. Two elements in a group are said to be positively independent if they generate a free semigroup. The diameter of positive independence of set Σ containing e is the quantity d^{pi}(Σ) = inf{n ∈ ℕ : Σ^{n} contains two positively independent elements}. Similarly, the diameter of positive independence of the group Γ is defined by d_{Γ}^{pi} = sup{d^{pi}(Σ) : Σ ∈ C}.

The next definition is more standard:

Definition 2.2. Assume Γ is finitely generated. For Σ in C we can define the algebraic entropy of the pair (Γ, Σ) to be the quantity S_{Γ}(Σ) = lim \frac{1}{n} log(#Σ^{n}). Similarly, the algebraic entropy of Γ is defined by S_{Γ} = inf_{Σ∈C} S_{Γ}(Σ).

It is easy to see that S_{Γ}(Σ) is either positive for all Σ in C or 0 for all Σ simultaneously. Accordingly, the group Γ is said to have exponential or sub-exponential growth. If S_{Γ} > 0, then Γ is said to have uniform exponential growth. It is a consequence of Tits’ proof of the Tits alternative and some additional simple argument for solvable groups that for a linear group Γ ≤ GL_{n}(K) generated by a finite set Σ, either d^{pi}(Σ) < +∞ (and Γ has exponential growth) or Γ is virtually nilpotent, hence d^{pi}(Σ) = +∞ and Γ actually has polynomial growth. The latter quantities are related by the following inequality:

S_{Γ} ≥ \frac{log 2}{d_{Γ}^{pi}}

A. Eskin, S. Mozes and H. Oh proved in [7] that if Γ ≤ GL_{n}(K) is finitely generated non-virtually nilpotent then d_{Γ}^{pi} < ∞, hence S_{Γ} > 0. In general, the constant d_{Γ}^{pi} depends strongly on Γ (see the paragraph concluding this section) however, for discrete subgroups of Lie groups, as well as for nonrelatively compact subgroups over non-Archimedean local fields we have the following uniform result. Note further that Σ is not assumed to be symmetric in the following statement:

Theorem 2.1. For every integer d ≥ 1, there is a constant m = m(d) ≥ 1 with the following property. Let k be a local field and Σ ⊂ GL_{d}(k) a subset which generates a non-virtually nilpotent group. Assume further that either:

• the group ⟨Σ⟩ is discrete, or

• the field k is non-Archimedean and ⟨Σ⟩ is not relatively compact. Then d^{pi}(Σ) ≤ m(d).

This implies:

Corollary 2.2. (Entropy Gap for Discrete Subgroups) For any integer d ≥ 1, there is a constant s = s(d) > 0 such that

S_{Γ} > s

for all non-virtually nilpotent finitely generated discrete subgroups Γ of GL_{d}(ℝ)× GL_{d}(k_{1}) × ... × GL_{d}(k_{n}) for any n ≥ 0 and any non-archimedean local fields k_{1}, ..., k_{n}.

We also prove the following uniform statement for linear groups over general fields:

Theorem 2.3. For any n there is m = m(n) ≥ 1, such that if d ≤ n and 𝕂 is an algebraic extension of degree [𝕂 : 𝔽] ≤ n over a purely transcendental extension 𝔽 of the prime field 𝕂_{0}, and Σ ⊂ GL_{d}(𝕂) generates a non-virtually nilpotent group, then d^{pi}(Σ) ≤ m.

The restrictions on [K : F] and on the dimension d are really necessary. In fact, even for d = 2, it is possible to find a sequence Σ_{n} of finite symmetric sets in SL_{2}(\overline{ℚ}) such that each Σ_{n} generates a non virtually nilpotent group, although no pair of elements in Σ_{n}^{n} generates a free semigroup (see [2]). Similarly, R. Grigorchuk and P. de la Harpe have exhibited in [9] a sequence of finitely generated non-virtually solvable subgroups Γ_{n} in SL_{k_{n}}(ℤ) such that lim inf S_{Γ_{n}} = 0 and k_{n} → +∞.

3. Proofs

In this section we sketch the proofs of the above results. Let k be a local field.

3.1. Proximal elements. Like in Tits’ original proof of his alternative, one basic ingredient in all the results above is the so-called ping-pong lemma. This ensures that if two projective transformations a and b are in a suitable geometric configuration when acting on the projective space ℙ(k^{d}), then a and b generate a free semigroup, or a free group. To describe this geometric configuration, we need the following definition:

Definition 3.1. An element g ∈ P GL_{d}(k) is called ε-contracting, for some ε > 0, if there exists a projective hyperplane H, called a repelling hyperplane, and a projective point v called an attracting point such that d(gp, v) ≤ ε whenever p ∈ ℙ(k^{d}) satisfies d(p, H) ≥ ε. Moreover g is called (r, ε)- proximal, for r > 2ε, if it is ε-contracting for some H and v with d(H, v) ≥ r. Finally, g is called ε-very contracting (resp. (ε, r)-very proximal) if both g and g^{−1} are ε-contracting (resp. (r, ε)-proximal).

The distance d([x], [y]) on ℙ(k^{d}) is the standard distance d([x], [y]) = \frac{∥x∧y∥}{∥x∥∥y∥} where ∥·∥ is a Euclidean norm on k^{n} if k is ℝ or ℂ and the supermum norm if k is non-Archimedean. We refer the reader to [3] for elementary properties of such projective transformations. We then have:

Lemma 3.1. (The ping-pong lemma) Assume that a and b are (r, ε)-very proximal transformations, for some r > 2ε, and the attracting points of a and a^{−1} (resp. b and b^{−1}) are at least r apart from the repelling hyperplanes of b and b^{−1} (resp. a and a^{−1}), then a and b generate a free group.

Such elements a and b will be called ping-pong players. Observe that the conditions imposed on a and b imply that the attracting points of a and b must be at least r − 2ε apart. This separation property is a crucial difficulty encountered when trying to find generators of a free group as opposed to generators of a mere free semigroup. Indeed, if one only needs a free semigroup, then no condition on the distance between the two attracting points is necessary as the following version of the ping-pong lemma for semigroups show:

Lemma 3.2. (The ping lemma) Assume ε ≤ \frac{1}{3} and r > 4ε^{2}. Let a be an (r, ε^{3})-proximal transformation with attracting fixed point v and repelling hyperplane H. Let b be a projective transformation such that bv ≠ v, d(bv, H) ≥ ε and such that the global Lipschitz constant of b on ℙ(k^{d}) satisfies Lip(b) ≤ \frac{1}{ε}. Then a and ba generate a free semigroup.

To exhibit ε-contracting elements, it is useful to look at the Cartan decomposition of SL_{d}(k) since the ratio between the highest and second to highest component in the diagonal part of the decomposition determines the contraction properties of the transformation g on ℙ(k^{d}) (see [3]). When g is a diagonal matrix, then this ratio coincides with the ratio between the highest eigenvalue of g to the second highest, and the attracting point of g will be the direction of the highest eigenvector. This situation prevails when g is only assumed to be quasi-diagonal, meaning that the size of its operator norm is comparable to its highest eigenvalue. This is the ideal situation, because the attracting points of g being eigendirections, we have control upon them. In general, elements in a generating set Σ need not be simultaneously quasi-diagonal, however the following crucial proposition says that up to conjugating Σ and looking at a bounded power Σ^{d^{2}} it is possible to bound the norm of elements in Σ by the maximal eigenvalue.

For y ∈ SL_{d}(k), let Λ_{k}(y) = max{|λ|_{k} : λ is an eigenvalue of y}^{1}. For a bounded set Ω in SL_{d}(k), let Λ_{k}(Ω) = sup{Λ_{k}(y), y ∈ Ω} and

E_{k}(Ω) = inf_{h∈SL_{d}(k)}{∥hΩh^{−1}∥}

where ∥Ω∥ := sup_{y∈Ω} ∥y∥ and ∥ ∥ is the operator norm. The quantity E_{k}(Ω) is comparable (up to bounded powers) with the minimal exponential displacement of the set Ω acting on the symmetric space or building associated to SL_{d}(k). Clearly Λ_{k}(Ω) ≤ E_{k}(Ω).

Proposition 3.3. There is a constant c = c(d) > 0 such that for any compact subset Ω in SL_{d}(k) with e ∈ Ω we have

(3.1)  Λ_{k}(Ω^{d^{2}}) ≥ c · E_{k}(Ω)

Furthermore, if k is not Archimedean, the same holds with c = 1.

Proposition 3.3 is a strong version of Proposition 8.5 of [7], while its proof is significantly simpler and shorter.

3.2. Generation of free semigroups and a proof of the Eskin-Mozes-Oh theorem. The above Proposition is the main step towards producing a proximal element in Σ^{d^{2}}. Its proof is a rather simple contrapositive argument. Together with some elementary properties of projective transformations as studied in [3], it is essentially enough to prove the result of [7], namely that d_{Γ}^{pi} < +∞ for all non virtually solvable finitely generated linear groups Γ, hence also uniform exponential growth for such Γ’s. The pingpong pair is obtained as follows.

1the eigenvalue λ may not be in k but in a finite extension of it, however the absolute value on k extends uniquely to any algebraic extension, thus the notion |λ|_{k} is meaningful

Taking the Zariski closure and after moding out by the solvable radical, we can assume that the group Γ generated by Σ is Zariski dense in some semisimple algebraic group lying in SL_{d}. By Selberg’s lemma we can assume that Γ is torsion free. Using Lemma 3.4 below, we see that, up to taking a bounded power of Σ, we may assume that Σ contains a non trivial semisimple element. Then at least one eigenvalue of this element is not a root of unity, hence there exists a local field k such that Γ ≤ SL_{d}(k) and Λ_{k}(Σ) > 1 + δ where δ > 0 depends only on Γ. Let α ∈ Σ^{d^{2}} be such that Λ_{k}(α) = Λ_{k}(Σ^{d^{2}}). By Proposition 3.3, one can conjugate Σ inside SL_{d}(k) so that Λ_{k}(α) ≥ c · ∥Σ∥ . Up to considering a suitable wedge power representation V_{i} = Λ^{i}k^{d}, we may assume that Λ_{k}(A)/λ_{k}(A) ≥ Λ_{k}(A)^{1/d^{2}} where λ_{k}(A) is the maximum modulus of the second highest eigenvalue and A = Λ^{i}(α).

After this operation we have ∥Σ∥ ≤ (\frac{Λ_{k}(A)}{c})^{d} . Applying Lemma 3.5 below we can conjugate further Σ in SL(V_{i}) and get that for all n large enough (so that (1+δ)^{n/2d^{2}} > 3 say), A^{n} is a (1, 1/Λ_{k}(A)^{n/2d^{2}})-proximal transformation with attracting fixed point v and repelling hyperplane H and is such that

Λ_{k}(A) = ∥A∥ , while ∥Σ∥ ≤ (\frac{3Λ_{k}(A)}{c})^{3d·dim^{2} V_{i}} . Since Γ is Zariski dense, not all elements from Σ can fix v. Applying Lemma 3.4 again, we may find an element B in some bounded power of Σ such that none of the powers B^{j} for j = 1, ..., dim V_{i} fixes v. But, as can be seen from Cayley Hamilton’s theorem for instance, at least one of the B^{j}’s must send v at least ε away from H where ε is at least some fixed bounded power of ∥B∥ , hence of

Λ_{k}(A) because ∥B∥ ≤ ∥Σ∥ ≤ (\frac{3Λ_{k}(A)}{c})^{3d·dim^{2} V_{i}} . Hence A^{n} and B^{j}A^{n} are ping-players (i.e. generate a free semigroup) as soon as n is larger than a fixed constant depending only on d, c and δ. We can apply the ping lemma 3.2. □

In order to find non-torsion semisimple ping-pong players in a bounded ball Σ^{m} we have just used the following lemma from [7]:

Lemma 3.4. ([7]) Let 𝔾 be a Zariski connected algebraic group. Given a closed algebraic subvariety X ⊂ 𝔾, there is an integer k = k(𝔾, X) such that for any subset Σ ⊂ 𝔾 with e ∈ Σ generating a Zariski dense subgroup of 𝔾, the set Σ^{k} is not contained in X.

Also we made use of the following simple lemma:

Lemma 3.5. Suppose A ∈ SL_{d}(k) satisfies Λ_{k}(A) ≥ 2λ_{k}(A) where λ_{k}(A) is the modulus of the second highest eigenvalue of A. Then the top eigenvalue λ_{1} belongs to k, |λ_{1}| = Λ_{k}(A) and there exists h ∈ SL_{d}(\overline{k}) with ∥h∥ ≤ 3^{d} ∥A∥^{d^{2}} such that the matrix A′ = hAh^{−1} is such that A′e_{1} = λ_{1}e_{1} and A′H = H where H = ⟨e_{2}, ..., e_{d}⟩ and ∥A′_{|H} ∥ ≤ λ_{k}(A).

To obtain the uniformity in Theorem 2.1 we make use of the classical Margulis lemma which can be stated as follows:

Lemma 3.6. (The Margulis lemma) There is a constant ε = ε(d) > 0 such that for every finite set Σ in SL_{d}(ℝ), if Σ generates a non virtually nilpotent discrete subgroup, then E_{ℝ}(Σ) ≥ 1 + ε.

By another compactness argument we finally obtain:

Proposition 3.7. For every d ∈ ℕ^{∗} there is a constant C = C(d) > 0 and an integer N = N(d) > 0 such that for any finite subset Σ in SL_{d}(k) with e ∈ Σ such that Σ generates a non-virtually solvable group, if E_{k}(Σ) > C, then d^{pi}(Σ) ≤ N.

In particular the constant s in Corollary 2.2 depends on the Margulis constant ε(d) and on the constant c(d) from Proposition 3.3.

The argument sketched above treats the case of non-virtually solvable linear groups. For virtually solvable non-virtually nilpotent linear groups we apply a different argument using one dimensional affine representations instead of projective representations, which is based on some tools developed in [[4] Section 10] and in [2].

3.3. Separation properties, arithmeticity and free subgroups. Here we give some hints on the proof of our main result, Theorem 1.5. For the sake of simplicity, let us restrict ourselves to the case of Zariski-dense subgroups of SL_{d}(ℤ). In the last paragraph of this section, we shall give some indications about the general case.

The main difficulty comes from the fact that in order to generate a free group rather than just a free semigroup, one should construct a very proximal element rather than just a proximal one. To do that, one needs both a good control on the norms of the generators and good separation properties. For the latter we shall need arithmeticity.

Proposition 3.3 supplies us, for each given Σ, with a conjugating element h in SL_{d}(ℝ) such that the norm of hΣh^{−1} is bounded in terms of Λ(Σ). However, conjugating by h we “loose the arithmeticity”. The first part of the proof of Theorem 1.5 consists in replacing the conjugating element h by some γ ∈ SL_{d}(ℤ):

Proposition 3.8. There are positive constants c_{1} = c_{1}(d) and r_{1} = r_{1}(d) such that for any subset Σ in SL_{d}(ℤ) that generates a Zariski-dense subgroup of SL_{d}(ℝ) there exists γ ∈ SL_{d}(ℤ) such that

∥γΣγ^{−1}∥ ≤ c_{1} · E(Σ)^{r_{1}}

The proof of Proposition 3.8 relies on the following quantitative variant of Kazhdan–Margulis theorem^{2} which was suggested to us by G.A. Margulis:

2Note that Kazhdan-Margulis theorem (which states merely the existence of unipotents) is trivial in our case because our lattice is arithmetic, however we need the quantitative estimate.

Lemma 3.9. There are positive constants k_{0}, l_{0} such that for any h ∈ SL_{d}(ℝ) the group hSL_{d}(ℤ)h^{−1} ≤ G contains a non-trivial unipotent u with

∥u − 1∥ ≤ l_{0} · ∥π(g)∥^{−k_{0}}

where π : G → SL_{d}(ℝ)/SL_{d}(ℤ) is the canonical projection and ∥π(g)∥ = min_{γ∈SL_{d}(ℤ)} ∥gγ∥.

The main part of the proof of Theorem 1.5 relies on the construction of a very proximal element in a bounded power of γΣγ^{−1} acting on the projective space of a corresponding wedge power. This is done in three steps, in the first we construct a proximal element, in the second a very contracting one and in the third a very proximal one.

Note that, using Lemma 3.4, we can find a semisimple torsion free element inside a bounded power Σ^{k_{1}} for some constant k_{1}. The eigenvalues of this element are algebraic integers of bounded degree, hence Λ(Σ^{k_{1}}) ≥ 1 + ε_{1} for some constant ϵ_{1} > 0. Combining this observation with Proposition 3.8 we may therefore assume ∥Σ∥ ≤ Λ(Σ)^{r_{2}} for some constant r_{2} = r_{2}(d) > 0, after changing Σ into γΣ^{N}γ^{−1} for some power N = N(d).

We now find α ∈ Σ such that Λ(α) = Λ(Σ) and make Γ act on the (irreducible) wedge power representation V_{i} = Λ^{i}ℂ^{d}, where i is chosen so that Λ(A)/λ(A) ≥ Λ(Σ)^{1/d} and λ(A) is the maximum modulus of the second highest eigenvalue and A = Λ^{i}(α). Changing Σ into its image under this representation, we get

∥Σ∥ ≤ Λ(A)^{r_{3}}

for some other constant r_{3} = r_{3}(d) > 0. This produces the desired proximal element, hence concludes Step 1.

In order to find a very contracting element in a bounded power of Σ we need to find an element B with good separation properties with respect to A, namely a B that sends one eigenvector of A far from some hyperplane spanned by d − 1 eigenvectors of A.

Part of the problem is to make the word “far” more explicit. The condition that a matrix sends a vector outside a given hyperplane (with no condition on how far) is an algebraic one and is easily fulfilled thanks to Lemma 3.4. If the matrix has integer coefficients, as it will be the case thanks to Proposition 3.8 above, then it is possible to estimate this gap in terms of the norm of the matrix and the arithmetic complexity of the rationally defined hyperplane. This is the content of Lemma 3.10 below. For a vector u ∈ \overline{ℚ}^{d} ⊂ ℂ^{d} we denote ∥u∥_{m} = max\{∥σ(u)∥ , σ ∈ Gal(\overline{ℚ}, ℚ)\}.

Lemma 3.10. Let u_{1}, ..., u_{d} be d vectors in \overline{ℚ}^{d} whose coordinates are algebraic integers of degree at most n ≥ 1, and let M := max_{i} ∥u_{i}∥_{m} . If H is the hyperplane spanned by u_{2}, ..., u_{d} and B ∈ SL_{d}(ℤ), then either Bu_{1} ∈ H, or

d([Bu_{1}], [H]) ≥ \frac{1}{∥B∥^{n^{d}} M^{2dn^{d}}}

By Lemma 3.4 we can find B (in a bounded power of Σ) which is in “general position” with respect to the eigenvectors of A. We then prove:

Proposition 3.11. There is N = N(d) such that the following holds. Given q ∈ ℕ, there is a constant m_{0} > 0 and there is B ∈ Σ^{N} such that the element A^{m_{0}}BA^{−m_{0}} is Λ(A)^{−q}-very contracting, with both attracting points lying at a distance at most Λ(A)^{−q} from \overline{v} – the eigendirection corresponding to the maximal eigenvalue of A.

The proof of Lemma 3.11 relies on the following characterization of contracting elements in terms of their Lipschitz constants.

Lemma 3.12 (See Lemma 3.4, Lemma 3.5 and Proposition 3.3 in [4]). Let ϵ ∈ (0, \frac{1}{4}], r ∈ (0, 1]. Let g ∈ SL_{n}(ℝ) and let k_{g}a_{g}k′_{g} be a KAK expression for g where a_{g} = diag(a_{1}(g), a_{2}(g), …, a_{n}(g)), a_{i}(g) ≥ a_{i+1}(g) > 0.

(1) If a_{2}(g)/a_{1}(g) ≤ ϵ then g is ϵ/r^{2}-Lipschitz outside the r-neighborhood of the repelling hyperplane span{k′_{g}^{−1}(e_{i})}_{i=1}^{n}.

(2) If the restriction of g to some open neighborhood O ⊂ ℙ^{n−1}(ℝ) is ϵ-Lipschitz, then a_{2}(g)/a_{1}(g) ≤ ϵ/2.

(3) If a_{2}(g)/a_{2}(g) ≤ ϵ^{2} then g is ϵ-contracting, and vice versa, if g is ϵ-contracting, then a_{2}(g)/a_{2}(g) ≤ 4ϵ^{2}.

The third step is then to obtain a very proximal element by multiplying the very contracting one A^{m_{0}}BA^{−m_{0}} by some bounded word in the generators. We want to“separate” the repelling hyperplanes from the attracting points. Note that we do not have any information on the position of the repelling hyperplanes of A^{m_{0}}BA^{−m_{0}}, but we do have a good estimate on the position of its attracting points. We find the right multiplying element using a simple argument based on the pigeon-hole principle, and the fact that if d arithmetically defined vectors are linearly independent in ℂ^{d} then we can bound from below their maximal distance to an arbitrary hyperplane in terms of their arithmetic complexities and norms.

In the last part of the proof of Theorem 1.1, we conjugate our very proximal element by a suitable bounded word in the generators and obtain a second very proximal element which plays ping-pong with the first one. The argument for finding the appropriate conjugating element is quite similar to the argument for making the very contracting element a very proximal one.

Let us now say some words about the general case, i.e. when Γ is Zariskidense in 𝔾(O_{𝕂}(S)). By the Borel–Harish-Chandra theorem, 𝔾(O_{𝕂}(S)) is an arithmetic lattice in some semisimple Lie group G ≤ ∏_{v∈S} SL_{d}(𝕂_{v}) over a product of local fields. The absolute value on each 𝕂_{v} extends uniquely to any algebraic extension. For g = (g_{v})_{v∈S} we define ∥g∥ = max ∥g_{v}∥_{v} and Λ(g) = max(Λ_{𝕂_{v}}(g_{v})). We obtain the general version of Proposition 3.8 from Proposition 3.3 in two steps. The fist step consists in replacing the conjugating element h ∈ ∏_{v∈S} SL_{d}(𝕂_{v}) by some element g ∈ G. To do that we exploit theorems of Mostow and Landvogt about totally geodesic embeddings of symmetric spaces, and some simple geometric argument using orthogonal projections on convex subsets in CAT(0) spaces. In a second step, we replace the element g by some element γ ∈ 𝔾((O_{𝕂}(S)). This step is quite simple in the case where 𝔾 is anisotropic, i.e. when G/𝔾(O_{𝕂}(S)) is compact, because then we can pick γ at a bounded distance from g. In the isotropic case we use a generalized version of Lemma 3.9.

The rest of the proof goes along the same lines sketched above. The guiding idea is that the distance between arithmetically defined geometric objects is either 0 or can be bound from below in terms of their arithmetic complexity.

Remark 3.1. Let us note that the uniform bound for the independence diameter that our proof gives for a subgroup of an arithmetic lattice Δ = 𝔾(O_{𝕂}(S)) ≤ G does strongly depend on Δ and not just on the ambient Lie group G. In case Δ is a uniform lattice, it depends on the the diameter and the injectivity radius of the associated locally symmetric manifold K\G/Γ. However, for non-uniform arithmetic lattices Δ ≤ G we do obtain a uniform constant depending only on G.

References

[1] G.N. Arzhantseva, J. Burillo, M. Lustig, L. Reeves, H. Short, E. Ventura, Uniform non-amenability, Advances in Math., (2005).

[2] E. Breuillard, A note on exponential growth for solvable groups, preprint.

[3] E. Breuillard, T. Gelander, On dense free subgroups of Lie groups, J. Algebra, 261 , no. 2, pp. 448–467, (2003).

[4] E. Breuillard, T. Gelander, A topological Tits alternative, to appear in the Annals of Math.

[5] E. Breuillard, T. Gelander, A uniform Tits alternative, in preperation,

[6] E. Breuillard, T. Gelander, A. Salehi-Golsefidy, On uniform exponental growth in general characteristic, an appendix to [5], in preparation.

[7] A. Eskin, M. Mozes, H. Oh, On uniform exponential growth for linear groups in characteristic zero, Invent. Math. 160, no. 1, pp. 1–30, (2005).

[8] T. Gelander, A. Zuk, Dependence of Kazhdan constants on generating subsets, Israel J. Math. 129 (2002), 93–98.

[9] R. Grigorchuk, P. de la Harpe, Limit behaviour of exponential growth rates for finitely generated groups, in Essays on geometry and related topics, Vol. 1, 2, 351–370, Monogr. Enseign. Math., 38, (2001).

[10] Y. Shalom, Explicit Kazhdan constants for representations of semisimple and arithmetic groups, Ann. Inst. Fourier, 50 (2000), no. 3, 833–863.

[11] J. Tits, Free subgroups of Linear groups, Journal of Algebra 20 (1972), 250-270.

  E-mail address: emmanuel.breuillard@math.univ-lille1.fr
  E-mail address: tsachik.gelander@yale.edu