New way of thinking about lower bound and maybe improvement
Marin Kisic
Hi,
A few weeks ago, I tried to improve the lower bound with GPT-5.6 Pro, and I got
S(k) >= k! + (k-1)! + (k-2)! + ceil(((k-2)! - (k-2)) / (2(k-1)(k-3) - 1)) + k - 3
for every k >= 5.
I spent several days trying to understand what is going on in the proof, and I believe it is correct. Here is a short summary in my own words:
In the proof, we introduce a graph in which each 2-cycle is a node, and two nodes are connected if they share a 1-cycle.
We consider three types of 2-cycles:
non-isolated;
isolated (called "tainted" in the PDF), but entered or exited through an edge that has slack;
isolated (called "good" in the PDF), with no incident edges having slack.
The proof establishes a bound for each of these three types and then obtains the final lower bound through straightforward calculations.
In the meantime, I saw that Raudvere posted an improvement which is stronger than this one. However, I think this proof uses a different approach, so I decided to post it anyway.
I also asked GPT-5.6 Pro to try to improve the lower bound further by combining ideas from both approaches. It produced a result that I have not been able to verify, since I do not understand the details of Raudvere's work well enough. If anyone would be willing to take a look at it, I would be very grateful.
The only kind of verification I have done is to open a few new chats and prompt the model with: "There is a mistake in this proof, find it!" Each time, however, it responded that the proof appeared to be correct.
The resulting bound is
S(k) >= k! + (k-1)! + (k-2)! + ceil(2*((k-2)! - (k-2)) / (k(k-3))) + k - 3
for every k >= 5.
Everything can be found here:
https://github.com/mkisic/superpermutations
I am sorry if any of this turns out to be AI-generated slop, although I am reasonably confident that at least the proof of the first lower bound is correct.
Marin
