“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 \(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
- 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 must hold.
@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!
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
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
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].