You are currently browsing the tag archive for the ‘quasirandom groups’ tag.

Suppose that ${G = (G,\cdot)}$ is a finite group of even order, thus ${|G|}$ is a multiple of two. By Cauchy’s theorem, this implies that ${G}$ contains an involution: an element ${g}$ in ${G}$ of order two. (Indeed, if no such involution existed, then ${G}$ would be partitioned into doubletons ${\{g,g^{-1}\}}$ together with the identity, so that ${|G|}$ would be odd, a contradiction.) Of course, groups of odd order have no involutions ${g}$, thanks to Lagrange’s theorem (since ${G}$ cannot split into doubletons ${\{ h, hg \}}$).

The classical Brauer-Fowler theorem asserts that if a group ${G}$ has many involutions, then it must have a large non-trivial subgroup:

Theorem 1 (Brauer-Fowler theorem) Let ${G}$ be a finite group with at least ${|G|/n}$ involutions for some ${n > 1}$. Then ${G}$ contains a proper subgroup ${H}$ of index at most ${n^2}$.

This theorem (which is Theorem 2F in the original paper of Brauer and Fowler, who in fact manage to sharpen ${n^2}$ slightly to ${n(n+2)/2}$) has a number of quick corollaries which are also referred to as “the” Brauer-Fowler theorem. For instance, if ${g}$ is a an involution of a group ${G}$, and the centraliser ${C_G(g) := \{ h \in G: gh = hg\}}$ has order ${n}$, then clearly ${n \geq 2}$ (as ${C_G(g)}$ contains ${1}$ and ${g}$) and the conjugacy class ${\{ aga^{-1}: a \in G \}}$ has order ${|G|/n}$ (since the map ${a \mapsto aga^{-1}}$ has preimages that are cosets of ${C_G(g)}$). Every conjugate of an involution is again an involution, so by the Brauer-Fowler theorem ${G}$ contains a subgroup of order at least ${\max( n, |G|/n^2)}$. In particular, we can conclude that every group ${G}$ of even order contains a proper subgroup of order at least ${|G|^{1/3}}$.

Another corollary is that the size of a simple group of even order can be controlled by the size of a centraliser of one of its involutions:

Corollary 2 (Brauer-Fowler theorem) Let ${G}$ be a finite simple group with an involution ${g}$, and suppose that ${C_G(g)}$ has order ${n}$. Then ${G}$ has order at most ${(n^2)!}$.

Indeed, by the previous discussion ${G}$ has a proper subgroup ${H}$ of index less than ${n^2}$, which then gives a non-trivial permutation action of ${G}$ on the coset space ${G/H}$. The kernel of this action is a proper normal subgroup of ${G}$ and is thus trivial, so the action is faithful, and the claim follows.

If one assumes the Feit-Thompson theorem that all groups of odd order are solvable, then Corollary 2 suggests a strategy (first proposed by Brauer himself in 1954) to prove the classification of finite simple groups (CFSG) by induction on the order of the group. Namely, assume for contradiction that the CFSG failed, so that there is a counterexample ${G}$ of minimal order ${|G|}$ to the classification. This is a non-abelian finite simple group; by the Feit-Thompson theorem, it has even order and thus has at least one involution ${g}$. Take such an involution and consider its centraliser ${C_G(g)}$; this is a proper subgroup of ${G}$ of some order ${n < |G|}$. As ${G}$ is a minimal counterexample to the classification, one can in principle describe ${C_G(g)}$ in terms of the CFSG by factoring the group into simple components (via a composition series) and applying the CFSG to each such component. Now, the “only” thing left to do is to verify, for each isomorphism class of ${C_G(g)}$, that all the possible simple groups ${G}$ that could have this type of group as a centraliser of an involution obey the CFSG; Corollary 2 tells us that for each such isomorphism class for ${C_G(g)}$, there are only finitely many ${G}$ that could generate this class for one of its centralisers, so this task should be doable in principle for any given isomorphism class for ${C_G(g)}$. That’s all one needs to do to prove the classification of finite simple groups!

Needless to say, this program turns out to be far more difficult than the above summary suggests, and the actual proof of the CFSG does not quite proceed along these lines. However, a significant portion of the argument is based on a generalisation of this strategy, in which the concept of a centraliser of an involution is replaced by the more general notion of a normaliser of a ${p}$-group, and one studies not just a single normaliser but rather the entire family of such normalisers and how they interact with each other (and in particular, which normalisers of ${p}$-groups commute with each other), motivated in part by the theory of Tits buildings for Lie groups which dictates a very specific type of interaction structure between these ${p}$-groups in the key case when ${G}$ is a (sufficiently high rank) finite simple group of Lie type over a field of characteristic ${p}$. See the text of Aschbacher, Lyons, Smith, and Solomon for a more detailed description of this strategy.

The Brauer-Fowler theorem can be proven by a nice application of character theory, of the type discussed in this recent blog post, ultimately based on analysing the alternating tensor power of representations; I reproduce a version of this argument (taken from this text of Isaacs) below the fold. (The original argument of Brauer and Fowler is more combinatorial in nature.) However, I wanted to record a variant of the argument that relies not on the fine properties of characters, but on the cruder theory of quasirandomness for groups, the modern study of which was initiated by Gowers, and is discussed for instance in this previous post. It gives the following slightly weaker version of Corollary 2:

