bandwidthBudget_zero
plain-language theorem explainer
The bandwidth budget over zero recognition cycles equals zero. Researchers deriving substrate-dependent exponential lower bounds for NP witness certification would cite this base case to anchor induction on cycle count. The proof is a one-line wrapper that unfolds the bandwidthBudget definition and reduces the resulting arithmetic identity via ring.
Claim. Let $B(t)$ denote total bandwidth over $t$ cycles, defined by $B(t) = b t$ where $b$ is the constant per-cycle bandwidth. Then $B(0) = 0$.
background
The module derives structural lower bounds on the recognition operator acting on a finite-state substrate whose BIT bandwidth is bounded per cycle. The definition bandwidthBudget(t) computes total available bandwidth as the product of the fixed per-cycle quantity bitBandwidthPerCycle and the cycle count t. This supplies the arithmetic foundation for the zero and successor cases used in the exponential runtime bound $t geq 2^n / B$ for NP-search problems.
proof idea
The proof is a one-line wrapper that unfolds the definition of bandwidthBudget and applies the ring tactic to obtain the identity bitBandwidthPerCycle * 0 = 0.
why it matters
This base case is referenced by pVsNPFromBITCert to assemble the full certificate for the BIT-bandwidth lower bound on NP certification time. It closes the zero case in the inductive argument that any recognition substrate requires exponential time for problems whose search space is $Omega(2^n)$. The result contributes to the phi-rung lower-bound track by showing that bounded per-cycle bandwidth forces exponential separation independent of classical Turing models.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.