The diameter of permutation groups

Ákos Seress and I have recently uploaded to the arxiv our new preprint, “On the diameter of permutation groups”. In it we prove that the diameter of the symmetric group is always small, irrespectively of the set of generators. By a standard result, this implies that the diameter of every transitive permutation group is small, again with respect to any set of generators.

Quite concretely – and forgetting about the actual mathematical applications for a moment – this means the following. Let a set A of ways to scramble
a finite set \Gamma=\{1,\dotsc,n\} be given. (Rubik’s cube and other combination puzzles are nice examples.) If you are told that a position can in fact be reached (or unscrambled) by applying some succession of actions in A, is there any way you can give a bound on how long the shortest possible way to do so might be?

What I have just proved with Akos is that, for every puzzle on n elements, every position that can be reached can in fact be reached quickly: the length of the shortest solution is at most quasipolynomial on n. This is true for any n and any set A, with the very soft condition that \langle A\rangle be transitive (i.e., with the condition that, given two elements x, y of \Gamma, there be some succession of actions in A taking x to y).

(On the more recreational side of things, giving an exact tight bound for the specific case of the Rubik cube was an open problem for a long time. Here we are more concerned with bounds as n goes to infinity. The point is precisely that we get to prove things for all possible permutation groups (“puzzles”), rather than for just a single one in particular.)

Before we can discuss things in more detail, let me give a bit of background and notation.

Let G be a group, A\subset G finite. Define
A^{-1} = \{g^{-1} : g\in A\}, A\cdot A = \{g_1 g_2 : g_1\in A, g_2\in A\}, A^k = \{g_1 g_2 \dotsc g_k : g_1,\dotsc,g_k\in A\} for k\geq 1. As is usual, we say that A generates G (or: A is a set of generators of G) if every element of G can be written as a product of elements of A and their inverses, i.e., if every element of G is in (A\cup A^{-1} \cup \{e\})^k for some k, where e is the identity. Assume from now on, for the sake of simplicity, that A = A^{-1} (i.e., A is closed under inversion) and e\in A.

A Cayley graph for the group of symmetries of a square, with a rotation (a) and a reflection (b) as generators. Thanks, Wikipedia.

If A generates G, we define the (undirected) Cayley graph \Gamma(G,A) of G with respect to A to be the graph we obtain by drawing one vertex for every element g of G and joining the vertices corresponding to the elements g, h by an edge if the quotient g^{-1} h is in A. The good thing about this graph is that it allows us to speak of properties of A and G in geometric terms. For starters, \Gamma(G,A) is connected, and this is precisely equivalent to the fact that A generates G. We can speak of the length of a path in the graph (meaning just the number of edges in the path) and we can also speak of the distance d(x,y) between two vertices x, y in the graph (meaning the length of the shortest path from one to the other). Then the distance from the origin e to a vertex g is just the length of the shortest product of elements of A that equals g, i.e., the smallest k such that g\in A^k. We can also define (again, this is completely standard for graphs) the diameter of a graph to be the greatest possible distance \max_{x,y} d(x,y) between two vertices of the graph. Then the diameter \text{diam}(\Gamma(G,A)) of the Cayley graph \Gamma(G,A) is just the smallest k such that G = A^k.

(Cultural-enrichment note: if you are studying an infinite group G with a finite set of generators A, you don’t study the diameter (it is obviously infinite), but rather the rate of growth \beta(k) = |A^k| (where |S| is the number of elements of a set S), particularly as k\to \infty. If you are study a finite group G, you do study the diameter rather than the rate of growth, since \beta(k) becomes constant after a while (namely, as soon as k\geq \text{diam}(\Gamma(G,A))). It’s clear, however, that in the two cases we are studying related questions. In fact, our methods give bounds on the behaviour of the rate of growth before it hits the diameter.)

We define the diameter \text{diam}(G) of a group $G$ to be the worst-case diameter, i.e., the maximum of \text{diam}(\Gamma(G,A)) over all sets of generators A of G. The symmetric group \text{Sym}(n) on n elements is just the group consisting of all the ways of permuting \{1,2,\dotsc,n\}, with composition as the group operation; thus |\text{Sym}(n)| = n!. A {\em permutation group} is any subgroup of \text{Sym}(n).

Theorem (Helfgott-Seress).- Let G = \text{Sym}(n). Then \text{diam}(G) \leq e^{(\log n)^{O(1)}}.

This is what is meant by a “quasipolynomial” bound; like, say, “polylogarithmic”, it is a standard term for complexity theorists but less so for, say, geometric group theorists. Here O(1), as usual, stands for a constant. (This is an “absolute constant”, i.e., an honest-to-goodness constant, not something that depends on something else.) We actually prove a more precise bound, namely, \text{diam}(G) \leq e^{O((\log n)^4 (\log \log n))}.

There are several immediate consequences thanks to standard results. For example, by (Babai-Seress, 1992), we get a bound of the same quality (\text{diam}(G) \leq e^{O((\log n)^4 (\log \log n))}) for any transitive permutation group. A similar bound follows for the mixing time, i.e., the time it takes for a succession of random moves to lead to every possible position with almost uniform probability.

In case you were wondering where this all fits: questions of diameter, mixing time, growth rate and so on are relevant in all groups, not just permutation groups. Up to a few years ago, the following fields of study were developing independently:

(a) The diameter of the symmetric group

The best general bound here was (Babai-Seress, 1988) (exponential on \sqrt{n}), but there are better results in special cases (Babai-Beals-Seress, 2006), (Babai-Hayes, 2005).

(b) Diameters and mixing time in linear algebraic groups (i.e., matrix groups).

This was an area of great interest to some number theorists and people who worked on property (T). Selberg’s spectral gap on quotients of the upper half plane was used to give bounds for some specific generators, but the problem for arbitrary generators was wide open. (Flash-forward to what was then the future: thanks to the work of Bourgain, Gamburd and Sarnak, things can now be done the other way around: bounds on the mixing time for finite groups imply spectral gaps for quotients of the upper half plane.)

(c) Arithmetic combinatorics

The classical setup is as follows. Let G be an abelian group. Let A be a finite subset of G. Is A\cdot A much larger than A? If not, what does that imply about A?

In 2005, I proved a polylogarithmic bound on the diameter of \text{SL}_2(Z/pZ), for arbitrary generators. This was the first group for which such a general bound had been proven. What was of particular interest to me was that I could apply some of the techniques in (c) to solve a problem in (b).

Since then this result has been generalised to such an extent (imagine long list of citations here; see p. 2 in the paper) that the main outstanding area left completely uncovered by the new methods was precisely permutation groups.

My new work with Ákos addresses this lack; I also hope it will serve to establish closer connections between (a), (b) and (c). While little of classical arithmetic combinatorics appears as such, several ideas from my own work on (b) and (c) do recur. Much use is made, not just of work in (a), but also (most importantly?) of previous work on the classification of permutation groups ((Babai 1982), (Pyber 1993)).


About valuevar

I am a number theorist with side interests in combinatorics and group theory.
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s