Corollary 3 (Weak Brauer-Fowler theorem) Let ${G}$ be a finite simple group with an involution ${g}$, and suppose that ${C_G(g)}$ has order ${n}$. Then ${G}$ can be identified with a subgroup of the unitary group ${U_{4n^3}({\bf C})}$.

One can get an upper bound on ${|G|}$ from this corollary using Jordan’s theorem, but the resulting bound is a bit weaker than that in Corollary 2 (and the best bounds on Jordan’s theorem require the CFSG!).

Proof: Let ${A}$ be the set of all involutions in ${G}$, then as discussed above ${|A| \geq |G|/n}$. We may assume that ${G}$ has no non-trivial unitary representation of dimension less than ${4n^3}$ (since such representations are automatically faithful by the simplicity of ${G}$); thus, in the language of quasirandomness, ${G}$ is ${4n^3}$-quasirandom, and is also non-abelian. We have the basic convolution estimate

$\displaystyle \|1_A * 1_A * 1_A - \frac{|A|^3}{|G|} \|_{\ell^\infty(G)} \leq (4n^3)^{-1/2} |G|^{1/2} |A|^{3/2}$

(see Exercise 10 from this previous blog post). In particular,

$\displaystyle 1_A * 1_A * 1_A(0) \geq \frac{|A|^3}{|G|} - (4n^3)^{-1/2} |G|^{1/2} |A|^{3/2} \geq \frac{1}{2n^3} |G|^2$

and so there are at least ${|G|^2/2n^3}$ pairs ${(g,h) \in A \times A}$ such that ${gh \in A^{-1} = A}$, i.e. involutions ${g,h}$ whose product is also an involution. But any such involutions necessarily commute, since

$\displaystyle g (gh) h = g^2 h^2 = 1 = (gh)^2 = g (hg) h.$

Thus there are at least ${|G|^2/2n^3}$ pairs ${(g,h) \in G \times G}$ of non-identity elements that commute, so by the pigeonhole principle there is a non-identity ${g \in G}$ whose centraliser ${C_G(g)}$ has order at least ${|G|/2n^3}$. This centraliser cannot be all of ${G}$ since this would make ${g}$ central which contradicts the non-abelian simple nature of ${G}$. But then the quasiregular representation of ${G}$ on ${G/C_G(g)}$ has dimension at most ${2n^3}$, contradicting the quasirandomness. $\Box$

I’ve just uploaded to the arXiv my paper “Mixing for progressions in non-abelian groups“, submitted to Forum of Mathematics, Sigma (which, along with sister publication Forum of Mathematics, Pi, has just opened up its online submission system). This paper is loosely related in subject topic to my two previous papers on polynomial expansion and on recurrence in quasirandom groups (with Vitaly Bergelson), although the methods here are rather different from those in those two papers. The starting motivation for this paper was a question posed in this foundational paper of Tim Gowers on quasirandom groups. In that paper, Gowers showed (among other things) that if ${G}$ was a quasirandom group, patterns such as ${(x,xg,xh, xgh)}$ were mixing in the sense that, for any four sets ${A,B,C,D \subset G}$, the number of such quadruples ${(x,xg,xh, xgh)}$ in ${A \times B \times C \times D}$ was equal to ${(\mu(A) \mu(B) \mu(C) \mu(D) + o(1)) |G|^3}$, where ${\mu(A) := |A| / |G|}$, and ${o(1)}$ denotes a quantity that goes to zero as the quasirandomness of the group goes to infinity. In my recent paper with Vitaly, we also considered mixing properties of some other patterns, namely ${(x,xg,gx)}$ and ${(g,x,xg,gx)}$. This paper is concerned instead with the pattern ${(x,xg,xg^2)}$, that is to say a geometric progression of length three. As observed by Gowers, by applying (a suitably quantitative version of) Roth’s theorem in (cosets of) a cyclic group, one can obtain a recurrence theorem for this pattern without much effort: if ${G}$ is an arbitrary finite group, and ${A}$ is a subset of ${G}$ with ${\mu(A) \geq \delta}$, then there are at least ${c(\delta) |G|^2}$ pairs ${(x,g) \in G}$ such that ${x, xg, xg^2 \in A}$, where ${c(\delta)>0}$ is a quantity depending only on ${\delta}$. However, this argument does not settle the question of whether there is a stronger mixing property, in that the number of pairs ${(x,g) \in G^2}$ such that ${(x,xg,xg^2) \in A \times B \times C}$ should be ${(\mu(A)\mu(B)\mu(C)+o(1)) |G|^2}$ for any ${A,B,C \subset G}$. Informally, this would assert that for ${x, g}$ chosen uniformly at random from ${G}$, the triplet ${(x, xg, xg^2)}$ should resemble a uniformly selected element of ${G^3}$ in some weak sense.

