science – Random Permutations

I am delighted to announce that our paper Diameter bounds for arbitrary finite groups and applications (joint with Elena Maini, Luca Sabatini, and Gareth Tracey) has now appeared. The arXiv link is here: 2604.15303.

Let me explain what the paper is about. Given a group ${G}$ with a generating set ${X}$ , we measure the length of elements in ${G}$ by the length of the shortest ${X}$ -word representing them. This can be thought of as graph distance in the Cayley graph. The diameter of the group (if it is finite), denoted

$\displaystyle \mathrm{diam}(G,X)$

is the length of the longest element. This is “how long it takes” to generate the group.

For example, if your group is the Rubik’s cube group, the diameter is how long it takes to solve the Rubik’s cube, starting from the worst possible state.

We take an extra pessimistic view by additionally taking the worst possible generating set ${X}$ , and we denote this worst-case diameter simply

$\displaystyle \mathrm{diam}(G).$

This is the key quantity that we want to bound, and it is generally difficult to understand due to the double-universal quantification.

We consider the problem of bounding the diameter of an arbitrary finite group ${G}$ with respect to a worst-case generating set. In a sense, this is obviously hopeless. We can say

$\displaystyle \mathrm{diam}(G) \le |G|,$

and the cyclic group ${G = C_n}$ has diameter ${\lfloor n/2 \rfloor}$ , so what can we really hope for other than the linear bound?

It turns out that to bound the diameter up to a polylog factor, it suffices to understand just two things: (1) the diameters of its composition factors, and (2) the maximal exponent ${\varepsilon(G)}$ of its normal abelian sections, i.e.,

$\displaystyle \varepsilon(G) = \max\{\exp(N / N') : N \unlhd G\}.$

(The exponent of a group is the minimal integer ${e}$ such that ${g^e = 1}$ identically.) Essentially, this result is a reduction of the diameter question to the simple case. Often reducing to the simple case is a routine exercise in group theory papers, but in this case it is deep and surprising.

That probably sounds technical, and it is, so let me describe the most exciting consequences.

Babai’s conjecture predicts that every nonabelian finite simple group has polylogarithmic diameter, i.e., if ${G}$ is a nonabelian finite simple group then

$\displaystyle \mathrm{diam}(G) \le O((\log |G|)^B),$

for some universal constant ${B}$ (conceivably ${B = 2}$ ). This is a fundamental open conjecture in finite group theory. It has been proved in many cases (groups of bounded rank, some groups of unbounded rank with typical generators, etc), but it is still open in general. Our result is orthogonal to the finite simple case. We are studying groups that are “crumbly” (lots of composition factors), like the Rubik’s cube group. Let’s assume Babai’s conjecture holds, or at least let’s assume it holds for all the composition factors in whatever group we’re considering.

Under this hypothesis, we prove that ${\mathrm{diam}(G) \le \varepsilon(G) (\log |G|)^{O(1)}}$ . In words, only the exponent parameter matters, up to polylog factors.

A group is called anabelian if it has no abelian composition factors. For anabelian groups it follows that ${\mathrm{diam}(G) \le (\log |G|)^{O(1)}}$ , i.e., Babai’s conjecture extends to all anabelian groups.

Now assume ${G}$ is actually a transitive permutation group, ${G \le S_n}$ . Permutation puzzles can generally be modelled in this way, for example the Rubik’s cube, the ${15}$ -puzzle, and the “Hungarian rings”. In this case, we find that Babai’s conjecture implies that ${\mathrm{diam}(G) \le n^{O(1)}}$ . This is a folkloric conjecture originating in the early 1980’s. (Cultural note: For several months we have been referring to this conjecture as the “weak Babai conjecture”, although the logical relationship was unclear. Now we know that strong ${\implies}$ weak.)

Now let’s go to the world of infinite groups, which is much more of a wilderness. For infinite groups the diameter is infinite, so instead we talk about the growth function ${\gamma(n)}$ , which is the number of elements of ${X}$ -length at most ${n}$ . In typical examples, ${\gamma(n)}$ grows either polynomially or exponentially. It is a key mystery in geometric group theory what kind of growth functions one can have between these two extremes. Such groups are called groups of intermediate growth.

Grigorchuk’s gap conjecture predicts the existence of a constant ${\beta > 0}$ such that the following holds. If the growth function ${\gamma(n)}$ is bounded by ${\exp(O(n^\beta))}$ , then ${\gamma(n)}$ is bounded a polynomial.

A group is called residually finite if it is approximated by its finite quotients. This is “crumbly” for infinite groups. We show that Babai’s conjecture implies the gap conjecture for residually finite groups. It then follows that the gap conjecture holds in general if and only if it holds for infinite simple groups.

To the best of my knowledge, the close relationship between the conjectures of Babai and Grigorchuk had not been noticed before, partly because the sets of mathematicians familiar with either are mostly disjoint.

The exponent ${\beta}$ in the gap conjecture is the subject of further conjecture. Our constant depends on whatever constant holds in Babai’s conjecture, with a further factor of ${20}$ or so. It is conjectured that the optimal exponent in Babai’s conjecture is ${2}$ , and the optimal exponent in Grigorchuk’s conjecture is ${1/2}$ . The relation between these is striking, but deceptive, as the reasons for believing that they might be optimal are very different. In the case of Grigorchuk’s conjecture, for example, it remains possible that the optimal exponent is actually larger than ${1/2}$ .

We are far from knowing the answers to these mysteries, except in special cases. If ${G}$ is residually nilpotent (an important class including some of the most well-known examples of groups of intermediate growth), then Grigorchuk proved that the growth is ${> \exp(c n^{1/2})}$ unless ${G}$ is virtually nilpotent. If ${G}$ is residually soluble (a larger class), we have a result with ${1/4}$ in place of ${1/2}$ ; this is contained in another recent paper of Elena and myself, improving earlier work of Wilson (who obtained ${1/6}$ ). These papers are important predecessors to the paper that appeared today.

Now we just have to prove Babai’s conjecture…

Tag: science

Diameter bounds for crumbly groups