# P2834: Logarithmic DFA separation of binary words

- ID: `P2834`
- Reference: `binary-word-logarithmic-dfa-separation`
- Page: https://theoremdb.org/statements/P2834
- Record maturity: Reviewed problem with recorded work

## Problem

For distinct words \(x,y\in\{0,1\}^n\), let \(s(x,y)\) be the minimum number of states in a deterministic finite automaton that accepts exactly one of \(x,y\), and let \(S(n)=\max_{x\ne y}s(x,y)\). Is \(S(n)=O(\log n)\)?

### Problem setup

- **Remark.** A deterministic finite automaton has a finite state set, one start state, a set of accepting states, and one outgoing transition for each state and input symbol.
- **Remark.** An automaton separates \(x\) and \(y\) when it accepts one word and rejects the other.
- **Definition.** The assertion \(S(n)=O(\log n)\) means that an absolute constant \(C\) exists with \(S(n)\le C\log n\) for every sufficiently large \(n\).

### What counts as a solution

- Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded.

## Status

UNKNOWN as of 2026-07-31. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound. Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded. [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (Current status and unresolved remainder).** UNKNOWN as of 2026-07-31. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound. Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded.

UNKNOWN as of 2026-07-31. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.

A complete resolution must satisfy this condition: Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded.

### Background and intake notes

The problem asks how little finite memory suffices to distinguish two known inputs. Modular position counts and short pattern statistics can be stored as independent separators, while hard pairs record which entire classes of small automata fail.

- Original intake status: UNKNOWN as of 2026-07-27. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.
- 2026-07-27 status search checked the 2011 separating-words survey, the 2020 bound, the March 2025 polylogarithmic improvement, and 2026 work on minimal DFA witnesses. No source checked settles \(S(n)=O(\log n)\).
- The strongest neighboring result is the 2025 \(O(\log^2 n)\) construction, improving an earlier \(O(n^{1/3}\log^7 n)\) bound.
- A reusable positive artifact should specify the distinguishing statistic and compile it into a DFA with an explicit state count. A lower-bound artifact should give hard word pairs and an equivalence relation respected by every smaller DFA.

- Recorded example: For \(x=0\) and \(y=1\), a two-state DFA separates the words. For arbitrary \(x\ne y\) of length \(n\), a DFA recognizing the singleton language \(\{x\}\) gives the elementary bound \(s(x,y)\le n+2\).

### Open directions

- **Route 1** (reported): Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded. [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `binary-word-logarithmic-dfa-separation`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1 entry has incomplete source metadata. Each affected row names the fields that still need editorial review.

1. <a id="reference-1"></a>A Sharper Upper Bound for the Separating Words Problem The preprint proves the current polylogarithmic upper bound; the logarithmic target is the standard remaining separating-words question. This CC0 self-contained record was prepared on 2026-07-27. https://arxiv.org/abs/2503.23184
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - preprint; reference source; checked 2026-07-31
   - Source metadata incomplete: source version.
   - Source use: citation_only
   - Source used to formulate or check the problem record.
   - Source used to assess the problem's recorded status.
   - Source named by the research packet.
2. <a id="reference-2"></a>Zachary Chase, “A new upper bound for separating words”. arXiv:2007.12097 (2020). Full preprint relevant to Logarithmic DFA separation of binary words. https://arxiv.org/abs/2007.12097
   - preprint; reference source; arXiv:2007.12097, checked 2026-07-31; checked 2026-07-31
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - For Logarithmic DFA separation of binary words: UNKNOWN as of 2026-07-27. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.
3. <a id="reference-3"></a>Erik D. Demaine, Sarah Eisenstat, Jeffrey Shallit, and David A. Wilson, “Remarks on separating words”. arXiv:1103.4513 (2011). Full preprint relevant to Logarithmic DFA separation of binary words. https://arxiv.org/abs/1103.4513
   - preprint; reference source; arXiv:1103.4513, checked 2026-07-31; checked 2026-07-31
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - For Logarithmic DFA separation of binary words: UNKNOWN as of 2026-07-27. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.