Theorem 1.4 — random LDPC codes have the random-linear-code threshold of every convex local property
OpenSilasListCapacity.Main.Supplement.theorem_1_4Let be a finite field with elements and . Let be a local property with columns: is closed under permutations of rows and of columns, and a code satisfies the property if it contains no matrix of . Let be a set of probability laws on and
Assume that is the threshold rate of for random linear codes: a random linear code of rate (the image of a uniform matrix) satisfies with probability for every , and does not satisfy with probability for every . Assume that is convex:
- is closed under mixtures and under multiplication of rows by an element of ;
- for every some has support equal to ;
- every scale-invariant whose support is a subspace has scale-invariant roundings to denominator (probabilities in , ) that are bad types of supported in and, when , whose matrices have columns of even weight.
Then for every there is such that for every odd and every number of layers with rate , the random -LDPC code of rate
as through the multiples of .
This answers the question of Mosheiff et al. on which local properties random LDPC codes and random linear codes share a threshold; distance, list decoding, average-radius list decoding and list recovery are all convex.
Formalization Note The objects are those of the supplement definition SilasListCapacity_Main_Supplement_LDPC on top of the published model; is an EReal infimum, and both conclusions are limits of the exact ensemble probability along .
Differences from the source:
- reading: "for random linear codes, the threshold rate for P is R_RLC" → RLC satisfies P w.p. 1−o(1) for every rate 0 ≤ R < R_RLC and fails P w.p. 1−o(1) for every R_RLC < R < 1; reason: the paper's definition of the threshold rate (printed p. 1 and Lemma 2.3); for nonempty T, R_RLC ≤ 1, so the first range is inside [0, 1); for empty T (R_RLC = +∞) the first range is every real R ≥ 0, which is equivalent to every rate R ∈ [0, 1], since a random linear code of rate 1 is all of F^n with probability bounded away from 0, so satisfying P w.p. 1−o(1) at R = 1 already forces Bad_n = ∅ for large n.
- encoding: inf_{τ∈T} R*_τ → an EReal infimum (+∞ for empty T); reason: the real sInf ∅ = 0 would change the statement; for nonempty T the value is the real infimum.
- reading: multiplication of rows by elements of F_q^× → the law of ξx for one fixed ξ ∈ F^×; reason: the paper's own check of condition (1) on printed p. 25 multiplies "by one nonzero element".
- reading: "has roundings ν_n" → one rounding for every sufficiently large n, the O(1/n) bound with one existential constant; reason: the paper's proof of condition (3) provides ν_n only for n large.
- encoding: random s-LDPC code of rate R, t := (1−R)s layers → t ∈ ℕ layers with R = 1 − t/s ≥ 0 and limits along n = s·b; reason: the ensemble is only defined for integer t and n divisible by s.
- encoding: columns of even weight → n·Pr_{ν_n}[x_j ≠ 0] is an even natural number for every column j; reason: that number is the weight of column j of every matrix of type ν_n.
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 1.4 (Silas, STOC 2027 #505, printed p. 4 / PDF p. 5): for a convex local property
`Bad` whose random-linear-code threshold is `R_RLC = inf_{τ ∈ T} R*_τ`, random s-LDPC codes have
the same threshold. -/
theorem theorem_1_4 {F : Type*} [Field F] [Fintype F] {m : ℕ}
(Bad : ∀ n : ℕ, Set (Fin n → Fin m → F)) (hBad : IsLocalProperty Bad)
(T : Set ((Fin m → F) → ℝ)) (hT : ∀ τ ∈ T, IsLaw τ)
(hsat : ∀ R : ℝ, 0 ≤ R → (R : EReal) < rlcThreshold T →
WHP F R (fun n C => Satisfies Bad (n := n) C))
(hfail : ∀ R : ℝ, rlcThreshold T < (R : EReal) → R < 1 →
WHP F R (fun n C => ¬ Satisfies Bad (n := n) C))
(h1 : MixScaleClosed T) (h2 : SpanSupported T) (h3 : RoundsToBad Bad T) :
∀ γ : ℝ, 0 < γ → ∃ s₀ : ℕ, ∀ s : ℕ, Odd s → s₀ ≤ s → ∀ t : ℕ,
0 ≤ 1 - (t : ℝ) / (s : ℝ) →
((((1 - (t : ℝ) / (s : ℝ) : ℝ) : EReal) ≤ rlcThreshold T - (γ : EReal) →
LDPCWHP F s t (fun n C => Satisfies Bad (n := n) C)) ∧
(rlcThreshold T + (γ : EReal) ≤ ((1 - (t : ℝ) / (s : ℝ) : ℝ) : EReal) →
1 - (t : ℝ) / (s : ℝ) ≤ 1 - γ →
LDPCWHP F s t (fun n C => ¬ Satisfies Bad (n := n) C))) := by sorry
end SilasListCapacity.Main.Supplement