AFTD Auto-Formalizing Theoretical Domains

ErrorCorrectingCodes.Codeword.singleton_bound

theoremverifiedformalizationimported Lean

Let $\alpha$ be a finite alphabet with at least two symbols, and let $C$ be a code of length $n$ over $\alpha$ — that is, a finite set of codewords $c : \mathrm{Fin}\,n \to \alpha$. Suppose $C$ has minimum distance $d$, meaning that some two distinct codewords of $C$ are at Hamming distance exactly $d$ and no two distinct codewords are at distance less than $d$. Then \[ \abs{C} \;\le\; \abs{\alpha}^{\,n-d+1}. \]

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
set_option linter.unusedSectionVars false in
set_option linter.unusedVariables false in
open Set Filter Asymptotics Finset in
variable {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] in
variable {n k : ℕ} in
theorem ErrorCorrectingCodes.Codeword.singleton_bound (C : Code n α) (d : ℕ) (h : distance C d) (hα : Nontrivial α) :
    C.card ≤ (Fintype.card α)^(n - d + 1)
Formalizes
Singleton bound, as formalized in TCSlib (`ErrorCorrectingCodes.Codeword.singleton_bound`)
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
Classical.choiceQuot.soundpropext
Built on 5

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inset_option linter.unusedSectionVars false inset_option linter.unusedVariables false inopen Set Filter Asymptotics Finset invariable {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] invariable {n k : ℕ} in/-- **Singleton bound**: every code of block-length `n` and minimum distance `d` has at most `|α|^(n - d + 1)` codewords. Proof sketch: project each codeword onto its first `n - d + 1` coordinates. Two distinct codewords in `C` must have distinct projections (otherwise their distance would be less than `d`), so `|C|` is at most the number of possible projections. -/theorem ErrorCorrectingCodes.Codeword.singleton_bound (C : Code n α) (d : ℕ) (h : distance C d) (hα : Nontrivial α) :    C.card ≤ (Fintype.card α)^(n - d + 1) := by {  by_cases h01: C.card = 0 ∨ C.card = 1  · rcases h01 with h0|h1    · rw[h0]      exact Nat.zero_le (Fintype.card α ^ (n - d + 1))    · rw[h1]      have hcard : 0 < Fintype.card α := by exact Fintype.card_pos      have h' : n-d+1 >=1 := by linarith      exact Nat.one_le_pow (n-d+1) (Fintype.card α) (hcard)  by_contra h'  push_neg at h' h01  have h_two_le_card_C: 1 < C.card := by exact (Nat.two_le_iff C.card).mpr h01  have h_dist_le_length : d <= n := by exact dist_le_length C d h  have h_one_le_d : 1 <= d := by    by_contra h_d_le_one    push_neg at h_d_le_one    apply Nat.lt_one_iff.1 at h_d_le_one    rcases h.1 with ⟨c₁, ⟨_, ⟨c₂, ⟨_, ⟨hneq, hdzero⟩⟩⟩⟩⟩    rw[h_d_le_one] at hdzero    dsimp [hamming_distance]at hdzero    symm at hdzero    apply hamming_zero_eq_dist.1 at hdzero    tauto  have h_n_gt_one : 1 <= n := by    calc      n >= d := by exact dist_le_length C d h      _ >= 1 := by exact h_one_le_d  have hle : n - d + 1 <= n := by{    calc      n - d + 1 <= n - 1 + 1 := by rel[h_one_le_d]              _  = n         := by exact Nat.sub_add_cancel h_n_gt_one  }  obtain ⟨_, h_hd_gt⟩ := h  change Finset (Codeword n α) at C  let f : Codeword n α → Codeword (n-d+1) α := fun c ↦ (fun i ↦ c ((Fin.castLE hle) i))  let K : (Finset (Codeword (n-d+1) α)) := Finset.univ  have h_f_to_K : ∀ c ∈ C, f c ∈ K := by intros c _ ; exact Finset.mem_univ (f c)  have h_Kcard: K.card = Fintype.card α ^ (n- d + 1) := by    rw [Finset.card_univ, Fintype.card_fun, Fintype.card_fin]  rw[← h_Kcard] at h'  rcases Finset.exists_ne_map_eq_of_card_lt_of_maps_to h' h_f_to_K with ⟨c₁, ⟨hc₁_mem, ⟨c₂,⟨hc₂_mem, ⟨hc₁₂_neq, hc₁₂feq⟩⟩⟩⟩⟩  change (fun i => c₁ (Fin.castLE hle i)) = fun i => c₂ (Fin.castLE hle i) at hc₁₂feq  have hc₁₂feq' := funext_iff.mp hc₁₂feq  specialize h_hd_gt c₁ hc₁_mem c₂ hc₂_mem hc₁₂_neq  have h_card_complement : (filter (fun i => c₁ i = c₂ i) Finset.univ).card +  (filter (fun i => ¬c₁ i = c₂ i) Finset.univ).card = n := by    dsimp[Finset.card]    rw[← Multiset.card_add (Multiset.filter (fun i => c₁ i = c₂ i) Finset.univ.val) (Multiset.filter (fun i => ¬c₁ i = c₂ i) Finset.univ.val)]    rw[Multiset.filter_add_not (fun i => c₁ i = c₂ i) Finset.univ.val]    simp  have h_card_eq_ge_d : (filter (fun i => c₁ i = c₂ i) Finset.univ).card >= n - d + 1 := by    let S₁ : Finset (Fin n) := filter (fun i => i < n - d +1) Finset.univ    have h_S_disj : Disjoint S₁ S₁ᶜ := by exact disjoint_compl_right    rw [← Finset.union_compl S₁]    rw [Finset.filter_union]    have h_filter_disj : Disjoint (filter (fun i => c₁ i = c₂ i) S₁) (filter (fun i => c₁ i = c₂ i) S₁ᶜ) := by exact disjoint_filter_filter h_S_disj    rw[Finset.card_union_eq_card_add_card.2 h_filter_disj]    have h_filter_eq_S₁ : filter (fun i => c₁ i = c₂ i) S₁ = S₁ := by      ext i      constructor      · exact fun a => mem_of_mem_filter i a      · intro hi        refine Finset.mem_filter.mpr ?_        constructor        · exact hi        · have hi' : i < n - d + 1 := by            simpa [S₁] using hi          have h_cast_eq : i = Fin.castLE hle (i.castLT hi') := by            ext            rfl          specialize hc₁₂feq' (Fin.castLT i hi')          rw [h_cast_eq]          exact hc₁₂feq'    have h_Scard : S₁.card = n - d + 1 := by      apply Finset.card_eq_of_equiv_fin      apply Fintype.equivFinOfCardEq      simpa [S₁] using Fintype.card_fin_lt_of_le hle    rw[h_filter_eq_S₁]    rw[h_Scard]    exact Nat.le_add_right _ _  have h_hd_lt_d : hamming_distance c₁ c₂ < d := by    dsimp [hamming_distance, hammingDist]    calc      (filter (fun i => ¬c₁ i = c₂ i) Finset.univ).card = (filter (fun i => c₁ i = c₂ i) Finset.univ).card                                                          + (filter (fun i => ¬c₁ i = c₂ i) Finset.univ).card                                                          - (filter (fun i => c₁ i = c₂ i) Finset.univ).card  := by exact (Nat.add_sub_cancel_left (filter (fun i => c₁ i = c₂ i) Finset.univ).card (filter (fun i => ¬c₁ i = c₂ i) Finset.univ).card).symm                                                      _ = n - (filter (fun i => c₁ i = c₂ i) Finset.univ).card:= by rw[h_card_complement]                                                      _ <= n - (n - d + 1) := by rel[h_card_eq_ge_d]                                                      _ = n - (n - d) - 1  := by rw[Nat.sub_sub]                                                      _ = d - 1            := by rw[Nat.sub_sub_self h_dist_le_length]                                                      _ < d                := by exact Nat.sub_lt h_one_le_d Nat.zero_lt_one  apply Nat.lt_le_asymm at h_hd_lt_d  tauto}
See it in the graphDiscuss this resultChallenge it