Combinatorics of words and permutation overlaps

Shortest superpermutations: general case

Collaboration beta

Find the shortest word that contains every permutation of n symbols as a contiguous block. The source reports exact and bounded small cases, general lower-bound machinery, and an eight-symbol construction that still needs an integral completion.

S (n) = \min {| w | : every π \in S_{n} occurs contiguously in w}, n \geq 1

Known results and sources

Illustration: A permutation must occur in consecutive positions. The nine-symbol word is a small example.

Research problem

Exact mathematical statement

For every integer $n\ge1$ , let $[n]=\{1,…,n\}$ and let $\mathfrak S_n$ denote its permutations. Determine

S(n)=\min\left\{|w|: \ w\in[n]^*, \forall\pi\in\mathfrak S_n\ \exists i\in\{1,…,|w|-n+1\}: (w_i,…,w_{i+n-1})=\pi\right\}.

Length counts symbols. Labels and permutation windows may repeat, and other windows are allowed. For $n\ge10$ , labels must be separated rather than read as decimal digits. The full target requires matching constructions and lower bounds, or another resolving determination for every $n$ ; an equivalent Hamiltonian-path formulation alone does not solve it.

Problem infographic

Problem at a glance

Illustration: The word 123121321 contains six displayed three-symbol permutation windows, beside the rules and the general minimum-length question. — Illustration: Every permutation must appear consecutively; repeats and extra windows are allowed. The exact minimum for general n is the open target.

Current mathematical picture

Where work on Shortest superpermutations: general case stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureInferring integrality from attachment equations and rooted cuts

The root and disjoint triples A,B,C,D,E,F use child sets A+B,A+C,B+C,D+E,D+F,E+F with weight one-half each. A rounding theorem must exploit actual insertion structure; the strong rational point neither proves nor refutes an integral tree for the concrete kernel.

Route status · Narrowed route

Main reductionCurrent reduction

The exact directed-overlap Hamiltonian-path model preserves repeated windows. Normalized-path coarsening and defect budgets lead to a general lower-bound route based on attainable row surplus and minimum integral completion loss. Separately, the fixed eight-symbol kernel needs a rooted tree of 822 distinct allowed full blocks before any 46203-word conclusion.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeControl attainable row surplus jointly with unavoidable integral completion loss on the actual insertion-incidence families for all degrees.Task status · Ready to work on

Work mapped so far

Shortest superpermutations: general case in numbers

1.1kretained lines of mathematical investigation1,067 in the current working snapshot

Argument development: 638 · 60%
Explored or eliminated routes: 64 · 6%
Computational analysis: 91 · 9%
Open obligations: 168 · 16%
Definitions and setup: 106 · 10%

9selected mapped statements2routes investigated3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedSep 7, 2026

Source recordedSep 7, 2026

Recommended next task

Control attainable row surplus jointly with unavoidable integral completion loss on the actual insertion-incidence families for all degrees.

Suggested move: Suggested next step: Prove a joint inequality on normalized-path root blocks with the exact available graph and defect hypotheses, and supply matching constructions where needed instead of optimizing row and cover data separately.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

14 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded

Narrowed routeInferring integrality from attachment equations and rooted cuts

Route status · Narrowed route

Narrowed routeDeletion-only retargeting of the explicit classical degree-eight family

All ten representatives surviving the modular filter fail the exact forest dynamic program after the complete relabelling reduction. Adding blocks, changing the kernel, using a different 833-attachment forest, or solving unrestricted integral completion remains outside this exclusion.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Control attainable row surplus jointly with unavoidable integral completion loss on the actual insertion-incidence families for all degrees.Suggested move: Suggested next step: Prove a joint inequality on normalized-path root blocks with the exact available graph and defect hypotheses, and supply matching constructions where needed instead of optimizing row and cover data separately.

Ready to work on

Find 822 whole attachments forming a rooted incidence tree for the fixed eight-symbol kernel, or prove impossibility in the precisely declared column universe.Suggested move: Suggested next step: Retain all fourteen exclusions and whole-block constraints, produce integral parents and children, preserve parallel root incidences and unused splice edges, then spell the word and verify all 40320 windows.

Ready to work on

Advance the seven-symbol lower bound beyond the completely covered defect-twelve threshold with exact charge and mark semantics.Suggested move: Suggested next step: Enumerate the newly relevant profiles under a stated larger threshold and isolate the missing capacities or global coverage obstructions; do not extrapolate finite capacity identities across charges.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Sep 7, 2026

Current statusOpen problem

The selected sources leave open the minimum length for every alphabet size. Constructions and lower bounds constrain that minimum; the factorial-sum conjecture is already false at six symbols.

