AFTD Auto-Formalizing Theoretical Domains

hammingDist_eq_of_codeword_supp_inter_singleton

theoremverified

Let $\alpha$ be an alphabet with decidable equality and zero element $0$. For any two codewords $x, y : \mathrm{Fin}\, n \to \alpha$ whose supports intersect in a singleton $\mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y) = \{i\}$, their Hamming distance is $\mathrm{hammingDist}(x, y) = (\mathrm{codeword\_supp}(x)).\mathrm{card} + (\mathrm{codeword\_supp}(y)).\mathrm{card} - 2 + (\mathrm{if}\ x\ i = y\ i\ \mathrm{then}\ 0\ \mathrm{else}\ 1)$.

Statement

theorem hammingDist_eq_of_codeword_supp_inter_singleton
    {n : ℕ} {α : Type*} [DecidableEq α] [Zero α]
    (x y : Fin n → α) (i : Fin n)
    (h_inter : codeword_supp x ∩ codeword_supp y = {i}) :
    hammingDist x y = (codeword_supp x).card + (codeword_supp y).card - 2 +
      (if x i = y i then 0 else 1)
Source
arXiv:2610.30613, Lemma 2.1
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • codeword_suppThe support of a codeword $x : \mathrm{Fin}\, n \to \alpha$ over an alphabet $\alpha$ with decidable equality and zero is the finite set…
Used by 1

Read back from the Lean

