Random Walks in Compact Groups

Péter Pál Varjú^{1}

Received: December 17, 2012

Communicated by Ursula Hamenstädt

Abstract. Let X_{1}, X_{2}, … be independent identically distributed random elements of a compact group G. We discuss the speed of convergence of the law of the product X_{l} ⋯ X_{1} to the Haar measure. We give poly-log estimates for certain finite groups and for compact semi-simple Lie groups. We improve earlier results of Solovay, Kitaev, Gamburd, Shahshahani and Dinai.

2010 Mathematics Subject Classification: 60B15, 22E30, 05E15 Keywords and Phrases: random walk, spectral gap, diameter, polylog, Solovay-Kitaev, compact group, Cayley graph

1 Introduction

Let G be a group and S ⊂ G a finite set. We study the distribution of the product of l random elements of S. In particular, we are interested in how fast this distribution becomes uniform as l grows. We discuss the problem in two different but very related settings: profinite groups, and compact Lie groups.

1.1 Two ways to measure uniformity

We begin by describing the details in the first setting. Let G be a finite group and S ⊂ G be a finite generating set. For simplicity, we assume that 1 ∈ S. The unit element of any group is denoted by 1 in this paper. Write

S^{l} = {g_{1} ⋯ g_{l} : g_{1}, …, g_{l} ∈ S}

for the l-fold product set of S. The diameter of G with respect to S is defined by

diam(G, S) = min{l : S^{l} = G}.

1 I gratefully acknowledge the support of the Simons Foundation and the European Research Council (Advanced Research Grant 267259)

Documenta Mathematica 18 (2013) 1137–1175

The diameter is the minimal length of a product that can express any element of the group. Hence it is a (very weak) quantity to measure uniformity. We quantify uniformity in a stronger sense, too. To this end, we introduce the notion of random walks. Denote by μ_{S} the normalized counting measure on the set S, and let X_{1}, X_{2}, … be a sequence of independent random elements of S with law μ_{S}. The (simple) random walk is the sequence of random elements Y_{0}, Y_{1}, … of G such that Y_{0} = 1 almost surely, and Y_{l+1} = X_{l+1}Y_{l} for all l ≥ 0. Denote by μ_{S}^{∗(l)} the l-fold convolution of the measure μ_{S} with itself. Convolution of two measures (or functions) μ, ν is defined by the usual formula

μ ∗ ν(g) = ∑_{h∈G} μ(gh^{−1})ν(h).

Observe that μ_{S}^{∗(l)} is the law of Y_{l}. We want to understand, how large l is needed to be taken such that μ_{S}^{∗(l)} is “very close” to the uniform distribution. We make this precise with the following construction. Consider the space L^{2}(G) which is simply the vector space of complex valued functions on G endowed with the standard scalar product. The group G acts on this by

Reg_{G}(g)f(h) = f(g^{−1}h) for f ∈ L^{2}(G).

This is a unitary representation called the regular representation. To a measure μ, we associate an operator (linear transformation) on L^{2}(G):

Reg_{G}(μ) = ∑_{g∈G} μ(g) · Reg_{G}(g).

This is an analogue of the Fourier transform of classical harmonic analysis. In particular, it has the following property:

Reg_{G}(μ ∗ ν) = Reg_{G}(μ) · Reg_{G}(ν),

which is easy to verify from the definitions. We can recover μ by the formula

μ = Reg_{G}(μ)δ_{1},  (1)

where δ_{1} is the Dirac measure supported at 1. (Recall that G is finite, hence we can embed the space of probability measures into L^{2}.) The operator Reg_{G}(μ_{S}) is of norm 1 and it acts trivially on the one dimensional space of constant functions. We denote by Reg_{G}^{∘} the restriction of Reg_{G} to the 1 codimensional space orthogonal to constants. We define by

gap(G, S) := 1 − ∥Reg_{G}^{∘}(μ_{S})∥

the spectral gap of the random walk on G generated by S. Later, we will consider a slightly more general situation and replace μ_{S} by an arbitrary probability measure μ. Then we write

gap(G, μ) := 1 − ∥Reg_{G}^{∘}(μ)∥.

It is clear that

∥Reg_{G} (μ_{S}^{∗(l)}) − Reg_{G}(μ_{G})∥ < e^{−l·gap(G,S)}.  (2)

This shows that if we take say l = 10 log |G|/gap(G, S), then μ_{S}^{∗(l)} is very close to the uniform distribution (see (1)). In particular, the support of μ_{S}^{∗(l)} is the whole group. Thus spectral gap is a stronger quantity to measure uniformity than diameter. Somewhat surprisingly we can obtain a bound in the other direction, as well.

Lemma 1. Let G be an arbitrary finite group, and 1 ∈ S ⊂ G. Suppose that S is symmetric, i.e. g ∈ S if and only if g^{−1} ∈ S. We have:

(diam(G, S) − 1)/ log |G| ≤ gap(G, S)^{−1} ≤ |S|diam(G, S)^{2}.

This lemma is well-known. The second (and more difficult) inequality of it can be found for example in [13, Corollary 1 in Section 3]. The other estimate follows directly from (2). The assumption on symmetricity is not an essential one. Later, at the beginning of Section 2.1 we show how to reduce the problem to the symmetric case. We stop for a moment to connect our terminology to the computer science and combinatorics literature. If S is symmetric, then the matrix of the operator Reg_{G}(μ_{S}) is proportional to the adjacency matrix of the Cayley graph of G with respect to the generating set S. In that case gap(G, S) is proportional to the spectral gap of the Cayley graph. If gap(G, S) ≥ c > 0 for a family of groups and generators than the corresponding family of Cayley graphs are called expanders. However, in this paper we are looking for weaker bounds of the form gap(G, S) ≥ log^{−A} |G| which, in light of the above Lemma, is equivalent to diam(G, S) ≤ log^{A′} |G| as long as say |S| < 10 and one does not care about the value of A and A′. We call such bounds poly-logarithmic.

1.2 Prior results

It was conjectured by Babai and Seress [1, Conjecture 1.7] that the family of non-Abelian finite simple groups have poly-logarithmic diameter, i.e. there is a constant A such that diam(G, S) ≤ log^{A} |G| holds for any non-Abelian finite simple group G and generating set S ⊂ G. This has been verified for the family SL_{2}(F_{p}) by Helfgott [22, Main Theorem] and for finite simple groups of Lie type of bounded rank by Breuillard, Green and Tao [11, Theorem 7.1] and Pyber and Szabó [30, Theorem 2] independently. The conjecture is still open for other families of finite simple groups. The best known bound to date on the diameter of alternating groups is due to Helfgott and Seress [24] and it is slightly weaker than poly-logarithmic. However, the first results on poly-logarithmic diameter were obtained for nonsimple groups. Fix a prime p and a symmetric set S ⊂ SL_{2}(Z) such that (the projection of) S generates SL_{2}(Z/p^{2}Z). Gamburd and Shahshahani [20, Theorem 2.1] proved the poly-log diameter estimate

diam(SL_{2}(Z/p^{n}Z), S) ≤ C log^{A} |SL_{2}(Z/p^{n}Z)|,

where C depends only on S and A is an absolute constant. Dinai [15, Theorem 1.2] observed that the result holds with C depending only on p and he also improved the parameter A. Thus the family SL_{2}(Z/p^{n}Z) enjoys a uniform poly-log diameter bound with respect to arbitrary generators. Using the result of Helfgott [22], the constant C can be made absolute. In [16, Theorem 1.1], Dinai extended the result to the quotients of other Chevalley groups over local rings. The result of this paper is also about non-simple finite groups. In fact, it is part of our assumptions that all simple quotients of the groups we study has poly-logarithmic diameter. Our result has a huge overlap with [20], [15] and [16]. We will remark on this later.

1.3 The role of quasirandomness

Our approach is based on representation theory, but we will use only very basic facts of the theory. We explain the key idea of the paper, which allows us to estimate the spectral gap based on lower bounds for the dimension of nontrivial representations of the group. Let μ be a probability measure on G. Write χ_{G} and χ_{G}^{∘} respectively for the characters of Reg_{G} and Reg_{G}^{∘}. Furthermore, we write

χ(μ) = ∑_{g∈G} μ(g) · χ(g),

where χ is the character of a representation of G. Then χ_{G}(μ) is the trace of the operator Reg_{G}(μ). For the moment, assume that μ is symmetric that is μ(g^{−1}) = μ(g) for all g ∈ G. Then Reg_{G}(μ) is selfadjoint. We can decompose L^{2}(G) as the orthogonal sum of irreducible subrepresentations of Reg_{G}. As is well known, if π is an irreducible representation of G, then exactly dim π isomorphic copies of π appear in the decomposition of Reg_{G}. If λ is an eigenvalue of Reg_{G}(μ) then there is a corresponding eigenvector in one of the irreducible representations of G. Moreover, there is one in each isomorphic copy. This leads us to the following inequality which is fundamental to us:

dim(π) · λ^{2} ≤ χ_{G}(μ ∗ μ),  (3)

where π is an irreducible representation of G such that there is an eigenvector corresponding to λ in π. (Note that all eigenvalues of Reg_{G}(μ ∗ μ) are nonnegative.) This idea goes back to Sarnak and Xue [32] and it is also one of the major steps in the work of Bourgain and Gamburd [2] on estimating spectral gaps and also in several papers [4], [5], [7], [34], [9], [31] which follow it. Gowers [21] also exploited the idea, and introduced the term quasirandom for groups that does not have low dimensional non-trivial representations. He proved several properties of such groups, in particular that they do not have large productfree subsets. Nikolov and Pyber [29, Corollary 1] pointed out that Gowers’s result implies that any element of a quasirandom group can be expressed as the product of three elements of a sufficiently large subset. In what follows, G is a profinite group and Ω denotes the family of finite index normal subgroups of it. An interesting example to have in mind is G = SL_{d}(Ẑ), where Ẑ is the profinite (congruence) completion of the integers. (The reader unfamiliar with the notion of profinite groups may assume that G is finite without loss of generality.) Inspired by Gowers’s terminology, we make the following definition.

Definition 2. We say that a profinite group G is (c, α)-quasirandom if for every irreducible unitary representation π of G, we have

dim π ≥ c[G : Ker(π)]^{α}.

1.4 Results about profinite groups

Let G be a profinite group and Γ a finite index normal subgroup. Our plan is to prove the estimate

gap(G/Γ, S) ≥ c log^{−A}[G : Γ]  (4)

with constants c, A independent of Γ and S. We prove this statement by induction as follows: We find a larger subgroup Γ ◁_{≠} Γ′ ∈ Ω and assume that the above spectral gap estimate holds for Γ′. We use this to bound the trace of the operator Reg_{G/Γ′}(μ_{S}^{∗(l)}) for a suitable integer l. This in turn gives an

estimate for the trace of Reg_{G/Γ}(μ_{S}^{∗(l)}), and by (3) we can estimate gap(G/Γ, S) and continue by induction. In order that the induction step works, we need to ensure that [Γ′ : Γ] is “not very large” compared to [G : Γ]. Of course, we cannot always find a suitable Γ′, in particular when G/Γ is simple. The statement of the following theorem is very technical, so we first explain it informally: We suppose that G is a quasirandom profinite group and partition its finite index normal subgroups into two sets: Ω_{1} ˙∪Ω_{2}. We assume that for Γ ∈ Ω_{1} we can find a larger subgroup Γ′ ∈ Ω so that [Γ′ : Γ] is “not very large”. We assume further that for Γ ∈ Ω_{2}, the quotient G/Γ has poly-log spectral gap (i.e. (4) is satisfied). Then we can conclude a poly-log estimate (4) for all Γ ∈ Ω.

Theorem 3. Let c_{1}, α, β and A be positive numbers satisfying β < α and

A ≥ (α − β)^{−1} − 1.

Then there is a positive number C_{1} depending only on c_{1}, α, β and A such that the following holds.

Let G be a (c_{1}, α)-quasirandom profinite group. Let Ω_{1} ˙∪Ω_{2} = Ω be a partition of the family of finite index normal subgroups of G. Suppose that for all Γ ∈ Ω_{1}, we have [G : Γ] > C_{1} and there is Γ′ ∈ Ω with Γ ◁_{≠} Γ′ such that

[Γ′ : Γ] ≤ [G : Γ′]^{β}.  (5)

Let μ be a Borel probability measure on G and suppose that

gap(G/Γ, μ) ≥ B · log^{−A}[G : Γ]  (6)

for all Γ ∈ Ω_{2}. Then for all Γ ∈ Ω

gap(G/Γ, μ) ≥ C_{1}^{−1}B · log^{−A}[G : Γ].

To verify assumption (6), we need to use known cases of the Babai–Seress conjecture mentioned above. Fortunately, this is available for many cases in the papers [22, Main Theorem], [23, Corollary 1.1], [11, Theorem 7.1], [30, Theorem 2]. In particular we can deduce the following.

