Shorter superpermutations for n=7?

[Robin Houston]

I think there are probably superpermutations for n=7 that are shorter than 5907. If I am right, that implies there are, in general, superpermutations shorter than

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

symbols, contradicting our working conjecture.

We’ve been looking at superpermutations consisting of a kernel of some number of 3-cycles, with the rest of the 2-cycles attached as a tree. But there is no reason to restrict ourselves to kernels of this form, and:

• There are superpermutations that use other kernels, for n=6;
• There are many potential kernels for n=7 that, if they can be completed to superpermutations, would yield superpermutations shorter than 5907.

I‘ve been looking at kernels that consist of complete 1-cycles – i.e. whenever they enter a 1-cycle, they traverse the whole 1-cycle before leaving – and that never enter a 2-cycle that has been entered before.

As a convenient notation for kernels, let’s write a sequence of numbers showing how many 1-cycles are followed before leaving the 2-cycle. I’ll also write a space to indicate where a (standard) weight-4 edge is used.

The three kernels we have considered for n=6 so far are denoted:

5555

5555 5555

5555 5555 5555

It’s easy to count how many 1-cycles a kernel covers: just add up the digits.

To work out whether it’s possible arithmetically to complete the kernel to a superpermutation, and if so how long the superpermutation will be, we need another measure that I call the score of the kernel, which I’ll explain now.

Our baseline is that each 2-cycle should cover (n-2) 1-cycles, and the score measures the efficiency of the kernel relative to that benchmark. So each digit d contributes (d - (n-2)) to the score. A space represents a unit of slack, and a unit of slack is as bad as a whole 2-cycle, so a space contributes -(n-2).

For example, all the n=6 kernels listed above have a score of 4.

If the score is a multiple of (n-2), then it is arithmetically possible to complete the kernel to a superpermutation. If the score is k(n-2) then the resulting superpermutation has length:

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

For n=6 there are many kernels (of the form I’ve been considering) with score 4, and two that have a score of 8:

• 5553553555 5553553555

• 5553553552552553553555

I have checked that neither of these can be completed to a superpermutation, so it’s not unreasonable to think that 872 is minimal for n=6. But for larger n, there are many many possible kernels that would give rise to shorter superpermutations than we’ve been considering so far, and – unless there’s some obstruction we haven’t thought about – it seems likely that some of them will be completable.

I checked all the kernels with score 4, and found 1024 new superpermutations for n=6 that use one of these non-standard kernels. The list is here: https://github.com/superpermutators/superperm/blob/master/superpermutations/6/872-nonstandard.txt

Here are a couple of kernels for n=7 that have score 15 – so if they could be completed, they would give rise to superpermutations of length 5905:

• 666646664666466466646664666
• 66664666466646646664466646666

There are many more possibilities here! These are just two shortish ones that I haven’t been able to rule out.

Cheers,

Robin

[Robin Houston]

Someone asked off list which kernels for n=6 can be completed to superpermutations. In case it’s useful for anyone else, here’s the list of kernels that could be completed to a superpermutation, together with the number of superpermutations found for each of them.

These are listed in the same order as the list of superpermutations. I.e. the first eight superpermutations in the list have kernel 5555 555355, the ninth has kernel 5555 553555, and so on. (You can see in this list that – unsurprisingly – for the kernels that are not palindromic, reversing the kernel yields the same number of superpermutations.)

5555 555355: 8

5555 553555: 1

555355: 470

5553554: 6

55535535: 2

555355255: 9

555355 5555: 1

55533555: 4

5552555: 26

555255355: 1

553555: 470

553555 5555: 8

553552555: 1

552553555: 9

53553555: 2

4553555: 6

[Greg Egan]

I've now added an option to the PermutationChains program in the GitHub repository that lets it handle these kinds of non-standard kernels. For example:

PermutationChains 6 nsk555355

gives 470 solutions — and overall, I get the same 1024 solutions as Robin Houston obtained from the kernels he listed.

I started it running on the two kernels Robin mentioned for n=7, but no solutions have been found yet ...

[Robin Houston]

A small clarification:

On Sun, 24 Feb 2019 at 14:52, Robin Houston <robin....@gmail.com> wrote:

To work out whether it’s possible arithmetically to complete the kernel to a superpermutation, and if so how long the superpermutation will be, we need another measure that I call the score of the kernel, which I’ll explain now.

We don’t need the score just to check whether it’s possible arithmetically to complete the kernel to a superpermutation. For that we can just check whether the number of 1-cycles covered (the sum of the digits of the kernel) is a multiple of (n-2).

The purpose of the score is to work out how long the resulting superpermutation will be.

(The score is congruent, modulo (n-2), to the number of 1-cycles in the kernel; so in particular the number of 1-cycles is a multiple of (n-2) just when the score is.)

[Keith Garner]

Can you send me a full list of the kernels for 7 that would result in a superpermutation less than 5907