For non-quasirandom groups, such mixing properties can certainly fail. For instance, if ${G}$ is the cyclic group ${G = ({\bf Z}/N{\bf Z},+)}$ (which is abelian and thus highly non-quasirandom) with the additive group operation, and ${A = \{1,\ldots,\lfloor \delta N\rfloor\}}$ for some small but fixed ${\delta > 0}$, then ${\mu(A) = \delta + o(1)}$ in the limit ${N \rightarrow \infty}$, but the number of pairs ${(x,g) \in G^2}$ with ${x, x+g, x+2g \in A}$ is ${(\delta^2/2 + o(1)) |G|^2}$ rather than ${(\delta^3+o(1)) |G|^2}$. The problem here is that the identity ${(x+2g) = 2(x+g) - x}$ ensures that if ${x}$ and ${x+g}$ both lie in ${A}$, then ${x+2g}$ has a highly elevated likelihood of also falling in ${A}$. One can view ${A}$ as the preimage of a small ball under the one-dimensional representation ${\rho: G \rightarrow U(1)}$ defined by ${\rho(n) := e^{2\pi i n/N}}$; similar obstructions to mixing can also be constructed from other low-dimensional representations.

However, by definition, quasirandom groups do not have low-dimensional representations, and Gowers asked whether mixing for ${(x,xg,xg^2)}$ could hold for quasirandom groups. I do not know if this is the case for arbitrary quasirandom groups, but I was able to settle the question for a specific class of quasirandom groups, namely the special linear groups ${G := SL_d(F)}$ over a finite field ${F}$ in the regime where the dimension ${d}$ is bounded (but is at least two) and ${F}$ is large. Indeed, for such groups I can obtain a count of ${(\mu(A) \mu(B) \mu(C) + O( |F|^{-\min(d-1,2)/8} )) |G|^2}$ for the number of pairs ${(x,g) \in G^2}$ with ${(x, xg, xg^2) \in A \times B \times C}$. In fact, I have the somewhat stronger statement that there are ${(\mu(A) \mu(B) \mu(C) \mu(D) + O( |F|^{-\min(d-1,2)/8} )) |G|^2}$ pairs ${(x,g) \in G^2}$ with ${(x,xg,xg^2,g) \in A \times B \times C \times D}$ for any ${A,B,C,D \subset G}$.

I was also able to obtain a partial result for the length four progression ${(x,xg,xg^2, xg^3)}$ in the simpler two-dimensional case ${G = SL_2(F)}$, but I had to make the unusual restriction that the group element ${g \in G}$ was hyperbolic in the sense that it was diagonalisable over the finite field ${F}$ (as opposed to diagonalisable over the algebraic closure ${\overline{F}}$ of that field); this amounts to the discriminant of the matrix being a quadratic residue, and this holds for approximately half of the elements of ${G}$. The result is then that for any ${A,B,C,D \subset G}$, one has ${(\frac{1}{2} \mu(A) \mu(B) \mu(C) \mu(D) + o(1)) |G|^2}$ pairs ${(x,g) \in G}$ with ${g}$ hyperbolic and ${(x,xg,xg^2,xg^3) \subset A \times B \times C \times D}$. (Again, I actually show a slightly stronger statement in which ${g}$ is restricted to an arbitrary subset ${E}$ of hyperbolic elements.)

For the length three argument, the main tools used are the Cauchy-Schwarz inequality, the quasirandomness of ${G}$, and some algebraic geometry to ensure that a certain family of probability measures on ${G}$ that are defined algebraically are approximately uniformly distributed. The length four argument is significantly more difficult and relies on a rather ad hoc argument involving, among other things, expander properties related to the work of Bourgain and Gamburd, and also a “twisted” version of an argument of Gowers that is used (among other things) to establish an inverse theorem for the ${U^3}$ norm.

I give some details of these arguments below the fold.

I’ve just uploaded to the arXiv my joint paper with Vitaly Bergelson, “Multiple recurrence in quasirandom groups“, which is submitted to Geom. Func. Anal.. This paper builds upon a paper of Gowers in which he introduced the concept of a quasirandom group, and established some mixing (or recurrence) properties of such groups. A ${D}$-quasirandom group is a finite group with no non-trivial unitary representations of dimension at most ${D}$. We will informally refer to a “quasirandom group” as a ${D}$-quasirandom group with the quasirandomness parameter ${D}$ large (more formally, one can work with a sequence of ${D_n}$-quasirandom groups with ${D_n}$ going to infinity). A typical example of a quasirandom group is ${SL_2(F_p)}$ where ${p}$ is a large prime. Quasirandom groups are discussed in depth in this blog post. One of the key properties of quasirandom groups established in Gowers’ paper is the following “weak mixing” property: if ${A, B}$ are subsets of ${G}$, then for “almost all” ${g \in G}$, one has

$\displaystyle \mu( A \cap gB ) \approx \mu(A) \mu(B) \ \ \ \ \ (1)$

