Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.2 — actual hypertree factorization and unit GDP

Open
PrivateContinualCounting.Kraft.Supplement.hypertree_privacy

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

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

Fix a>0a>0a>0 and 0<ξ<10<\xi<10<ξ<1, and form the A/B/C factors and releases of Section 5 using the square-root inner family. There exists an actual Gaussian factorization counter on their one countable product seed whose decoder, strategy and noise process are precisely those formulas, and

LR=A,Δ2=1,(Y1,…,Yn) is 1-GDP for every n≥1.LR=A,\qquad\Delta^2=1,\qquad (Y_1,\ldots,Y_n)\text{ is }1\text{-GDP for every }n\ge1.LR=A,Δ2=1,(Y1​,…,Yn​) is 1-GDP for every n≥1.

The counter's transcript law is identified with the directly defined Section 5 release law for every stream and horizon. Exact factorization and row/column summability are part of constructing the published Gaussian-counter object; sensitivity equality and testing privacy are additional conclusions. No privacy or desired covariance is assumed in the raw hypertree data. This establishes privacy for the single infinite causal mechanism.

Differences from the source:

  • encoding: positive source time and stream indices → natural times with source input i+1 at coordinate i and zero-time noise zero; reason: the published base conventions are reused and every positive time and interval is retained
  • encoding: factor sensitivity Delta=1 → squared sensitivity deltaSq=1; reason: factor sensitivity is nonnegative, so these equalities are equivalent
  • encoding: the constructed infinite Gaussian factorization counter → existence of a counter with exactly the computed matrices and finite-row Gaussian sums, plus equality of transcript laws; reason: no product, sensitivity or privacy property is assumed of the raw construction
Preamble
import Definitions.Def_PrivateContinualCounting_Kraft_Supplement_Hypertree

open MeasureTheory ProbabilityTheory Filter

set_option autoImplicit false
Formal statement
namespace PrivateContinualCounting.Kraft.Supplement

/-- Lemma 5.2: exact factorization, exact sensitivity and actual transcript GDP. -/
theorem hypertree_privacy (a ξ : ℝ) (ha : 0 < a) (hξ0 : 0 < ξ) (hξ1 : ξ < 1) :
    ∃ M : GaussianCounter TreeIndex,
      IsTree M squareRootFamily a ξ ∧ M.factors.deltaSq = 1 ∧
      TranscriptGDP (treeLaw squareRootFamily a ξ) 1 ∧
      (∀ x : Stream, ∀ n : ℕ,
        M.transcriptLaw ⟨1, by norm_num⟩ x n = treeLaw squareRootFamily a ξ x n) := by sorry

end PrivateContinualCounting.Kraft.Supplement
Source
Kisung Park, STOC 2027 submission #86 (October 2026), p. 11, PDF p. 13, Lemma 5.2

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