AFTD Auto-Formalizing Theoretical Domains

ErrorCorrectingCodes.Codeword.hamming_ball_size

theoremverifiedimported Lean

Cardinality of Hamming balls. Let $\alpha$ be a finite alphabet, and regard a codeword of length $n$ as a function $\mathrm{Fin}\,n \to \alpha$, with the Hamming distance $d(x,y)$ counting the coordinates in which two codewords differ. For every radius $l$ and every center codeword $c$, the Hamming ball $B_l(c) = \{c' : d(c',c) \le l\}$ has cardinality \[ \abs{B_l(c)} \;=\; \sum_{i=0}^{l} \binom{n}{i}\,(\abs{\alpha}-1)^{i}, \] where $\abs{\alpha}$ is the number of symbols in the alphabet.

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_ball_size (n l : ℕ) :
    ∀ c : Codeword n α,
      (hamming_ball l c).card =
        Finset.sum (Finset.range (l + 1)) (λ i => Nat.choose n i * (Fintype.card α - 1)^i)
Source
TCSlib, `ErrorCorrectingCodes.Codeword.hamming_ball_size`
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.
What was changed in ErrorCorrectingCodes.Codeword.hamming_ball_size
--- TCSlib/ErrorCorrectingCodes/HammingBound.lean:35 (ErrorCorrectingCodes.Codeword.hamming_ball_size)
+++ as compiled here
@@ -1,4 +1,9 @@
-/-- **Volume formula**: the Hamming ball of radius `l` centred at any codeword has exactly
-    `Σ_{i=0}^{l} C(n,i) · (|α|-1)^i` elements. -/
-theorem hamming_ball_size (n l : ℕ) :
+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_ball_size (n l : ℕ) :
     ∀ c : Codeword n α,
@@ -19,4 +24,4 @@
     have h_card_α_nonzero : α_nonzero.card = Fintype.card α - 1 := by
-      rw [toFinset_card]
-      simp
+      have h0 : α_nonzero = Finset.univ.erase 0 := by ext x; simp [α_nonzero]
+      rw [h0, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ]
 
@@ -52,24 +57,15 @@
       apply Finset.mem_sigma.1 at ha
-      rw[toFinset]
-      simp [hammingDist]
-      have : (filter (fun i => i ∈ a.fst) Finset.univ).card = d := by
+      rw [Set.mem_toFinset, Set.mem_setOf_eq]
+      have hcard : (Finset.univ.filter (fun i => i ∈ a.fst)).card = d := by
         simpa [d_comb] using ha.1
