The pancake sorting problem is to determine the diameter of the pancake graph, the Cayley graph of with respect to the generating set , where is defined (in two-line notation) by
(i.e., flips the top pancakes). It is not hard to see that the diameter is between and . Both lower and upper bound have been sharpened by a constant factor, and a natural conjecture is that converges to some intermediate constant (to be determined, ideally).
Here is a natural model problem: estimate for each fixed as . Clearly , and we should be able to detect some fall-off from this trivial upper bound.
Proposition 1 There is an integer sequence , beginning
(not in the OEIS) such that as with fixed.
To define it is useful to introduce the hyperoctahedral group (cf. burnt pancake sorting). You can think of as the group of “signed” or “antipodal” permutations: permutations of such that for all . There is a natural cover defined by forgetting signs. We lift to in a particular way: define , where
I computed the initial terms in the sequence using this simple formula. The first nontrivial relations are
and its inverse (to verify I recommend using four asymmetric cards from a deck of cards), which together account for .
To sketch the proof of Proposition 1, consider composing random elements of . You can think of this as a two-step process: randomly divide the stack in places, and then rearrange the resulting pieces, possibly with some reversals. With high probability the points of division are all distinct, so they can be inferred from the result (this is true for up to about ). The only question is whether the order can be inferred, and this is precisely what is defined by .
It would be informative for the pancake problem to know more about the sequence . I don’t know whether can be computed more efficiently than the naive way above, e.g., whether there is a recurrence: if so that would really help a lot.
There is at least a submultiplicativity property that follows from the proposition:
Corollary 2 For , . Hence there is a constant such that
Proof: This follows from , dividing by , and taking the limit. The second part follows from the subadditivity lemma and the data point .
I think a stronger bound should be true: there should be a constant such that
(One might then contemplate whether is the diameter of the pancake graph, but that seems a little bold at this stage.)
The subject matter is diameters of groups. A familiar example is Rubik’s cube, which has ( billion billion) possible configurations. The set of all configurations of the cube can be viewed as a group . (For the exact group structure, see wikipedia.) The standard generating set consists of rotations of any of the 6 faces, a set of size (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 from the origin, denoted , is at most : at each step, choose one of the possible moves. Therefore the diameter cannot be smaller than
The exact answer is not that much larger: 20. The size of is plotted below, which exhibits almost perfect exponential growth, until the end when it runs out of space.
In general, let be a finite group and a set of generators. Assume and . The Cayley graph is the graph with vertex set and an edge for every pair with and . The diameter of a graph 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 is the same as the smallest such that .
One expects similar behaviour as we saw for the Rubik’s cube group for any group which is sufficiently nonabelian (so that most products of generators are different, causing the balls 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
uniformly over finite simple groups and generating sets . The trivial lower bound is , 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:
finite groups of a fixed Lie type over a field of order with ;
quasisimple classical groups of dimension with and arbitrary: namely, the special linear group , the symplectic group , the derived subgroup of the orthogonal group , and the special unitary group ;
alternating groups .
The first part is the “bounded rank” case, and the latter two parts make up the “unbounded rank” case (and you can loosely consider to be , 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 have a uniform spectral gap, and in particular that
Personally I am most interested in high-rank groups, such as the alternating group (cf. the name of this blog). In the case of , Babai’s conjecture (a much older conjecture in this case) asserts simply that
For example, if the generating set consists just of the cycles and , then the the diameter is comparable to . 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
which is quasipolynomial rather than polynomial, and the result of Helfgott–Seress–Zuk which states that, if the generators are random,
Thus we are “almost there” with . On the other hand, we are still a long way off for high-rank classical groups such as . Such a group has size comparable to , and Babai’s conjecture asserts that
In many ways and, say, behave similarly, but in other ways they are very different. For example, suppose your generating set for contains a -cycle. Then because there are at most -cycles in all, it is clear that every -cycle has length at most in your generators, and hence every element of has length at most , so the conjecture is trivial in this case. On other hand, suppose your generating set for contains the closest analogue to a -cycle, a transvection. Unfortunately, there is not a trivial argument in this case, because the number of transvections is roughly . Indeed this is a difficult problem that was solved only earlier this year by Halasi.
However, if the size of the field is bounded, and you have at least random generators, then Urban and I know what to do. Under these conditions we show that
as conjectured by Babai.
Roughly, the recipe is the following. Let be your set of random generators. We want to show that we can reach everywhere in using steps in .
Start with a random walk of length . All of the points you get to will have “large support”, in the sense that has no large eigenspace.
Use explicit character bounds and the second moment method to show that, within the first steps, you will reach any specified large normal subset .
Choose so that every element of has a power which has minimal support. Hence we can reach such an element with steps.
Now act on that element by conjugation. This looks much like the standard action of on the natural module . 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.
Every element of can be written as the product of such elements, so every element of has length in .
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 on 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 , with joined to for each 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 random generators.
Our method needs generators. The reason is that we have great difficulty saying anything about the behaviour of the random walk after about 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.