\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} \raggedbottom \relpenalty=9999 \binoppenalty=9999 \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} \newcommand{\hmain}{13} \newcommand{\gmain}{0.821963} \newcommand{\zmain}{0.3568} \newcommand{\Nmain}{165{,}695{,}219{,}469} \newcommand{\Emain}{3{,}217{,}333{,}414{,}315} \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.24414180} \newcommand{\repoURL}{https://github.com/tejasvi/chvatal-sankoff-certificates/tree/v6} \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, 68V20} \keywords{Chv\'atal--Sankoff constant, longest common subsequence, random strings, Lueker's method, finite automata, computer-assisted proof, Lean~4} \begin{abstract} The expected length of a longest common subsequence of two independent uniformly random binary strings of length $n$ is $\gamma_2n+o(n)$, where $\gamma_2$ is the Chv\'atal--Sankoff constant. Simulations suggest $\gamma_2\approx0.8122$. In 2009 Lueker obtained the bound $\gamma_2\le\gL$ with a weighted finite automaton that remembers the last $h=8$ symbols of each string. We prove $\gamma_2\le\gmain$ by the same method with $h=\hmain$, where the automaton has about $1.66\cdot10^{11}$ reachable states up to symmetry. The proof rests on an explicit vector $v>0$ and a number $\lambda<1$ with $Av\le\lambda v$, where $A$ is the weighted transition matrix; a program checks the inequality $Av\le\lambda v$ entry by entry, in exact arithmetic. The bound is also proved in the Lean~4 proof assistant. \end{abstract} \maketitle \enlargethispage{3pt} \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{BC22}. Dan\v{c}\'ik \cite{Dan94} proved $\gamma_2\ge\gDPlow$. Dan\v{c}\'ik and Paterson \cite{DP95} (see also \cite{Dan94}) proved $\gamma_2\le\gDP$ with a $52$-state automaton. Lueker \cite{Lue09} improved both bounds, to $\gLlow\le\gamma_2\le\gL$; the lower bound has since been improved to $\glow$ \cite{SSMRSH25}. Lueker's upper-bound technique uses finite automata $M_h$ that read a pair of strings as a sequence of minimal match pairs (Section~\ref{sec:mmp}); here $h$ is the history length: $M_h$ remembers the last $h$ symbols of each string. The bound $\gL$ comes from $M_8$, which has $6{,}419{,}109$ reachable states after a symmetry reduction \cite[Table~II]{Lue09}, \cite{LueCode}. This bound shows that the value $2/(1+\sqrt2)\approx0.828427$ conjectured by Steele is too large \cite{Lue09}. Lueker also proved that the bounds obtainable from $M_h$ converge to $\gamma_2$ as $h\to\infty$. Jack \cite{Jac26} has computed the bounds of Lueker's method for $h=9$ and $h=10$: $\gamma_2\le\gJnine$ and $\gamma_2\le\gJ$, respectively. The known bounds on $\gamma_2$ are collected in \cite[page~31a]{DIT26}. We prove the following bound. \begin{theorem}\label{thm:main} $\gamma_2\le\gmain$. \end{theorem} Bukh and Cox \cite[Section~5]{BC22} found a binary word $P$ of length $28$ with the following property. Let $P_n$ be the $n$-letter periodic word with period $P$; then the expected length of a longest common subsequence of $P_n$ and a uniformly random binary string of length $n$ 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 than an independent random string is, in the sense of the expected length of a longest common subsequence. Bukh and Cox note that the bound $\gamma_2\le\gL$ does not suffice for this comparison; the bound of Theorem~\ref{thm:main} does not suffice either, but it comes within $0.0008$ of $\gBC$. We follow Lueker's method. A pair of strings decomposes canonically into minimal match pairs followed by a final pair of strings with no matching symbols (Lemma~\ref{lem:canon}). There is one minimal match pair for each symbol of a particular longest common subsequence, the one found by the canonical traceback of Section~\ref{sec:canon}. The automaton $\Mh$ reads the minimal match pairs one at a time. Its state records the last $h$ symbols of each string, the last $h$ increments down the last column of the dynamic programming table, and the last $h$ increments along its last row. When the canonical traceback rule shows that the pair just read cannot be the next pair of a canonical decomposition, the automaton rejects this pair. Each minimal match pair of size $s$ (the total length of its two strings) gets the weight $z^s$; let $A_z$ be the weighted transition matrix of $\Mh$. If $00$ on the states satisfies $A_zv\le\lambda v$ for some $0<\lambda<1$, then $\gamma_2\le2\ln(2z)/\ln\lambda$ (Theorem~\ref{thm:count}). Lueker introduced the automata $\Mh$ and this way of bounding $\gamma_2$ with them \cite{Lue09}; the counting bound of Theorem~\ref{thm:count} is due to Dan\v{c}\'ik and Paterson \cite{Dan94,DP95}, in the form stated in \cite[Theorem~3.3]{Lue09}. A certificate consists of three parts: the parameter $z$; the states reachable from the start state, up to the symmetry that complements every symbol (Lemma~\ref{lem:reduce}); and a vector $v$ on these states, found by a power iteration. Our checking program, the checker of Section~\ref{sec:cert}, computes $\lambda$ from these data. Theorem~\ref{thm:main} comes from a certificate for $h=\hmain$. Table~\ref{tab:ladder} lists the bounds that we obtain with the same method for $h=8,\dots,\hmain$, each at one chosen value of $z$ (Section~\ref{sec:z}); for $h=8$ we recover Lueker's value $\gL$, and for $h=9$ and $h=10$ we recover the values of \cite{Jac26}. Our verification differs from the earlier computations in two respects. First, the final bound of \cite{Lue09} is justified there under the assumption that the floating-point operations of Lueker's program perform as expected \cite[Section~3.2.2]{Lue09}. 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 (the checker and two further implementations of its checks; Section~\ref{sec:checker}) verify the required inequalities \eqref{eq:cw} of Section~\ref{sec:count} exactly. They work in integer arithmetic, for a rational parameter $z$, with the weights of the inputs rounded up to integer multiples of $2^{-64}$ (Section~\ref{sec:cert}). Second, Lueker explains why the automaton never rejects the canonical decomposition of a pair of strings \cite[Section~3.2]{Lue09}; we give a detailed proof of this property, which we call the covering property (Lemma~\ref{lem:cover}). Theorem~\ref{thm:main} has also been proved in the Lean~4 proof assistant (Section~\ref{sec:lean}). The formal proof does not use \texttt{native\_decide}, a tactic that executes compiled code; instead, the certificate of Section~\ref{sec:cert} is split into parts, and Lean's kernel checks each part. The formal proof covers the whole argument, from the definition of $\gamma_2$ to the check of the certificate. 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. Section~\ref{sec:lean} describes the formal proofs, 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|$ for its length, $A[i]$ for its $i$th symbol and $A[i..j]$ for $A[i]A[i+1]\cdots A[j]$. 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, for all $r,s\ge1$, the recurrence \eqref{eq:rec} with $W,a_r,b_s$ in place of $L,A[i],B[j]$. 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 $t=W(r-1,s-1)$, $t'=W(r-1,s)$ and $t''=W(r,s-1)$; by induction $t',t''\in\{t,t+1\}$. If $a_r=b_s$, then $W(r,s)=t+1$ lies in $\{t',t'+1\}$ and in $\{t'',t''+1\}$. Otherwise $W(r,s)=\max\{t',t''\}$, which lies in $\{t',t'+1\}$ and in $\{t'',t''+1\}$ because $|t'-t''|\le1$. \end{proof} In particular all increments of $L$ lie in $\{0,1\}$, so $L$ is nondecreasing in each argument. \subsection{Minimal match pairs}\label{sec:mmp} 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 pair of positions $(i,j)\ne(|u|,|w|)$. 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 symbol of the other string except its last differs from $c$. \end{proof} \subsection{The canonical decomposition}\label{sec:canon} 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$ and $j>j_m$. Moreover $L(i_k,j_k-1)=L(i_k-1,j_k)=k-1$. If $p_k=T_{c,l}$ with $l<0$ and $k\ge2$, then \begin{equation}\label{eq:C} L(i_{k-1}-1,j)i_m$ and $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, by the remark before Lemma~\ref{lem:canon}. 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 all these steps are left steps along row $i_{k-1}$, and $L=k-1$ at every cell they pass. A left step at $(i_{k-1},j)$ with $j\ge1$ is taken only if the rule does not move up, that is, $L(i_{k-1}-1,j)h$, in row-major order, by \eqref{eq:rec} with $W,a_r,b_s$ in place of $L,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)$. Steps (3)--(5) read only cells that are 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); in steps (4) and (5), because these steps read only cells with $\max\{r,s\}>h$ and cells of row $h$ or 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 (column $h$) whose increments lie in $\{0,1\}$: up to row $h$ they are given by $d_x$, and below row $h$ by the first rectangle. So Lemma~\ref{lem:incr} applies again, and the increments of $W$ on the filled region, the union of these two rectangles, lie in $\{0,1\}$. Hence the new $d_x'$ and $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. A diagonal step from a cell of row $h$ or column $h$ leaves the region of cells with both coordinates at least $h$, so the input would be rejected. A diagonal step at a filled cell $(r,s)$ with $r,s>h$ requires $a_r=b_s$ by \eqref{eq:rec}, and this happens only at $(\aLen,\bLen)$, since $T_{c,l}$ is a minimal match pair. For $q=(x,y,d_x,d_y)$ put $\bar q=(\bar x,\bar y,d_x,d_y)$. Complementing every symbol of $a$, $b$ and of the input does not change any comparison. Hence $T_{\cb,l}$ is rejected at $\bar q$ if and only if $T_{c,l}$ is rejected at $q$, and otherwise \begin{equation}\label{eq:sym} \delta(\bar q,T_{\cb,l})=\overline{\delta(q,T_{c,l})}. \end{equation} Let $\rep(q)=\bar q$ if $x[1]=1$, and let $\rep(q)=q$ otherwise. We call a state $q$ \emph{reduced} if $x[1]=0$. The \emph{reduced automaton} has the reduced states as its states and $\delta_{\mathrm{red}}=\rep\circ\delta$ as its transition function; it is the automaton of Lueker's programs. Truncation sends an arbitrary minimal match pair to an input: $\mu(T_{c,l^\circ})=T_{c,l}$ with $l=\operatorname{sign}(l^\circ)\min\{|l^\circ|,h-1\}$. For $0h-1$, the truncation removes symbols $\cb$ at the left end of the longer string. 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 cells set in step (2), the claim follows from $(\mathrm{Inv}_k)$ and the monotonicity of $L^*$; for the cells of row $h$ and column $h$, the claim is $(\mathrm{Inv}_k)$. For a cell filled in step (3), induct in the order of filling. If $a_r=b_s$, then $A^*[\phi(r)]=B^*[\psi(s)]$, since $\phi$ and $\psi$ preserve symbols. As $\phi(r-1)\le\phi(r)-1$ and $\psi(s-1)\le\psi(s)-1$, we get \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)+C\le L^*(I'-1,J')=h+k=W(h,h)+C$, because $\psi(h+1)=J'$ and $\phi(\aLen-1)=I'-1$ (also when $\aLen=h+1$, since then $l^\circ=0$). Since also $W(\aLen-1,h+1)\ge W(\aLen-1,h)=W(h,h)$, we get $W(\aLen-1,h+1)=W(h,h)$. Since $a_\aLen=b_\bLen$, we get $W(\aLen,\bLen)=W(\aLen-1,h)+1=W(h,h)+1$, which exceeds both $W(\aLen-1,\bLen)=W(\aLen-1,h+1)$ and $W(\aLen,\bLen-1)=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$, we have $\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} By the Collatz--Wielandt bound, a positive vector $v$ with $A_zv\le\lambda v$ shows that the Perron root of $A_z$ is at most $\lambda$; the proof above uses the inequality $A_zv\le\lambda v$ only through the iterated inequalities $A_z^kv\le\lambda^kv$. 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 $z$ and $\lambda$ be as in Theorem~\ref{thm:count}, and 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}}\}$, with $v$ extended by $v(\bar q)=v(q)$, satisfies 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; it satisfies $v(q')=v(\rep(q'))$ for all $q'\in S$. For $q\in S_{\mathrm{red}}$ and an accepted input $p$, the states $\delta(q,p)$ and $\delta_{\mathrm{red}}(q,p)=\rep(\delta(q,p))$ differ at most by complementation, and $\delta_{\mathrm{red}}(q,p)\in S_{\mathrm{red}}$. 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 the left sum runs over the inputs accepted at $\bar q$ and the right sum over the inputs $T_{\cb,l}$ accepted at $q$. \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 the list. The entries of $v$ are stored as double-precision floating-point numbers (single-precision for $h=13$), and we read them as exact dyadic rationals. Each state is stored as the integer $x\cdot2^{3h}+y\cdot2^{2h}+d_x\cdot2^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}\label{sec:checker} The checker rebuilds the transitions with its own implementation of steps (1)--(5) and of $\rep$. This implementation is a direct dynamic programming computation of the table $W$ of steps (1)--(5); it marks which cells are defined and stops if a cell read in steps (3) or (4) is undefined (step (5) reads only cells filled in step (3)). It also asserts two facts: all increments lie in $\{0,1\}$, and an accepted input causes exactly one diagonal step. The checker also checks that the list is strictly increasing and consists of integers below $2^{4h}$, that the list contains $q_0$, that $\delta_{\mathrm{red}}(q,p)$ is listed for every listed state $q$ and every input $p$ accepted at $q$, and that every entry of $v$ is a positive normal floating-point number. For \eqref{eq:cw} the checker uses the integer weights $\hat w_j=\lceil2^{64}w_z(T_{c,l})\rceil$, where $j=|l|$. A separate script computes these weights from the exact rational $z$, and the same $z$ is used for the final bound. The checker writes each entry of $v$ exactly as $m\cdot2^e$ with integers $m$ and $e$. For every state $q$ it then evaluates, in $128$-bit integer arithmetic, the sum of the terms $\hat w_{|l|}\,v(\delta_{\mathrm{red}}(q,T_{c,l}))$ over the accepted inputs, with each term scaled to the exponent of $v(q)$; terms that are shifted to the right are rounded up. Write $v(q)=m_q\cdot2^{e_q}$ and let $\sigma_q$ be the scaled sum at $q$; the checker reports $\Lambda=\max_q\Lambda_q$, where $\Lambda_q=\lceil\sigma_q/m_q\rceil$. If the sum at some state $q$ (the row of $q$ in $A_zv\le\lambda v$) overflows, 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 $h=9$, $10$, $11$ and $12$ by its own breadth-first search and verified these four certificates; in each case the smallest $\Lambda$ for which its check passes equals the value reported by the first checker. The second checker also accepted the certificate for $h=8$. The certificate for $h=13$ was checked by a third implementation of the same checks, written for the size of this certificate. The third implementation computes the transitions by an incremental version of the dynamic programming computation and evaluates \eqref{eq:cw} in the same exact arithmetic. Before the third implementation was used, its transition function was compared with that of the checker on every reachable state and every input for $h\le10$; the README of the archive (see Data availability) describes this comparison and further tests of the checking programs, among them tests with altered certificates. The third implementation also reported the same $\Lambda$ as the checker on the certificates for $h=8$, $9$ and $10$. For $h=13$ the numbers of accepted transitions counted by the third implementation agree with those found by the breadth-first search of Section~\ref{sec:search}, which uses a different transition function. The Lean proof of Section~\ref{sec:lean} checks the inequality \eqref{eq:cw} at every state again. \subsection{Search}\label{sec:search} The vectors $v$ come from a power iteration. Any positive vector that passes the check gives a valid certificate; the iteration only serves to make $\Lambda$ small. For $h=12$ the certificate comes from a deterministic version of the iteration, whose output does not depend on the processor or the number of threads. For $h=13$, the certificate comes from a version of the iteration distributed over four machines, with the iterates stored in single precision. This iteration starts from the vector for $h=12$: each state for $h=13$ gets the value of that vector at the state for $h=12$ obtained by deleting the oldest symbol of each of $x$, $y$, $d_x$, $d_y$ and reducing by the symmetry, or, if there is no such state, the smallest entry of that vector. The state sets are found by breadth-first search from $q_0$. The search programs for $h=12$ and $h=13$ use a faster, bit-parallel transition function (Section~\ref{sec:valid}); none of the checking programs uses any code of the search programs. The README describes all programs and runs of Sections~\ref{sec:cert} and~\ref{sec:lean}, with the machines and the running times. \subsection{Validation of the automaton}\label{sec:valid} For $h=2$ our programs reproduce the transition table of the $7$-state automaton printed in the description of Lueker's programs \cite{LueCode}. For $h=2,\dots,8$ the numbers of reachable reduced states are $7$; $98$; $1{,}020$; $10{,}160$; $89{,}960$; $780{,}368$; and $6{,}419{,}109$, as in \cite[Table~II]{Lue09}. 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$ agree with those of \cite{Jac26}. For $h\le10$, the transition function of the checker agrees, on every input at every reachable state, with both the direct and the bit-parallel transition functions of the search programs. \subsection{Results} Table~\ref{tab:ladder} summarizes 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 check that $\delta_{\mathrm{red}}(q,p)$ is listed (Section~\ref{sec:checker}), and is closed under $\delta_{\mathrm{red}}$; moreover, the inequality \eqref{eq:cw} holds at each state of $R$. Theorem~\ref{thm:count}, together with Lemma~\ref{lem:reduce} applied to $R$ and the restriction of $v$, gives the bound in each row of Table~\ref{tab:ladder}. 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 reachable states and accepted transitions refer to the reduced automaton. The column headed ``$\lambda\le$'' gives $\lambda=\Lambda/2^{64}$ rounded up to $12$ decimals. The next column gives $2\ln(2z)/\ln\lambda$, computed with the exact $\lambda$ and truncated to $10$ decimals; the last column gives the same quantity rounded up to six decimals.}\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$\\ 12 & $22{,}670{,}087{,}101$ & $418{,}139{,}991{,}128$ & $0.3505$ & $\lamTwelve$ & $\bndTwelve$ & $0.822579$\\ 13 & $165{,}695{,}219{,}469$ & $3{,}217{,}333{,}414{,}315$ & $0.3568$ & $\lamThirteen$ & $\bndThirteen$ & $0.821963$\\ \bottomrule \end{tabular} \end{table} \subsection{The choice of \texorpdfstring{$z$}{z}}\label{sec: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. For $h=12$ we used only $z=0.3505$. For an iterate $v$ of the power iteration, the smallest ratio $(A_zv)(q)/v(q)$ is at most the Perron root of $A_z$, by the Collatz--Wielandt bound; a floating-point evaluation of this ratio indicates that no positive vector gives a bound below $0.822578$ at this $z$. For $h=13$ we used only $z=0.3568$; the same evaluation for the $99$th iterate, the iterate just before the one used in the certificate, indicates that no positive vector gives a bound below $0.821958$ at this $z$. \section{Formal verification}\label{sec:lean} The formal proofs use the Lean~4 proof assistant \cite{Lean4} with the Mathlib library \cite{Mathlib}. The formal statements define three objects: $\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, using the inequality $\E L_{m+n}\ge\E L_m+\E L_n$ and Fekete's lemma. These three definitions are the only ones 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}. 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 (i) $h\ge2$, $00$ and $\theta>0$, (ii) $S$ is a set of states that contains $q_0$ and is closed under $\delta_{\mathrm{red}}$, (iii) $v>0$ on $S$, (iv) the inequality \eqref{eq:cw} with $\delta_{\mathrm{red}}$ in place of $\delta$ holds at every $q\in S$, and (v) $\lambda^\theta<(2z)^2$, then $\gamma_2\le\theta$. A checking program written in Lean verifies a certificate, and Lean proofs show that every certificate accepted by this program yields data that satisfy these hypotheses; the transition function of the program is a fast implementation that is proved to agree with the definition of $\Mh$. Theorem~\ref{thm:main} is proved in Lean by the theorem \texttt{K13TopH13.gamma2\_le}, and the bounds for $h=9,\dots,12$ in Table~\ref{tab:ladder} are proved by four further theorems. All five are in Lean files written by generator programs, and these programs are archived (see Data availability). These proofs use no \texttt{native\_decide}, and their trusted base is Lean's kernel, including the kernel's built-in arithmetic on natural numbers. Each certificate is split into parts, and the kernel checks each part with the tactic \texttt{decide +kernel}. Compiled code runs only while the data modules, which hold the certificate, are compiled; at that stage, compiled code builds the Lean terms of these modules from the certificate files or from pieces cut from these files. For $h\ge11$ the checking program packs up to $64$ consecutive states of the list into one natural number and processes them together, using bit operations. Lean proofs show that every certificate accepted by this packed version of the program also yields data that satisfy the hypotheses above. For $h=13$ the checking program looks up, in the data modules, each entry that it needs, and the Lean proofs assume nothing about these entries, not even their order or the uniqueness of their keys, so the proof does not depend on how the pieces were cut. Each of the five theorems for $h=9,\dots,13$ depends only on the axioms \leanStd. For Theorem~\ref{thm:main} this statement about axioms rests on two things: the tables of axioms that are stored in the compiled module files and read by Lean's \texttt{\#print axioms}, and a scan of the proof terms. The scan covered all modules of this proof except $4{,}414$ of its $4{,}478$ data modules.\footnote{The scan found no reference to \texttt{sorryAx}, \texttt{Lean.ofReduceBool}, \texttt{Lean.ofReduceNat} or \texttt{Lean.trustCompiler}, and no scanned constant is an axiom or an \texttt{opaque}, \texttt{implemented\_by}, \texttt{extern} or \texttt{unsafe} declaration. For the $4{,}414$ unscanned modules the statement about axioms rests on the stored tables alone; the kernel checked these modules again, and the compiled files of these modules match the checksums recorded when the files were built.} Proofs that evaluate the checks with \texttt{native\_decide}, which executes compiled code, also exist for $h=12$ and $h=13$; their trusted base includes the Lean compiler, through one auxiliary axiom for each compiled check. \section{Remarks}\label{sec:remarks} Lueker's proof of convergence \cite[Theorems~3.13 and~3.26]{Lue09} also gives a rate: for history length $h$ the bounds can be made at most $\gamma_2+O((\log h/h)^{1/3})$. The improvements in Table~\ref{tab:ladder} decrease slowly: from $h=8$ to $h=9$, the bound improves by $0.001179$, and from $h=12$ to $h=13$ by $0.000616$. Meanwhile the number of states grows by a factor that decreases from $8.0$ (from $h=8$ to $h=9$) to $7.3$ (from $h=12$ to $h=13$). Theorem~\ref{thm:main} leaves open whether $\gamma_2<\gamma_P$ for the word $P$ of Bukh and Cox (Section~\ref{sec:intro}). \section*{Data availability} The checking programs, the search programs, the weights, the Lean files of Section~\ref{sec:lean} and the logs of the checks are archived at \href{https://doi.org/\DOIsupp}{doi:\DOIsupp} and available at \url{\repoURL}. For the proofs that use no \texttt{native\_decide}, the archive holds the programs that generate their Lean files and the \mbox{SHA-256} checksums of these files, not the generated files themselves. The Lean files use Lean~4.35.0-rc3 and Mathlib at its tag \texttt{v4.35.0-rc3}, as pinned in \texttt{lean/lake-manifest.json}. The archive also contains the certificates for $h=8$, $9$, $10$ and $11$, compressed losslessly to $28.3$~GB. 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; its \mbox{SHA-256} checksum begins with \texttt{bef385e5}. Then $240$ iterations of the deterministic power iteration with $z=0.3505$ give the vector; its checksum begins with \texttt{\vdetsha}. For these two files the checker reports $\Lambda=\LAMdet$, and any vector for which the checker reports $\Lambda\le7776819092424481736$ gives the same bound $\gTwelve$. The README of the archive gives the commands, the full checksums and the computing resources needed; 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. The certificate for $h=13$ is not archived either, because of its size: the list of states takes $1.33$~TB, and the vector, stored in single precision, takes $663$~GB. The breadth-first search regenerates the list. Its \mbox{SHA-256} checksum begins with \texttt{8454e843}. Its $64$-bit fingerprint, as printed by the checking program used for $h=13$ (the third implementation in Section~\ref{sec:cert}), begins with \texttt{9e2d85eb}. Any positive vector accepted by this program gives a certificate. The checked vector has a checksum beginning with \texttt{\vthirteensha}; it comes from the distributed power iteration of Section~\ref{sec:search} with $z=0.3568$, started from the vector for $h=12$. 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 ran on a machine with $160$ virtual cores and $3.8$~TB of memory, and so did each of the four parts of the iteration and each of the four parts of the check. For the Lean proof of Theorem~\ref{thm:main} the archive also contains its hand-written Lean files; the programs that cut the certificate into pieces and generate the other $2{,}921{,}665$ source files; the \mbox{SHA-256} checksums of all generated source files and of the compiled modules that hold the certificate data; and the records of the scan described in Section~\ref{sec:lean}. The generated files are not archived: once compiled, the $4{,}478$ data modules of this proof take $3.50$~TB on their own. The README gives the commands that regenerate these files and the resources needed to do so. \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/}. \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.\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.\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}