where ${\mu(A) := |A|/|G|}$ denotes the density of ${A}$ in ${G}$. Here, we use ${x \approx y}$ to informally represent an estimate of the form ${x=y+o(1)}$ (where ${o(1)}$ is a quantity that goes to zero when the quasirandomness parameter ${D}$ goes to infinity), and “almost all ${g \in G}$” denotes “for all ${g}$ in a subset of ${G}$ of density ${1-o(1)}$“. As a corollary, if ${A,B,C}$ have positive density in ${G}$ (by which we mean that ${\mu(A)}$ is bounded away from zero, uniformly in the quasirandomness parameter ${D}$, and similarly for ${B,C}$), then (if the quasirandomness parameter ${D}$ is sufficiently large) we can find elements ${g, x \in G}$ such that ${g \in A}$, ${x \in B}$, ${gx \in C}$. In fact we can find approximately ${\mu(A)\mu(B)\mu(C) |G|^2}$ such pairs ${(g,x)}$. To put it another way: if we choose ${g,x}$ uniformly and independently at random from ${G}$, then the events ${g \in A}$, ${x \in B}$, ${gx \in C}$ are approximately independent (thus the random variable ${(g,x,gx) \in G^3}$ resembles a uniformly distributed random variable on ${G^3}$ in some weak sense). One can also express this mixing property in integral form as

$\displaystyle \int_G \int_G f_1(g) f_2(x) f_3(gx)\ d\mu(g) d\mu(x) \approx (\int_G f_1\ d\mu) (\int_G f_2\ d\mu) (\int_G f_3\ d\mu)$

for any bounded functions ${f_1,f_2,f_3: G \rightarrow {\bf R}}$. (Of course, with ${G}$ being finite, one could replace the integrals here by finite averages if desired.) Or in probabilistic language, we have

$\displaystyle \mathop{\bf E} f_1(g) f_2(x) f_3(gx) \approx \mathop{\bf E} f_1(x_1) f_2(x_2) f_3(x_3)$

where ${g, x, x_1, x_2, x_3}$ are drawn uniformly and independently at random from ${G}$.

As observed in Gowers’ paper, one can iterate this observation to find “parallelopipeds” of any given dimension in dense subsets of ${G}$. For instance, applying (1) with ${A,B,C}$ replaced by ${A \cap hB}$, ${C \cap hD}$, and ${E \cap hF}$ one can assert (after some relabeling) that for ${g,h,x}$ chosen uniformly and independently at random from ${G}$, the events ${g \in A}$, ${h \in B}$, ${gh \in C}$, ${x \in D}$, ${gx \in E}$, ${hx \in F}$, ${ghx \in H}$ are approximately independent whenever ${A,B,C,D,E,F,H}$ are dense subsets of ${G}$; thus the tuple ${(g,h,gh,x,gh,hx,ghx)}$ resebles a uniformly distributed random variable in ${G^7}$ in some weak sense.

However, there are other tuples for which the above iteration argument does not seem to apply. One of the simplest tuples in this vein is the tuple ${(g, x, xg, gx)}$ in ${G^4}$, when ${g, x}$ are drawn uniformly at random from a quasirandom group ${G}$. Here, one does not expect the tuple to behave as if it were uniformly distributed in ${G^4}$, because there is an obvious constraint connecting the last two components ${gx, xg}$ of this tuple: they must lie in the same conjugacy class! In particular, if ${A}$ is a subset of ${G}$ that is the union of conjugacy classes, then the events ${gx \in A}$, ${xg \in A}$ are perfectly correlated, so that ${\mu( gx \in A, xg \in A)}$ is equal to ${\mu(A)}$ rather than ${\mu(A)^2}$. Our main result, though, is that in a quasirandom group, this is (approximately) the only constraint on the tuple. More precisely, we have

Theorem 1 Let ${G}$ be a ${D}$-quasirandom group, and let ${g, x}$ be drawn uniformly at random from ${G}$. Then for any ${f_1,f_2,f_3,f_4: G \rightarrow [-1,1]}$, we have

$\displaystyle \mathop{\bf E} f_1(g) f_2(x) f_3(gx) f_4(xg) = \mathop{\bf E} f_1(x_1) f_2(x_2) f_3(x_3) f_4(x_4) + o(1)$

where ${o(1)}$ goes to zero as ${D \rightarrow \infty}$, ${x_1,x_2,x_3}$ are drawn uniformly and independently at random from ${G}$, and ${x_4}$ is drawn uniformly at random from the conjugates of ${x_3}$ for each fixed choice of ${x_1,x_2,x_3}$.

This is the probabilistic formulation of the above theorem; one can also phrase the theorem in other formulations (such as an integral formulation), and this is detailed in the paper. This theorem leads to a number of recurrence results; for instance, as a corollary of this result, we have

$\displaystyle \mu(A) \mu(B)^2 - o(1) \leq \mu( A \cap gB \cap Bg ) \leq \mu(A) \mu(B) + o(1)$

for almost all ${g \in G}$, and any dense subsets ${A, B}$ of ${G}$; the lower and upper bounds are sharp, with the lower bound being attained when ${B}$ is randomly distributed, and the upper bound when ${B}$ is conjugation-invariant.