Corollary 4. Let S ⊂ SL_{d}(Ẑ) be a set generating a dense subgroup. Then for all integers q > 1, we have

gap(SL_{d}(Z/qZ), S) ≥ c log^{−A}(q),

where A > 0 is a number depending on d and c is a number depending on d and |S|.

We stress here that c depends only on the cardinality of S. Note that this dependence is necessary, owing to the following example: It may happen that all but one element of S projects into a proper subgroup of SL_{d}(Z/qZ) in which case the characteristic function of the subgroup is an almost invariant function if |S| is large. In the case S ⊂ SL_{d}(Z) one can improve the poly-log bound to a uniform one. More precisely, Bourgain and Varjú [9, Theorem 1] proved gap(SL_{d}(Z/qZ), S) ≥ c with a constant c > 0 independent of q but dependent on S. This strongly resonates with the sate of affairs for compact semi-simple Lie groups to be discussed below. Finally, we compare our result to the papers of Gamburd and Shahshahani [20, Theorem 2.1] and Dinai [15, Theorem 1.2], [16, Theorem 1.1]. These papers give results similar to Corollary 4, and even more, the proofs have some common features with our approach. However, they obtain the diameter bound directly and they use properties of commutators instead of representation theory. A flaw of our approach that it is not constructive, i.e. we can not give an efficient algorithm to express an element of G/Γ as a product of elements of S. On the contrary, [20, Theorem 2.1], [15, Theorem 1.2], [16, Theorem 1.1] give such algorithms. The advantage of our paper that it seems to apply in more general situations, e.g. [20, Theorem 2.1], [15, Theorem 1.2], [16, Theorem 1.1] are restricted to the case when q is the power of a prime. A comment on the exponents: If one considers the group G = SL_{2}(Z_{p}), where p is a fixed prime, then the conditions of Theorem 3 can be satisfied for any A > 2. This via Lemma 1 exactly recovers the diameter bound for SL_{2}(Z/p^{k}Z) in the paper [15, Theorem 1.2], but our bound for the spectral gap is better than what could be obtained from [15]. If one considers SL_{d} with d large than our bounds deteriorate compared to [15]. However, it seems possible that a more careful version of our argument could give better bounds, but this requires a more precise understanding of the representations. In Section 2.2 we include some remarks about what this would require. These ideas are worked out in the setting of compact Lie groups.

1.5 Results about compact Lie groups

We turn to the second setting of our paper. Let G be a semi-simple compact Lie group endowed with the bi-invariant Riemannian metric. We denote by dist(g, h) the distance of two elements g, h ∈ G. Let ε > 0 be a number and S ⊂ G be a finite subset which generates a dense subgroup. Again, for simplicity, we assume 1 ∈ S. We define the diameter of G at scale ε with respect to S by

diam_{ε}(G, S) = min{l : for every g ∈ G there is h ∈ S^{l} such that dist(g, h) < ε}.

We also introduce the relevant spectral gap notion. This requires some basic facts about the representation theory of compact Lie groups. We follow the notation in [12], but the results we need can be found in many of the textbooks on the subject, as well. Let T be a maximal torus in G and denote by LT its tangent space at 1. Then T can be identified with LT/I via the exponential map, where I is a lattice in LT. Denote by LT^{∗} the dual of LT and by I^{∗} ⊂ LT^{∗} the lattice dual to I. We denote by R ⊂ I^{∗} the set of roots, and by R_{+} (a choice of) the positive roots. We fix an inner product ⟨·, ·⟩ on LT which is invariant under the Weyl group. Denote by

K = {u ∈ LT : ⟨u, v⟩ > 0 for every v ∈ R_{+}}

the positive Weyl chamber and by \overline{K} its closure. It is well known (see [12, Chapter IV (1.7)]) that the irreducible representations of G can be parametrized by the elements of I^{∗} ∩\overline{K}. For v ∈ I^{∗} ∩\overline{K}, we denote by π_{v} the unitary representation of G with highest weight v. For a finite Borel measure μ on G, we write

π_{v}(μ) = ∫ π_{v}(g) dμ(g),

which is an operator (linear transformation) on the representation space of π_{v}. Let r > 1 be a number, and S ⊂ G a finite set which contains 1 and generates a dense subgroup. Define the spectral gap at scale 1/r with respect to S by

gap_{r}(G, S) := 1 − max_{0<|v|≤r} ∥π_{v}(μ_{S})∥.

As in the finite case, the notions of spectral gap and diameter are closely related:

Lemma 5. Let G be a compact connected semi-simple Lie group, and let 1 ∈ S ⊂ G be finite. Then there is a constant C > 0 depending only on G such that for any ε > 0

diam_{ε}(G, S) ≤ \frac{C log(ε^{−1})}{gap_{Cε^{−C}} (G, S)}

and for any r ≥ 1

gap_{r}(G, S) ≥ \frac{1}{|S|diam_{(Cr)^{−C}} (G, S)^{2}} .

This lemma is also well-known. We give a proof in Section 4 for completeness. In Section 3, we develop an analogue for compact Lie groups of the ideas explained in the previous section. A replacement for (3) was given by Gamburd, Jacobson and Sarnak [19] and it appeared in various forms in [3] and [6], as well. However, these are based on direct calculation with characters rather than on multiplicities of eigenvalues. A more direct analogue of (3) and also of the results of Gowers [21] and Nikolov and Pyber [29] was developed very recently by Saxcé [33]. Our main result in the setting of compact Lie groups is the following:

Theorem 6. For every semi-simple compact connected Lie group G, there are numbers c, r_{0} and A such that the following holds. Let μ be an arbitrary probability measure on G. Then

gap_{r}(G, μ) ≥ c · gap_{r_{0}}(G, μ) · log^{−A} r.

For simple groups, the value of A can be found in Table 1. For semi-simple groups A is the maximum of the corresponding values over all simple quotients of G. In particular, A ≤ 2 for all groups.

\begin{matrix}A_{n} & B_{n} & C_{n} & D_{n} & E_{6} & E_{7} & E_{8} & F_{4} & G_{2} \\ 1 + \frac{2}{n+1} & 1 + \frac{1}{n} & 1 + \frac{1}{n} & 1 + \frac{1}{n−1} & \frac{7}{6} & \frac{10}{9} & \frac{16}{15} & \frac{7}{6} & \frac{4}{3} \end{matrix}

Table 1: The value of A(G) in terms of the Dynkin diagram

A poly-logarithmic estimate for diam_{ε}(SU(2), S) was found by Solovay and Kitaev independently. Nice expositions are in the paper of Dawson and Nielsen [14, Theorem 1] and in the book [26, Chapter 8.3], where they obtain the bound diam_{ε}(SU(2), S) < log^{3} ε^{−1}. Our theorem provides the same bound for the diameter of SU(2). On the other hand, our spectral gap bound in Theorem 6 beats anything that could be obtained from a diameter bound via Lemma 5. Dolgopyat [17, Theorems A.2 and A.3] gave an estimate for the spectral gap which is weaker than poly-logarithmic but his argument would give a poly-log estimate without significant changes. His proof consists of a version of the Solovay-Kitaev argument (that he discovered independently) and a variant of Lemma 5. The connection between the present paper and [17] was pointed out to me by Breuillard, see also his survey [10]. We note that Bourgain and Gamburd [3, Corollary 1.1], [6, Theorem 1] showed that when μ = μ_{S} for some finite set 1 ∈ S ⊂ SU(d) and the entries of the elements of S are algebraic numbers, then

gap_{r}(G, S) ≥ c

for some constant c depending on G and S. Their argument is likely to carry over to arbitrary semi-simple compact Lie groups, however the assumption on algebraicity is essential for the proof. It is a very interesting open problem whether this assumption can be removed. Moreover, we raise the following question: Is it true that there are numbers c, r_{0} depending only on G such that

gap_{r}(G, μ) ≥ c · gap_{r_{0}}(G, μ)

for all probability measures μ on G? Finally, we state a technical result which almost immediately follow from Theorem 6. Its purpose is that this is the version used in the paper [35] to study random walks in the group of Euclidean isometries. For a measure ν on G, we define the measure ν̃ by

∫ f(x) dν̃(x) = ∫ f(x^{−1}) dν(x)

for all continuous functions f. We write m_{G} for the Haar measure on G.

Corollary 7. Let G be a compact Lie group with semi-simple connected component. Let μ be a probability measure on G such that supp (μ̃ ∗ μ) generates a dense subgroup in G. Then there is a constant c > 0 depending only on μ such that the following holds. Let φ ∈ Lip(G) be a function such that ∥φ∥_{2} = 1 and ∫ φ dm_{G} = 0. Then

∥∫ φ(h^{−1}g) dμ(h)∥_{2} < 1 − c log^{−A}(∥φ∥_{Lip} + 2),

where A depends on G and is the same as in Theorem 6.

The rest of the paper is organized as follows. In Section 2 we give the proof of Theorem 3 and Corollary 4. The proof of Theorem 6 is given in Section 3. Sections 2 and 3 are independent, but there is a strong analogy between the two arguments. Finally we prove Corollary 7 and Lemma 5 in Section 4.

Throughout the paper we use the letters c and C to denote numbers which may depend on several other quantities and their value may change at each occurrence. We follow the convention that c tends to denote numbers that we consider “small” and C denotes those that we consider “large”.

1.6 Motivation

In recent years there was a lot of progress on the Babai-Seress conjecture mentioned above, although it has not been settled yet. In addition, poly-log spectral gap and diameter is known to hold for some families of non-simple finite groups as well. What the scope of this phenomenon is, is an interesting question. Our result on finite groups is a (very modest) step towards understanding this. In Section 2.2 we include some remarks on how to exploit our approach for non-quasirandom groups. Our main motivation for Theorem 6 is the application in the paper [35]. Although it seems easy to extend the Solovay-Kitaev approach to prove similar poly-log type bounds, we believe that our method gives better exponents, at least for spectral gaps. There are many recent applications of spectral gaps. Many of these require stronger bounds than what we obtain in this paper, e.g. the results in [2], [4], [5], [7], [34], [9], [31] mentioned above. However, for some applications, the poly-log type bounds are enough, at least to obtain the same qualitative result. Prominent examples are the work of Ellenberg, Hall and Kowalski [18], the Group Large Sieve developed by Lubotzky and Meiri [28], the study of curvatures in Apollonian Circle Packings by Bourgain and Kontorovich [8] and the study of random walks on Euclidean isometries by Varjú [35]. However, our results are relevant only for the last two of the above papers, because [18] and [28] requires spectral gaps only for products of two simple groups. In addition, in the case of [8] a better uniform spectral gap is available. Acknowledgments. I thank Jean Bourgain for discussions related to this project, in particular, for explaining to me the relation between the diameter and the spectral gap. I thank Nicolas de Saxcé for careful reading of my manuscript and for his suggestions which greatly improved the presentation of the paper. I thank Emmanuel Breuillard for calling my attention on the work of Dolgopyat [17].

2 Profinite groups

2.1 Proof of Theorem 3

Recall that G is a profinite group and Ω is the family of finite index normal subgroups of it. Assume that the hypothesis of the theorem is satisfied. We note that α ≤ 1/2, since (dim π)^{2} ≤ |G/Γ| for any irreducible representation π of the group G/Γ. Consequently A ≥ 1.

We first explain how to reduce to the case when μ is symmetric. Define the probability measure μ̃ by

∫ f(g) dμ̃(g) = ∫ f(g^{−1}) dμ(g).

(If G is finite, this is can be expressed as μ̃(g) = μ(g^{−1}).) Clearly μ̃ ∗ μ is symmetric and

Reg_{G/Γ}^{∘}(μ̃ ∗ μ) = Reg_{G/Γ}^{∘}(μ)^{∗} · Reg_{G/Γ}^{∘}(μ).

Hence

∥Reg_{G/Γ}^{∘}(μ̃ ∗ μ)∥ = ∥Reg_{G/Γ}^{∘}(μ)∥^{2}.

This yields

gap(G/Γ, μ̃ ∗ μ) ≥ gap(G/Γ, μ) ≥ gap(G/Γ, μ̃ ∗ μ)/2.

This shows that the spectral gap of μ̃ ∗ μ is roughly proportional to that of μ, hence it suffices to prove the theorem for the first one. From now on, we assume that μ is symmetric, hence the operator Reg_{G/Γ}(μ) is selfadjoint and has an eigenbasis with real eigenvalues. We define

l_{Γ} = 2⌊C_{Γ} log^{A+1}[G : Γ]⌋,

where

C_{Γ} := C_{0}(10 − log^{−1/10}([G : Γ])),

and

C_{0} = max_{Γ∈Ω_{2}} \frac{1}{gap(G/Γ, μ) · log^{A}[G : Γ]}.

