Proved
SaglamGV.vol_ge_choose_gecoding-theorygilbert-varshamov-boundlinear-codesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , , and . Then
This standard estimate converts the entropy form of the Kirshner–Samorodnitsky bounds into bounds in terms of .
Differences from the source:
- generalization: w in the regime lg n ≪ w ≤ (1/2 − ε)n → every 1 ≤ w ≤ n; reason: the estimate holds for every such w; it specializes to the paper's
- encoding: 2^{nH₂(ρ)} → a real power (2 : ℝ) ^ (n * H2 (w / n)); reason: Lean convention; same values
Preamble
import Mathlib import Definitions.Def_SaglamGV_Code import Definitions.Def_SelectiveDPT_H2
Formal statement
namespace SaglamGV
/-- The standard binomial estimate (M. Saglam, *Linear codes exceeding the Gilbert–Varshamov bound*, STOC 2027 submission manuscript (held version, sha256 ac6f2bba…), Appendix A, p.7: "The standard estimate
V ≥ (n choose w) ≥ 2^{nH_2(ρ)}/(n + 1)").
For $1 ≤ w ≤ n$, $d = w + 1$ and $ρ = w/n$: $V ≥ \binom{n}{w} ≥ 2^{nH_2(ρ)}/(n+1)$.
**Formalization Note** $H_2$ is the published `SelectiveDPT.H2` (`Real.binEntropy p / Real.log 2`, the binary entropy in bits). The power $2^{nH_2(ρ)}$ is a real power. -/
theorem vol_ge_choose_ge (n w : ℕ) (hn : 1 ≤ n) (hw : 1 ≤ w) (hwn : w ≤ n) :
(n.choose w : ℝ) ≤ vol n (w + 1) ∧
(2 : ℝ) ^ ((n : ℝ) * SelectiveDPT.H2 ((w : ℝ) / n)) / ((n : ℝ) + 1) ≤ n.choose w := 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.7 (display V ≥ (n choose w) ≥ 2^{nH₂(ρ)}/(n + 1))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.