Theorem 7.8 — maximum-growth uniqueness
ProvedCallCountPOPBR.Supplement.theorem_7_8p2o-gran-per-chapterp2o-plan-paperp2o-v1recursive-algorithmstheoretical-computer-science
For every full-binary decreasing specification with base set , the following are equivalent:
- its invocation count is
- for every , both immediate recursive arguments are .
Thus the maximal-growth sequence exactly characterises the specification that doubles the preceding subtree at every input.
Differences from the source:
- encoding: an unordered child pair with repetition → an element of equal to ; reason: this is the direct finite-index representation of both recursive arguments
- encoding: → natural-number exponentiation and subtraction; reason: the subtraction is exact because
Preamble
import Mathlib import Definitions.Def_CallCountPOPBR_Supplement_BinSpec set_option autoImplicit false
Formal statement
namespace CallCountPOPBR.Supplement
/-- **Theorem 7.8 (Maximum-growth uniqueness).** Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and
Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), Theorem 7.8, p.13: "In the full-binary model
with base set {0} (that is, β = 1), the following statements are equivalent: (i) c_n = 2^{n+1} − 1
for every n ≥ 0; (ii) at every input n ≥ 1, both immediate recursive arguments are n − 1."
For every full-binary specification `σ` with base set `{0}`: its call counts are `2^{n+1} − 1` for
all `n` iff its child pair at every `n ≥ 1` is `{n − 1, n − 1}`.
**Formalization Note.** `2^{n+1} − 1` is natural-number subtraction, exact since `2^{n+1} ≥ 1`. -/
theorem theorem_7_8 (σ : BinSpec 1) :
(∀ n, σ.count n = 2 ^ (n + 1) - 1) ↔
∀ n (h : 1 ≤ n), σ n h = s((⟨n - 1, by omega⟩ : Fin n), (⟨n - 1, by omega⟩ : Fin n)) := by sorry
end CallCountPOPBR.Supplement
Source
Swain, Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction, STOC 2027 submission (manuscript sha256 79135884…), Theorem 7.8, pp.13–14