Lemma 23 (used in the proof of Theorem 27) — Generalized potential bounds OPI success
OpenRandomStreamCI.CodeIntersection.Supplement.generalized_potential_bounds_successoptimal-polynomial-intersectionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationstreaming
Fix a finite code , a branching program on the complete Boolean oracle stream, , and . Let satisfy and increments in . With ,
Both assertions use the actual uniform oracle/order law and actual posteriors. This is the terminal conversion from the generalized potential to OPI success, supporting Theorem 27.
Differences from the source:
- encoding: coordinates, times and symbols as finite labelled sets → Fin indices numbered from zero and finite alphabet types; reason: bijections of labels preserve every source instance
- encoding: the infinite threshold sum in (79)/(88) and integer binomial arguments → the finite range kappa(k_c) <= j <= min(k_c,tau), with signed integer tau-j and beta zero off its support; reason: all omitted terms vanish for positive eta, including on unreachable events
- encoding: kappa on {0,...,n} with positive integer values → a total natural function positive only on its used domain; (78) is a separate predicate; reason: values outside the finite domain are never read
Preamble
import Definitions.Def_RandomStreamCI_CodeIntersection_Supplement_Potential
Formal statement
namespace RandomStreamCI.CodeIntersection.Supplement
/-- Lemma 23, p. 18: both the zero initial value and the full terminal success bound. -/
theorem generalized_potential_bounds_success {n w : ℕ} {Alphabet : Type*}
[Fintype Alphabet] [DecidableEq Alphabet] (B : BranchingProgram n Alphabet w)
(C : Finset (Word n Alphabet)) (η : ℝ) (κ : ℕ → ℕ) (τ : ℕ)
(hη0 : 0 < η) (hη1 : η < 1/2) (hτ0 : 1 ≤ τ) (hτn : τ ≤ n)
(hκ : AdmissibleThreshold n τ κ) :
vertexPotential B C η κ τ 0 = 0 ∧
tauSuccess B C τ ≤ 2 * η + vertexPotential B C η κ τ (Fintype.card (Address n Alphabet)) := by sorry
end RandomStreamCI.CodeIntersection.Supplement
Source
Bouland–Ding–Jain, Exponential quantum space advantage in random data streams, STOC 2027 submission #71, preprint dated 2026-11-02, release papers-1/71.pdf, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/71.pdf, SHA256 3fe1835efedc1b9f29103379085d28d84ab1057dc30c3e3f05a8dce9f536a797, Lemma 23, p. 18 (printed = PDF; offset 0)