AFTD Auto-Formalizing Theoretical Domains

hamming_ball_card_eq_zero

theoremverified

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
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.

  1. 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.

    line 5

      have h_zero : (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α) = 0 := rfl
  2. 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.

    lines 6–13

    uses sub_ne_zero

      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]
  3. 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.

    lines 14–21

      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
  4. 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`.

    lines 22–26

      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]
  5. 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.

    lines 27–29

    uses congr_arg

      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
  6. 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.

    lines 30–44

    uses Finset.mem_image

      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
  7. 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.

    lines 45–46

    uses Finset.card_image_of_injective

      rw [← 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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it