binary_extremizer_has_singleton_sccs
For every natural number n, the binary extremizer NFA binary_extremizer_nfa n has singleton strongly connected components.
Statement
theorem binary_extremizer_has_singleton_sccs (n : ℕ) :
nfa_has_singleton_sccs (binary_extremizer_nfa n)- Source
- arXiv:2610.08525, Stronger bounds on the degree of ambiguity of finite automata
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- binary_extremizer_nfaFor each n, binary_extremizer_nfa n is the NFA over alphabet Fin 2 with states Fin n, unique initial state 0, unique accepting state n -…
- nfa_has_singleton_sccsAn NFA M has singleton strongly connected components if for all states p and q, whenever q is reachable from {p} by some word and p is…
Read back from the Lean
For every natural number $n$, the NFA binary_extremizer_nfa n has singleton strongly connected components: for any two states $p, q : \text{Fin } n$, if $q$ is reachable from $\{p\}$ via some word $w_1$ over $\text{Fin } 2$ and $p$ is reachable from $\{q\}$ via some word $w_2$ over $\text{Fin } 2$, then $p = q$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows that any reachable path in the binary extremizer NFA cannot decrease state indices. First, case analysis on the transition relation shows that every single transition from p to q satisfies p.val ≤ q.val. By induction on word length and transitivity of ≤, this non-decreasing property extends to all paths. Therefore, any two mutually reachable states p and q must satisfy both p.val ≤ q.val and q.val ≤ p.val, forcing p = q by antisymmetry and ensuring that all strongly connected components are singletons.
Any single transition preserves non-decreasing state indices: if q ∈ step p k, then p.val ≤ q.val.
Unfolding the definition of the binary extremizer NFA's transition relation reveals three cases: either p.val < q.val (which implies p.val ≤ q.val by le_of_lt), or p.val = 0 and q.val = 0 (which gives 0 ≤ 0), or q.val = p.val (which holds reflexively).
uses
le_of_ltdsimp [binary_extremizer_nfa] at h rcases h with hlt | ⟨-, hp, hq⟩ | ⟨-, -, hqp⟩ · exact le_of_lt hlt · rw [hp, hq] · rw [hqp]
Evaluating on the empty word preserves state index ordering: if q ∈ evalFrom {p} [], then p.val ≤ q.val.
We proceed by induction on the word w, generalizing over p. In the base case w = [], the set of states reached from {p} is just {p} by NFA.evalFrom_nil and Set.mem_singleton_iff, so q = p and reflexivity gives p.val ≤ q.val.
uses
NFA.evalFrom_nil,Set.mem_singleton_iffinduction' w with a w ih generalizing p · simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at h rw [h]
Evaluating on any non-empty word preserves state index ordering: if q ∈ evalFrom {p} (a :: w), then p.val ≤ q.val.
In the inductive step for a :: w, applying NFA.evalFrom_cons, NFA.stepSet_singleton, and NFA.mem_evalFrom_iff_exists shows that reaching q requires transitioning on symbol a to some intermediate state r, and then reaching q from r via w. By binary_extremizer_has_singleton_sccs_step_le, p.val ≤ r.val, and by the induction hypothesis on w, r.val ≤ q.val. Transitivity of inequality (le_trans) then gives p.val ≤ q.val.
uses
NFA.evalFrom_cons,NFA.stepSet_singleton,NFA.mem_evalFrom_iff_exists,binary_extremizer_has_singleton_sccs_step_le,le_trans· rw [NFA.evalFrom_cons, NFA.stepSet_singleton] at h rw [NFA.mem_evalFrom_iff_exists] at h rcases h with ⟨r, hr, hq⟩ have h1 := binary_extremizer_has_singleton_sccs_step_le hr have h2 := ih hq exact le_trans h1 h2
Mutually reachable states p and q satisfy p.val ≤ q.val and q.val ≤ p.val.
Assume p and q are mutually reachable, witnessed by words w₁ taking p to q and w₂ taking q to p. Applying binary_extremizer_has_singleton_sccs_evalFrom_le to each path yields p.val ≤ q.val and q.val ≤ p.val.
uses
binary_extremizer_has_singleton_sccs_evalFrom_leintro p q ⟨w1, hw1⟩ ⟨w2, hw2⟩ have h1 := binary_extremizer_has_singleton_sccs_evalFrom_le n w1 hw1 have h2 := binary_extremizer_has_singleton_sccs_evalFrom_le n w2 hw2
p = q, proving that every strongly connected component is a singleton.
By extensionality for Fin n (ext), equality of p and q reduces to equality of their numerical values, p.val = q.val. Linear integer arithmetic (omega) deduces p.val = q.val from the mutual inequalities p.val ≤ q.val and q.val ≤ p.val.
ext omega
binary_extremizer_has_singleton_sccs_step_le- Any single transition from state p to state q in the binary extremizer NFA satisfies p.val ≤ q.val.
binary_extremizer_has_singleton_sccs_evalFrom_le- If state q is reachable from state p via an input word w in the binary extremizer NFA, then p.val ≤ q.val.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
le_trans- The inequality relation ≤ is transitive: a ≤ b and b ≤ c imply a ≤ c.
NFA.evalFrom_nil- Evaluating an NFA from a set of states on the empty word yields the starting set itself.
Set.mem_singleton_iff- An element belongs to a singleton set {b} if and only if it equals b.
NFA.evalFrom_cons- Evaluating an NFA on a word a :: x from a set of states S equals evaluating x from the set of states reached from S on symbol a.
NFA.stepSet_singleton- Transitioning a singleton set {s} on an input symbol a yields the step set of s on a.
NFA.mem_evalFrom_iff_exists- A state is reachable from a set S on word x if and only if it is reachable on x from some state in S.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma binary_extremizer_has_singleton_sccs_step_le {n : ℕ} {p q : Fin n} {k : Fin 2} (h : q ∈ (binary_extremizer_nfa n).step p k) : p.val ≤ q.val := by dsimp [binary_extremizer_nfa] at h rcases h with hlt | ⟨-, hp, hq⟩ | ⟨-, -, hqp⟩ · exact le_of_lt hlt · rw [hp, hq] · rw [hqp]lemma binary_extremizer_has_singleton_sccs_evalFrom_le (n : ℕ) (w : List (Fin 2)) {p q : Fin n} (h : q ∈ (binary_extremizer_nfa n).evalFrom {p} w) : p.val ≤ q.val := by induction' w with a w ih generalizing p · simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at h rw [h] · rw [NFA.evalFrom_cons, NFA.stepSet_singleton] at h rw [NFA.mem_evalFrom_iff_exists] at h rcases h with ⟨r, hr, hq⟩ have h1 := binary_extremizer_has_singleton_sccs_step_le hr have h2 := ih hq exact le_trans h1 h2/-- The binary extremizer automaton has singleton strongly connected components. -/theorem binary_extremizer_has_singleton_sccs (n : ℕ) : nfa_has_singleton_sccs (binary_extremizer_nfa n) := by intro p q ⟨w1, hw1⟩ ⟨w2, hw2⟩ have h1 := binary_extremizer_has_singleton_sccs_evalFrom_le n w1 hw1 have h2 := binary_extremizer_has_singleton_sccs_evalFrom_le n w2 hw2 ext omega