Fact 13 — node counts by weight
ProvedBuchiRabinIndex.LowerBound.fact_13automata-theoryfinite-combinatoricsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1rabin-index
Let and let be the unique -full ordered tree. Then
For every integer with , exactly nodes have weight .
This counts every possible implicit history-tree node name, and supplies the level counts used in the coexistence graph.
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, fact 13; statement only. -/
theorem fact_13 (n : ℕ) (hn : 1 ≤ n) :
(fullTree n).card = 2 ^ (n - 1) ∧
(fullTree n).filter (weight · = 0) = {[]} ∧
∀ w, 0 < w → w ≤ n - 1 →
((fullTree n).filter (weight · = w)).card = 2 ^ (w - 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), Fact 13, p. 11; 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.