Certified upper bounds for the Chvátal–Sankoff constant
Version 1 / Nov 15, 2026 / CC BY 4.0
Abstract
Let 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 is . Lueker proved with a finite automaton that reads a pair of strings as a sequence of minimal match pairs and remembers the last symbols of each string, for . We carry out his method up to and prove . For the certificate lists 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. The bound is also proved in the Lean 4 proof assistant, with a computation evaluated by compiled code, and the bounds , , and for , , and by formal proofs that are checked entirely by the Lean kernel.
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.23610945CurrentNov 15, 2026