Lemma 4.3 — Erdős–Rényi identity
ProvedQaryCVP.lemma_4_3closest-vector-problemcomputational-complexitylatticesp2o-gran-per-chapterp2o-plan-paperp2o-v1q-ary-lattices
Let be a finite abelian group and . Let be uniform in and a fixed function with . Choose with independent uniform columns, independently of , and let be independent and uniform in , where . Then
It is the second-moment identity behind the passage from average success to success for every right-hand side (Lemma 4.4).
Formalization Note All expectations are finite uniform averages, written as sums.
Differences from the source: none.
Preamble
import Mathlib
Formal statement
namespace QaryCVP
/-- **Lemma 4.3** (Erdős–Rényi second-moment identity). Kim, Kwon, Lee, Lee, STOC 2027 submission
manuscript (sha256 9aeb2ff4…ab4), Lemma 4.3, pp.35–36.
Let `G` be a finite abelian group and `ℓ ≥ 1`. Let `s` be uniform in `G` and `Φ : G → R` a fixed
function with `E_s[Φ(s)] = 0`. Choose `C ∈ G^ℓ` with independent uniform columns, independently of
`s`, and `u` independent and uniform in `{0, 1}^ℓ`, where `Cu = Σ_{i : uᵢ = 1} Cᵢ`. Then
`E_{C,s}[(E_u[Φ(s − Cu)])²] = 2^{−ℓ} E_s[Φ(s)²]`.
**Formalization Note.** All expectations are finite uniform averages; `E_s[Φ] = 0` is `Σ_s Φ(s) = 0`. -/
theorem lemma_4_3 {G : Type} [AddCommGroup G] [Fintype G] (ℓ : ℕ) (hℓ : 1 ≤ ℓ) (Φ : G → ℝ)
(hΦ : ∑ s, Φ s = 0) :
(∑ C : Fin ℓ → G, ∑ s : G,
((∑ u : Fin ℓ → Bool, Φ (s - ∑ i, if u i then C i else 0)) / (2 : ℝ) ^ ℓ) ^ 2) /
((Fintype.card G : ℝ) ^ ℓ * Fintype.card G) =
(1 / 2 : ℝ) ^ ℓ * ((∑ s, Φ s ^ 2) / Fintype.card G) := by sorry
end QaryCVP
Source
Kim, Kwon, Lee, Lee, Fast Provable Algorithms for Approximate CVP and Exact SVP on Random q-ary Lattices, STOC 2027 submission manuscript (sha256 9aeb2ff4…ab4), Lemma 4.3, pp.35–36
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.