AFTD Auto-Formalizing Theoretical Domains

card_hamming_ring

theoremverifiedformalization

For natural numbers n, q, c, c' with 2 ≤ q and c + c' ≤ n, and any x : Fin n → Fin q, the cardinality of the (c, c') Hamming ring centered at x is ∑ j ∈ Finset.Icc (c + 1) (c + c'), Nat.choose n j * (q - 1) ^ j.

Statement

theorem card_hamming_ring (n q c c' : ℕ) (hq : 2 ≤ q) (hc : c + c' ≤ n) (x : Fin n → Fin q) :
    (hamming_ring c c' x).card = ∑ j ∈ Finset.Icc (c + 1) (c + c'), Nat.choose n j * (q - 1) ^ j
Formalizes
arXiv:2611.18156 Definition III.1
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • hamming_ringGiven implicit parameters n and q, the (c, c') Hamming ring hamming_ring c c' x centered at x : Fin n → Fin q is the finite set (Finset)…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Used by 1
  • joint_hamming_boundLet q ≥ 2, n ≥ 1, and let c, c' be non-negative integers with c + c' ≤ n. If C ⊆ (Fin n → Fin q) is a (c, c') joint error-correcting and…

Read back from the Lean

For all natural numbers $n$, $q$, $c$, and $c'$, assuming $2 \le q$ and $c + c' \le n$, and for every function $x : \text{Fin } n \to \text{Fin } q$, the cardinality of hamming_ring c c' x is equal to $\sum_{j = c + 1}^{c + c'} \binom{n}{j}(q - 1)^j$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

private def card_hamming_ring_diffSet {n q : ℕ} (x y : Fin n → Fin q) : Finset (Fin n) :=
  Finset.univ.filter (fun i => x i ≠ y i)

private def card_hamming_ring_piEquiv {n q : ℕ} (t : Fin n → Finset (Fin q)) :
    {y : Fin n → Fin q // ∀ i, y i ∈ t i} ≃ ((i : Fin n) → {a : Fin q // a ∈ t i}) where
  toFun y i := ⟨y.1 i, y.2 i⟩
  invFun g := ⟨fun i => (g i).1, fun i => (g i).2⟩
  left_inv _ := rfl
  right_inv _ := rfl

private lemma card_hamming_ring_filter_diffSet {n q : ℕ} (x : Fin n → Fin q) (S : Finset (Fin n)) :
    (Finset.univ.filter (fun y : Fin n → Fin q => card_hamming_ring_diffSet x y = S)).card
      = (q - 1) ^ S.card := by
  classical
  let t : Fin n → Finset (Fin q) :=
    fun i => if i ∈ S then Finset.univ.filter (fun a => a ≠ x i) else {x i}
  have hset : Finset.univ.filter (fun y : Fin n → Fin q => card_hamming_ring_diffSet x y = S)
      = Finset.univ.filter (fun y : Fin n → Fin q => ∀ i, y i ∈ t i) := by
    apply Finset.filter_congr
    intro y _
    constructor
    · intro hy i
      by_cases hi : i ∈ S
      · have hmem : i ∈ card_hamming_ring_diffSet x y := by rw [hy]; exact hi
        simp only [card_hamming_ring_diffSet, Finset.mem_filter, Finset.mem_univ, true_and] at hmem
        simp only [t, if_pos hi, Finset.mem_filter, Finset.mem_univ, true_and]
        exact hmem.symm
      · have hmem : i ∉ card_hamming_ring_diffSet x y := by rw [hy]; exact hi
        simp only [card_hamming_ring_diffSet, Finset.mem_filter, Finset.mem_univ, true_and,
          not_not] at hmem
        simp only [t, if_neg hi, Finset.mem_singleton]
        exact hmem.symm
    · intro hy
      ext i
      simp only [card_hamming_ring_diffSet, Finset.mem_filter, Finset.mem_univ, true_and]
      have hmem := hy i
      by_cases hi : i ∈ S
      · have hyi : y i ≠ x i := by simpa [t, hi] using hmem
        exact ⟨fun _ => hi, fun _ => hyi.symm⟩
      · have hyi : y i = x i := by simpa [t, hi] using hmem
        exact ⟨fun h => absurd hyi.symm h, fun h => absurd h hi⟩
  have hcard : (Finset.univ.filter (fun y : Fin n → Fin q => ∀ i, y i ∈ t i)).card
      = ∏ i, (t i).card := by
    rw [← Fintype.card_subtype (fun y : Fin n → Fin q => ∀ i, y i ∈ t i)]
    rw [Fintype.card_congr (card_hamming_ring_piEquiv t), Fintype.card_pi]
    simp
  have hprod : (∏ i, (t i).card) = (q - 1) ^ S.card := by
    have hterm : ∀ i, (t i).card = if i ∈ S then q - 1 else 1 := by
      intro i
      by_cases hi : i ∈ S
      · simp only [t, if_pos hi]
        rw [show Finset.univ.filter (fun a : Fin q => a ≠ x i) = Finset.univ.erase (x i) by
          ext a; simp]
        rw [Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin]
      · simp [t, hi]
    rw [Finset.prod_congr rfl (fun i _ => hterm i), Finset.prod_ite_mem]
    simp
  rw [hset, hcard, hprod]

private lemma card_hamming_ring_sphere {n q : ℕ} (j : ℕ) (x : Fin n → Fin q) :
    (Finset.univ.filter (fun y : Fin n → Fin q => hammingDist x y = j)).card
      = Nat.choose n j * (q - 1) ^ j := by
  classical
  have hset : Finset.univ.filter (fun y : Fin n → Fin q => hammingDist x y = j)
      = (Finset.univ.powersetCard j).biUnion
          (fun S => Finset.univ.filter (fun y : Fin n → Fin q => card_hamming_ring_diffSet x y = S)) := by
    ext y
    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_biUnion,
      Finset.mem_powersetCard]
    constructor
    · intro h
      have hd : hammingDist x y = (card_hamming_ring_diffSet x y).card := rfl
      exact ⟨card_hamming_ring_diffSet x y, ⟨Finset.subset_univ _, by rw [← hd, h]⟩, rfl⟩
    · rintro ⟨S, ⟨-, hS⟩, hEq⟩
      have hd : hammingDist x y = (card_hamming_ring_diffSet x y).card := rfl
      rw [hd, hEq, hS]
  rw [hset, Finset.card_biUnion]
  · trans ∑ S ∈ (Finset.univ : Finset (Fin n)).powersetCard j, (q - 1) ^ j
    · apply Finset.sum_congr rfl
      intro S hS
      rw [card_hamming_ring_filter_diffSet]
      rw [(Finset.mem_powersetCard.mp hS).2]
    · rw [Finset.sum_const, smul_eq_mul]
      congr 1
      rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin]
  · intro S _ T _ hST
    change Disjoint (Finset.univ.filter (fun y : Fin n → Fin q => card_hamming_ring_diffSet x y = S))
      (Finset.univ.filter (fun y : Fin n → Fin q => card_hamming_ring_diffSet x y = T))
    rw [Finset.disjoint_left]
    intro y hyS hyT
    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hyS hyT
    exact hST (hyS.symm.trans hyT)

