# Minimum word length for an unusual set of generators of the symmetric group

Problem. Let $n\geq 2$ and let $T$ be the set of all permutations in $S_n$ of the form $$t_k:=\prod_{1\leq i\leq k/2}(i,k-i) \qquad \hbox{for k=3,4,\ldots,n+1}.$$ Find the least integer $f_n$ such that every $x \in S_n$ can be written as a product of at most $f_n$ elements from $T$.

This is part (ii) of Exercise 1.2.16 in Chapter 1 of Permutation Groups by Dixon and Mortimer (Springer 1996) and is labeled as an unsolved problem. It has been 18 years since the book was published (I guess there hasn't been any further edition yet), so I was wondering whether it is solved or not; if it is can somebody give me a hint? It looks very tough. I have solved part (i) of the exercise, showing that $T$ generates $S_n$, and showing that $2n-3$ is always an upper bound.

I asked it on math.stackexchange but did not get any answers there. I am an active member there, but here it is my first question; I hope it meets the standards here.

• @Bhaskar Vashishth: (1) You asked this just 7 hours ago at math.stackexchange.com/questions/962121/…, so maybe you are a little impatient. (2) The book you mention is by Dixon and Mortimer. (3) The assertion you showed is exercise 1.2.16(i) there, your question is about the unsolved part (ii). Oct 7 '14 at 18:58
• Isn't this just prefix reversal? In other words, you are asking for the diameter of the "pancake graph". This is open but see oeis.org/A058986 for lots of information. Oct 8 '14 at 1:31
• The standard name for this problem is "Pancake Sorting" and the Wikipedia article is pretty good en.wikipedia.org/wiki/Pancake_sorting . One fun fact is that this is the subject of Bill Gates only published paper in math cs.berkeley.edu/~christos/papers/… Oct 8 '14 at 12:19
• @verret: That looks like an answer and I encourage you to post it as such. Oct 8 '14 at 14:57
• Another fun fact is that the problem was originally raised by an author writing under the pseudonym of Harry Dweighter ("harried waiter"). mathoverflow.net/questions/45185/… Oct 9 '14 at 4:29

This problem is known as ''pancake sorting'' or ''sorting by prefix reversal''. Imagine you have a stack of pancakes numbered $1,2,3,\ldots$ starting from the top. Then $t_k$ corresponds to taking the top $k-1$ pancakes and flipping them'' (as a stack). The minimum number of flips needed to reach any given arrangement (alternatively, the diameter of the corresponding Cayley graph) is a well-known problem. The exact number is not known, but some decent bounds are.