cert-machine · the registry's asterisks

The Chvátal–Sankoff constant: two asterisked upper bounds replayed

Two asterisks on the Chvátal–Sankoff constant, replayed

On 2026-10-18 the optimization-constants registry merged PR #231: Lueker's 2009 upper-bound method for the binary Chvátal–Sankoff constant, run two history lengths past his paper, giving γ₂ ≤ 0.825101 at h = 9 and γ₂ ≤ 0.824120 at h = 10, below the 0.826280 that had stood since 2009. Both rows carry the registry's asterisk: every check so far was the claimant's own. Here the automaton is rebuilt from Lueker's paper and nothing else, in two implementations, calibrated on his own table, run with witness vectors of our own, and the printed bounds decided.

Published, not peer-reviewed. The claimant's code was neither read nor run: the automaton here is written from Lueker's Figure 7 and weights from his eq. (36); the claimant's commit supplies only the two printed bounds, the two values of z, and the state counts to compare against. Lueker's theorem and his proof that the automaton covers Σ* for every h are the paper's, peer-reviewed in 2009, and are used, not re-proved. The asterisk itself moves only by a pull request the maintainer merges.

tl;dr

The finding. Both rows CERTIFIED by an independent certificate. h = 9: 51,425,006 states (the claimant's 51,425,006), our λ ≤ 0.364708361168896 against the claimant's 0.36470836118429101, bound γ₂ ≤ 0.8251002730 against the printed 0.825101; h = 10: 400,253,317 states (the claimant's 400,253,317), our λ ≤ 0.385532597279844 against the claimant's 0.38553270543451057, bound γ₂ ≤ 0.8241195407 against the printed 0.824120. The construction reproduces Lueker's Table II for h = 2..8 exactly — every state count, every λ to his nine digits, every bound to his six — and the h = 8 transition count the claimant publishes.
The mechanism. Lueker's Theorem 3.3: if the automaton covers Σ*, z ∈ (0, ½), λ ∈ (0, 1) and a positive vector v satisfies A_z v ≤ λ v, then γ₂ ≤ 2 log(2z)/log λ. Any positive v is a witness, so our own vector serves: λ is the largest ratio (A_z v)_s / v_s, computed with the rounding mode set upward in every thread and once more in round-to-nearest with an explicit inflation; the smallest ratio, rounded downward, is a certified lower bound on the spectral radius, below which no claimant's λ can lie.
Check it. python3 tools/run-lueker.py --check re-runs the reference at h ≤ 4, re-derives every decision from the record's own hex values and re-fires the red controls in seconds; python3 tools/run-lueker.py DATA_DIR rebuilds everything up to h = 8 from nothing (minutes) and re-certifies h = 9 and h = 10 from the stored vectors; the h = 10 table itself is 27.5 GB and regenerates deterministically with mh build 10.

rows decided

2 · 2 CERTIFIED

The registry's two asterisked C₃₁ rows, PR #231, merged 2026-10-18.

calibration

7 of 7

Lueker's Table II, h = 2..8: states, λ to nine digits, bounds to six — reproduced from the paper alone.

states at h = 10

400,253,317

The claimant's count 400,253,317; 6,574,257,580 accepted transitions.

reference agreement

166,000 sampled · 0 mismatches

Full tables identical at h ≤ 5; h = 8: 2,000 states, h = 9: 2,000 states, h = 10: 1,000 states re-derived by the Python reference.

red controls

9/9

Wrong weights, a claim below the certificate, a λ below the spectral radius, z = ½, λ = 1, a zero in v, a short v, the all-ones v.

§1 · the claim

What the registry prints, and what was checked before

The constant is the limit of E[LCS(x, y)]/n for two uniformly random binary strings of length n. Its value is unknown; simulations put it near 0.812. The best upper bound since 2009 was Lueker's 0.826280, from his automaton at history length h = 8. The claimant ran the same method at h = 9 and h = 10 and the registry merged both rows on 2026-10-18 with an asterisk, the mark it gives a bound replayed by nobody but its author. The claimant's own repository (cd99c689, pinned under corpus/optconst-queue/c31-2026-10-21) says what was checked: Lueker's unmodified Java agrees with the claimant's tables transition for transition at h ≤ 8 and on 200,000 random states at h = 9 and 10; the code reproduces Lueker's table; a second implementation of Figure 7, by the claimant in a later pass, re-derived every transition; the λ bound was also computed in a variant that does not depend on the rounding mode. A later commit corrects the README's "independent reviewer" to the claimant's own review pass, which is also what the e-mail asking for this replay said. What an outside replay adds is one thing only: another person's reading of Figure 7 and another arithmetic.

h	printed bound	claimant's states	z (the double)	claimant's certified λ	asterisked at pin
9	γ₂ ≤ 0.825101	51,425,006	0.3298	0.36470836118429101	yes
10	γ₂ ≤ 0.824120	400,253,317	0.3376	0.38553270543451057	yes

§2 · the method

Lueker's theorem, and the automaton read from his figure

The theorem. Lueker's Theorem 2 (journal Theorem 3.3), after Dančík–Paterson: M covers Σ*, z ∈ (0, 1/2), λ ∈ (0, 1), v > 0 with A_z v ≤ λ v component-wise ⇒ γ₂ ≤ 2 log(2z)/log λ; any positive v is a witness (eq. 41). The paper was read in the author's extended version (the author's extended version dated 2008-12-18 (41 pages), Wayback Machine capture of 2009-02-05; its Theorem 2, Figure 8 and Figure 9 are the journal's Theorem 3.3, Figure 7 and Table II; sha256 c662fc3b2473…), the journal article being closed and the author's page returning 403 since 2015.

The automaton. A state is (x, y, dx, dy): the last h characters of each string and the last h differences down the last column and along the last row of the dynamic-programming table. An input is a minimal match pair after Lueker's truncation μ: for a match character c, (c̄ᵃ c / c) with 0 ≤ a ≤ h−1 or (c / c̄ᵇ c) with 1 ≤ b ≤ h−1, 4h−2 inputs in all. The transition fills the new table entries with lower bounds (Figure 7, lines 7–13), backtracks canonically (lines 14–22) and rejects when the path misses the old corner. z^{a+2} for a < h−1, z^{h+1}/(1−z) at a = h−1 (eq. 36), rounded up from exact for the certificate. Figure 8 (journal Figure 7), transition by transition; states (x, y, dx, dy); one representative per complement orbit (x̄, ȳ, dx, dy), the symmetry Lueker names in §3.2 and checks here on every state at h = 4. The reference implementation (instruments/lueker/mh.py, standard library, exact where it can be) is the specification; the fast one (instruments/lueker/mh.c) is held to it: identical full tables at h ≤ 5, sampled states re-derived at h = 8, 9 and 10, the complement symmetry checked on every state at h = 4.

The certificate. λ_cert = max_s (A_z v)_s / v_s with FE_UPWARD in every thread (self-tested); λ_free the same in round-to-nearest inflated by (1+2^-52)^(4h−1); ρ_lower = min_s with FE_DOWNWARD, a lower bound on the spectral radius; the bound 2 ln(2z)/ln λ in 60-digit decimal, widened outward. The witness vector comes from power iteration, which only has to make it good; its quality shows in the spread between the largest and smallest ratio.

§3 · calibration

Lueker's Table II, reproduced from the paper alone

Before h = 9 and 10 were touched, the construction had to give Lueker's own numbers. It does: every orbit count, every λ to the nine digits he prints, every bound to his six. At h = 8 the number of accepted transitions, 91,508,397, is the number the claimant publishes for his table, so the two readings of Figure 7 agree transition for transition where both are counted.

h	states (orbits)	Lueker	z	our λ_cert	Lueker's λ	our bound ≤	Lueker's	power iterations
2	7	7	0.2118	0.131204211497	0.131204211	0.845855	0.845855	32
3	98	98	0.2422	0.177752610443	0.177752610	0.839250	0.839250	71
4	1,020	1,020	0.2642	0.217017510099	0.217017510	0.835072	0.835072	101
5	10,160	10,160	0.2828	0.254100606061	0.254100606	0.831910	0.831910	136
6	89,960	89,960	0.2980	0.287155608669	0.287155609	0.829530	0.829530	172
7	780,368	780,368	0.3104	0.316022744106	0.316022744	0.827727	0.827727	211
8	6,419,109	6,419,109	0.3209	0.341832258719	0.341832259	0.826280	0.826280	251

At h = 2..5 the Python reference also decides λ in exact rational arithmetic from its own vector: h = 2 λ = 0.13120421149…, h = 3 λ = 0.17775261044…, h = 4 λ = 0.21701751009…, h = 5 λ = 0.25410060606…, the same digits.

§4 · the rows

h = 9 and h = 10, with our own vectors

Each row: the automaton built here (Apple M2, 16 GB), a vector from power iteration to a relative spread below 10⁻¹³, the certificate pass under directed rounding at the claimant's own z (the exact double nearest the decimal he prints), the bound evaluated outward, and the word.

h	states	accepted	our λ_cert	λ_free (nearest, inflated)	ρ lower bound	claimant's λ	bound ≤	printed	verdict
9	51,425,006	790,078,170	0.36470836116889566	0.36470836116890087	0.36470836116886302	0.36470836118429101	0.8251002730	0.825101	CERTIFIED
10	400,253,317	6,574,257,580	0.38553259727984301	0.38553259727984895	0.38553259727980727	0.38553270543451057	0.8241195407	0.824120	CERTIFIED

h = 9. γ₂ ≤ 0.825100272904 by our certificate, at or below the printed 0.825101. The claimant's λ sits 1.540e-11 above ours and above our certified lower bound on the spectral radius: a certificate a positive vector can reach. Power iteration: 294 passes, ratio spread 9.5e-14; build 81.3 s, iteration 10.6 min, certificate 5.2 s. Files: table 3.3 GB (sha256 316208ccbc5e…), keys 392 MB (c3d2d3fea4ba…), vector 392 MB (888395f17f2e…); 2000 random states (68,000 transitions) re-derived by the reference, 0 mismatches.
h = 10. γ₂ ≤ 0.824119540695 by our certificate, at or below the printed 0.824120. The claimant's λ sits 1.082e-07 above ours and above our certified lower bound on the spectral radius: a certificate a positive vector can reach. Power iteration: 338 passes, ratio spread 9.7e-14; build 3.8 h, iteration 3.4 h, certificate 46.4 s. Files: table 27.5 GB (sha256 a5fb5091773a…), keys 3 GB (8633d1f70da4…), vector 3 GB (a4822c9e044d…); 1000 random states (38,000 transitions) re-derived by the reference, 0 mismatches.

§5 · red controls

What must come out wrong, and does

Every control is re-fired by --check except the three on the binary, which the record keeps with their messages.

control	what	expected	got	fired
weights-off-by-one-power	the weights read as z^{a+1} instead of z^{a+2} at h = 4	DIFFERS from Lueker	0.821413740 (Lueker 0.217017510)	yes
truncation-weight-not-summed	the truncated input weighted z^{h+1} instead of z^{h+1}/(1−z) at h = 4	DIFFERS from Lueker	0.215991524 (Lueker 0.217017510)	yes
claim-below-the-certificate	Lueker's h = 8 certificate against a printed bound 10^-6 below his	REFUSED	REFUSED	yes
lambda-below-the-spectral-radius	a claimant λ one part in 10^9 below our certified lower bound on ρ(A_z) at h = 8	REFUTED	REFUTED	yes
z-at-one-half	z = 1/2, outside Theorem 2's (0, 1/k)	REFUSED	REFUSED	yes
lambda-at-one	λ = 1, outside (0, 1)	REFUSED	REFUSED	yes
vector-with-a-zero	a witness vector with one zero component (h = 5)	REFUSED	REFUSED	yes
vector-wrong-length	a witness vector one component short (h = 5)	REFUSED	REFUSED	yes
all-ones-vector	the all-ones vector as the witness at h = 8: a valid certificate (λ = the largest row sum), too weak for the printed bound	REFUSED	REFUSED	yes

§6 · what is claimed, and what is not

The limits

Claimed. For each row, a certificate of our own — our automaton, our vector, directed rounding, the bound outward — that reaches the printed bound; the construction calibrated on Lueker's published table; the claimant's λ consistent with our certified bracket on the spectral radius.
Used, not re-proved. Lueker's Theorem 3.3 and his proof that M_h covers Σ* for every h (J. ACM 2009, peer-reviewed). A reader who doubts them doubts the 2009 bound too.
Not claimed. That the claimant's own vectors satisfy his inequality under our matrix — his vectors were offered and would make that a one-pass check; that the printed λ is the spectral radius (ours and his are both upper bounds on it, and the gap between them is the vectors' quality, not an error); anything about the lower bound rows of the same page.
Independence. From the claimant, whose code was never opened; not from the operator (one). The second implementation here is a reference the fast one is held to, not a second person.