-      rw[← this]
-      rw[← Fintype.card_subtype]
-      apply Fintype.card_of_subtype
-      simp
-      intros x
-      constructor
-      · intro hx
-        push_neg
-        refine dite_ne_right_iff.mpr ?_
-        use hx
-        have : ↑(a.snd ⟨x, hx⟩) ∈  α_nonzero := by
-          exact coe_mem (Sigma.snd a { val := x, property := hx })
-        simp[α_nonzero] at this
-        exact this
-      · intros hx
-        simp[f'] at hx
-        rcases hx with ⟨h₁, h₂⟩
-        exact h₁
+      rw [← hcard]
+      unfold hammingDist
+      congr 1
+      ext x
+      simp only [Finset.mem_filter, Finset.mem_univ, true_and]
+      by_cases hx : x ∈ a.fst
+      · have hmem := (a.snd ⟨x, hx⟩).2
+        simp only [α_nonzero, Set.mem_toFinset, Set.mem_setOf_eq] at hmem
+        simp [f', zero, hx, hmem]
+      · simp [f', zero, hx]
 
@@ -137,3 +133,3 @@
         have : Sigma.snd b { val := ↑x, property := (h₃' : ↑x ∈ b.fst) } = b' x := by
-          dsimp[f_b, f']
+          try dsimp[f_b, f']
           apply congr_heq -- Life Saving Theorem
@@ -175,3 +171,5 @@
         have h_setEq : (toFinset {i | ¬b i = 0}) = (filter (fun i => b i ≠ zero i) Finset.univ) := by
-          simp
+          ext i
+          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Set.mem_toFinset, Set.mem_setOf_eq]
+          exact Iff.rfl
         constructor
@@ -181,20 +179,8 @@
       use h_a
-      simp[a₁, a₂, f, f', S, d_comb]
       funext x
-
       by_cases h_x : b x = 0
-      · simp
-        intro h'
-        rw[h_x]
-      · simp
-        intro h'
-        by_contra h_x
-        have h_xb : x ∈ toFinset {i | ¬b i = 0} := by
-          apply Set.mem_toFinset.2
-          simp
-          contrapose h_x
-          simp at h_x
-          simp
-          rw[h_x]
-        (expose_names; exact h_x_1 h')
+      · have hx : x ∉ a₁ := by simp [a₁, h_x]
+        simp [f', hx, h_x]
+      · have hx : x ∈ a₁ := by simp [a₁, h_x]
+        simp [f', hx, a₂]
 
@@ -208,29 +194,19 @@
     rw[← h_card_x0]
-    let f : Codeword n α → Codeword n α := fun x ↦ sub x c
-    apply Finset.card_bij (fun a _ ↦ f a)
-    simp [toFinset]
-    · intros a ha
-      dsimp [hamming_distance, sub] at *
-      rw[hammingDist_eq_hammingNorm] at ha
-      exact ha
-    · intros a b ha hb hfab
-      simp [toFinset] at *
+    apply Finset.card_bij (fun a _ ↦ sub a c)
+    · intro a ha
+      rw [Set.mem_toFinset, Set.mem_setOf_eq] at ha ⊢
+      unfold hamming_distance at ha ⊢
+      rw [← ha, hammingDist_eq_hammingNorm, hammingDist_eq_hammingNorm]
+      congr 1; ext i; simp [sub, zero]; try ring
+    · intro a _ b _ hab
       ext i
-      apply funext_iff.1 at hfab
-      specialize hfab i
-      simp[f] at hfab
-      exact hfab
-    · intros b hb
-      use add b c
-      simp [toFinset, hamming_distance] at *
-      constructor
-      · rw[hammingDist_eq_hammingNorm]
-        have : add b c - c = b := by ext i; simp
-        rw[this]
-        exact hb
-      · ext i
-        simp[f]
-
-
-
+      have := congrFun hab i
+      simpa [sub] using this
+    · intro b hb
+      refine ⟨add b c, ?_, ?_⟩
+      · rw [Set.mem_toFinset, Set.mem_setOf_eq] at hb ⊢
+        unfold hamming_distance at hb ⊢
+        rw [← hb, hammingDist_eq_hammingNorm, hammingDist_eq_hammingNorm]
+        congr 1; ext i; simp [add, zero]
+      · ext i; simp [sub, add]
 
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 2

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
/-- **Volume formula**: the Hamming ball of radius `l` centred at any codeword has exactly `Σ_{i=0}^{l} C(n,i) · (|α|-1)^i` elements. -/
theorem ErrorCorrectingCodes.Codeword.hamming_ball_size (n l : ℕ) :
    ∀ c : Codeword n α,
      (hamming_ball l c).card =
        Finset.sum (Finset.range (l + 1)) (λ i => Nat.choose n i * (Fintype.card α - 1)^i) := by {
  intro c
  simp

  have h_card_x0 : ∀ d, {c' : Codeword n α | hamming_distance c' Codeword.zero = d}.toFinset.card = Nat.choose n d * (Fintype.card α - 1)^d := by
    intro d
    dsimp [hamming_distance, zero]

    let d_comb : Finset (Finset (Fin n)) := Finset.powersetCard d Finset.univ
    have h_card_d_comb : d_comb.card = Nat.choose n d := by
      simp [d_comb]

    let α_nonzero := {x : α | x ≠ 0}.toFinset
    have h_card_α_nonzero : α_nonzero.card = Fintype.card α - 1 := by
      have h0 : α_nonzero = Finset.univ.erase 0 := by ext x; simp [α_nonzero]
      rw [h0, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ]

    have h_card_fun : ∀ s ∈ d_comb, Fintype.card (s → α_nonzero) = (Fintype.card α - 1)^d := by
      intro s hs
      rw [Fintype.card_fun]
      rw [show Fintype.card { x // x ∈ α_nonzero } = Fintype.card α - 1 by
        simpa using h_card_α_nonzero]
      dsimp[d_comb] at hs
      simp! at *
      rw[hs]

    let f := fun (s : Finset (Fin n)) ↦ (Finset.univ : Finset (s → α_nonzero))

    have : ∀ s ∈ d_comb, (f s).card = (Fintype.card α - 1)^d := by intro s hs; exact h_card_fun s hs

    let S := d_comb.sigma f
    have h_card_S : S.card = Nat.choose n d * (Fintype.card α - 1) ^ d := by
      simp [S]
      rw [Finset.sum_eq_card_nsmul this, h_card_d_comb]
      rfl

    rw[←h_card_S]
    let f' : (s : ((k : Finset (Fin n)) × ({ x // x ∈ k } → { x // x ∈ α_nonzero }))) → s ∈ S → Codeword n α := fun s _ ↦ (fun i ↦ if h : i ∈ s.1 then s.2 ⟨i, h⟩ else 0)

    symm
    apply Finset.card_bij f'

    -- f' maps S to the hamming ball
    have h_f'_map_to_ball: ∀ (a : (k : Finset (Fin n)) × ({ x // x ∈ k } → { x // x ∈ α_nonzero })) (ha : a ∈ S), f' a ha ∈ toFinset {c' | hammingDist c' zero = d} := by
      intros a ha
      dsimp[S] at ha
      apply Finset.mem_sigma.1 at ha
      rw [Set.mem_toFinset, Set.mem_setOf_eq]
      have hcard : (Finset.univ.filter (fun i => i ∈ a.fst)).card = d := by
        simpa [d_comb] using ha.1
      rw [← hcard]
      unfold hammingDist
      congr 1
      ext x
      simp only [Finset.mem_filter, Finset.mem_univ, true_and]
      by_cases hx : x ∈ a.fst
      · have hmem := (a.snd ⟨x, hx⟩).2
        simp only [α_nonzero, Set.mem_toFinset, Set.mem_setOf_eq] at hmem
        simp [f', zero, hx, hmem]
      · simp [f', zero, hx]

    exact h_f'_map_to_ball

    -- f' is injective
    have h_f'_injective: ∀ (a : (k : Finset (Fin n)) × ({ x // x ∈ k } → { x // x ∈ α_nonzero })) (ha : a ∈ S),
     ∀ (b : (k : Finset (Fin n)) × ({ x // x ∈ k } → { x // x ∈ α_nonzero })) (hb : b ∈ S), f' a ha = f' b hb → a = b := by
      intros a h_a b h_b
      intro h_feq
      let f_a := (f' a h_a)
      let f_b := (f' b h_b)
      have fab_eq: f_a = f_b := by exact h_feq

      have first_eq: a.1 = b.1 := by
        ext x
        constructor
        · intro h1
          by_contra h_xb
          have h_fbzero: f_b x = 0 := by simp[f_b, f']; intro h_inb; exact absurd h_inb h_xb
          have h_fazero: f_a x = 0 := by rw[fab_eq]; exact h_fbzero
          dsimp[f_a, f'] at h_fazero; simp at h_fazero
          let a₀ := a.2 ⟨x, h1⟩
          apply h_fazero at h1
          have h_azero : ¬a₀.val ≠ 0 := by simp; exact h1
          have h_anonzero : a₀.val ∈ α_nonzero := by exact a₀.property
          rw [Set.mem_toFinset, Set.mem_setOf] at h_anonzero
          exact absurd h_anonzero h_azero
        · intro h2
          by_contra h_xa
          have h_fazero: f_a x = 0 := by simp[f_a, f']; intro h_ina; exact absurd h_ina h_xa
          have h_fbzero: f_b x = 0 := by rw[←fab_eq]; exact h_fazero
          dsimp[f_b, f'] at h_fbzero; simp at h_fbzero
          let b₀ := b.2 ⟨x, h2⟩
          apply h_fbzero at h2
          have h_bzero : ¬b₀.val ≠ 0 := by simp; exact h2
          have h_bnonzero : b₀.val ∈ α_nonzero := by exact b₀.property
          rw [Set.mem_toFinset, Set.mem_setOf] at h_bnonzero
          exact absurd h_bnonzero h_bzero

      have h_2eq : ({ x // x ∈ b.fst } → { x // x ∈ α_nonzero }) = ({ x // x ∈ a.fst } → { x // x ∈ α_nonzero }) := by rw[first_eq]

      let b' := cast h_2eq b.2
      have h_bheq : HEq b' b.2 := by simp[b']

      ext
      rw[first_eq]
      refine HEq.symm (heq_of_cast_eq h_2eq ?h_f'_injective.a.x)
      funext x
      suffices b' x = a.snd x by {
        exact this
      }

      have h₁' : f_a x = a.2 x := by
        simp [f_a, f']
      have h₂ : (f_a x) = (f_b x) := by rw[fab_eq]
      have h₃ : (f_b x) = (b' x) := by
        dsimp[f_b, f']
        have h₃' : ↑x ∈ b.1 := by
          have h₃'' : ↑x ∈ a.1 := by simp
          rw[← first_eq]
          exact h₃''
        simp[h₃']

        have : Sigma.snd b { val := ↑x, property := (h₃' : ↑x ∈ b.fst) } = b' x := by
          try dsimp[f_b, f']
          apply congr_heq -- Life Saving Theorem
          exact h_bheq.symm
          refine (Subtype.heq_iff_coe_eq ?this.h₂.h).mpr rfl
          rw[first_eq]
          tauto
        exact this


      rw[h₃] at h₂
      rw[h₂] at h₁'
      exact SetCoe.ext h₁'

    exact h_f'_injective

    -- f' is surjective
    have h_f'_surjective: ∀ b ∈ toFinset {c' | hammingDist c' zero = d}, ∃ a, ∃ (ha : a ∈ S), f' a ha = b := by
      intro b
      intro h_b
      let a₁ := toFinset { i | b i ≠ 0 }

      have h_y : ∀ y ∈ a₁, (b ↑y) ∈ α_nonzero := by
        intro y hy
        simp [α_nonzero, a₁] at hy ⊢
        exact hy

      let a₂ (y : { x // x ∈ a₁ }) : { x // x ∈ α_nonzero } := ⟨b y, by {
        apply h_y
        exact y.property
      }⟩

      use ⟨a₁, a₂⟩

      have h_a : ⟨a₁, a₂⟩ ∈ S := by
        simp[a₁, a₂, S, d_comb]
        have h_d : hammingDist b zero = d := by rw[Set.mem_toFinset, Set.mem_setOf] at h_b; exact h_b
        unfold hammingDist at h_d
        have h_setEq : (toFinset {i | ¬b i = 0}) = (filter (fun i => b i ≠ zero i) Finset.univ) := by
          ext i
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Set.mem_toFinset, Set.mem_setOf_eq]
          exact Iff.rfl
        constructor
        · exact h_d
        · simp[f]

      use h_a
      funext x
      by_cases h_x : b x = 0
      · have hx : x ∉ a₁ := by simp [a₁, h_x]
        simp [f', hx, h_x]
      · have hx : x ∈ a₁ := by simp [a₁, h_x]
        simp [f', hx, a₂]

    exact h_f'_surjective




  have h_card_dist_eq : ∀ d, {c' : Codeword n α | hamming_distance c' c = d}.toFinset.card = Nat.choose n d * (Fintype.card α - 1)^d := by
    intro d
    rw[← h_card_x0]
    apply Finset.card_bij (fun a _ ↦ sub a c)
    · intro a ha
      rw [Set.mem_toFinset, Set.mem_setOf_eq] at ha ⊢
      unfold hamming_distance at ha ⊢
      rw [← ha, hammingDist_eq_hammingNorm, hammingDist_eq_hammingNorm]
      congr 1; ext i; simp [sub, zero]; try ring
    · intro a _ b _ hab
      ext i
      have := congrFun hab i
      simpa [sub] using this
    · intro b hb
      refine ⟨add b c, ?_, ?_⟩
      · rw [Set.mem_toFinset, Set.mem_setOf_eq] at hb ⊢
        unfold hamming_distance at hb ⊢
        rw [← hb, hammingDist_eq_hammingNorm, hammingDist_eq_hammingNorm]
        congr 1; ext i; simp [add, zero]
      · ext i; simp [sub, add]

  induction l
  · simp [hamming_distance]
    refine (Fintype.existsUnique_iff_card_one fun x => x = c).mp ?_
    simp
  · expose_names

    rw[Nat.succ_add]
    rw[Finset.sum_range_succ]
    rw[← h]

    have : Fintype.card { x // hamming_distance x c ≤n_1+ 1 } = Fintype.card { x // hamming_distance x c ≤n_1} + Fintype.card { x // hamming_distance x c = n_1 + 1} := by
      have : fun x ↦ hamming_distance x c ≤ n_1 + 1 = fun x ↦ hamming_distance x c ≤ n_1 ∨ hamming_distance x c = n_1 + 1 := by
        ext x
        constructor
        · intros h_d1
          apply Nat.eq_or_lt_of_le at h_d1
          rcases h_d1 with hl | hr
          right
          exact hl
          left
          linarith
        · intros h_or
          rcases h_or with hl | hr
          linarith
          linarith

      have : {x // hamming_distance x c ≤ n_1 + 1} = {x // hamming_distance x c ≤ n_1 ∨ hamming_distance x c = n_1 + 1 } := by exact congrArg Subtype this

      have : Fintype.card {x // hamming_distance x c ≤ n_1 + 1} = Fintype.card {x // hamming_distance x c ≤ n_1 ∨ hamming_distance x c = n_1 + 1 } := by exact Fintype.card_congr' this

      rw[this]

      have : Disjoint (fun x ↦ hamming_distance x c ≤ n_1)  (fun x ↦ hamming_distance x c = n_1 + 1) := by
        apply Pi.disjoint_iff.2
        intros c'
        simp
        intro hc'
        linarith

      apply Fintype.card_subtype_or_disjoint
      exact this

    rw[Fintype.card_subtype, Fintype.card_subtype, Fintype.card_subtype] at this
    rw[this]
    simp
    have : {c' : Codeword n α | hamming_distance c' c = n_1 + 1}.toFinset.card = Nat.choose n (n_1 + 1) * (Fintype.card α - 1)^(n_1 + 1) := by exact h_card_dist_eq (n_1 + 1)
    simp at this
    linarith
}
See it in the graphDiscuss this resultChallenge it