To me, the more interesting thing here is not the result itself, but how it is proven. Vitaly and I were not able to find a purely finitary way to establish this mixing theorem. Instead, we had to first use the machinery of ultraproducts (as discussed in this previous post) to convert the finitary statement about a quasirandom group to an infinitary statement about a type of infinite group which we call an ultra quasirandom group (basically, an ultraproduct of increasingly quasirandom finite groups). This is analogous to how the Furstenberg correspondence principle is used to convert a finitary combinatorial problem into an infinitary ergodic theory problem.

Ultra quasirandom groups come equipped with a finite, countably additive measure known as Loeb measure ${\mu_G}$, which is very analogous to the Haar measure of a compact group, except that in the case of ultra quasirandom groups one does not quite have a topological structure that would give compactness. Instead, one has a slightly weaker structure known as a ${\sigma}$-topology, which is like a topology except that open sets are only closed under countable unions rather than arbitrary ones. There are some interesting measure-theoretic and topological issues regarding the distinction between topologies and ${\sigma}$-topologies (and between Haar measure and Loeb measure), but for this post it is perhaps best to gloss over these issues and pretend that ultra quasirandom groups ${G}$ come with a Haar measure. One can then recast Theorem 1 as a mixing theorem for the left and right actions of the ultra approximate group ${G}$ on itself, which roughly speaking is the assertion that

$\displaystyle \int_G f_1(x) L_g f_2(x) L_g R_g f_3(x)\ d\mu_G(x) \approx 0 \ \ \ \ \ (2)$

for “almost all” ${g \in G}$, if ${f_1, f_2, f_3}$ are bounded measurable functions on ${G}$, with ${f_3}$ having zero mean on all conjugacy classes of ${G}$, where ${L_g, R_g}$ are the left and right translation operators

$\displaystyle L_g f(x) := f(g^{-1} x); \quad R_g f(x) := f(xg).$

To establish this mixing theorem, we use the machinery of idempotent ultrafilters, which is a particularly useful tool for understanding the ergodic theory of actions of countable groups ${G}$ that need not be amenable; in the non-amenable setting the classical ergodic averages do not make much sense, but ultrafilter-based averages are still available. To oversimplify substantially, the idempotent ultrafilter arguments let one establish mixing estimates of the form (2) for “many” elements ${g}$ of an infinite-dimensional parallelopiped known as an IP system (provided that the actions ${L_g,R_g}$ of this IP system obey some technical mixing hypotheses, but let’s ignore that for sake of this discussion). The claim then follows by using the quasirandomness hypothesis to show that if the estimate (2) failed for a large set of ${g \in G}$, then this large set would then contain an IP system, contradicting the previous claim.

Idempotent ultrafilters are an extremely infinitary type of mathematical object (one has to use Zorn’s lemma no fewer than three times just to construct one of these objects!). So it is quite remarkable that they can be used to establish a finitary theorem such as Theorem 1, though as is often the case with such infinitary arguments, one gets absolutely no quantitative control whatsoever on the error terms ${o(1)}$ appearing in that theorem. (It is also mildly amusing to note that our arguments involve the use of ultrafilters in two completely different ways: firstly in order to set up the ultraproduct that converts the finitary mixing problem to an infinitary one, and secondly to solve the infinitary mixing problem. Despite some superficial similarities, there appear to be no substantial commonalities between these two usages of ultrafilters.) There is already a fair amount of literature on using idempotent ultrafilter methods in infinitary ergodic theory, and perhaps by further development of ultraproduct correspondence principles, one can use such methods to obtain further finitary consequences (although the state of the art for idempotent ultrafilter ergodic theory has not advanced much beyond the analysis of two commuting shifts ${L_g, R_g}$ currently, which is the main reason why our arguments only handle the pattern ${(g,x,xg,gx)}$ and not more sophisticated patterns).

We also have some miscellaneous other results in the paper. It turns out that by using the triangle removal lemma from graph theory, one can obtain a recurrence result that asserts that whenever ${A}$ is a dense subset of a finite group ${G}$ (not necessarily quasirandom), then there are ${\gg |G|^2}$ pairs ${(x,g)}$ such that ${x, gx, xg}$ all lie in ${A}$. Using a hypergraph generalisation of the triangle removal lemma known as the hypergraph removal lemma, one can obtain more complicated versions of this statement; for instance, if ${A}$ is a dense subset of ${G^2}$, then one can find ${\gg |G|^2}$ triples ${(x,y,g)}$ such that ${(x,y), (gx, y), (gx, gy), (gxg^{-1}, gyg^{-1})}$ all lie in ${A}$. But the method is tailored to the specific types of patterns given here, and we do not have a general method for obtaining recurrence or mixing properties for arbitrary patterns of words in some finite alphabet such as ${g,x,y}$.

