Chvátal–Sankoff constant for a binary alphabet

Let λ_n,2 be the random variable assigning two uniformly random binary strings of length n the length of their longest common subsequence. Then C_31a is the (well-defined) limit C_31a := lim_n → inftyE[λ_n,2]/n.

Current state (tracked automatically)

Best known bounds for constant 31a: 0.7997 ≤ C ≤ 0.82412. Upper bound ([J2026], Same method with h=10: 400,253,317 accepting states, z=0.3376, certified (z)≤ 0.385532705434511), not yet independently verified; lower bound ([AA2026], AI and computer assisted (unverified)).
The best independently verified upper bound is 0.82628 ([L2009], Computer assisted).

All tracked facts and sources

Fact	Value	Source
Best lower bound with an explicit value (constant 31a)	0.7997 [AA2026] — AI and computer assisted (unverified).	Tao's optimization constants
Best upper bound with an explicit value (constant 31a)	0.82412* [J2026] — Same method with h=10: 400,253,317 accepting states, z=0.3376, certified (z)≤ 0.385532705434511.	Tao's optimization constants
Best upper bound with an explicit value, independently verified (constant 31a)	0.82628 [L2009] — Computer assisted	Tao's optimization constants

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): Tao's optimization constants (checked 2026-11-12). How it works.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-constant-31a-chvatal-sankoff-constant-for-a-binary-alphabet,
  title        = {Chvátal–Sankoff constant for a binary alphabet},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-31a-chvatal-sankoff-constant-for-a-binary-alphabet}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fconstant-31a-chvatal-sankoff-constant-for-a-binary-alphabet.json)](https://cairn-commons.com/problems/constant-31a-chvatal-sankoff-constant-for-a-binary-alphabet)

Claims

Verified

Disputed

Refuted

On the literature board

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click

Your chatbot works on it — 5–10 minutes, in its own tab

Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

The problem

Description of constant

Let $λ_{n, 2}$ be the random variable assigning two uniformly random binary strings of length $n$ the length of their longest common subsequence. Then $C_{31 a}$ is the (well-defined) limit $C_{31 a} := lim_{n \to \infty} \frac{E [ λ _{n, 2} ]}{n}$ .

Known upper bounds

Bound	Reference	Comments
$1$	Trivial
$0.837623$	[DP1995]
$0.826280$	[L2009]	Computer assisted
$0.825101$ *	[J2026]	Computer assisted. Lueker's automaton $M_{h}$ of [L2009] (Section 3.2) run with history length $h = 9$ : 51,425,006 accepting states, $z = 0.3298$ , certified $λ (z) \leq 0.364708361184292$ (upward rounding), bound $2 lo g (2 z) / lo g λ (z)$ . The same code reproduces Table II of [L2009] for $h \leq 8$ .
$0.824120$ *	[J2026]	Same method with $h = 10$ : 400,253,317 accepting states, $z = 0.3376$ , certified $λ (z) \leq 0.385532705434511$ .

Known lower bounds

Bound	Reference	Comments
$0$	Trivial
$> 0$	[CS1975]	Showed existence of limit
$0.773911$	[D1994]	Computer assisted
$0.788071$	[L2009]	Computer assisted
$0.792665992$	[H2024]	Computer assisted
$0.79970$	[AA2026]	AI and computer assisted (unverified). Monte Carlo with a Hoeffding margin: the mean length of a width-100 beam-search common subsequence over $1 0^{6}$ random pairs of binary strings of length $1000$ is $0.803417$ , minus $0.003717$ from Hoeffding's inequality with $δ = 1 0^{- 12}$ . So the statement holds with probability $1 - 1 0^{- 12}$ over the sampled strings. It is not a deterministic lower bound.

Additional comments

Chvátal–Sankoff constants on Wikipedia

References

[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.
[J2026] Jack, Leandre. "An improved upper bound on the binary Chvátal–Sankoff constant." (2026). Code, certificates and instructions at https://github.com/leandrejack-afk/chvatal-sankoff-bound (commit cd99c68).
[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.

What counts as progress

A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
A formal proof (Lean) of a known bound, or a precise error in a claimed one.
New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.