Conditions on the Possibility of 871-Length Superpermutations on n=6

[Cole Fritsch]

As a warning, all of this information depends upon my lower bound that has not yet been proof-read or agreed upon by others.

I decided to look into Superpermutations (SPs) again briefly. One of the things that I have known about for a while but haven't really expressed yet for some reason is how close my bound is to showing that 872 is the shortest length for a SP of n=6. The bound currently gives a number strictly between 870 and 871, meaning it must be of length at least 871 (must be an integer). If we assume an SP of length 871 exists, a few more conditions can be created as well:

(1) The SP must not contain a 5-edge (mustn't have 4 consecutive wasted symbols).

(2) Cannot have "early exits" (If a previously unvisited 1-cycle is entered, it must be completed by a series of 1-edges before leaving the 1-cycle).

(3) Must contain a "strange edge" (14 edge-transitions that will be explained later).

Condition (1) comes from taking two of my constructions used for my lower bound that sum to a length of 6!=720 permutations and connecting them by a 5-edge. This construction represents a lower bound on an SP of n=6 that includes a 5-edge. The resulting length is 872, meaning a 5-edge cannot be used for a 871 length SP.

Condition (2) comes from Zach Hunter's concept of "splitting paths"/"peripheral paths" which is the foundation for his bound and my improvement. The idea is a little too complicated to explain here. The inefficient nature even just one of these early exists is enough to make the minimum length at least 872.

Condition (3) is a result of the "z-end" concept that I discovered. If the following conditions are met then a special transformation can be made:

(a) The path is "exitless" (has no early exits).

(b) Every edge other than a 1-edge must move the first symbol of the initial permutation to be the last symbol of the terminal permutation.

Condition (a) is ensured by (2). "Strange edges", as described in (3), are edges that do not follow condition (b). If both conditions hold, then the first permutation visited in every 1-cycle will always have the same last symbol (hence "z-end"). Furthermore, we can make a transformation where we turn our n=6 path into a n=5 path; this can be done by turning each n=6 1-cycle into a n=5 permutation, labeled by the first visited permutation of its 1-cycle (with the last symbol dropped). Additionally, each edge will be altered to match as well. All 1-edges will be dropped and each k-edge will become a (k-1)-edge for arbitrary k>1. This will decrease the length by 6!=720. The inverse also holds as long as (a) and (b) are true: since 153 is the minimum length for n=5, 6!+153=873 is the minimum length for n=6 under. For an SP of length 871 to exist, (b) must not hold, therefore a "strange edge" exists.

There are 4 3-edges and 18 4-edges that fit the criteria. However, 2 3-edges and 6 4-edges can be thrown out, because they can be "decomposed" into a series of operations ending with a 1-edge. Because the decomposed set of operations was not used itself, it implies that the permutation a 1-edge behind was already visited, but the permutation after the 1-edge hadn't been visited -- this cannot happen unless an early exit was made which is thrown out by (2).

These 14 operations are the following:

123456 --> 456132

123456 --> 456312

123456 --> 561243

123456 --> 562143

123456 --> 561423

123456 --> 564123

123456 --> 562413

123456 --> 564213

123456 --> 561342

123456 --> 563142

123456 --> 561432

123456 --> 564132

123456 --> 563412

123456 --> 564312

It should not be too difficult to remove some of the 4-edges from the list, but the 3-edges appear to be problematic. However, if we can throw out any potential of a 871 length SP under these strange edges, then 872 will be the minimum-length SP for n=6.

Below is the link to my proof for the lower bound, but it is unfinished, because I lost interest. The proof is all there, but it is terribly hard to read, because of my writing skills and the nature of what I am writing about (I really need more visual aids and diagrams):

https://www.overleaf.com/read/qptbxxwrhwhh 

If you have any questions, feel free to ask. This information is built upon a year's worth of me swimming in my own notation and terminology, so I totally understand if it makes no sense.

- Cole Fritsch

[Cole Fritsch]

If I am understanding the concept of kernels and extensions correctly, then extensions are affectively the same as peripheral paths, meaning a 871 length SP must be one big kernel with no extensions.

In short, the solution would have to be very weird.