Expansion in finite simple groups of Lie type

Emmanuel Breuillard, Ben Green, Bob Guralnick, and I have just uploaded to the arXiv our joint paper “Expansion in finite simple groups of Lie type“. This long-delayed paper (announced way back in 2010!) is a followup to our previous paper in which we showed that, with one possible exception, generic pairs of elements of a simple algebraic group (over an uncountable field) generated a free group which was strongly dense in the sense that any nonabelian subgroup of this group was Zariski dense. The main result of this paper is to establish the analogous result for finite simple groups of Lie type (as defined in the previous blog post) and bounded rank, namely that almost all pairs of elements of such a group generate a Cayley graph which is a (two-sided) expander, with expansion constant bounded below by a quantity depending on the rank of the group. (Informally, this means that the random walk generated by spreads out in logarithmic time to be essentially uniformly distributed across the group, as opposed for instance to being largely trapped in an algebraic subgroup. Thus if generic elements did not generate a strongly dense group, one would probably expect expansion to fail.)

There are also some related results established in the paper. Firstly, as we discovered after writing our first paper, there was one class of algebraic groups for which our demonstration of strongly dense subgroups broke down, namely the groups in characteristic three. In the current paper we provide in a pair of appendices a new argument that covers this case (or more generally, in odd characteristic), by first reducing to the case of affine groups (which can be found inside as a subgroup) and then using a ping-pong argument (in a p-adic metric) in the latter context.

Secondly, we show that the distinction between one-sided expansion and two-sided expansion (see this set of lecture notes of mine for definitions) is erased in the context of Cayley graphs of bounded degree, in the sense that such graphs are one-sided expanders if and only if they are two-sided expanders (perhaps with slightly different expansion constants). The argument turns out to be an elementary combinatorial one, based on the “pivot” argument discussed in these lecture notes of mine.

Now to the main result of the paper, namely the expansion of random Cayley graphs. This result had previously been established for by Bourgain and Gamburd, and Ben, Emmanuel and I had used the Bourgain-Gamburd method to achieve the same result for Suzuki groups. For the other finite simple groups of Lie type, expander graphs had been constructed by Kassabov, Lubotzky, and Nikolov, but they required more than two generators, which were placed deterministically rather than randomly. (Here, I am skipping over a large number of other results on expanding Cayley graphs; see this survey of Lubotzsky for a fairly recent summary of developments.) The current paper also uses the “Bourgain-Gamburd machine”, as discussed in these lecture notes of mine, to demonstrate expansion. This machine shows how expansion of a Cayley graph follows from three basic ingredients, which we state informally as follows:

• Non-concentration (A random walk in this graph does not concentrate in a proper subgroup);
• Product theorem (A medium-sized subset of this group which is not trapped in a proper subgroup will expand under multiplication); and
• Quasirandomness (The group has no small non-trivial linear representations).

Quasirandomness of arbitrary finite simple groups of Lie type was established many years ago (predating, in fact, the introduction of the term “quasirandomness” by Gowers for this property) by Landazuri-Seitz and Seitz-Zalesskii, and the product theorem was already established by Pyber-Szabo and independently by Breuillard, Green, and myself. So the main problem is to establish non-concentration: that for a random Cayley graph on a finite simple group of Lie type, random walks did not concentrate in proper subgroups.

The first step was to classify the proper subgroups of . Fortunately, these are all known; in particular, such groups are either contained in proper algebraic subgroups of the algebraic group containing (or a bounded cover thereof) with bounded complexity, or are else arising (up to conjugacy) from a version of the same group associated to a proper subfield of the field respectively; this follows for instance from the work of Larsen and Pink, but also can be deduced using the classification of finite simple groups, together with some work of Aschbacher, Liebeck-Seitz, and Nori. We refer to the two types of subgroups here as “structural subgroups” and “subfield subgroups”.

To preclude concentration in a structural subgroup, we use our previous result that generic elements of an algebraic group generate a strongly dense subgroup, and so do not concentrate in any algebraic subgroup. To translate this result from the algebraic group setting to the finite group setting, we need a Schwarz-Zippel lemma for finite simple groups of Lie type. This is straightforward for Chevalley groups, but turns out to be a bit trickier for the Steinberg and Suzuki-Ree groups, and we have to go back to the Chevalley-type parameterisation of such groups in terms of (twisted) one-parameter subgroups, that can be found for instance in the text of Carter; this “twisted Schwartz-Zippel lemma” may possibly have further application to analysis on twisted simple groups of Lie type. Unfortunately, the Schwartz-Zippel estimate becomes weaker in twisted settings, and particularly in the case of triality groups , which require a somewhat ad hoc additional treatment that relies on passing to a simpler subgroup present in a triality group, namely a central product of two different ‘s.

