Theorem 6.1 — random LDPC codes above contain a matrix of type
OpenSilasListCapacity.Main.Supplement.theorem_6_1Let be a finite field with elements and let be a scale-invariant probability law on with full support: and for every and . Let and . Then there is with the following property. Let be any scale-invariant rounding of to denominator (probabilities in , ) such that, when , the matrices of type have columns of even weight. For every odd and every rate with
the random -LDPC code of rate contains a matrix of type with probability as through the multiples of .
Here is the random-linear-code threshold of Definition 2.2, so the theorem says that above that threshold random LDPC codes, like random linear codes, contain matrices of the type. It is the converse used to prove the second statement of Theorem 1.4.
Formalization Note "Contains a matrix of type " is the existence of with exactly rows equal to for every and all columns in the code. is chosen before the rounding sequence.
Differences from the source:
- reading: "τ_n a scale-invariant rounding of τ to denominator n" → one rounding for every sufficiently large n, eventually scale invariant (and with even-weight columns when q = 2), with an existential O(1/n) constant; reason: the conclusion is a statement as n → ∞, and the paper's own roundings exist only for large n.
- 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: columns of even weight → n·Pr_{τ_n}[x_j ≠ 0] even for every column j; reason: that number is the weight of column j.
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
/-- Theorem 6.1 (Silas, STOC 2027 #505, printed p. 24 / PDF p. 25): for a scale-invariant
full-support law `τ` on `F^m`, a random s-LDPC code of rate `R ∈ [R*_τ + γ, R₀]` contains a
matrix of type `τ_n` with probability `1 - o(1)`, for every odd `s ≥ s₀(q, τ, γ, R₀)` and every
scale-invariant rounding `τ_n` of `τ` (with even-weight columns when `q = 2`). -/
theorem theorem_6_1 {F : Type*} [Field F] [Fintype F] {m : ℕ} (τ : (Fin m → F) → ℝ)
(hτ : IsLaw τ) (hfull : ∀ v, 0 < τ v) (hsc : ScaleInvariant τ)
(γ : ℝ) (hγ : 0 < γ) (R₀ : ℝ) (hR₀ : R₀ < 1) :
∃ s₀ : ℕ, ∀ τs : ℕ → (Fin m → F) → ℝ, IsScaleInvRounding τ τs →
∀ s : ℕ, Odd s → s₀ ≤ s → ∀ t : ℕ,
Rstar τ + γ ≤ 1 - (t : ℝ) / (s : ℝ) → 1 - (t : ℝ) / (s : ℝ) ≤ R₀ →
LDPCWHP F s t (fun n C => ∃ B : Fin n → Fin m → F, HasType B (τs n) ∧ Contains C B) := by sorry
end SilasListCapacity.Main.Supplement