We also give some properties of a model example of an ultra quasirandom group, namely the ultraproduct ${SL_2(F)}$ of ${SL_2(F_{p_n})}$ where ${p_n}$ is a sequence of primes going off to infinity. Thanks to the substantial recent progress (by Helfgott, Bourgain, Gamburd, Breuillard, and others) on understanding the expansion properties of the finite groups ${SL_2(F_{p_n})}$, we have a fair amount of knowledge on the ultraproduct ${SL_2(F)}$ as well; for instance any two elements of ${SL_2(F)}$ will almost surely generate a spectral gap. We don’t have any direct application of this particular ultra quasirandom group, but it might be interesting to study it further.

In the previous set of notes we saw how a representation-theoretic property of groups, namely Kazhdan’s property (T), could be used to demonstrate expansion in Cayley graphs. In this set of notes we discuss a different representation-theoretic property of groups, namely quasirandomness, which is also useful for demonstrating expansion in Cayley graphs, though in a somewhat different way to property (T). For instance, whereas property (T), being qualitative in nature, is only interesting for infinite groups such as ${SL_d({\bf Z})}$ or ${SL_d({\bf R})}$, and only creates Cayley graphs after passing to a finite quotient, quasirandomness is a quantitative property which is directly applicable to finite groups, and is able to deduce expansion in a Cayley graph, provided that random walks in that graph are known to become sufficiently “flat” in a certain sense.

The definition of quasirandomness is easy enough to state:

Definition 1 (Quasirandom groups) Let ${G}$ be a finite group, and let ${D \geq 1}$. We say that ${G}$ is ${D}$-quasirandom if all non-trivial unitary representations ${\rho: G \rightarrow U(H)}$ of ${G}$ have dimension at least ${D}$. (Recall a representation is trivial if ${\rho(g)}$ is the identity for all ${g \in G}$.)

Exercise 1 Let ${G}$ be a finite group, and let ${D \geq 1}$. A unitary representation ${\rho: G \rightarrow U(H)}$ is said to be irreducible if ${H}$ has no ${G}$-invariant subspaces other than ${\{0\}}$ and ${H}$. Show that ${G}$ is ${D}$-quasirandom if and only if every non-trivial irreducible representation of ${G}$ has dimension at least ${D}$.

Remark 1 The terminology “quasirandom group” was introduced explicitly (though with slightly different notational conventions) by Gowers in 2008 in his detailed study of the concept; the name arises because dense Cayley graphs in quasirandom groups are quasirandom graphs in the sense of Chung, Graham, and Wilson, as we shall see below. This property had already been used implicitly to construct expander graphs by Sarnak and Xue in 1991, and more recently by Gamburd in 2002 and by Bourgain and Gamburd in 2008. One can of course define quasirandomness for more general locally compact groups than the finite ones, but we will only need this concept in the finite case. (A paper of Kunze and Stein from 1960, for instance, exploits the quasirandomness properties of the locally compact group ${SL_2({\bf R})}$ to obtain mixing estimates in that group.)

Quasirandomness behaves fairly well with respect to quotients and short exact sequences:

Exercise 2 Let ${0 \rightarrow H \rightarrow G \rightarrow K \rightarrow 0}$ be a short exact sequence of finite groups ${H,G,K}$.

• (i) If ${G}$ is ${D}$-quasirandom, show that ${K}$ is ${D}$-quasirandom also. (Equivalently: any quotient of a ${D}$-quasirandom finite group is again a ${D}$-quasirandom finite group.)
• (ii) Conversely, if ${H}$ and ${K}$ are both ${D}$-quasirandom, show that ${G}$ is ${D}$-quasirandom also. (In particular, the direct or semidirect product of two ${D}$-quasirandom finite groups is again a ${D}$-quasirandom finite group.)

Informally, we will call ${G}$ quasirandom if it is ${D}$-quasirandom for some “large” ${D}$, though the precise meaning of “large” will depend on context. For applications to expansion in Cayley graphs, “large” will mean “${D \geq |G|^c}$ for some constant ${c>0}$ independent of the size of ${G}$“, but other regimes of ${D}$ are certainly of interest.

The way we have set things up, the trivial group ${G = \{1\}}$ is infinitely quasirandom (i.e. it is ${D}$-quasirandom for every ${D}$). This is however a degenerate case and will not be discussed further here. In the non-trivial case, a finite group can only be quasirandom if it is large and has no large subgroups:

Exercise 3 Let ${D \geq 1}$, and let ${G}$ be a finite ${D}$-quasirandom group.

• (i) Show that if ${G}$ is non-trivial, then ${|G| \geq D+1}$. (Hint: use the mean zero component ${\tau\downharpoonright_{\ell^2(G)_0}}$ of the regular representation ${\tau: G \rightarrow U(\ell^2(G))}$.) In particular, non-trivial finite groups cannot be infinitely quasirandom.
• (ii) Show that any proper subgroup ${H}$ of ${G}$ has index ${[G:H] \geq D+1}$. (Hint: use the mean zero component of the quasiregular representation.)

The following exercise shows that quasirandom groups have to be quite non-abelian, and in particular perfect:

Exercise 4 (Quasirandomness, abelianness, and perfection) Let ${G}$ be a finite group.

