Lemma 36 — small cliques and the recursion
ProvedBuchiRabinIndex.LowerBound.lemma_36automata-theoryfinite-combinatoricsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1rabin-index
For , write for the largest clique of with all weights at most . For ,
For and ,
The maximum ranges over a nonempty finite set, including . Both the small-weight formula and the complete recursion are stated.
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 36; statement only. -/
theorem lemma_36 (n : ℕ) (hn : 1 ≤ n) :
(∀ c, c ≤ n / 2 → g n c = 2 ^ c) ∧
(2 ≤ n → ∀ c, 1 ≤ c → c ≤ n - 1 →
g n c = (((Finset.range c).product (Finset.range c)).filter
(fun ab => ab.1 + ab.2 ≤ n - 2)).sup
(fun ab => g (n - 1) ab.1 + g (n - 1) ab.2)) := 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 36, p. 26; 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.