(The role of the subtracted term in the definition of C_{Γ} is simply to cancel lower order terms later.) Recall that we denote by χ_{G/Γ} the character of Reg_{G/Γ}. Our goal is to prove

χ_{G/Γ} (μ^{∗(l_{Γ})}) ≤ M,  (7)

where M ≥ 2 is a suitably large number depending on α and β. Once we proved this, the claim of the theorem will be concluded easily. The proof is by induction with respect to the partial order ◁ on Γ ∈ Ω. Suppose that (7) holds for all Γ′ ∈ Ω with Γ ◁_{≠} Γ′. We distinguish two cases. First we suppose that Γ ∈ Ω_{2}. Note that χ_{G/Γ}(μ^{∗(l_{Γ})}) is the trace of the operator Reg_{G/Γ}(μ^{∗(l_{Γ})}), hence it is the sum of its eigenvalues. The non-trivial eigenvalues are bounded by e^{−l_{Γ}·gap(G/Γ,μ)}, hence

χ_{G/Γ} (μ^{∗(l_{Γ})}) ≤ 1 + [G : Γ] · e^{−l_{Γ}·gap(G/Γ,μ)}
≤ 1 + [G : Γ] · e^{−C_{0} log^{A+1}[G:Γ]·gap(G/Γ,μ)} ≤ 1 + 1

using the definitions of l_{Γ}, C_{Γ} and C_{0}. Hence (7) follows. Now we suppose that Γ ∉ Ω_{2}, hence Γ ∈ Ω_{1}, in particular [G : Γ] ≥ C_{1}, where C_{1} can be taken as large as we need depending on α, β, c_{1}, A. Let Γ′ be such that Γ ◁ Γ′ ∈ Ω and [Γ′ : Γ] is minimal but larger than 1. Then by assumption, [Γ′ : Γ] ≤ [G : Γ′]^{β}. Since χ_{G/Γ} is pointwise majorized by the function [Γ′ : Γ] · χ_{G/Γ′}, and μ^{∗(l′_{Γ})} is a positive measure, we have

χ_{G/Γ} (μ^{∗(l_{Γ′})}) ≤ [Γ′ : Γ] · χ_{G/Γ} (μ^{∗(l_{Γ′})}) ≤ M[Γ′ : Γ].  (8)

We applied (7) for Γ′ in the second inequality. Denote by λ_{0} = 1, λ_{1}, … λ_{k} the eigenvalues of the operator Reg_{G/Γ}(μ) each listed as many times as its multiplicity. Then

χ_{G/Γ} (μ^{∗(l_{Γ})}) = 1 + ∑_{i=1}^{k} λ_{i}^{l_{Γ}} ≤ 1 + (∑_{i=1}^{k} λ_{i}^{l_{Γ′}} ) · max{λ_{i}}^{l_{Γ}−l_{Γ′}}
≤ 1 + M[Γ′ : Γ] max{λ_{i}}^{l_{Γ}−l_{Γ′}} .  (9)

We applied (8) in the last line. Also note, that all terms are positive because l_{Γ} is even by construction. Our next goal is to obtain a sufficient bound on the λ_{i}. This can be deduced from (8) and the assumption about the dimension of faithful representations. The representation Reg(G/Γ) can be decomposed as the orthogonal sum of irreducible subrepresentations. Each irreducible representation occur with multiplicity equal to its dimension. Consider now an eigenvalue λ_{i}. There is a corresponding eigenvector which is contained in an irreducible subrepresentation of Reg(G/Γ). Denote this representation by π. Write Γ′′ = Ker(π). First we consider the case that Γ′′ = Γ. It follows that λ_{i}^{l_{Γ′}} is an eigenvalue of Reg_{G/Γ}(μ^{∗(l_{Γ′})}) with multiplicity at least

dim π ≥ c_{1}[G : Γ]^{α},

(by the assumption on quasirandomness). Hence by (8) we can conclude that

λ_{i}^{l_{Γ′}} ≤ \frac{M[Γ′ : Γ]}{c_{1}[G : Γ]^{α}} .

Next, we consider the case when Γ′′ ≠ Γ. By the assumption on the minimality of [Γ′ : Γ], we have [G : Γ′′] ≤ [G : Γ′]. We apply (7) for Γ′′ along with the bound for the multiplicity of eigenvalues and get

λ_{i}^{l_{Γ′′}} ≤ \frac{M}{c_{1}[G : Γ′′]^{α}} .

An easy calculation shows that the bound we obtain for |λ_{i}| is worsening when [G : Γ′′] grows.

Thus in both cases we obtain:

λ_{i}^{l_{Γ′}} ≤ \frac{M[Γ′ : Γ]}{c_{1}[G : Γ′]^{α}} .  (10)

We plug this into (9) and we want to conclude χ_{G/Γ}(μ^{∗(l_{Γ})}) ≤ M. To this end, we need

M[Γ′ : Γ] (\frac{M[Γ′ : Γ]}{c_{1}[G : Γ′]^{α}} )^{(l_{Γ}−l_{Γ′})/l_{Γ′}} ≤ M − 1

that is

\frac{M}{M − 1}[Γ′ : Γ] ≤ (\frac{c_{1}[G : Γ′]^{α}}{M[Γ′ : Γ]} )^{(l_{Γ}−l_{Γ′})/l_{Γ′}} .  (11)

For simplicity, we write X = log[G : Γ′] and Y = log[Γ′ : Γ]. Then by the definition of l_{Γ}:

\frac{l_{Γ} − l_{Γ′}}{l_{Γ′}} = \frac{2⌊C_{Γ}(X + Y)^{A+1}⌋ − 2⌊C_{Γ′}X^{A+1}⌋}{2⌊C_{Γ′}X^{A+1}⌋}
≥ \frac{C_{Γ}(X + Y)^{A+1} − C_{Γ′}X^{A+1} − 1}{C_{Γ′}X^{A+1}}
≥ \frac{C_{Γ′}(X + Y)^{A+1} − C_{Γ′}X^{A+1}}{C_{Γ′}X^{A+1}} + \frac{C_{Γ} − C_{Γ′}}{C_{Γ′}} − \frac{1}{C_{Γ′}X^{A+1}}
≥ (A + 1)\frac{Y}{X} + c_{2} \frac{Y}{X^{11/10}} ,  (12)

where c_{2} is an absolute constant if X is larger than an absolute constant. (Using the definition of C_{Γ}, we evaluate (C_{Γ} − C_{Γ′})/C_{Γ′} and get the second term of (12). Notice that this is of larger order of magnitude than 1/X^{A+1}.) Then the logarithm of the right hand side of (11) is at least

((A + 1)\frac{Y}{X} + c_{2} \frac{Y}{X^{11/10}} ) (αX − log(M/c_{1}) − Y)

≥ α(A + 1)Y − log(M/c_{1})(A + 1)\frac{Y}{X} − (A + 1)\frac{Y^{2}}{X} + c_{3} \frac{Y}{X^{1/10}}

≥ α(A + 1)Y − (A + 1)\frac{Y^{2}}{X} + c_{3} \frac{Y}{2X^{1/10}}

if X is sufficiently large depending on α, β, c_{1}, A. Here c_{3} is a sufficiently small constant depending on α and β satisfying c_{3}X ≤ c_{2}(αX − log(M/c_{1}) − Y). (Recall that Y ≤ βX by assumption.) To get (11), we need

log(M/(M − 1)) + Y ≤ α(A + 1)Y − (A + 1)\frac{Y^{2}}{X} + c_{3} \frac{Y}{2X^{1/10}}

that is

A + 1 ≥ \frac{1 + log(M/(M − 1))/Y − c_{4}X^{−1/10}}{α − Y/X + c_{4}X^{−1/10}} ,  (13)

Documenta Mathematica 18 (2013) 1137–1175

where c_{4} is yet another number depending on α, β, c_{1}, A. We consider two cases. If Y ≤ \sqrt{X} (and X is sufficiently large) then Y/X ≤ c_{4}X^{−1/10}. Clearly Y ≥ log 2, hence (13) holds if

A + 1 ≥ \frac{1 + log(M/(M − 1))/ log 2}{α}.

On the other hand if Y ≥ \sqrt{X} (and X is sufficiently large) then log(M/(M − 1))/Y ≤ c_{4}X^{−1/10}. Recall that Y/X ≤ β by assumption, hence (13) holds if A + 1 ≥ (α − β)^{−1}. By choosing M sufficiently large depending on α, β, we can ensure that

\frac{1 + log(M/(M − 1))/ log 2}{α} ≤ \frac{1}{α − β} .

Thus (13) holds in either case if A + 1 ≥ (α − β)^{−1}, which was assumed in the theorem. This completes the induction to prove (7). Let λ be an eigenvalue of Reg_{G/Γ}^{∘}(μ). We want to show that

|λ| < 1 − C_{1}^{−1}B · log^{−A}[G : Γ].

Denote by π an irreducible representation of G/Γ that contains an eigenvector corresponding to λ. Without loss of generality, we can assume that Γ = Ker(π). From quasirandomness and (7) we get

λ^{l_{Γ}} ≤ \frac{M}{c_{1}[G : Γ]^{α}} .

Thus

log |λ| ≤ \frac{log M/c_{1} − α log[G : Γ]}{l_{Γ}}.

If we compare this with the definition of l_{Γ} we can conclude the theorem.

2.2 Some remarks about weakening the hypothesis on quasirandomness

In this section we present some ideas that lead to a refined version of (9) and (10). Using this, one could obtain a version of Theorem 3 with a weaker hypothesis instead of quasirandomness. Namely one would require that the quotient groups does not have “many” irreducible representations with “small” dimension. This weaker form of quasirandomness would be very technical hence we do not state a theorem. However, (based on analogy with compact Lie groups) it seems possible that these ideas lead to better bounds for the groups SL_{d}(Z_{p}) than Theorem 3.

Proposition 8. Let G be a finite group and N a normal subgroup. Let ρ_{1}, …, ρ_{n} be all irreducible representations of N up to isomorphism. Denote by a(ρ_{j}) the number of G-conjugates of ρ_{j}. Denote by d(ρ_{j}) the smallest possible dimension of a representation of G whose restriction to N contains ρ_{j}. Let μ be a symmetric probability measure on G and suppose that

χ_{G/N} (μ^{∗(2l)}) ≤ M  (14)

for some numbers l and M > 1. Then for all integers l′ > l we have:

χ_{G} (μ^{∗(2l′)}) ≤ ∑_{j=1}^{n} [dim(ρ_{j})^{2}M · (\frac{a(ρ_{j}) dim(ρ_{j})^{2}M}{d(ρ_{j})} )^{(l′−l)/l}] .  (15)

Observe that ∑ dim(ρ_{j})^{2} = |N| and a(ρ_{j}) dim(ρ_{j})^{2} ≤ |N|, hence we obtain (9) combined with (10), if we estimate d(ρ_{j}) using quasirandomness. If d(ρ_{j}) is small only for a very few j, Proposition 8 significantly improves the argument given in the previous section.

Proof. We recall some facts from representation theory. Let π be an irreducible representation of G, and denote by χ_{π} its character. Denote by π|_{N} the restriction of π to N. By Clifford’s theorem, the irreducible components of π|_{N} is a G-conjugacy class of representations and each appears with the same multiplicity. We denote by a(π) the number of different irreducible components of π|_{N}, by b(π) their common multiplicity and by c(π) their common dimension. Thus dim(π) = a(π) · b(π) · c(π). Denote one of the irreducible components of π|_{N} by ρ and its character by χ_{ρ}. Let ρ^{g_{1}}, ⋯, ρ^{g_{a(π)}} be all G-conjugates of ρ. In what follows, the function

φ = ∑_{i=1}^{a(π)} χ_{ρ^{g_{i}}}

will play an important role. We also extend it to G by setting it 0 in the complement of N, i.e. we write φ̃(g) = φ(g) for g ∈ N and φ̃(g) = 0 otherwise. We use two inner products, one on L^{2}(G) and one on L^{2}(N) defined by:

⟨f_{1}, f_{2}⟩_{G} = \frac{1}{|G|} ∑_{g∈G} f_{1}(g)f_{2}(g), ⟨f_{1}, f_{2}⟩_{N} = \frac{1}{|N|} ∑_{g∈N} f_{1}(g)f_{2}(g).

These are the inner products with respect to which the irreducible characters of the corresponding groups are orthonormal. We write:

⟨χ_{π}, φ̃⟩_{G} = \frac{|N|}{|G|}⟨χ_{π|_{N}} , φ⟩_{N} = \frac{|N|a(π)b(π)}{|G|}.

A similar calculation shows that the inner product of φ̃ with an irreducible character of G is always non-negative.

