Theorem 5.5 — diversity-index approximation needs bits
OpenCosDensity.Supplement.theorem_5_5complexity-theorycosine-similarityfrequency-momentsp2o-gran-per-chapterp2o-plan-paperp2o-v1streaming-algorithms
Fix . There exist constants , , and such that, for every , any one-pass algorithm that returns a -approximation to with probability at least on every nonempty stream with strictly positive pairwise cosine, length at most , and rational coordinates of height at most , satisfies
Differences from the source:
- encoding: , polynomial stream length, and -bit rational coordinates → constants , length , coordinate numerator and denominator , and memory ; reason: this is the standard quantified reading of the theorem's asymptotic clauses
- encoding: success probability at least → inner probability at least for a persistent public seed; reason: this is the base mission's nonmeasurability-safe success convention
Preamble
import Definitions.Def_CosDensity_Stream import Definitions.Def_CosDensity_StreamAlg import Definitions.Def_CosDensity_Supplement_diversityIndex open MeasureTheory open scoped RealInnerProductSpace
Formal statement
namespace CosDensity.Supplement
set_option autoImplicit false
/-- Q. Zhang, *Frequency Moments Beyond Equality: Streaming Cosine Density Moments*,
arXiv:2609.06925 (held version, sha256 f4d4df22…), Theorem 5.5, p.19 (PDF p.20).
For every fixed `epsilon` in `(0,1/5)`, correctness only on polynomial-length finite-precision
streams with strictly positive pairwise cosine already forces a quadratic number of bits. The
constants `c`, `K`, and `d₀` are chosen before the dimension and the algorithm. -/
theorem theorem_5_5 :
∀ epsilon : ℝ, 0 < epsilon → epsilon < 1 / 5 →
∃ c : ℝ, 0 < c ∧ ∃ K d₀ : ℕ, ∀ d ≥ d₀,
∀ (S Omega : Type) [Fintype S] [Nonempty S] [MeasurableSpace Omega]
(mu : Measure Omega) [IsProbabilityMeasure mu]
(A : CosDensity.StreamAlg (EuclideanSpace ℝ (Fin d)) Omega S),
(∀ P : List (EuclideanSpace ℝ (Fin d)),
P ≠ [] → (∀ x ∈ P, x ≠ 0) →
(∀ x ∈ P, ∀ y ∈ P, 0 < ⟪CosDensity.unitize x, CosDensity.unitize y⟫) →
P.length ≤ d ^ K → CosDensity.IsBitBounded (d ^ K) P →
CosDensity.SucceedsWP mu (fun omega =>
CosDensity.IsApprox epsilon (diversityIndex P) (A.estimate omega P))
(2 / 3 : ENNReal)) →
c * (d : ℝ) ^ 2 ≤ CosDensity.memoryBits S := by sorry
end CosDensity.Supplement
Source
Q. Zhang, Frequency Moments Beyond Equality: Streaming Cosine Density Moments, arXiv:2609.06925 (held version, sha256 f4d4df22…), Theorem 5.5, p.19 (PDF p.20)