Babai’s conjecture for classical groups with random generators

Yesterday Urban Jezernik and I uploaded to the arxiv our preprint Babai’s conjecture for high-rank classical groups with random generators. I want to use this space to explain what our work is about and where it fits in the literature. To try to cater for a possibly wide range of mathematical backgrounds, I will start friendly and informal and get progressively more precise and technical. Thanks in advance for your attention!

Rubik's cube

The subject matter is diameters of groups. A familiar example is Rubik’s cube, which has {n \approx 4 \times 10^{19}} ({40} billion billion) possible configurations. The set of all configurations of the cube can be viewed as a group {R}. (For the exact group structure, see wikipedia.) The standard generating set {S} consists of rotations of any of the 6 faces, a set of size {19} (including the do-nothing operation). The diameter is the maximum number of moves it takes to solve the cube from any configuration. Now the number of configurations a distance {d} from the origin, denoted {S^d}, is at most {19^d}: at each step, choose one of the {19} possible moves. Therefore the diameter cannot be smaller than

\displaystyle  \left\lceil\frac{\log n}{\log 19}\right\rceil = 16.

The exact answer is not that much larger: 20. The size of {S^d} is plotted below, which exhibits almost perfect exponential growth, until the end when it runs out of space.

Growth of S^d in the Rubik’s cube group

In general, let {G} be a finite group and {S} a set of generators. Assume {S = S^{-1}} and {1 \in S}. The Cayley graph {\mathrm{Cay}(G, S)} is the graph with vertex set {G} and an edge for every pair {\{g, gs\}} with {g\in G} and {s \in S \setminus \{1\}}. The diameter {\mathrm{diam}\,\,\Gamma} of a graph {\Gamma} is the “longest shortest path”: the distance between two vertices is the length of the shortest path between them, and the diameter is the greatest distance between any two vertices. The diameter of a Cayley graph {\mathrm{Cay}(G, S)} is the same as the smallest {d} such that {S^d = G}.

One expects similar behaviour as we saw for the Rubik’s cube group {R} for any group {G} which is sufficiently nonabelian (so that most products of generators are different, causing the balls {S^d} to expand at about the rate they do in a tree). The most ideal form of nonabelianness is simplicity, and Babai’s conjecture is a precise form of this intuition for finite simple groups. The conjecture states that

\displaystyle  \mathrm{diam}\, \mathrm{Cay}(G, S) \leq (\log |G|)^{O(1)},

uniformly over finite simple groups {G} and generating sets {S}. The trivial lower bound is {\log_2|G|}, so the conjecture states that the truth is within a power of this trivial lower bound.