Since φ̃ is a class function on G, it can be decomposed as a linear combination of irreducible characters. According to the above calculation, the coefficient of χ_{π} is |N|a(π)b(π)/|G| and all other characters have non-negative contribution. Thus

χ_{π} (μ^{∗(2l)}) ≤ \frac{|G|}{|N|a(π)b(π)}φ̃ (μ^{∗(2l)}) .  (16)

(Note that χ_{π}(μ^{∗(2l)}) ≥ 0 being the trace of a positive operator.) On the other hand,

∥φ̃∥_{∞} ≤ ∑_{i=1}^{a(π)} ∥χ_{ρ^{g_{i}}} ∥_{∞} = a(π)c(π).

Thus for every g ∈ G, we have

|φ̃(g)| ≤ \frac{|N|a(π)c(π)}{|G|}χ_{G/N}(g).

(Note that for g ∉ N both sides are 0.) Therefore

φ̃ (μ^{∗(2l)}) ≤ \frac{|N|a(π)c(π)}{|G|}χ_{G/N} (μ^{∗(2l)}) .  (17)

We combine (16) and (17) and get

χ_{π} (μ^{∗(2l)}) ≤ \frac{c(π)}{b(π)}χ_{G/N} (μ^{∗(2l)}) .

This implies that for all eigenvalues λ of π(μ^{∗(2l)}), we have

|λ| < \frac{c(π)}{b(π)}M = \frac{a(π)c(π)^{2}}{dim(π)} M.  (18)

(Here we also used the hypothesis (14).) Now let π_{1}, π_{2}, …, π_{k} denote all the irreducible representations (up to isomorphism) of G whose restriction to N contain ρ. By a calculation very similar to the one leading to (16) we get

∑_{i=1}^{k} \frac{|N|a(π_{i})b(π_{i})}{|G|}χ_{π_{i}} (μ^{∗(2l)}) ≤ φ̃ (μ^{∗(2l)}) .

Combining with (17), we get

∑_{i=1}^{k} \frac{b(π_{i})}{c(π_{i})}χ_{π_{i}} (μ^{∗(2l)}) ≤ χ_{G/N} (μ^{∗(2l)}) ≤ M.

Documenta Mathematica 18 (2013) 1137–1175

(We used again the hypothesis (14).) Multiplying by a(π)c(π)^{2} = a(π_{i})c(π_{i})^{2} (which is independent of i) we get

∑_{i=1}^{k} dim(π_{i})χ_{π_{i}} (μ^{∗(2l)}) ≤ a(π)c(π)^{2}M.  (19)

We use (18) and write for an integer l′ ≥ l:

∑_{i=1}^{k} dim(π_{i})χ_{π_{i}} (μ^{∗(2l′)}) ≤ a(π)c(π)^{2}M (\frac{a(π)c(π)^{2}M}{dim(π)} )^{(l′−l)/l} .  (20)

We sum (20) for ρ = ρ_{1}, …, ρ_{n} and get (15).

2.3 Proof of Corollary 4

We first discuss quasirandomness. This was already proved for SL_{d}(Ẑ) by Bourgain and Varjú [9]. In fact, it is easy to deduce it from the corresponding result about SL_{d}(Z_{p}) which was obtained by Bourgain and Gamburd [4, Lemma 7.1] for d = 2 and by Saxcé [33, Lemme 5.1] for d ≥ 2. For completeness, we explain this deduction. For an integer q > 0 denote by

Γ_{q} = {g ∈ SL_{d}(Ẑ) : g ≡ 1 (mod q)}

the mod q congruence subgroup of SL_{d}(Ẑ). Let p be a prime, k ≥ 1 be an integer, and let π be a representation of SL_{d}(Ẑ)/Γ_{p^{k}} which is not a representation of SL_{d}(Ẑ)/Γ_{p^{k−1}}. By [33, Lemme 5.1], π is of dimension at least

c · [SL_{d}(Ẑ) : Γ_{p^{k}}]^{1/(d+1)},

where c > 0 is a number depending on d. For any ε > 0, we can replace this bound by |SL_{d}(Ẑ)/Γ_{q}|^{1/(d+1)−ε} if p is sufficiently large depending on ε. Let π be an irreducible unitary representation of SL_{d}(Ẑ). Since Γ_{q}, q > 1 form a system of neighborhoods of 1 in SL_{d}(Ẑ), there is q such that Ker(π) ⊃ Γ_{q}. Let q be minimal with this property. Let q = p_{1}^{k_{1}} ⋯ p_{n}^{k_{n}} such that p_{i} are primes. Then

SL_{d}(Ẑ)/Γ_{q} = (SL_{d}(Ẑ)/Γ_{p_{1}^{k_{1}}} ) × ⋯ × (SL_{d}(Ẑ)/Γ_{p_{n}^{kn}} ) .

Any representation of this group is a tensor product of representations of SL_{d}(Ẑ)/Γ_{p_{i}^{k_{i}}}. Hence

dim π ≥ c^{m}[SL_{d}(Ẑ) : Γ_{p^{k}}]^{1/(d+1)−ε},  (21)

where m is the number of not large enough primes in the sense of the previous paragraph. Thus SL_{d}(Ẑ) is (c^{m}, 1/(d + 1) − ε)-quasirandom.

We refer the interested reader to the paper of Kelmer and Silberman [25, Section 4], where quasirandomness is proved with optimal parameter α for some other arithmetic groups. We define Ω_{1} and Ω_{2}. We fix an integer M that we will set later depending on d. Let Γ ◁ SL_{d}(Ẑ) be a finite index normal subgroup. Denote by q the smallest integer such that Γ_{q} ◁ Γ. We put Γ in Ω_{1}, if q has at least M + 1 prime factors (taking multiplicities into account) and q is sufficiently large. We put Γ in Ω_{2} otherwise. Let Γ ∈ Ω_{1} and let q be the same as above. Let p|q be the smallest prime divisor of q. By simple calculation:

[Γ_{q/p} : Γ_{q}] ≤ [SL_{d}(Ẑ) : Γ_{q/p}]^{1/M}.

Now we define Γ′ := Γ_{q/p}Γ. Clearly

[Γ′ : Γ] ≤ [Γ_{q/p} : Γ_{q}],

so we only need to estimate [SL_{d}(Ẑ) : Γ′] in terms of [SL_{d}(Ẑ) : Γ_{q/p}]. For our purposes the very crude bound

[SL_{d}(Ẑ) : Γ′] ≥ c^{m}[SL_{d}(Ẑ) : Γ_{q/p}]^{1/(d+1)−ε}

is sufficient which follows from (21). This implies

[Γ′ : Γ] ≤ [SL_{d}(Ẑ) : Γ′]^{(d+2)/M}

if q is sufficiently large (and ε is sufficiently small). We choose α and β in such a way that β < α < 1/(d + 1). Then the quasirandomness is satisfied, and also (5) if we set M ≥ (d + 2)/β. It is left to verify (6) for μ = μ_{S}. First we note that by the same argument as at the beginning of the proof of Theorem 3, we can assume that S is symmetric. We show that the groups SL_{d}(Ẑ)/Γ_{q} for Γ_{q} ∈ Ω_{2} have poly-logarithmic diameter with respect to any generating set S. In light of Lemma 1 this implies (6). Let now Γ_{q} ∈ Ω_{2}. There are two possibilities. If q is small (e.g. q ≤ C_{1} or as in the definition of Ω_{1}), then we have the trivial bound

diam(SL_{d}(Ẑ)/Γ_{q}, S) ≤ |SL_{d}(Ẑ)/Γ_{q}| ≤ C log^{A}(SL_{d}(Ẑ)/Γ_{q})

for some suitably large constant C. The other situation that may happen is that q contains at most M prime factors counting multiplicities. In this case we can easily deduce the poly-log diameter bound from [11, Theorem 7.1] and [30, Theorem 2] which contain this result in the case when q is prime. This deduction is very similar to [9, Proof of Proposition 3]. Let q_{0} = 1, q_{1}, q_{2}, …, q_{n} = q be a sequence of integers such that q_{i+1}/q_{i} is a prime number for all i. We will apply the following lemma repeatedly to prove the diameter bound we are looking for.

Lemma 9. Fix i and write p = q_{i}/q_{i−1}. Then

diam(SL_{d}(Z/q_{i}Z), S) ≤ C(diam(SL_{d}(Z/q_{i−1}Z), S) + diam(SL_{d}(Z/pZ), S)),

where C is a number depending on d.

Proof. Let

D = max{diam(SL_{d}(Z/q_{i−1}Z), S), diam(SL_{d}(Z/pZ), S)}.

Then

S^{D} · Γ_{q_{i−1}} = SL_{d}(Z/q_{i}Z).

Since S is generating, S^{D+1} must intersect some Γ_{q_{i−1}}-coset in at least two points. Thus there is

1 ≠ g_{0} ∈ S^{2D+1} ∩ Γ_{q_{i−1}}.

If p ∤ q_{i−1}, and hence Γ_{q_{i−1}}/Γ_{q_{i}} = SL_{d}(Z/pZ), we also want to show that g_{0} can be taken non-central in SL_{d}(Z/pZ). With the same argument as above, we can show that S^{(j+1)D+j} intersects all Γ_{q_{i−1}}-cosets in at least j + 1 points. Taking j = |Z(SL_{d}(Z/pZ))|, we can find a suitable g_{0} in S^{(j+1)D+j}. We put

X = {g^{−1}g_{0}g, g^{−1}g_{0}^{−1}g : g ∈ S^{D}}.

We show that

X^{C} = Γ_{q_{i−1}}/Γ_{q_{i}}  (22)

for some constant C depending on d. We have two cases. First, we suppose that p ∤ q_{i−1}. Then Γ_{q_{i−1}}/Γ_{q_{i}} = SL_{d}(Z/pZ), and X is a non-trivial conjugacy class. In this case (22) is a result of Lev [27, Theorem 2]. Now suppose that p|q_{i−1}. In this case Γ_{q_{i−1}}/Γ_{q_{i}} is isomorphic to 𝔰𝔩_{d}(Z/pZ), and the conjugation action

h ↦ g^{−1}hg, g ∈ SL_{d}(Z/q_{i}Z), h ∈ Γ_{q_{i−1}}/Γ_{q_{i}}

factors through G/Γ_{p} = SL_{d}(Z/pZ). Now the claim (22) follows from [9, Lemma 5]. Therefore, we have S^{C·D} ⊃ Γ_{q_{i−1}}/Γ_{q_{i}} for some other constant C depending on d. This implies S^{(C+1)·D} = SL_{d}(Z/q_{i}Z) which was to be proved.

Now Corollary 4 is immediate. By [11, Theorem 7.1] and [30, Theorem 2] we have

diam(SL_{d}(Z/pZ), S) ≤ C log^{A}(p)

for all primes p. We can use Lemma 9 repeatedly to show

diam(SL_{d}(Ẑ)/Γ_{q}, S) ≤ C log^{A}(p)

for Γ_{q} ∈ Ω_{2}, where p is the largest prime factor of q and C is a different constant depending on M. This is precisely the poly-log diameter estimate we were looking for.

3 Compact Lie groups

The purpose of this section is to prove Theorem 6. Recall the definitions of T, LT, LT^{∗}, I, I^{∗}, R, R_{+}, K and π_{v} from Section 1. Let μ be a probability measure on G. Denote by χ_{v} the character of π_{v}. For a continuous function f and a measure ν on G, we write

f(ν) = ∫ f(x) dν(x).

If f is a continuous class function on G, then by the Peter-Weyl theorem, we can decompose it as a linear combination of irreducible characters. Denote by m_{v}(f) the coefficient of χ_{v} in this decomposition. We introduce two partial orders on the space of continuous class functions on G. We write f_{1} ≤ f_{2}, if f_{1}(g) ≤ f_{2}(g) for every g ∈ G. We write f_{1} ⊑ f_{2} if m_{v}(f_{1}) ≤ m_{v}(f_{2}) for all v ∈ \overline{K} ∩ I^{∗}. Denote by ⪯ the transitive closure of the union of ≤ and ⊑, i.e. we write f_{1} ⪯ f_{2} if there is a sequence of class functions φ_{i} such that

f_{1} ≤ φ_{1} ⊑ φ_{2} ≤ φ_{3} ⊑ … ≤ φ_{n} ⊑ f_{2}.

These relations have a crucial property contained in the following Lemma. Recall that for a measure ν on G, we define the measure ν̃ by

∫ f(x) dν̃(x) = ∫ f(x^{−1}) dν(x)

for all continuous functions f. We say that ν is symmetric if ν = ν̃.

Lemma 10. Let ν be a symmetric probability measure and let f_{1} ⪯ f_{2} be two continuous class functions on G. Then

f_{1}(ν ∗ ν) ≤ f_{2}(ν ∗ ν).

