hamming_sphere_packing_bound
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
- ErrorCorrectingCodes.Codeword.hamming_ball_non_intersectDisjointness of decoding balls around distinct codewords. Let $C$ be a code of length $n$ over a finite alphabet $\alpha$ whose minimum…
- hamming_ball_card_eq_zeroTranslation 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…
- ErrorCorrectingCodes.Codeword.distance
distance C dholds when $d$ is the minimum Hamming distance of $C$: there exist distinct codewords at distance exactly $d$, and… - ErrorCorrectingCodes.Codeword.hamming_distanceHamming distance between two codewords, wrapping Mathlib's
hammingDist. - ErrorCorrectingCodes.Codeword.CodeA (block) code of length $n$ over $\alpha$ is a finite set (
Finset) of codewords. - 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.CodewordA codeword of length $n$ over alphabet $\alpha$ is a function $c : \mathrm{Fin}\,n \to \alpha$.
- ErrorCorrectingCodes.Codeword.zeroPointwise addition, subtraction, and the all-zero codeword.
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.
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 ℕ.
uses
Nat.cast_pred,Nat.floor_div_eq_divopen 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
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₂.
uses
Function.onFun,Finset.disjoint_left,Finset.mem_coe,ErrorCorrectingCodes.Codeword.hamming_ball_non_intersecthave 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'
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.
uses
Finset.card_biUnionhave h_card_union := Finset.card_biUnion (s := C) (t := fun c => ErrorCorrectingCodes.Codeword.hamming_ball ((d - 1) / 2) c) hdisj
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.
uses
hamming_ball_card_eq_zero,Finset.sum_congr,Finset.sum_const,smul_eq_mulhave 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]
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.
uses
card_le_univrw [← 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.
- The lemma `hamming_ball_non_intersect` expresses the packing radius using the floor of real division $\lfloor (d - 1) / 2 \rfloor$, so the proof begins with an arithmetic lemma (`hfloor`) showing that this coincides with natural number division $(d - 1) / 2$.
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.
/-- 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