Shortest superpermutations

A superpermutation is a word that contains every ordering of n different symbols as a contiguous block. How short can such a word be?

Why it matters and what counts as progress

Why it matters: Adjacent permutation blocks can overlap. Shorter constructions find ways to reuse more positions, and lower bounds limit the amount of reuse possible in any word.

What counts as progress: Construct a shorter covering word or prove that every covering word has at least a stated length. Separate bounds for a specific alphabet size from bounds that hold as the alphabet grows.

How the problem developed

  1. 6 Oct 2026 · Earlier all-size bounds [1]

    Superpermutators community Jakub Halfar announced a new upper coefficient and formal verification of Cole Fritsch’s general lower bound, alongside finite bounds.

  2. 27 Oct 2026 · New asymptotic bounds [2]

    Jay Pantone with AI assistance Jay Pantone’s projects sharpen the upper coefficient and improve lower-order terms in the general lower bound. The projects credit AI with the new research and keep prior constructions and search tools separately attributed.

  3. 27 Oct 2026 · New lower bound [3]

    Jay Pantone with AI assistance The results improve a general lower bound below its leading correction and give separate finite refinements.

AI contributions 2

Chain returns and lower bounds for superpermutations

Jay Pantone

Pantone reports two lower bounds on minimum superpermutation length for n≥8n \ge 8. Both add a leading correction of (2+o(1))(n−4)!(2+o(1))(n-4)! to n!+(n−1)!+(n−2)!n! + (n-1)! + (n-2)!. The exact-order formula improves the cited general bound in lower-order terms for all sufficiently large n.

AI involvementAI-led
ImportanceModest
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

A smaller upper bound for superpermutations

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)!.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. Halfar’s 6 October upper and lower bounds
  2. A smaller upper bound for superpermutations
  3. Chain returns and lower bounds for superpermutations
  4. Pinned theorem, provenance and checking record
  5. Pinned theorem, provenance and checking record
  6. Pantone’s earlier 43/80 construction
Publication history