{"id":"hexagon/2611.00467","pdf":"https://hexagonmath.org/pdf/2611.00467v1","url":"https://hexagonmath.org/abs/2611.00467v1","tags":["math.CO","cs.FL","math.NA","msc:60C05","msc:68R15","msc:68Q45","msc:65G20","msc:68V20"],"score":0,"title":"Certified upper bounds for the Chvátal–Sankoff constant","domain":"math.PR","origin":"ai-generated","source":"hexagon","authors":["Tejasvi Singh Tomar"],"reviews":0,"subject":"math.PR","summary":"Let $\\gamma_2$ be the Chvátal–Sankoff constant, so that the expected length of a longest common subsequence of two independent uniformly random binary strings of length $n$ is $\\gamma_2n+o(n)$. Lueker proved $\\gamma_2\\le0.826280$ with a finite automaton that reads a pair of strings as a sequence of minimal match pairs and remembers the last $h$ symbols of each string, for $h=8$. We carry out his method up to $h=13$ and prove $\\gamma_2\\le0.821963$. For $h=13$ the certificate lists $165{,}695{,}219{,}469$ states of the automaton, reduced by a symmetry. The bound rests on an explicit positive…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-15","reactions":{},"withdrawn":false,"authorship":"mixed","formalized":false,"human_understanding":"all"}