{"id":"arxiv/2609.08191","url":"https://arxiv.org/abs/2609.08191","tags":["cs.FL","cs.CC","math.CO"],"score":0,"title":"An Elementary Proof of the $\\widetilde O(n^{1/3})$ Bound for Separating Words","domain":"cs.FL","source":"arxiv","authors":["Chen Xu"],"reviews":0,"subject":"cs.FL","summary":"For two distinct binary words of length $n$, the separating words problem asks for a small deterministic finite automaton that accepts exactly one of them. Chase proved a $\\widetilde O(n^{1/3})$ upper bound using a complex-analytic estimate for sparse polynomials. We replace that estimate by a finite-difference argument and a second-order real recurrence cutoff. The resulting elementary proof gives an explicit bound of $O(n^{1/3}(\\log n)^{7/3})$ states.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}