For any natural number $n$, any type $\alpha$ with decidable equality and a zero element, any two vectors $x, y : \mathrm{Fin}\ n \to \alpha$, and any index $i : \mathrm{Fin}\ n$, if the intersection of the supports of $x$ and $y$ (the set of indices where both are non-zero) is the singleton $\{i\}$, then the Hamming distance between $x$ and $y$ equals the size of the support of $x$ plus the size of the support of $y$ minus 2, plus 0 if $x(i) = y(i)$ and 1 if $x(i) \neq y(i)$ (using natural number subtraction).

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 proof computes the Hamming distance between two codewords by partitioning the set of coordinates where they disagree into three pairwise disjoint sets: coordinates where only $x$ is non-zero, coordinates where only $y$ is non-zero, and the singleton coordinate $\{i\}$ where both are non-zero (if $x\ i \ne y\ i$). Since the supports overlap solely at $\{i\}$, the two set-difference parts have cardinalities $|\mathrm{supp}(x)| - 1$ and $|\mathrm{supp}(y)| - 1$, while the singleton contributes $0$ if $x\ i = y\ i$ and $1$ if $x\ i \ne y\ i$. Summing the sizes of these disjoint components and simplifying via integer arithmetic yields the stated formula.

  1. The set of coordinates where $x$ and $y$ disagree partitions into three disjoint sets: coordinates where only $x$ is non-zero, coordinates where only $y$ is non-zero, and coordinates where both are non-zero but distinct.

    By set extensionality (`ext j`), an index $j$ satisfies $x\ j \ne y\ j$ if and only if it belongs to $(\mathrm{codeword\_supp}(x) \setminus \mathrm{codeword\_supp}(y)) \cup (\mathrm{codeword\_supp}(y) \setminus \mathrm{codeword\_supp}(x)) \cup \{j \in \mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y) \mid x\ j \ne y\ j\}$. Simplifying set memberships into non-zero assertions, a case split on whether $x\ j = 0$ and $y\ j = 0$ places any disagreeing coordinate into one of the three components. Conversely, coordinates in any of the three components have differing values.

    lines 8–27

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_sdiff, Finset.mem_inter, codeword_supp, ne_eq, not_not, Or.inl, Or.inr

      have hset : (Finset.univ.filter (fun j => x j ≠ y j) : Finset (Fin n))
          = (codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x)
            ∪ ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) := by
        ext j
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union,
          Finset.mem_sdiff, Finset.mem_inter, codeword_supp, ne_eq, not_not]
        constructor
        · intro h
          by_cases hx : x j = 0
          · by_cases hy : y j = 0
            · exact absurd (by rw [hx, hy]) h
            · exact Or.inl (Or.inr ⟨hy, hx⟩)
          · by_cases hy : y j = 0
            · exact Or.inl (Or.inl ⟨hx, hy⟩)
            · exact Or.inr ⟨⟨hx, hy⟩, h⟩
        · intro hmem
          rcases hmem with (⟨hx, hy⟩ | ⟨hy, hx⟩) | ⟨⟨_, _⟩, h⟩
          · exact fun e => hx (e.trans hy)
          · exact fun e => hy (e.symm.trans hx)
          · exact h
  2. The index $i$ belongs to the intersection of the supports, the intersection has cardinality $1$, and each support has cardinality at least $1$.

    Since $\mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y) = \{i\}$, $i$ is in the intersection and its cardinality is $1$. Because $i$ is in both $\mathrm{codeword\_supp}(x)$ and $\mathrm{codeword\_supp}(y)$, neither support is empty, so each has cardinality at least $1$.

    lines 28–34

    uses Finset.card_pos.2, Finset.mem_inter.mp

      have hi : i ∈ codeword_supp x ∩ codeword_supp y := by rw [h_inter]; simp
      have hcard_inter : (codeword_supp x ∩ codeword_supp y).card = 1 := by
        rw [h_inter]; simp
      have hAx : 1 ≤ (codeword_supp x).card :=
        Finset.card_pos.2 ⟨i, (Finset.mem_inter.mp hi).1⟩
      have hBy : 1 ≤ (codeword_supp y).card :=
        Finset.card_pos.2 ⟨i, (Finset.mem_inter.mp hi).2⟩
  3. The set differences have sizes $(\mathrm{codeword\_supp}(x)).\mathrm{card} - 1$ and $(\mathrm{codeword\_supp}(y)).\mathrm{card} - 1$, and the filtered intersection has size $0$ if $x\ i = y\ i$ and $1$ if $x\ i \ne y\ i$.

    By `Finset.card_sdiff`, $|A \setminus B| = |A| - |A \cap B|$; since the intersection has size $1$, each difference has size one less than the respective support. Because the intersection is the singleton $\{i\}$, filtering it on $x\ j \ne y\ j$ gives $\{i\}$ if $x\ i \ne y\ i$ and $\emptyset$ if $x\ i = y\ i$, which have sizes $1$ and $0$ respectively.

    lines 35–42

    uses Finset.card_sdiff, Finset.inter_comm, Finset.filter_singleton

      have h1 : (codeword_supp x \ codeword_supp y).card = (codeword_supp x).card - 1 := by
        rw [Finset.card_sdiff, Finset.inter_comm, hcard_inter]
      have h2 : (codeword_supp y \ codeword_supp x).card = (codeword_supp y).card - 1 := by
        rw [Finset.card_sdiff, hcard_inter]
      have h3 : ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)).card
          = (if x i = y i then 0 else 1) := by
        rw [h_inter, Finset.filter_singleton]
        by_cases h : x i = y i <;> simp [h]
  4. The three component sets partitioning the disagreement set are pairwise disjoint.

    The filtered intersection is a subset of $\mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y)$ by `Finset.filter_subset`. The differences $\mathrm{codeword\_supp}(x) \setminus \mathrm{codeword\_supp}(y)$ and $\mathrm{codeword\_supp}(y) \setminus \mathrm{codeword\_supp}(x)$ cannot share an element, as membership in one requires non-membership in the other's support. Furthermore, neither difference can intersect the intersection of the supports.

    lines 43–58

    uses Finset.filter_subset, Finset.disjoint_left, Finset.mem_sdiff.mp, Finset.mem_union.mp, Finset.mem_inter.mp

      have hCsub : ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j))
          ⊆ codeword_supp x ∩ codeword_supp y := Finset.filter_subset _ _
      have hd12 : Disjoint (codeword_supp x \ codeword_supp y)
          (codeword_supp y \ codeword_supp x) := by
        rw [Finset.disjoint_left]
        intro a ha hb
        exact (Finset.mem_sdiff.mp hb).2 (Finset.mem_sdiff.mp ha).1
      have hd3 : Disjoint ((codeword_supp x \ codeword_supp y) ∪
          (codeword_supp y \ codeword_supp x))
          ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) := by
        rw [Finset.disjoint_left]
        intro a ha hb
        have hb' := hCsub hb
        rcases Finset.mem_union.mp ha with ha' | ha'
        · exact (Finset.mem_sdiff.mp ha').2 (Finset.mem_inter.mp hb').2
        · exact (Finset.mem_sdiff.mp ha').2 (Finset.mem_inter.mp hb').1
  5. The cardinality of the union of the three components is $(\mathrm{codeword\_supp}(x)).\mathrm{card} - 1 + ((\mathrm{codeword\_supp}(y)).\mathrm{card} - 1) + (\mathrm{if}\ x\ i = y\ i\ \mathrm{then}\ 0\ \mathrm{else}\ 1)$.

    Because the components are pairwise disjoint, `Finset.card_union_of_disjoint` applies twice to express the cardinality of the union as the sum of the cardinalities of the three components, which are then replaced by their previously established formulas.

    lines 59–63

    uses Finset.card_union_of_disjoint

      have hcard : ((codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x)
          ∪ ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j))).card
          = (codeword_supp x).card - 1 + ((codeword_supp y).card - 1) +
            (if x i = y i then 0 else 1) := by
        rw [Finset.card_union_of_disjoint hd3, Finset.card_union_of_disjoint hd12, h1, h2, h3]
  6. The Hamming distance between $x$ and $y$ equals $(\mathrm{codeword\_supp}(x)).\mathrm{card} + (\mathrm{codeword\_supp}(y)).\mathrm{card} - 2 + (\mathrm{if}\ x\ i = y\ i\ \mathrm{then}\ 0\ \mathrm{else}\ 1)$. automation

    By definition, $\mathrm{hammingDist}(x, y)$ is the number of coordinates where $x$ and $y$ disagree. Substituting the partition and its cardinality reduces the claim to the identity $(a - 1) + (b - 1) + c = a + b - 2 + c$. Since $a \ge 1$ and $b \ge 1$ were established in earlier steps, no underflow occurs in $\mathbb{N}$, and `omega` closes the goal by linear arithmetic.

    lines 64–67

      have hh : hammingDist x y
          = (Finset.univ.filter (fun j => x j ≠ y j) : Finset (Fin n)).card := rfl
      rw [hh, hset, hcard]
      omega
