Theorem 5.3 — bounded-branching realisability
ProvedCallCountPOPBR.Supplement.theorem_5_3additive-combinatoricsp2o-gran-per-chapterp2o-plan-paperp2o-v1recursive-algorithms
Fix . An integer sequence is realised by an abstract decreasing-argument recursive specification making at most immediate calls per invocation if and only if and, for every ,
where consists of sums of elements of with repetitions allowed and .
Moreover, a computable specification with the same branching bound exists if and only if there is a computable choice, for every , of a list of at most indices below whose corresponding -values sum to .
Differences from the source:
- reading: an effective realisation requires a computable choice of representations in (9) → existence of a computable realising call-list function is equivalent to existence of a computable representation-list function; reason: this makes the paper's final sentence an explicit two-way mathematical assertion
- encoding: is defined by choosing elements of with repetition → a length- list of indices below whose -values are summed; reason: the two descriptions define the same multiset sums
Preamble
import Mathlib import Definitions.Def_CallCountPOPBR_Supplement_DecSpec import Definitions.Def_CallCountPOPBR_Supplement_sumset set_option autoImplicit false
Formal statement
namespace CallCountPOPBR.Supplement
/-- **Theorem 5.3 (Bounded-branching realisability).** Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and
Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), Theorem 5.3, p.9: "Fix b ≥ 0. A
sequence (c_n)_{n≥0} is realisable by an abstract decreasing-argument recursive specification
making at most b calls at each invocation if and only if c_0 = 1 and, for every n ≥ 1,
c_n − 1 ∈ ⋃_{j=0}^{b} jS_n. (9) For an effective realisation, a computable choice of
representations in (9) is additionally required."
1. Some specification with at most `b` calls per invocation realises `c` iff `c_0 = 1` and
`c_n − 1 ∈ ⋃_{j ≤ b} jS_n` for every `n ≥ 1`.
2. Some *computable* specification with at most `b` calls per invocation realises `c` iff
`c_0 = 1` and there is a computable map `n ↦ r(n)` choosing, for every `n ≥ 1`, a representation
in (9): a list of at most `b` indices `k < n` with `∑_{k ∈ r(n)} c_k = c_n − 1`.
**Formalization Note.** Part 2 is the reading of the last sentence: an effective realisation is a
realising specification whose call map `n ↦ calls n : List ℕ` is `Computable` (Mathlib). -/
theorem theorem_5_3 (b : ℕ) (c : ℕ → ℤ) :
((∃ s : DecSpec, (∀ n, (s.calls n).length ≤ b) ∧ ∀ n, c n = (s.count n : ℤ)) ↔
(c 0 = 1 ∧ ∀ n, 1 ≤ n → c n - 1 ∈ ⋃ (j : ℕ) (_ : j ≤ b), sumset c n j)) ∧
((∃ s : DecSpec, Computable s.calls ∧ (∀ n, (s.calls n).length ≤ b) ∧
∀ n, c n = (s.count n : ℤ)) ↔
(c 0 = 1 ∧ ∃ r : ℕ → List ℕ, Computable r ∧ ∀ n, 1 ≤ n →
(r n).length ≤ b ∧ (∀ k ∈ r n, k < n) ∧ c n - 1 = ((r n).map c).sum)) := 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 5.3, Eq. (9), p.9