Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Integer covariance kernels and spectral decompositions

Definition
PrivateContinualCounting_Kraft_Supplement_Covariance

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

continual-countingdifferential-privacyharmonic-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

A covariance kernel is a function Γ:Z×Z→R\Gamma:\mathbb Z\times\mathbb Z\to\mathbb RΓ:Z×Z→R. Positive semidefiniteness is the nonnegativity of every finite quadratic form. For a finite integer window WWW, a coordinate j∈Wj\in Wj∈W and arbitrary real coefficients bib_ibi​, the coordinate lower bound is

∑i,k∈WbiΓ(i,k)bk≥cbj2.\sum_{i,k\in W}b_i\Gamma(i,k)b_k\ge c b_j^2.i,k∈W∑​bi​Γ(i,k)bk​≥cbj2​.

The stationarised-envelope predicate collects symmetry, finite-window positive semidefiniteness, Γ(i+1,k+1)=Γ(i,k)\Gamma(i+1,k+1)=\Gamma(i,k)Γ(i+1,k+1)=Γ(i,k), the coordinate lower bound and

∑i,k=1wΓ(a+i,a+k)≤B(w)(a∈Z, w≥1).\sum_{i,k=1}^w\Gamma(a+i,a+k)\le B(w)\quad(a\in\mathbb Z,\ w\ge1).i,k=1∑w​Γ(a+i,a+k)≤B(w)(a∈Z, w≥1).

These predicates are used as conclusions of stationarisation and as the inherited input of interpolation, never as assumptions defining an additive process.

A spectral decomposition specifies finite positive measures ν,νs\nu,\nu_sν,νs​ on the circle and a nonnegative measurable integrable density fff such that

ν=f dm+νs,νs⊥m,Γ(i,k)=∫ei(i−k)θ dν(θ).\nu=f\,dm+\nu_s,\quad\nu_s\perp m,\quad\Gamma(i,k)=\int e^{\mathrm i(i-k)\theta}\,d\nu(\theta).ν=fdm+νs​,νs​⊥m,Γ(i,k)=∫ei(i−k)θdν(θ).

Here mmm is the published normalized circle measure on (−π,π](-\pi,\pi](−π,π], and ν\nuν is supported there and invariant under circle reflection (the endpoints are identified). The singular part is retained. Positivity almost everywhere and reciprocal integrability of fff are not part of the definition: Lemma 4.3 must prove them. This separates the covariance and spectral interfaces from privacy and from any special envelope.

Definition code
import Definitions.Def_PrivateContinualCounting_Kraft_Supplement_Privacy
import Definitions.Def_PrivateContinualCounting_Kraft_SpectralConstruction

open MeasureTheory ProbabilityTheory Filter

set_option autoImplicit false

namespace PrivateContinualCounting.Kraft.Supplement

abbrev Kernel := ℤ → ℤ → ℝ

def KernelPSD (Γ : Kernel) : Prop :=
  ∀ (W : Finset ℤ) (b : ℤ → ℝ), 0 ≤ ∑ i ∈ W, ∑ k ∈ W, b i * Γ i k * b k

def KernelLowerBound (Γ : Kernel) (c : ℝ) : Prop :=
  ∀ (W : Finset ℤ) (j : ℤ), j ∈ W → ∀ b : ℤ → ℝ,
    c * (b j)^2 ≤ ∑ i ∈ W, ∑ k ∈ W, b i * Γ i k * b k

def StationaryEnvelope (Γ : Kernel) (c : ℝ) (B : ℕ → ℝ) : Prop :=
  (∀ i k, Γ i k = Γ k i) ∧ KernelPSD Γ ∧
  (∀ i k, Γ (i+1) (k+1) = Γ i k) ∧ KernelLowerBound Γ c ∧
  ∀ (a : ℤ) (w : ℕ), 0 < w →
    (∑ i ∈ Finset.range w, ∑ k ∈ Finset.range w,
      Γ (a+(i:ℤ)+1) (a+(k:ℤ)+1)) ≤ B w

/-- Reflection on (-π,π], with the endpoints identified. -/
noncomputable def circleReflect (θ : ℝ) : ℝ := if θ = Real.pi then Real.pi else -θ

/-- Actual Herglotz representation and Lebesgue decomposition; no reciprocal
integrability or positivity is assumed. f is a nonnegative measurable representative. -/
def SpectralDecomposition (Γ : Kernel) (ν νs : Measure ℝ) (f : ℝ → ℝ) : Prop :=
  IsFiniteMeasure ν ∧ IsFiniteMeasure νs ∧
  ν (Set.Ioc (-Real.pi) Real.pi)ᶜ = 0 ∧
  ν.map circleReflect = ν ∧
  Measurable f ∧ (∀ θ, 0 ≤ f θ) ∧ Integrable f circleMeasure ∧
  ν = circleMeasure.withDensity (fun θ => ENNReal.ofReal (f θ)) + νs ∧
  νs.MutuallySingular circleMeasure ∧
  ∀ i k : ℤ, (Γ i k : ℂ) =
    ∫ θ, Complex.exp (((i-k : ℤ) : ℂ) * (θ : ℂ) * Complex.I) ∂ν

end PrivateContinualCounting.Kraft.Supplement
Source
Kisung Park, STOC 2027 submission #86 (October 2026), p. 9, PDF p. 11, Section 4 and Lemmas 4.2–4.3; p. 21, PDF p. 23, Appendix D

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me