Chvátal–Sankoff constant for a binary alphabet ()
Chvátal–Sankoff constant for a binary alphabet: determine or improve its bounds; the repository records 0.792665992 (0.79970*) (lower) and 0.826280 (upper).
Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.
Problem statement
Let be the random variable assigning two uniformly random binary strings of length the length of their longest common subsequence. Then is the (well-defined) limit .
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
References (from the repository page)
- [CS1975] Chvatal, Václáv, and David Sankoff. "Longest common subsequences of two random sequences." Journal of applied probability 12.2 (1975): 306-315. Available at https://par.cse.nsysu.edu.tw/resource/paper/2013/131230/CS-TR-75-477.pdf
- [H2024] Heineman, George T., et al. "Improved Lower Bounds on the Expected Length of Longest Common Subsequences." arXiv preprint (2024) arXiv:2407.10925.
- [L2009] Lueker, George S. "Improved bounds on the average length of longest common subsequences." Journal of the ACM (JACM) 56.3 (2009): 1-38. Available at https://dl.acm.org/doi/pdf/10.1145/1516512.1516519
- [DP1995] Dančík, Vlado, and Mike Paterson. "Upper bounds for the expected length of a longest common subsequence of two binary sequences." Random Structures & Algorithms 6.4 (1995): 449-458. Available at https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.3240060408
- [D1994] Dancík, Vladimír. Expected length of longest common subsequences. Diss. University of Warwick, 1994. Available at https://wrap.warwick.ac.uk/id/eprint/107547/1/WRAP_Theses_Dancik_1994.pdf
- [AA2026] Archivara Agent. "An Improved Lower Bound on the Chvátal–Sankoff Constant for Binary Strings via Monte Carlo Beam Search." (2026). Available at https://archivara.org/paper/1a5c6a48-a106-40e4-a5f0-97833f3a25a7. Code and reproducible data at https://github.com/spicylemonade/constant.
Progress & source assessment
Repository table (commit 2c1968c, 26 September 2026): best known lower bound 0.792665992 (0.79970*); best known upper bound 0.826280. Values marked with an asterisk have minimal verification.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| Trivial | ||
| [DP1995] | ||
| [L2009] | Computer assisted |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| Trivial | ||
| [CS1975] | Showed existence of limit | |
| [D1994] | Computer assisted | |
| [L2009] | Computer assisted | |
| [H2024] | Computer assisted | |
| [AA2026] | AI and computer assisted (unverified) |
- [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Chvátal–Sankoff constant for a binary alphabet ($C_{31}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.