Pairwise code agreement and high-value events
DefinitionRandomStreamCI_CodeIntersection_Supplement_Agreementoptimal-polynomial-intersectionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationstreaming
For a finite code , pairwise agreement at most means that distinct codewords coincide on at most coordinate indices. For and a normalized Boolean law on , put and define
The corresponding probability sums the full PMF over this event. The surplus is real, and the event uses exactly the coordinates in . No independence or density-restoring condition on is part of the definition. These notions apply to arbitrary finite codes, independently of polynomial structure.
Definition code
import Definitions.Def_RandomStreamCI_CodeIntersection_Stream
noncomputable section
namespace RandomStreamCI.CodeIntersection.Supplement
open scoped BigOperators
attribute [local instance] Classical.propDecidable
/-- Lemmas 25 and 26: pairwise coordinate agreement, for arbitrary finite codes. -/
def PairwiseAgreement {n : ℕ} {Alphabet : Type*} [DecidableEq Alphabet]
(C : Finset (Word n Alphabet)) (d : ℕ) : Prop :=
∀ c ∈ C, ∀ c' ∈ C, c ≠ c' →
(Finset.univ.filter (fun i => c i = c' i)).card ≤ d - 1
/-- Lemma 25's observed Hamming weight on exactly T_c intersect A, under any Boolean law on A. -/
def HighValue {n : ℕ} {Alphabet : Type*} [DecidableEq Alphabet]
(A : Finset (Address n Alphabet)) (c : Word n Alphabet) (s : ℝ) (x : A → Bool) : Prop :=
(observedCount c A : ℝ) / 2 + s ≤
((Finset.univ.filter (fun u : A => (u : Address n Alphabet) ∈ wordAddresses c ∧ x u = true)).card : ℝ)
/-- Event probability under the whole normalized law, without any partition or density hypothesis. -/
def highValueProbability {n : ℕ} {Alphabet : Type*} [DecidableEq Alphabet]
(A : Finset (Address n Alphabet)) (X : PMF (A → Bool)) (c : Word n Alphabet) (s : ℝ) : ℝ :=
eventMass (weights X) (HighValue A c s)
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 25, pp. 19--20; Lemma 26, p. 20