Close the gap for the minimal superpermutation length on 6 symbols: 867 <= s(6) <= 872
Statement
A superpermutation on $n$ symbols is a string over the alphabet $\{1,\dots,n\}$ that contains every one of the $n!$ permutations of the symbols as a contiguous substring. Let $s(n)$ be the length of a shortest superpermutation. The exact values are $s(1)=1,\ s(2)=3,\ s(3)=9,\ s(4)=33,\ s(5)=153$. For $n=6$ the exact value is open: it is known that $867 \le s(6) \le 872$. Find a superpermutation on 6 symbols of length at most 871 (improving the upper bound), or prove $s(6) \ge 868$ (improving the lower bound), ideally pinning $s(6)$ exactly.
Acceptance. FULLY RESOLVES (upper bound): a string of length $\le 871$ over $\{1,\dots,6\}$ verified to contain all 720 permutations of $123456$ as substrings - checkable in milliseconds by sliding a length-6 window and collecting the set of permutations seen. FULLY RESOLVES (lower bound): a machine-checkable proof that no superpermutation of length $\le L$ exists for some $L \ge 867$, raising the lower bound. Pinning $s(6)$ exactly (matching bounds) fully settles it. PARTIAL: a construction matching the current record (872), or any verified improvement to either bound. Provide the string and/or the search certificate plus a verification script.
Background
Until 2018 the shortest superpermutations for all $n$ were conjectured to have length $\sum_{k=1}^{n} k!$ ($=873$ for $n=6$), but this was disproved: for $n \ge 6$ shorter superpermutations exist. The upper bound $s(6) \le 872$ comes from an explicit construction of the collaborative superpermutation project (2018-2019); see OEIS A180632. The best known lower bound $s(6) \ge 867$ follows from the general bound $s(n) \ge n! + (n-1)! + (n-2)! + n - 3$ (Egan, 2018, sharpening an argument first posted anonymously in 2011); see Johnston, 'The Minimal Superpermutation Problem' (njohnston.ca, 2013) and Egan et al., 'Tackling the Minimal Superpermutation Problem' (arXiv:1408.5108). A circulated claim that $s(6)=872$ exactly rests on an unverified exhaustive-search argument and is not an accepted proof, so the interval $[867,872]$ stands. Whether $s(6)$ equals 872, 871, or something smaller is open. Source: OEIS A180632 (minimal superpermutation lengths).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | OEIS A180632: minimal superpermutation lengths | link |
| REF-02 | Egan et al., Tackling the Minimal Superpermutation Problem (2014) | link |
| REF-03 | Johnston, The Minimal Superpermutation Problem (2013) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.