Lemma 6.2 — exact formula (10) for the probability that a matrix satisfies one LDPC layer
OpenSilasListCapacity.Main.Supplement.lemma_6_2Let be a finite field, a block size and a multiple of . For a matrix of type , let be the probability that every column of satisfies all parity checks of one random layer (a uniform permutation of into blocks of size , coefficients i.i.d. uniform on ). Let be a law on with whenever , let have independent rows distributed as , independent of the layer, and let be times the type of conditioned on satisfying the layer. Then
- , and
- formula (10) holds:
where is the multinomial coefficient.
Both statements hold for every matrix of type ; in particular depends only on the type. The formula is the starting point of the first- and second-moment computations for the number of matrices of a given type in a random LDPC code (Lemma 6.4, Lemma 6.5).
Formalization Note is layerProb F s B; is written as the row count of in , which equals by the type hypothesis. Conditional probabilities are ratios of the finite sums in the supplement definition.
Differences from the source:
- generalization: s odd (the standing assumption of §6) → any block size s ≥ 1 with s | n; reason: the lemma's statement and proof never use that s is odd; odd s is a special case.
- encoding: nω_a in the exponent and the multinomial coefficient → the number of rows of B equal to a; reason: equal to nω_a by the type hypothesis, and a natural number as an exponent must be.
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
/-- Lemma 6.2 (Silas, STOC 2027 #505, printed p. 26 / PDF p. 27): the probability `p(ω)` that a
matrix of type `ω` satisfies the parity checks of one layer equals
`Pr[Λ satisfies the layer | type Λ = ω]` and is given by formula (10). -/
theorem lemma_6_2 {F : Type*} [Field F] [Fintype F] {n d s : ℕ} (hs : 0 < s) (hsn : s ∣ n)
(ω μ : (Fin d → F) → ℝ) (hμ : IsLaw μ) (hpos : ∀ a, 0 < ω a → 0 < μ a)
(B : Fin n → Fin d → F) (hB : HasType B ω) :
layerProb F s B = satGivenType s μ B ∧
layerProb F s B =
Pd F s μ ^ (n / s) * sMuProb s μ B /
((Nat.multinomial Finset.univ (fun a => rowCount B a) : ℝ) *
∏ a, μ a ^ rowCount B a) := by sorry
end SilasListCapacity.Main.Supplement