hamming_ball_card_eq_zero
Translation invariance of Hamming ball size. Let alpha be a finite field, and let c be a codeword of length n over alpha. Then for any radius r, the cardinality of the Hamming ball of radius r around c equals the cardinality of the Hamming ball of radius r around the all-zero codeword.
Statement
theorem hamming_ball_card_eq_zero {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] {n : ℕ} (r : ℕ) (c : ErrorCorrectingCodes.Codeword n α) : (ErrorCorrectingCodes.Codeword.hamming_ball r c).card = (ErrorCorrectingCodes.Codeword.hamming_ball r (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α)).card
- Source
- Cover & Thomas, Elements of Information Theory, Ch. 7
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- ErrorCorrectingCodes.Codeword.hamming_ballThe Hamming ball of radius $l$ around $c$: \[ B_l(c) = \{c' : d(c',c) \le l\}, \] implemented as a
Finset. - ErrorCorrectingCodes.Codeword.zeroPointwise addition, subtraction, and the all-zero codeword.
- ErrorCorrectingCodes.Codeword.hamming_distanceHamming distance between two codewords, wrapping Mathlib's
hammingDist. - ErrorCorrectingCodes.CodewordA codeword of length $n$ over alphabet $\alpha$ is a function $c : \mathrm{Fin}\,n \to \alpha$.
- ErrorCorrectingCodes.Codeword.hamming_ballThe Hamming ball of radius $l$ around $c$: \[ B_l(c) = \{c' : d(c',c) \le l\}, \] implemented as a
- Used by 1
- hamming_sphere_packing_boundHamming (sphere-packing) bound. Let alpha be a finite field with at least one element, and let C be a code of length n over alpha with…
Read back from the Lean
For any type α with finite type, nonempty, decidable equality, and field structures, any natural number n, any natural number r, and any codeword c : ErrorCorrectingCodes.Codeword n α, the cardinality of the Hamming ball of radius r centered at c equals the cardinality of the Hamming ball of radius r centered at the zero codeword (ErrorCorrectingCodes.Codeword.zero).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows that translation by -c (the map x ↦ x - c) is an injective function that maps the Hamming ball of radius r around c onto the Hamming ball of radius r around the zero codeword. This bijection holds because subtracting c preserves the Hamming distance to c, so d(x - c, 0) = d(x, c). Because injective maps preserve the cardinality of finite sets, the ball around c and the ball around zero have the same size.
The codeword Codeword.zero is definitionally equal to the algebraic zero vector 0.
This holds definitionally by reflexivity (`rfl`), identifying the library's zero codeword with the standard additive zero of the codeword type.
have h_zero : (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α) = 0 := rfl
For every codeword x, the Hamming distance from x - c to 0 equals the Hamming distance from x to c.
Unfolding the definition of Hamming distance, the distance between two codewords is the number of coordinates at which they differ. For any coordinate index i, (x - c)ᵢ ≠ 0 if and only if xᵢ ≠ cᵢ by `sub_ne_zero`. Thus the sets of differing coordinates are identical, so their cardinalities are equal.
uses
sub_ne_zerohave h_sub_dist : ∀ x : ErrorCorrectingCodes.Codeword n α, ErrorCorrectingCodes.Codeword.hamming_distance (x - c) 0 = ErrorCorrectingCodes.Codeword.hamming_distance x c := by intro x dsimp [ErrorCorrectingCodes.Codeword.hamming_distance, hammingDist] congr 1 ext i simp [sub_ne_zero]
For every codeword y, the Hamming distance from y + c to c equals the Hamming distance from y to 0.
Unfolding Hamming distance, the condition (y + c)ᵢ ≠ cᵢ at each coordinate simplifies directly to yᵢ ≠ 0 in the underlying field. Thus the index sets where the coordinates differ are identical, so their cardinalities coincide.
have h_add_dist : ∀ y : ErrorCorrectingCodes.Codeword n α, ErrorCorrectingCodes.Codeword.hamming_distance (y + c) c = ErrorCorrectingCodes.Codeword.hamming_distance y 0 := by intro y dsimp [ErrorCorrectingCodes.Codeword.hamming_distance, hammingDist] congr 1 ext i simp
A codeword x belongs to the Hamming ball of radius s around w if and only if the Hamming distance between x and w is at most s.
This characterisation holds directly by expanding the definition of `ErrorCorrectingCodes.Codeword.hamming_ball`.
have h_mem : ∀ (s : ℕ) (w x : ErrorCorrectingCodes.Codeword n α), x ∈ ErrorCorrectingCodes.Codeword.hamming_ball s w ↔ ErrorCorrectingCodes.Codeword.hamming_distance x w ≤ s := by intro s w x simp [ErrorCorrectingCodes.Codeword.hamming_ball]
The translation map x ↦ x - c is injective.
If x - c = y - c, applying the function z ↦ z + c to both sides via `congr_arg` yields (x - c) + c = (y - c) + c, which simplifies to x = y.
uses
congr_arghave h_inj : Function.Injective (fun x : ErrorCorrectingCodes.Codeword n α => x - c) := by intro x y hxy simpa using congr_arg (fun z => z + c) hxy
The image of the Hamming ball of radius r around c under the translation map x ↦ x - c equals the Hamming ball of radius r around the zero codeword.
We establish set equality by double inclusion using `Finset.mem_image`. If y = x - c for some x in the ball around c, then d(y, 0) = d(x - c, 0) = d(x, c) ≤ r, so y belongs to the ball around 0. Conversely, if y belongs to the ball around 0, we take y + c as the preimage witness: (y + c) - c simplifies to y, and d(y + c, c) = d(y, 0) ≤ r shows that y + c lies in the ball around c.
uses
Finset.mem_imagehave h_img : (ErrorCorrectingCodes.Codeword.hamming_ball r c).image (fun x => x - c) = ErrorCorrectingCodes.Codeword.hamming_ball r (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α) := by ext y rw [Finset.mem_image] constructor · rintro ⟨x, hx, rfl⟩ rw [h_mem] at hx ⊢ rw [h_zero, h_sub_dist] exact hx · intro hy rw [h_mem] at hy refine ⟨y + c, ?_, by simp⟩ rw [h_mem, h_add_dist] rw [h_zero] at hy exact hy
The cardinality of the Hamming ball around c equals the cardinality of the Hamming ball around the zero codeword.
Rewriting the ball around the zero codeword as the image of the ball around c under x ↦ x - c, the two cardinalities are equal by `Finset.card_image_of_injective` because the translation map is injective.
uses
Finset.card_image_of_injectiverw [← h_img] exact (Finset.card_image_of_injective _ h_inj).symm
sub_ne_zero- In an additive group, the difference a - b is non-zero if and only if a ≠ b.
congr_arg- If two elements are equal, applying any function to both preserves equality: a₁ = a₂ implies f(a₁) = f(a₂).
Finset.mem_image- An element b is in the image of a finite set s under f if and only if there exists a ∈ s with f(a) = b.
Finset.card_image_of_injective- An injective map preserves the cardinality of any finite set when mapped to its image.
- The distinction between `ErrorCorrectingCodes.Codeword.zero` and the algebraic `0` is a formal Lean detail; mathematically, both denote the all-zero codeword.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Translation invariance of Hamming ball size: the size of a Hamming ball of radius r around any codeword equals the size of the Hamming ball of radius r around the all-zero codeword. -/theorem hamming_ball_card_eq_zero {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] {n : ℕ} (r : ℕ) (c : ErrorCorrectingCodes.Codeword n α) : (ErrorCorrectingCodes.Codeword.hamming_ball r c).card = (ErrorCorrectingCodes.Codeword.hamming_ball r (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α)).card := by have h_zero : (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α) = 0 := rfl have h_sub_dist : ∀ x : ErrorCorrectingCodes.Codeword n α, ErrorCorrectingCodes.Codeword.hamming_distance (x - c) 0 = ErrorCorrectingCodes.Codeword.hamming_distance x c := by intro x dsimp [ErrorCorrectingCodes.Codeword.hamming_distance, hammingDist] congr 1 ext i simp [sub_ne_zero] have h_add_dist : ∀ y : ErrorCorrectingCodes.Codeword n α, ErrorCorrectingCodes.Codeword.hamming_distance (y + c) c = ErrorCorrectingCodes.Codeword.hamming_distance y 0 := by intro y dsimp [ErrorCorrectingCodes.Codeword.hamming_distance, hammingDist] congr 1 ext i simp have h_mem : ∀ (s : ℕ) (w x : ErrorCorrectingCodes.Codeword n α), x ∈ ErrorCorrectingCodes.Codeword.hamming_ball s w ↔ ErrorCorrectingCodes.Codeword.hamming_distance x w ≤ s := by intro s w x simp [ErrorCorrectingCodes.Codeword.hamming_ball] have h_inj : Function.Injective (fun x : ErrorCorrectingCodes.Codeword n α => x - c) := by intro x y hxy simpa using congr_arg (fun z => z + c) hxy have h_img : (ErrorCorrectingCodes.Codeword.hamming_ball r c).image (fun x => x - c) = ErrorCorrectingCodes.Codeword.hamming_ball r (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α) := by ext y rw [Finset.mem_image] constructor · rintro ⟨x, hx, rfl⟩ rw [h_mem] at hx ⊢ rw [h_zero, h_sub_dist] exact hx · intro hy rw [h_mem] at hy refine ⟨y + c, ?_, by simp⟩ rw [h_mem, h_add_dist] rw [h_zero] at hy exact hy rw [← h_img] exact (Finset.card_image_of_injective _ h_inj).symm