• (i) If ${G}$ is abelian and non-trivial, show that ${G}$ is not ${2}$-quasirandom. (Hint: use Fourier analysis or the classification of finite abelian groups.)
• (ii) Show that ${G}$ is ${2}$-quasirandom if and only if it is perfect, i.e. the commutator group ${[G,G]}$ is equal to ${G}$. (Equivalently, ${G}$ is ${2}$-quasirandom if and only if it has no non-trivial abelian quotients.)

Later on we shall see that there is a converse to the above two exercises; any non-trivial perfect finite group with no large subgroups will be quasirandom.

Exercise 5 Let ${G}$ be a finite ${D}$-quasirandom group. Show that for any subgroup ${G'}$ of ${G}$, ${G'}$ is ${D/[G:G']}$-quasirandom, where ${[G:G'] := |G|/|G'|}$ is the index of ${G'}$ in ${G}$. (Hint: use induced representations.)

Now we give an example of a more quasirandom group.

Lemma 2 (Frobenius lemma) If ${F_p}$ is a field of some prime order ${p}$, then ${SL_2(F_p)}$ is ${\frac{p-1}{2}}$-quasirandom.

This should be compared with the cardinality ${|SL_2(F_p)|}$ of the special linear group, which is easily computed to be ${(p^2-1) \times p = p^3 - p}$.

Proof: We may of course take ${p}$ to be odd. Suppose for contradiction that we have a non-trivial representation ${\rho: SL_2(F_p) \rightarrow U_d({\bf C})}$ on a unitary group of some dimension ${d}$ with ${d < \frac{p-1}{2}}$. Set ${a}$ to be the group element

$\displaystyle a := \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix},$

and suppose first that ${\rho(a)}$ is non-trivial. Since ${a^p=1}$, we have ${\rho(a)^p=1}$; thus all the eigenvalues of ${\rho(a)}$ are ${p^{th}}$ roots of unity. On the other hand, by conjugating ${a}$ by diagonal matrices in ${SL_2(F_p)}$, we see that ${a}$ is conjugate to ${a^m}$ (and hence ${\rho(a)}$ conjugate to ${\rho(a)^m}$) whenever ${m}$ is a quadratic residue mod ${p}$. As such, the eigenvalues of ${\rho(a)}$ must be permuted by the operation ${x \mapsto x^m}$ for any quadratic residue mod ${p}$. Since ${\rho(a)}$ has at least one non-trivial eigenvalue, and there are ${\frac{p-1}{2}}$ distinct quadratic residues, we conclude that ${\rho(a)}$ has at least ${\frac{p-1}{2}}$ distinct eigenvalues. But ${\rho(a)}$ is a ${d \times d}$ matrix with ${d < \frac{p-1}{2}}$, a contradiction. Thus ${a}$ lies in the kernel of ${\rho}$. By conjugation, we then see that this kernel contains all unipotent matrices. But these matrices generate ${SL_2(F_p)}$ (see exercise below), and so ${\rho}$ is trivial, a contradiction. $\Box$

Exercise 6 Show that for any prime ${p}$, the unipotent matrices

$\displaystyle \begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ t & 1 \end{pmatrix}$

for ${t}$ ranging over ${F_p}$ generate ${SL_2(F_p)}$ as a group.

Exercise 7 Let ${G}$ be a finite group, and let ${D \geq 1}$. If ${G}$ is generated by a collection ${G_1,\ldots,G_k}$ of ${D}$-quasirandom subgroups, show that ${G}$ is itself ${D}$-quasirandom.

Exercise 8 Show that ${SL_d(F_p)}$ is ${\frac{p-1}{2}}$-quasirandom for any ${d \geq 2}$ and any prime ${p}$. (This is not sharp; the optimal bound here is ${\gg_d p^{d-1}}$, which follows from the results of Landazuri and Seitz.)

As a corollary of the above results and Exercise 2, we see that the projective special linear group ${PSL_d(F_p)}$ is also ${\frac{p-1}{2}}$-quasirandom.

Remark 2 One can ask whether the bound ${\frac{p-1}{2}}$ in Lemma 2 is sharp, assuming of course that ${p}$ is odd. Noting that ${SL_2(F_p)}$ acts linearly on the plane ${F_p^2}$, we see that it also acts projectively on the projective line ${PF_p^1 := (F_p^2 \backslash \{0\}) / F_p^\times}$, which has ${p+1}$ elements. Thus ${SL_2(F_p)}$ acts via the quasiregular representation on the ${p+1}$-dimensional space ${\ell^2(PF_p^1)}$, and also on the ${p}$-dimensional subspace ${\ell^2(PF_p^1)_0}$; this latter representation (known as the Steinberg representation) is irreducible. This shows that the ${\frac{p-1}{2}}$ bound cannot be improved beyond ${p}$. More generally, given any character ${\chi: F_p^\times \rightarrow S^1}$, ${SL_2(F_p)}$ acts on the ${p+1}$-dimensional space ${V_\chi}$ of functions ${f \in \ell^2( F_p^2 \backslash \{0\} )}$ that obey the twisted dilation invariance ${f(tx) = \chi(t) f(x)}$ for all ${t \in F_p^\times}$ and ${x \in F_p^2 \backslash \{0\}}$; these are known as the principal series representations. When ${\chi}$ is the trivial character, this is the quasiregular representation discussed earlier. For most other characters, this is an irreducible representation, but it turns out that when ${\chi}$ is the quadratic representation (thus taking values in ${\{-1,+1\}}$ while being non-trivial), the principal series representation splits into the direct sum of two ${\frac{p+1}{2}}$-dimensional representations, which comes very close to matching the bound in Lemma 2. There is a parallel series of representations to the principal series (known as the discrete series) which is more complicated to describe (roughly speaking, one has to embed ${F_p}$ in a quadratic extension ${F_{p^2}}$ and then use a rotated version of the above construction, to change a split torus into a non-split torus), but can generate irreducible representations of dimension ${\frac{p-1}{2}}$, showing that the bound in Lemma 2 is in fact exactly sharp. These constructions can be generalised to arbitrary finite groups of Lie type using Deligne-Luzstig theory, but this is beyond the scope of this course (and of my own knowledge in the subject).

