Lemma 16 — decomposition
ProvedBuchiRabinIndex.LowerBound.lemma_16automata-theoryfinite-combinatoricsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1rabin-index
For , let and let be obtained by incrementing the first entry of each nonroot word of . Then
The maps and are bijections onto and , respectively. For each node in either part,
Both bijections and both weight identities are included. This decomposition relates successive coexistence graphs.
Differences from the source:
- encoding: nodes are finite words of positive integers → List Nat with positivity in node and tree predicates; reason: children retain the source’s indices starting at 1
- encoding: the unique n-full ordered tree of Definition 12 → the explicitly enumerated positive words of weight at most n−1; reason: this is the same finite tree; no size is fixed
Preamble
import Definitions.Def_BuchiRabinIndex_LowerBound_Nodes set_option autoImplicit false
Formal statement
namespace BuchiRabinIndex.LowerBound
/-- STOC 2027 submission #1731, lemma 16; statement only. -/
theorem lemma_16 (n : ℕ) (hn : 2 ≤ n) :
fullTree n = {[]} ∪ part1 n ∪ part2 n ∧
Set.BijOn phi1 {x | x ∈ part1 n} {x | x ∈ fullTree (n - 1)} ∧
Set.BijOn phi2 {x | x ∈ part2 n} {x | x ∈ (fullTree (n - 1)).erase []} ∧
(∀ x ∈ part1 n, weight x = weight (phi1 x) + 1) ∧
(∀ x ∈ part2 n, weight x = weight (phi2 x) + 1) := by sorry
end BuchiRabinIndex.LowerBound
Source
Cong Tian, Runzhe Ma, Wensheng Wang, Zhenhua Duan, Büchi Determinization with Optimal States and Square Root Index Improvement, STOC 2027 submission #1731 (October 2026), Lemma 16, p. 14; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1731.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.