By the classification of finite simple groups, Babai’s conjecture breaks naturally into three parts:

  1. finite groups {X(q)} of a fixed Lie type {X} over a field of order {q} with {q \to \infty};
  2. quasisimple classical groups of dimension {n} with {n \to \infty} and {q} arbitrary: namely, the special linear group {\mathrm{SL}_n(q)}, the symplectic group {\mathrm{Sp}_n(q)}, the derived subgroup of the orthogonal group {O_n(q)'}, and the special unitary group {\mathrm{SU}_n(q)};
  3. alternating groups {A_n}.

The first part is the “bounded rank” case, and the latter two parts make up the “unbounded rank” case (and you can loosely consider {A_n} to be {\mathrm{PSL}_n(1)}, if you want).

The bounded rank case of Babai’s conjecture is completely resolved, following breakthrough work of Helfgott, Pyber–Szabo, and Breuillard–Green–Tao. Even stronger conjectures can be made in this case. For instance, it may be that the graphs {\mathrm{Cay}(G, S)} have a uniform spectral gap, and in particular that

\displaystyle  \mathrm{diam}\,\,\mathrm{Cay}(G,S) \leq O(\log|G|),

with the implicit constant depending only on the rank. This is true if the generators are random, by work of Breuillard–Green–Guralnick–Tao.

Personally I am most interested in high-rank groups, such as the alternating group {A_n} (cf. the name of this blog). In the case of {A_n}, Babai’s conjecture (a much older conjecture in this case) asserts simply that

\displaystyle  \mathrm{diam}\, \mathrm{Cay}(A_n, S) = n^{O(1)}.

For example, if the generating set consists just of the cycles {(12)} and {(12\cdots n)^{\pm1}}, then the the diameter is comparable to {n^2}. A folklore conjecture asserts that this is the worst case up to a constant factor. The strongest results in this direction are the result of Helfgott–Seress (see also this later paper of Helfgott) which states that

\displaystyle  \mathrm{diam}\, \mathrm{Cay}(A_n, S) \leq \exp O((\log n)^{4 + o(1)}),

which is quasipolynomial rather than polynomial, and the result of Helfgott–Seress–Zuk which states that, if the generators are random,

\displaystyle  \mathrm{diam}\, \mathrm{Cay}(A_n, S) \leq n^2 (\log n)^{O(1)}.

Thus we are “almost there” with {A_n}. On the other hand, we are still a long way off for high-rank classical groups such as {\mathrm{SL}_n(q)}. Such a group has size comparable to {q^{n^2}}, and Babai’s conjecture asserts that

\displaystyle  \mathrm{diam}\, \mathrm{Cay}(G, S) \leq (n \log q)^{O(1)}.

In this case the best bound we have is one of Halasi–Maroti–Pyber–Qiao (building on Biswas–Yang), which states

\displaystyle  \mathrm{diam}\, \mathrm{Cay}(G, S) \leq q^{O(n (\log n)^2)}.

In many ways {A_n} and, say, {\mathrm{SL}_n(2)} behave similarly, but in other ways they are very different. For example, suppose your generating set for {A_n} contains a {3}-cycle. Then because there are at most {n^3} {3}-cycles in all, it is clear that every {3}-cycle has length at most {n^3} in your generators, and hence every element of {A_n} has length at most {n^4}, so the conjecture is trivial in this case. On other hand, suppose your generating set for {\mathrm{SL}_n(2)} contains the closest analogue to a {3}-cycle, a transvection. Unfortunately, there is not a trivial argument in this case, because the number of transvections is roughly {2^{2n-1}}. Indeed this is a difficult problem that was solved only earlier this year by Halasi.

However, if the size of the field {q} is bounded, and you have at least {q^C} random generators, then Urban and I know what to do. Under these conditions we show that

\displaystyle  \mathrm{diam}\, \mathrm{Cay}(G, S) \leq n^{O(1)},

as conjectured by Babai.

Roughly, the recipe is the following. Let {S} be your set of random generators. We want to show that we can reach everywhere in {G} using {n^{O(1)}} steps in {S}.

  1. Start with a random walk of length {n/10}. All of the points you get to will have “large support”, in the sense that {g-1} has no large eigenspace.
  2. Use explicit character bounds and the second moment method to show that, within the first {n/10} steps, you will reach any specified large normal subset {\mathfrak{C}}.
  3. Choose {\mathfrak{C}} so that every element of {\mathfrak{C}} has a {n^{O(1)}} power which has minimal support. Hence we can reach such an element with {n^{O(1)}} steps.
  4. Now act on that element by conjugation. This looks much like the standard action of {G} on the natural module {\mathbf{F}_q^n}. We show that with high probability the Schreier graph of this action actually has a spectral gap, and in particular logarithmic diameter. Hence we can cover the entire conjugacy class.
  5. Every element of {G} can be written as the product of {O(n)} such elements, so every element of {G} has length {n^{O(1)}} in {S}.

Some of these ideas are recycled from my previous paper with Stefan Virchow (discussed in this earlier post).

Probably the most interesting part is step 4, which generalizes a result of Friedman–Joux–Roichman–Stern–Tillich for the symmetric group. The Schreier graph of the usual action of {S_n} on {\{1, \dots, n\}} is one of the standard models for a random bounded-degree regular graph, and the spectral gap of this graph is well-studied. The graph we care about on the other hand has vertex set {\mathbf{F}_q^n \setminus \{0\}}, with {v} joined to {gv} for each {g} in our set of random generators. We found experimentally that, spectrally, this graph is virtually indistinguishable from the random regular graph. In particular, there should be a spectral gap for at least {2} random generators.

Our method needs {q^C} generators. The reason is that we have great difficulty saying anything about the behaviour of the random walk after about {n} steps, or indeed somewhat fewer depending on the type (linear/symplectic/unitary/orthogonal) of the group. To get around this problem we need to ensure that the random walk covers the whole Schreier graph before this critical time, so we need enough generators so that the random walk spreads quickly enough.

An asymptotic for the Hall–Paige conjecture

Problem 1 Let {G} be a group of order {n}. Is there a bijection {f \colon G \to G} such that the map {x \mapsto x f(x)} is also a bijection?

For example, if {G} has odd order, you can just take {f(x) = x}. Then {x f(x) = x^2}, and because every element has odd order this defines a bijection. If {G = \mathbf{F}_2^d}, then it suffices to find a linear map without an eigenvalue. Cyclic groups of even order never have complete mappings (option 1: stop reading and try to prove this as a diverting puzzle; option 2: read on, and it will be explained and become essential).

In general, a solution to Problem 1 is called a complete mapping. The definition of complete mapping is a little strange. Here is some motivation, if you want some. The construction of finite projective planes is a problem going back to Euler. You can think of a finite projective plane as a collection of {n-1} mutually orthogonal {n \times n} Latin squares, where two Latin squares are termed orthogonal if, when superimposed, the {n^2} pairs of symbols are distinct. The most familiar Latin square is the cyclic Latin square, which has entries {i + j \bmod n} for {0 \leq i, j < n}. More generally, for any group {G} of order {n}, the multiplication table of {G} is an {n \times n} Latin square. If you write down what it means for another square to be orthogonal to the {G}-based Latin square, you will find yourself re-inventing the definition of complete mapping.

Another motivation, of possibly broader interest, is simply that counting complete mappings turns out to be interesting and difficult, and requires us to hone some counting skills that, we hope, will be applicable elsewhere.

The concerted effort to answer Problem 1 began with Hall and Paige (1955). First, there is an obstruction, beginning with cyclic groups of even order. More generally, consider the abelianization {G^\textup{ab}} of {G}, and suppose all the elements of {G} have nontrivial sum in {G^\textup{ab}}. Then if {f} is a bijection the elements {x f(x)} will sum up to zero, so {x f(x)} cannot possibly be a bijection. Therefore in order for a complete mapping to exist, we must have {\prod G \in [G, G]}. Hall and Paige proved that this condition is equivalent to the Sylow 2-subgroups of {G} being trivial or noncyclic. Henceforth this condition will be called the Hall–Paige condition. Conversely, Hall and Paige conjectured that Problem 1 has a solution as long as {G} satisfies their condition.

Conjecture 2 (Hall–Paige) Every group satisfying the Hall–Paige condition has a complete mapping.

Progress on the Hall–Paige conjecture was slow. Hall and Paige (1955) proved the conjecture for solvable groups and symmetric and alternating groups, but progress on the full conjecture didn’t really get under way until the classification was established. For a complete history, see the book by Evans. Aschbacher (1990) proved various restrictions on the form of a minimal counterexample. The real breakthrough came in 2009 when Wilcox showed that a minimal counterexample would have to be simple, and furthermore could not be any of the simple groups of Lie type, which leaves only the Tits group and the 26 sporadic groups. At this point the problem is in principle a finite check, but still a mammoth one. Combining Wilcox’s technology with extensive computer algebra, Evans ruled out all of the remaining groups, with one exception: the fourth Janko group {J_4}, a group of order {86775571046077562880 \approx 9 \times 10^{19}}, and finally {J_4} was ruled out by Bray in work that remained unpublished until last year. Thus the Hall–Paige conjecture was proved. Although many people contributed, it is customary to attribute the final result to Wilcox, Evans, and Bray.

Meanwhile, another strand of study was developing. Suppose we take just the cyclic group {G = C_n}. We know there is at least one complete mapping as long as {n} is odd. But how many are there?

Problem 3 How many complete mappings does the cyclic group {C_n} have?

This problem can be compared with the well-known {n} queens puzzle: how many ways can you place {n} queens on an {n \times n} chessboard so that no two are attacking? If you make the chessboard toroidal, so that going off one edge brings you back on the opposite one, and if you only allow the queens to use one of the two diagonals, then you get an equivalent question.

Heuristically, there are {n!} bijections {f}, and for each the function {x\mapsto x f(x)} has a roughly {n!/n^n} chance of being a bijection, so you can guess that the number of complete mappings is about {n!^2 / n^n}; this conjecture is attributed to Vardi (1991) (in a weaker form) and Wanless (2011).

Conjecture 4 (Vardi–Wanless) The number of complete mappings of {C_n} is asymptotically {(e^{-1} + o(1))^n n!}.

This is where additive combinatorics enters. A few years ago Freddie Manners, Rudi Mrazović, and I started thinking about Problem 3, motivated by the observation that it can be thought of as requesting the number of solutions to

\displaystyle  \pi_1 + \pi_2 = \pi_3

(or additive triples) with {\pi_1, \pi_2, \pi_3 \in S}, where {S \subset C_n^n} is the set of bijections. The usual tool for counting additive triples (or solutions to any linear equation) is Fourier analysis; hence the problem reduces to understanding the Fourier transform of {S}. After barking up this tree (for quite a while), we were eventually able to prove the Vardi–Wanless conjecture. In fact we proved something even more precise: the solution to Problem 3 turns out to be asymptotically

\displaystyle  (e^{-1/2} + o(1)) n!^2/n^{n-1},

which differs from the Vardi–Wanless guess (though they never made a guess so precise) in two important respects: there is an extra factor of {n}, and a factor of {e^{-1/2}} (what the hell?).

Since the key to unlocking Problem 3 is Fourier analysis, it seems like we are using the abelianness of {C_n} in an absolutely essential way, but today Freddie and Rudi and I have a new announcement: we can count complete mappings in nonabelian groups too, and the asymptotic is essentially unchanged.

Theorem 5 Let {G} be a group of order {n} satisfying the Hall–Paige condition. Then the number of complete mappings of {G} is asymptotically

\displaystyle  (e^{-1/2} + o(1)) |G^\textup{ab}| n!^2 / n^n.

Here are some other highlights from our paper:

  1. The asymptotic above is begging for a heuristic explanation. We give one! It uses something called the principle of maximum entropy, which I personally can’t wait to use again. Basically, if {f} is a random bijection, {x \mapsto x f(x)} is more prone to collisions than a random function, and, heuristically, has a Gibbs distribution with a particular partition function, and a calculation shows that its probability of being a bijection is therefore smaller by a constant factor.
  2. We evaluate the next term in the asymptotic! We actually show that the number of complete mappings is

    \displaystyle  e^{-1/2} (1 + (1/3 + \textup{inv}(G)/4)/n + O(1/n^2)) |G^\textup{ab}| n!^2/n^n,

    where {\textup{inv}(G)} is the proportion of involutions in {G}. This verifies another conjecture of Wanless: that elementary abelian {2}-groups have the most complete mappings of any group of the same order. We can keep going, in principle, but really we would rather not: there is a combinatorial explosion in the number of “collision types” (in a sense we make precise), and to give the next term in the asymptotic you need to sum over all of these.

  3. Orthogonally, we can give effective estimates instead of asymptotics. For example, we can show that as long as {|G| > 10^5} and all nontrivial complex representations of {G} have degree at least {21}, then {G} has a positive number of complete mappings (in fact, within a constant factor of {n!^2/n^n} such). By combining a few such effective statements, we can cover all the simple sporadic groups, apart from the two smallest {M_{11}} and {M_{12}}. You can view this as a second-generation proof of the Evans–Bray contribution to the Hall–Paige conjecture. In fact, our proof covers all nonabelian finite simple groups except for some alternating groups, some {\textup{PSL}_2(q)'s}, and about ten other groups that we list.

The preprint is available at Any comments appreciated, as always!