A smaller upper bound for superpermutations

Get email updates

Jay Pantone

Let S(n)S(n) be the minimum length of a word containing all permutations of n symbols as contiguous blocks. Pantone’s construction proves S(n)≤n!+(n−1)!+(n−2)!+(926683/1814400+o(1))(n−3)!S(n) \le n! + (n-1)! + (n-2)! + (926683/1814400 + o(1))(n-3)!.

What was already known

The new coefficient is about 0.510738, below Pantone’s earlier 43/80 and Halfar’s announced 1771/3456. It exceeds one half.

AI involvement AI-led

Pantone directed the research. The project attributes the new finite selection, smaller connector cover, manuscript and formal proof to AI, and separately credits inherited mathematics and code.

Importance Notable

The construction lowers a general asymptotic coefficient beyond the cited earlier bounds.

Technical verification Formal (Lean)

The pinned package reports Lean 4.35.0 builds and NanoDa replay for the explicit finite bound for n≥14n \ge 14 and the asymptotic bound, using the three standard axioms.

Formal checking

The pinned package reports Lean 4.35.0 builds and NanoDa replay for the explicit finite bound for n≥14n \ge 14 and the asymptotic bound, using the three standard axioms.

Checker
Jay Pantone, reporting Lean 4 verification
Scope
The pinned package reports Lean 4.35.0 builds and NanoDa replay for the explicit finite bound for n≥14n \ge 14 and the asymptotic bound, using the three standard axioms.
Basis
Reported by the linked checker

Human understanding Few

The released explanation is attributed to AI. The source does not document a human explanation of the new connector argument.

Correction and publication history