Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Observation 2.4 — a counting query has global sensitivity at most 1/n

Proved
PrivateRelease.NetMechanism.observation_2_4

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

counting-queriesdifferential-privacyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sensitivity

Let XXX be a data universe (any set), n≥1n\ge 1n≥1, and φ:X→{0,1}\varphi:X\to\{0,1\}φ:X→{0,1} a predicate. The counting query Qφ(z)=1n#{i:φ(zi)=1}Q_\varphi(z)=\frac1n\#\{i: \varphi(z_i)=1\}Qφ​(z)=n1​#{i:φ(zi​)=1} on inputs z∈Xnz\in X^nz∈Xn changes by at most 1/n1/n1/n when one entry of zzz is replaced:

GSQφ≤1n.GS_{Q_\varphi}\le\frac1n .GSQφ​​≤n1​.

This bound on the sensitivity of counting queries is what turns the general utility bound of the Net mechanism (Property 3.4) into its counting-query form (Corollary 3.5).

Formalization Note Neighbouring inputs differ in exactly one entry (PrivLearn.Generic.Neighbors). The input is read as the multiset of its entries. The global sensitivity is a real supremum over neighbouring pairs; the differences lie in [0,1][0,1][0,1], so it is a genuine supremum for any XXX.

Preamble
import Mathlib
import Definitions.Def_PrivateRelease_NetMechanism_Queries
Formal statement
namespace PrivateRelease.NetMechanism

/-- Observation 2.4 (p. 6): for any predicate `φ : X → {0,1}`, the counting query
`Q_φ : Xⁿ → [0, 1]` has global sensitivity `GS_{Q_φ} ≤ 1/n` (replace-one neighbours). -/
theorem observation_2_4 {X : Type} (φ : X → Bool) (n : ℕ) (hn : 1 ≤ n) :
    GS (fun z : Fin n → X => countQ φ (inputDB z)) ≤ 1 / (n : ℝ) := by sorry

end PrivateRelease.NetMechanism
Source
Blum, Ligett, Roth, A Learning Theory Approach to Non-Interactive Database Privacy, arXiv:1109.2229v1 (2011), p. 6, Observation 2.4
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 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