AFTD Auto-Formalizing Theoretical Domains

binary_code_avoids_odd_dist_card_le

theoremverified

Let n ≥ 1 and 1 ≤ d ≤ n. Every finite set of binary words F : Finset (Fin n → Fin 2) such that no two elements have Hamming distance d satisfies F.card ≤ 2 ^ (n - 1).

Statement

theorem binary_code_avoids_odd_dist_card_le (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (F : Finset (Fin n → Fin 2)) (hF : ∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) : F.card ≤ 2 ^ (n - 1)
Source
arXiv:2611.04523, Proposition 3.1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For all natural numbers $n$ and $d$ such that $1 \le n$, $1 \le d$, and $d \le n$, and for every finite set $F$ of binary sequences of length $n$ (elements of $\mathrm{Fin}\ n \to \mathrm{Fin}\ 2$), if no pair of elements $x, y \in F$ has Hamming distance equal to $d$ ($\forall x \in F, \forall y \in F, \operatorname{hammingDist}(x, y) \neq d$), then the cardinality of $F$ is at most $2^{n - 1}$.

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 theorem is proved by a translation argument. We construct a fixed binary vector v of length n with Hamming weight d (having ones in its first d coordinates). Translating any codeword by v changes it by Hamming distance d, so the shifted code F' = F + v must be disjoint from F, which avoids distance d by assumption. Because translation is injective, |F'| = |F|, and since F and F' are disjoint subsets of the ambient space {0, 1}^n of size 2^n, their union has size 2|F| ≤ 2^n, which yields |F| ≤ 2^(n - 1).

  1. The support of the shift vector v consists of the indices strictly less than d.

    The shift vector v is defined by setting the i-th coordinate to 1 if i < d and 0 otherwise. Since an element of Fin 2 is non-zero if and only if it equals 1, the condition v i ≠ 0 is equivalent to i < d. Filtering the universe of indices Fin n for non-zero coordinates therefore yields the set of indices strictly less than d.

    lines 4–12

    uses Finset.mem_filter, Finset.mem_univ, true_and, binary_code_avoids_odd_dist_card_le_shift

    lemma binary_code_avoids_odd_dist_card_le_card_shift (n d : ℕ) (hdn : d ≤ n) :
        (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)).card = d := by
      have h1 : (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)) =
                Finset.univ.filter (fun i : Fin n => (i : ℕ) < d) := by
        ext i
        simp only [Finset.mem_filter, Finset.mem_univ, true_and]
        dsimp [binary_code_avoids_odd_dist_card_le_shift]
        split_ifs with h <;> simp [h]
      rw [h1]
  2. The shift vector v has Hamming weight d (exactly d non-zero coordinates).

    Since d ≤ n, the canonical embedding Fin.castLE maps Finset.univ of Fin d bijectively onto the set of indices in Fin n that are strictly less than d. Rewriting the support of v as the image of Finset.univ under this embedding, its cardinality is given by the cardinality of Fin d, which is d.

    lines 13–27

    uses Fin.castLE, Fin.castLE_injective, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map, Function.Embedding.coeFn_mk, Finset.card_map, Finset.card_univ, Fintype.card_fin

      have h2 : Finset.univ.filter (fun i : Fin n => (i : ℕ) < d) =
          Finset.map ⟨Fin.castLE hdn, Fin.castLE_injective hdn⟩ Finset.univ := by
        ext ⟨i, hi⟩
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map,
          Function.Embedding.coeFn_mk]
        constructor
        · intro h
          refine ⟨⟨i, h⟩, ?_⟩
          ext
          rfl
        · rintro ⟨⟨j, hj⟩, h⟩
          have : j = i := by injection h
          rw [← this]
          exact hj
      rw [h2, Finset.card_map, Finset.card_univ, Fintype.card_fin]
  3. Shifting any binary word by v changes it by Hamming distance d.

    By definition, the Hamming distance between x and x + v is the number of coordinates i where x i ≠ (x + v) i. In Fin 2 = ℤ/2ℤ, adding v i alters the coordinate if and only if v i ≠ 0. Therefore, the distance is the number of non-zero coordinates of v, which was shown in binary_code_avoids_odd_dist_card_le_card_shift to equal d.

    lines 29–37

    uses hammingDist, binary_code_avoids_odd_dist_card_le_card_shift

    lemma binary_code_avoids_odd_dist_card_le_hammingDist_shift (n d : ℕ) (hdn : d ≤ n) (x : Fin n → Fin 2) :
        hammingDist x (x + binary_code_avoids_odd_dist_card_le_shift n d) = d := by
      have h : hammingDist x (x + binary_code_avoids_odd_dist_card_le_shift n d) =
               (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)).card := by
        unfold hammingDist
        congr 1
        ext i
        simp
      rw [h, binary_code_avoids_odd_dist_card_le_card_shift n d hdn]
  4. Define the shift vector v, the translation embedding f(x) = x + v, and the shifted code F' = f(F).

    We define v as the shift vector of length n with d ones. Adding v is injective by additive cancellation (add_left_injective), giving an embedding f. We let F' be the image of F under f.

    lines 40–43

    uses binary_code_avoids_odd_dist_card_le_shift, add_left_injective

    theorem binary_code_avoids_odd_dist_card_le (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (F : Finset (Fin n → Fin 2)) (hF : ∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) : F.card ≤ 2 ^ (n - 1) := by
      let v := binary_code_avoids_odd_dist_card_le_shift n d
      let f : (Fin n → Fin 2) ↪ (Fin n → Fin 2) := ⟨fun x => x + v, add_left_injective v⟩
      let F' := F.map f
  5. The code F and its shifted copy F' are disjoint.

    Suppose for contradiction that an element y belongs to both F and F'. Since y ∈ F', we have y = x + v for some x ∈ F. By binary_code_avoids_odd_dist_card_le_hammingDist_shift, the Hamming distance between x and x + v is d. Since both x and x + v = y belong to F, this contradicts the hypothesis that no two codewords in F have Hamming distance d.

    lines 44–49

    uses Finset.disjoint_left, Finset.mem_map.mp, binary_code_avoids_odd_dist_card_le_hammingDist_shift

      have hdisj : Disjoint F F' := by
        rw [Finset.disjoint_left]
        intro y hy1 hy2
        rcases Finset.mem_map.mp hy2 with ⟨x, hx, rfl⟩
        have hd_eq := binary_code_avoids_odd_dist_card_le_hammingDist_shift n d hdn x
        exact hF x hx (x + v) hy1 hd_eq
  6. The shifted code has |F'| = |F|, their disjoint union has size 2|F|, and the ambient space has size 2^n.

    Because f is an embedding, |F'| = |F| by Finset.card_map. Since F and F' are disjoint, |F ∪ F'| = |F| + |F'| = 2|F| by Finset.card_union_of_disjoint. The union F ∪ F' is a subset of the full space of binary words {0, 1}^n, so its size is at most the total number of words, which is 2^n by Fintype.card_fun and Fintype.card_fin.

    lines 50–54

    uses Finset.card_map, Finset.card_union_of_disjoint, Finset.card_le_univ, Fintype.card_fun, Fintype.card_fin

      have h_card_eq : F'.card = F.card := Finset.card_map f
      have h_union : (F ∪ F').card = F.card + F'.card := Finset.card_union_of_disjoint hdisj
      have h_le_univ : (F ∪ F').card ≤ Fintype.card (Fin n → Fin 2) := Finset.card_le_univ (F ∪ F')
      have h_total : Fintype.card (Fin n → Fin 2) = 2 ^ n := by
        rw [Fintype.card_fun, Fintype.card_fin, Fintype.card_fin]
  7. The cardinality of F is at most 2^(n - 1).

    From the preceding bounds we have 2|F| ≤ 2^n. Using 1 ≤ n, we rewrite 2^n as 2^(n - 1 + 1) = 2^(n - 1) * 2 via Nat.sub_add_cancel and pow_succ. Linear integer arithmetic (omega) then divides by 2 to conclude |F| ≤ 2^(n - 1).

    lines 55–59

    uses Nat.sub_add_cancel, pow_succ

      have h_sum : F.card + F.card ≤ 2 ^ n := by
        omega
      have h_pow : 2 ^ n = 2 ^ (n - 1 + 1) := by rw [Nat.sub_add_cancel hn]
      rw [h_pow, pow_succ] at h_sum
      omega
add_left_injective
In an additive structure with right cancellation, the translation map x ↦ x + a is injective.
binary_code_avoids_odd_dist_card_le_card_shift
For d ≤ n, the shift vector has exactly d non-zero coordinates.
binary_code_avoids_odd_dist_card_le_hammingDist_shift
Translating any binary word x by the shift vector yields a word at Hamming distance d from x.
binary_code_avoids_odd_dist_card_le_shift
The binary vector in {0, 1}^n whose i-th coordinate is 1 when i < d and 0 otherwise.
Fin.castLE
The canonical embedding from Fin n to Fin m when n ≤ m.
Fin.castLE_injective
The embedding Fin.castLE is injective.
Finset.card_le_univ
The cardinality of any finset is at most the cardinality of the ambient finite type.
Finset.card_map
The image of a finset under an embedding has the same cardinality as the original finset.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
Finset.card_univ
The cardinality of Finset.univ for a finite type α equals Fintype.card α.
Finset.disjoint_left
Two finsets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_filter
An element x belongs to s.filter p if and only if x ∈ s and p(x) holds.
Finset.mem_map
An element y belongs to Finset.map f s if and only if y = f(x) for some x ∈ s.
Finset.mem_map.mp
If y ∈ Finset.map f s, then there exists some x ∈ s such that f(x) = y.
Finset.mem_univ
Every element of a finite type belongs to Finset.univ.
Fintype.card_fin
The cardinality of Fin n is n.
Fintype.card_fun
The number of functions from a finite type α to a finite type β is |β|^|α|.
Function.Embedding.coeFn_mk
Coercing an embedding ⟨f, inj⟩ to a function yields f.
hammingDist
The Hamming distance between two vectors, defined as the number of coordinates where they differ.
Nat.sub_add_cancel
For natural numbers with m ≤ n, (n - m) + m = n.
pow_succ
For any base a and natural number n, a^(n + 1) = a^n * a.
true_and
The logical proposition True ∧ p is equivalent to p.

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

def binary_code_avoids_odd_dist_card_le_shift (n d : ℕ) : Fin n → Fin 2 :=  fun i => if (i : ℕ) < d then 1 else 0lemma binary_code_avoids_odd_dist_card_le_card_shift (n d : ℕ) (hdn : d ≤ n) :    (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)).card = d := by  have h1 : (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)) =            Finset.univ.filter (fun i : Fin n => (i : ℕ) < d) := by    ext i    simp only [Finset.mem_filter, Finset.mem_univ, true_and]    dsimp [binary_code_avoids_odd_dist_card_le_shift]    split_ifs with h <;> simp [h]  rw [h1]  have h2 : Finset.univ.filter (fun i : Fin n => (i : ℕ) < d) =      Finset.map ⟨Fin.castLE hdn, Fin.castLE_injective hdn⟩ Finset.univ := by    ext ⟨i, hi⟩    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map,      Function.Embedding.coeFn_mk]    constructor    · intro h      refine ⟨⟨i, h⟩, ?_⟩      ext      rfl    · rintro ⟨⟨j, hj⟩, h⟩      have : j = i := by injection h      rw [← this]      exact hj  rw [h2, Finset.card_map, Finset.card_univ, Fintype.card_fin]lemma binary_code_avoids_odd_dist_card_le_hammingDist_shift (n d : ℕ) (hdn : d ≤ n) (x : Fin n → Fin 2) :    hammingDist x (x + binary_code_avoids_odd_dist_card_le_shift n d) = d := by  have h : hammingDist x (x + binary_code_avoids_odd_dist_card_le_shift n d) =           (Finset.univ.filter (fun i : Fin n => binary_code_avoids_odd_dist_card_le_shift n d i ≠ 0)).card := by    unfold hammingDist    congr 1    ext i    simp  rw [h, binary_code_avoids_odd_dist_card_le_card_shift n d hdn]/-- A binary code in {0,1}^n avoiding a distance d with 1 ≤ d ≤ n has cardinality at most 2^(n-1). -/theorem binary_code_avoids_odd_dist_card_le (n d : ℕ) (hn : 1 ≤ n) (hd : 1 ≤ d) (hdn : d ≤ n) (F : Finset (Fin n → Fin 2)) (hF : ∀ x ∈ F, ∀ y ∈ F, hammingDist x y ≠ d) : F.card ≤ 2 ^ (n - 1) := by  let v := binary_code_avoids_odd_dist_card_le_shift n d  let f : (Fin n → Fin 2) ↪ (Fin n → Fin 2) := ⟨fun x => x + v, add_left_injective v⟩  let F' := F.map f  have hdisj : Disjoint F F' := by    rw [Finset.disjoint_left]    intro y hy1 hy2    rcases Finset.mem_map.mp hy2 with ⟨x, hx, rfl⟩    have hd_eq := binary_code_avoids_odd_dist_card_le_hammingDist_shift n d hdn x    exact hF x hx (x + v) hy1 hd_eq  have h_card_eq : F'.card = F.card := Finset.card_map f  have h_union : (F ∪ F').card = F.card + F'.card := Finset.card_union_of_disjoint hdisj  have h_le_univ : (F ∪ F').card ≤ Fintype.card (Fin n → Fin 2) := Finset.card_le_univ (F ∪ F')  have h_total : Fintype.card (Fin n → Fin 2) = 2 ^ n := by    rw [Fintype.card_fun, Fintype.card_fin, Fintype.card_fin]  have h_sum : F.card + F.card ≤ 2 ^ n := by    omega  have h_pow : 2 ^ n = 2 ^ (n - 1 + 1) := by rw [Nat.sub_add_cancel hn]  rw [h_pow, pow_succ] at h_sum  omega
See it in the graphDiscuss this resultChallenge it