New upper bound: Superpermutations of length n! + (n-1)! + (n-2)! + (43/80 + o(1))(n-3)!

[Jay Pantone]

Hi all,

With the help of ChatGPT 6 Astra (and a bit of Claude Opus 5.5), I've proved that

    S(n) <= n! + (n-1)! + (n-2)! + (43/80 + o(1))*(n-3)!,

lowering the coefficient of (n-3)! from the 1 in Egan's construction and Raudvere's improvement to 43/80. The proof is formalized in Lean.

New upper bounds, with the previous best (Egan - 1 for n>=9, this morning's post for n=8) in parentheses:
    n = 8:          46,181   (46,188)
    n = 9:         408,736   (408,965)
    n = 10:      4,034,894   (4,037,046)
    n = 11:     43,930,689   (43,948,807)
    n = 12:    522,748,520   (522,910,088)
    n = 13:  6,747,967,798   (6,749,568,009)

The words for n=9 to 11 come from the construction followed by a computer search to find local improvements.

That construction gives shorter superpermutations at all lengths >= 8, but also you can push a little further and lower the 43/80 = 0.5375 constant to 4061/7560 ~ 0.53717. I didn't think it was worth formalizing this small improvement, but nonetheless you can use it to get shorter words for n=12 and 13 above. I chose not to go past n=13 because that word already required nearly 7gb of disk space to store.

I put this in a git repo: https://github.com/jaypantone/superperm-upper-43-80. It has:
 - a brief summary, largely written by Opus 5.5 but edited by me, in docs/upper-bound-explained.pdf
 - the lean formalization
 - the new shortest words (compressed with xz for the longer ones)

The summary also mentions a lower bound improvement that I've formalized in Lean but haven't posted yet, because I want to write a good summary explainer for it first.

- Jay

[William Echols]

Wow, this is great!

Based on your comment that shorter n >= 12 are possible, I used GPT-6.1 Sol to find a superpermutation in n=12 with length 522,748,475 (shorter by 45). I'm looking forward to reading your explainer for the lower bound improvement.

[Jay Pantone]

Nice! I'm sure there is lots of room for improvement from these larger ones. The construction is inefficient, and right away some characters can be deleted, and some ad hoc rearranging can be done. I spent a fair amount of computation time searching for these improvements for n up to 11 but much less for n=12 and 13 given their size. Did Sol give any sense of how it found the improvement?

[William Echols]

According to Sol:

The improvement uses the same principle as Pantone's piece assembly: retain the
permutations already present inside pieces while improving their joins. Here the
pieces are finer than whole Eulerian components. The source word was split into
25,205 contiguous pieces whenever adjacent valid permutation windows started at
least four positions apart. Each piece begins at its first valid permutation
window and ends after its last one. Every valid window of the source lies wholly
inside a retained piece. The optimizer relocates blocks of consecutive pieces
and joins them using exact suffix-prefix overlaps of at most 11 letters.
Each move therefore preserves coverage. Eighteen moves saved 45 letters; the

sequence of gains was `5,5,4,4,3,3,2,2,1,5,1,3,2,1,1,1,1,1`.

[Jay Pantone]

Inspired by William, I tasked two instances of Opus 5.5 and two instances of Astra 6 to work together to find local improvements in the words. After about a day of work, they improved n=9 and above. Essentially this is about working harder to put the puzzle pieces together more efficiently. My github repo is updated with these new words. I'm sure there is still room for more local improvement!

The updated table of known words is now:
    n = 8:          46,181
    n = 9:         408,732
    n = 10:      4,034,889
    n = 11:     43,930,680
    n = 12:    522,745,581
    n = 13:  6,747,918,066

The improvements from my earlier words to these are:
n=8:   still 46,181
n=9:        408,736  ->       408,732        (-4)
n=10:     4,034,894  ->      4,034,889       (-5)
n=11:    43,930,689  ->     43,930,680       (-9)
n=12:   522,748,520  ->    522,745,581   (-2,939)
n=13: 6,747,967,798  ->  6,747,918,066  (-49,732)

[Theo H.]

To Jay and William,

This work is really impressive. I will try to find the time to read your summary, but it looks really complete. I have been really busy and initially I didn't read this thread because I only read the title, and I thought it was just a theoretical improvement. Well done on all the words.
Anyways, I managed to take off 2 symbols from your n=11 superpermutation (43,930,678) and I submitted a PR here: https://github.com/jaypantone/superperm-upper-43-80/pull/2/

I am excited to see the discovered words converge with your upper bound, and more convergence between the upper and lower bounds in the future

-T

--
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 view this discussion, visit https://groups.google.com/d/msgid/superpermutators/2ed5939a-ccb8-401b-9689-a77f9eea5ebbn%40googlegroups.com.

[Jakub Halfar]

Hi all,

Thanks to Jay for the construction and for publishing the words. I've been working on them with Claude Opus 5.5 in Claude Code, and we have three shorter words built from Jay's pieces:

    n = 11:     43,930,628   (43,930,668, rumstd's PR #4)
    n = 12:    522,745,538   (522,745,581)
    n = 13:  6,747,918,058   (6,747,918,066)

The pieces are exactly Jay's. What changes is where each one is cut open and the order they are joined in. Most of the gain for n=11 and n=12 comes from rumstd's trick in the n=10 word: cutting a piece open between two 2-cycles costs one letter, but then pieces can chain with no join cost. For n=13 we have only reordered the runs so far, so I expect there is more to find.

All three pass Jay's literal_check, and no single letter can be deleted. Words, tools and details are at https://github.com/jhalfar/superpermutations, and the words are in PR #5 to Jay's repo. I'd be glad if someone could check them independently.

Best,
Jakub

[Theo H.]

To Jakub and all,

What an improvement! How did you get such a massive 40 below savings?

After some effort, I managed to slightly shrink the n=11 and n=12 superpermutations you submitted using numerical methods.

With some good old fashioned dynamic programming, I was able to turn phase placement of Jay's closed trail beginnings into a minimization problem (aided by ChatGPT). This did not produce any gains below n=11 using my existing approach.

For n=11, Solving took one core about 46 seconds and produced length 43,930,624 from the previous record seed. 

For n=12, Solving took one core 20 minutes and produced length 522,745,531 from the previous record seed.

n=13 is still running on my computer and hasn't finished. I have no proof this construction is guaranteed to be shorter.

n = 11:     43,930,624   (43,930,628, jhalfar's PR #5)

n = 12:    522,745,531   (522,745,538, jhalfar's PR #5  )

I added some tooling, a corpus, and a tex document of the math to a github repo. I also submitted to Jay's repo (PR #6, PR#7)
Both superpermutations have been validated with Jay's  literal_check  and my own checker/waste printer/reduced alphabet program I included in the repo.

One of the restrictions that I dropped in order to achieve the solve was the restriction that a trail must open at a boundary between constituent 2-cycles.
The solver allows every assigned permutation-window start, including inside a constituent 1-cycle, and calculates how far each opening must extend to preserve coverage.

The methodology of the solver allows changes to be expensive locally. All costs are optimized jointly, so cost increases at one join can be repaid elsewhere.

Importantly, we retain all 2800 of Jay's closed trails, internal traversal sequences, order, and full assigned coverage.

Best,
Theo H.

P.S. 

[Jakub Halfar]

Hi Theo, hi all,

Thanks, and really nice work on the dynamic programming! To your question: the 40 letters at n = 11 came from a local search over the closed trails. It takes a few trails out and puts each one back wherever it fits best, and it can also choose where to cut the trail open. What worked in the end was making the cuts between two 2-cycles (rumstd's trick from the n = 10 word).

The cut inside a 1-cycle is the part I hadn't thought of. I use it in my n = 12 word now, so thanks for that one. As for the DP itself, I had a fixed-order DP of my own running that same night. My 522,745,531 was in my repo a few hours before your PR #7, and it's a different word from yours, so it looks like we both got there independently.

The words have got shorter since then:

n = 11: 43,930,614 (43,930,624, Theo's PR #6)
n = 12: 522,745,355 (522,745,531, Theo's PR #7)
n = 13: 6,747,916,917 (6,747,918,058 in my last post)

The DP settles the cuts for a given order of the pieces, so after it the gain has to come from changing the order. The move that helped most is basically 3-opt from TSP without any reversal. I cut the sequence of pieces in three places, swap the two middle parts and run the DP again on the whole new sequence to see if it got shorter. Today this took the n = 13 word down by 504 letters in about an hour, which is the biggest single step so far. It is now 1,149 below Jay's.

n = 11 and n = 12 pass Jay's literal_check with --deletions. For n = 13 that test needs about 13 GB here, so I wrote a version that needs 1.6 GB (delcheck.c in my repo), in case it is useful for your n = 13 run. Did that one finish?

Words and the plans to rebuild them: https://github.com/jhalfar/superpermutations and PR #8.

Best,
Jakub

[Theo H.]

Hi Jakub,

Hats off to you, I hand the crown back. It looks like we were thinking along similar lines at almost exactly the same time.

My n=13 search finished but the gain was only 11 characters from your record. I will upload later, but given your very effective optimization, I don't think it would be useful even for structure probing.

I will try to find some time to check out your repo and get an idea of the other differences in our DP. It has been really fun to go back and forth with these words.
Thank you for the explanation, I know a lot more now than I would have just dissecting your words. Take care and happy searching.

Best,

Theo H.

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/c7dc6934-313a-47e7-a011-b1615188f404n%40googlegroups.com.

[Miles Gould]

Wow! I've updated the spreadsheet with your results - well done, everyone! What does this tell us about the upper bounds for n=14 and n=15?

https://docs.google.com/spreadsheets/d/1m8mHizDHoDpT-9ohCiqmfKyQI6gmhuyuzb7TC7362Ko/edit?usp=sharing

[That link should allow anyone to suggest edits, which I can then accept or reject]

Thanks,

Miles

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/CA%2BPW3N--3HbMd3yWOM1NVR38KMfz_BP_v-g8Z8i%3D1mQ-3nJfAQ%40mail.gmail.com.

[Jakub Halfar]

Hi all,

I have new words for n = 10, 11, 12 and 13:

    n = 10:      4,034,873 ->      4,034,855  (-18, previous: rumstd)
    n = 11:     43,930,624 ->     43,930,578  (-46, previous: Theo H.)
    n = 12:    522,745,531 ->    522,737,299  (-8,232, previous: Theo H.)
    n = 13:  6,747,918,066 ->  6,747,802,875  (-115,191, previous: Jay Pantone)

I think this is a breakthrough for words made with this construction. Everything I did before kept Jay's closed trails and only changed the cuts and the order, and all of it together gave 1,409 letters at n = 13. These words use other closed trails.

After four days of rearranging, my own bounds said little was left: at n = 11 at most 133 letters with one cut per trail. So I looked at where the letters of the construction go. In Jay's selection one 2-loop in fifteen lies on an all-full trail, and an all-full trail completes to as many closed trails as it has slices. At n = 12 that is 24,192 of the 25,200 closed trails, and every closed trail costs at least a letter to join.

These 2-loops fall into 48 groups, and the slices of a group can be chosen again without touching the rest. With full and short slices only, a new choice already gave an n = 12 word 324 letters under my best one before any search had run. With slices that are neither full nor short it gets better: 3,648 closed trails at n = 12 where Jay's selection has 25,200, and 23,808 at n = 13 where it has 252,000. Completion works for such slices as it stands. Transport is defined for full and short slices only and I found no rule for the others, so n = 11, 12 and 13 each have a selection of their own. The construction is still Jay's and only the selection changes.

The many small closed trails that remain have to be written in chains, which an integer programme chooses. The n = 10 word is made differently: it has the structure of rumstd's word on a selection with 350 closed trails where Jay's has 364, with every cut chosen exactly.

Written as n! + (n-1)! + (n-2)! + c (n-3)!, my n = 12 word has c = 0.5239 and my n = 13 word has c = 0.5136. Jay's words have 0.5467 and 0.5453, and 43/80 is 0.5375. That is just the lengths of verified words and says nothing about the limit.

For the limit I have computation and no proof. One of the new selections has only full and short slices, so it can be transported to every n. The count behind Jay's 193/360, Q plus the number of closed trails, gives 193/378 = 0.5106 for it at n = 12 and n = 13. With connector cycles chosen at n = 12, Jay's argument would give 1771/3456 = 0.5124 in place of 43/80. I checked the hypotheses of his argument for this selection by computation only. Writing the proof down is what I want to do next, in Lean if Jay's certificates can take this selection. I haven't started, so please treat 0.5124 as a claim to be checked.

All four words pass Jay's literal_check --deletions, my delcheck and a short numpy script. The three programs share no code, and no single letter can be deleted. Each word can be rebuilt from its selection and a list of its closed trails in order with their cuts, with Python and a C compiler. Words, selections, tools and notes on every step, including what did not work, are at https://github.com/jhalfar/superpermutations, and the words are in PR #8 to Jay's repo. The programs behind my words of the last days are public only as of today.

The selections are the best I found and I don't know whether they are optimal, so there may be more to gain. I'd be glad if someone could check the words and the selections independently.

Best,
Jakub