To rule out concentration in a conjugate of a subfield group, we repeat an argument we introduced in our Suzuki paper and pass to a matrix model and analyse the coefficients of the characteristic polynomial of words in this Cayley graph, to prevent them from concentrating in a subfield. (Note that these coefficients are conjugation-invariant.)

254B, Notes 7: Sieving and expanders

In this final set of course notes, we discuss how (a generalisation of) the expansion results obtained in the preceding notes can be used for some number-theoretic applications, and in particular to locate almost primes inside orbits of thin groups, following the work of Bourgain, Gamburd, and Sarnak. We will not attempt here to obtain the sharpest or most general results in this direction, but instead focus on the simplest instances of these results which are still illustrative of the ideas involved.

One of the basic general problems in analytic number theory is to locate tuples of primes of a certain form; for instance, the famous (and still unsolved) twin prime conjecture asserts that there are infinitely many pairs in the line in which both entries are prime. In a similar spirit, one of the Landau conjectures (also still unsolved) asserts that there are infinitely many primes in the set . The Mersenne prime conjecture (also unsolved) asserts that there are infinitely many primes in the set , and so forth.

More generally, given some explicit subset in (or , if one wishes), such as an algebraic variety, one can ask the question of whether there are infinitely many integer lattice points in in which all the coefficients are simultaneously prime; let us refer to such points as prime points.

At this level of generality, this problem is impossibly difficult. Indeed, even the much simpler problem of deciding whether the set is non-empty (let alone containing prime points) when is a hypersurface cut out by a polynomial is essentially Hilbert’s tenth problem, which is known to be undecidable in general by Matiyasevich’s theorem. So one needs to restrict attention to a more special class of sets , in which the question of finding integer points is not so difficult. One model case is to consider orbits , where is a fixed lattice vector and is some discrete group that acts on somehow (e.g. might be embedded as a subgroup of the special linear group , or on the affine group ). In such a situation it is then quite easy to show that is large; for instance, will be infinite precisely when the stabiliser of in has infinite index in .

Even in this simpler setting, the question of determining whether an orbit contains infinitely prime points is still extremely difficult; indeed the three examples given above of the twin prime conjecture, Landau conjecture, and Mersenne prime conjecture are essentially of this form (possibly after some slight modification of the underlying ring , see this paper of Bourgain-Gamburd-Sarnak for details), and are all unsolved (and generally considered well out of reach of current technology). Indeed, the list of non-trivial orbits which are known to contain infinitely many prime points is quite slim; Euclid’s theorem on the infinitude of primes handles the case , Dirichlet’s theorem handles infinite arithmetic progressions , and a somewhat complicated result of Green, Tao, and Ziegler handles “non-degenerate” affine lattices in of rank two or more (such as the lattice of length arithmetic progressions), but there are few other positive results known that are not based on the above cases (though we will note the remarkable theorem of Friedlander and Iwaniec that there are infinitely many primes of the form , and the related result of Heath-Brown that there are infinitely many primes of the form , as being in a kindred spirit to the above results, though they are not explicitly associated to an orbit of a reasonable action as far as I know).

On the other hand, much more is known if one is willing to replace the primes by the larger set of almost primes – integers with a small number of prime factors (counting multiplicity). Specifically, for any , let us call an -almost prime an integer which is the product of at most primes, and possibly by the unit as well. Many of the above sorts of questions which are open for primes, are known for -almost primes for sufficiently large. For instance, with regards to the twin prime conjecture, it is a result of Chen that there are infinitely many pairs where is a prime and is a -almost prime; in a similar vein, it is a result of Iwaniec that there are infinitely many -almost primes of the form . On the other hand, it is still open for any fixed whether there are infinitely many Mersenne numbers which are -almost primes. (For the superficially similar situation with the numbers , it is in fact believed (but again unproven) that there are only finitely many -almost primes for any fixed (the Fermat prime conjecture).)

The main tool that allows one to count almost primes in orbits is sieve theory. The reason for this lies in the simple observation that in order to ensure that an integer of magnitude at most is an -almost prime, it suffices to guarantee that is not divisible by any prime less than . Thus, to create -almost primes, one can start with the integers up to some large threshold and remove (or “sieve out”) all the integers that are multiples of any prime less than . The difficulty is then to ensure that a sufficiently non-trivial quantity of integers remain after this process, for the purposes of finding points in the given set .

