Upper bounds for the Chvátal–Sankoff constants $\gamma_k$, $k\ge3$

David Niedbala Giraudin

Upper bounds for the Chvátal–Sankoff constants $\gamma_k$ , $k\ge3$

Primarily AI-generated textHuman understanding: no partsmath.PR — Probability math.CO — Combinatorics cs.DM — Discrete Mathematics

Contributed by David Niedbala Giraudin ↗

Version 1 / Nov 02, 2026 / CC BY 4.0

Abstract

Lueker (J. ACM 56(3), 2009) constructed a family of finite-state machines

\mathcal{M}_h

whose associated transfer matrices yield upper bounds on the Chvátal–Sankoff constants

\gamma_k

, and proved (his Theorem 3.26) that these bounds converge to

\gamma_k

for every alphabet size

k

. He published values only for

k=2

. For

k\ge3

the best upper bounds we were able to find in the literature in September 2026 were still those of Dančík's 1994 thesis: subsequent work generalising Lueker has generalised his Section 2, the lower bound. We implement

\mathcal{M}_h

for arbitrary

k

. One ingredient has no binary analogue — the generating function of a truncation class when both sides of a minimal match pair are truncated — and we derive it. We then give a reduction by relative forms under which the transition multiplicities of the transfer matrix are falling factorials in

k

; one alphabet-free construction consequently determines the exact matrix for every

k

. We obtain improved upper bounds for

k=3,\dots,15

, each supported by a Collatz–Wielandt certificate verified in exact rational arithmetic, among them

\gamma_5\le0.645033

. A note added on 31 October 2026 compares these values with those of a repository made public by L. Jack on 25 October 2026.

Provenance statement

The research and the writing were carried out by the author with Claude (Anthropic). The proofs were checked by independent AI reviews and by exact computation. No professional mathematician has reviewed the note yet.

Tools used

Anthropic: Claude Opus

References

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 , Ph.D. dissertation, Department of Computer Science, 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), no. 4, 449--458.
M. Kiwi, M. Loebl and J. Matoušek, Expected length of the longest common subsequence for large alphabets, Adv. Math. 197 (2005), no. 2, 480--498.
M. Kiwi and J. Soto, On a speculated relation between Chvátal--Sankoff constants of several sequences, Combin. Probab. Comput. 18 (2009), no. 4, 517--532.
G. S. Lueker, Improved bounds on the average length of longest common subsequences, J. ACM 56 (2009), no. 3, Article 17, 38 pp.
M. Rosenfeld, Upper bounds on the average edit distance between two random strings, arXiv:2407.18113 (2024).arXiv
L. Jack, Improved upper bounds on the Chvátal--Sankoff constants for alphabets of size 3 to 15, GitHub repository leandrejack-afk/chvatal-sankoff-bound , version ipl-2026 , 25 October 2026.

Version history

v1Submitted by David Niedbala GiraudinInitial depositCurrentOct 31, 2026