Theorem 4.3 — exact integer density moments in one pass
OpenCosDensity.Supplement.theorem_4_3complexity-theorycosine-similarityfrequency-momentsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1streaming-algorithms
For every integer and dimension , there is a one-pass algorithm that computes exactly for every stream . It stores the vector sum and one degree- symmetric-tensor counter for every multi-index of weight , hence uses at most
real words.
Differences from the source:
- generalization: input vectors are nonzero by the paper's standing convention → the exact algorithm also covers zero vectors under ; reason: all monomial identities remain valid and the result specializes to the source
- encoding: words → at most real words; reason: the proof explicitly counts these monomial counters and the shared vector sum
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 4.3, p.14 (PDF p.15).
For every integer `p ≥ 1`, the vector sum and the `choose (d+p-1) p` degree-`p` symmetric
monomial counters give an exact one-pass algorithm. -/
theorem theorem_4_3 :
∀ p : ℕ, 1 ≤ p → ∀ d : ℕ,
∃ A : WordStreamAlg (EuclideanSpace ℝ (Fin d)),
A.words ≤ d + Nat.choose (d + p - 1) p ∧
∀ (P : List (EuclideanSpace ℝ (Fin d))) (omega : A.Seed),
A.estimate omega P = some (CosDensity.moment p P) := by sorry
end CosDensity.Supplement
Source
Q. Zhang, Frequency Moments Beyond Equality: Streaming Cosine Density Moments, arXiv:2609.06925 (held version, sha256 f4d4df22…), Theorem 4.3, p.14 (PDF p.15)