groups – Random Permutations

1. Boston–Shalev for conjugacy classes

Last week Daniele Garzoni and I uploaded to the arxiv a preprint on the Boston–Shalev conjecture for the conjugacy class weighting. The Boston–Shalev conjecture in its original form predicts that, in any finite simple group $G$ , in any transitive action, the proportion of elements acting as derangements is at least some universal constant $c > 0$ . This conjecture was proved by Fulman and Guralnick in a long series of papers. Daniele and I looked at conjugacy classes instead, and we found an analogous result to be true: the proportion of conjugacy classes containing derangements is at least some universal constant $c' > 0$ .

Our proof depends on the correspondence between semisimple conjugacy classes in a group of Lie type and polynomials over a finite field possibly with certain restrictions: either symmetry or conjugate-symmetry. We studied these sets of polynomials from an “anatomical” perspective, and we needed to prove several nontrivial estimates, e.g., for

the number of polynomials with a factor of a given degree (which is closely related the “multiplication table problem”),
the number of polynomials with an even or odd number of irreducible factors,
the number of polynomials with no factors of small degree,
or the number of polynomials factorizing in a certain way (e.g., as $f = gg^*$ , $g$ irreducible, $g^*$ the reciprocal polynomial).

For a particularly neat example, we found that, if the order of the ground field is odd, exactly half the self-reciprocal polynomials have an even number of irreducible factors — is there a simple proof of this fact?

2. Growth in Linear Groups

Yesterday Brendan Murphy, Endre Szabo, Laci Pyber, and I uploaded a substantial update to our preprint Growth in Linear Groups, in which we prove one general form of the “Helfgott–Lindenstrauss conjecture”. This conjecture asserts that if a symmetric subset $A$ of a general linear group $\mathrm{GL}_n(F)$ ( $n$ bounded, $F$ an arbitrary field) exhibits bounded tripling, $|A^3| \le K|A|$ , then $A$ suffers a precise structure: there are subgroup $H \trianglelefteq \Gamma \le \langle A \rangle$ such that $\Gamma / H$ is nilpotent of class at most $n-1$ , $H$ is contained in a bounded power $A^{O_n(1)}$ , and $A$ is covered by $K^{O_n(1)}$ cosets of $\Gamma$ . Following prodding by the referee and others, we put a lot more work in and proved one additional property: $\Gamma$ can be taken to be normal in $\langle A \rangle$ . This seemingly technical additional point is actually very subtle, and I strongly doubted whether it was true late into the project, more-or-less until we actually proved it.

We also added another significant “application”. This is not exactly an application of the result, but rather of the same toolkit. We showed that if $G \le \mathrm{GL}_n(F)$ (again $F$ an arbitrary field) is any finite subgroup which is $K(n)$ -quasirandom, for some quantity $K(n)$ depending only on $n$ , then the diameter of any Cayley graph of $G$ is polylogarithmic in the order of $|G|$ (that is, Babai’s conjecture holds for $G$ ). This was previously known for $G$ simple (Breuillard–Green–Tao, Pyber–Szabo, 2010). Our result establishes that it is only necessary that $G$ is sufficiently quasirandom. (There is a strong trend in asymptotic group theory of weakening results requiring simplicity to only requiring quasirandomness.)

The intention of our paper is more-or-less to “polish off” the theory of growth in bounded rank. By contrast, growth in high-rank simple groups is still poorly understood.

3. The Kelley–Meka result

Not my own work, but it cannot go unmentioned. There was a spectacular breakthrough in additive combinatorics last week. Kelley and Meka proved a Behrend-like upper bound for the density of a subset $A \subset \{1, \dots, n\}$ free of three-term arithmetic progressions (Roth’s theorem): the density of $A$ is bounded by $\exp(-c (\log n)^\beta)$ for some constants $c, \beta > 0$ . Already there are other expositions of the method which are also worth looking at: see the notes by Bloom and Sisask and Green (to appear, possibly).