Exercise 9 Let ${p}$ be an odd prime. Show that for any ${n \geq p+2}$, the alternating group ${A_n}$ is ${p-1}$-quasirandom. (Hint: show that all cycles of order ${p}$ in ${A_n}$ are conjugate to each other in ${A_n}$ (and not just in ${S_n}$); in particular, a cycle is conjugate to its ${j^{th}}$ power for all ${j=1,\ldots,p-1}$. Also, as ${n \geq 5}$, ${A_n}$ is simple, and so the cycles of order ${p}$ generate the entire group.)

Remark 3 By using more precise information on the representations of the alternating group (using the theory of Specht modules and Young tableaux), one can show the slightly sharper statement that ${A_n}$ is ${n-1}$-quasirandom for ${n \geq 6}$ (but is only ${3}$-quasirandom for ${n=5}$ due to icosahedral symmetry, and ${1}$-quasirandom for ${n \leq 4}$ due to lack of perfectness). Using Exercise 3 with the index ${n}$ subgroup ${A_{n-1}}$, we see that the bound ${n-1}$ cannot be improved. Thus, ${A_n}$ (for large ${n}$) is not as quasirandom as the special linear groups ${SL_d(F_p)}$ (for ${p}$ large and ${d}$ bounded), because in the latter case the quasirandomness is as strong as a power of the size of the group, whereas in the former case it is only logarithmic in size.

If one replaces the alternating group ${A_n}$ with the slightly larger symmetric group ${S_n}$, then quasirandomness is destroyed (since ${S_n}$, having the abelian quotient ${S_n/A_n}$, is not perfect); indeed, ${S_n}$ is ${1}$-quasirandom and no better.

Remark 4 Thanks to the monumental achievement of the classification of finite simple groups, we know that apart from a finite number (26, to be precise) of sporadic exceptions, all finite simple groups (up to isomorphism) are either a cyclic group ${{\bf Z}/p{\bf Z}}$, an alternating group ${A_n}$, or is a finite simple group of Lie type such as ${PSL_d(F_p)}$. (We will define the concept of a finite simple group of Lie type more precisely in later notes, but suffice to say for now that such groups are constructed from reductive algebraic groups, for instance ${PSL_d(F_p)}$ is constructed from ${SL_d}$ in characteristic ${p}$.) In the case of finite simple groups ${G}$ of Lie type with bounded rank ${r=O(1)}$, it is known from the work of Landazuri and Seitz that such groups are ${\gg |G|^c}$-quasirandom for some ${c>0}$ depending only on the rank. On the other hand, by the previous remark, the large alternating groups do not have this property, and one can show that the finite simple groups of Lie type with large rank also do not have this property. Thus, we see using the classification that if a finite simple group ${G}$ is ${|G|^c}$-quasirandom for some ${c>0}$ and ${|G|}$ is sufficiently large depending on ${c}$, then ${G}$ is a finite simple group of Lie type with rank ${O_c(1)}$. It would be of interest to see if there was an alternate way to establish this fact that did not rely on the classification, as it may lead to an alternate approach to proving the classification (or perhaps a weakened version thereof).

A key reason why quasirandomness is desirable for the purposes of demonstrating expansion is that quasirandom groups happen to be rapidly mixing at large scales, as we shall see below the fold. As such, quasirandomness is an important tool for demonstrating expansion in Cayley graphs, though because expansion is a phenomenon that must hold at all scales, one needs to supplement quasirandomness with some additional input that creates mixing at small or medium scales also before one can deduce expansion. As an example of this technique of combining quasirandomness with mixing at small and medium scales, we present a proof (due to Sarnak-Xue, and simplified by Gamburd) of a weak version of the famous “3/16 theorem” of Selberg on the least non-trivial eigenvalue of the Laplacian on a modular curve, which among other things can be used to construct a family of expander Cayley graphs in ${SL_2({\bf Z}/N{\bf Z})}$ (compare this with the property (T)-based methods in the previous notes, which could construct expander Cayley graphs in ${SL_d({\bf Z}/N{\bf Z})}$ for any fixed ${d \geq 3}$).