AFTD Auto-Formalizing Theoretical Domains

hamming_sphere_packing_bound

theoremverifiedformalization

Hamming (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 minimum Hamming distance d > 0. Then the product of the code size card C and the volume of the Hamming ball of radius (d - 1) / 2 around the zero codeword is at most (card alpha) ^ n.

Statement

theorem hamming_sphere_packing_bound {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] {n : ℕ} (C : ErrorCorrectingCodes.Codeword.Code n α) (d : ℕ)
    (h : ErrorCorrectingCodes.Codeword.distance C d) (hd : 0 < d) :
    C.card * (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α)).card ≤ (Fintype.card α) ^ n
Formalizes
Cover & Thomas, Elements of Information Theory, Ch. 7; Hamming 1950
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

Read back from the Lean

For any type α with instances of Fintype, Nonempty, DecidableEq, and Field, any natural number n, any code C : ErrorCorrectingCodes.Codeword.Code n α, and any natural number d: if ErrorCorrectingCodes.Codeword.distance C d holds and 0 < d, then the cardinality of C multiplied by the cardinality of the Hamming ball of radius (d - 1) / 2 (using natural number division) centered at ErrorCorrectingCodes.Codeword.zero (of type ErrorCorrectingCodes.Codeword n α) is less than or equal to (Fintype.card α) ^ n.

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 Hamming (sphere-packing) bound states that for any code C of length n with minimum distance d > 0, the code size multiplied by the volume of a Hamming ball of radius (d - 1) / 2 is at most (card α) ^ n. Because distinct codewords are separated by at least d, their Hamming balls of radius (d - 1) / 2 are pairwise disjoint, so the size of their union equals the sum of their individual sizes. By translation invariance, every ball has the same size as the ball centered at the zero codeword, so this sum is |C| * |B(0, (d - 1) / 2)|. Finally, the union is contained in the ambient space of all n-tuples over α, which has size (card α) ^ n.

  1. The floor of real division ((d : ℝ) - 1) / 2 equals the natural division (d - 1) / 2.

    Since d > 0, the predecessor d - 1 in ℕ casts to (d : ℝ) - 1 by Nat.cast_pred. Rewriting with this casts the numerator to ℕ, after which Nat.floor_div_eq_div equates the floor of division in ℝ with integer division in ℕ.

    lines 5–9

    uses Nat.cast_pred, Nat.floor_div_eq_div

      open Finset in
      have hfloor : ⌊((d : ℝ) - 1) / 2⌋₊ = (d - 1) / 2 := by
        have h1 : (d : ℝ) - 1 = ((d - 1 : ℕ) : ℝ) := (Nat.cast_pred hd).symm
        rw [h1]
        exact Nat.floor_div_eq_div (d - 1) 2
  2. Hamming balls of packing radius (d - 1) / 2 centered at distinct codewords in C are pairwise disjoint.

    Let c₁ and c₂ be distinct codewords in C. Unfolding disjointness with Finset.disjoint_left, suppose c' belongs to the ball around c₁. Using hfloor to rewrite the radius into floor-division form and unpacking set membership with Finset.mem_coe, ErrorCorrectingCodes.Codeword.hamming_ball_non_intersect establishes that c' cannot belong to the ball around c₂.

    lines 10–18

    uses Function.onFun, Finset.disjoint_left, Finset.mem_coe, ErrorCorrectingCodes.Codeword.hamming_ball_non_intersect

      have hdisj : (↑C : Set (ErrorCorrectingCodes.Codeword n α)).PairwiseDisjoint
          (fun c => ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c) := by
        intro c₁ hc₁ c₂ hc₂ hne
        dsimp [Function.onFun]
        rw [Finset.disjoint_left]
        intro c' hc'
        rw [← hfloor] at hc' ⊢
        rw [Finset.mem_coe] at hc₁ hc₂
        exact ErrorCorrectingCodes.Codeword.hamming_ball_non_intersect C h hd c₁ c₂ ⟨hc₁, hc₂, hne⟩ c' hc'
  3. The size of the union of the Hamming balls around all codewords equals the sum of the sizes of the individual balls.

    Because the balls are pairwise disjoint, Finset.card_biUnion evaluates the cardinality of their union as the sum of their individual cardinalities over c ∈ C.

    lines 19–20

    uses Finset.card_biUnion

      have h_card_union := Finset.card_biUnion (s := C)
        (t := fun c => ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c) hdisj
  4. The sum of the ball sizes over all codewords in C equals |C| multiplied by the size of the ball centered at zero.

    By translation invariance of the Hamming metric (hamming_ball_card_eq_zero), every ball of radius (d - 1) / 2 has the same cardinality as the ball centered at zero. Replacing each term via Finset.sum_congr, the sum of this constant over C simplifies to |C| * |B(0, (d - 1) / 2)| using Finset.sum_const and smul_eq_mul.

    lines 21–27

    uses hamming_ball_card_eq_zero, Finset.sum_congr, Finset.sum_const, smul_eq_mul

      have h_sum_eq : (∑ c ∈ C, (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c).card) =
          C.card * (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α)).card := by
        have : ∀ c ∈ C, (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c).card =
            (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α)).card := by
          intro c _
          exact hamming_ball_card_eq_zero ((d - 1) / 2) c
        rw [Finset.sum_congr rfl this, Finset.sum_const, smul_eq_mul]
  5. The code size multiplied by the ball volume is at most (card α) ^ n.

    Rewriting the product as the size of the union of all balls, it suffices to bound this size. By card_le_univ, any subset of the codeword space has cardinality at most the total number of words. The codeword space Fin n → α has cardinality (card α) ^ n, which completes the bound.

    lines 28–34

    uses card_le_univ

      rw [← h_sum_eq, ← h_card_union]
      have h_le := (C.biUnion (fun c => ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c)).card_le_univ
      have h_total : Fintype.card (ErrorCorrectingCodes.Codeword n α) = (Fintype.card α) ^ n := by
        change Fintype.card (Fin n → α) = (Fintype.card α) ^ n
        simp
      rw [h_total] at h_le
      exact h_le
