Theorem 6.1 — lifted AMS estimator for even density moments
OpenCosDensity.Supplement.theorem_6_1complexity-theorycosine-similarityfrequency-momentsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1streaming-algorithms
There is an absolute constant such that, for every integer , every , and every stream in , a one-pass algorithm returns a -approximation to with probability at least using at most
real words.
Differences from the source:
- generalization: input vectors are nonzero by the paper's standing convention → the lifted AMS statement also covers zero vectors under ; reason: the tensor identity and AMS estimate remain valid and specialize to the source
- encoding: words → one algorithm for all stream lengths, with an absolute , the displayed ceiling, and the shared -word sum; reason: the proof uses one constant-success group plus median amplification, and quantifies the printed bound uniformly for every
Preamble
import Definitions.Def_CosDensity_Stream import Definitions.Def_CosDensity_Supplement_WordStreamAlg
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.1, p.20 (PDF p.21),
with the normalized monomial map and AMS calculation on pp.20–21.
One absolute constant controls the number of independent lifted AMS counters. The state bound
retains the exact lifted dimension `choose (d+k-1) k`, the `epsilon⁻²` averaging factor, the
base-two logarithmic median-amplification factor, and the shared `d`-word vector sum. The factor
`log₂(2/delta) = 1 + log₂(1/delta)` includes the one constant-success group needed before
amplification. -/
theorem theorem_6_1 :
∃ C : ℝ, 0 < C ∧ ∀ k : ℕ, 1 ≤ k →
∀ (epsilon delta : ℝ), 0 < epsilon → epsilon < 1 → 0 < delta → delta < 1 →
∀ d : ℕ,
∃ A : WordStreamAlg (EuclideanSpace ℝ (Fin d)),
A.words ≤ Nat.ceil
(C * (Nat.choose (d + k - 1) k : ℝ) / epsilon ^ 2 * Real.logb 2 (2 / delta) + d) ∧
∀ P : List (EuclideanSpace ℝ (Fin d)),
A.Succeeds (fun omega => ∃ estimate : ℝ,
A.estimate omega P = some estimate ∧
CosDensity.IsApprox epsilon (CosDensity.moment (2 * k) P) estimate)
(ENNReal.ofReal (1 - delta)) := 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.1, pp.20–21 (PDF pp.21–22)