Theorem 4.2 — exact computation needs bits
OpenCosDensity.Supplement.theorem_4_2complexity-theorycosine-similarityfrequency-momentsp2o-gran-per-chapterp2o-plan-paperp2o-v1streaming-algorithms
There are absolute constants and such that, for every , any randomized one-pass finite-state algorithm that computes exactly with probability at least on every stream of at most standard basis vectors in satisfies
where is its memory-state set.
Thus the linear lower bound already holds on -length nonnegative-cosine streams.
Differences from the source:
- encoding: bits on -length standard-basis streams → constants and the explicit promise , with memory ; reason: this is the quantified meaning supplied by the INDEX reduction with
- encoding: success probability at least → an inner-probability event of measure at least in the persistent-seed model; reason: measurable inner witnesses retain the paper's guarantee and support the one-way reduction
Preamble
import Definitions.Def_CosDensity_Stream import Definitions.Def_CosDensity_StreamAlg open MeasureTheory open scoped 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.2, p.14 (PDF p.15).
There is an absolute linear bit lower bound for exact one-pass computation of `M₁`, already on
streams of at most `d+1` standard basis vectors. -/
theorem theorem_4_2 :
∃ c : ℝ, 0 < c ∧ ∃ 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.length ≤ d + 1 →
(∀ x ∈ P, ∃ j : Fin d, x j = 1 ∧ ∀ k : Fin d, k ≠ j → x k = 0) →
CosDensity.SucceedsWP mu
(fun omega => A.estimate omega P = CosDensity.moment 1 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 4.2, p.14 (PDF p.15)