Proof. Clearly, it is enough to prove the statements for ≤ and ⊑ in place of ⪯. For ≤ it easily follows from the definitions and from the fact that ν ∗ ν is a positive measure. Suppose f_{1} ⊑ f_{2}. Observe that

f_{i}(ν ∗ ν) = ∑_{v∈\overline{K}∩I^{∗}} m_{v}(f_{i})χ_{v}(ν ∗ ν).

Hence the claim follows from m_{v}(f_{1}) ≤ m_{v}(f_{2}) once we prove that χ_{v}(ν ∗ν) ≥ 0 for all v. This follows from χ_{v}(ν ∗ ν) = Tr(π_{v}(ν ∗ ν)) and from the fact that π_{v}(ν ∗ ν) = π_{v}(ν) · π_{v}(ν)^{∗} is a positive selfadjoint operator.

Now we explain the strategy of the proof. First of all, we note that by the argument at the beginning of Section 2.1 we can assume that μ is symmetric. Hence Lemma 10 applies for ν = μ^{∗(2l)} for all positive integers l.

We write for r ≥ 1

χ_{r} = ( ∑_{|v|≤r} χ_{v})^{2} · r^{− dim LT}

which plays the role of χ_{G/Γ} used in the previous section. We also write

l_{r} = 2⌊C_{r} log^{A+1} r⌋,

where

C_{r} = C_{0} (10 − log^{−1/10}(r))

and C_{0} is a suitably large constant to be set later. Our goal is to prove the inequality

χ_{r} (μ^{∗(l_{r})}) ≤ E  (23)

for some constant E independent of r. This will easily imply the theorem. We assume that (23) holds for some range 1 ≤ r ≤ r_{1}. (This can be verified easily for r_{1} = r_{0} if C_{0} is suitably large in terms of gap_{r_{0}}(μ).) And then we show that (23) also holds for a suitable r = r_{2}. Iterating this argument, we can prove the claim for all r. We prove the “induction step” in the following way. We find suitable functions φ_{1}, …, φ_{n} such that

χ_{r_{2}} ⊑ φ_{1} + … + φ_{n}.

Then it will be enough to estimate φ_{i}(μ^{∗(l_{r_{2}} )}). We will show that φ_{i} ⪯ B_{i}χ_{r_{1}}, where B_{i} is a number depending on i, r_{1} and r_{2}. This allows us to estimate φ_{i}(μ^{∗(l_{r_{1}} )}). We will also show that m_{v}(φ_{i}) is either “large” or 0, and this will yield an estimate on the eigenvalues of π_{v}(μ^{∗(l_{r_{1}} )}) for all v which contributes to φ_{i}. Finally this allows us to get a refined estimate on φ_{i}(μ^{∗(l_{r_{2}} )}). To implement the above plan we need methods to estimate m_{v}(f). In our examples f will always be the character of a representation which is obtained from other representations using tensor products. Explicit formulas are available for m_{v}(f) in such cases, however, they do not seem very practical for our purposes. Instead, we will use elementary methods to estimate these coefficients based on double-counting dimensions. However, we still need some very basic facts about the representations π_{v}. The first fact is Weyl’s dimension formula [12, Chapter VI. (1.7) (iv)]:

dim π_{v} = ∏_{u∈R_{+}} \frac{⟨u, v + ρ⟩}{⟨u, ρ⟩},

where

ρ = \frac{1}{2} ∑_{u∈R_{+}} u

is the half sum of the positive roots. The second fact is the content of the following lemma which bounds the highest weight of possible irreducible constituents of π_{v} ⊗ π_{u}. Recall that we denote the Haar measure on G by m_{G}.

Lemma 11. There is a constant D depending only on G such that if

∫ χ_{v}χ_{u}\overline{χ_{w}} dm_{G} ≠ 0  (24)

for some v, u, w ∈ \overline{K} ∩ I^{∗}, then |v − w| < D|u|.

Proof. If (24) holds then π_{w} is contained in π_{v} ⊗ π_{u}. By [12, Chapter VI, Lemma (2.8)], v + u dominates w that is

⟨v + u, t⟩ ≥ ⟨w, t⟩

for every t ∈ \overline{K}. Similarly, if (24) holds then π_{v} is contained in π_{w} ⊗ \overline{π_{u}}, hence

⟨w + \overline{u}, t⟩ ≥ ⟨v, t⟩.

Here \overline{u} is the highest weight of \overline{χ_{u}}. Now let t_{1}, …, t_{dim T} be a basis of LT^{∗} consisting of unit vectors in \overline{K}. By the above inequalities, we have

|⟨w − v, t_{j}⟩| ≤ |u|

for all 1 ≤ j ≤ dim T. The claim follows from this with the constant D equal to the length of the longest vector in the set

{x ∈ LT^{∗} : |⟨x, t_{j}⟩| ≤ 1}.

We proceed by some Lemmata which bound the multiplicities of some irreducible constituents in certain tensor products.

Lemma 12. We have

∫ ( ∑_{|v|≤r} χ_{v})^{2} dm_{G} = |\{v ∈ \overline{K} ∩ I^{∗} : |v| ≤ r\}|.

In particular

c ≤ m_{χ_{0}}(χ_{r}) ≤ C,

where c, C > 0 are constants depending on G Proof. Since characters form an orthonormal basis, we have

∫ ( ∑_{|v|≤r} χ_{v})^{2} dm_{G} = ∫ ∑_{|v|≤r} χ_{v}\overline{χ_{v}} dm_{G} = |\{v ∈ \overline{K} ∩ I^{∗} : |v| ≤ r\}|.

For the second statement notice that

m_{χ_{0}}(χ_{r}) = \frac{1}{r^{dim LT}} ∫ ( ∑_{|v|≤r} χ_{v})^{2} χ_{0} dm_{G} = \frac{|\{v ∈ \overline{K} ∩ I^{∗} : |v| ≤ r\}|}{r^{dim LT}}.

Lemma 13. There is a constant C > 0 depending on G such that the following holds. Let u ∈ \overline{K} ∩ I^{∗}, and r ≥ 1.

m_{χ_{u}}(χ_{r}) ≤ C dim χ_{u}.

Moreover, m_{χ_{u}}(χ_{r}) = 0 if |u| > Cr.

Proof. For the first part of the lemma we write

r^{dim LT} m_{χ_{u}}(χ_{r}) = ∫ ( ∑_{|v|≤r} χ_{v})^{2} \overline{χ_{u}} dm_{G}

≤ 2 ∑_{\begin{matrix}|v|,|w|≤r \\ dim χ_{v}≤dim χ_{w} \end{matrix}} ∫ χ_{v}χ_{w}\overline{χ_{u}} dm_{G}

= 2 ∑_{|v|≤r} [  ∑_{\begin{matrix}|w|≤r \\ dim χ_{w}≥dim χ_{v} \end{matrix}} m\overline{χ_{w}}(χ_{v}\overline{χ_{u}})] .

The sum of the multiplicities of some irreducible components of π_{v} ⊗ \overline{π_{u}} can not be bigger than the dimension of π_{v} ⊗ \overline{π_{u}} divided by the minimal dimension of the irreducible components we consider. Thus

r^{dim LT} m_{χ_{u}}(χ_{r}) ≤ 2 ∑_{|v|≤r} \frac{dim(χ_{v}\overline{χ_{u}})}{dim(χ_{v})} ≤ Cr^{dim LT} dim χ_{u}.

The second part follows immediately from Lemma 11.

For u ∈ \overline{K} ∩ I^{∗} and r ≥ 1, we write

ψ_{u,r} = χ_{r} · ∑_{w:|u−w|<3Dr} χ_{w}.

We show that χ_{z} is contained in ψ_{u,r} with high multiplicity if |u − z| ≤ Dr.

Lemma 14. Let r ≥ 1 and z, u ∈ \overline{K} ∩ I^{∗} with |z − u| ≤ Dr. Then

m_{χ_{z}}(ψ_{u,r}) ≥ c · \frac{dim(χ_{z}) · r^{dim G}}{max_{w:|u−w|<3Dr}\{dim(χ_{w})\}},

where c > 0 is a constant depending only on G.

Proof. We can write

r^{dim LT} m_{χ_{z}}(ψ_{u,r}) = ∑_{w:|u−w|<3Dr} [ ∑_{|v_{1}|,|v_{2}|≤r} ∫ χ_{v_{1}}χ_{v_{2}}χ_{w}\overline{χ_{z}} dm_{G}]

= ∑_{w:|u−w|<3Dr} m_{χ_{w}} ( ∑_{|v_{1}|,|v_{2}|≤r} \overline{χ_{v_{1}}} \overline{χ_{v_{2}}}χ_{z})

≥ \frac{∑_{|v_{1}|,|v_{2}|≤r} dim χ_{v_{1}} · dim χ_{v_{2}} · dim χ_{z}}{max_{w:|u−w|<3Dr} dim χ_{w}} .  (25)

In the last line we used the fact that all irreducible components of \overline{χ_{v_{1}}} \overline{χ_{v_{2}}}χ_{z} has highest weight w satisfying |w − z| ≤ 2Dr and hence |u − w| < 3Dr which follows from two applications of Lemma 11. Hence all possible irreducible component appears in the range of summation, and the inequality follows by comparing dimensions. Let K′ be a closed convex cone strictly contained in the positive Weyl chamber K. For v ∈ K′ ∩ I^{∗} and |v| ≥ r/2 it follows from Weyl’s dimension formula that dim(χ_{v}) ≥ cr^{|R_{+}|} for some constant c > 0 depending only on G, K′. Thus the numerator in (25) is bounded below by

c dim(χ_{z}) · r^{2 dim LT +2|R_{+}|}.

The proof is finished by noting that dim G = dim LT + 2|R_{+}|.

We continue implementing our plan described above. Recall that r_{2} > r_{1} ≥ 1, are numbers that we will choose later and that we assume

χ_{r} (μ^{∗(l_{r})}) ≤ E  (26)

for r ≤ r_{1} and for some number E to be chosen later, as well. Our goal is to prove (26) with r = r_{2}. Let u_{0} = 0, u_{1}, … u_{m} be a maximal Dr_{1} separated subset of \{v ∈ \overline{K} ∩I^{∗} : |v| ≤ Cr_{2}}, where C is the constant from Lemma 13. For i = 0, …, m, let

M_{i} = \frac{C max_{w:|u_{i}−w|<3Dr_{1}}\{dim χ_{w}\}}{cr_{1}^{dim G}},

where c is the constant from Lemma 14 and C is as above. Write

φ_{i} = M_{i} ∑_{w:|u_{i}−w|<Dr_{1}} m_{χ_{w}}(ψ_{u_{i},r_{1}})χ_{w},

Documenta Mathematica 18 (2013) 1137–1175

i.e. we removed from ψ_{u_{i},r_{1}} those irreducible components whose multiplicities we cannot bound below. Hence m_{χ_{w}}(φ_{i}) ≥ C · dim(χ_{w}) if |w − u_{i}| < Dr_{1} by Lemma 14 (applied with r = r_{1}). It follows from Lemma 13 (applied with r = r_{2}) that

χ_{r_{2}} ⊑ ∑_{i=0}^{m} φ_{i}.

Moreover, we have

φ_{i} ⊑ M_{i}ψ_{u_{i},r_{1}} ≤ [M_{i} ∑_{w:|u_{i}−w|<3Dr_{1}} dim(χ_{w})] · χ_{r_{1}},

because χ_{r_{1}} is non-negative, and

∑_{w:|u_{i}−w|<3Dr_{1}} χ_{w}(g) ≤ ∑_{w:|u_{i}−w|<3Dr_{1}} dim χ_{w}

for every g ∈ G. Clearly

∑_{w:|u_{i}−w|<3Dr_{1}} dim χ_{w} ≤ Cr_{1}^{dim LT} max_{w:|u_{i}−w|<3Dr_{1}}{dim χ_{w}},

hence

φ_{i} ⪯ C \frac{(max_{w:|u_{i}−w|<3Dr_{1}}\{dim χ_{w}\})^{2}}{r_{1}^{2|R_{+}|}} · χ_{r_{1}}.  (27)

Denote by N_{i} the number of positive roots v ∈ R_{+} such that ⟨u_{i}, v⟩ ≤ 4Dr_{1}|v|. Then it follows from Weyl’s dimension formula that

max_{w:|u_{i}−w|<3Dr_{1}} dim χ_{w} ≤ Cr_{1}^{N_{i}} min_{w:|u_{i}−w|<3Dr_{1}} dim χ_{w}.  (28)

After these preparations, we can give an estimate on φ_{i}(μ^{∗(l_{r_{2}} )}). This is done in the next two Lemmata.

Lemma 15. Fix 0 ≤ i ≤ m such that N_{i} < |R_{+}|. If r_{1} is sufficiently large and

