Shorter superpermutations for n>=7

[Greg Egan]

I believe the current state of the art is that for n<=5, the shortest superpermutations have been proved to be of length L(n), where:

L(n) = 1! + 2! + ... + n!

while for n>=6 this can be reduced by 1, by making use of the n=6 superpermutations of length 872 = L(6)-1 that Robin Houston discovered use TSP solvers.

If that’s correct, then I believe I now have a method for constructing substantially shorter superpermutations for n>=7.  Two examples can be found at:

http://www.gregegan.net/SCIENCE/Superpermutations/7_5909.txt

http://www.gregegan.net/SCIENCE/Superpermutations/8_46206.txt

which are of length L(7)-4 and L(8)-27 respectively.

These superpermutations are “tight”: no two consecutive characters are ever wasted. They are constructed from Hamiltonian paths through the Cayley graph for S_n generated by the permutations {left rotation, transposition of first two elements followed by two left rotations}.

To find the Hamiltonian paths, I adapted the method used in:

"Hamiltonicity of the Cayley Digraph ... " by Aaron Williams

https://arxiv.org/abs/1307.2549

which worked with a different pair of generators of the symmetric group.

I don’t yet have a formula for the lengths of these superpermutations, but I will post that if I’m able to derive it.

[Robin Houston]

Bravo!

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/e33bc7c9-dfde-4aed-a24c-2bf40f3ffcbf%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Greg Egan]

I just improved both of these results by one digit, down to 5908=L(7)-5 and 46205=L(8)-28.

Williams’ method yields two loops through S_n that can be spliced together at some point where a vertex of one is separated by a weight-1 edge from a vertex of the other. But I didn’t think to check carefully that I was optimising the choice of this splice by trying to ensure that it replaced a weight-2 edge on both loops.

The shorter examples are in these files:

http://www.gregegan.net/SCIENCE/Superpermutations/7_5908.txt

http://www.gregegan.net/SCIENCE/Superpermutations/8_46205.txt

[Greg Egan]

As well as the two earlier files (7_5909.txt and 8_46206.txt) being for suboptimal results, I realised there was a bug in the code that packed the permutations into strings, so I've deleted those files.

I’ve fixed the bug in the newer files, 7_5908.txt and 8_46205.txt, and double-checked that they’re correct, but feel free to check them yourself!

On Friday, October 19, 2018 at 6:24:21 PM UTC+8, Greg Egan wrote:

[Niles Johnson]

Thanks!  I can't tell yet whether your method will apply for general n (I think you implied it does?)  and to what extent you expect it to be minimal.  Comments on twitter made me think that the ones you've found match a theoretical lower bound, and are therefore minimal -- is that not correct?

--

You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/68cf05e4-693e-438a-95ac-6b289b73aa04%40googlegroups.com.

[Greg Egan]

The method yields results for all n>3, though for n=4,5,6 the results are definitely not minimal.

There is no obstacle to applying it to arbitrarily high n.  So far the fact that it yields shorter superpermutations than other methods is just empirical, and I have no proof that this will continue to be true for values of n where I haven’t actually carried out the construction.

Robin Houston noted that the lengths so far follow the formula:

n! + (n-1)! + (n-2)! + (n-3)! + (n-3)

but I don’t have any proof yet that this holds in general. If we can prove this holds for all n>3, then that will show that the method does better than previous approaches for all n>=7. I don’t know if anyone has shown that:

n! + (n-1)! + (n-2)! + (n-3)! + (n-3)

is a lower bound. There is a lower bound of:

n! + (n-1)! + (n-2)! + n – 3

mentioned at:

http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/

but that still leaves a gap of (n-3)!

[Greg Egan]

I have written up an account of how these superpermutations are obtained via a construction adapted from that of Aaron Williams (who uses a slightly different pair of permutations as the generators of the Cayley graph):

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

This includes a proof that the construction gives a length of:

n! + (n–1)! + (n–2)! + (n–3)! + n – 3

I’ve also included the C program I wrote, which generates one example for a given n.

Although I understand enough about Williams’s construction to describe it, and to code it, I’m still rereading the section where he proves that it does what it claims to do.  So if I come to grips with that, I might say something more about it later.

[Greg Egan]

Williams also gives some “local rules” for determining which Cayley graph edge to follow from a given permutation, solely by inspecting that permutation, and I have now derived the equivalent rules for our own application.  They are described here:

Local Rules

[Nathaniel Johnston]

Apologies if this has been discussed elsewhere and I missed it, but has anyone tried combining Greg Egan's and Robin Houston's approaches? Robin's approach was to use TSP solvers like LKH and Concorde to computationally solve this problem, possibly given a restriction on the edge weight. Greg Egan's approach instead restricts the set of generating permutations rather than the edge weights (though of course his particular set of permutations restricts the edge weights to never be more than 2).

So my questions are:

1) Are Concorde/LKH fast enough to rediscover the n = 6 superpermutation of length 873 that Greg's method gives, if instead of specifying weight <= 2, it specifies that each permutation should have exactly two edges in the graph (one corresponding to sigma = 234...n1 and one more corresponding to delta = 345...n21)? This should be much faster to search through than the weight-2 graph since each vertex will only have 2 edges instead of 3, and now every edge connected to a vertex has a different weight, which should make pathing decisions through the graph much simpler.

2) If the answer to (1) is "yes", are they fast enough to handle the n = 7 case? n = 8?

3) If the answer to (1) is "yes", what if we add a third permutation to the generating list, on top of sigma and delta? In particular, what if we add something like tau = 456...n321? This allows for edges of weight 3, but it should be *far* easier to search through than the graph with *all* edges of weight <= 3 (or even the graph of all edges of weight <= 2), while at the same time guaranteeing that strings at least as short as Greg's are found.

Cheers.

[Jay Pantone]

Vince Vatter and I initially tried to answer these questions back in February when we got interested in the problem. I ran Concorde on the n=6 graph with edges only of weight 1 and 2. After about 3 million seconds of CPU time, the processes slowed to a halt and I couldn't figure out why, so I gave up. A few weeks ago I dove back in (motivated by Greg Egan's new results), and learned a little more about Concorde. Now it's at about 11 million seconds of CPU time, and still doesn't look to be anywhere close to finishing. 

We also tried a version with only a single proper weight 3 step, with no luck. I'm not optimistic that Concorde can answer any version of the n=6 question, unless those who wrote it back in the early 2000s know of some kind of manual pre-parsing that might help.