Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Square-root coefficients, ordinary gamma-two and finite inner factors

Definition
PrivateContinualCounting_Kraft_Supplement_Benchmarks

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

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

Define the square-root coefficients, their energy and the prefix matrix by

cj=4−j(2jj),S(n)=∑j<ncj2,S(0)=0,(An)ij=1j≤i.c_j=4^{-j}\binom{2j}{j},\qquad S(n)=\sum_{j<n}c_j^2,\quad S(0)=0,\qquad (A_n)_{ij}=\mathbf1_{j\le i}.cj​=4−j(j2j​),S(n)=j<n∑​cj2​,S(0)=0,(An​)ij​=1j≤i​.

The square-root family has decoder coefficients S(n)cj\sqrt{S(n)}c_jS(n)​cj​ and strategy coefficients cj/S(n)c_j/\sqrt{S(n)}cj​/S(n)​ for positive horizons. For an arbitrary finite real matrix MMM, the ordinary factorization norm is

γ2(M)=inf⁡k,L,R: LR=M(max⁡i∥Li,⋅∥2)(max⁡j∥R⋅,j∥2),\gamma_2(M)=\inf_{k,L,R:\,LR=M}\left(\max_i\|L_{i,\cdot}\|_2\right)\left(\max_j\|R_{\cdot,j}\|_2\right),γ2​(M)=k,L,R:LR=Minf​(imax​∥Li,⋅​∥2​)(jmax​∥R⋅,j​∥2​),

with every finite inner dimension kkk allowed. This is not a Toeplitz-restricted infimum. The factorization set contains MMM times the identity; all costs are nonnegative. Empty row or column maxima are assigned zero. The running maximum is vˉt=max⁡0≤s≤tvs\bar v_t=\max_{0\le s\le t}v_svˉt​=max0≤s≤t​vs​; every counter used here has v0=0v_0=0v0​=0, so it equals the source's positive-time maximum, and vˉ0=0\bar v_0=0vˉ0​=0.

A raw inner family consists only of horizon-dependent decoder and strategy coefficient sequences. Its accuracy predicate asks for exact prefix convolution, strategy columns normalized with first-column squared norm one, and every decoder prefix squared norm at most (S(n)+η)2(S(n)+\eta)^2(S(n)+η)2. A buffered sequence is specified by an actual finite linear state filter: c0=τ+v⊤uc_0=\tau+v^\top uc0​=τ+v⊤u and cj+1=v⊤Aj+1uc_{j+1}=v^\top A^{j+1}ucj+1​=v⊤Aj+1u. The existence of accurate buffered families and of their implementations is a conclusion of the clock theorem, not input data. This distinguishes finite filter state dimension from scalar recurrence order.

Definition code
import Definitions.Def_PrivateContinualCounting_Kraft_Supplement_Privacy

open MeasureTheory ProbabilityTheory Filter

set_option autoImplicit false

namespace PrivateContinualCounting.Kraft.Supplement

noncomputable def sqrtCoeff (j : ℕ) : ℝ := (Nat.choose (2*j) j : ℝ) / (4:ℝ)^j
noncomputable def squareEnergy (n : ℕ) : ℝ := ∑ j ∈ Finset.range n, (sqrtCoeff j)^2

def prefixMatrix (n : ℕ) : Matrix (Fin n) (Fin n) ℝ := fun i j => if j ≤ i then 1 else 0

/-- Ordinary finite-dimensional gamma₂: arbitrary inner dimension and arbitrary factors.
For every matrix the feasible set is nonempty (M times identity); costs are nonnegative.
Finite suprema include 0 to define the empty row/column case. -/
noncomputable def matrixGamma2 {m n : ℕ} (M : Matrix (Fin m) (Fin n) ℝ) : ℝ :=
  sInf {v : ℝ | ∃ k : ℕ, ∃ L : Matrix (Fin m) (Fin k) ℝ,
    ∃ R : Matrix (Fin k) (Fin n) ℝ, L * R = M ∧
      v = (Finset.univ.sup' (by simp) (fun i : Option (Fin m) =>
        match i with | none => 0 | some i => Real.sqrt (∑ j, (L i j)^2))) *
        (Finset.univ.sup' (by simp) (fun j : Option (Fin n) =>
        match j with | none => 0 | some j => Real.sqrt (∑ i, (R i j)^2)))}

noncomputable def runningMax (v : ℕ → ℝ) (t : ℕ) : ℝ :=
  (Finset.range (t+1)).sup' (by simp) v

/-- Raw horizon-dependent Toeplitz coefficient pairs, with no product or norm data. -/
structure InnerFamily where
  decoder : ℕ → ℕ → ℝ
  strategy : ℕ → ℕ → ℝ

noncomputable def squareRootFamily : InnerFamily where
  decoder n j := Real.sqrt (squareEnergy n) * sqrtCoeff j
  strategy n j := sqrtCoeff j / Real.sqrt (squareEnergy n)

/-- The normalized finite factors required in Appendix E.3. These are obligations
for an existential family, not hypotheses of the clock theorem. -/
def InnerAccuracy (F : InnerFamily) (η : ℝ) : Prop :=
  ∀ n : ℕ, 0 < n →
    (∀ s : ℕ, s < n →
      (∑ j ∈ Finset.range (s+1), F.decoder n j * F.strategy n (s-j)) = 1) ∧
    (∑ j ∈ Finset.range n, (F.strategy n j)^2) = 1 ∧
    (∀ s : ℕ, s ≤ n → (∑ j ∈ Finset.range s, (F.strategy n j)^2) ≤ 1) ∧
    (∀ s : ℕ, s ≤ n →
      (∑ j ∈ Finset.range s, (F.decoder n j)^2) ≤ (squareEnergy n + η)^2)

/-- A finite linear filter with feedthrough; both Toeplitz symbols admit this form.
The state dimension is not misidentified with the order of its scalar recurrence. -/
def IsBuffered (c : ℕ → ℝ) : Prop :=
  ∃ d : ℕ, ∃ A : Matrix (Fin d) (Fin d) ℝ, ∃ u v : Fin d → ℝ, ∃ τ : ℝ,
    c 0 = τ + (v ⬝ᵥ u) ∧
    ∀ j : ℕ, c (j+1) = dotProduct v (Matrix.mulVec (A^(j+1)) u)

def BufferedFamily (F : InnerFamily) : Prop :=
  ∀ n : ℕ, 0 < n → IsBuffered (F.decoder n) ∧ IsBuffered (F.strategy n)

end PrivateContinualCounting.Kraft.Supplement
Source
Kisung Park, STOC 2027 submission #86 (October 2026), p. 7, PDF p. 9, Section 2.4; pp. 23–24, PDF pp. 25–26, Appendix E.3

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