Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 29 min ago
PreprintarXiv licencearXiv

An Elementary Proof of the Õ(n1/3) Bound for Separating Words

  • Chen Xu
Open at sourcePDFDOICite

Abstract

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 Õ(n1/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(n1/3(log n)7/3) states.

Related

  1. An elementary proof of a tight Δ+1 bound for the additive chromatic number
    Alex Koutsoutis, Joseph Koutsoutis
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. The Tight Upper Bound on the Number of Distinct Squares in Circular Words
    Rikuya Hamai
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. An elementary proof of the Artin--Springer theorem for generalized quadratic forms over quaternion algebras
    Amir Hossein Nokhodkar
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. An elementary proof of the 2-regularity of Pythagorean triples
    William J. Wesley
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. An elementary proof of Brémont's theorem on the convergence of equilibrium measures at temperature zero
    Oliver Jenkinson, Mark Pollicott
    arXivPreprintCC BY 4.0Full textDynamical systemsMathematical physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{xu2026elementary,
  title = {{An Elementary Proof of the $\widetilde O(n^1/3)$ Bound for Separating Words}},
  author = {Chen Xu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08191},
  eprint = {2609.08191},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08191},
}
RIS
TY  - UNPB
TI  - An Elementary Proof of the Õ(n^1/3) Bound for Separating Words
AU  - Chen Xu
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08191
UR  - https://arxiv.org/abs/2609.08191
AB  - 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 Õ(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.
ER  -