TejasviTomar
October 2026 · Preprint

Certified upper bounds for the Chvátal–Sankoff constant

Tejasvi Singh Tomar

In plain words

A longest common subsequence of two strings is a longest string that can be read in both by skipping symbols. The file-comparison program diff computes one, treating each line as a symbol. For random strings of 0s and 1s of equal length, Chvátal and Sankoff showed in 1975 that the average length of a longest common subsequence, divided by the string length, approaches a fixed number as the strings grow. Lueker proved an upper bound of 0.826280 in 2009, and computations posted in October 2026 reached 0.824120. Pushing his method further brings the bound down to 0.822579.

Abstract

Let γ2 be the Chvátal–Sankoff constant, so that the expected length of a longest common subsequence of two independent uniformly random binary strings of length n is γ2n + o(n). Lueker proved γ2 ≤ 0.826280 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 = 12 and prove γ2 ≤ 0.822579. For h = 12 the certificate lists 22,670,087,101 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.

A square grid shaded from white at the top left to dark teal at the bottom right, crossed by thin white staircase lines and sprinkled with small grey dots. A black path runs from near the top left corner to the bottom right corner close to the diagonal, with a yellow dot at each diagonal step and small magenta patches along it, some of them short bars. Rows of black and white squares run along the top and left edges, and a green square outline, edged in black, sits on the path near the middle, with matching green bars beside the two rows of squares.
Illustration of the canonical decomposition for two random binary strings of length 48, A down the left and B across the top (black squares are 1s, white squares 0s). Each cell (i, j) is shaded by the length of a longest common subsequence of the first i symbols of A and the first j symbols of B, darker where it is longer, with white lines between cells of different value; grey dots mark the cells where the two symbols agree. The black path is the canonical traceback, and its 39 diagonal steps, the yellow dots, give a longest common subsequence. The magenta patches are the minimal match pairs between consecutive diagonal steps, which Lueker's automaton reads one at a time. The green square spans the last 12 symbols of each string once the first 24 pairs have been read. The automaton with history length 12 keeps these symbols, together with the increments down the last column and along the last row of its own table, which it updates from its previous state and the new pair alone; so they need not match the table shown, and here one of them differs.