Certified upper bounds for the Chvátal–Sankoff constant
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 is , where is the Chvátal–Sankoff constant. Simulations suggest . In 2009 Lueker obtained the bound with a weighted finite automaton that remembers the last symbols of each string. We prove by the same method with , where the automaton has about reachable states up to symmetry. The proof rests on an explicit vector and a number with , where is the weighted transition matrix; a program checks the inequality entry by entry, in exact arithmetic. The bound is also proved in the Lean 4 proof assistant.
References
- B. Bukh and C. Cox, Periodic words, common subsequences and frogs , Ann. Appl. Probab. 32 (2022), 1295--1332.
- V. Chvátal and D. Sankoff, Longest common subsequences of two random sequences , J. Appl. Probab. 12 (1975), 306--315.
- V. Dančík, Expected length of longest common subsequences , PhD thesis, University of Warwick, 1994.
- 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.
- 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
- 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
- G. S. Lueker, Improved bounds on the average length of longest common subsequences , J. ACM 56 (2009), no. 3, Article 17.
- 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
- The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
- 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
- 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
- v1 · 11 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23610945SupersededNov 15, 2026
- 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