[1][2][3]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2021
Peer reviewedEngen and Vatter surveyed permutation-containment problems, distinguishing contiguous superpermutations from subsequence and pattern-containment variants.[2]
2014-08-21
PreprintHouston exhibited a six-symbol superpermutation shorter than 1! + 2! + ⋯ + 6!, disproving the proposed factorial-sum formula. A shorter construction alone does not prove optimality.[1]

Mathematical neighborhood

Related results and reusable starting points

Current focusShortest superpermutations: general case

Related problemAsymmetric traveling-salesman formulation

Houston encoded permutation overlap as a traveling-salesman instance to search for short words. A heuristic tour supplies an upper bound, not a matching lower bound.

[1]

Related problemSubsequence and permutation-pattern containment

Changing contiguous substrings to other containment notions changes the optimization problem and the applicable bounds.

[2]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

formal proof · source linked; not reproduced by ProofAtlasAuthor-reported Lean lower-bound development
The repository reports a Lean formalization of a general lower bound and a bridge to the minimum-length definition. Compilation and dependency claims were not checked here; this is not a general exact-minimum formula.
[4]
software · source linked; not reproduced by ProofAtlasEgan's superpermutation constructions
The author's page explains constructive methods and links explicit superpermutations and computation materials. None were executed or rechecked here.
[3]

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

7 standing statements2 proposed statements3 open questions2 narrowed routes

Statements by mathematical role9 selected mapped statements

theorem candidate1 of 91
reduction3 of 93
lemma2 of 92
equivalence1 of 91
computational claim2 of 92

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.24 displayed rows · 2 routes included

retained route statementHow short can one word containing every permutation be?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementExact overlap Hamiltonian-path modelintermediate
retained route statementA general defect lower boundintermediate
retained route statementScoped small-degree boundsintermediate
retained route statementFour-hole seed with a conditional completion ledgerintermediate
retained route statementStrong rational cover remains fractionalintermediate
retained route statementIntegral completion loss records the missing selectionintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureInferring integrality from attachment equations and rooted cutsreported failure
Useful failureDeletion-only retargeting of the explicit classical degree-eight familyreported failure
Research targetControl attainable row surplus jointly with unavoidable integral completion loss on the actual insertion-incidence families for all degrees.open
Research targetFind 822 whole attachments forming a rooted incidence tree for the fixed eight-symbol kernel, or prove impossibility in the precisely declared column universe.open
Research targetAdvance the seven-symbol lower bound beyond the completely covered defect-twelve threshold with exact charge and mark semantics.open
Narrowed routeInferring integrality from attachment equations and rooted cutsThe root and disjoint triples A,B,C,D,E,F use child sets A+B,A+C,B+C,D+E,D+F,E+F with weight one-half each. A rounding theorem must exploit actual insertion structure; the strong rational point neither proves nor refutes an integral tree for the concrete kernel.
Narrowed routeDeletion-only retargeting of the explicit classical degree-eight familyAll ten representatives surviving the modular filter fail the exact forest dynamic program after the complete relabelling reduction. Adding blocks, changing the kernel, using a different 833-attachment forest, or solving unrestricted integral completion remains outside this exclusion.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeControl attainable row surplus jointly with unavoidable integral completion loss on the actual insertion-incidence families for all degrees.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointControl attainable row surplus jointly with unavoidable integral completion loss on the actual insertion-incidence families for all degrees.

Shortest superpermutations: general case · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references4 cited works · next context review by Dec 7, 2026

The mathematical context was checked on Sep 7, 2026. Status can be refreshed sooner after a material result or claim.

1
Tackling the Minimal Superpermutation Problempreprint · Robin Houston · arXiv · 2014-08-21 · ARXIV 1408.5108 · accessed Sep 7, 2026
2
Containing all permutationssurvey or monograph · Michael Engen, Vincent Vatter · American Mathematical Monthly 128, 4–24 · 2021 · ARXIV 1810.08252 · DOI 10.1080/00029890.2021.1835384 · accessed Sep 7, 2026
3
Superpermutationssoftware or dataset · Greg Egan · accessed Sep 7, 2026
4
A New Lower Bound for Superpermutations — Lean formalizationformalization · urdvr/superpermutations-hunter · accessed Sep 7, 2026

Important qualifications

This is a scoped administrative literature search, not an exhaustive survey or an independent mathematical review.
Submitted packets are not external evidence. Their novel claims, corrections and proof obligations retain their separate source-reported posture.
No external code, proof development, data file or certificate was executed or independently reproduced during collection. Public links confer no acceptance or redistribution authority.
An empty formalization or recognition list means no suitable item was established in this search; it does not establish nonexistence. Unknown origin dates and original attributions are left unresolved.
No contemporary shortest-word record census or independent optimality check was performed. Private packet assertions about six- or eight-symbol exact values and conditional constructions are not promoted to external facts.
The linked lower-bound repository was inspected as inert public text. Its stated Lean proof and dependency properties are author reports, not verified ProofAtlas evidence.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces