on , , and
ProvedSaglamGV.gammaKS_pos_and_lowercoding-theorygilbert-varshamov-boundlinear-codesp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let . Then
- for ;
- as : there are and with for ;
- for every there is with
The lower bound gives the factor in the third-moment estimate of Lemma 3.1.
Differences from the source:
- encoding: O(ρ) as ρ → 0 → ∃ C, δ > 0 with |γ(ρ) − (ρ/2) lg(1/ρ)| ≤ Cρ on (0, δ); reason: the meaning of O(·) at 0
Preamble
import Mathlib import Definitions.Def_SaglamGV_Analytic
Formal statement
namespace SaglamGV
/-- Positivity and growth of $γ$ (M. Saglam, *Linear codes exceeding the Gilbert–Varshamov bound*, STOC 2027 submission manuscript (held version, sha256 ac6f2bba…), Appendix A, p.6: "It follows that γ is strictly positive on
(0, 1/2) and γ(ρ) = (ρ/2) lg(1/ρ) + O(ρ) (ρ → 0). Consequently, for every fixed η > 0, there is a
constant c_η > 0 such that γ(ρ) ≥ c_η ρ lg(1/ρ) (0 < ρ ≤ 1/2 − η)").
**Formalization Note** "$O(ρ)$ as $ρ → 0$" is $|γ(ρ) − (ρ/2)\lg(1/ρ)| ≤ Cρ$ on some $(0, δ)$. -/
theorem gammaKS_pos_and_lower :
(∀ ρ : ℝ, 0 < ρ → ρ < 1 / 2 → 0 < gammaKS ρ) ∧
(∃ C δ : ℝ, 0 < δ ∧ ∀ ρ : ℝ, 0 < ρ → ρ < δ →
|gammaKS ρ - ρ / 2 * Real.logb 2 (1 / ρ)| ≤ C * ρ) ∧
(∀ η : ℝ, 0 < η → ∃ c : ℝ, 0 < c ∧ ∀ ρ : ℝ, 0 < ρ → ρ ≤ 1 / 2 - η →
c * ρ * Real.logb 2 (1 / ρ) ≤ gammaKS ρ) := 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 (γ positive on (0, 1/2); γ(ρ) = (ρ/2) lg(1/ρ) + O(ρ); γ(ρ) ≥ c_η ρ lg(1/ρ) for 0 < ρ ≤ 1/2 − η)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.