\documentclass[11pt]{amsart} \pdfsuppressptexinfo=-1 \usepackage[margin=1.1in]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{booktabs,enumitem} \usepackage[hidelinks]{hyperref} \hypersetup{pdftitle={Certified upper bounds for the Chvatal-Sankoff constant}, pdfauthor={Tejasvi Singh Tomar}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \setlength{\emergencystretch}{2em} \DeclareMathOperator{\LCS}{LCS} \DeclareMathOperator{\rep}{rep} \newcommand{\E}{\mathbb{E}} \newcommand{\cb}{\bar c} \newcommand{\Mh}{M_h} \newcommand{\Sig}{\Sigma} \newcommand{\aLen}{\alpha} \newcommand{\bLen}{\beta} % ===================================================================== % Values taken from the certificates and from the logs of the checking program. % Bounds are rounded up. h = 13 is the main result; h = 12 stays as a row. \newif\ifhtwelve \htwelvetrue \newif\ifhthirteen \hthirteentrue \newif\ifvthirteendet \vthirteendetfalse % true if 100 iterations are confirmed to reproduce the vector b5456a64 \ifhthirteen \newcommand{\hmain}{13} \newcommand{\gmain}{0.821963} \newcommand{\gmainexact}{0.8219629194} \newcommand{\zmain}{0.3568} \newcommand{\Nmain}{165{,}695{,}219{,}469} \newcommand{\Emain}{3{,}217{,}333{,}414{,}315} \else\ifhtwelve \newcommand{\hmain}{12} \newcommand{\gmain}{0.822579} \newcommand{\gmainexact}{0.8225783634} \newcommand{\zmain}{0.3505} \newcommand{\Nmain}{22{,}670{,}087{,}101} \newcommand{\Emain}{418{,}139{,}991{,}128} \else \newcommand{\hmain}{11} \newcommand{\gmain}{0.823290} \newcommand{\gmainexact}{0.8232896731} \newcommand{\zmain}{0.3445} \newcommand{\Nmain}{3{,}045{,}043{,}879} \newcommand{\Emain}{53{,}133{,}194{,}463} \fi\fi \newcommand{\gTwelve}{0.822579} % h = 12 bound \newcommand{\lamThirteen}{0.439973329782} % h = 13 row: lambda = 0.43997332978114057488 rounded up to 12 decimals \newcommand{\bndThirteen}{0.8219629194} % h = 13 row: 2 ln(2z)/ln(lambda) = 0.82196291940285596..., truncated \newcommand{\LAMthirteen}{8116075413730513074} % h = 13: Lambda (check2, 4 nodes; combine_check2) \newcommand{\vthirteensha}{b5456a64} % h = 13 vector (binary32, 662,780,877,876 bytes): first 8 hex digits of its SHA-256 \newcommand{\gL}{0.826280} % Lueker 2009, h = 8 \newcommand{\gLlow}{0.788071} % Lueker 2009, lower bound \newcommand{\gJnine}{0.825101} % Jack 2026, h = 9 \newcommand{\gJ}{0.824120} % Jack 2026, h = 10 \newcommand{\glow}{0.792665992} % Soiffer et al. 2025, lower bound \newcommand{\gDP}{0.837623} % Dancik-Paterson 1995 \newcommand{\gDPlow}{0.773911} % Dancik 1994, lower bound \newcommand{\gBC}{0.82118} % Bukh-Cox, periodic word \newcommand{\lamTwelve}{0.421581925965} % h = 12 row: lambda rounded up (deterministic certificate) \newcommand{\bndTwelve}{0.8225783634} % h = 12 row: bound truncated (deterministic certificate) \newcommand{\LAMdet}{7776813894375449830} % h = 12 deterministic certificate: Lambda \newcommand{\vdetsha}{915ac393} % h = 12 deterministic vector: first 8 hex digits of its SHA-256 \newcommand{\DOIsupp}{10.5281/zenodo.23610946} % supplement record, version 5 (reserved 10-24) \newcommand{\repoURL}{https://github.com/tejasvi/chvatal-sankoff-certificates-v5} % ---- Lean proofs ---- \newif\ifleanN \leanNtrue % CS31aData.gamma2_le_h12 (native_decide, 7 row shares) \newif\ifleanK \leanKtrue % CS31aK.H9/H10/H11.gamma2_le (decide +kernel only) \newif\ifleanNthirteen \leanNthirteentrue % CS31aData.gamma2_le_n13 (native_decide, 56 row shares) \newif\ifleanKtwelve \leanKtwelvetrue % CS31aK.H12.gamma2_le (decide +kernel only, lane-packed checker) \newif\iflean \leantrue % Section 6 and the Lean mentions \newcommand{\leanStd}{\texttt{propext}, \texttt{Classical.choice} and \texttt{Quot.sound}} \newcommand{\leanNparts}{7} % row shares of the h = 12 check \newcommand{\leanKparts}{524{,}288} % kernel checks (shards) of the h = 9 certificate \newcommand{\leanKtenparts}{4{,}194{,}304} % kernel checks of the h = 10 certificate \newcommand{\leanKtenmods}{131{,}072} % modules, h = 10 \newcommand{\leanKelevenparts}{8{,}388{,}608} % kernel checks of the h = 11 certificate \newcommand{\leanKelevenmods}{65{,}536} % modules, h = 11 \newcommand{\leanNthirteenparts}{56} % row shares of the h = 13 check \newcommand{\leanKtwelveparts}{67{,}108{,}864} % kernel checks of the h = 12 certificate (2^26: D1 = D2 = 13) \newcommand{\leanKtwelvemods}{524{,}288} % modules, h = 12 (2^26 / 128) \newcommand{\leanKtwelvecpuh}{69{,}000} % CPU-hours of the h = 12 shard modules: 59,513.9 timed (446,464 modules) + 77,824 x 449 s estimated \newcommand{\gTen}{0.824120} % h = 10 bound \newcommand{\gEleven}{0.823290} % h = 11 bound % ===================================================================== \begin{document} \title{Certified upper bounds for the Chv\'atal--Sankoff constant} \author{Tejasvi Singh Tomar} \renewcommand{\urladdrname}{{\itshape ORCID}} \urladdr{\href{https://orcid.org/0000-0003-4668-3639}{https://orcid.org/0000-0003-4668-3639}} \subjclass[2020]{60C05; 68R15, 68Q45, 65G20\iflean, 68V20\fi} \keywords{Chv\'atal--Sankoff constant, longest common subsequence, random strings, Lueker's method, Collatz--Wielandt bound, computer-assisted proof\iflean, Lean~4\fi} \begin{abstract} Let $\gamma_2$ be the Chv\'atal--Sankoff constant, so that the expected length of a longest common subsequence of two independent uniformly random binary strings of length $n$ is $\gamma_2n+o(n)$. Lueker proved $\gamma_2\le\gL$ with a finite automaton that reads a pair of strings as a sequence of minimal match pairs and remembers the last $h$ symbols of each string, for $h=8$. We carry out his method up to $h=\hmain$ and prove $\gamma_2\le\gmain$. For $h=\hmain$ the certificate lists $\Nmain$ states of the automaton, reduced by a symmetry. The bound rests on an explicit positive vector for the weighted transition matrix of the automaton; a checker rebuilds every transition with its own code and verifies the required inequalities in exact integer arithmetic. We also give a complete proof that the automaton accepts the truncated canonical decomposition of every pair of strings, the property on which the method depends.\iflean{} \ifleanNthirteen\ifleanKtwelve The bound $\gamma_2\le\gmain$ is also proved in the Lean~4 proof assistant, with a computation evaluated by compiled code, and the bounds $\gamma_2\le\gJnine$, $\gamma_2\le\gTen$, $\gamma_2\le\gEleven$ and $\gamma_2\le\gTwelve$ for $h=9$, $10$, $11$ and $12$ by formal proofs that are checked entirely by the Lean kernel.\else The bounds $\gamma_2\le\gmain$ and $\gamma_2\le\gTwelve$, for $h=13$ and $h=12$, are also proved in the Lean~4 proof assistant, with computations evaluated by compiled code, and the bounds $\gamma_2\le\gJnine$, $\gamma_2\le\gTen$ and $\gamma_2\le\gEleven$ for $h=9$, $10$ and $11$ by formal proofs that are checked entirely by the Lean kernel.\fi\else\ifleanKtwelve The weaker bounds $\gamma_2\le\gJnine$, $\gamma_2\le\gTen$, $\gamma_2\le\gEleven$ and $\gamma_2\le\gTwelve$ for $h=9$, $10$, $11$ and $12$ are also proved in the Lean~4 proof assistant, by formal proofs that are checked entirely by the Lean kernel.\else The weaker bound $\gamma_2\le\gTwelve$ for $h=12$ is also proved in the Lean~4 proof assistant, with a computation evaluated by compiled code, and the bounds $\gamma_2\le\gJnine$, $\gamma_2\le\gTen$ and $\gamma_2\le\gEleven$ for $h=9$, $10$ and $11$ by formal proofs that are checked entirely by the Lean kernel.\fi\fi\fi \end{abstract} \maketitle \iflean\enlargethispage{3pt}\fi \section{Introduction}\label{sec:intro} For strings $A$ and $B$ let $\LCS(A,B)$ be the length of a longest common subsequence of $A$ and $B$. Let $A_n$ and $B_n$ be independent uniformly random strings of length $n$ over $\Sig=\{0,1\}$ and put $L_n=\LCS(A_n,B_n)$. Chv\'atal and Sankoff \cite{CS75} showed that $\E L_n/n$ converges as $n\to\infty$; the limit $\gamma_2$ is called the Chv\'atal--Sankoff constant. Since $\E L_{m+n}\ge\E L_m+\E L_n$, the limit is also the supremum of $\E L_n/n$. The value of $\gamma_2$ is not known. Simulations suggest $\gamma_2\approx0.8122$ \cite[Section~1]{BC22}. Dan\v{c}\'ik \cite{Dan94} proved $\gamma_2\ge\gDPlow$, and Dan\v{c}\'ik and Paterson \cite{DP95} (see also \cite{Dan94}) proved $\gamma_2\le\gDP$ with a $52$-state automaton \cite[Section~3.1]{Lue09}. Lueker \cite{Lue09} improved both bounds, to $\gLlow\le\gamma_2\le\gL$. His upper-bound technique \cite[Section~3]{Lue09} uses finite automata $M_h$ with a history parameter $h$, which read a pair of strings as a sequence of minimal match pairs \cite[Section~3.2]{Lue09}. The bound $\gL$ comes from $M_8$, which has $6{,}419{,}109$ reachable states after a symmetry reduction \cite[Table~II]{Lue09}, \cite{LueCode}, and it shows that the value $2/(1+\sqrt2)\approx0.828427$ conjectured by Steele is too large \cite[p.~17:21]{Lue09}. Lueker also proved that the bounds obtainable from $M_h$ converge to $\gamma_k$ as $h\to\infty$, for every alphabet size $k$ \cite[Section~3.3]{Lue09}. The lower bound has since been improved to $\glow$ \cite{SSMRSH25}. In October 2026 Jack \cite{Jac26} posted computations with Lueker's automaton for $h=9$ and $h=10$, which give $\gamma_2\le\gJnine$ and $\gamma_2\le\gJ$. They have not been refereed; the repository of optimization constants maintained by Davis, Ivanisvili, Tao and contributors \cite[page~31a]{DIT26} lists them with an asterisk, its mark for bounds whose available verification is at a minimal level. \begin{theorem}\label{thm:main} $\gamma_2\le\gmain$. \end{theorem} The proof follows Lueker's method with history length $h=\hmain$. Table~\ref{tab:ladder} lists the bounds that the same method gives for $h=8,\dots,\hmain$, each verified by the exact checks of Section~\ref{sec:cert}\ifhthirteen{} (for $h=13$ with a separate implementation of these checks)\fi; for $h=8$ we recover Lueker's value $\gL$, and for $h=9$ and $h=10$ the values of \cite{Jac26}. Our verification differs from the earlier computations in two respects. First, Lueker justifies his final bound under the assumption that the floating-point operations of his program perform as expected \cite[Section~3.2.2]{Lue09}, and the computations of \cite{Jac26} use floating-point arithmetic with upward rounding, together with a recheck for $h=10$ that does not depend on the rounding mode. Our checking programs verify the required inequalities exactly, in integer arithmetic, for a rational parameter $z$ and with all weights rounded up. Second, Lueker explains why his automaton never rejects the canonical decomposition of a pair of strings \cite[Section~3.2]{Lue09}; we give a detailed proof of this covering property (Lemma~\ref{lem:cover}).\iflean{} \ifleanNthirteen\ifleanKtwelve Theorem~\ref{thm:main} has also been proved in the Lean~4 proof assistant, with a computation evaluated by compiled code (Section~\ref{sec:lean}), and so have the bounds for $h=9$, $10$, $11$ and $12$ in Table~\ref{tab:ladder}, by proofs that are checked entirely by the Lean kernel, so that the Lean compiler is not part of their trusted base.\else Theorem~\ref{thm:main} and the bound for $h=12$ in Table~\ref{tab:ladder} have also been proved in the Lean~4 proof assistant, with computations evaluated by compiled code (Section~\ref{sec:lean}), and so have the bounds for $h=9$, $10$ and $11$, by proofs that are checked entirely by the Lean kernel, so that the Lean compiler is not part of their trusted base.\fi\else\ifleanKtwelve The bounds for $h=9$, $10$, $11$ and $12$ in Table~\ref{tab:ladder} have also been proved in the Lean~4 proof assistant (Section~\ref{sec:lean}), by proofs that are checked entirely by the Lean kernel, so that the Lean compiler is not part of their trusted base; the bound of Theorem~\ref{thm:main} is not formalized.\else The bound for $h=12$ in Table~\ref{tab:ladder} has also been proved in the Lean~4 proof assistant, with a computation evaluated by compiled code (Section~\ref{sec:lean}), and so have the bounds for $h=9$, $10$ and $11$, by proofs that are checked entirely by the Lean kernel, so that the Lean compiler is not part of their trusted base; the bound of Theorem~\ref{thm:main} is not formalized.\fi\fi\fi \subsection*{The method} A pair of strings decomposes canonically into minimal match pairs, one for each symbol of a particular longest common subsequence, followed by a pair without matches (Lemma~\ref{lem:canon}). The automaton $\Mh$ reads the minimal match pairs one at a time. Its state consists of the last $h$ symbols of each string and of the last $h$ increments of the dynamic programming table down its last column and along its last row. It rejects an input when the canonical traceback rule shows that the input cannot continue a canonical decomposition. Give a minimal match pair of total length $s$ the weight $z^s$, and let $A_z$ be the weighted transition matrix of $\Mh$. If $00$ and $A_zv\le\lambda v$ for some $\lambda<1$, then $\gamma_2\le2\ln(2z)/\ln\lambda$ (Theorem~\ref{thm:count}). The automata $\Mh$ and this use of them are Lueker's \cite{Lue09}; the counting criterion is due to Dan\v{c}\'ik and Paterson \cite{Dan94,DP95}, in the form of \cite[Theorem~3.3]{Lue09}. For $h=\hmain$ and $z=\zmain$ the certificate lists the $\Nmain$ states of the reduced automaton that a breadth-first search from the start state finds, with $\Emain$ accepted transitions, and we take $v$ from a power iteration. Section~\ref{sec:prelim} collects facts about longest common subsequences and the canonical decomposition. Section~\ref{sec:automaton} defines $\Mh$ and proves the covering property, and Section~\ref{sec:count} proves the counting bound. Section~\ref{sec:cert} describes the certificates, the checker and the results\iflean, Section~\ref{sec:lean} describes the formal proofs\fi, and Section~\ref{sec:remarks} contains remarks. \section{Longest common subsequences}\label{sec:prelim} Throughout, $\Sig=\{0,1\}$ and $\cb=1-c$ for $c\in\Sig$. For a string $A$ we write $A[i]$ for its $i$th symbol, $A[i..j]$ for $A[i]A[i+1]\cdots A[j]$ and $|A|$ for its length. For strings $A,B$ let $L(i,j)=\LCS(A[1..i],B[1..j])$, with $L(i,0)=L(0,j)=0$. For $i,j\ge1$, \begin{equation}\label{eq:rec} L(i,j)=\begin{cases}L(i-1,j-1)+1,&A[i]=B[j],\\ \max\{L(i-1,j),L(i,j-1)\},&A[i]\ne B[j].\end{cases} \end{equation} \begin{lemma}\label{lem:incr} Let $a_1,\dots,a_m,b_1,\dots,b_n\in\Sig$ and let $W\colon\{0,\dots,m\}\times\{0,\dots,n\}\to\mathbb{Z}$ satisfy \eqref{eq:rec} with $a_r,b_s$ in place of $A[i],B[j]$ for all $r,s\ge1$. If $W(r,0)-W(r-1,0)\in\{0,1\}$ and $W(0,s)-W(0,s-1)\in\{0,1\}$ for all $r,s\ge1$, then $W(r,s)-W(r-1,s)\in\{0,1\}$ and $W(r,s)-W(r,s-1)\in\{0,1\}$ for all $r,s\ge1$. \end{lemma} \begin{proof} By induction on $r+s$. Put $u=W(r-1,s-1)$, $u'=W(r-1,s)$ and $u''=W(r,s-1)$; by induction $u',u''\in\{u,u+1\}$. If $a_r=b_s$, then $W(r,s)=u+1$ lies in $\{u',u'+1\}$ and in $\{u'',u''+1\}$. Otherwise $W(r,s)=\max\{u',u''\}$, which lies in $\{u',u'+1\}$ and in $\{u'',u''+1\}$ because $|u'-u''|\le1$. \end{proof} In particular all increments of $L$ lie in $\{0,1\}$, so $L$ is nondecreasing in each argument. \subsection{Minimal match pairs} A pair of nonempty strings $(u,w)$ is a \emph{minimal match pair} if $u[|u|]=w[|w|]$ and $u[i]\ne w[j]$ for every other pair of positions $(i,j)$. Its \emph{size} is $|u|+|w|$. For $c\in\Sig$ and $l\in\mathbb{Z}$ put \[ T_{c,l}=(\cb^{\,l}c,\ c)\quad(l\ge0),\qquad T_{c,l}=(c,\ \cb^{\,|l|}c)\quad(l<0), \] a pair of size $|l|+2$. \begin{lemma}\label{lem:mmp} The minimal match pairs over $\Sig$ are exactly the pairs $T_{c,l}$, $c\in\Sig$, $l\in\mathbb{Z}$. \end{lemma} \begin{proof} Each $T_{c,l}$ is a minimal match pair. Conversely, let $(u,w)$ be a minimal match pair with last symbol $c$. If $|u|,|w|\ge2$, then $u[1]\ne w[|w|]=c$ and $u[|u|]=c\ne w[1]$ give $u[1]=w[1]=\cb$, which contradicts $u[1]\ne w[1]$. So $|u|=1$ or $|w|=1$, and every other symbol of the longer string differs from $c$. \end{proof} \subsection{The canonical decomposition} The \emph{canonical traceback} starts at a cell $(i,j)$ and, while $i,j\ge1$, moves up to $(i-1,j)$ if $L(i-1,j)=L(i,j)$, else left to $(i,j-1)$ if $L(i,j-1)=L(i,j)$, and else diagonally to $(i-1,j-1)$. By Lemma~\ref{lem:incr} and \eqref{eq:rec}, a diagonal step from $(i,j)$ happens only if $A[i]=B[j]$ and $L(i-1,j)=L(i,j-1)=L(i-1,j-1)=L(i,j)-1$. \begin{lemma}[{cf.\ \cite[Lemmas~3.4 and~3.5]{Lue09}}]\label{lem:canon} Let $A,B\in\Sig^n$ and let $(i_1,j_1),\dots,(i_m,j_m)$, with $i_1<\dotsi_m$, $j>j_m$. Moreover $L(i_k,j_k-1)=L(i_k-1,j_k)=k-1$, and if $p_k=T_{c,l}$ with $l<0$, then \begin{equation}\label{eq:C} L(i_{k-1}-1,j)i_m$, $j>j_m$ would give $L(n,n)\ge L(i_m,j_m)+1=m+1$. The equalities $L(i_k,j_k-1)=L(i_k-1,j_k)=k-1$ hold at every diagonal step. For $k\ge2$, between the diagonal steps at $(i_k,j_k)$ and $(i_{k-1},j_{k-1})$ the traceback moves from $(i_k-1,j_k-1)$ to $(i_{k-1},j_{k-1})$ by up and left steps only. If $p_k=T_{c,l}$ with $l<0$, then $i_k=i_{k-1}+1$, so these are left steps along row $i_{k-1}$, on which $L=k-1$. A left step at $(i_{k-1},j)$ with $j\ge1$ is taken only if the up step is refused, that is, $L(i_{k-1}-1,j)h$, in row-major order, by \eqref{eq:rec} with $a_r,b_s$ in place of $A[i],B[j]$. \item Starting at $(\aLen,\bLen)$, apply the canonical traceback rule to $W$ until the current cell is $(h,h)$ or has a coordinate smaller than $h$. The input is \emph{accepted} if the traceback stops at $(h,h)$, and \emph{rejected} otherwise. \item If the input is accepted, the new state is $(x',y',d_x',d_y')$ with $x'=a[\aLen-h+1..\aLen]$, $y'=b[\bLen-h+1..\bLen]$, $d_x'[t]=W(\aLen-h+t,\bLen)-W(\aLen-h+t-1,\bLen)$ and $d_y'[t]=W(\aLen,\bLen-h+t)-W(\aLen,\bLen-h+t-1)$ for $1\le t\le h$. \end{enumerate} The \emph{start state} is $q_0=(0^h,0^h,1^h,1^h)$. Every cell that steps (3)--(5) read is defined: in step (3) because the neighbours of a cell being filled are filled cells, cells of row $h$ or column $h$, or cells set in step (2), and in steps (4) and (5) because they read only cells with $\max\{r,s\}>h$ and cells of row $h$ and column $h$. The rectangle $\{h,\dots,\aLen\}\times\{0,\dots,h\}$ has a first row with increments $d_y[s]$ and a constant first column, so by Lemma~\ref{lem:incr} its increments lie in $\{0,1\}$; then the rectangle $\{0,\dots,\aLen\}\times\{h,\dots,\bLen\}$ has a constant first row and a first column with increments in $\{0,1\}$, and Lemma~\ref{lem:incr} applies again. So the increments of $W$ on the filled region lie in $\{0,1\}$, and the new $d_x',d_y'$ are bit strings. On an accepted input the traceback takes exactly one diagonal step, at $(\aLen,\bLen)$. It takes at least one, because $a_\aLen=b_\bLen$ and monotonicity give $W(\aLen,\bLen)=W(\aLen-1,\bLen-1)+1>W(h,h)$, while up and left steps keep the value. It takes at most one, because a diagonal step from a cell of row $h$ or column $h$ leaves the region of cells with both coordinates at least $h$, and a diagonal step at a filled cell $(r,s)$ requires $a_r=b_s$ by \eqref{eq:rec}, which for $r,s>h$ happens only at $(\aLen,\bLen)$, since $T_{c,l}$ is a minimal match pair. Complementing every symbol of $a$, $b$ and of the input does not change any comparison, so \begin{equation}\label{eq:sym} \delta(\bar q,T_{\cb,l})=\overline{\delta(q,T_{c,l})},\qquad\text{where }\overline{(x,y,d_x,d_y)}=(\bar x,\bar y,d_x,d_y), \end{equation} and one side is a rejection if and only if the other is. Let $\rep(q)=\bar q$ if $x[1]=1$ and $\rep(q)=q$ otherwise. The \emph{reduced automaton} has the states $q$ with $x[1]=0$ and the transitions $\delta_{\mathrm{red}}=\rep\circ\delta$; it is the automaton of Lueker's programs. Truncation sends an arbitrary minimal match pair to an input: $\mu(T_{c,l})=T_{c,l'}$ with $l'=\operatorname{sign}(l)\min\{|l|,h-1\}$. For $0h-1$, the truncation removes symbols $\cb$ on the left of the longer string, and the last $\aLen-h$ (respectively $\bLen-h$) symbols are kept. We claim that $W(r,s)+C\le L^*(\phi(r),\psi(s))$ for every cell of the filled region, where $W$ is the table of step (3). For the constant extensions of step (2) this follows from $(I_k)$ and the monotonicity of $L^*$, and for the cells of row $h$ and column $h$ it is $(I_k)$. For a filled cell, induct in the order of filling. If $a_r=b_s$, then $\phi(r-1)\le\phi(r)-1$ and $\psi(s-1)\le\psi(s)-1$ give \begin{align*} L^*(\phi(r),\psi(s))&\ge L^*(\phi(r)-1,\psi(s)-1)+1\ge L^*(\phi(r-1),\psi(s-1))+1\\ &\ge W(r-1,s-1)+C+1=W(r,s)+C. \end{align*} Otherwise $L^*(\phi(r),\psi(s))\ge\max\{L^*(\phi(r-1),\psi(s)),L^*(\phi(r),\psi(s-1))\}\ge W(r,s)+C$. \emph{Acceptance when $l\ge0$.} Then $\bLen=h+1$, $J'=J+1$, and Lemma~\ref{lem:canon} gives $L^*(I',J)=L^*(I'-1,J')=h+k$. Hence $W(\aLen,h)+C\le h+k=W(h,h)+C$, and since $W$ is nondecreasing, $W(r,h)=W(h,h)$ for $h\le r\le\aLen$. Likewise $W(\aLen-1,h+1)\le W(h,h)$, because $\phi(\aLen-1)=I'-1$ (also when $\aLen=h+1$, since then $l^\circ=0$), and $W(\aLen-1,h+1)\ge W(\aLen-1,h)=W(h,h)$. Since $a_\aLen=b_\bLen$, $W(\aLen,\bLen)=W(\aLen-1,h)+1=W(h,h)+1$, which exceeds $W(\aLen-1,\bLen)=W(\aLen-1,h+1)$ and $W(\aLen,h)$. So the traceback steps diagonally at $(\aLen,\bLen)$ and then moves up along column $h$, where $W$ is constant, to $(h,h)$: the input is accepted. \emph{Acceptance when $l<0$.} Then $\aLen=h+1$, $I'=I+1$, and Lemma~\ref{lem:canon} gives $L^*(I,J')=L^*(I',J'-1)=h+k$. As before $W(h,s)=W(h,h)$ for $h\le s\le\bLen$ and $W(h+1,\bLen-1)=W(h,h)$, so the traceback steps diagonally at $(\aLen,\bLen)$ to $(h,\bLen-1)$. At a cell $(h,s)$ with $h2\ln(2z)/\ln\lambda$ and $k=\lceil\theta n\rceil$. Then \[ \Pr(L_n\ge\theta n)\le\frac{v(q_0)}{\min v}\exp\bigl(n(-2\ln(2z)+\theta\ln\lambda)\bigr), \] which decays geometrically in $n$. Since $L_n\le n$, $\E L_n\le\theta n+n\Pr(L_n\ge\theta n)$, so $\gamma_2\le\theta$. Let $\theta$ decrease to $2\ln(2z)/\ln\lambda$. \end{proof} The certificates are stated for the reduced automaton; the next lemma transfers them to $\Mh$ with the same $\lambda$. \begin{lemma}\label{lem:reduce} Let $S_{\mathrm{red}}$ be a set of reduced states that contains $q_0$ and satisfies $\delta_{\mathrm{red}}(q,p)\in S_{\mathrm{red}}$ for every $q\in S_{\mathrm{red}}$ and every input $p$ accepted at $q$. Let $v\colon S_{\mathrm{red}}\to(0,\infty)$ satisfy \eqref{eq:cw} with $\delta_{\mathrm{red}}$ in place of $\delta$. Then $S=S_{\mathrm{red}}\cup\{\bar q:q\in S_{\mathrm{red}}\}$ and $v(\bar q)=v(q)$ satisfy the hypotheses of Theorem~\ref{thm:count} with the same $\lambda$. \end{lemma} \begin{proof} The extension of $v$ is well defined because $\bar q$ is not reduced when $q$ is, and $v(q')=v(\rep(q'))$ for all $q'\in S$. For $q\in S_{\mathrm{red}}$ and an accepted input $p$, $\delta(q,p)$ and $\rep(\delta(q,p))=\delta_{\mathrm{red}}(q,p)\in S_{\mathrm{red}}$ differ at most by complementation, so $\delta(q,p)\in S$, and the left side of \eqref{eq:cw} at $q$ is the same for $\delta$ and $\delta_{\mathrm{red}}$. At $\bar q$, \eqref{eq:sym} gives $\delta(\bar q,T_{c,l})=\overline{\delta(q,T_{\cb,l})}\in S$, and since $w_z(T_{c,l})$ does not depend on $c$, \[ \sum_{c,l}w_z(T_{c,l})\,v(\delta(\bar q,T_{c,l}))=\sum_{c,l}w_z(T_{\cb,l})\,v(\delta_{\mathrm{red}}(q,T_{\cb,l}))\le\lambda v(q)=\lambda v(\bar q), \] where both sums run over the accepted inputs. \end{proof} \section{Certificates and computations}\label{sec:cert} \subsection{Certificates} A certificate for history length $h$ consists of a rational $z\in(0,1/2)$ given as a decimal, a sorted list of states, and a vector $v>0$ on it stored as double-precision floating-point numbers (single-precision for $h=13$), which we read as exact dyadic rationals. Each state is stored as the integer $x2^{3h}+y2^{2h}+d_x2^h+d_y$, where each bit string is read as a binary number with its first symbol as the most significant bit. The checker computes an integer $\Lambda$ such that \eqref{eq:cw} holds with $\lambda=\Lambda/2^{64}$. \subsection{The checker} The checker rebuilds the transitions with its own implementation of steps (1)--(5) and of $\rep$: a direct dynamic programming computation on the window that marks which cells are defined, stops if a cell read in steps (3) or (4) is undefined, and asserts that all increments lie in $\{0,1\}$ and that an accepted input causes exactly one diagonal step. It checks that the list is strictly increasing and consists of integers below $2^{4h}$, that it contains $q_0$, that every accepted reduced successor of every listed state is listed, and that every entry of $v$ is a positive normal floating-point number. For \eqref{eq:cw} it uses the integer weights $\hat w_j=\lceil2^{64}w_z(T_{c,l})\rceil$ for $j=|l|$, which a separate script computes from the exact rational $z$; the same $z$ is used for the final bound. It writes each entry of $v$ exactly as $m2^e$ with an integer $m$ and evaluates, for every state $q$, the sum of the terms $\hat w_{|l|}\,v(\delta_{\mathrm{red}}(q,T_{c,l}))$ over the accepted inputs in $128$-bit integer arithmetic, scaled to the exponent of $v(q)$; terms that are shifted to the right are rounded up. With $\Lambda_q=\lceil(\text{sum})/m_q\rceil$ it reports $\Lambda=\max_q\Lambda_q$. If a row cannot be bounded in this way, the checker reports $\Lambda=2^{64}-1$, which gives no useful bound; otherwise $A_zv\le(\Lambda/2^{64})v$ holds exactly, and no rounding occurs except the upward roundings described. Finally $2\ln(2z)/\ln(\Lambda/2^{64})$ is evaluated in interval arithmetic and rounded up to six decimals. A second checker, written independently from the same definitions, regenerated the state sets for \ifhtwelve$h=9$, $10$, $11$ and $12$ by its own breadth-first search and verified these four certificates\else$h=9$, $10$ and $11$ by its own breadth-first search and verified these three certificates\fi; in each case the smallest admissible $\Lambda$ that it computes equals the value reported by the first checker. It also passes the certificate for $h=8$, and it rejects perturbed certificates: for \ifhtwelve$h=9$, $10$, $11$ and $12$\else$h=9$, $10$ and $11$\fi, $\Lambda-1$ in place of $\Lambda$ and a slightly larger $z$; for $h=9$ and $h=11$, a slightly smaller entry of $v$ and a list with one state removed. \ifhthirteen Neither of these two checkers checked the certificate for $h=13$. It was checked by a third implementation of the same checks, written for this size. This implementation computes the transitions by an incremental version of the dynamic programming computation, reads the single-precision entries of $v$ exactly, evaluates \eqref{eq:cw} in the same exact integer arithmetic, and prints $64$-bit fingerprints of the list, the vector and the weights. Its transition function agrees with that of the checker on all $1.72\cdot10^{10}$ pairs of a reachable state and an input for $h=2,\dots,10$ and on $2.56\cdot10^9$ pairs met in random walks for $h=11,\dots,15$, and on the certificates for $h=8$, $9$ and $10$ it reports the same $\Lambda$ as the checker. Four machines checked the rows of the certificate for $h=13$ in four consecutive ranges, each also making the global checks on the whole input, with identical fingerprints of the input files. The numbers of accepted transitions that they counted add up to the number found by the breadth-first search, which uses a different transition function, and the largest of their four values, $\Lambda=\LAMthirteen$, gives the value of $\lambda$ in Table~\ref{tab:ladder}. \ifleanNthirteen Apart from the Lean check of Section~\ref{sec:lean}, this program is the only one that checked every row for $h=13$.\else This program is the only one that checked every row for $h=13$.\fi{} In an additional check, the list was regenerated by the breadth-first search, with the same numbers of states and accepted transitions and the same fingerprint, and the vector was reassembled from its stored parts and matched the recorded SHA-256 checksum and fingerprint. On these files the same program was run again on $14\%$ of the rows, including the row at which $\Lambda$ is attained, with identical results. A separate program, which uses the transition function of the checker but its own lookup and exact arithmetic, reproduced the largest values of the four ranges exactly at the rows where they are attained and gave values below $\Lambda$ at $1000$ random rows. \fi \subsection{Search}\label{sec:search} The vectors $v$ come from a power iteration in double precision\ifhthirteen{} (for $h=13$ the row sums are formed in double precision and the iterates are stored in single precision)\fi; any positive vector that passes the check is a valid certificate, and the iteration only serves to make $\Lambda$ small.\ifhtwelve{} The certificate for $h=12$ in Table~\ref{tab:ladder} is the output of a version of the iteration that starts at the all-ones vector, runs a fixed number of iterations and adds in a fixed order; compiled without contraction of multiply-adds, it rounds every operation separately, and its output does not depend on the processor or the number of threads.\fi\ The state sets are the sets of states reachable from $q_0$; for $h=\hmain$ the breadth-first search finds $\Nmain$ reduced states and $\Emain$ accepted transitions. \ifhtwelve For $h=12$ the transition table is stored compactly, each target as its rank among the states with the same pair $(x,y)$, which takes $881$~GB; the computation ran on a machine with $288$ virtual cores and $2.2$~TB of memory, and the exact check took $45$ minutes after loading and preprocessing the input.\fi\ \ifhthirteen For $h=13$ the iteration is distributed: each of four machines computes the rows of a block of states and keeps a copy of the whole vector, which the machines exchange after every iteration. It starts from the vector for $h=12$: each state for $h=13$ takes the value at the state for $h=12$ obtained by deleting the oldest symbol of $x$, $y$, $d_x$ and $d_y$ and reducing by the symmetry, or the smallest entry of that vector if there is no such state. Row sums are formed in a fixed order and normalized by the exact maximum, and the program is designed so that its result does not depend on the number of machines or threads. The certificate is the iterate after $100$ iterations. The list for $h=13$ takes $1.33$~TB and the vector $663$~GB; the breadth-first search took $2.3$ hours on a machine with $160$ virtual cores and $3.8$~TB of memory, and each of the four checks took between $53$ and $56$ minutes, about $15$ of them for loading the input, on a machine of the same kind.\fi\ The programs used for $h=12$\ifhthirteen{} and $h=13$\fi{} use a faster, bit-parallel transition function (Section~\ref{sec:valid}); none of the checking programs uses any code of the search programs. \subsection{Validation of the automaton}\label{sec:valid} For $h=2$ our implementation reproduces the transition table of the $7$-state automaton printed in Lueker's description of his programs \cite{LueCode}. For $h=2,\dots,8$ the numbers of reduced states are $7$, $98$, $1020$, $10160$, $89960$, $780368$ and $6419109$, as in \cite[Table~II]{Lue09}, and for $h=9$ and $h=10$ they are $51{,}425{,}006$ and $400{,}253{,}317$, as in \cite{Jac26}. Our transition tables for $h=9$ and $h=10$, written in the format of \cite{Jac26}, have the SHA-256 checksums published there. The transition function of the checker and the direct and bit-parallel transition functions of the search programs agree on every input at every reachable state for $h\le10$. \subsection{Results} Table~\ref{tab:ladder} lists the certificates. The checking programs do not verify that the listed states are reduced, and this is not needed: the set $R$ of states reachable from $q_0$ under $\delta_{\mathrm{red}}$ consists of reduced states, lies in the list by the closure check, and is closed under $\delta_{\mathrm{red}}$, and the inequality \eqref{eq:cw} holds at each of its states. Lemma~\ref{lem:reduce}, applied to $R$ and the restriction of $v$, and Theorem~\ref{thm:count} give the bound of each row, and Theorem~\ref{thm:main} follows from the row $h=\hmain$. \begin{table}[ht] \centering \caption{Certified upper bounds on $\gamma_2$ from Lueker's automaton with history length $h$. The numbers of states and accepted transitions refer to the reduced automaton. The value $\lambda=\Lambda/2^{64}$ is rounded up; the value $2\ln(2z)/\ln\lambda$, computed with the exact $\lambda$, is truncated, and the last column is that value rounded up.}\label{tab:ladder} \small \begin{tabular}{@{}rrrcccc@{}} \toprule $h$ & states & accepted transitions & $z$ & $\lambda\le$ & $2\ln(2z)/\ln\lambda$ & $\gamma_2\le$\\ \midrule 8 & $6{,}419{,}109$ & $91{,}508{,}397$ & $0.3209$ & $0.341832258719$ & $0.8262791785$ & $0.826280$\\ 9 & $51{,}425{,}006$ & $790{,}078{,}170$ & $0.3298$ & $0.364708361170$ & $0.8251002729$ & $0.825101$\\ 10 & $400{,}253{,}317$ & $6{,}574{,}257{,}580$ & $0.3376$ & $0.385532597280$ & $0.8241195406$ & $0.824120$\\ 11 & $3{,}045{,}043{,}879$ & $53{,}133{,}194{,}463$ & $0.3445$ & $0.404566031012$ & $0.8232896731$ & $0.823290$\\ \ifhtwelve 12 & $22{,}670{,}087{,}101$ & $418{,}139{,}991{,}128$ & $0.3505$ & $\lamTwelve$ & $\bndTwelve$ & $0.822579$\\ \fi \ifhthirteen 13 & $165{,}695{,}219{,}469$ & $3{,}217{,}333{,}414{,}315$ & $0.3568$ & $\lamThirteen$ & $\bndThirteen$ & $0.821963$\\ \fi \bottomrule \end{tabular} \end{table} \iflean \section{Formal verification}\label{sec:lean} The formal proofs use the Lean~4 proof assistant \cite{Lean4}, version 4.35.0-rc3, with the Mathlib library \cite{Mathlib} at the same version. The formal statements define $\LCS(A,B)$, for lists $A$ and $B$ of bits, as the largest length of a list that is a subsequence of both, $\E L_n$ as the average of $\LCS(A,B)$ over the $4^n$ pairs of strings of length $n$, and $\gamma_2$ as the limit of $\E L_n/n$. The formalization proves that this limit exists, from the inequality $\E L_{m+n}\ge\E L_m+\E L_n$ and Fekete's lemma. These are the only definitions that occur in the statements of the theorems below; the automaton and the checking programs are auxiliary definitions, and everything needed about them is proved. The automaton $\Mh$, the reduced transition function and the weights are defined in Lean as in Sections~\ref{sec:automaton} and~\ref{sec:count}, and the covering property (Lemma~\ref{lem:cover}) is proved for every $h\ge2$, in the form used in the proof of Theorem~\ref{thm:count}. Theorem~\ref{thm:count} is proved, together with Lemma~\ref{lem:reduce}, in the following form, which avoids logarithms: if $h\ge2$, $00$, $\theta>0$, $S$ is a set of states that contains $q_0$ and is closed under $\delta_{\mathrm{red}}$, $v>0$ on $S$, the inequality \eqref{eq:cw} with $\delta_{\mathrm{red}}$ in place of $\delta$ holds at every $q\in S$, and $\lambda^\theta<(2z)^2$, then $\gamma_2\le\theta$. A checking program written in Lean verifies a certificate in exact integer arithmetic, and Lean proofs show that a certificate it accepts gives these hypotheses; the transition function of the program is a fast implementation that is proved to agree with the definition of $\Mh$. \ifleanN \ifleanNthirteen \enlargethispage{-\baselineskip}% layout: avoids an underfull page 9 in the states with the h = 13 paragraph The theorem \texttt{CS31aData.gamma2\_le\_n13} states $\gamma_2\le\gmain$, the bound of Theorem~\ref{thm:main}. Its proof runs a version of the checking program on the certificate for $h=13$ of Table~\ref{tab:ladder}, split by rows into $\leanNthirteenparts$ parts. Each part is evaluated with \texttt{native\_decide}, which executes compiled code, so the trusted base includes the Lean compiler; besides the three standard axioms \leanStd, the theorem depends on one auxiliary axiom for each of the $\leanNthirteenparts$ compiled checks, which asserts that the compiled evaluation of that check returned true. This version reads the list in a compact form: for each state, the $20$ least significant of the $52$ bits of the integer that encodes it, and a table that gives, for each value of the $32$ most significant bits, the position in the list of the first state whose $32$ most significant bits are at least that value. It reads the single-precision entries of $v$ and converts them exactly. Each part checks that the table is nondecreasing, so that each position determines one state, and every position that a search in these data returns is checked against them; the Lean proofs that a certificate accepted by this version gives the hypotheses above therefore use no property of the searches, nor of the program that wrote the compact form. Each part took between $1.4$ and $1.7$ hours on a machine with $360$ virtual cores and $2.8$~TiB of memory and needed about $2.3$~TiB; the checks took about $23{,}800$ CPU-hours in total. The bound $\gamma_2\le\gTwelve$ for $h=12$ is proved in the same way by the theorem \texttt{CS31aData.gamma2\_le\_h12}, on $\leanNparts$ parts of the certificate for $h=12$, with the checking program itself, which reads the list and the vector as they are stored. In an independent check of the proof for $h=13$, the data modules were compiled again from the stored pieces of the certificate, and two of the $\leanNthirteenparts$ parts, drawn at random before any result was known, were evaluated again with \texttt{native\_decide}; all compiled files agreed byte for byte with ours, as did the final module compiled again from source. Lean's kernel, run on each module separately, accepted $3{,}137$ of the $3{,}138$ modules, with the compiled checks entering as their auxiliary axioms; the run on the remaining module, which assembles the data in four definitions, ran out of memory on a machine of the same kind, and its compiled file agrees with one compiled independently, during which the kernel checked these four definitions. \else The theorem \texttt{CS31aData.gamma2\_le\_h12} states $\gamma_2\le\gTwelve$, the bound for $h=12$ in Table~\ref{tab:ladder}. Its proof runs the checking program on the certificate for $h=12$ of Table~\ref{tab:ladder}, split by rows into $\leanNparts$ parts. Each part is evaluated with \texttt{native\_decide}, which executes compiled code, so the trusted base includes the Lean compiler; besides the three standard axioms \leanStd, the theorem depends on one auxiliary axiom for each of the $\leanNparts$ compiled checks, which asserts that the compiled evaluation of that check returned true. Each part needed about $860$~GB of memory; one part took about $1.6$ hours on a machine with $192$ virtual cores, and each of the other six about $2.1$ hours on a machine with $224$ virtual cores. \fi \fi \ifleanK The theorems \texttt{CS31aK.H9.gamma2\_le}, \texttt{CS31aK.H10.gamma2\_le}\ifleanKtwelve, \texttt{CS31aK.H11.gamma2\_le} and \texttt{CS31aK.H12.gamma2\_le} state $\gamma_2\le\gJnine$, $\gamma_2\le\gTen$, $\gamma_2\le\gEleven$ and $\gamma_2\le\gTwelve$, the bounds for $h=9$, $10$, $11$ and $12$\else{} and \texttt{CS31aK.H11.gamma2\_le} state $\gamma_2\le\gJnine$, $\gamma_2\le\gTen$ and $\gamma_2\le\gEleven$, the bounds for $h=9$, $10$ and $11$\fi{} in Table~\ref{tab:ladder}. Their proofs are checked entirely by the Lean kernel and do not use \texttt{native\_decide}, so the Lean compiler is not part of their trusted base: each certificate is split into parts, the kernel checks each part with the tactic \texttt{decide +kernel}, and each theorem depends only on \leanStd. Compiled code is used only to read the certificate files into Lean terms when the modules are compiled, and the kernel then checks every step. For $h=9$ the kernel evaluates the checking program on $\leanKparts$ parts, grouped into $32{,}768$ modules, whose checks took about $1{,}900$ CPU-hours in total; for $h=10$ it evaluates the same program on $\leanKtenparts$ parts in $\leanKtenmods$ modules, whose checks took about $21{,}100$ CPU-hours. For $h=11$\ifleanKtwelve{} and $h=12$\fi{} the kernel evaluates a version of the checking program that processes up to $64$ consecutive states of the list together. For each input, each of these states occupies its own $64$-bit field of a single natural number, and the bit operations of the transition function act on all fields at once, with masks that keep shifted bits inside their fields. Lean proofs show that a certificate that this version accepts also gives the hypotheses above. The certificate for $h=11$ is split into $\leanKelevenparts$ parts in $\leanKelevenmods$ modules, whose checks took about $8{,}800$ CPU-hours\ifleanKtwelve, and the certificate for $h=12$ into $\leanKtwelveparts$ parts in $\leanKtwelvemods$ modules, whose checks took about $\leanKtwelvecpuh$ CPU-hours\fi. \fi \fi \ifleanNthirteen\else\clearpage\fi % layout: without the h = 13 paragraph, avoids an underfull page 9 \section{Remarks}\label{sec:remarks} \subsection*{Convergence} By \cite[Theorems~3.13 and~3.26]{Lue09} the bounds obtainable from $\Mh$ converge to $\gamma_2$ as $h\to\infty$, and for history length $h$ they can be made at most $\gamma_2+O((\log h/h)^{1/3})$. The improvements in Table~\ref{tab:ladder} decrease slowly, from $0.001179$ between $h=8$ and $h=9$ to \ifhthirteen$0.000616$ between $h=12$ and $h=13$\else\ifhtwelve$0.000711$ between $h=11$ and $h=12$\else$0.000830$ between $h=10$ and $h=11$\fi\fi, while the number of states grows by a factor that decreases from $8.0$ to \ifhthirteen$7.3$\else\ifhtwelve$7.4$\else$7.6$\fi\fi{} for each step of $h$. \subsection*{The choice of \texorpdfstring{$z$}{z}} For each $h\le12$ the parameter $z$ was chosen near the value that minimizes the bound. For $h=11$, power iterations at $z=0.3425$, $0.3445$ and $0.3465$ indicate that the optimal $z$ lowers the bound by less than $10^{-7}$, which does not change the rounded value.\ifhtwelve{} For $h=12$ we used only $z=0.3505$; a floating-point evaluation of the smallest ratio $(A_zv)_q/v_q$ for an iterate of the power iteration, which bounds the Perron root of $A_z$ from below, indicates that no positive vector gives a bound below $0.822578$ at this $z$.\fi\ifhthirteen{} For $h=13$ we used only $z=0.3568$; the same evaluation for the $99$th iterate, the one before the certificate, indicates that no positive vector gives a bound below $0.821958$ at this $z$.\fi \subsection*{Periodic words} Bukh and Cox \cite[Section~5]{BC22} found a binary word $P$ of length $28$ such that the expected length of a longest common subsequence of a uniformly random binary string of length $n$ and the $n$-letter periodic word with period $P$ is $\gamma_Pn+O(\sqrt n)$ with $\gamma_P\ge\gBC$. An upper bound $\gamma_2<\gBC$ would show that this periodic word is closer to a random string, in this sense, than an independent random string is; they note that the bound $\gamma_2\le\gL$ does not suffice. Theorem~\ref{thm:main} does not suffice either. \section*{Data availability} The checking programs, the search programs, the weights\iflean, the Lean files of Section~\ref{sec:lean}\fi{} and the logs of the checks are archived at \href{https://doi.org/\DOIsupp}{doi:\DOIsupp} and available at \url{\repoURL}. The archive also contains the certificates for $h=8$, $9$, $10$ and $11$, compressed losslessly to $28.3$~GB.\ifhtwelve{} The certificate for $h=12$ consists of two files of $181$~GB each and is not archived; the archived programs regenerate it. A breadth-first search from the start state gives the list of states, whose SHA-256 checksum begins with \texttt{bef385e5}, and $240$ iterations of the deterministic power iteration with $z=0.3505$ give the vector, whose checksum begins with \texttt{\vdetsha}; for these two files the checker reports $\Lambda=\LAMdet$, and any vector for which it reports $\Lambda\le7776819092424481736$ gives the same bound $\gTwelve$. The README of the archive gives the commands, the full checksums and the resources; regenerating and checking the certificate takes less than two and a half hours on a machine with $288$ virtual cores and $2.2$~TB of memory.\fi\ifhthirteen{} The certificate for $h=13$ is not archived either, because of its size: the list of states has $1.33$~TB and the vector, in single precision, $663$~GB. The breadth-first search regenerates the list, whose SHA-256 checksum begins with \texttt{8454e843} and whose fingerprint, as printed by the program used for $h=13$ in Section~\ref{sec:cert}, begins with \texttt{9e2d85eb}. \ifvthirteendet Running $100$ iterations of the distributed power iteration of Section~\ref{sec:search} with $z=0.3568$, started from the vector for $h=12$, regenerates the vector, whose checksum begins with \texttt{\vthirteensha}. \else Any positive vector that this program accepts is a certificate; the vector that we checked comes from the distributed power iteration of Section~\ref{sec:search} with $z=0.3568$, started from the vector for $h=12$, and has a checksum beginning with \texttt{\vthirteensha}. \fi For the checked vector the program used for $h=13$, run on row ranges that cover all states, reports $\Lambda=\LAMthirteen$, and any vector for which it reports $\Lambda\le8116076067129428569$ gives the same bound $\gmain$. The README of the archive gives the commands and the full checksums; the breadth-first search, and each of the four parts of the iteration and of the check, ran on a machine with $160$ virtual cores and $3.8$~TB of memory.\fi \section*{Acknowledgements} Generative AI tools were used to write code, run analyses and draft text; the author directed the work and takes full responsibility for its content. \begin{thebibliography}{99} \bibitem{BC22} B.~Bukh and C.~Cox, \emph{Periodic words, common subsequences and frogs}, Ann. Appl. Probab. \textbf{32} (2022), 1295--1332. \bibitem{CS75} V.~Chv\'atal and D.~Sankoff, \emph{Longest common subsequences of two random sequences}, J. Appl. Probab. \textbf{12} (1975), 306--315. \bibitem{Dan94} V.~Dan\v{c}\'ik, \emph{Expected length of longest common subsequences}, PhD thesis, University of Warwick, 1994. \bibitem{DP95} V.~Dan\v{c}\'ik and M.~Paterson, \emph{Upper bounds for the expected length of a longest common subsequence of two binary sequences}, Random Structures Algorithms \textbf{6} (1995), 449--458. \bibitem{DIT26} D.~Davis, P.~Ivanisvili, T.~Tao and contributors, \emph{Optimization constants in mathematics}, GitHub repository, \url{https://github.com/teorth/optimizationproblems}, page \texttt{constants/31a.md} at commit \texttt{7d762bbb}, 2026. \bibitem{Jac26} L.~Jack, \emph{An improved upper bound on the binary Chv\'atal--Sankoff constant}, GitHub repository \url{https://github.com/leandrejack-afk/chvatal-sankoff-bound}, commit \texttt{472c18de}, 2026. \bibitem{Lue09} G.~S.~Lueker, \emph{Improved bounds on the average length of longest common subsequences}, J. ACM \textbf{56} (2009), no.~3, Article~17. \bibitem{LueCode} G.~S.~Lueker, \emph{Overview of the code}, with the Java programs for the bounds of \cite{Lue09}, \url{https://www.ics.uci.edu/~lueker/papers/lcs/code/}. \iflean\bibitem{Mathlib} The mathlib Community, \emph{The Lean mathematical library}, in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.\fi \iflean\bibitem{Lean4} L.~de~Moura and S.~Ullrich, \emph{The Lean 4 theorem prover and programming language}, in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. \textbf{12699}, Springer, 2021, 625--635.\fi \bibitem{SSMRSH25} D.~Soiffer, A.~Salls, C.~Miller, D.~Reichman, G.~S\'ark\"ozy and G.~Heineman, \emph{Improved lower bounds on the expected length of longest common subsequences}, in: Proc. 2025 IEEE International Symposium on Information Theory (ISIT), 2025, 1--6; arXiv:2407.10925. \end{thebibliography} \end{document}