The Chvátal–Sankoff constant for binary strings

Two random binary strings of length $n$ share a common subsequence of length about $\gamma n$. Chvátal and Sankoff proved in 1975 that the constant $\gamma$ exists; fifty years later it is known only to lie between 0.7926 and 0.8263, and both bounds come from large exact computations that can be rerun.

Problem

Let $X$ and $Y$ be independent, uniformly random strings in $\{0,1\}^n$, and let $L_n$ be the length of a longest common subsequence of $X$ and $Y$ (a subsequence need not be contiguous). Chvátal and Sankoff showed that the limit

$$\gamma = \lim_{n \to \infty} \frac{\mathbb{E}[L_n]}{n}$$

exists. Determine $\gamma$, or narrow the rigorous bounds $0.792665992 \le \gamma \le 0.826280$.

Background

The longest common subsequence is a standard measure of similarity between strings. Chvátal and Sankoff (1975) proved that $\mathbb{E}[L_n]/n$ converges without identifying the limit; the analogous constants for larger alphabets and more strings are also open. Lower bounds come from large exact computations on finite strings, and upper bounds from counting arguments organised by finite automata, so progress has tracked improvements in algorithms and hardware.

What is known

• Upper bounds: $0.837623$ (Dančík and Paterson, 1995); $0.826280$ (Lueker, 2009, computer-assisted).
• Lower bounds: $0.773911$ (Dančík, 1994); $0.788071$ (Lueker, 2009); $0.792665992$ (Heineman, Miller, Reichman, Salls, Sárközy and Soiffer, 2024), from an optimized and parallelized version of the earlier lower-bound algorithms.
• Unverified claims (asterisked on the source): an upper bound of $0.824120$ (Jack, 2026), from Lueker's automaton method run at history length 10 with about 400 million accepting states (history length 9 gives $0.825101$); and a lower bound of $0.79970$ (Archivara, 2026), produced with AI assistance and marked unverified on the source.

What would count as progress

• A rigorous upper bound below $0.826280$, or an independent rerun of Jack's computation with certified (outward-rounded) arithmetic, which would establish $0.824120$. The automaton at history length 10 is large but finite, so the computation can be repeated by a second implementation.
• A rigorous lower bound above $0.792665992$, with code that recomputes it exactly, or a check of whether the claimed $0.79970$ is a valid bound.
• A new method for either side that scales better than enlarging the existing computations.

References

1. V. Chvátal and D. Sankoff, "Longest common subsequences of two random sequences", Journal of Applied Probability 12 (1975), 306–315. doi:10.2307/3212444
2. V. Dančík and M. Paterson, "Upper bounds for the expected length of a longest common subsequence of two binary sequences", Random Structures & Algorithms 6 (1995), 449–458. doi:10.1002/rsa.3240060408
3. G. S. Lueker, "Improved bounds on the average length of longest common subsequences", Journal of the ACM 56 (2009), 1–38. doi:10.1145/1516512.1516519
4. G. T. Heineman, C. Miller, D. Reichman, A. Salls, G. Sárközy and D. Soiffer, "Improved lower bounds on the expected length of longest common subsequences" (2024). arXiv:2407.10925

Source

Imported from Optimization Constants in Mathematics, constant 31, curated by Terence Tao and contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.