AFTD Auto-Formalizing Theoretical Domains

ErrorCorrectingCodes.Codeword.hamming_bound

theoremverifiedformalizationimported Lean

Hamming (sphere-packing) bound. Let $\alpha$ be a finite alphabet with $q = \abs{\alpha} > 1$ symbols, and let $C \subseteq \alpha^n$ be a code (a finite set of length-$n$ codewords) whose minimum Hamming distance is $d$, with $d > 0$. Then \[ \abs{C} \;\le\; \frac{q^{\,n}}{\displaystyle\sum_{i=0}^{\lfloor (d-1)/2 \rfloor} \binom{n}{i}\,(q-1)^{i}}. \]

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.hamming_bound (n d : ℕ) (C : Code n α) (h : distance C d) (h'' : Fintype.card α > 1)
    (hd : 0 < d) :
    C.card ≤ Fintype.card α ^ n /
      (Finset.sum (Finset.range ((Nat.floor (((d : ℝ)-1)/2)) + 1))
        (λ i => Nat.choose n i * (Fintype.card α - 1)^i))
Formalizes
Hamming (sphere-packing) bound, as formalized in TCSlib (`ErrorCorrectingCodes.Codeword.hamming_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
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12

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
/-- **Hamming bound** (sphere-packing bound): a code `C` of block-length `n` and minimum distance `d` over an alphabet `α` with `|α| > 1` satisfies `|C| ≤ |α|^n / Vol(n, ⌊(d-1)/2⌋)`. -/
theorem ErrorCorrectingCodes.Codeword.hamming_bound (n d : ℕ) (C : Code n α) (h : distance C d) (h'' : Fintype.card α > 1)
    (hd : 0 < d) :
    C.card ≤ Fintype.card α ^ n /
      (Finset.sum (Finset.range ((Nat.floor (((d : ℝ)-1)/2)) + 1))
        (λ i => Nat.choose n i * (Fintype.card α - 1)^i)) := by {
  have h1 : 0 < Finset.sum (Finset.range ((Nat.floor (((d : ℝ)-1)/2)) + 1)) (λ i=> Nat.choose n i * (Fintype.card α - 1)^i) := by
    apply Finset.sum_pos
    intros i hi
    apply mul_pos
    · apply Nat.choose_pos
      have : (Nat.floor (((d : ℝ)-1)/2)) + 1 ≤ d := by
        suffices (Nat.floor (((d : ℝ)-1)/2)) ≤ d - 1 by exact Nat.add_le_of_le_sub hd this
        suffices (Nat.floor (((d : ℝ)-1)/2)) ≤ ((d - (1 : ℕ) ) : ℝ) by{
          rw[← Nat.cast_sub] at this
          exact Nat.cast_le.1 this
          exact hd
        }
        calc
          (Nat.floor (((d : ℝ)-1)/2)) ≤ ((d : ℝ)-1)/2        := by {
            apply Nat.floor_le
            apply div_nonneg
            simp
            exact hd
            linarith
          }
          _                           ≤ ((d - (1 : ℕ) ) : ℝ) := by {
            simp
            linarith
          }
      calc
        i ≤ ((Nat.floor (((d : ℝ)-1)/2)) + 1)  := by linarith [Finset.mem_range.1 hi]
        _ ≤ d  := by exact this
        _ ≤ n  := by exact dist_le_length C d h
    · apply Nat.pow_pos
      simp
      exact h''
    simp


  suffices C.card * (Finset.sum (Finset.range ((Nat.floor (((d : ℝ)-1)/2)) + 1)) (λ i=> Nat.choose n i * (Fintype.card α - 1)^i)) ≤ Fintype.card α ^ n by exact (Nat.le_div_iff_mul_le h1).mpr this

  let S : Finset (Codeword n α) := Finset.univ
  have h_Scard: S.card = Fintype.card α ^ n := by simp[S]

  have h_disjoint : (C : Set (Codeword n α)).PairwiseDisjoint (fun c ↦ (hamming_ball (Nat.floor (((d:ℝ)-1)/2)) c)) := by
    intros x hx y hy hxy
    simp at hx hy
    exact hamming_ball'_disjoint C h hd x y ⟨hx, hy, hxy⟩

  let SU : Finset (Codeword n α) := Finset.disjiUnion C (fun c ↦ (hamming_ball (Nat.floor (((d:ℝ)-1)/2)) c)) h_disjoint


  have h_SUcard : SU.card = C.card * (Finset.sum (Finset.range ((Nat.floor (((d : ℝ)-1)/2)) + 1)) (λ i=> Nat.choose n i * (Fintype.card α - 1)^i)) := by
    rw[Finset.card_disjiUnion]
    apply Finset.sum_eq_card_nsmul
    exact fun a _ => hamming_ball_size n (Nat.floor (((d : ℝ)-1)/2)) a

  calc
    (C.card * Finset.sum (Finset.range ((Nat.floor (((d : ℝ)-1)/2)) + 1)) fun i => Nat.choose n i * (Fintype.card α - 1) ^ i) = SU.card := by exact h_SUcard.symm
    _                                                                                                            ≤ S.card  := by exact Finset.card_le_univ SU
    _                                                                                                            = Fintype.card α ^ n   := by exact h_Scard


}
See it in the graphDiscuss this resultChallenge it