Superpermutation of length 5906 for n=7

[Greg Egan]

Robin Houston’s idea for nonstandard kernels yielding shorter superpermutations for n=7 has been successful!

Last week, Robin generated some palindromic kernels with a score of 10, and using one of them, 666646664466646666, I was able to find a superpermutation of length 5906, speeding up the search by requiring the solution to share the symmetry of the kernel.  (This was done with my PermutationChains searcher, based on Bogdan Coanda’s methods, available to download from the GitHub repository.)

A few more details, and a link to the superpermutation itself, here:

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

This result was announced a few hours ago at a maths event where Matt Parker was speaking, and he arranged to have it “performed” on a self-playing piano ... keeping up the tradition of superpermutation results being published in strange venues!

[Greg Egan]

I’ve uploaded all the n=7, length 5906 superpermutations I’ve found so far to GitHub:

7_5906

There are 22 so far, from 5 different kernels. The file names tell you which kernel they came from. These are all palindromic kernels, and the solutions all share the symmetry of the kernel.

Also, I’ve uploaded a C program I use to search for non-standard kernels:

KernelFinder

[Robin Houston]

Here’s the sheet music as played last night, in case anyone would like to play it themselves. https://s3.boskent.com/superpermutations/7/5906-piano-score.pdf

--
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/480265a4-903d-4815-b2b8-14ae24156720%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Robin Houston]

The video Matt Parker filmed at the event has just been released: https://www.youtube.com/watch?v=_tpNuulTeSQ

[Greg Egan]

I want to summarise the results of some fairly extensive searches I’ve conducted recently. These are still ongoing, but they have already yielded a fair amount of information.

Search 1: Full two-fold symmetry

Using KernelFinder, I generated 1,572,390 palindromic kernels with scores of 10 or more, and lengths up to 60.

I then used PermutationChains to search for solutions starting from these kernels, with full two-fold symmetry.  That is, the solution, apart from the kernel, had to consist entirely of pairs of distinct 2-cycles mapped into each other by the same symmetry as mapped the permutations of the kernel into themselves in reversed order. (To be clear, by a palindromic kernel I mean that the description of it using Robin Houston’s notation is palindromic; the list of permutations that results is not a palindrome, but it can be mapped into itself by a suitable operation that includes swapping some pairs of digits.)

Of those 1,572,390 kernels, only 7 yielded solutions. As you can probably deduce by the fact that I even know this, all the kernels that don’t yield solutions result in searches that terminate very rapidly compared to those that do yield solutions. At the time of writing, the searches on 6 of the 7 kernels have completed, but one search is still running. The total number of solutions, currently, is 80, but I will keep updating the repository if and when any more are found.

The fruitful kernels all had scores of 10 (if there’d been one with a higher score, I’d be shouting about it!). They had lengths in Robin’s notation ranging from 18 to 26, and they covered between 100 and 140 1-cycles.  They are:

666466646646664666 with 49 solutions [and still running]

666646664466646666 with 9 solutions

56664666466466646665 with 2 solutions

6664664666446664664666 with 9 solutions

666366466646646664663666 with 1 solution

666646646636636646646666 with 8 solutions

66466466466644666466466466 with 2 solutions

Search 2: Generic kernels with a higher score

I also generated 13,294 completely generic kernels (i.e. with no special symmetries) with scores of 15 or more, and lengths up to 35.

I’ve been searching for completely generic solutions that start from any of these kernels. For lower-scoring kernels, generic searches take too long, but these higher-scoring kernels give searches that terminate relatively quickly.

The search is still ongoing, and of course it would be very exciting if there turns out to be a solution, because then we would have a superpermutation of length 7,905. But so far, it looks as if the result will be to exclude such shorter superpermutations (at least with kernels up to length 35).

[Greg Egan]

“Search 1” is now complete. It ended up with 83 solutions in total, which can all be found in the GitHub repository here:

7_5906

(The comments GitHub shows from earlier commits might be a bit confusing; all of these files are now complete, but only those which changed with the final commit have the word “complete” in their commit comment.)

[Gunther Leenaert]

Coincidence? 7!+6!+5!+4!+3!+2!+1! = 5913 Current sequence length = 5906 Difference of 7. Intuition tells me there will be no shorter sequence and the shortest possible superpermutations of n will always be of length (n! + n-1! + n-2! + ... + 1! ) - n and palindromic. If someone can make a proof out of this (or disprove, heh), then we have something to work with for all superpermutations.

Op zaterdag 2 maart 2019 23:41:19 UTC+1 schreef Greg Egan:

[Greg Egan]

> On 12 Mar 2019, at 5:46 pm, Gunther Leenaert <gunther....@gmail.com> wrote:
>
> Coincidence? 7!+6!+5!+4!+3!+2!+1! = 5913 Current sequence length = 5906 Difference of 7. Intuition tells me there will be no shorter sequence and the shortest possible superpermutations of n will always be of length (n! + n-1! + n-2! + ... + 1! ) - n and palindromic. If someone can make a proof out of this (or disprove, heh), then we have something to work with for all superpermutations.

We already know how to construct superpermutations for any n of length:

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

(See http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html for the detailed recipe.)

For n<=7, this is definitely not the best, and it probably isn't the best for higher n, but it still disproves your conjecture, because for n=8, it is 46205, which is 20 shorter than (n! + n-1! + n-2! + ... + 1!) - n = 46225, and the difference just gets bigger with greater n.

The most plausible conjectured minimum lengths at this point are:

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

or less.