Lemma 3.4 — fractional-part shift identity
ProvedLowRandomnessDP.KNorm.Supplement.lemma_3_4differential-privacydiscrete-geometryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , and satisfy . With defined by Algorithm 1,
This exact shift identity relates the finite minimization criterion to counts of coordinates near the end of a unit interval.
Differences from the source:
- encoding: one-based coordinate count and congruence →
Fin dcoordinates and shifts, real-cast finite cardinality, andInt.ModEqwith integer subtraction; reason: the same index sets and exact integer congruence are retained without natural subtraction truncation
Preamble
import Definitions.Def_LowRandomnessDP_KNorm_Supplement_Rounding set_option autoImplicit false open Classical
Formal statement
namespace LowRandomnessDP.KNorm.Supplement
/-- Lemma 3.4, PDF 12 / printed 10. Congruence uses integer subtraction. -/
theorem lemma_3_4 (d : ℕ) (hd : 0 < d) (x : Vec d) (a b m : Fin d)
(hcong : Int.ModEq (d : ℤ) (b.val : ℤ) ((a.val : ℤ) - (m.val : ℤ))) :
phi x b - phi x a = (m.val : ℝ) -
((Finset.univ.filter (fun i : Fin d =>
1 - (m.val : ℝ) / d ≤ Int.fract (x i - (a.val : ℝ) / d))).card : ℝ) := by sorry
end LowRandomnessDP.KNorm.Supplement
Source
Surendra Ghentiyala, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, STOC 2027 submission #514 (October 2026), Lemma 3.4, PDF p. 12 / printed p. 10; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/514.pdf; SHA-256 1562e70c55d785f992aaa32a161f0b06ac058da62f8f71fb07610037a20bc37b