AFTD Auto-Formalizing Theoretical Domains

ErrorCorrectingCodes.Codeword.list_decodable

defimported Lean

A code $C$ is $(\rho,L)$-list-decodable if every Hamming ball of radius $\lfloor\rho n\rfloor$ contains at most $L$ codewords of $C$.

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
def ErrorCorrectingCodes.Codeword.list_decodable (ρ : ℝ) (hρ₁: 0 ≤ ρ) (hρ₂: ρ ≤ 1) (n L : ℕ) (hL : L ≥ 1) (C : Code n α) : Prop
Defined in
TCSlib, `ErrorCorrectingCodes.Codeword.list_decodable`
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.
Verified
07 Oct 2026
Axioms
none listed
Built on 3
Used by 2

Lean source view module on GitHub

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
/-- A code `C` is `(ρ, L)`-list-decodable if every Hamming ball of radius `⌊ρn⌋` contains at most `L` codewords of `C`. -/
def ErrorCorrectingCodes.Codeword.list_decodable (ρ : ℝ) (hρ₁: 0 ≤ ρ) (hρ₂: ρ ≤ 1) (n L : ℕ) (hL : L ≥ 1) (C : Code n α) : Prop :=
  (∀ y : Codeword n α, (hamming_ball (Nat.floor (ρ*n)) y ∩ C).card ≤ L)
See it in the graphDiscuss this resultChallenge it