Theorem 6.6 — higher even moments need bits
OpenCosDensity.Supplement.theorem_6_6complexity-theorycosine-similarityfrequency-momentsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1streaming-algorithms
Fix an even integer and . There exist , a length constant , a precision exponent , and such that, for every , any one-pass algorithm that -approximates with probability at least on every nonempty stream of nonzero vectors of length at most and rational coordinate height at most satisfies
No cosine-sign promise is imposed.
Differences from the source:
- encoding: bits → constants chosen after and before , with the displayed base-two logarithm and memory ; reason: this is the quantified meaning of the printed lower bound
- generalization: stream length and -bit rationals → length and coordinate height for constants fixed before ; reason: the proof gives , so the Lean promise is stronger and every source algorithm specializes to it
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.6, p.23 (PDF p.24),
with the quantitative reduction on pp.23–25.
For fixed even `p ≥ 4` and fixed `epsilon`, the constants in the `Omega`, stream-length, and
coordinate-precision bounds precede the dimension and algorithm. The promise has no cosine-sign
restriction. -/
theorem theorem_6_6 :
∀ p : ℕ, 4 ≤ p → Even p → ∀ epsilon : ℝ, 0 < epsilon → epsilon < 1 →
∃ 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) →
P.length ≤ C * d ^ (p / 2) → CosDensity.IsBitBounded (d ^ K) P →
CosDensity.SucceedsWP mu (fun omega =>
CosDensity.IsApprox epsilon (CosDensity.moment p P) (A.estimate omega P))
(2 / 3 : ENNReal)) →
c * ((d : ℝ) ^ (p / 2) / (Real.logb 2 d) ^ (p / 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 6.6, pp.23–25 (PDF pp.24–26)