Certified upper bounds for the Chvátal–Sankoff constant

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 15, 2026 / CC BY 4.0

Abstract

Let γ2\gamma_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 nn is γ2n+o(n)\gamma_2n+o(n). Lueker proved γ2≤0.826280\gamma_2\le0.826280 with a finite automaton that reads a pair of strings as a sequence of minimal match pairs and remembers the last hh symbols of each string, for h=8h=8. We carry out his method up to h=13h=13 and prove γ2≤0.821963\gamma_2\le0.821963. For h=13h=13 the certificate lists 165,695,219,469165{,}695{,}219{,}469 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 γ2≤0.821963\gamma_2\le0.821963 is also proved in the Lean 4 proof assistant, with a computation evaluated by compiled code, and the bounds γ2≤0.825101\gamma_2\le0.825101, γ2≤0.824120\gamma_2\le0.824120, γ2≤0.823290\gamma_2\le0.823290 and γ2≤0.822579\gamma_2\le0.822579 for h=9h=9, 1010, 1111 and 1212 by formal proofs that are checked entirely by the Lean kernel.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23610945

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.23610945CurrentNov 15, 2026