Parseval and
ProvedSaglamGV.parseval_muHat_and_log_volcoding-theorygilbert-varshamov-boundlinear-codesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
- For every and every , .
- There is an absolute constant such that for all and , with and ,
Together these give the normalization needed to apply the third-moment bound to .
Differences from the source:
- generalization: Parseval's identity in the regime of Appendix A → every n and every d ≥ 2; reason: Parseval's identity does not use the regime
- generalization: lg V = nH₂(ρ) + O(lg n) for ρ = w/n in the regime lg n ≪ w ≤ (1/2 − ε)n → one absolute constant C for all n ≥ 2 and 1 ≤ w ≤ n/2; reason: a uniform constant on a range containing the paper's specializes to it
- encoding: O(lg n) → |lg V − nH₂(w/n)| ≤ C·lg n for n ≥ 2; reason: the usual meaning of O(·) with an explicit constant
Preamble
import Mathlib import Definitions.Def_SaglamGV_Code import Definitions.Def_SelectiveDPT_H2 import Definitions.Def_SaglamGV_Walk import Definitions.Def_SaglamGV_Fourier
Formal statement
namespace SaglamGV
/-- Parseval and the size of $V$ (M. Saglam, *Linear codes exceeding the Gilbert–Varshamov bound*, STOC 2027 submission manuscript (held version, sha256 ac6f2bba…), Appendix A, p.6: "Moreover, Parseval's identity and
Stirling's formula give E_x µ̂(x)^2 = 1/V, lg V = nH_2(ρ) + O(lg n)").
(a) For $d ≥ 2$, $E_y \hat μ(y)^2 = 1/V$. (b) There is an absolute constant $C$ with
$|\lg V − nH_2(w/n)| ≤ C \lg n$ for all $n ≥ 2$ and $1 ≤ w ≤ n/2$, where $d = w + 1$.
**Formalization Note** $H_2$ is the published `SelectiveDPT.H2` (`Real.binEntropy p / Real.log 2`, the binary entropy in bits). The $O(\lg n)$ is made uniform over $1 ≤ w ≤ n/2$, a range containing the
paper's $ρ ≤ 1/2 − ε$; $\lg$ is `Real.logb 2`. -/
theorem parseval_muHat_and_log_vol :
(∀ n d : ℕ, 2 ≤ d → avgY (fun y => muHat n d y ^ 2) = 1 / (vol n d : ℝ)) ∧
∃ C : ℝ, ∀ n w : ℕ, 2 ≤ n → 1 ≤ w → 2 * w ≤ n →
|Real.logb 2 (vol n (w + 1)) - n * SelectiveDPT.H2 ((w : ℝ) / n)| ≤ C * Real.logb 2 n := by sorry
end SaglamGV
Source
M. Saglam, Linear codes exceeding the Gilbert–Varshamov bound, STOC 2027 submission manuscript (held version, sha256 ac6f2bba913aa15cfec8dda07a8e9e37b7186e145fef4719cb623dd04d15baa3), Appendix A, p.6 (display E_x µ̂(x)² = 1/V, lg V = nH₂(ρ) + O(lg n))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.