AFTD Auto-Formalizing Theoretical Domains

ErrorCorrectingCodes.Codeword.dist_le_length

theoremverifiedimported Lean

Minimum distance is at most the block length. Let $C$ be a code of length $n$ over an alphabet $\alpha$ — that is, a finite set of codewords, each a function $\mathrm{Fin}\,n \to \alpha$ — and let $d$ be a natural number that is the minimum distance of $C$: there exist two distinct codewords of $C$ at Hamming distance exactly $d$, and every pair of distinct codewords of $C$ is at Hamming distance at least $d$. Then $d \le n$.

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.dist_le_length (C : Code n α) (d : ℕ) (h : distance C d) : d ≤ n
Source
TCSlib, `ErrorCorrectingCodes.Codeword.dist_le_length`
Lean proof
By Allan Li, Hydroxyi (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
Classical.choiceQuot.soundpropext
Built on 3
Used by 2

Lean source view module on GitHub

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/-- The minimum distance of a code is at most the block length. -/lemma ErrorCorrectingCodes.Codeword.dist_le_length (C : Code n α) (d : ℕ) (h : distance C d) : d ≤ n := by  rcases h with ⟨h1, _⟩  rcases h1 with ⟨c₁, ⟨_, ⟨c₂, ⟨_, ⟨_, hdeq⟩⟩⟩⟩⟩  have hle : hammingDist c₁ c₂ ≤ n :=    calc      hammingDist c₁ c₂ ≤ Fintype.card (Fin n) := by exact hammingDist_le_card_fintype      _                 = n                    := by rel[Fintype.card_fin n]  dsimp [hamming_distance] at hdeq  rw [hdeq] at hle  exact hle
See it in the graphDiscuss this resultChallenge it