The most basic sieve of this form is the sieve of Eratosthenes, which when combined with the inclusion-exclusion principle gives the Legendre sieve (or exact sieve), which gives an exact formula for quantities such as the number of natural numbers less than or equal to that are not divisible by any prime less than or equal to a given threshold . Unfortunately, when one tries to evaluate this formula, one encounters error terms which grow exponentially in , rendering this sieve useful only for very small thresholds (of logarithmic size in ). To improve the sieve level up to a small power of such as , one has to replace the exact sieve by upper bound sieves and lower bound sieves which only seek to obtain upper or lower bounds on quantities such as , but contain a polynomial number of terms rather than an exponential number. There are a variety of such sieves, with the two most common such sieves being combinatorial sieves (such as the beta sieve), based on various combinatorial truncations of the inclusion-exclusion formula, and the Selberg upper bound sieve, based on upper bounds that are the square of a divisor sum. (There is also the large sieve, which is somewhat different in nature and based on almost orthogonality considerations, rather than on any actual sieving, to obtain upper bounds.) We will primarily work with a specific sieve in this notes, namely the beta sieve, and we will not attempt to optimise all the parameters of this sieve (which ultimately means that the almost primality parameter in our results will be somewhat large). For a more detailed study of sieve theory, see the classic text of Halberstam and Richert, or the more recent texts of Iwaniec-Kowalski or of Friedlander-Iwaniec.

Very roughly speaking, the end result of sieve theory is that excepting some degenerate and “exponentially thin” settings (such as those associated with the Mersenne primes), all the orbits which are expected to have a large number of primes, can be proven to at least have a large number of -almost primes for some finite . (Unfortunately, there is a major obstruction, known as the parity problem, which prevents sieve theory from lowering all the way to ; see this blog post for more discussion.) One formulation of this principle was established by Bourgain, Gamburd, and Sarnak:

Theorem 1 (Bourgain-Gamburd-Sarnak) Let be a subgroup of which is not virtually solvable. Let be a polynomial with integer coefficients obeying the following primitivity condition: for any positive integer , there exists such that is coprime to . Then there exists an such that there are infinitely many with non-zero and -almost prime.

This is not the strongest version of the Bourgain-Gamburd-Sarnak theorem, but it captures the general flavour of their results. Note that the theorem immediately implies an analogous result for orbits , in which is now a polynomial from to , and one uses instead of . It is in fact conjectured that one can set here, but this is well beyond current technology. For the purpose of reaching , it is very natural to impose the primitivity condition, but as long as one is content with larger values of , it is possible to relax the primitivity condition somewhat; see the paper of Bourgain, Gamburd, and Sarnak for more discussion.

By specialising to the polynomial , we conclude as a corollary that as long as is primitive in the sense that it contains matrices with all coefficients coprime to for any given , then contains infinitely many matrices whose elements are all -almost primes for some depending only on . For further applications of these sorts of results, for instance to Appolonian packings, see the paper of Bourgain, Gamburd, and Sarnak.

It turns out that to prove Theorem 1, the Cayley expansion results in from the previous set of notes are not quite enough; one needs a more general Cayley expansion result in where is square-free but not necessarily prime. The proof of this expansion result uses the same basic methods as in the case, but is significantly more complicated technically, and we will only discuss it briefly here. As such, we do not give a complete proof of Theorem 1, but hopefully the portion of the argument presented here is still sufficient to give an impression of the ideas involved.

254B, Notes 4: The Bourgain-Gamburd expansion machine

We have now seen two ways to construct expander Cayley graphs . The first, discussed in Notes 2, is to use Cayley graphs that are projections of an infinite Cayley graph on a group with Kazhdan’s property (T). The second, discussed in Notes 3, is to combine a quasirandomness property of the group with a flattening hypothesis for the random walk.

We now pursue the second approach more thoroughly. The main difficulty here is to figure out how to ensure flattening of the random walk, as it is then an easy matter to use quasirandomness to show that the random walk becomes mixing soon after it becomes flat. In the case of Selberg’s theorem, we achieved this through an explicit formula for the heat kernel on the hyperbolic plane (which is a proxy for the random walk). However, in most situations such an explicit formula is not available, and one must develop some other tool for forcing flattening, and specifically an estimate of the form

for some , where is the uniform probability measure on the generating set .

