Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.1 — Characterization of private uniform language generation

Proved
PrivateUniformGen.Characterization.theorem_1_1

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

differential-privacylanguage-generationp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let XXX be any countable example space and CCC any nonempty, possibly uncountable family of infinite subsets of XXX. Then

C is privately uniformly generatable⟺CDim⁡(C)<∞ and NBDim⁡(C)<∞.C\text{ is privately uniformly generatable}\quad\Longleftrightarrow\quad\operatorname{CDim}(C)<\infty\ \text{and}\ \operatorname{NBDim}(C)<\infty.C is privately uniformly generatable⟺CDim(C)<∞ and NBDim(C)<∞.

Private uniform generatability means there are n0≥1n_0\ge1n0​≥1, algorithms AnA_nAn​ for every n≥n0n\ge n_0n≥n0​, and nonnegative errors δn\delta_nδn​ with nδn→0n\delta_n\to0nδn​→0, such that AnA_nAn​ is (1,δn)(1,\delta_n)(1,δn​)-private on all of XnX^nXn and almost surely returns an infinite subset of LLL excluding the input on every sequence of nnn distinct examples from every L∈CL\in CL∈C. The closure dimension retains its finite value −1-1−1. This is both directions of the paper's main characterization, without restrictions on class cardinality.

Differences from the source:

  • reading: measurable subsets of the output range → the product sigma-algebra on subsets of X; randomized algorithms are arbitrary maps to probability laws; reason: membership events generate this sigma-algebra; X is countable, all stated utility events are measurable, and the upper-bound laws have finite support; no computability requirement is imposed by the source
  • encoding: randomized algorithms and probability-one guarantees → ProbabilityMeasure-valued maps and almost-everywhere predicates; reason: bundles probability one for every input and expresses the identical almost-sure events without allowing zero measures
  • encoding: CDim in {-1,0,1,...,infinity} and nonnegative ranks with infinity → WithTop integers for CDim and extended naturals for ranks and Helly numbers; reason: retains both -1 and infinity; finite-value projections are used only where finiteness is assumed or follows from the source results
  • encoding: unrestricted branching trees with equal root-to-leaf node counts → the inductive existence predicate HasTree with unlimited arity; reason: sets of child labels permit arbitrary branching; equal duplicate labels can be merged without altering tree existence or any intersection
Preamble
import Mathlib
import Definitions.Def_PrivateUniformGen_Characterization_Languages
import Definitions.Def_PrivateUniformGen_Characterization_Branching

open MeasureTheory
Formal statement
namespace PrivateUniformGen.Characterization

theorem theorem_1_1 {X : Type} [Countable X] (C : LanguageClass X) :
  PrivatelyUniformlyGeneratable C ↔ closureDim C < ⊤ ∧ nbDim C ⊤ < ⊤ := by sorry

end PrivateUniformGen.Characterization
Source
Di Wang, Peng Ye, STOC 2027 submission #178 (October 2026), Theorem 1.1, p. 3. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/178.pdf
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

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