ErrorCorrectingCodes.Codeword.list_decoding_capacity
theoremverifiedformalizationimported Lean
List-decoding over a q-ary alphabet. Let $\alpha$ be a finite field, write $q = \abs{\alpha}$ for the number of its elements, and fix a real number $p$ with $0 < p \le 1 - \tfrac{1}{q}$ together with an integer $L \ge 1$. In this regime one considers block codes over the alphabet $\alpha$ that admit list decoding from a $p$-fraction of symbol errors with output lists of size at most $L$, and the associated rate $r$ they can achieve.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open ErrorCorrectingCodes ErrorCorrectingCodes.Codeword in set_option linter.unusedSectionVars false in open Set Filter Asymptotics Finset in variable {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] in variable {n k : ℕ} in theorem ErrorCorrectingCodes.Codeword.list_decoding_capacity (q : ℕ) (p : ℝ) (hq : q = (Fintype.card α)) (hp : 0 < p ∧ p ≤ 1 - 1/q) (L : ℕ) (hL : 1 ≤ L) : let r := 1 - (qaryEntropy q p) - 1 / (L : ℝ) let M := Nat.floor ((q : ℝ) ^ (r * n)) ∃ C : Code n α, (M ≤ C.card) ∧ list_decodable p (by linarith [hp]) (by linarith [hp, one_div_nonneg.2 (show (0 : ℝ) ≤ (q : ℝ) from by exact_mod_cast (Nat.zero_le q))]) n L hL C
- Formalizes
- List-decoding over a q-ary alphabet, as formalized in TCSlib (`ErrorCorrectingCodes.Codeword.list_decoding_capacity`)
- Lean proof
- By Allan Li (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.ErrorCorrectingCodes.Codeword.list_decoding_capacity← ErrorCorrectingCodes.Codeword.list_decoding_capacity (TCSlib/ErrorCorrectingCodes/ListDecoding.lean:166): verbatim
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 18
- ErrorCorrectingCodes.Codeword.hamming_ball_size_asymptotic_upper_boundEntropy upper bound on Hamming balls. Let $\alpha$ be a finite alphabet with at least two symbols, write $q = \abs{\alpha}$ for its size,…
- ErrorCorrectingCodes.CodewordA codeword of length $n$ over alphabet $\alpha$ is a function $c : \mathrm{Fin}\,n \to \alpha$.
- ErrorCorrectingCodes.Codeword.CodeA (block) code of length $n$ over $\alpha$ is a finite set (
Finset) of codewords. - ErrorCorrectingCodes.Codeword.hamming_ballThe Hamming ball of radius $l$ around $c$: \[ B_l(c) = \{c' : d(c',c) \le l\}, \] implemented as a
Finset. - ErrorCorrectingCodes.Codeword.lt_one_of_le_one_sub_invA rate bound below one. Let $q$ and $p$ be real numbers with $q > 0$. If $p \le 1 - 1/q$, then $p < 1$.
- ErrorCorrectingCodes.Codeword.natCast_one_lt_of_two_leOne is less than a natural number at least two. For any natural number $q$ with $q \ge 2$, the image of $q$ under the canonical embedding…
- ErrorCorrectingCodes.Codeword.natCast_pos_of_two_lePositivity of a natural number at least two. Let $q$ be a natural number with $q \ge 2$. Then its image in the real numbers satisfies…
- ErrorCorrectingCodes.Codeword.qaryEntropy\[ H_q(p) \;=\; p\log_q(q-1) - p\log_q p - (1-p)\log_q(1-p). \]
- ErrorCorrectingCodes.Codeword.qary_entropy_posPositivity of the $q$-ary entropy. Let $\alpha$ be a finite alphabet with $q = \abs{\alpha}$ symbols, and let $p$ be a real number with…
- ErrorCorrectingCodes.Codeword.exists_listDecodable_codeExistence of list-decodable codes. Let $\alpha$ be a finite field, and fix natural numbers $n$, $L$, $M$ and a real number $p$ with…
- ErrorCorrectingCodes.Codeword.listDecoding_counting_ineqCounting inequality for list decoding. Fix an integer alphabet size $q \ge 2$, a real number $p$, and integers $n$ and $L \ge 1$. Set the…
- ErrorCorrectingCodes.Codeword.list_decodableA code $C$ is $(\rho,L)$-list-decodable if every Hamming ball of radius $\lfloor\rho n\rfloor$ contains at most $L$ codewords of $C$.
- ErrorCorrectingCodes.Codeword.addPointwise addition of two codewords.
- ErrorCorrectingCodes.Codeword.subPointwise subtraction of two codewords.
- ErrorCorrectingCodes.Codeword.zeroPointwise addition, subtraction, and the all-zero codeword.
- ErrorCorrectingCodes.Codeword.hamming_distanceHamming distance between two codewords, wrapping Mathlib's
hammingDist. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open ErrorCorrectingCodes ErrorCorrectingCodes.Codeword in set_option linter.unusedSectionVars false in open Set Filter Asymptotics Finset in variable {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] in variable {n k : ℕ} in /-- **List-decoding capacity theorem**: for any `0 < ρ ≤ 1 − 1/q` and `L ≥ 1`, there exist codes of rate `r = 1 − H_q(ρ) − 1/L` that are `(ρ, L)`-list-decodable. In other words, one can list-decode at any rate below the list-decoding capacity `1 − H_q(ρ)` using list size `L`. -/ theorem ErrorCorrectingCodes.Codeword.list_decoding_capacity (q : ℕ) (p : ℝ) (hq : q = (Fintype.card α)) (hp : 0 < p ∧ p ≤ 1 - 1/q) (L : ℕ) (hL : 1 ≤ L) : let r := 1 - (qaryEntropy q p) - 1 / (L : ℝ) let M := Nat.floor ((q : ℝ) ^ (r * n)) ∃ C : Code n α, (M ≤ C.card) ∧ list_decodable p (by linarith [hp]) (by linarith [hp, one_div_nonneg.2 (show (0 : ℝ) ≤ (q : ℝ) from by exact_mod_cast (Nat.zero_le q))]) n L hL C := by classical intro r M have hq2 : 2 ≤ q := by rw [hq] exact Nat.succ_le_iff.mpr (by simpa using Fintype.one_lt_card) have hq_pos : (1 : ℝ) < (q : ℝ) := by exact natCast_one_lt_of_two_le hq2 have hq_ge_0 : (0 : ℝ) ≤ (q : ℝ) := by exact_mod_cast (Nat.zero_le q) have hq_ge_1 : (1 : ℝ) ≤ (q : ℝ) := by linarith have hr : r ≤ 1 := by have hH : 0 < qaryEntropy q p := qary_entropy_pos q p hq hp have hL0 : 0 ≤ 1 / (L : ℝ) := by have : (0 : ℝ) < (L : ℝ) := by exact_mod_cast (lt_of_lt_of_le (Nat.succ_pos 0) hL) exact one_div_nonneg.mpr (le_of_lt this) dsimp [r] linarith have exists_code_card_eq (hM : M ≤ Fintype.card (Codeword n α)) : ∃ C : Code n α, C.card = M := by classical obtain ⟨S, hSsub, hScard⟩ := Finset.exists_subset_card_eq hM (s := (Finset.univ : Finset (Codeword n α))) refine ⟨S, ?_⟩ simpa using hScard by_cases hML : M ≤ L · have hM_le_univ : M ≤ Fintype.card (Codeword n α) := by have : Fintype.card (Codeword n α) = q^n := by simp [Codeword, hq, Fintype.card_pi] have hM_le_qn : M ≤ q^n := by have h_rn : r * (n : ℝ) ≤ (n : ℝ) := by nlinarith [hr] have hpow : (q : ℝ) ^ (r * (n : ℝ)) ≤ (q : ℝ) ^ ((n : ℝ)) := by exact Real.rpow_le_rpow_of_exponent_le hq_ge_1 h_rn have hfloor_le : (M : ℝ) ≤ (q : ℝ) ^ (r * (n : ℝ)) := by simpa using (Nat.floor_le (Real.rpow_nonneg hq_ge_0 (r * (n : ℝ)))) have : (M : ℝ) ≤ (q : ℝ) ^ ((n : ℝ)) := le_trans hfloor_le hpow have : (M : ℝ) ≤ (q^n : ℝ) := by simpa [Real.rpow_natCast] using this exact_mod_cast this simpa [this] using hM_le_qn rcases exists_code_card_eq hM_le_univ with ⟨C, hCcard⟩ refine ⟨C, ?_, ?_⟩ · simp [hCcard] · unfold list_decodable intro y have hleC : (hamming_ball (Nat.floor (p * n)) y ∩ C).card ≤ C.card := by exact Finset.card_le_card (Finset.inter_subset_right) have : (hamming_ball (Nat.floor (p * n)) y ∩ C).card ≤ L := by rw [← hCcard] at hML simpa [hCcard] using le_trans hleC hML exact this · have hL_lt_M : L < M := Nat.lt_of_not_ge hML let N : ℕ := q^n let V : ℕ := Nat.floor (Real.rpow q ((qaryEntropy q p) * n)) have hV_def : V = Nat.floor (Real.rpow q ((qaryEntropy q p) * n)) := by rfl have hM_le : M ≤ q^n := by have h_rn : r * (n : ℝ) ≤ (n : ℝ) := by nlinarith [hr] have hpow : (q : ℝ) ^ (r * (n : ℝ)) ≤ (q : ℝ) ^ ((n : ℝ)) := by exact Real.rpow_le_rpow_of_exponent_le hq_ge_1 h_rn have hfloor_le : (M : ℝ) ≤ (q : ℝ) ^ (r * (n : ℝ)) := by simpa using (Nat.floor_le (Real.rpow_nonneg hq_ge_0 (r * (n : ℝ)))) have : (M : ℝ) ≤ (q : ℝ) ^ ((n : ℝ)) := le_trans hfloor_le hpow have : (M : ℝ) ≤ (q^n : ℝ) := by simpa [Real.rpow_natCast] using this exact_mod_cast this have hM_pos : 0 < M := by linarith have hV_ball : ∀ y : Codeword n α, (hamming_ball (Nat.floor (p * n)) y).card ≤ V := by intro y have hball_real : (hamming_ball (Nat.floor (p * n)) y).card ≤ Real.rpow q (qaryEntropy q p * n) := by have hα : Nontrivial α := inferInstance have hradius : Nat.floor (p * n) = ⌊(n : ℝ) * p⌋₊ := by simp [mul_comm] simpa [hradius] using (hamming_ball_size_asymptotic_upper_bound q n p hq hα hp) y have : ((hamming_ball (Nat.floor (p * n)) y).card : ℝ) ≤ Real.rpow q (qaryEntropy q p * n) := by exact_mod_cast hball_real exact (Nat.le_floor this) have hr_def : r = 1 - (qaryEntropy q p) - 1 / (L : ℝ) := rfl have hM_def : M = Nat.floor ((q : ℝ) ^ (r * n)) := rfl have h_ineq : (q : ℝ)^n * (Nat.choose V (L+1)) * (Nat.choose (q^n - (L+1)) (M - (L+1))) < Nat.choose (q^n) M := by refine listDecoding_counting_ineq q p n L hq2 hL r hr_def M hM_def V hV_def (by exact hM_pos) hM_le hL_lt_M have h_ineq_nat : (Fintype.card α)^n * Nat.choose V (L+1) * Nat.choose ((Fintype.card α)^n - (L+1)) (M - (L+1)) < Nat.choose ((Fintype.card α)^n) M := by have h_ineq_real : ((Fintype.card α)^n : ℝ) * (Nat.choose V (L+1) : ℝ) * (Nat.choose ((Fintype.card α)^n - (L+1)) (M - (L+1)) : ℝ) < (Nat.choose ((Fintype.card α)^n) M : ℝ) := by simpa [Nat.cast_pow, hq] using h_ineq exact_mod_cast h_ineq_real have hp1 : 0 ≤ p := le_of_lt hp.1 have hp2 : p ≤ 1 := by exact le_of_lt (lt_one_of_le_one_sub_inv (natCast_pos_of_two_le hq2) hp.2) obtain ⟨C, hCcard, hCld⟩ := exists_listDecodable_code (n := n) (L := L) (M := M) (p := p) hp1 hp2 hL V hV_ball h_ineq_nat (by simpa [hq] using hM_le) hL_lt_M refine ⟨C, ?_, hCld⟩ simp [hCcard]