log^{1/3} r_{1} ≤ log r_{2} − log r_{1} ≤ log^{1/2} r_{1},

then

φ_{i} (μ^{∗(l_{r_{2}} )}) ≤ (\frac{r_{1}}{r_{2}} )^{(A−1)(|R_{+}|−N_{i})} .

Recall that the value of A is given in the statement of Theorem 6 and it also appears in the definition of l_{r} above.

Proof. For notational simplicity, write

X = max_{w:|u_{i}−w|<3Dr_{1}} dim χ_{w},

and note that by Weyl’s dimension formula, we have

X ≤ Cr_{1}^{N_{i}}r_{2}^{|R_{+}|−N_{i}}.  (29)

By (27), the induction hypothesis and Lemma 10, we have

φ_{i} (μ^{∗(l_{r_{1}} )}) ≤ CE \frac{X^{2}}{r_{1}^{2|R_{+}|}} .  (30)

Denote by λ_{max} the maximum of the absolute values of the eigenvalues of the operators π_{v}(μ) for |v − u_{i}| ≤ Dr_{1}, i.e. for the irreducible characters contained in φ_{i}. Clearly

λ_{max}^{l_{r_{1}}} ≤ CE \frac{X^{2}}{r_{1}^{2|R_{+}|}m_{χ_{v}}(φ_{i})},  (31)

where χ_{v} is the character of the representation, which contains λ_{max}. Recall that by Lemma 14 and the definition of φ_{i}, we have

m_{χ_{v}}(φ_{i}) ≥ c dim χ_{v}.

If we combine this with (28) and (31), we get

λ_{max}^{l_{r_{1}}} ≤ CE \frac{X}{r_{1}^{2|R_{+}|−N_{i}}} ≤ CE \frac{r_{2}^{|R_{+}|−N_{i}}}{r_{1}^{2|R_{+}|−2N_{i}}} .  (32)

(For the second inequality we used (29).) By (30), we clearly have

φ_{i} (μ^{∗(l_{r_{2}} )}) ≤ CE \frac{X^{2}}{r_{1}^{2|R_{+}|}} · λ_{max}^{l_{r_{2}} −l_{r_{1}}}

≤ CE \frac{r_{2}^{2|R_{+}|−2N_{i}}}{r_{1}^{2|R_{+}|−2N_{i}}} · (CE \frac{r_{2}^{|R_{+}|−N_{i}}}{r_{1}^{2|R_{+}|−2N_{i}}} )^{\frac{lr_{2} −lr_{1}}{lr_{1}}} .  (33)

By a computation very similar to (12), we get

\frac{l_{r_{2}} − l_{r_{1}}}{l_{r_{1}}} ≥ (A + 1 + \frac{c}{log^{1/10} r_{1}} ) \frac{log r_{2} − log r_{1}}{log r_{1}} ,  (34)

where c is an absolute constant. Now we write

(log r_{2} − 2 log r_{1})\frac{log r_{2} − log r_{1}}{log r_{1}} = (log r_{1} − log r_{2}) (1 − \frac{log r_{2} − log r_{1}}{log r_{1}} ) . (35)

Documenta Mathematica 18 (2013) 1137–1175

and

(A + 1 + \frac{c}{log^{1/10} r_{1}} ) (1 − \frac{log r_{2} − log r_{1}}{log r_{1}} ) ≥ A + 1 + \frac{c}{2 log^{1/10} r_{1}} (36)

which follows from our assumption log r_{2} − log r_{1} ≤ log^{1/2} r_{1}. Combining (34), (35) and (36) we get

(\frac{r_{2}^{|R_{+}|−N_{i}}}{r_{1}^{2|R_{+}|−2N_{i}}} )^{\frac{lr_{2} −lr_{1}}{lr_{1}}} ≤ (\frac{r_{1}}{r_{2}} )^{(A+1)(|R_{+}|−N_{i})+c·log^{−1/10} r_{1}} .

If we plug this into (33), we get

φ_{i} (μ^{∗(l_{r_{2}} )}) ≤ (\frac{r_{1}}{r_{2}} )^{(A−1)(|R_{+}|−N_{i})+c·log^{−1/10} r_{1}} (CE)^{l_{r_{2}} /l_{r_{1}}} .

Finally we note that by log r_{2} − log r_{1} ≥ log^{1/3} r_{1}, we have

(\frac{r_{2}}{r_{1}} )^{c/ log^{1/10} r_{1}} ≥ e^{c log^{7/30} r_{1}} ≥ (CE)^{2}

if r_{1} is sufficiently large depending on G and E. On the other hand, by the computation leading to (34), we have l_{r_{2}}/l_{r_{1}} < 2. This finishes the proof.

Lemma 16. Fix 0 ≤ i ≤ m such that N_{i} = |R_{+}|. If log r_{2} − log r_{1} > log^{1/3} r_{1} and r_{1} is sufficiently large then

φ_{i}(μ^{∗(l_{r_{2}} )}) < C,

where C is a constant depending only on G (and not on E).

Proof. Let v ∈ \overline{K} ∩ I^{∗}, such that m_{χ_{v}}(φ_{i}) > 0. By Weyl’s formula, we have dim(χ_{v}) ≤ Cr_{1}^{|R_{+}|}, since N_{i} = |R_{+}|. Let λ be an eigenvalue of π_{v}(μ). Then by (31) we get

λ^{l_{r_{1}}} ≤ \frac{CE}{dim χ_{v}} .

In fact, we can get a better bound if |v| ≤ r_{1}. By a similar argument and using the induction hypothesis for r = |v| ≤ r_{1}, we get

λ^{l_{|v|}} ≤ \frac{CE}{dim χ_{v}} .

Weyl’s dimension formula gives dim χ_{v} ≥ c|v|, and an easy calculation shows that

λ^{l_{r_{1}}} ≤ (\frac{CE}{|v|} )^{l_{r_{1}} /l_{|v|}} ≤ \frac{CE}{r_{1}}  (37)

if |v| is sufficiently large (depending on G and E). We suppose that r_{0} is so large that |v| < r_{0} for those v which are too small for the above argument. We set C_{0} > gap_{r_{0}}^{−1}(G, μ), hence for r_{0} ≥ |v| ≠ 0 we have

λ^{l_{r_{1}}} ≤ e^{−gap_{r_{0}} (G,μ)l_{r_{1}}} ≤ e^{− log^{A+1}(r_{1})},

which is stronger than (37). By (27), the induction hypothesis and Lemma 10, we have

φ_{i} (μ^{∗(l_{r_{1}} )}) ≤ CE,

hence

φ_{i} (μ^{∗(l_{r_{1}} )}) ≤ m_{χ_{0}}(φ_{i}) + CE (\frac{CE}{r_{1}} )^{\frac{lr_{2} −lr_{1}}{lr_{1}}} .

Since log r_{2} − log r_{1} > log^{1/3} r_{1} and

\frac{l_{r_{2}} − l_{r_{1}}}{l_{r_{1}}} > c\frac{log r_{2} − log r_{1}}{log r_{1}}

we easily get

φ_{i} (μ^{∗(l_{r_{1}} )}) ≤ m_{χ_{0}}(φ_{i}) + 1

if r_{1} is sufficiently large (depending on G and E) which was to be proved.

It is left to estimate the number of u_{i} for which N_{i} takes a particular value. This is done with the help of the next lemma. Denote by S the set of simple roots. (This is not to be confused with the generating set of the random walk, which is denoted by S in other sections.)

Lemma 17. Let S′ ⊊ S be a set of simple roots. Denote by R′ ⊂ R_{+} the set of all positive roots which can be expressed as a combination of elements of S′. We have

\frac{|S| − |S′|}{|R_{+}| − |R′|} ≤ A(G) − 1,

where the value of A(G) is given in Table 1, for simple Lie groups and for non-simple ones it is defined to be A(G) = max{A(H)} where H runs through all simple quotients.

Proof. If the Dynkin diagram of G is not connected, we can write R_{+} = R_{1} ∪ …∪R_{n}, where R_{i} is a system of positive roots in a root system with connected diagram. Clearly

\frac{|S| − |S′|}{|R_{+}| − |R′|} ≤ max_{1≤i≤n} \frac{|S ∩ R_{i}| − |S′ ∩ R_{i}|}{|R_{i}| − |R′ ∩ R_{i}|}.

Hence we can assume without loss of generality that the diagram of G is connected.

Documenta Mathematica 18 (2013) 1137–1175

By a simple calculation, one can verify that |S|/|R_{+}| = A(G) − 1 as given in Table 1. Now notice that R′ is itself (the set of positive roots in) a root system and its diagram is the subgraph spanned by S′ in the diagram of G. Examining Table 1 it is easy to check that

\frac{|S′|}{|R′|} ≥ A(G) − 1 = \frac{|S|}{|R_{+}|}.

(In fact, it is enough to check that the value in the table is never smaller for connected subdiagrams.) Then

\frac{|S| − |S′|}{|R_{+}| − |R′|} ≤ \frac{|S| − |S||R′|/|R_{+}|}{|R_{+}| − |R′|} = \frac{|S|}{|R_{+}|} = A(G) − 1.

Let S′ ⊂ S be a subset of the simple roots. We write Ω(S′) for the set of indices i such that ⟨u_{i}, v⟩ ≤ 4Dr_{1} for v ∈ S if and only if v ∈ S′. We estimate |Ω(S′)|. Since S′ consist of linearly independent vectors, the elements of Ω(S′) are in a Cr_{1} neighborhood of a subspace of LT of dimension |S| − |S′|. Since they are Dr_{1}-separated, we have

|Ω(S′)| ≤ C (\frac{r_{2}}{r_{1}} )^{|S|−|S′|} .  (38)

All positive roots are positive linear combinations of simple roots, hence N_{i} ≤ |R′| for i ∈ Ω(S′), where R′ is the set of positive roots which are combinations of the elements of S′. If S′ ≠ S, then Lemmata 15 and 17 together with (38) gives

∑_{i∈Ω(S′)} φ_{i} (μ^{∗(l_{r_{2}} )}) ≤ C

with a constant C depending on G. If S′ = S, the same follows from Lemma 16. Summing this up for all S′ ⊂ S, we get

∑_{i} φ_{i} (μ^{∗(l_{r_{2}} )}) ≤ C.  (39)

This completes the proof of (26) for r = r_{2} with E = C, where C is the constant in (39). We explain how to set the various parameters and how to complete the induction. We set E = C with the constant C from (39) in the previous paragraph. Then we pick r_{0} to be sufficiently large (depending on E and G) so that all of the above arguments are valid with r_{1} ≥ r_{0}.

For r_{0} ≥ r ≥ 1, we have

χ_{r} (μ^{∗(l_{r})}) ≤ m_{χ_{0}}(χ_{r}) + e^{−l_{r}·gap_{Cr}(G,μ)} · ∑_{0<|v|≤Cr} m_{χ_{v}}(χ_{r})
≤ C + Cr^{−C_{0}·gap_{Cr}(G,μ)} · ∑_{0<|v|≤Cr} dim(χ_{v})
≤ C + Cr^{C(dim LT +|R_{+}|)−C_{0}·gap_{Cr}(G,μ)}.  (40)

Here we first used the definition of gap_{r}(G, μ), then the definition of l_{r} and Lemmata 12 and 13, finally Weyl’s dimension formula. We put C_{0} = C · gap_{Cr_{0}}^{−1}(G, μ), where C is a suitable constant depending on the constant in (40) such that

χ_{r} (μ^{∗(l_{r})}) ≤ E

for 1 ≤ r ≤ r_{0}. (Recall that the only constraint we had for C_{0} above is in the proof of Lemma 16 and it is satisfied with this choice.) Thus we see that (26) hold for 1 ≤ r ≤ r_{0}. Once we know that (26) holds on an interval r ∈ [1, a], we can extend it to r ∈ [1, e^{log(a)+log^{1/2}(a)}]. This follows from the above argument with the choice r_{2} = r and any r_{1} ≤ a which satisfies

log^{1/3} r_{1} ≤ log r_{2} − log r_{1} ≤ log^{1/2} r_{1}.

If we apply this repeatedly, we can conclude that (26) holds for all r ≥ 1. Finally, we conclude the proof of the theorem. Fix r ≥ 1 and suppose that π_{v_{0}} is the representation for which the maximum in the definition of gap_{r}(G, μ) is attained. We use Lemma 14 with z = u = v_{0} and (26) to get

χ_{v_{0}} (μ^{∗(l_{r})}) ≤ C \frac{max_{w:|v_{0}−w|<3Dr}\{dim(χ_{w})\}}{dim(χ_{v_{0}}) · r^{dim G}} · ψ_{v_{0},r} (μ^{∗(l_{r})})
≤ CE \frac{(max_{w:|v_{0}−w|<3Dr}\{dim(χ_{w})\}) · ∑_{w:|v_{0}−w|<3Dr} dim(χ_{w})}{dim(χ_{v_{0}}) · r^{dim G}}.

