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

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

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

  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

    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

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

  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!

  11. October 22nd, 2018 at 02:16 | #11

    An ingenious construction in a 2013 paper by Aaron Williams on finding Hamiltonian paths through the Cayley graph of the symmetric group can be adapted to give shorter superpermutations for n > 6 than any of the other methods currently known.

    Williams uses a different pair of generators than this application requires, but it’s not hard to modify his results to use the relevant generators.

    I’ve written about this here:

    http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html

  12. Stephen
    October 27th, 2018 at 21:57 | #12

    Algorithm to solve minimum supermutations

    First calculate the max string which is the number of permutations multiplied by n.
    Then divide the max string by n – 1
    Then add to the answer the fibonacci number located at 2(n-3)

    int max_string = n! * n;
    int answer = max_string / (n – 1);
    answer += fib(2(n-3));

    Example for n = 5;

    max_string = 5! * 5 = 600
    answer = 600 / 4 = 150
    answer += fib(2(5-3)) = fib(4) = 3
    answer = 153

    Here is the first 14 using this method:

    2 -> 3
    3 -> 9
    4 -> 33
    5 -> 153
    6 -> 872
    7 -> 5901
    8 -> 46135
    9 -> 408384
    10 -> 4032377
    11 -> 43909467
    12 -> 522549784
    13 -> 6745945965
    14 -> 93884331311

  13. December 4th, 2018 at 11:31 | #13

    For n=3 length is 8: 12312132. Seems to me we are working with cycled numbers – it is ring, saying in other words. But we are are working with ring as if it is chain. Chain is realy 123121321 = 9, but the ring is 12312132 = 8 We take last 1 for 321 from the beginning of the sequence 12312132[1].

  1. No trackbacks yet.