AFTD Auto-Formalizing Theoretical Domains

joint_hamming_bound

theoremverifiedformalization

Let 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 detecting code, then |C| * ∑ i ∈ Finset.range (c + 1), Nat.choose n i * (q - 1) ^ i + ∑ j ∈ Finset.Icc (c + 1) (c + c'), Nat.choose n j * (q - 1) ^ j ≤ q ^ n.

Statement

theorem joint_hamming_bound (n q c c' : ℕ) (hq : 2 ≤ q) (hn : 1 ≤ n) (hc : c + c' ≤ n)
    (C : Finset (Fin n → Fin q)) (hC : is_joint_error_correcting_detecting c c' C) :
    C.card * (∑ i ∈ Finset.range (c + 1), Nat.choose n i * (q - 1) ^ i) +
      ∑ j ∈ Finset.Icc (c + 1) (c + c'), Nat.choose n j * (q - 1) ^ j ≤ q ^ n
Formalizes
arXiv:2611.18156 Theorem III.6
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • hamming_ballGiven implicit parameters n and q, the Hamming ball hamming_ball r x of radius r centered at x : Fin n → Fin q is the finite set…
  • 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)…
  • is_joint_error_correcting_detectingGiven implicit parameters n and q, a code C : Finset (Fin n → Fin q) is a (c, c') joint error-correcting and detecting code if distinct…
  • disjoint_hamming_ball_hamming_ring_sameGiven implicit parameters n and q, for any point x : Fin n → Fin q, the Hamming ball of radius c centered at x and the (c, c') Hamming…
  • card_hamming_ballFor natural numbers n, q, r with 2 ≤ q and r ≤ n, and any x : Fin n → Fin q, the cardinality of the Hamming ball of radius r centered at x…
  • card_hamming_ringFor 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…

Read back from the Lean

Let $n, q, c, c' \in \mathbb{N}$ such that $q \ge 2$, $n \ge 1$, and $c + c' \le n$. Let $C \subseteq (\mathrm{Fin}\ n \to \mathrm{Fin}\ q)$ be a code (a finite set of words of length $n$ over an alphabet of size $q$) satisfying is_joint_error_correcting_detecting c c' C, which means: 1. For all $x_1, x_2 \in C$ with $x_1 \ne x_2$, the Hamming balls of radius $c$ centered at $x_1$ and $x_2$ are disjoint: $$\{y \mid \mathrm{hammingDist}(x_1, y) \le c\} \cap \{y \mid \mathrm{hammingDist}(x_2, y) \le c\} = \emptyset$$ 2. For all $x_1, x_2 \in C$, the Hamming ball of radius $c$ centered at $x_1$ and the Hamming ring with inner radius $c + 1$ and outer radius $c + c'$ centered at $x_2$ are disjoint: $$\{y \mid \mathrm{hammingDist}(x_1, y) \le c\} \cap \{y \mid c + 1 \le \mathrm{hammingDist}(x_2, y) \le c + c'\} = \emptyset$$ Then the joint Hamming bound holds: $$|C| \cdot \left(\sum_{i=0}^c \binom{n}{i} (q - 1)^i\right) + \sum_{j=c+1}^{c+c'} \binom{n}{j} (q - 1)^j \le q^n$$

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

/-- Hamming-type upper bound for (c, c') joint error-correcting and detecting codes. -/
theorem joint_hamming_bound (n q c c' : ℕ) (hq : 2 ≤ q) (hn : 1 ≤ n) (hc : c + c' ≤ n)
    (C : Finset (Fin n → Fin q)) (hC : is_joint_error_correcting_detecting c c' C) :
    C.card * (∑ i ∈ Finset.range (c + 1), Nat.choose n i * (q - 1) ^ i) +
      ∑ j ∈ Finset.Icc (c + 1) (c + c'), Nat.choose n j * (q - 1) ^ j ≤ q ^ n := by
  rcases C.eq_empty_or_nonempty with rfl | ⟨x₀, hx₀⟩
  · simp only [Finset.card_empty, zero_mul, zero_add]
    let x₀ : Fin n → Fin q := fun _ => ⟨0, by omega⟩
    rw [← card_hamming_ring n q c c' hq hc x₀]
    have hle := Finset.card_le_univ (hamming_ring c c' x₀)
    have huniv : Fintype.card (Fin n → Fin q) = q ^ n := by simp
    omega
  · have hc_le : c ≤ n := by omega
    have h_card_ball : ∀ x ∈ C, (hamming_ball c x).card = ∑ i ∈ Finset.range (c + 1), Nat.choose n i * (q - 1) ^ i :=
      fun x _ => card_hamming_ball n q c hq hc_le x
    have h_pw : (↑C : Set (Fin n → Fin q)).PairwiseDisjoint (hamming_ball c) :=
      fun x₁ hx₁ x₂ hx₂ hne => hC.1 x₁ hx₁ x₂ hx₂ hne
    have h_union_card : (C.biUnion (hamming_ball c)).card =
        C.card * (∑ i ∈ Finset.range (c + 1), Nat.choose n i * (q - 1) ^ i) := by
      rw [Finset.card_biUnion h_pw]
      rw [Finset.sum_congr rfl h_card_ball]
      simp
    have h_disj : Disjoint (C.biUnion (hamming_ball c)) (hamming_ring c c' x₀) := by
      rw [Finset.disjoint_biUnion_left]
      intro x hx
      exact hC.2 x hx x₀ hx₀
    have h_disj_union : ((C.biUnion (hamming_ball c)) ∪ (hamming_ring c c' x₀)).card =
        (C.biUnion (hamming_ball c)).card + (hamming_ring c c' x₀).card :=
      Finset.card_union_of_disjoint h_disj
    have h_ring_card : (hamming_ring c c' x₀).card =
        ∑ j ∈ Finset.Icc (c + 1) (c + c'), Nat.choose n j * (q - 1) ^ j :=
      card_hamming_ring n q c c' hq hc x₀
    have hle := Finset.card_le_univ ((C.biUnion (hamming_ball c)) ∪ (hamming_ring c c' x₀))
    have huniv : Fintype.card (Fin n → Fin q) = q ^ n := by simp
    omega
See it in the graphDiscuss this resultChallenge it