In 2006, Bourgain and Gamburd introduced a general method for achieving this goal. The intuition here is that the main obstruction that prevents a random walk from spreading out to become flat over the entire group is if the random walk gets trapped in some proper subgroup of (or perhaps in some coset of such a subgroup), so that remains large for some moderately large . Note that

since , , and is symmetric. By iterating this observation, we seethat if is too large (e.g. of size for some comparable to ), then it is not possible for the random walk to converge to the uniform distribution in time , and so expansion does not occur.

A potentially more general obstruction of this type would be if the random walk gets trapped in (a coset of) an approximate group . Recall that a -approximate group is a subset of a group which is symmetric, contains the identity, and is such that can be covered by at most left-translates (or equivalently, right-translates) of . Such approximate groups were studied extensively in last quarter’s course. A similar argument to the one given previously shows (roughly speaking) that expansion cannot occur if is too large for some coset of an approximate group.

It turns out that this latter observation has a converse: if a measure does not concentrate in cosets of approximate groups, then some flattening occurs. More precisely, one has the following combinatorial lemma:

Lemma 1 (Weighted Balog-Szemerédi-Gowers lemma) Let be a group, let be a finitely supported probability measure on which is symmetric (thus for all ), and let . Then one of the following statements hold:

• (i) (Flattening) One has .
• (ii) (Concentration in an approximate group) There exists an -approximate group in with and an element such that .

This lemma is a variant of the more well-known Balog-Szemerédi-Gowers lemma in additive combinatorics due to Gowers (which roughly speaking corresponds to the case when is the uniform distribution on some set ), which in turn is a polynomially quantitative version of an earlier lemma of Balog and Szemerédi. We will prove it below the fold.

The lemma is particularly useful when the group in question enjoys a product theorem, which roughly speaking says that the only medium-sized approximate subgroups of are trapped inside genuine proper subgroups of (or, contrapositively, medium-sized sets that generate the entire group cannot be approximate groups). The fact that some finite groups (and specifically, the bounded rank finite simple groups of Lie type) enjoy product theorems is a non-trivial fact, and will be discussed in later notes. For now, we simply observe that the presence of the product theorem, together with quasirandomness and a non-concentration hypothesis, can be used to demonstrate expansion:

Theorem 2 (Bourgain-Gamburd expansion machine) Suppose that is a finite group, that is a symmetric set of generators, and that there are constants with the following properties.

1. (Quasirandomness). The smallest dimension of a nontrivial representation of is at least ;
2. (Product theorem). For all there is some such that the following is true. If is a -approximate subgroup with then generates a proper subgroup of ;
3. (Non-concentration estimate). There is some even number such that

   

   where the supremum is over all proper subgroups .

Then is a two-sided -expander for some depending only on , and the function (and this constant is in principle computable in terms of these constants).

This criterion for expansion is implicitly contained in this paper of Bourgain and Gamburd, who used it to establish the expansion of various Cayley graphs in for prime . This criterion has since been applied (or modified) to obtain expansion results in many other groups, as will be discussed in later notes.

Suzuki groups as expanders

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv the paper “Suzuki groups as expanders“, to be submitted. The purpose of this paper is to finish off the last case of the following theorem:

Theorem 1 (All finite simple groups have expanders) For every finite simple non-abelian group , there exists a set of generators of cardinality bounded uniformly in , such that the Cayley graph on generated by (i.e. the graph that connects with for all and ) has expansion constant bounded away from zero uniformly in , or equivalently that for all with and some independent of .

To put in an essentially equivalent way, one can quickly generate a random element of a finite simple group with a near-uniform distribution by multiplying together a few (, to be more precise) randomly chosen elements of a fixed set . (The most well-known instance of this phenomenon is the famous result of Bayer and Diaconis that one can shuffle a 52-card deck reasonably well after seven riffle shuffles, and almost perfectly after ten.) Note that the abelian simple groups do not support expanders due to the slow mixing time of random walks in the abelian setting.

The first step in proving this theorem is, naturally enough, the classification of finite simple groups. The sporadic groups have bounded cardinality and are a trivial case of this theorem, so one only has to deal with the seventeen infinite families of finite non-abelian simple groups. With one exception, the groups in all of these families contain a copy of for some that goes to infinity as . Using this and several other non-trivial tools (such as Kazhdan’s property (T) and a deep model-theoretic result of Hrushovski and Pillay), the above theorem was proven for all groups outside of this exceptional family by a series of works culminating in the paper of Kassabov, Lubotzky, and Nikolov.

