Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial coefficient outputs and OPI success

Definition
RandomStreamCI_CodeIntersection_Supplement_OPI

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

optimal-polynomial-intersectionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationstreaming

Let FFF be a finite field, nnn the number of coordinates, and ddd the dimension. A coefficient tuple x∈Fdx\in F^dx∈Fd denotes fx(X)=∑j=0d−1xjXjf_x(X)=\sum_{j=0}^{d-1}x_jX^jfx​(X)=∑j=0d−1​xj​Xj, using the published coefficient polynomial. Evaluation at the points αi\alpha_iαi​ gives the codeword (fx(αi))i(f_x(\alpha_i))_i(fx​(αi​))i​. The Reed–Solomon code is the published generalized Reed–Solomon evaluation image with all multipliers equal to one, rendered as a finite set.

For any finite code C⊆ΣnC\subseteq\Sigma^nC⊆Σn, a word output succeeds at threshold τ\tauτ precisely when it is in CCC and at least τ\tauτ of its oracle membership bits are one. An absent output fails. Success is averaged over independent uniform Boolean oracle and complete uniform address order; independent private coins are represented by a PMF mixture of executions. The common target is

τ(n,d)=⌈n2+dn8⌉.\tau(n,d)=\left\lceil\frac n2+\frac{\sqrt{dn}}8\right\rceil.τ(n,d)=⌈2n​+8dn​​⌉.

These definitions share the base execution and score without changing CI success. The zero coefficient tuple is included. All sums and divisions inside the ceiling are real.

Definition code
import Definitions.Def_RandomStreamCI_CodeIntersection_Branching
import Definitions.Def_QAlgorithms_Defs_ReedSolomonData

noncomputable section

namespace RandomStreamCI.CodeIntersection.Supplement

open scoped BigOperators
attribute [local instance] Classical.propDecidable

/-- Problem 2, p. 6: all polynomials of degree strictly below d, in coefficient coordinates.
The zero polynomial and polynomials of smaller degree are included. -/
abbrev Coefficients (F : Type*) (d : ℕ) := Fin d → F

/-- Evaluation of the public coefficient polynomial, (8), p. 7. -/
def evaluation {F : Type*} [Field F] {n d : ℕ} (α : Fin n → F)
    (x : Coefficients F d) : Word n F :=
  fun i => (QAlgorithms.OPI.coefficientPolynomial x).eval (α i)

/-- The source RS code, using the published general GRS evaluation image with multipliers 1.
No root-count, cardinality or decoding claim is assumed. -/
def rsCode {F : Type*} [Field F] [Fintype F] {n : ℕ}
    (α : Fin n ↪ F) (d : ℕ) (hd : d ≤ n) : Finset (Word n F) :=
  Finset.univ.filter (fun c => c ∈ QAlgorithms.ReedSolomon.grsCode α (fun _ => 1) d
    α.injective (fun _ => one_ne_zero) hd)

/-- General codeword interpretation of OPI, (6)--(8), including invalid outputs and aborts. -/
def TauValid {n : ℕ} {Alphabet : Type*} [Fintype Alphabet] [DecidableEq Alphabet]
    (C : Finset (Word n Alphabet)) (τ : ℕ) (H : Oracle n Alphabet) : Option (Word n Alphabet) → Prop
  | none => False
  | some c => c ∈ C ∧ τ ≤ value H c Finset.univ

/-- Actual success over independent uniform oracle and complete random ordering. -/
def tauSuccess {n w : ℕ} {Alphabet : Type*} [Fintype Alphabet] [DecidableEq Alphabet]
    (B : BranchingProgram n Alphabet w) (C : Finset (Word n Alphabet)) (τ : ℕ) : ℝ :=
  streamProbability (fun ω => TauValid C τ ω.1
    (B.output (B.state ω (Fintype.card (Address n Alphabet)))))

/-- Independent private random coins: a finite mixture of actual deterministic executions. -/
def randomizedTauSuccess {n w : ℕ} {Alphabet Ω : Type*} [Fintype Alphabet] [DecidableEq Alphabet]
    [Fintype Ω] (p : PMF Ω) (B : Ω → BranchingProgram n Alphabet w)
    (C : Finset (Word n Alphabet)) (τ : ℕ) : ℝ :=
  ∑ ω, weights p ω * tauSuccess (B ω) C τ

/-- The exact target in Theorems 27 and 29: real division, radical, then natural ceiling. -/
def target (n d : ℕ) : ℕ := ⌈(n : ℝ) / 2 + Real.sqrt ((d : ℝ) * n) / 8⌉₊

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, Problem 2, p. 6; (8), p. 7; (11), p. 8; Theorems 27/29, pp. 22/28

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me