for
ProvedSaglamGV.redund_thetacoding-theorygilbert-varshamov-boundlinear-codesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Fix . There is a constant , depending only on , such that for all integers and with , writing , and ,
So the redundancy is linear in the block length throughout the regime of the paper. The upper bound is used in §3.3 in the form .
Differences from the source:
- generalization: the regime ln n ≪ w ≤ (1/2 − ε)n → every n ≥ 1 and 1 ≤ w ≤ (1/2 − ε)n, with no growth condition on w; reason: the bound needs only V ≥ 1 and w ≤ (1/2 − ε)n; the paper's regime implies 1 ≤ w
- encoding: w = d − 1 → d = w + 1 with w : ℕ; reason: avoids natural-number subtraction; same instances
Preamble
import Mathlib import Definitions.Def_SaglamGV_Code import Definitions.Def_SaglamGV_Params
Formal statement
namespace SaglamGV
/-- $R = Θ(n)$ (M. Saglam, *Linear codes exceeding the Gilbert–Varshamov bound*, STOC 2027 submission manuscript (held version, sha256 ac6f2bba…), §2, p.2: "Our assumptions imply R = Θ(n)"; the upper bound $R ≤ n \ln 2$ is
used again on p.4: "τ < R ≤ n ln 2 < n").
For every $ε > 0$ there is $a > 0$ such that $a n ≤ R ≤ n \ln 2$ whenever $1 ≤ w ≤ (1/2 − ε)n$,
where $d = w + 1$ and $R = \ln(2^n/V)$.
**Formalization Note** The paper's regime is $\ln n ≪ w ≤ (1/2 − ε)n$; the statement only needs
$w ≥ 1$ (so that $V ≥ 1$), which that regime implies. -/
theorem redund_theta (ε : ℝ) (hε : 0 < ε) :
∃ a : ℝ, 0 < a ∧ ∀ n w : ℕ, 1 ≤ n → 1 ≤ w → (w : ℝ) ≤ (1 / 2 - ε) * n →
a * n ≤ redund n (w + 1) ∧ redund n (w + 1) ≤ n * Real.log 2 := by sorry
end SaglamGV
Source
M. Saglam, Linear codes exceeding the Gilbert–Varshamov bound, STOC 2027 submission manuscript (held version, sha256 ac6f2bba913aa15cfec8dda07a8e9e37b7186e145fef4719cb623dd04d15baa3), §2, p.2 ("Our assumptions imply R = Θ(n)"); upper bound used on p.4 ("τ < R ≤ n ln 2 < n")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.