\pdfoutput=1 \documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage{lmodern,amsmath,amssymb,amsthm,booktabs,microtype} \usepackage[hmargin=1in,vmargin=0.9in]{geometry} \usepackage[colorlinks=true,urlcolor=blue,citecolor=blue,linkcolor=blue]{hyperref} \hypersetup{pdftitle={The shortest word containing every permutation of ten symbols as a subsequence has length 83},pdfauthor={Jason Davies}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newcommand{\cov}{\mathcal U} \newcommand{\repo}{\url{https://github.com/jasondavies/permutation-supersequence-length}} \title{The shortest word containing every permutation of ten symbols as a subsequence has length 83} \author{Jason Davies\thanks{\href{mailto:jason@jasondavies.com}{\nolinkurl{jason@jasondavies.com}}}} \date{November 18, 2026} \begin{document} \maketitle \begin{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. \end{abstract} \noindent\textbf{AI transparency statement.} The proof, its implementation and certificates, the Lean formalisation and this manuscript were produced by artificial intelligence under the direction of the human author. Details are given at the end of the paper. \section{The extremal problem} A word over an alphabet is \emph{universal} if it contains every permutation of the alphabet as a subsequence, that is, at strictly increasing but not necessarily consecutive positions. Write $f(n)$ for the least length of a universal word over $[n]$. Requiring each permutation to occur contiguously gives the different superpermutation problem, whose answers grow factorially. The problem is due to Karp \cite[Problem~36]{ckk}. Newey computed $f(n)$ through seven letters \cite{newey}, and Adleman gave an early general construction \cite{adleman}. Tan proved $f(8)=52$ \cite{tan}, and the OEIS credits Vitaliy Garnashevich with computing $f(9)=66$ in 2025 \cite{oeis,garnashevich}. In general $f(n)=n^2-o(n^2)$. Kleitman and Kwiatkowski proved $f(n)\ge n^2-C_\varepsilon n^{7/4+\varepsilon}$ \cite{kk}. Radomirovi\'c proved $f(n)\le\lceil n^2-\tfrac73n+\tfrac{19}3\rceil$ for $n\ge7$ \cite{radomirovic}, and Tan obtained $n^2-(\tfrac52-\varepsilon)n+C_\varepsilon$ for infinitely many $n$ \cite{tan2022}. Engen and Vatter survey the problem \cite{engenvatter}. At ten letters Z\u{a}linescu records an earlier example of length 83 and gives a construction of length $n^2-2n+3$ for all $n\ge10$ \cite{zalinescu}. \begin{theorem}\label{thm:main} The shortest universal word on ten symbols has length $83$. \end{theorem} Here is an upper-bound witness, written on two lines to be concatenated. \begin{center}\ttfamily 012345678901234567802934516708234519607821\par 34506978231405678213904567823109456782301 \end{center} Matching each requested digit at its earliest available position verifies all 3,628,800 permutations. For the lower bound it suffices to exclude length 82, since appending letters preserves universality. The numerical inputs on smaller alphabets are \[ (f(0),\ldots,f(9))=(0,1,3,7,12,19,28,39,52,66). \] The companion computation independently recovers the last entry from the preceding ones. Section~\ref{sec:cut} reduces the problem to four possible multiplicities of a least frequent symbol. Section~\ref{sec:tests} describes the tests that turn each case into a finite list of block templates, sequences of multisets whose concatenated orderings stand for candidate words. Section~\ref{sec:cases} treats the cases, summarised in Table~\ref{tab:cases}. \begin{table}[ht] \centering\small \begin{tabular}{cll} \toprule Minimum frequency & Cases retained & Final check\\ \midrule 4 & Two outer cuts & Gap replacement gives a contradiction\\ 5 & 922 block templates & 922 ordering refutations\\ 6 & 1,372 endpoint patterns & 1,372 ordering refutations\\ 7 & 1,131 endpoint templates & 229 projected and 2 joint refutations\\ \bottomrule \end{tabular} \caption{The exclusion at length 82. The six-copy case also uses 304 smaller-alphabet frequency exclusions, proved with 777 auxiliary refutations.}\label{tab:cases} \end{table} \section{A cut at consecutive copies}\label{sec:cut} Write $\cov(S,V)$ when $V$ contains every ordering of the set $S$. Choose a symbol $x$ with $r$ occurrences in a word $W$, and let $A$ be the alphabet with $x$ removed. Delete all copies of $x$. In the resulting word, let $P_i$ and $Q_i$ be the portions before and after the location of the $i$th copy. Thus $|P_i|+|Q_i|=t=|W|-r$. \begin{lemma}\label{lem:cut} For $r\ge1$, $W$ is universal if and only if $\cov(A,Q_1)$ and $\cov(A,P_r)$ hold and, for every $1\le i