Nat.cast_pred
For any positive natural number n, casting n - 1 into a ring equals casting n minus 1.
Nat.floor_div_eq_div
The floor of the quotient of two natural numbers cast to an ordered field equals their natural number division.
Function.onFun
Combines a binary relation on β with a function from α to β to yield the relation on α.
Finset.disjoint_left
Two finite sets are disjoint if and only if every element of the first does not belong to the second.
Finset.mem_coe
An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
ErrorCorrectingCodes.Codeword.hamming_ball_non_intersect
In a code with minimum distance d > 0, Hamming balls of radius ⌊(d - 1) / 2⌋ centered at distinct codewords are disjoint.
Finset.card_biUnion
The cardinality of a union of pairwise disjoint finite sets equals the sum of their individual cardinalities.
hamming_ball_card_eq_zero
The cardinality of a Hamming ball of radius r centered at any codeword equals that of the ball of radius r centered at the zero codeword.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on all elements.
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set multiplied by that value.
smul_eq_mul
Scalar multiplication of natural numbers is standard multiplication.
card_le_univ
The cardinality of any finite subset of a finite type is at most the total cardinality of that type.

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

/-- Hamming (sphere-packing) bound: the cardinality of any code of minimum distance d multiplied by the volume of a ball of packing radius (d-1)/2 is at most the total number of words. -/theorem hamming_sphere_packing_bound {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] {n : ℕ} (C : ErrorCorrectingCodes.Codeword.Code n α) (d : ℕ)    (h : ErrorCorrectingCodes.Codeword.distance C d) (hd : 0 < d) :    C.card * (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α)).card ≤ (Fintype.card α) ^ n := by  open Finset in  have hfloor : ⌊((d : ℝ) - 1) / 2⌋₊ = (d - 1) / 2 := by    have h1 : (d : ℝ) - 1 = ((d - 1 : ℕ) : ℝ) := (Nat.cast_pred hd).symm    rw [h1]    exact Nat.floor_div_eq_div (d - 1) 2  have hdisj : (↑C : Set (ErrorCorrectingCodes.Codeword n α)).PairwiseDisjoint      (fun c => ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c) := by    intro c₁ hc₁ c₂ hc₂ hne    dsimp [Function.onFun]    rw [Finset.disjoint_left]    intro c' hc'    rw [← hfloor] at hc' ⊢    rw [Finset.mem_coe] at hc₁ hc₂    exact ErrorCorrectingCodes.Codeword.hamming_ball_non_intersect C h hd c₁ c₂ ⟨hc₁, hc₂, hne⟩ c' hc'  have h_card_union := Finset.card_biUnion (s := C)    (t := fun c => ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c) hdisj  have h_sum_eq : (∑ c ∈ C, (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c).card) =      C.card * (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α)).card := by    have : ∀ c ∈ C, (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c).card =        (ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) (ErrorCorrectingCodes.Codeword.zero : ErrorCorrectingCodes.Codeword n α)).card := by      intro c _      exact hamming_ball_card_eq_zero ((d - 1) / 2) c    rw [Finset.sum_congr rfl this, Finset.sum_const, smul_eq_mul]  rw [← h_sum_eq, ← h_card_union]  have h_le := (C.biUnion (fun c => ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c)).card_le_univ  have h_total : Fintype.card (ErrorCorrectingCodes.Codeword n α) = (Fintype.card α) ^ n := by    change Fintype.card (Fin n → α) = (Fintype.card α) ^ n    simp  rw [h_total] at h_le  exact h_le
See it in the graphDiscuss this resultChallenge it