Lemma 3.6 — small-ball image bound
OpenLowRandomnessDP.KNorm.Supplement.lemma_3_6differential-privacydiscrete-geometryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is an absolute real constant such that, for every , every and every integer , the image of the closed sup-norm ball under Algorithm 1 is finite and satisfies
The same constant works for all dimensions, centres and scales. This is the small-ball image bound for the explicit partition.
Differences from the source:
- reading: without an explicit boundary convention → the closed coordinate sup-norm ball; reason: the interval argument on PDF p. 13 covers the endpoints and agrees with the published partition interface
- encoding: cardinality at most → explicit finiteness and real-cast
Set.ncardbounded by a real power with one positive constant before ; reason: this expresses the absolute O bound and prevents infinite sets receiving cardinal zero
Preamble
import Definitions.Def_LowRandomnessDP_KNorm_Supplement_Rounding set_option autoImplicit false open Classical
Formal statement
namespace LowRandomnessDP.KNorm.Supplement
/-- Lemma 3.6, PDF 13 / printed 11. One absolute O constant, before all instances. -/
theorem lemma_3_6 :
∃ c : ℝ, 0 < c ∧ ∀ (d : ℕ) (hd : 0 < d) (x : Vec d)
(ℓ : ℕ), 1 ≤ ℓ → ℓ ≤ d →
(R hd '' infinityBall x (1 / (ℓ : ℝ))).Finite ∧
((R hd '' infinityBall x (1 / (ℓ : ℝ))).ncard : ℝ) ≤
Real.rpow ((ℓ : ℝ) + 1) (c * (d : ℝ) / ℓ) := by sorry
end LowRandomnessDP.KNorm.Supplement
Source
Surendra Ghentiyala, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, STOC 2027 submission #514 (October 2026), Lemma 3.6, PDF p. 13 / printed p. 11; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/514.pdf; SHA-256 1562e70c55d785f992aaa32a161f0b06ac058da62f8f71fb07610037a20bc37b