Theorem 4.1 — first density moment identity and exact -word algorithm
OpenCosDensity.Supplement.theorem_4_1complexity-theorycosine-similarityfrequency-momentsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1streaming-algorithms
For every finite stream in , write and . Then
Consequently there is a one-pass algorithm that stores the coordinates of and outputs exactly, using at most real words.
Differences from the source:
- generalization: input vectors are nonzero by the paper's standing convention → the identity and algorithm also cover zero vectors using the published convention ; reason: the bilinear identity remains valid and specializes to every source stream
- encoding: words → a state embedding into exactly real words; reason: the proof stores only the -coordinate vector sum
Preamble
import Definitions.Def_CosDensity_Stream import Definitions.Def_CosDensity_Supplement_WordStreamAlg open scoped BigOperators 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 4.1, p.13 (PDF p.14).
The first density moment is the squared norm of the sum of the normalized stream vectors, and a
one-pass algorithm computes it exactly while storing only that `d`-coordinate sum.
**Formalization Note.** The identity and algorithm are stated for all lists, including lists containing
zero vectors; `unitize 0 = 0`, so this is a genuine generalization of the paper's nonzero-input convention.
The algorithm's state embeds into exactly `d` real words. -/
theorem theorem_4_1 :
(∀ (d : ℕ) (P : List (EuclideanSpace ℝ (Fin d))),
CosDensity.moment 1 P =
‖∑ i : Fin P.length, CosDensity.unitize (P.get i)‖ ^ 2) ∧
(∀ d : ℕ, ∃ A : WordStreamAlg (EuclideanSpace ℝ (Fin d)),
A.words ≤ d ∧ ∀ (P : List (EuclideanSpace ℝ (Fin d))) (omega : A.Seed),
A.estimate omega P = some (CosDensity.moment 1 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.1, p.13 (PDF p.14)