/-- Cardinality of a (c, c') Hamming ring in (Fin n → Fin q). -/
theorem card_hamming_ring (n q c c' : ℕ) (hq : 2 ≤ q) (hc : c + c' ≤ n) (x : Fin n → Fin q) :
    (hamming_ring c c' x).card = ∑ j ∈ Finset.Icc (c + 1) (c + c'), Nat.choose n j * (q - 1) ^ j := by
  classical
  have _hq := hq
  have _hc := hc
  have hset : hamming_ring c c' x = (Finset.Icc (c + 1) (c + c')).biUnion
      (fun j => Finset.univ.filter (fun y : Fin n → Fin q => hammingDist x y = j)) := by
    ext y
    simp only [hamming_ring, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_biUnion,
      Finset.mem_Icc]
    constructor
    · rintro ⟨h1, h2⟩
      exact ⟨hammingDist x y, ⟨h1, h2⟩, rfl⟩
    · rintro ⟨j, ⟨h1, h2⟩, rfl⟩
      exact ⟨h1, h2⟩
  rw [hset, Finset.card_biUnion]
  · apply Finset.sum_congr rfl
    intro j _
    exact card_hamming_ring_sphere j x
  · intro j _ k _ hjk
    change Disjoint (Finset.univ.filter (fun y : Fin n → Fin q => hammingDist x y = j))
      (Finset.univ.filter (fun y : Fin n → Fin q => hammingDist x y = k))
    rw [Finset.disjoint_left]
    intro y hj hk
    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hj hk
    exact hjk (hj.symm.trans hk)
See it in the graphDiscuss this resultChallenge it