Until this work, density $1 /\log n$ was the “logarithmic barrier”, only very recently and barely overcome by Bloom and Sisask. Now that the logarithmic barrier has been completely smashed, it seems inevitable that the new barometer for progress on Roth’s theorem is the exponent $\beta$ . Kelley and Meka obtain $\beta = 1/11$ , while the Behrend construction shows $\beta \le 1/2$ .

Let ${G}$ be a finite group. The group algebra ${\mathbf{C} G}$ is the complex algebra with basis ${G}$ , with multiplication defined by linearly extending the group law of ${G}$ . The description of ${\mathbf{C} G}$ as an algebra is called representation theory. Relatedly, we want to understand the structure of ${\mathbf{C} G}$ -modules. We often call ${\mathbf{C} G}$ -modules (complex) representations of ${G}$ , and simple ${\mathbf{C} G}$ -modules irreducible representations.

Lemma 1 (Schur’s lemma) If ${V}$ and ${V'}$ are simple ${\mathbf{C} G}$ -modules, then every nonzero homomorphism ${V\rightarrow V'}$ is an isomorphism. Moreover every homomorphism ${V\rightarrow V}$ is a scalar multiple of the identity.

Proof: Suppose that ${f:V\rightarrow V'}$ is a nonzero homomorphism. Then ${\ker f}$ is a submodule, so ${\ker f = 0}$ , and similarly ${f(V) = V'}$ , so ${f}$ is an isomorphism. Now suppose ${V=V'}$ . Since every eigenspace of ${f}$ is a submodule, by simplicity every eigenspace is either ${0}$ or ${V}$ . From the spectral theorem we deduce that ${f}$ is a scalar multiple of the identity. $\Box$

It turns out that we can ask for a unitary structure in ${\mathbf{C} G}$ -modules for free.

Lemma 2 (Weyl’s averaging tricking) Every ${\mathbf{C} G}$ -module ${V}$ has a ${G}$ -invariant inner product. Moreover if ${V}$ is simple then this inner product is unique up to scaling.

Proof: Let ${V}$ be a ${\mathbf{C} G}$ -module and let ${(,)}$ be any inner product on ${V}$ . Define a new inner product ${\langle,\rangle}$ by

$\displaystyle \langle u, v\rangle = \frac{1}{|G|} \sum_{g\in G} (g\cdot u, g\cdot v).$

Clearly ${\langle,\rangle}$ has the desired properties. Now suppose that ${V}$ is simple, and that ${\langle,\rangle'}$ is another ${G}$ -invariant inner product. Let ${f:V\rightarrow V}$ be the adjoint of the formal identity

$\displaystyle (V,\langle,\rangle)\rightarrow(V,\langle,\rangle').$

In other words let ${f}$ be the unique function ${V\rightarrow V}$ satisfying

$\displaystyle \langle u,v\rangle' = \langle u, f(v)\rangle$

for all ${u,v\in V}$ . Then ${f}$ is a homomorphism, so by Schur’s lemma it must be a multiple of the identity, so ${\langle,\rangle'}$ must be a multiple of ${\langle,\rangle}$ . $\Box$

Lemma 3 Let ${U}$ be a finite-dimensional ${\mathbf{C} G}$ -module with ${G}$ -invariant inner product ${\langle,\rangle}$ , and for each simple ${\mathbf{C} G}$ -module ${V}$ let ${U_V}$ be the sum of all submodules of ${U}$ isomorphic to ${V}$ (the isotypic component of ${U}$ corresponding to ${V}$ ). Then ${U_V\cong V^{\oplus m}}$ for some ${m}$ , and ${U}$ is the orthogonal direct sum of the submodules ${U_V}$ .

Proof: Since the orthogonal complement of a submodule is a submodule, it follows by induction on dimension that ${U}$ is an orthogonal direct sum of simple submodules, so ${U = \bigoplus U'_V}$ , where ${V}$ runs over simple ${\mathbf{C} G}$ -modules and each ${U'_V \cong V^{\oplus m}}$ for some ${m\geq 0}$ . Moreover by Schur’s lemma any two nonisomorphic simple submodules must be orthogonal, as the orthogonal projection from one to the other is a homomorphism, so every submodule of ${U}$ isomorphic to ${V}$ must be contained in ${U'_V}$ , so ${U'_V=U_V}$ . $\Box$

The above lemma is particularly interesting when applied to the ${\mathbf{C} G}$ -module ${\mathbf{C} G}$ itself, the regular representation. We give ${\mathbf{C} G}$ a ${G}$ -invariant inner product by declaring the basis ${G}$ to be orthonormal. From the above lemma we know then that ${\mathbf{C} G = \bigoplus \mathbf{C} G_V}$ , where ${V}$ runs over simple ${\mathbf{C} G}$ -modules, and ${\mathbf{C} G_V\cong V^{\oplus m}}$ for some ${m\geq 0}$ . Note then by Schur’s lemma that ${\dim\textup{Hom}(\mathbf{C} G,V)=m}$ . On the other hand every homomorphism ${\mathbf{C} G\rightarrow V}$ is determined uniquely by the destination of the unit ${1}$ in ${V}$ , so ${\dim\textup{Hom}(\mathbf{C} G,V)=\dim V}$ . We deduce that as ${\mathbf{C} G}$ -modules

$\displaystyle \mathbf{C} G \cong \bigoplus V^{\oplus \dim V}.$

In particular there are only finitely many simple ${\mathbf{C} G}$ -modules, and their dimensions obey

$\displaystyle |G| = \sum (\dim V)^2.$

One can also prove ${\mathbf{C} G_V\cong V^{\oplus\dim V}}$ in a more informative way, as follows. Fix an invariant inner product ${\langle,\rangle_V}$ on ${V}$ , and consider any homomorphism ${f:V\rightarrow\mathbf{C} G}$ . The adjoint ${f^*:\mathbf{C} G\rightarrow V}$ is also a homomorphism, so

$\displaystyle f(v) = \sum_{g\in G}\langle f(v),g\rangle_{\mathbf{C} G} g = \sum_{g\in G}\langle v, f^*(g)\rangle_V g = \sum_{g\in G}\langle v,g f^*(1)\rangle_V g.$

Conversely for any ${u\in V}$ we may define a homomorphism ${V\rightarrow\mathbf{C} G}$ by

$\displaystyle f_{V,u}(v) = \sum_{g\in G} \langle v,g\cdot u\rangle_V g.$

We deduce therefore that ${\mathbf{C} G_V}$ is the subspace of ${\mathbf{C} G}$ spanned by the elements ${f_{V,u}(v)}$ , where ${u,v\in V}$ . Moreover using Schur’s lemma one can show that the images of ${f_{V,u}}$ and ${f_{V,u'}}$ are orthogonal whenever ${u}$ and ${u'}$ are orthogonal in ${V}$ , so by letting ${u}$ range over a basis of ${V}$ we thus see that ${\mathbf{C} G_V}$ is the orthogonal direct sum of ${\dim V}$ copies of ${V}$ .

In any case we now understand the structure of ${\mathbf{C} G}$ as a ${\mathbf{C} G}$ -module, and we are only a short step away from understanding its structure as an algebra. Consider the obvious map

$\displaystyle \mathbf{C} G \longrightarrow \bigoplus \textup{End}(V),$

where as always the sum runs over a complete set of irreducible representations up to isomorphism. We claim this map is an isomorphism. Since we already know the dimensions agree, it suffices to prove injectivity. Thus suppose ${x\in\mathbf{C} G}$ maps to zero, i.e., that ${x}$ acts trivially on each simple ${\mathbf{C} G}$ -module ${V}$ . Then ${x}$ acts trivially on ${\mathbf{C} G}$ , so ${x = x1 = 0}$ . Thus we have proved the following theorem.

Theorem 4 As complex algebras, ${\mathbf{C} G \cong \bigoplus \textup{End}(V)}$ .

Finally, it is useful to understand how to project onto isotypic components. Given ${g\in G}$ , we can compute the trace of ${g}$ as an operator on ${\mathbf{C} G}$ in two different ways. On the one hand, by looking at the basis ${G}$ ,

$\displaystyle \textup{tr}_{\mathbf{C} G} (g) = \begin{cases} |G| & \text{if }g=1,\\ 0 &\text{if }g\neq 1.\end{cases}$

On the other hand from the decomposition ${\mathbf{C} G\cong\bigoplus V^{\oplus\dim V}}$ we have

$\displaystyle \textup{tr}_{\mathbf{C} G} (g) = \sum_V (\dim V) \textup{tr}_V(g).$

As a consequence, for every ${x\in \mathbf{C} G}$ we have

$\displaystyle x = \sum_V P_V x,$

where ${P_V : \mathbf{C} G \rightarrow \mathbf{C} G}$ is the operator defined by

$\displaystyle P_V x = \frac{\dim V}{|G|} \sum_{g\in G} \textup{tr}_V(xg^{-1}) g = \frac{\dim V}{|G|} \sum_{g\in G} \textup{tr}_V(g^{-1}) gx.$

These identities are most easily verified first for ${x\in G}$ , then extending to all of ${\mathbf{C} G}$ by linearity. Now if ${x \in \mathbf{C} G_U}$ for ${U\neq V}$ then ${x}$ acts as zero on ${V}$ , so ${\textup{tr}_V(x g^{-1}) = 0}$ , so ${P_V x = 0}$ . On the other hand one can verify directly that ${P_V}$ is a homomorphism, so by Schur’s lemma the image of ${P_V}$ must be contained in ${\mathbf{C} G_V}$ . We deduce therefore from ${x = \sum_V P_V x}$ that ${P_V}$ is the orthogonal projection onto ${\mathbf{C} G}$ .

The function ${\chi_V(g) = \textup{tr}_V(g)}$ is usually called the character of ${V}$ . From the relations ${P_V^2 = P_V}$ and ${P_U P_V = 0}$ for ${U\neq V}$ one can deduce the well known orthogonality relations for characters. In fact the distinction between ${P_V}$ and ${\chi_V}$ is hardly more than notational. Often we identify functions ${f:G\rightarrow \mathbf{C}}$ with elements ${\sum_{g\in G} f(g) g \in \mathbf{C} G}$ , in which case the operation of convolution corresponds to multiplication in the group algebra. The operator ${P_V}$ then is just convolution with ${(\dim V)\chi_V}$ . So, in brief, to project onto the ${V}$ -isotypic component you convolve with the character of ${V}$ and multiply by ${\dim V}$ .

We have kept to almost the bare minimum in the above discussion: the complex numbers ${\mathbf{C}}$ and finite groups ${G}$ . There are a number of directions we could try to move in. We could replace ${\mathbf{C}}$ with a different field, say one which is not algebraically closed, or one which has positive characteristic. Alternatively we could replace ${G}$ with an infinite group, say with a locally compact topology. We mention two such generalisations.

Theorem 5 (Artin–Wedderburn) Every semisimple ring is isomorphic to a product ${\prod_{i=1}^k M_{n_i}(D_i)}$ of matrix rings, where the ${n_i}$ are integers and the ${D_i}$ are division rings. In particular every semisimple ${\mathbf{C}}$ -algebra is isomorphic to a product ${\prod_{i=1}^k M_{n_i}(\mathbf{C})}$ .

When defining unitary representations for compact groups ${G}$ we demand that the map ${G\rightarrow U(V)}$ be continuous, where ${U(V)}$ is given the strong operator topology.

Theorem 6 (Peter–Weyl) Let ${G}$ be a compact group and ${\mu}$ its normalised Haar measure. Let ${\widehat{G}}$ be the set of all irreducible unitary representations of ${G}$ up to isomorphism. Then ${\widehat{G}}$ is countable, every ${V\in\widehat{G}}$ is finite-dimensional, and the algebra ${L^2(G)}$ of square-integrable functions with the operation of convolution decomposes as a Hilbert algebra as

$\displaystyle L^2(G) \cong \bigoplus_{V\in\widehat{G}} (\dim V) \cdot \textup{HS}(V),$

where ${\textup{HS}(V)}$ is the space ${\textup{End}(V)}$ together with the Hilbert–Schmidt inner product.