Certified upper bounds for the Chvátal–Sankoff constant

Contributed by Tejasvi Singh Tomar

Version 2 / Nov 15, 2026 / CC BY 4.0

Abstract

The expected length of a longest common subsequence of two independent uniformly random binary strings of length nn is γ2n+o(n)\gamma_2n+o(n), where γ2\gamma_2 is the Chvátal–Sankoff constant. Simulations suggest γ2≈0.8122\gamma_2\approx0.8122. In 2009 Lueker obtained the bound γ2≤0.826280\gamma_2\le0.826280 with a weighted finite automaton that remembers the last h=8h=8 symbols of each string. We prove γ2≤0.821963\gamma_2\le0.821963 by the same method with h=13h=13, where the automaton has about 1.66⋅10111.66\cdot10^{11} reachable states up to symmetry. The proof rests on an explicit vector v>0v>0 and a number λ<1\lambda<1 with Av≤λvAv\le\lambda v, where AA is the weighted transition matrix; a program checks the inequality Av≤λvAv\le\lambda v entry by entry, in exact arithmetic. The bound is also proved in the Lean 4 proof assistant.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.24414179 Changes from the previous version: the bounds for h = 13 and h = 12 are now also proved in Lean 4 by proofs that Lean's kernel checks without native_decide; corrected: the previous version said that the Lean files are archived, but for the kernel-checked proofs the archive holds the programs that generate them and their SHA-256 checksums, not the generated files; the main theorem and the certificates are unchanged.

References

  1. B. Bukh and C. Cox, Periodic words, common subsequences and frogs , Ann. Appl. Probab. 32 (2022), 1295--1332.
  2. V. Chvátal and D. Sankoff, Longest common subsequences of two random sequences , J. Appl. Probab. 12 (1975), 306--315.
  3. V. Dančík, Expected length of longest common subsequences , PhD thesis, University of Warwick, 1994.
  4. 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.
  5. D. Davis, P. Ivanisvili, T. Tao and contributors, Optimization constants in mathematics , GitHub repository, https://github.com/teorth/optimizationproblems, page constants/31a.md at commit 7d762bbb , 2026.link
  6. L. Jack, An improved upper bound on the binary Chvátal--Sankoff constant , GitHub repository https://github.com/leandrejack-afk/chvatal-sankoff-bound, commit 472c18de , 2026.link
  7. G. S. Lueker, Improved bounds on the average length of longest common subsequences , J. ACM 56 (2009), no. 3, Article 17.
  8. G. S. Lueker, Overview of the code , with the Java programs for the bounds of Lue09 , https://www.ics.uci.edu/~lueker/papers/lcs/code/.link
  9. The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
  10. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, 2021, 625--635.
Show all 11 referencesShow fewer references
  1. D. Soiffer, A. Salls, C. Miller, D. Reichman, G. Sárközy and G. Heineman, 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.arXiv

Version history

  1. v1 · 11 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23610945SupersededNov 15, 2026
  2. v2 · 11 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.24414179 Changes from the previous version: the bounds for h = 13 and h = 12 are now also proved in Lean 4 by proofs that Lean's kernel checks without native_decide; corrected: the previous version said that the Lean files are archived, but for the kernel-checked proofs the archive holds the programs that generate them and their SHA-256 checksums, not the generated files; the main theorem and the certificates are unchanged.CurrentNov 21, 2026