The exceptional family is the family of Suzuki groups , where is an odd power of . The Suzuki group can be viewed explicitly as a subgroup of the symplectic group and has cardinality . This cardinality is not divisible by , whereas all groups of the form have cardinality divisible by ; thus Suzuki groups do not contain copies of and the Kassabov-Lubotsky-Nikolov argument does not apply.

Our main result is that the Suzuki groups also support expanders, thus completing the last case of the above theorem. In fact we can pick just two random elements of the Suzuki group, and with probability , the Cayley graph generated by will be an expander uniformly in . (As stated in the paper of Kassabov-Lubotsky-Nikolov, the methods in that paper should give an upper bound on which they conservatively estimate to be .)

Our methods are different, instead following closely the arguments of Bourgain and Gamburd, which established the analogue of our result (i.e. that two random elements generate an expander graph) for the family of groups ( a large prime); the arguments there have since been generalised to several other major families of groups, and our result here can thus be viewed as one further such generalisation. Roughly speaking, the strategy is as follows. Let be the uniform probability measure on the randomly chosen set of generators , and let be the -fold convolution. We need to converge rapidly to the uniform measure on (with a mixing time of ). There are three steps to obtain this mixing:

• (Early period) When for some small , one wants to spread out a little bit in the sense that no individual element of is assigned a mass of any more than for some fixed . More generally, no proper subgroup of should be assigned a mass of more than .
• (Middle period) Once is somewhat spread out, one should be able to convolve this measure with itself a bounded number of times and conclude that the measure for some suitable is reasonably spread out in the sense that its norm is comparable (up to powers of for some small ) to the norm of the uniform distribution.
• (Late period) Once is reasonably spread out, a few more convolutions should make it extremely close to uniform (e.g. within in the norm).

The late period claim is easy to establish from Gowers’ theory of quasirandom groups, the key point being that (like all other finite simple nonabelian groups), the Suzuki groups do not admit any non-trivial low-dimensional irreducible representations (we can for instance use a precise lower bound of , due to Landazuri and Seitz). (One can also proceed here using a trace formula argument of Sarnak and Xue; the two approaches are basically equivalent.) The middle period reduces, by a variant of the Balog-Szemerédi-Gowers lemma, to a product estimate in which was recently established by Pyber-Szábo and can also be obtained by the methods of proof of the results announced by ourselves. (These arguments are in turn based on an earlier result of Helfgott establishing the analogous claim for .) This requires checking that is a “sufficiently Zariski dense” subgroup of the finite Lie group , but this can be done using an explicit description of the Suzuki group and the Schwartz-Zippel lemma.

The main difficulty is then to deal with the early period, obtaining some initial non-concentration in the random walk associated to away from subgroups of . These subgroups have been classified for some time (see e.g. the book of Wilson); they split into two families, the algebraic subgroups, which in the Suzuki case turn out to be solvable of derived length at most three, and the arithmetic subgroups, which are conjugate to , where is a subfield of .

In the algebraic case, one can prevent concentration using a lower bound on the girth of random Cayley graphs due to Gamburd, Hoory, Shahshahani, Shalev, and Virág (and we also provide an independent proof of this fact for completeness, which fortunately is able to avoid any really deep technology, such as Lang-Weil estimates); this follows an analogous argument of Bourgain-Gamburd in the case fairly closely, and is ultimately based on the fact that all the algebraic subgroups obey a fixed law (in this case, the law arises from the solvability). In the arithmetic case, the main task is to show that the coefficients of the characteristic polynomial of a typical word in does not fall into a proper subfield of , but this can be accomplished by a variant of the Schwartz-Zippel lemma.

Marker lecture IV: “Sieving for almost primes and expanders”

In this final lecture in the Marker lecture series, I discuss the recent work of Bourgain, Gamburd, and Sarnak on how arithmetic combinatorics and expander graphs were used to sieve for almost primes in various algebraic sets.

Distinguished Lecture Series II: Avi Wigderson, “Expander graphs – constructions and applications”

On Thursday, Avi Wigderson continued his Distinguished Lecture Series here at UCLA on computational complexity with his second lecture “Expander Graphs – Constructions and Applications“. As in the previous lecture, he spent some additional time after the talk on an “encore”, which in this case was how lossless expanders could be used to obtain rapidly decodable error-correcting codes.

The talk was largely based on these slides. Avi also has a recent monograph with Hoory and Linial on these topics. (For a brief introduction to expanders, I can also recommend Peter Sarnak’s Notices article. I also mention expanders to some extent in my third Milliman lecture.)