ErrorCorrectingCodes.Codeword.gv_bound
theoremverifiedformalizationimported Lean
Gilbert–Varshamov bound for linear codes. Let $\alpha$ be a finite field with $q = \abs{\alpha}$ elements, and let $n, k, d$ be natural numbers. Write $B_{d-1}(\mathbf{0})$ for the Hamming ball of radius $d-1$ about the all-zero codeword in $\alpha^n$, and suppose \[ k \le n - \bigl\lceil \log_q \abs{B_{d-1}(\mathbf{0})} \bigr\rceil - 1. \] Then there exists an $n \times k$ generator matrix $G$ over $\alpha$ such that for every nonzero message $x \in \alpha^k$, the codeword $Gx \in \alpha^n$ has Hamming weight at least $d$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true 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.gv_bound (n k q d : ℕ) (h_q : q = (Fintype.card α)) (h_k : k ≤ n - ((Nat.clog q) (hamming_ball (d-1) (zero : Codeword n α)).card) - 1): (Set.toFinset {G : (Matrix (Fin n) (Fin k) α) | ∀ (x : Codeword k α), x ≠ 0 → weight (Matrix.mulVec G x) ≥ d}).card ≥ 1
- Formalizes
- Gilbert–Varshamov bound for linear codes, as formalized in TCSlib (`ErrorCorrectingCodes.Codeword.gv_bound`)
- 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.ErrorCorrectingCodes.Codeword.gv_bound← ErrorCorrectingCodes.Codeword.gv_bound (TCSlib/ErrorCorrectingCodes/GilbertVarshamov.lean:299): adapted
What was changed in
ErrorCorrectingCodes.Codeword.gv_bound--- TCSlib/ErrorCorrectingCodes/GilbertVarshamov.lean:299 (ErrorCorrectingCodes.Codeword.gv_bound) +++ as compiled here @@ -1,5 +1,8 @@ -/-- **Gilbert–Varshamov bound**: if `k ≤ n − ⌈log_q Vol(n, d−1)⌉ − 1`, then there exists - an `n×k` generator matrix `G` such that every nonzero message is mapped to a codeword - of Hamming weight at least `d`. -/ -theorem gv_bound (n k q d : ℕ) (h_q : q = (Fintype.card α)) (h_k : k ≤ n - ((Nat.clog q) (hamming_ball (d-1) (zero : Codeword n α)).card) - 1): +set_option autoImplicit true in +set_option relaxedAutoImplicit true 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.gv_bound (n k q d : ℕ) (h_q : q = (Fintype.card α)) (h_k : k ≤ n - ((Nat.clog q) (hamming_ball (d-1) (zero : Codeword n α)).card) - 1): (Set.toFinset {G : (Matrix (Fin n) (Fin k) α) | ∀ (x : Codeword k α), x ≠ 0 → weight (Matrix.mulVec G x) ≥ d}).card ≥ 1 := by { @@ -16,3 +19,5 @@ have h_all_card : Fintype.card (Matrix (Fin n) (Fin k) α) = (Fintype.card α)^(n*k) := by - simp only [Matrix, Fintype.card_fun, Fintype.card_fin]; ring + rw [show Fintype.card (Matrix (Fin n) (Fin k) α) = Fintype.card (Fin n → Fin k → α) from + Fintype.card_congr (Equiv.refl _)] + simp only [Fintype.card_fun, Fintype.card_fin]; ring have hq_gt1 : 1 < (Fintype.card α) := Fintype.one_lt_card - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- ErrorCorrectingCodes.Codeword.existence_boundExistence bound via union bound. Let $\alpha$ be a finite nonempty field, let $n$ and $k$ be natural numbers with $k \ge 1$, and let $d$…
- 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
Finset. - ErrorCorrectingCodes.Codeword.zeroPointwise addition, subtraction, and the all-zero codeword.
- ErrorCorrectingCodes.Codeword.weightThe Hamming weight of $c$ is $d(c, \mathbf{0})$.
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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inset_option linter.unusedSectionVars false inopen Set Filter Asymptotics Finset invariable {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] [Field α] invariable {n k : ℕ} in/-- **Gilbert–Varshamov bound**: if `k ≤ n − ⌈log_q Vol(n, d−1)⌉ − 1`, then there exists an `n×k` generator matrix `G` such that every nonzero message is mapped to a codeword of Hamming weight at least `d`. -/theorem ErrorCorrectingCodes.Codeword.gv_bound (n k q d : ℕ) (h_q : q = (Fintype.card α)) (h_k : k ≤ n - ((Nat.clog q) (hamming_ball (d-1) (zero : Codeword n α)).card) - 1):(Set.toFinset {G : (Matrix (Fin n) (Fin k) α) | ∀ (x : Codeword k α), x ≠ 0 → weight (Matrix.mulVec G x) ≥ d}).card ≥ 1 := by { set bc := (hamming_ball (d-1) (zero : Codeword n α)).card with h_bc_def let bad_G := Set.toFinset {G : (Matrix (Fin n) (Fin k) α) | ∃ (x : Codeword k α), x ≠ 0 ∧ weight (Matrix.mulVec G x) < d} have h_good_eq : Set.toFinset {G : (Matrix (Fin n) (Fin k) α) | ∀ (x : Codeword k α), x ≠ 0 → weight (Matrix.mulVec G x) ≥ d} = Finset.univ \ bad_G := by ext G simp only [bad_G, Finset.mem_sdiff, Finset.mem_univ, true_and, Set.mem_toFinset, Set.mem_setOf_eq] constructor · intro h ⟨x, hxne, hlt⟩; exact absurd (h x hxne) (Nat.not_le.mpr hlt) · intro h x hxne; exact Nat.le_of_not_lt (fun hlt => h ⟨x, hxne, hlt⟩) have h_all_card : Fintype.card (Matrix (Fin n) (Fin k) α) = (Fintype.card α)^(n*k) := by rw [show Fintype.card (Matrix (Fin n) (Fin k) α) = Fintype.card (Fin n → Fin k → α) from Fintype.card_congr (Equiv.refl _)] simp only [Fintype.card_fun, Fintype.card_fin]; ring have hq_gt1 : 1 < (Fintype.card α) := Fintype.one_lt_card have hq_gt1' : 1 < q := h_q ▸ hq_gt1 have hq_pos : 0 < (Fintype.card α) := by omega have h_ball_le_pow_of_clog_le : ∀ c : ℕ, Nat.clog q bc ≤ c → bc ≤ (Fintype.card α)^c := by intro c hc rw [h_bc_def, ← h_q] at * exact (Nat.clog_le_iff_le_pow hq_gt1').mp hc rw [h_good_eq, Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ, h_all_card] suffices h : bad_G.card < (Fintype.card α)^(n*k) by omega by_cases hk0 : k = 0 · have h_bad_empty : bad_G = ∅ := by apply Finset.eq_empty_of_forall_notMem simp only [bad_G, Set.mem_toFinset, Set.mem_setOf_eq, not_exists, not_and] intro G x hxne have : x = 0 := by ext i; exact Fin.elim0 (hk0 ▸ i) exact absurd this hxne simp [h_bad_empty, hk0] · have hk_pos : k ≥ 1 := Nat.one_le_iff_ne_zero.mpr hk0 have h_clog_le : Nat.clog q bc + k + 1 ≤ n := by omega have h_ball_le_pow : bc ≤ (Fintype.card α)^(n - k - 1) := h_ball_le_pow_of_clog_le _ (by omega) by_cases hd0 : d = 0 · have h_bad_empty : bad_G = ∅ := by apply Finset.eq_empty_of_forall_notMem simp only [bad_G, Set.mem_toFinset, Set.mem_setOf_eq, not_exists, not_and] intro G x _; simp [hd0] simp [h_bad_empty]; positivity · have hd_pos : d > 0 := Nat.pos_of_ne_zero hd0 have h_exist : bad_G.card ≤ ((Fintype.card α)^k - 1) * (Fintype.card α)^(n*k - n) * bc := existence_bound d hk_pos hd_pos have hn_pos : 1 ≤ n := by omega have hnk_ge_n : n ≤ n * k := Nat.le_mul_of_pos_right n hk_pos have hnk_ge_k : k ≤ n * k := Nat.le_mul_of_pos_left k hn_pos have h_exp_combine : n*k - n + (n - k - 1) = n*k - k - 1 := by omega have h_exp_merge : k + (n*k - k - 1) = n*k - 1 := by omega have h_combine : ((Fintype.card α)^k - 1) * (Fintype.card α)^(n*k - n) * (Fintype.card α)^(n - k - 1) = ((Fintype.card α)^k - 1) * (Fintype.card α)^(n*k - k - 1) := by rw [mul_assoc, ← pow_add, h_exp_combine] calc bad_G.card ≤ ((Fintype.card α)^k - 1) * (Fintype.card α)^(n*k - n) * bc := h_exist _ ≤ ((Fintype.card α)^k - 1) * (Fintype.card α)^(n*k - n) * (Fintype.card α)^(n - k - 1) := Nat.mul_le_mul_left _ h_ball_le_pow _ = ((Fintype.card α)^k - 1) * (Fintype.card α)^(n*k - k - 1) := h_combine _ < (Fintype.card α)^k * (Fintype.card α)^(n*k - k - 1) := Nat.mul_lt_mul_of_pos_right (Nat.sub_lt (Nat.pow_pos hq_pos) Nat.one_pos) (Nat.pow_pos hq_pos) _ = (Fintype.card α)^(n*k - 1) := by rw [← pow_add, h_exp_merge] _ ≤ (Fintype.card α)^(n*k) := Nat.pow_le_pow_right hq_pos (by omega)}