Finset.mem_filter
An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set `Finset.univ`.
true_and
The conjunction `True ∧ p` is logically equivalent to `p`.
Finset.mem_union
An element belongs to the union `s ∪ t` if and only if it belongs to `s` or to `t`.
Finset.mem_sdiff
An element belongs to the set difference `s \ t` if and only if it belongs to `s` and does not belong to `t`.
Finset.mem_inter
An element belongs to the intersection `s ∩ t` if and only if it belongs to `s` and to `t`.
codeword_supp
The support of a codeword `x` is defined as the set of indices `j` where `x j ≠ 0`.
ne_eq
The inequality `a ≠ b` is definitionally `¬(a = b)`.
not_not
Double negation elimination: `¬¬a` is equivalent to `a`.
Or.inl
Injects a proof of `a` into the left branch of a disjunction `a ∨ b`.
Or.inr
Injects a proof of `b` into the right branch of a disjunction `a ∨ b`.
Finset.card_pos.2
A finite set containing an element has cardinality at least 1.
Finset.mem_inter.mp
If an element belongs to `s ∩ t`, then it belongs to `s` and to `t`.
Finset.card_sdiff
The cardinality of `t \ s` equals `t.card - (s ∩ t).card`.
Finset.inter_comm
Intersection of finite sets is commutative: `s₁ ∩ s₂ = s₂ ∩ s₁`.
Finset.filter_singleton
Filtering a singleton set `{a}` with predicate `p` yields `{a}` if `p a` is true, and `∅` otherwise.
Finset.filter_subset
Filtering a finite set produces a subset of the original finite set: `Finset.filter p s ⊆ s`.
Finset.disjoint_left
Two finite sets `s` and `t` are disjoint if and only if no element of `s` belongs to `t`.
Finset.mem_sdiff.mp
If an element belongs to `s \ t`, then it belongs to `s` and does not belong to `t`.
Finset.mem_union.mp
If an element belongs to `s ∪ t`, then it belongs to `s` or to `t`.
Finset.card_union_of_disjoint
If two finite sets are disjoint, the cardinality of their union is the sum of their cardinalities.

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

