Lemma 6.5 — an LDPC code containing a given matrix of type has no low-weight codewords w.h.p.
OpenSilasListCapacity.Main.Supplement.lemma_6_5Let be a finite field with elements, , and . Work in the setting of Theorem 6.1: is a scale-invariant law on with full support ( for every ), is the largest for which is -smooth, is a scale-invariant rounding of (with even-weight columns when ), and . For a random -LDPC code let be the number of matrices of type contained in , let be the event that every nonzero codeword of has weight at least , and let .
There is , depending only on , and , such that for every there is such that for every odd and every rate with ,
Equivalently, a random -LDPC code that contains a given matrix of type has no nonzero codeword of weight less than with probability .
The lemma lets the second-moment argument for Theorem 6.1 restrict to codes of good distance, replacing by at the cost of a factor in .
Formalization Note is chosen before , , the rounding and (it depends on , , only, as the lemma states); may depend on everything. is a ratio of uniform averages over the LDPC ensemble, and is a limit along .
Differences from the source:
- encoding: "δ > 0 small enough in terms of q, δ_τ and R_0" → ∃ δ₀ > 0 chosen from F, R₀ and δ_τ before m, τ, (τ_n), γ, and the claim for every δ ∈ (0, δ₀]; reason: that is the quantifier order the phrase states.
- encoding: δ_τ → a parameter d_τ > 0 with the hypothesis that it is the largest δ for which τ is δ-smooth; reason: lets δ₀ be chosen in terms of δ_τ before τ.
- encoding: rate R → t ∈ ℕ layers with R = 1 − t/s, limits along n = s·b; reason: the ensemble is defined only for integer t and s | n.
- encoding: Ẽ[F] = E[XF]/E[X], defined where E[X] > 0 → real division, with value 0 when E[X] = 0; reason: in this setting E[X] > 0 (Lemma 6.4 gives p(τ_n)^t > 0 for the matrices of type τ_n), so the convention changes no instance the source considers.
import Mathlib import Definitions.Def_SilasListCapacity_Main_Model import Definitions.Def_SilasListCapacity_Main_Supplement_LDPC set_option autoImplicit false noncomputable section open scoped BigOperators open Filter Topology
namespace SilasListCapacity.Main.Supplement
open SilasListCapacity.Main
open Classical in
/-- Lemma 6.5 (Silas, STOC 2027 #505, printed p. 27 / PDF p. 28): for `δ` small in terms of
`q`, `δ_τ` and `R₀`, and `s` large, a random s-LDPC code containing a given matrix of type
`τ_n` has no nonzero codeword of weight below `δ n` with probability `1 - o(1)`:
`Ẽ[1_{D_δ^c}] = E[X·1_{D_δ^c}] / E[X] → 0`. -/
theorem lemma_6_5 (F : Type*) [Field F] [Fintype F] (R₀ : ℝ) (hR₀ : R₀ < 1)
(dτ : ℝ) (hdτ : 0 < dτ) :
∃ δ₀ : ℝ, 0 < δ₀ ∧
∀ (m : ℕ) (τ : (Fin m → F) → ℝ), IsLaw τ → (∀ v, 0 < τ v) → ScaleInvariant τ →
IsSmoothnessConst dτ τ →
∀ τs : ℕ → (Fin m → F) → ℝ, IsScaleInvRounding τ τs →
∀ γ : ℝ, 0 < γ → ∀ δ : ℝ, 0 < δ → δ ≤ δ₀ →
∃ s₁ : ℕ, ∀ s : ℕ, Odd s → s₁ ≤ s → ∀ t : ℕ,
Rstar τ + γ ≤ 1 - (t : ℝ) / (s : ℝ) → 1 - (t : ℝ) / (s : ℝ) ≤ R₀ →
Tendsto (fun b : ℕ =>
ldpcExp F (s * b) s t
(fun C => (typeCount C (τs (s * b)) : ℝ) *
(if MinWeightAtLeast δ C then 0 else 1)) /
ldpcExp F (s * b) s t (fun C => (typeCount C (τs (s * b)) : ℝ)))
atTop (𝓝 0) := by sorry
end SilasListCapacity.Main.Supplement