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

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

August 22nd, 2014

One of my favourite examples of an “obvious” mathematical statement that is actually false is the “fact” that if R,S,T \subseteq \mathbb{R}^n are vector spaces then

\dim(R + S + T) = \dim(R) + \dim(S) + \dim(T) \\ {}_{{}_{{}_{.}}}\quad\quad\quad\quad\quad\quad\quad\quad - \dim(R\cap S) -\dim(R\cap T) -\dim(S\cap T) \\ {}_{{}_{{}_{.}}}\quad\quad\quad\quad\quad\quad\quad\quad+\dim(R\cap S\cap T).

The reason that the above statement seems so obvious is that the similar fact \dim(R + S) = \dim(R) + \dim(S) - \dim(R\cap S) 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 \mathbb{R}^2.

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].


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:


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.


  1. R. Houston. Tackling the Minimal Superpermutation Problem. E-print: arXiv:1408.5108 [math.CO], 2014.
  1. August 22nd, 2014 at 12:54 | #1

    Thanks for this very nice write-up!

  2. Andrey Mokhov
    August 24th, 2014 at 10:32 | #2

    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?

  3. August 24th, 2014 at 17:18 | #3

    @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.

  4. August 24th, 2014 at 21:36 | #4

    @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 must hold.

  5. Andrey Mokhov
    August 25th, 2014 at 05:39 | #5

    @Robin Houston
    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.

  6. November 18th, 2014 at 19:26 | #6

    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..

  7. Shishir
    October 6th, 2015 at 04:37 | #7


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


  8. October 8th, 2015 at 06:23 | #8

    @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.

  9. Shishir
    October 8th, 2015 at 07:18 | #9

    @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 ?


  10. October 13th, 2015 at 13:04 | #10

    @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!

  1. No trackbacks yet.