/-- Hamming distance formula for two codewords whose supports intersect at a single coordinate. -/theorem hammingDist_eq_of_codeword_supp_inter_singleton    {n : ℕ} {α : Type*} [DecidableEq α] [Zero α]    (x y : Fin n → α) (i : Fin n)    (h_inter : codeword_supp x ∩ codeword_supp y = {i}) :    hammingDist x y = (codeword_supp x).card + (codeword_supp y).card - 2 +      (if x i = y i then 0 else 1) := by  have hset : (Finset.univ.filter (fun j => x j ≠ y j) : Finset (Fin n))      = (codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x)        ∪ ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) := by    ext j    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union,      Finset.mem_sdiff, Finset.mem_inter, codeword_supp, ne_eq, not_not]    constructor    · intro h      by_cases hx : x j = 0      · by_cases hy : y j = 0        · exact absurd (by rw [hx, hy]) h        · exact Or.inl (Or.inr ⟨hy, hx⟩)      · by_cases hy : y j = 0        · exact Or.inl (Or.inl ⟨hx, hy⟩)        · exact Or.inr ⟨⟨hx, hy⟩, h⟩    · intro hmem      rcases hmem with (⟨hx, hy⟩ | ⟨hy, hx⟩) | ⟨⟨_, _⟩, h⟩      · exact fun e => hx (e.trans hy)      · exact fun e => hy (e.symm.trans hx)      · exact h  have hi : i ∈ codeword_supp x ∩ codeword_supp y := by rw [h_inter]; simp  have hcard_inter : (codeword_supp x ∩ codeword_supp y).card = 1 := by    rw [h_inter]; simp  have hAx : 1 ≤ (codeword_supp x).card :=    Finset.card_pos.2 ⟨i, (Finset.mem_inter.mp hi).1⟩  have hBy : 1 ≤ (codeword_supp y).card :=    Finset.card_pos.2 ⟨i, (Finset.mem_inter.mp hi).2⟩  have h1 : (codeword_supp x \ codeword_supp y).card = (codeword_supp x).card - 1 := by    rw [Finset.card_sdiff, Finset.inter_comm, hcard_inter]  have h2 : (codeword_supp y \ codeword_supp x).card = (codeword_supp y).card - 1 := by    rw [Finset.card_sdiff, hcard_inter]  have h3 : ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)).card      = (if x i = y i then 0 else 1) := by    rw [h_inter, Finset.filter_singleton]    by_cases h : x i = y i <;> simp [h]  have hCsub : ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j))      ⊆ codeword_supp x ∩ codeword_supp y := Finset.filter_subset _ _  have hd12 : Disjoint (codeword_supp x \ codeword_supp y)      (codeword_supp y \ codeword_supp x) := by    rw [Finset.disjoint_left]    intro a ha hb    exact (Finset.mem_sdiff.mp hb).2 (Finset.mem_sdiff.mp ha).1  have hd3 : Disjoint ((codeword_supp x \ codeword_supp y) ∪      (codeword_supp y \ codeword_supp x))      ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j)) := by    rw [Finset.disjoint_left]    intro a ha hb    have hb' := hCsub hb    rcases Finset.mem_union.mp ha with ha' | ha'    · exact (Finset.mem_sdiff.mp ha').2 (Finset.mem_inter.mp hb').2    · exact (Finset.mem_sdiff.mp ha').2 (Finset.mem_inter.mp hb').1  have hcard : ((codeword_supp x \ codeword_supp y) ∪ (codeword_supp y \ codeword_supp x)      ∪ ((codeword_supp x ∩ codeword_supp y).filter (fun j => x j ≠ y j))).card      = (codeword_supp x).card - 1 + ((codeword_supp y).card - 1) +        (if x i = y i then 0 else 1) := by    rw [Finset.card_union_of_disjoint hd3, Finset.card_union_of_disjoint hd12, h1, h2, h3]  have hh : hammingDist x y      = (Finset.univ.filter (fun j => x j ≠ y j) : Finset (Fin n)).card := rfl  rw [hh, hset, hcard]  omega
See it in the graphDiscuss this resultChallenge it