ErrorCorrectingCodes.Codeword.exists_listDecodable_code
Existence of list-decodable codes. Let $\alpha$ be a finite field, and fix natural numbers $n$, $L$, $M$ and a real number $p$ with $0 \le p \le 1$, $1 \le L$, $L < M$, and $M \le \abs{\alpha}^n$. Suppose $V$ is a natural number bounding the volume of every Hamming ball of radius $\lfloor pn\rfloor$, in the sense that each such ball around an arbitrary word $y \in \alpha^n$ contains at most $V$ codewords, and suppose that \[ \abs{\alpha}^n \cdot \binom{V}{L+1} \cdot \binom{\abs{\alpha}^n - (L+1)}{\,M-(L+1)\,} \;<\; \binom{\abs{\alpha}^n}{M}. \] Then there exists a code $C$ of length $n$ over $\alpha$ consisting of exactly $M$ codewords that is $(p,L)$-list-decodable.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in set_option linter.unusedSectionVars false in open Set Filter Asymptotics Finset in variable {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] in variable {n k : ℕ} in lemma ErrorCorrectingCodes.Codeword.exists_listDecodable_code (n L M : ℕ) (p : ℝ) (hp1 : 0 ≤ p) (hp2 : p ≤ 1) (hL : 1 ≤ L) (V : ℕ) (hV : ∀ y : Codeword n α, (hamming_ball (Nat.floor (p*n)) y).card ≤ V) (h_ineq : (Fintype.card α)^n * (Nat.choose V (L+1)) * (Nat.choose ((Fintype.card α)^n - (L+1)) (M - (L+1))) < Nat.choose ((Fintype.card α)^n) M) (hM_le_N : M ≤ (Fintype.card α)^n) (hL_lt_M : L < M) : ∃ C : Code n α, C.card = M ∧ list_decodable p hp1 hp2 n L hL C
- Source
- TCSlib, `ErrorCorrectingCodes.Codeword.exists_listDecodable_code`
- 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.exists_listDecodable_code← ErrorCorrectingCodes.Codeword.exists_listDecodable_code (TCSlib/ErrorCorrectingCodes/ListDecoding.lean:50): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.CodeA (block) code of length $n$ over $\alpha$ is a finite set (
Finset) of codewords. - ErrorCorrectingCodes.CodewordA codeword of length $n$ over alphabet $\alpha$ is a function $c : \mathrm{Fin}\,n \to \alpha$.
- ErrorCorrectingCodes.Codeword.hamming_ballThe Hamming ball of radius $l$ around $c$: \[ B_l(c) = \{c' : d(c',c) \le l\}, \] implemented as a
Finset.
- Used by 1
- ErrorCorrectingCodes.Codeword.list_decoding_capacityList-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…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inset_option linter.unusedSectionVars false inopen Set Filter Asymptotics Finset invariable {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] invariable {n k : ℕ} in/-- **Existence of list-decodable codes**: if the ball volume `V` and code size `M` satisfy the given counting inequality, then there exists a code `C` of size `M` that is `(p, L)`-list-decodable. -/lemma ErrorCorrectingCodes.Codeword.exists_listDecodable_code (n L M : ℕ) (p : ℝ) (hp1 : 0 ≤ p) (hp2 : p ≤ 1) (hL : 1 ≤ L) (V : ℕ) (hV : ∀ y : Codeword n α, (hamming_ball (Nat.floor (p*n)) y).card ≤ V) (h_ineq : (Fintype.card α)^n * (Nat.choose V (L+1)) * (Nat.choose ((Fintype.card α)^n - (L+1)) (M - (L+1))) < Nat.choose ((Fintype.card α)^n) M) (hM_le_N : M ≤ (Fintype.card α)^n) (hL_lt_M : L < M) : ∃ C : Code n α, C.card = M ∧ list_decodable p hp1 hp2 n L hL C := by contrapose h_ineq; have h_bad_codes : ∀ y : Codeword n α, (Finset.filter (fun C => (Finset.filter (fun c => c ∈ C) (hamming_ball ⌊p * n⌋₊ y)).card ≥ L + 1) (Finset.powersetCard M (Finset.univ : Finset (Codeword n α)))).card ≤ Nat.choose V (L + 1) * Nat.choose ((Fintype.card α) ^ n - (L + 1)) (M - (L + 1)) := by intro y have h_bad_codes_y : (Finset.filter (fun C => (Finset.filter (fun c => c ∈ C) (hamming_ball ⌊p * n⌋₊ y)).card ≥ L + 1) (Finset.powersetCard M (Finset.univ : Finset (Codeword n α)))).card ≤ (Finset.powersetCard (L + 1) (hamming_ball ⌊p * n⌋₊ y)).card * Nat.choose ((Fintype.card α) ^ n - (L + 1)) (M - (L + 1)) := by refine' le_trans ( Finset.card_le_card _ ) _; exact Finset.biUnion ( Finset.powersetCard ( L + 1 ) ( hamming_ball ⌊p * n⌋₊ y ) ) fun S => Finset.image ( fun T => S ∪ T ) ( Finset.powersetCard ( M - ( L + 1 ) ) ( Finset.univ \ S ) ); · intro C hC; simp_all +decide [ Finset.subset_iff ] ; obtain ⟨ S, hS ⟩ := Finset.exists_subset_card_eq hC.2; refine' ⟨ S, ⟨ fun x hx => _, hS.2 ⟩, C \ S, ⟨ fun x hx => _, _ ⟩, _ ⟩ <;> simp_all +decide [ Finset.subset_iff ]; grind; · refine' le_trans ( Finset.card_biUnion_le ) _; refine' le_trans ( Finset.sum_le_sum fun x hx => Finset.card_image_le ) _; simp +decide [ Finset.card_sdiff ]; refine' le_trans ( Finset.sum_le_sum fun x hx => Nat.choose_le_choose _ _ ) _; rotate_left; use fun x => Fintype.card α ^ n - ( L + 1 ); · simp +decide [ Finset.card_powersetCard ]; · grind; refine' le_trans h_bad_codes_y _; exact Nat.mul_le_mul_right _ ( by rw [ Finset.card_powersetCard ] ; exact Nat.choose_le_choose _ ( hV y ) ); have h_bad_codes_count : (Finset.filter (fun C => ∃ y : Codeword n α, (Finset.filter (fun c => c ∈ C) (hamming_ball ⌊p * n⌋₊ y)).card ≥ L + 1) (Finset.powersetCard M (Finset.univ : Finset (Codeword n α)))).card ≤ (Fintype.card α) ^ n * Nat.choose V (L + 1) * Nat.choose ((Fintype.card α) ^ n - (L + 1)) (M - (L + 1)) := by have h_bad_codes_count : (Finset.filter (fun C => ∃ y : Codeword n α, (Finset.filter (fun c => c ∈ C) (hamming_ball ⌊p * n⌋₊ y)).card ≥ L + 1) (Finset.powersetCard M (Finset.univ : Finset (Codeword n α)))).card ≤ (∑ y : Codeword n α, (Finset.filter (fun C => (Finset.filter (fun c => c ∈ C) (hamming_ball ⌊p * n⌋₊ y)).card ≥ L + 1) (Finset.powersetCard M (Finset.univ : Finset (Codeword n α)))).card) := by have h_bad_codes_count : (Finset.filter (fun C => ∃ y : Codeword n α, (Finset.filter (fun c => c ∈ C) (hamming_ball ⌊p * n⌋₊ y)).card ≥ L + 1) (Finset.powersetCard M (Finset.univ : Finset (Codeword n α)))).card ≤ (Finset.biUnion (Finset.univ : Finset (Codeword n α)) (fun y => Finset.filter (fun C => (Finset.filter (fun c => c ∈ C) (hamming_ball ⌊p * n⌋₊ y)).card ≥ L + 1) (Finset.powersetCard M (Finset.univ : Finset (Codeword n α))))).card := by exact Finset.card_le_card fun x hx => by aesop; exact h_bad_codes_count.trans ( Finset.card_biUnion_le ); refine' le_trans h_bad_codes_count ( le_trans ( Finset.sum_le_sum fun _ _ => h_bad_codes _ ) _ ); simp +decide [ mul_assoc, Fintype.card_pi ]; simp_all +decide [ list_decodable ]; refine' le_trans _ h_bad_codes_count; rw [ Finset.filter_true_of_mem ]; · simp +decide [ Finset.card_univ ]; · intro C hC; specialize h_ineq C; aesop;