Theorem 4.1 — exact affine criterion
ProvedCallCountPOPBR.Supplement.theorem_4_1p2o-gran-per-chapterp2o-plan-paperp2o-v1recursive-algorithmstheoretical-computer-science
Let a terminating recursive procedure on inputs have ordered child list , returned value , and total invocation count . Fix with . Then
if and only if both of the following hold:
- at every base case, ;
- at every non-base case,
This criterion exactly characterises when returned values and invocation counts are affinely related.
Differences from the source:
- reading: the source calls a numerical value without naming its scalar domain → are real-valued; reason: the real numbers support every affine operation used in the theorem and the divisions used immediately afterward in Corollary 4.2
- encoding: terminating recursive calls and the invocation count satisfying (5) → a well-founded child relation and its well-foundedly defined count; reason: this is the direct Lean representation of the source's terminating call tree
Preamble
import Mathlib import Definitions.Def_CallCountPOPBR_Supplement_RecProc set_option autoImplicit false
Formal statement
namespace CallCountPOPBR.Supplement
universe u
/-- **Theorem 4.1 (Exact affine criterion).** Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and
Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), Theorem 4.1, p.8: "Fix constants a ≠ 0 and b.
The identity C(x) = aV(x) + b holds for every input if and only if both conditions hold: (i) for
every base-case input x, aV(x) + b = 1; (ii) for every non-base-case input x,
a(V(x) − ∑_{i=1}^{r(x)} V(x_i)) = 1 + (r(x) − 1)b. (6)"
`P` is a terminating recursive procedure with child lists `P.ch x` (`r(x)` = its length), `V` the
returned values and `P.count` the invocation count of Eq. (5).
**Formalization Note.** `r(x) − 1` is computed in `ℝ`. The hypothesis `a ≠ 0` is kept as printed. -/
theorem theorem_4_1 {X : Type u} (P : RecProc X) (V : X → ℝ) (a b : ℝ) (ha : a ≠ 0) :
(∀ x, (P.count x : ℝ) = a * V x + b) ↔
((∀ x, P.ch x = [] → a * V x + b = 1) ∧
(∀ x, P.ch x ≠ [] →
a * (V x - ((P.ch x).map V).sum) = 1 + (((P.ch x).length : ℝ) - 1) * b)) := 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 4.1, Eq. (6), p.8