I gave a talk “at” TAU yesterday. The talk is below if you are interested!

See also this previous post: Babai’s conjecture for classical groups with random generators

Skip to content
# Random Permutations

# Talk at TAU about Babai’s conjecture in high rank

# A thought about pancakes

Sean Eberhard's mathematics blog

I gave a talk “at” TAU yesterday. The talk is below if you are interested!

See also this previous post: Babai’s conjecture for classical groups with random generators

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 1There 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

Now defineI 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 2For , . 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.)