§1.1–1.2, §6 — matrix types, local properties, convexity conditions, random s-LDPC codes and the one-layer quantities of §6.2
DefinitionSilasListCapacity_Main_Supplement_LDPCThroughout, is a finite field with elements (every prime power, extension fields included). The laws , the probability , the threshold functional and the span of the support are those of the published model SilasListCapacity_Main_Model; a linear code is an -subspace .
Matrices, types and containment. A matrix has rows (indexed by the coordinates) and columns (words of ). It has type , a law on , if for every exactly rows of equal . A code contains if every column of lies in .
Local properties. A local property with columns is a family , one for each , closed under permutations of the rows and of the columns. A code satisfies it if it contains no matrix of . A law is a bad type at length if some matrix of type is bad.
Scale invariance, roundings, convexity conditions. is scale invariant if for every . A sequence is a rounding of if there is a constant such that, for every sufficiently large , is a law with all probabilities in and for all . Matrices of type have columns of even weight if is even for every column . A scale-invariant rounding of is a rounding whose terms are eventually scale invariant and, when , eventually have even-weight columns. For a set of laws on :
- condition (1): is closed under mixtures , , and, for each , under passing from the law of to the law of ;
- condition (2): for every some has support exactly ;
- condition (3): every scale-invariant whose support is a subspace has a rounding whose terms are, for all large , scale invariant, bad types at length , supported in , and, when , have even-weight columns.
The threshold of is , an extended real ( for empty ).
Random -LDPC codes. A layer on coordinates is a permutation of and coefficients . Its -th block is and imposes the check . The -LDPC code with layers is the set of words satisfying every check of every layer. The random -LDPC code draws the permutations uniformly and all coefficients uniformly from , all independent; its rate is . A property holds for it with probability if its probability tends to as through the multiples of .
One-layer quantities (§6.2). For a matrix , is the probability that one random layer is satisfied by every column of . For a law on , has independent rows distributed as and is independent of the layer; the definition records , , their joint probability, the conditional probability of satisfying given the type, and . Finally
Smoothness and distance (§6.2). is -smooth if for all and, when , also ; is the largest such . counts the matrices of type contained in the code, and is the event that every nonzero codeword has Hamming weight at least .
These are the objects of Theorems 1.4 and 6.1 and Lemmas 6.2 and 6.5.
Formalization Note Matrices are functions Fin n → Fin m → F (row i is B i). Probabilities over the LDPC ensemble are uniform averages over (Fin t → Perm (Fin n)) × (Fin t → Fin n → Fˣ); coefficients are indexed by coordinate, which gives the same distribution as indexing by block position. Conditional probabilities are ratios. rlcThreshold is an EReal infimum so that an empty is not mapped to .
import Mathlib
import Definitions.Def_SilasListCapacity_Main_Model
set_option autoImplicit false
noncomputable section
open scoped BigOperators
open Filter Topology
namespace SilasListCapacity.Main.Supplement
open SilasListCapacity.Main
variable {F : Type*} [Field F] [Fintype F]
/-! ### Matrices, their types and containment (Silas, STOC 2027 #505, §1.1, printed p. 3 / PDF p. 4)
A matrix `B ∈ F^{n×m}` is a function `Fin n → Fin m → F`: `B i` is its `i`-th row (a vector of
`F^m`), and `fun i => B i j` is its `j`-th column (a word of `F^n`). -/
/-- Number of rows of `B ∈ F^{n×m}` that are equal to `v ∈ F^m`. -/
def rowCount {n m : ℕ} (B : Fin n → Fin m → F) (v : Fin m → F) : ℕ := by
classical
exact (Finset.univ.filter (fun i => B i = v)).card
/-- `B ∈ F^{n×m}` has type `ω` (its row distribution is `ω`): for every `v ∈ F^m`,
exactly `n·ω(v)` rows of `B` are equal to `v`. -/
def HasType {n m : ℕ} (B : Fin n → Fin m → F) (ω : (Fin m → F) → ℝ) : Prop :=
∀ v : Fin m → F, (rowCount B v : ℝ) = (n : ℝ) * ω v
/-- The code `C ≤ F^n` contains the matrix `B ∈ F^{n×m}`: every column of `B` is a codeword. -/
def Contains {n m : ℕ} (C : CodingTheory.LinearCode F (Fin n)) (B : Fin n → Fin m → F) : Prop :=
∀ j : Fin m, (fun i => B i j) ∈ C
/-! ### Local properties (§1.1, printed p. 3 / PDF p. 4; Theorem 1.4, printed p. 4 / PDF p. 5) -/
/-- `Bad` is a local property with `m` columns: for every length `n` a family `Bad n` of bad
matrices in `F^{n×m}`, closed under permutations of the rows and under permutations of the
columns. -/
def IsLocalProperty {m : ℕ} (Bad : ∀ n : ℕ, Set (Fin n → Fin m → F)) : Prop :=
(∀ (n : ℕ) (B : Fin n → Fin m → F) (π : Equiv.Perm (Fin n)),
B ∈ Bad n → (fun i => B (π i)) ∈ Bad n) ∧
(∀ (n : ℕ) (B : Fin n → Fin m → F) (π : Equiv.Perm (Fin m)),
B ∈ Bad n → (fun i j => B i (π j)) ∈ Bad n)
/-- The code `C ≤ F^n` satisfies the local property `Bad`: it contains no bad matrix. -/
def Satisfies {m n : ℕ} (Bad : ∀ n : ℕ, Set (Fin n → Fin m → F))
(C : CodingTheory.LinearCode F (Fin n)) : Prop :=
∀ B ∈ Bad n, ¬ Contains C B
/-- `ν` is a bad type of `Bad` at length `n`: some matrix in `F^{n×m}` of type `ν` is bad
(by row-permutation invariance, then every matrix of type `ν` is bad). -/
def IsBadType {m : ℕ} (Bad : ∀ n : ℕ, Set (Fin n → Fin m → F)) (n : ℕ)
(ν : (Fin m → F) → ℝ) : Prop :=
∃ B ∈ Bad n, HasType B ν
/-! ### Scale invariance, roundings and the convexity conditions (Theorem 1.4, printed p. 4 /
PDF p. 5; Theorem 6.1, printed p. 24 / PDF p. 25) -/
/-- `ν` is scale invariant: `ν(ξ v) = ν(v)` for every `ξ ∈ F^×` and every `v ∈ F^m`. -/
def ScaleInvariant {m : ℕ} (ν : (Fin m → F) → ℝ) : Prop :=
∀ ξ : F, ξ ≠ 0 → ∀ v : Fin m → F, ν (ξ • v) = ν v
/-- `ν` is a law on `F^m` with denominator `n`: every probability lies in `(1/n)ℤ`. -/
def HasDenominator {m : ℕ} (n : ℕ) (ν : (Fin m → F) → ℝ) : Prop :=
IsLaw ν ∧ ∀ v : Fin m → F, ∃ k : ℕ, (n : ℝ) * ν v = (k : ℝ)
/-- `νs` is a sequence of roundings of `ν`: for every sufficiently large `n`, `νs n` is a law
with probabilities in `(1/n)ℤ`, and `νs n - ν = O(1/n)`, i.e. `|νs n v - ν v| ≤ C / n` for one
constant `C` and all `v`. -/
def IsRounding {m : ℕ} (ν : (Fin m → F) → ℝ) (νs : ℕ → (Fin m → F) → ℝ) : Prop :=
∃ C : ℝ, ∀ᶠ n in atTop,
HasDenominator n (νs n) ∧ ∀ v : Fin m → F, |νs n v - ν v| ≤ C / (n : ℝ)
/-- Every matrix in `F^{n×m}` of type `ν` has columns of even weight: for each column `j`,
`n · Pr_{x∼ν}[x_j ≠ 0]` (the weight of column `j`) is an even natural number. -/
def EvenColumns {m : ℕ} (n : ℕ) (ν : (Fin m → F) → ℝ) : Prop :=
∀ j : Fin m, ∃ k : ℕ, (n : ℝ) * prob ν (fun v => v j ≠ 0) = 2 * (k : ℝ)
/-- `τs` is a scale-invariant rounding of `τ` to denominator `n` such that, when `q = |F| = 2`,
the matrices of type `τs n` have columns of even weight (all for `n` large). -/
def IsScaleInvRounding {m : ℕ} (τ : (Fin m → F) → ℝ) (τs : ℕ → (Fin m → F) → ℝ) : Prop :=
IsRounding τ τs ∧
∀ᶠ n in atTop, ScaleInvariant (τs n) ∧ (Fintype.card F = 2 → EvenColumns n (τs n))
/-- Condition (1) of Theorem 1.4: `T` is closed under mixtures `(1-θ)τ + θτ'`, `θ ∈ [0,1]`, and
under multiplication of rows by an element `ξ ∈ F^×` (the law of `ξx` for `x ∼ τ`, whose mass
at `v` is `τ(ξ⁻¹ v)`). -/
def MixScaleClosed {m : ℕ} (T : Set ((Fin m → F) → ℝ)) : Prop :=
(∀ τ ∈ T, ∀ τ' ∈ T, ∀ θ : ℝ, 0 ≤ θ → θ ≤ 1 → (fun v => (1 - θ) * τ v + θ * τ' v) ∈ T) ∧
(∀ τ ∈ T, ∀ ξ : F, ξ ≠ 0 → (fun v => τ (ξ⁻¹ • v)) ∈ T)
/-- Condition (2) of Theorem 1.4: for every `τ ∈ T` some `τ' ∈ T` has support equal to the
span of `supp τ`. -/
def SpanSupported {m : ℕ} (T : Set ((Fin m → F) → ℝ)) : Prop :=
∀ τ ∈ T, ∃ τ' ∈ T, ∀ v : Fin m → F, 0 < τ' v ↔ v ∈ suppSpan τ
/-- Condition (3) of Theorem 1.4: every scale-invariant `ν ∈ T` whose support is a subspace has
scale-invariant roundings `νs n` to denominator `n` (eventually in `n`) that are bad types of
`Bad` at length `n`, with support contained in `supp ν`, and, when `q = 2`, whose matrices have
columns of even weight. -/
def RoundsToBad {m : ℕ} (Bad : ∀ n : ℕ, Set (Fin n → Fin m → F))
(T : Set ((Fin m → F) → ℝ)) : Prop :=
∀ ν ∈ T, ScaleInvariant ν →
(∃ W : Submodule F (Fin m → F), ∀ v : Fin m → F, 0 < ν v ↔ v ∈ W) →
∃ νs : ℕ → (Fin m → F) → ℝ, IsRounding ν νs ∧
∀ᶠ n in atTop, ScaleInvariant (νs n) ∧ IsBadType Bad n (νs n) ∧
(∀ v : Fin m → F, 0 < νs n v → 0 < ν v) ∧
(Fintype.card F = 2 → EvenColumns n (νs n))
/-- `R_RLC := inf_{τ ∈ T} R*_τ`, as an extended real (`+∞` for an empty `T`). -/
def rlcThreshold {m : ℕ} (T : Set ((Fin m → F) → ℝ)) : EReal :=
⨅ τ ∈ T, ((Rstar τ : ℝ) : EReal)
/-! ### Random s-LDPC codes (§1.2, printed p. 4 / PDF p. 5)
A layer on `n` coordinates is a permutation `σ` of `Fin n` and coefficients `ξ : Fin n → F^×`.
Its `j`-th block is `{σ(js), …, σ(js + s - 1)}`, i.e. the coordinates `i` with
`⌊σ⁻¹(i)/s⌋ = j`, and imposes the parity check `∑_{i in block j} ξ_i x_i = 0`. -/
/-- The block of the layer with permutation `σ` that contains coordinate `i`. -/
def blockIndex {n : ℕ} (s : ℕ) (σ : Equiv.Perm (Fin n)) (i : Fin n) : ℕ :=
((σ.symm i : Fin n) : ℕ) / s
/-- The parity check of block `j`: `x ↦ ∑_{i in block j} ξ_i x_i`. -/
def checkFun {n : ℕ} (s : ℕ) (σ : Equiv.Perm (Fin n)) (ξ : Fin n → Fˣ) (j : ℕ) :
(Fin n → F) →ₗ[F] F :=
∑ i ∈ Finset.univ.filter (fun i => blockIndex s σ i = j),
(ξ i : F) • (LinearMap.proj i : (Fin n → F) →ₗ[F] F)
/-- The words satisfying every parity check of one layer. -/
def layerCode {n : ℕ} (s : ℕ) (σ : Equiv.Perm (Fin n)) (ξ : Fin n → Fˣ) :
CodingTheory.LinearCode F (Fin n) :=
⨅ j : ℕ, LinearMap.ker (checkFun s σ ξ j)
/-- The s-LDPC code with `t` layers `(σs l, ξs l)`: the words satisfying every check of every
layer (all of `F^n` when `t = 0`). -/
def ldpcCode {n t : ℕ} (s : ℕ) (σs : Fin t → Equiv.Perm (Fin n)) (ξs : Fin t → Fin n → Fˣ) :
CodingTheory.LinearCode F (Fin n) :=
⨅ l : Fin t, layerCode s (σs l) (ξs l)
/-- Expectation of `f(C)` for the random s-LDPC code `C` of length `n` with `t` layers: the
`t` permutations are independent and uniform on `Perm (Fin n)`, and the `t·n` coefficients are
independent and uniform on `F^×`. -/
def ldpcExp (F : Type*) [Field F] [Fintype F] (n s t : ℕ)
(f : CodingTheory.LinearCode F (Fin n) → ℝ) : ℝ := by
classical
exact (∑ e : (Fin t → Equiv.Perm (Fin n)) × (Fin t → Fin n → Fˣ), f (ldpcCode s e.1 e.2)) /
(Fintype.card ((Fin t → Equiv.Perm (Fin n)) × (Fin t → Fin n → Fˣ)) : ℝ)
/-- Probability that the random s-LDPC code of length `n` with `t` layers satisfies `P`. -/
def ldpcProb (F : Type*) [Field F] [Fintype F] (n s t : ℕ)
(P : CodingTheory.LinearCode F (Fin n) → Prop) : ℝ := by
classical
exact ldpcExp F n s t (fun C => if P C then 1 else 0)
/-- "With probability `1 - o(1)`, a random s-LDPC code with `t` layers (rate `1 - t/s`)
satisfies `P`": the probability tends to `1` as `n → ∞` through the multiples `n = s·b`. -/
def LDPCWHP (F : Type*) [Field F] [Fintype F] (s t : ℕ)
(P : ∀ n : ℕ, CodingTheory.LinearCode F (Fin n) → Prop) : Prop :=
Tendsto (fun b : ℕ => ldpcProb F (s * b) s t (P (s * b))) atTop (𝓝 1)
/-! ### One-layer quantities of Lemma 6.2 (§6.2, printed p. 26 / PDF p. 27) -/
/-- `p(B)`: the probability, over one random layer (uniform permutation of `Fin n`, independent
uniform coefficients in `F^×`), that every column of `B ∈ F^{n×d}` satisfies all its checks. -/
def layerProb (F : Type*) [Field F] [Fintype F] {n d : ℕ} (s : ℕ)
(B : Fin n → Fin d → F) : ℝ := by
classical
exact ((Finset.univ.filter (fun e : Equiv.Perm (Fin n) × (Fin n → Fˣ) =>
Contains (layerCode s e.1 e.2) B)).card : ℝ) /
(Fintype.card (Equiv.Perm (Fin n) × (Fin n → Fˣ)) : ℝ)
/-- Probability `∏_i μ(Λ_i)` of the matrix `Λ` when its rows are independent samples of `μ`. -/
def rowsWeight {n d : ℕ} (μ : (Fin d → F) → ℝ) (Λ : Fin n → Fin d → F) : ℝ :=
∏ i, μ (Λ i)
/-- `Λ` and `B` have the same type (the same number of rows equal to each `v`). -/
def SameType {n d : ℕ} (Λ B : Fin n → Fin d → F) : Prop :=
∀ v : Fin d → F, rowCount Λ v = rowCount B v
/-- `Pr[Λ has the type of B]`, `Λ` with independent rows `∼ μ`. -/
def typeProb {n d : ℕ} (μ : (Fin d → F) → ℝ) (B : Fin n → Fin d → F) : ℝ := by
classical
exact ∑ Λ : Fin n → Fin d → F, rowsWeight μ Λ * (if SameType Λ B then 1 else 0)
/-- `Pr[Λ satisfies the checks of one layer]`, `Λ ∈ F^{n×d}` with independent rows `∼ μ` and
independent of the layer. -/
def satProb (F : Type*) [Field F] [Fintype F] (n : ℕ) {d : ℕ} (s : ℕ)
(μ : (Fin d → F) → ℝ) : ℝ :=
∑ Λ : Fin n → Fin d → F, rowsWeight μ Λ * layerProb F s Λ
/-- `Pr[Λ satisfies the checks of one layer and has the type of B]`. -/
def satTypeProb {n d : ℕ} (s : ℕ) (μ : (Fin d → F) → ℝ) (B : Fin n → Fin d → F) : ℝ := by
classical
exact ∑ Λ : Fin n → Fin d → F,
rowsWeight μ Λ * layerProb F s Λ * (if SameType Λ B then 1 else 0)
/-- `Pr[Λ satisfies the checks of one layer | Λ has the type of B]`. -/
def satGivenType {n d : ℕ} (s : ℕ) (μ : (Fin d → F) → ℝ) (B : Fin n → Fin d → F) : ℝ :=
satTypeProb s μ B / typeProb μ B
/-- `Pr[S_μ = nω]` with `ω` the type of `B`: `S_μ` is `n` times the type of `Λ` conditioned on
`Λ` satisfying the checks of one layer, so this is
`Pr[Λ has type ω | Λ satisfies the layer]`. -/
def sMuProb {n d : ℕ} (s : ℕ) (μ : (Fin d → F) → ℝ) (B : Fin n → Fin d → F) : ℝ :=
satTypeProb s μ B / satProb F n s μ
/-- `Pr_ξ[∑_i ξ_i w_i = 0]` for a block `w = (w_1, …, w_s)` of rows in `F^d`, with
`ξ_1, …, ξ_s` independent and uniform on `F^×`. -/
def blockSatProb (F : Type*) [Field F] [Fintype F] {s d : ℕ} (w : Fin s → Fin d → F) : ℝ := by
classical
exact ((Finset.univ.filter (fun ξ : Fin s → Fˣ => ∑ i, (ξ i : F) • w i = 0)).card : ℝ) /
(Fintype.card (Fin s → Fˣ) : ℝ)
/-- `P_d(μ) := ∑_{w ∈ (F^d)^s} Pr_ξ[∑_i ξ_i w_i = 0] ∏_i μ(w_i)`. -/
def Pd (F : Type*) [Field F] [Fintype F] (s : ℕ) {d : ℕ} (μ : (Fin d → F) → ℝ) : ℝ :=
∑ w : Fin s → Fin d → F, blockSatProb F w * ∏ i, μ (w i)
/-! ### Smoothness, distance and the tilted expectation of Lemma 6.5 (§6.2, printed pp. 26–27 /
PDF pp. 27–28) -/
/-- `μ` is `δ`-smooth: `Pr_{v∼μ}[⟨z, v⟩ ≠ 0] ≥ δ` for every `z ≠ 0`, and when `q = 2` also
`Pr_{v∼μ}[⟨z, v⟩ = 0] ≥ δ`. -/
def IsSmooth {m : ℕ} (δ : ℝ) (μ : (Fin m → F) → ℝ) : Prop :=
∀ z : Fin m → F, z ≠ 0 →
δ ≤ prob μ (fun v => z ⬝ᵥ v ≠ 0) ∧
(Fintype.card F = 2 → δ ≤ prob μ (fun v => z ⬝ᵥ v = 0))
/-- `δ` is `δ_τ`, the largest `δ` for which `τ` is `δ`-smooth. -/
def IsSmoothnessConst {m : ℕ} (δ : ℝ) (τ : (Fin m → F) → ℝ) : Prop :=
IsSmooth δ τ ∧ ∀ δ' : ℝ, δ < δ' → ¬ IsSmooth δ' τ
/-- `X`: the number of matrices in `F^{n×m}` of type `ν` contained in the code `C`. -/
def typeCount {n m : ℕ} (C : CodingTheory.LinearCode F (Fin n)) (ν : (Fin m → F) → ℝ) : ℕ := by
classical
exact (Finset.univ.filter (fun B : Fin n → Fin m → F => HasType B ν ∧ Contains C B)).card
/-- The event `D_δ`: every nonzero codeword of `C ≤ F^n` has Hamming weight at least `δ n`. -/
def MinWeightAtLeast {n : ℕ} (δ : ℝ) (C : CodingTheory.LinearCode F (Fin n)) : Prop := by
classical
exact ∀ x ∈ C, x ≠ 0 → δ * (n : ℝ) ≤ (hammingNorm x : ℝ)
end SilasListCapacity.Main.Supplement