Theorem 19 — Canonical flag correctness: distinctness and exact range
ProvedBuchiRabinIndex.LowerBound.Supplement.theorem_19automata-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , and let cf be the literal recursive function of Definition 17. It satisfies both conclusions:
- If are in , have equal weight and , then .
- At every weight ,
The second conclusion asserts every flag in the stated interval is attained. For no name has weight and , so both sides are empty; the proof on p. 16 treats . These properties establish the canonical identifiers used by the reduced condition.
Differences from the source:
- encoding: positive integer node words, finite chains and the n-full tree → published List Nat names with positivity, Finset chains and explicit fullTree n; reason: the existing published representation preserves each source name, chain and coexistence edge
- encoding: the threshold is ceil((n-1)/2) for positive n → natural division n / 2; reason: these integers agree for every n ≥ 1; all subtractions and exponents are exact on the stated branches
- encoding: the finite chromatic numbers of G_n and its weight subgraphs → Mathlib chromaticNumber converted to Nat; reason: these graphs have finite carriers, so their chromatic numbers are finite; no infinite default is used
Preamble
import Definitions.Def_BuchiRabinIndex_LowerBound_Supplement_Flags set_option autoImplicit false
Formal statement
namespace BuchiRabinIndex.LowerBound.Supplement
/-- STOC 2027 submission #1731, theorem 19. Statement only. -/
theorem theorem_19 (n : ℕ) (hn : 1 ≤ n) :
(∀ x ∈ fullTree n, ∀ y ∈ fullTree n, x ≠ y → weight x = weight y →
(chain x ∪ chain y).card ≤ n → cf n x ≠ cf n y) ∧
(∀ w : ℕ,
((fullTree n).filter fun x => weight x = w).image (cf n) =
Finset.Icc 1 (sf n w)) := by sorry
end BuchiRabinIndex.LowerBound.Supplement
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), https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1731.pdf, Theorem 19, p. 15