## “Obvious” Does Not Imply “True”: The Minimal Superpermutation Conjecture is False

One of my favourite examples of an “obvious” mathematical statement that is actually false is the “fact” that if are vector spaces then

The reason that the above statement seems so obvious is that the similar fact *does* hold, so it’s very tempting to think “inclusion-exclusion, yadda yadda, it’s simple enough to prove that it’s not worth writing down or working through the details”. However, it’s not true: a counterexample is provided by 3 distinct lines through the origin in .

There is another problem that I’ve been thinking about for quite some time that is also “obvious”: the minimal superpermutation conjecture. This conjecture was so obvious, in fact, that it appeared as a question in a national programming contest in 1998. Well, last night Robin Houston posted a note on the arXiv showing that, despite being obvious, the conjecture is false [1].

### Superpermutations

What is the shortest string that contains each permutation of “123” as a contiguous substring? It is straightforward to check that “123121321” contains each of “123”, “132”, “213”, “231”, “312”, and “321” as substrings (i.e., it is a *superpermutation* of 3 symbols), and it’s not difficult to argue (or use a computer search to show) that it is the shortest string with this property.

Well, we can repeat this question for any number of symbols. I won’t repeat all of the details (because I already wrote about the problem here), but there is a natural recursive construction that takes an (n-1)-symbol superpermutation of length L and spits out an n-symbol superpermutation of length L+n!. This immediately gives us an n-symbol superpermutation of length 1! + 2! + 3! + … + n! for all n. Importantly, it seemed like this construction was the best we could do: computer search verifies that these superpermutations are the smallest possible, and are even unique, for n ≤ 4.

Furthermore, it is not difficult to come up with some lower bounds on the length of superpermutations that seem to suggest that we have found the right answer. A trivial argument shows that an n-symbol superpermutation must have length at least (n-1) + n!, since we need n characters for the first permutation, and 1 additional character for each of the remaining n!-1 permutations. This argument can be refined to show that a superpermutation must actually have length at least (n-2) + (n-1)! + n!, since there is no way to pack the permutations tightly enough so that each one only uses 1 additional character (spend a few minutes trying to construct superpermutations by hand and you’ll see this for yourself). In fact, we can even refine this argument further (see a not-so-pretty proof sketch here) to show that n-symbol superpermutations must have length at least (n-3) + (n-2)! + (n-1)! + n!.

A-ha! A pattern has emerged – surely we can just keep refining this argument over and over again to eventually get a lower bound of 1! + 2! + 3! + … + n!, which shows that the superpermutations we already have are indeed minimal, right? Some variant of this line of thought seemed to be where almost everyone’s mind went when introduced to this problem, and it seemed fairly convincing: this argument is more or less contained within the answers when this question was posted on MathExchange and on StackOverflow (although the authors are usually careful to state that their method only *appears* to be optimal), and this problem was presented as a programming question in the 1998 Turkish Informatics Olympiad (see the resulting thread here). Furthermore, even on pages where this was acknowledged to be a difficult open problem, it was sometimes claimed that it had been proved for n ≤ 11 (example).

For the above reasons, it was a long time before I was even convinced that this problem was indeed unsolved – it seemed like people had solved this problem but just found it not worth the effort of writing up a full proof, or that people had found a simple way to tackle the problem for moderately large values of n like 10 or 11 that I couldn’t even dream of handling.

### The Conjecture is False

It turns out that the minimal superpermutation conjecture is false for all n ≥ 6. That is, there exists a superpermutation of length strictly less than 1! + 2! + 3! + … + n! in all of these cases [1]. In particular, Robin Houston found the following 6-symbol superpermutation of length 872, which is smaller than the conjectured minimum length of 1! + 2! + … + 6! = 873:

12345612345162345126345123645132645136245136425136452136451234651234156234152634 15236415234615234165234125634125364125346125341625341265341235641235461235416235 41263541236541326543126453162435162431562431652431625431624531642531462531426531 42563142536142531645231465231456231452631452361452316453216453126435126431526431 25643215642315462315426315423615423165423156421356421536241536214536215436215346 21354621345621346521346251346215364215634216534216354216345216342516342156432516 43256143256413256431265432165432615342613542613452613425613426513426153246513246 53124635124631524631254632154632514632541632546132546312456321456324156324516324 56132456312465321465324165324615326415326145326154326514362514365214356214352614 35216435214635214365124361524361254361245361243561243651423561423516423514623514 263514236514326541362541365241356241352641352461352416352413654213654123

So not only are congratulations due to Robin for settling the conjecture, but a big “thank you” are due to him as well for (hopefully) convincing everyone that this problem is not as easy as it appears upon first glance.

**References**

- R. Houston.
*Tackling the Minimal Superpermutation Problem*. E-print: arXiv:1408.5108 [math.CO], 2014.

Thanks for this very nice write-up!

Very interesting! I even wrote a simple program to convince myself — this is indeed a superpermutation for n=6 of length 872. Congratulations Robin! 🙂

Curiously, my program found 147 positions within the sequence that do not correspond to permutations (e.g., 123451 starting on 7th position). This means that there are 872 (all positions) – 720 (correct permutations) – 147 (not permutations) – 5 (beginning of the sequence) = 0 repetitions of valid permutations. That is, permutations are never repeated. It is not obvious for me if this must hold in all shortest superpermutations. Robin, do you know if this is always the case?

@Andrey Mokhov That’s an excellent question. I’ve wondered the same thing. I’m pretty sure that permutations are never repeated in any of the minimal superpermutations we know about, but it isn’t obvious to me that must necessarily hold.

@Robin Houston – Yep, I’ll just confirm that there are no repetitions in any of the known minimal (or even formerly smallest but now known not to be minimal) superpermutations. But I also am not aware of a proof that this fact

musthold.@Robin Houston

@Nathaniel

Thank you! Perhaps, a search could be set up to find a 6-superpermutation of length 872, which contains 123456 twice. Due to symmetry, if we find such a superpermutation, it will generate a family of 720 solutions with all possible duplicates. On the other hand, if the search fails then there are no 6-superpermutations of length 872 with duplicates.

By the way, I just checked: Robin’s superpermutation doesn’t contain repetitions of non-permutations either. That is, all contiguous substrings of length 6 are distinct.

Thank you for this post. It’s very interesting and yet comprehensible. Same goes for the article, by the way. He used a nice transformation to interpret the problem as a directed travelling salesman problem, for which powerful solvers exist. Unfortunately no new key insights though..

Hi,

As per the arxiv paper should it be considered that the superpermutation problem is now resolved (in terms of algorithm to find one) ?

Thanks,

S

@Shishir – Nope, it’s only resolved in that we know the original conjecture is false. We still don’t have an algorithm for finding minimal superpermutations, and we still don’t even know how long minimal superpermutations are.

@Nathaniel

@Nathaniel – Thanks for your response. Do you reckon it makes for a good problem in quantum algorithm domain and whether anyone has already come up with one to solve this ?

Cheers,

S

@Shishir – I doubt anyone has already come up with a good algorithm for this problem, since it’s not a particularly famous problem, so I probably would have heard of any substantial progress on it.

I don’t really know if there would be a quantum algorithm that would outperform classical algorithms — I don’t even know if there’s a classical algorithm better than greedy search!