HEXAGONbeta

A superlogarithmic lower bound for deterministic word separation

Primarily AI-generated textHuman understanding: all partscs.FL — Formal Languages and Automata Theory

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer ↗, Liam Kruer

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

Let S(n)S(n) be the maximum, over distinct binary words of length nn, of the least number of states in a complete deterministic finite automaton that accepts exactly one of them. We prove S(n)≥(1−o(1))log⁡nlog⁡log⁡nS(n)\geq(1-o(1))\log n\log\log n. The main step is a common word of length exp⁡(O(klog⁡k))\exp(O(\sqrt{k}\log k)) that, after suitable powering of the generators, reaches the sink components of every transformation pair on kk states and attains minimum rank on each sink. This transfers the balanced positive permutation identities of Xu and Regan to the full transformation monoid without changing their leading logarithmic length. The conclusion concerns deterministic automata; it makes no assertion about nondeterministic separators.

Provenance statement

The mathematical draft and exposition were produced primarily with OpenAI Codex under the direction of the listed contributors. Lean was used to check supporting finite transformation, stationary-probability, and common-word lemmas.

Tools used

OpenAI
Codex
Lean
Lean

References

  1. A. A. Bulatov, O. Karpova, A. M. Shur, and K. Startsev, Lower bounds on words separation: Are there short identities in transformation semigroups? , Electronic Journal of Combinatorics 24 (2017), no. 3, Paper P3.35. doi:10.37236/6450 (https://doi.org/10.37236/6450).DOI
  2. C. Xu and K. Regan, An improved lower bound for separating words by permutation automata , arXiv:2610.11098v1 (2026), Theorem A.1. https://arxiv.org/abs/2610.11098.arXiv

Version history

  1. v1 · 7 pagesSubmitted by Jensen KohlmeyerInitial depositCurrentNov 11, 2026