Updates to spreadsheet of bounds

[Miles Gould]

In light of the onslaught of progress we've seen this week, I've made some updates to the spreadsheet of known bounds (Superpermutation bounds - Google Sheets):

1. I've added Uku Raudvere's improvement to the Anon-Houston-Pantone-Vatter lower bound.
2. I've fixed the overflow in the n=14 and n=15 terms of Zach Hunter's lower bound, and removed the "correctness uncertain" caveat.
3. I've added Uku's formalised version of the Hunter lower bound - this dominates the AHPV bound (and the Raudvere lower bound for n > 5), but is sometimes one less than Zach's original sequence. Unless I've got something wrong?
4. I've marked 872 for n=6 as "known optimal" in light of Vlad Gheorghe and Benjamin Grayzel's independent proofs.
5. I've added new best-known superpermutations found by Uku Raudvere, William Echols and Theo H for n in {7, 8, ..., 13}. It's still not clear how the n = 7, 8 or 9 examples were found, so I've marked them as "Unclear (LLM assisted)".
6. I've made the "Search space" column compare the best-known value for n with the best-known lower bound for n.

I guess it's possible we'll have to retract edit #4 if both Vlad and Benjamin's proofs turn out to have bugs, but that's what edit history is for 😅

Am I right in thinking that superpermutation-examples/formal at main · urdvr/superpermutation-examples provides a nonconstructive existence proof of superpermutations of length E(n) - 1, where E is the Egan-Williams length? Or can it be used to calculate actual examples?

Also, have I missed anything? A lot has happened in the last few days.

Cheers,

Miles

[William Echols]

Thank you for bringing everything together!

The n=9 and n=10 superpermutations of length E(n) - 1 were found by lifting Raudvere's n=8 superpermutation. The same lift works for at least n=10->11 and n=11->12. I believe that Raudvere likely found the same lift and based his existence proof on it.  

[Robin Houston]

Is there a reason you didn’t include a column for Raudvere’s new upper bound (https://github.com/urdvr/superpermutation-examples/tree/main/formal) that is 1 less than the Egan bound?

Robin

--
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/9965cf6e-7001-4187-9aef-534c724938c4n%40googlegroups.com.

[Miles Gould]

Mainly that I didn't understand its scope, but I have now added it (and updated the "best known" column for n=14 and n=15).

Miles

To view this discussion, visit https://groups.google.com/d/msgid/superpermutators/CAD9Xfq0j18KFQZXH4ZbBtFuFxCeWwmx3NC%3DenXLBOmA8FSBVJg%40mail.gmail.com.