HEXAGONbeta

Upper bounds for the Chvátal–Sankoff constants γk\gamma_k, k≥3k\ge3

Primarily AI-generated textHuman understanding: no partsmath.PR — Probabilitymath.CO — Combinatoricscs.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 Mh\mathcal{M}_h whose associated transfer matrices yield upper bounds on the Chvátal–Sankoff constants γk\gamma_k, and proved (his Theorem 3.26) that these bounds converge to γk\gamma_k for every alphabet size kk. He published values only for k=2k=2. For k≥3k\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 Mh\mathcal{M}_h for arbitrary kk. 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 kk; one alphabet-free construction consequently determines the exact matrix for every kk. We obtain improved upper bounds for k=3,…,15k=3,\dots,15, each supported by a Collatz–Wielandt certificate verified in exact rational arithmetic, among them γ5≤0.645033\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

  1. V. Chvátal and D. Sankoff, Longest common subsequences of two random sequences, J. Appl. Probab. 12 (1975), 306--315.
  2. V. Dančík, Expected length of longest common subsequences , Ph.D. dissertation, Department of Computer Science, University of Warwick, 1994.
  3. 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.
  4. 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.
  5. 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.
  6. G. S. Lueker, Improved bounds on the average length of longest common subsequences, J. ACM 56 (2009), no. 3, Article 17, 38 pp.
  7. M. Rosenfeld, Upper bounds on the average edit distance between two random strings, arXiv:2407.18113 (2024).arXiv
  8. 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

  1. v1 · 7 pagesSubmitted by David Niedbala GiraudinInitial depositCurrentOct 31, 2026