Theorem 6.4 — approximating needs bits
OpenCosDensity.Supplement.theorem_6_4complexity-theorycosine-similarityfrequency-momentsp2o-gran-per-chapterp2o-plan-paperp2o-v1streaming-algorithms
Fix . There are constants , , , and such that, for every , any one-pass algorithm that -approximates with probability at least on every nonempty stream of nonzero vectors with nonnegative pairwise cosine, length at most , and rational coordinates of height at most , satisfies
Differences from the source:
- encoding: bits, length, and -bit coordinates → constants , length , coordinate height , and memory ; reason: this is the quantified content of the theorem's asymptotic clauses
- encoding: the lower bound holds even in the nonnegative-cosine regime → correctness is required only on the stated nonzero, nonnegative-cosine finite-precision class; reason: this expresses the theorem's promise clause in the paper's normalize-on-arrival model
Preamble
import Definitions.Def_CosDensity_Stream import Definitions.Def_CosDensity_StreamAlg open MeasureTheory
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 6.4, p.22 (PDF p.23).
For fixed `epsilon < 1/5`, correctness only on nonzero, nonnegative-cosine streams of linear length,
with polynomially bounded rational coordinate height, forces linear bit memory. -/
theorem theorem_6_4 :
∀ epsilon : ℝ, 0 < epsilon → epsilon < 1 / 5 →
∃ c : ℝ, 0 < c ∧ ∃ 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) → CosDensity.NonnegCosine P →
P.length ≤ C * d → CosDensity.IsBitBounded (d ^ K) P →
CosDensity.SucceedsWP mu (fun omega =>
CosDensity.IsApprox epsilon (CosDensity.moment 2 P) (A.estimate omega P))
(2 / 3 : ENNReal)) →
c * d ≤ 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 6.4, pp.22–23 (PDF pp.23–24)