The shortest word containing every permutation of ten symbols as a subsequence has length 83

Contributed by Jason Davies ↗

Version 1 / Nov 19, 2026 / CC BY 4.0

Abstract

A word is universal for an alphabet if it contains every permutation of the alphabet as a subsequence. We prove that no word of length 82 is universal for ten symbols. Together with the known construction of length 83, this shows that the shortest universal word on ten symbols has length 83. The proof cuts a word at the copies of one symbol: universality is equivalent to complementary prefix and suffix conditions at consecutive copies. A counting argument confines a least frequent symbol to four, five, six or seven copies and excludes four. In the remaining cases, frequency tests reduce the possibilities to finitely many block templates, and machine-checked propositional refutations exclude every ordering of each. The computation also reproduces the nine-symbol value 66.

Provenance statement

The proof, its implementation and certificates, the Lean 4 formalisation and the manuscript were produced by AI under the direction of the human contributor. GPT-6.2-Astra (OpenAI), used through Codex, developed the mathematical arguments, the enumerators and encoders, the certificates and their verification, the Lean formalisation and the manuscript. Claude Opus 5.5 (Anthropic), used through Claude Code, reviewed and revised the manuscript and implemented the certificates for the 265 central five-copy cuts, the replay's progress reporting and the regression tests. The human contributor wrote no part of the manuscript.

Tools used

Anthropic
Claude CodeVersion Claude Opus 5.5
OpenAI
CodexVersion GPT-6.2-Astra
Lean
LeanVersion 4

References

  1. Leonard Adleman. Short permutation strings. Discrete Mathematics 10(2):197--200, 1974. doi:10.1016/0012-365X(74)90116-2 (https://doi.org/10.1016/0012-365X(74)90116-2).DOI
  2. Václav Chvátal, David A. Klarner and Donald E. Knuth. Selected combinatorial research problems . Stanford University Technical Report STAN-CS-72-292, 1972. http://infolab.stanford.edu/TR/CS-TR-72-292.html.link
  3. Jason Davies. Permutation supersequence length : software, proof certificates and Lean source. . This paper describes release v1.0 .
  4. Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction -- CADE 28 , Lecture Notes in Computer Science, vol. 12699, pp. 625--635. Springer, 2021. doi:10.1007/978-3-030-79876-5_37 (https://doi.org/10.1007/978-3-030-79876-5_37).DOI
  5. Michael Engen and Vincent Vatter. Containing all permutations. American Mathematical Monthly 128:4--24, 2021. doi:10.1080/00029890.2021.1835384 (https://doi.org/10.1080/00029890.2021.1835384).DOI
  6. Vitaliy Garnashevich. Solver for OEIS A136094 . https://github.com/vsg/A136094.link
  7. Daniel J. Kleitman and David J. Kwiatkowski. A lower bound on the length of a sequence containing all permutations as subsequences. Journal of Combinatorial Theory, Series A 21(2):129--136, 1976. doi:10.1016/0097-3165(76)90057-1 (https://doi.org/10.1016/0097-3165(76)90057-1).DOI
  8. Malcolm Newey. Notes on a problem involving permutations as subsequences . Stanford Artificial Intelligence Laboratory Memo AIM-190, STAN-CS-73-340, 1973. http://infolab.stanford.edu/TR/CS-TR-73-340.html.link
  9. OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences , sequence A062714. https://oeis.org/A062714.link
  10. Saša Radomirović. A construction of short sequences containing all permutations of a set as subsequences. Electronic Journal of Combinatorics 19(4):#P31, 2012. doi:10.37236/2859 (https://doi.org/10.37236/2859).DOI
Show all 13 referencesShow fewer references
  1. Oliver Tan. Skip letters for short supersequence of all permutations. Discrete Mathematics 345, Article 113070, 2022. doi:10.1016/j.disc.2022.113070 (https://doi.org/10.1016/j.disc.2022.113070).DOI
  2. Oliver Tan. Conjecture on supersequence lower bound related to Connell sequence. arXiv:2501.11386 [math.CO], 2025. doi:10.48550/arXiv.2501.11386 (https://doi.org/10.48550/arXiv.2501.11386).arXivDOI
  3. Eugen Zălinescu. Shorter strings containing all kk-element permutations. Information Processing Letters 111(12):605--608, 2011. doi:10.1016/j.ipl.2011.03.018 (https://doi.org/10.1016/j.ipl.2011.03.018).DOI

Version history

  1. v1 · 8 pagesSubmitted by Jason DaviesInitial depositCurrentNov 19, 2026