We evaluate dimensions using Weyl’s formula and get

∥π_{v_{0}} (μ^{∗(l_{r})})∥ ≤ χ_{v_{0}} (μ^{∗(l_{r})}) ≤ CE/ dim(χ_{v_{0}}) ≤ CE/r ≤ r^{−1/2},

if r ≥ r_{0} and r_{0} is sufficiently large, as we may assume. This implies

gap_{r}(G, μ) ≥ (1/10)\frac{log r}{l_{r}} .

Inspecting the definition of l_{r} and the above choice of C_{0}, we see that this is exactly what was to be proved.

4 Some technicalities

We begin this section by proving Corollary 7. First we give a lemma which will be used for reducing the problem to the connected case:

Lemma 18. Let G be a Lie group and let μ be a symmetric probability measure on it such that supp μ generates a dense subgroup and 1 ∈ supp μ. Write G^{∘} for the connected component of G and let n = [G : G^{∘}]. Then supp (μ^{∗(2n−1)}) ∩ G^{∘} generates a dense subgroup of G^{∘}.

Proof. Suppose to the contrary that for some h ∈ G^{∘} and ε > 0 there is no h′ in the group generated by supp (μ^{∗(2n−1)}) ∩ G^{∘} such that dist(h, h′) < ε. On the other hand, by assumption, there is g = g_{1} ⋯ g_{l} with g_{i} ∈ supp (μ) and dist(h, g) < ε. We show that g is in the group generated by supp (μ^{∗(2n−1)}) ∩ G^{∘}, a contradiction. If l ≤ 2n − 1, then by definition, g ∈ supp (μ^{∗(2n−1)}) ∩ G^{∘}. Suppose l > 2n − 1. By the pigeon hole principle, there are i ≤ j ≤ n such that g_{i} ⋯ g_{j} ∈ G^{∘}. We can write g = g′ · g′′, where

g′ = g_{1} ⋯ g_{i−1}g_{i} ⋯ g_{j}g_{i−1}^{−1} ⋯ g_{1}^{−1} and
g′′ = g_{1} ⋯ g_{i−1}g_{j+1} ⋯ g_{l}.

Now clearly g′, g′′ ∈ G^{∘}, and g′ ∈ supp (μ^{∗(2n−1)}), since it is a product of length at most 2n − 1. Since the length of g′′ is strictly less than that of g the proof can be completed by induction.

If G is a compact connected semi-simple Lie group, the space L^{2}(G) can be decomposed as an orthogonal sum of finite dimensional irreducible representations. We write H_{r} ⊂ L^{2}(G) for the sum of those constituents which have highest weight v with |v| ≤ r. In the next lemma we construct an approximate identity in H_{r}.

Lemma 19. Let G be a compact connected semi-simple Lie group. Then for each r, there is a non-negative function f_{r} ∈ H_{r} such that

∫ f_{r} dm_{G} = 1, ∥f_{r}∥_{2} ≤ Cr^{dim G/4} and ∫ f_{r}(g)dist(g, 1)dm_{G}(g) ≤ C/\sqrt{r},

where C is a constant depending on G.

Proof. We fix a maximal torus T ⊂ G. Let π be a faithful (not necessarily irreducible) finite dimensional unitary representation of G with real character χ. We can decompose the representation space as the sum of weight spaces, i.e. there is an orthonormal basis φ_{1}, …, φ_{m} (where m = dim π) such that the following holds. For each φ_{i}, there is a weight u_{j} ∈ I^{∗} such that for the elements g ∈ T we have π(g)φ_{j} = e^{2πi⟨log g,u_{j}⟩}φ_{j}. (Here log : T → LT is a branch of the inverse of the exponential map.) Since χ is real, we have

χ(g) = ∑_{j=1}^{m} e^{2πi⟨log g,u_{j}⟩} = ∑_{j=1}^{m} cos(2π⟨log g, u_{j}⟩).

Since π is faithful, χ(g) < m for g ≠ 1 and we can deduce from the above formula that

m − c_{1}dist(g, 1)^{2} ≤ χ(g) ≤ m − c_{2}dist(g, 1)^{2},  (41)

where c_{1}, c_{2} > 0 are constants depending on G. Denote by r_{0} the length of the highest weight of the irreducible components of π. We define

f_{r}(g) = c_{r}(χ(g) + m)^{⌊r/r_{0}⌋},

where c_{r} is a normalizing constant so that ∫ f_{r}dm_{G} = 1. Observe that f_{r} ∈ H_{r}. By simple calculation based on (41), we get

c\frac{⌊r/r_{0}⌋^{dim G/2}}{(2m)^{⌊r/r_{0}⌋}} ≤ c_{r} ≤ C \frac{⌊r/r_{0}⌋^{dim G/2}}{(2m)^{⌊r/r_{0}⌋}} ,

where c, C > 0 are numbers depending on G. We have

∥f_{r}∥_{∞} = c_{r}(2m)^{⌊r/r_{0}⌋} ≤ Cr^{dim G/2}.

The L^{2} bound now follows from ∥f_{r}∥_{2}^{2} ≤ ∥f_{r}∥_{1}∥f_{r}∥_{∞}. Now using again (41), we get

∫ f_{r}(g)dist(1, g) dm_{G}(g)
≤ c_{r} ∫ (2m − c_{2}dist(g, 1)^{2})^{⌊r/r_{0}⌋}dist(1, g) dm_{G}(g)
≤ C⌊r/r_{0}⌋^{dim G/2} ∫ e^{−c_{3}dist(g,1)^{2}⌊r/r_{0}⌋}dist(1, g) dm_{G}(g)
≤ C⌊r/r_{0}⌋^{dim G/2} ∫_{R^{dim G}} e^{−c_{3}|x|^{2}⌊r/r_{0}⌋}|x| dx
= C⌊r/r_{0}⌋^{−1/2} ∫_{R^{dim G}} e^{−c_{3}|y|^{2}}|y| dy ≤ C/\sqrt{r},

which was to be proved.

Proof of Corollary 7. Write Reg(g)f(h) = f(g^{−1}h) for f ∈ L^{2}(G), which is the left regular representation of G. Assume to the contrary that f ∈ Lip(G), ∫ f = 0, ∥f∥_{2} = 1 and yet

∥∫ Reg(g)f dμ(g)∥_{2} = ∥Reg(μ)f∥_{2} ≥ 1 − c_{0} log^{−A}(∥f∥_{Lip} + 2)  (42)

with a constant c_{0} which will be chosen to be sufficiently small depending on μ. By the same argument as in the beginning of Section 2, we have ∥Reg(μ)f∥_{2}^{2} = ∥Reg(μ̃ ∗ μ)f∥_{2}. Thus (42) holds (with a different c_{0}) for μ replaced by μ̃ ∗ μ, hence we can assume that μ is symmetric and 1 ∈ supp μ.

Write n = [G : G^{∘}] as in Lemma 18. Furthermore, we define μ_{1} to be the probability measure on G^{∘} that we obtain from μ^{∗(2n−1)} by restricting it to G^{∘} and then normalizing it. By Lemma 18, we can apply Theorem 6 for the measure μ_{1}. Now we need to find a suitable test function related to f. First, we want to rule out the possibility that f is “almost constant” on cosets of G^{∘}. It follows from (42) that there is a set X ⊂ G with μ(X) > 1 − ε such that

∥f − Reg(g)f∥_{2} < 1/(10n)  (43)

where ε > 0 is as small as we wish, if we choose c_{0} in (42) sufficiently small. (In fact, we could obtain a much stronger estimate from (42)). In particular, we can ensure that X · G^{∘} generates G/G^{∘}. Since ∫ f dm_{G} = 0,

∫ ⟨Reg(g)f, f⟩ dm_{G}(g) = 0.

Hence there is g ∈ G such that ⟨Reg(g)f, f⟩ ≤ 0, in particular ∥Reg(g)f −f∥_{2} ≥ \sqrt{2}. We can write g = h_{1} ⋯ h_{n}g_{0}, where h_{i} ∈ X and g_{0} ∈ G^{∘}. By the triangle inequality, either

∥Reg(h_{1} ⋯ h_{n}g_{0})f − Reg(h_{1} ⋯ h_{n})f∥_{2} > 1  (44)

or

∥Reg(h_{1} ⋯ h_{j})f − Reg(h_{1} ⋯ h_{j−1})f∥_{2} > (\sqrt{2} − 1)/n  (45)

for some 1 ≤ j ≤ n. Since Reg is unitary, the second case yields ∥Reg(h_{j})f − f∥_{2} > (\sqrt{2} − 1)/n which is a contradiction to (43). Thus only the first case is possible, from which we conclude ∥Reg(g_{0})f − f∥_{2} > 1 again by unitarity. This shows that f can not be “almost constant” on all cosets of G^{∘}. Let x_{1}, …, x_{n} ∈ G be a system of representatives for G^{∘}-cosets. Write f_{i} for the restriction of f to the coset G^{∘} ·x_{i} considered a function on G^{∘}. More formally:

f_{i}(g) = f(gx_{i}) ∈ L^{2}(G^{∘}).

We have

∥Reg(g_{0})f − f∥_{2}^{2} = ∑_{i=1}^{n} ∥Reg(g_{0})f_{i} − f_{i}∥_{2}^{2},

hence there is 1 ≤ i_{0} ≤ n such that ∥Reg(g_{0})f_{i_{0}} − f_{i_{0}}∥_{2} ≥ 1/\sqrt{n}. We define

φ = \frac{f_{i_{0}} − ∫ f_{i_{0}} dm_{G}}{∥f_{i_{0}} − ∫ f_{i_{0}} dm_{G}∥_{2}}

aiming to estimate ∥Reg(μ_{1})φ∥_{2} using Theorem 6. It follows from the above considerations that ∥f_{i_{0}} − ∫ f_{i_{0}} dm_{G}∥_{2} ≥ 1/(2\sqrt{n}). Thus ∥φ∥_{Lip} < 2\sqrt{n}∥f∥_{Lip}. From Lemma 18, we know that supp μ_{1} is not contained in a proper closed subgroup of G^{∘}. Thus we have

gap_{r}(G^{∘}, μ_{1}) > 0

for all r. Then Theorem 6 implies that

gap_{r}(G^{∘}, μ_{1}) > c log^{−A(G)} r

with a constant c > 0 depending on μ. To apply this spectral gap estimate, we need to approximate φ by a function in H_{r} with small r. We use Lemma 19 with r = D(∥φ∥_{Lip} + 2)^{4}; we will chose the sufficiently large number D later. Then the Lemma gives:

∥f_{r} ∗ φ − φ∥_{∞} ≤ ∫ f_{r}(g)dist(g, 1)∥φ∥_{Lip} dm_{G}(g) ≤ \frac{C}{D^{1/2}(∥φ∥_{Lip} + 2)}.

Clearly f_{r} ∗ φ ∈ H_{r}, and moreover

∫ f_{r} ∗ φ dm_{G} = 0.

Thus

∥Reg(μ_{1})φ∥_{2} ≤ ∥Reg(μ_{1})(f_{r} ∗ φ)∥_{2} + \frac{C}{D^{1/2}(∥φ∥_{Lip} + 2)}
≤ 1 − gap_{r}(G^{∘}, μ_{1}) + \frac{C}{D^{1/2}(∥φ∥_{Lip} + 2)}
≤ 1 − c log^{−A(G)}(D^{1/2}(∥φ∥_{Lip} + 2)) + \frac{C}{D^{1/2}(∥φ∥_{Lip} + 2)}.

Now we choose D sufficiently large depending on μ so that for the quantities in the last line we have

c log^{−A(G)}(D^{1/2}(∥φ∥_{Lip} + 2)) ≥ \frac{2C}{D^{1/2}(∥φ∥_{Lip} + 2)}.

This in turn implies with a different constant c:

∥Reg(μ_{1})φ∥_{2} ≤ 1 − c log^{−A(G)}(∥φ∥_{Lip} + 2).

Furthermore, by the definition of φ, we have

∥Reg(μ_{1})f_{i_{0}}∥_{2} ≤ ∥f_{i_{0}}∥_{2} − c log^{−A(G)}(∥f∥_{Lip} + 2).

This yields

∥Reg(μ_{1})f∥_{2} ≤ 1 − c log^{−A(G)}(∥f∥_{Lip} + 2).

By selfadjointness

∥Reg(μ)f∥_{2}^{2n−1} ≤ ∥Reg(μ^{∗(2n−1)})f∥_{2} ≤ 1 − c′(1 − ∥Reg(μ_{1})f∥_{2}),

where c′ = μ^{∗(2n−1)}(G^{∘}) is the normalizing constant in the definition of μ_{1}. This is a contradiction to (42), if we choose there c_{0} to be sufficiently small.

The rest of the section is devoted to the proof of Lemma 5. We start with a Lemma which provides an estimate on the Lipschitz norm of a function in H_{r}.

Lemma 20. Let G be a connected compact semi-simple Lie group and let f ∈ H_{r} with ∥f∥_{2} = 1. Then ∥f∥_{Lip} ≤ Cr^{dim G/2+1}, where C is a constant depending on G.

Proof. We fix a maximal torus T and write

∥f∥_{Lip(T)} = max_{t∈T,g∈G} \{\frac{f(tg) − f(g)}{dist(1, t)}\}

for f ∈ Lip(G). Since every element of G is contained in a maximal torus, it is enough to bound this new semi-norm which a priori could be smaller. As in the proof of Lemma 19, we decompose H_{r} as the sum of weight spaces for T. There is an orthonormal basis φ_{1}, …, φ_{m} ∈ H_{r} (where m = dim H_{r}) such that for g ∈ T we have

π(g)φ_{j} = e^{2πi⟨log g,u_{j}⟩}φ_{j},

where u_{j} ∈ I^{∗} is a weight and |u_{j}| ≤ r. Thus ∥φ_{j}∥_{Lip(T)} ≤ Cr. We can write f = ∑ α_{j}φ_{j} such that ∑ α_{j}^{2} = 1. Then

∥f∥_{Lip(T)} ≤ Cr ∑ α_{j} ≤ Cr\sqrt{m}.

By Weyl’s dimension formula it follows that each irreducible representation in H_{r} is of dimension at most Cr^{|R_{+}|} and each appears with multiplicity equal to its dimension. The number of irreducible components is at most Cr^{dim T}. Putting these together we get m ≤ Cr^{dim G} which proves the Lemma.

Proof of Lemma 5. First we bound the diameter in terms of the spectral gap. Let ε > 0 be a number, and g_{0} ∈ G. Suppose that for some integer l, there is no g ∈ S^{l} such that dist(g, g_{0}) ≤ ε. We fix a number D that we will specify later, and write r = Dε^{−2 dim G−2} and let f_{r} be the approximate identity constructed in Lemma 19. Then

∫_{dist(g,g_{0})< \frac{ε}{2}} Reg(μ_{S})^{l}f_{r}(g) dm_{G}(g) = ∫_{dist(g,g_{0})< \frac{ε}{2}} ∑_{h∈S^{l}} μ_{S}^{∗(l)}(h)f_{r}(h^{−1}g) dm_{G}(g)

≤ ∫_{dist(g,1)> \frac{ε}{2}} f_{r}(g) dm_{G}(g) ≤ \frac{C}{ε\sqrt{r}} . (46)

For the inequality between the first and second lines, we used that dist(h, g) ≥ ε/2, hence dist(1, h^{−1}g) ≥ ε/2. On the other hand, we have

∥1 − Reg(μ_{S})^{l}f_{r}∥_{2} ≤ Cr^{dim G/4}e^{−l·gap_{r}(G,S)}.

(Recall ∥f_{r}∥_{2} ≤ Cr^{dim G/4} from Lemma 19.) Hence

∫_{dist(g,g_{0})< \frac{ε}{2}} Reg(μ_{S})^{l}f_{r}(g) dm_{G}(g) ≥ ∫_{dist(g,g_{0})< \frac{ε}{2}} 1 dm_{G}(g) − \frac{Cr^{dim G/4}}{e^{l·gap_{r}(G,S)}}

≥ cε^{dim G}.  (47)

provided

l > \frac{log (2Cr^{dim G/4}/(cε^{dim G}))}{gap_{r}(G, S)} ≥ C′ · \frac{log(ε^{−1})}{gap_{r}(G, S)},

where C′ depends on G and D. Now we choose D such that

\frac{C}{ε\sqrt{r}} ≤ cε^{dim G},

where C and c are the constants form (46) and (47), respectively. This is impossible. We can conclude

diam(G, S) ≤ \frac{C log(ε^{−1})}{gap_{Dε^{−2 dim G−2}}(G, S)}.

Now we estimate the spectral gap in terms of the diameter. This argument was communicated to me by Jean Bourgain. Let r > 0 be a number, and set ε = Dr^{− dim G/2−1}, where D > 0 depends on G and will be set later. Let f ∈ H_{r} and assume that ∥f∥_{2} = 1 and ∫ f = 0. Then ∫ ⟨Reg(g)f, f⟩dm_{G}(g) = 0, hence there is g ∈ G such that ⟨Reg(g)f, f⟩ ≤ 0. Thus ∥Reg(g)f − f∥_{2} ≥ \sqrt{2}. Let l = diam_{ε}(G, S) and g_{0} = g_{1} ⋯ g_{l} ∈ S^{l} such that dist(g, g_{0}) ≤ ε. By Lemma 20 we have

∥Reg(g_{0})f − f∥_{2} ≥ ∥Reg(g)f − f∥_{2} − ∥Reg(g_{0})f − Reg(g)f∥_{2}
≥ \sqrt{2} − εCr^{dim G/2+1} ≥ 1

if we choose D to be sufficiently small in the definition of ε. By the triangle inequality, there is 1 ≤ j ≤ l such that

∥Reg(g_{j})f − f∥_{2} = ∥Reg(g_{1} ⋯ g_{j})f − Reg(g_{1} ⋯ g_{j−1})f∥_{2} ≥ 1/l.

This implies

∥Reg(g_{j})f + f∥_{2} ≤ 2 − 1/l^{2}.

Finally, we can conclude

∥Reg(μ_{S})f∥_{2} ≤ \frac{1}{|S|} (∥Reg(g_{j})f + f∥_{2} + ∥ ∑_{g∈S\\{1,g_{j}\}} Reg(g)f∥_{2})

≤ 1 − \frac{1}{|S|diam_{ε}(G, S)^{2}}

which was to be proved. (Recall the assumption 1 ∈ S.)

Documenta Mathematica 18 (2013) 1137–1175

References

[1] L. Babai and Á. Seress, On the diameter of permutation groups, European J. Combin. 13 No. 4 (1992), 231–243. 1139

[2] J. Bourgain and A. Gamburd, Uniform expansion bounds for Cayley graphs of SL_{2}(𝔽_{p}), Ann. of Math. 167 (2008), 625–642. 1140, 1146

[3] J. Bourgain and A. Gamburd, On the spectral gap for finitely-generated subgroups of SU(2) Invent. math. 171 (2008), no. 1, 83–121. 1144, 1145

[4] J. Bourgain and A. Gamburd, Expansion and random walks in SL_{d}(ℤ/p^{n}ℤ):I, J. Eur. Math. Soc. 10 (2008), 987–1011. 1140, 1146, 1153

[5] J. Bourgain and A. Gamburd, Expansion and random walks in SL_{d}(ℤ/p^{n}ℤ):II. With an appendix by J. Bourgain, J. Eur. Math. Soc. 11 No. 5. (2009), 1057–1103. 1140, 1146

[6] J. Bourgain and A. Gamburd, A spectral gap theorem in SU(d), J. Eur. Math. Soc. (JEMS) 14 No. 5 (2012), 1455-1511. 1144, 1145

[7] J. Bourgain, A. Gamburd and P. Sarnak, Affine linear sieve, expanders, and sum-product, Invent. math., 179 No. 3. (2010), 559–644. 1140, 1146

[8] J. Bourgain and A. Kontorovich, On the local–global conjecture for integral Apollonian gaskets, With an appendix by Péter P. Varjú, Invent. math., to appear http://dx.doi.org/10.1007/s00222-013-0475-y 1146

[9] J. Bourgain and P. P. Varjú, Expansion in SL_{d}(Z/qZ), q arbitrary, Invent. math. 188, No 1. (2012) 151–173. 1140, 1142, 1146, 1153, 1154, 1155

[10] E. Breuillard, Random walks on Lie groups, preprint,

http://www.math.u-psud.fr/∼breuilla/part0gb.pdf 1145

[11] E. Breuillard, B. J. Green and T. C. Tao, Approximate subgroups of linear groups, Geom. Funct. Anal. 21 (2011) 774–819. 1139, 1142, 1154, 1155

[12] T. Bröcker and T. tom Dieck, Representations of compact Lie groups, Graduate Texts in Mathematics, 98 Springer-Verlag, New York, 1995. 1143, 1157, 1158

[13] P. Diaconis and L. Saloff-Coste, Comparison techniques for random walk on finite groups, Ann. Probab. 21, No. 4 (1993) 2131–2156. 1139

[14] C. M. Dawson and M. A. Nielsen, The Solovay-Kitaev algorithm, Quantum Inf. Comput. 6 No. 1 (2006), 81–95. 1144

[15] O. Dinai, Poly-log diameter bounds for some families of finite groups, Proc. Amer. Math. Soc. 134 No. 11. (2006), 3137–3142. 1140, 1142, 1143 [16] O. Dinai, Diameters of Chevalley groups over local rings, Arch. Math.

(Basel) 99 No. 5 (2012), 417-424. 1140, 1142, 1143

[17] D. Dolgopyat, On mixing properties of compact group extensions of hyperbolic systems, Israel J. Math. 130 (2002), 157–205. 1145, 1146

[18] J. S. Ellenberg, C. Hall and E. Kowalski, Expander graphs, gonality, and variation of Galois representations Duke Math. J. 161 No. 7, (2012), 1233– 1275. 1146

[19] A. Gamburd, D. Jakobson and P. Sarnak, Spectra of elements in the group ring of SU(2), J. Eur. Math. Soc. 1, (1999) 51–85. 1144

[20] A. Gamburd, M. Shahshahani, Uniform diameter bounds for some families of Cayley graphs. Int. Math. Res. Not. 71 (2004), 3813–3824. 1140, 1142, 1143

[21] W. T. Gowers, Quasirandom Groups, Combin. Probab. Comput. 17 (2008), 363–387. 1140, 1144

[22] H. A. Helfgott, Growth and generation in SL_{2}(ℤ/pℤ), Ann. of Math. 167 (2008), 601–623. 1139, 1140, 1142

[23] H. A. Helfgott, Growth in SL_{3}(ℤ/pℤ), J. Eur. Math. Soc., 13 No. 3 (2011), 761–851. 1142

[24] H. A. Helfgott, Á. Seress, On the diameter of permutation groups, Ann. of Math., to appear, http://arxiv.org/abs/1109.3550v4 1139

[25] D. Kelmer and L. Silberman, A uniform spectral gap for congruence covers of a hyperbolic manifold, Amer. J. Math. 135 No 4 (2013), 1067–1085. 1154

[26] A. Yu. Kitaev, A. H. Shen and M. N. Vyalyi, Classical and quantum computation, Translated from the 1999 Russian original by Lester J. Senechal. Graduate Studies in Mathematics, 47 American Mathematical Society, Providence, RI, 2002. 1144

[27] A. Lev, The covering number of the group PSL_{n}(F) J. Algebra 182 No. 1 (1996), 60–84. 1155

[28] A. Lubotzky and C. Meiri, Sieve methods in group theory I: Powers in linear groups J. Amer. Math. Soc. 25 No. 4 (2012), 1119–1148. 1146

[29] N. Nikolov and L. Pyber, Product decompositions of quasirandom groups and a Jordan type theorem, J. Eur. Math. Soc. 13 No. 4 (2011), 1063–1077. 1141, 1144

[30] L. Pyber, E. Szabó, Growth in finite simple groups of Lie type of bounded rank, preprint, http://arxiv.org/abs/1005.1858 1139, 1142, 1154, 1155 [31] A. Salehi Golsefidy and P. P. Varjú, Expansion in perfect groups, Geom.

Funct. Anal. 22 No. 6 (2012), 1832-1891. 1140, 1146

[32] P. Sarnak and X. X. Xue, Bounds for multiplicities of automorphic representations, Duke Math. J., 64 No. 1, (1991), 207–227. 1140

[33] N. de Saxcé, Trou dimensionel dans les groupes de Lie compacts semisimples via les séries de Fourier, J. Anal. Math., to appear, http://www.ma.huji.ac.il/∼saxce/dimensionnel.pdf 1144, 1153

[34] P. P. Varjú, Expansion in SL_{d}(O_{K}/I), I square-free, J. Eur. Math. Soc. 14 No 1. (2012) 273–305. 1140, 1146

[35] P. P. Varjú, Random walks in Euclidean space, preprint, http://arxiv.org/abs/1205.3399 1145, 1146

Péter P. Varjú Centre for Mathematical Sciences Wilberforce Road Cambridge CB3 0WA England pv270@dpmms.cam.ac.uk and The Einstein Institute of Mathematics Edmond J. Safra Campus Givat Ram The Hebrew University of Jerusalem Jerusalem, 91904 Israel 1176

Documenta Mathematica 18 (2013)