AFTD Auto-Formalizing Theoretical Domains

hamming_dist_eq_exceptional_add_all_distinct

theoremverified

For vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$, the Hamming distance $\mathrm{hammingDist}(x, y)$ equals the number of coordinates where $x$ is exceptional, plus the number where $y$ is exceptional, plus the number where all three coordinates are distinct.

Statement

theorem hamming_dist_eq_exceptional_add_all_distinct {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :
    hammingDist x y =
      (hamming_exceptional_coords x y z).card +
      (hamming_exceptional_coords y x z).card +
      (hamming_all_distinct_coords x y z).card
Source
arXiv:2610.32789 "Triangle-Free Sets in Exact-Distance Hamming Graphs", Proposition 2.2
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

Read back from the Lean

For any natural number $n$, any type $\alpha$ with decidable equality, and any three functions $x, y, z : \mathrm{Fin}\; n \to \alpha$, the Hamming distance between $x$ and $y$ equals the sum of: 1. the number of coordinates $i$ where $y(i) = z(i)$ and $x(i) \neq y(i)$ (hamming_exceptional_coords x y z), 2. the number of coordinates $i$ where $x(i) = z(i)$ and $y(i) \neq x(i)$ (hamming_exceptional_coords y x z), and 3. the number of coordinates $i$ where $x(i)$, $y(i)$, and $z(i)$ are all pairwise distinct (hamming_all_distinct_coords x y z).

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 partitions the set of coordinates where $x$ and $y$ differ into three pairwise disjoint subsets: indices where $x$ is exceptional ($y_i = z_i$ and $x_i \ne y_i$), indices where $y$ is exceptional ($x_i = z_i$ and $y_i \ne x_i$), and indices where all three vectors differ. This decomposition is established by a propositional equivalence showing that whenever $x_i \ne y_i$, exactly one of these three cases occurs. Since the three subsets are mutually disjoint, the Hamming distance—defined as the number of coordinates where $x_i \ne y_i$—equals the sum of their cardinalities by additivity of set size over disjoint unions.

  1. For any three elements $a, b, c \in \alpha$, $a \ne b$ holds if and only if either ($b = c$ and $a \ne b$), ($a = c$ and $b \ne a$), or all three are pairwise distinct. automation

    This is an exhaustive propositional case analysis: whenever $a \ne b$, the third element $c$ must equal $b$, equal $a$, or differ from both. The equivalence is established by propositional logic via `tauto`.

    lines 7–9

      have prop_equiv (a b c : α) :
          (a ≠ b) ↔ ((b = c ∧ a ≠ b) ∨ (a = c ∧ b ≠ a)) ∨ (a ≠ b ∧ a ≠ c ∧ b ≠ c) := by
        tauto
  2. The set of coordinates where $x$ and $y$ differ is the union of the coordinates where $x$ is exceptional, where $y$ is exceptional, and where all three vectors differ.

    Applying the coordinate-wise equivalence `prop_equiv` across the universe of coordinates via `Finset.filter_congr` rewrites the condition $x_i \ne y_i$ into the three-way disjunction. Distributing the filter over disjunctions using `Finset.filter_or` expresses the set as the union of the three filtered subsets, which match the definitions of the exceptional and all-distinct coordinate sets.

    lines 10–18

    uses Finset.filter_congr, Finset.filter_or

      have h_split : (Finset.filter (fun i => x i ≠ y i) (Finset.univ : Finset (Fin n))) =
          (hamming_exceptional_coords x y z ∪ hamming_exceptional_coords y x z) ∪
          hamming_all_distinct_coords x y z := by
        have h_congr : (Finset.filter (fun i => x i ≠ y i) (Finset.univ : Finset (Fin n))) =
            Finset.filter (fun i => ((y i = z i ∧ x i ≠ y i) ∨ (x i = z i ∧ y i ≠ x i)) ∨
              (x i ≠ y i ∧ x i ≠ z i ∧ y i ≠ z i)) Finset.univ :=
          Finset.filter_congr (fun i _ => prop_equiv (x i) (y i) (z i))
        rw [h_congr, Finset.filter_or, Finset.filter_or]
        rfl
  3. The coordinates where $x$ is exceptional and the coordinates where $y$ is exceptional are disjoint.

    By `Finset.disjoint_filter`, two filtered sets are disjoint if no coordinate satisfies both predicates. If an index $i$ were in both sets, we would have $y_i = z_i$ and $x_i = z_i$, which together imply $x_i = y_i$, contradicting the assumption $x_i \ne y_i$ in the definition of exceptional coordinates for $x$.

    lines 19–23

    uses Finset.disjoint_filter

      have disj1 : Disjoint (hamming_exceptional_coords x y z) (hamming_exceptional_coords y x z) := by
        rw [hamming_exceptional_coords, hamming_exceptional_coords, Finset.disjoint_filter]
        intro i _ ⟨hyz, hxy⟩ ⟨hxz, _⟩
        apply hxy
        rw [hyz, hxz]
  4. The union of both exceptional coordinate sets is disjoint from the set of all-distinct coordinates.

    Using `Finset.disjoint_union_left`, it suffices to verify disjointness for each exceptional set separately. If $x$ is exceptional at $i$, then $y_i = z_i$, contradicting the requirement $y_i \ne z_i$ of all-distinct coordinates. Similarly, if $y$ is exceptional at $i$, then $x_i = z_i$, contradicting $x_i \ne z_i$.

    lines 24–33

    uses Finset.disjoint_union_left, Finset.disjoint_filter

      have disj2 : Disjoint (hamming_exceptional_coords x y z ∪ hamming_exceptional_coords y x z)
          (hamming_all_distinct_coords x y z) := by
        rw [Finset.disjoint_union_left]
        constructor
        · rw [hamming_exceptional_coords, hamming_all_distinct_coords, Finset.disjoint_filter]
          intro i _ ⟨hyz, _⟩ ⟨_, _, hyz'⟩
          exact hyz' hyz
        · rw [hamming_exceptional_coords, hamming_all_distinct_coords, Finset.disjoint_filter]
          intro i _ ⟨hxz, _⟩ ⟨_, hxz', _⟩
          exact hxz' hxz
  5. The Hamming distance $\mathrm{hammingDist}(x, y)$ equals the sum of the cardinalities of the three coordinate sets.

    By definition, $\mathrm{hammingDist}(x, y)$ is the number of coordinates where $x_i \ne y_i$. Rewriting this set via the partition `h_split` and applying `Finset.card_union_of_disjoint` twice using the disjointness facts `disj2` and `disj1` converts the cardinality of the union into the sum of the three individual cardinalities.

    lines 34–35

    uses Finset.card_union_of_disjoint

      change (Finset.filter (fun i => x i ≠ y i) Finset.univ).card = _
      rw [h_split, Finset.card_union_of_disjoint disj2, Finset.card_union_of_disjoint disj1]
Finset.filter_congr
If two predicates are equivalent on every element of a finite set, then filtering by either predicate produces the same subset.
Finset.filter_or
Filtering a finite set by a disjunction of two predicates is equal to the union of the two individually filtered sets.
Finset.disjoint_filter
Two subsets formed by filtering a common finite set are disjoint if and only if no element satisfies both predicates simultaneously.
Finset.disjoint_union_left
A union of two sets is disjoint from a third set if and only if each of the two sets is disjoint from the third.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their individual 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

/-- The Hamming distance between x and y is the sum of exceptional coordinates for x, exceptional coordinates for y, and all-distinct coordinates. -/theorem hamming_dist_eq_exceptional_add_all_distinct {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :    hammingDist x y =      (hamming_exceptional_coords x y z).card +      (hamming_exceptional_coords y x z).card +      (hamming_all_distinct_coords x y z).card := by  have prop_equiv (a b c : α) :      (a ≠ b) ↔ ((b = c ∧ a ≠ b) ∨ (a = c ∧ b ≠ a)) ∨ (a ≠ b ∧ a ≠ c ∧ b ≠ c) := by    tauto  have h_split : (Finset.filter (fun i => x i ≠ y i) (Finset.univ : Finset (Fin n))) =      (hamming_exceptional_coords x y z ∪ hamming_exceptional_coords y x z) ∪      hamming_all_distinct_coords x y z := by    have h_congr : (Finset.filter (fun i => x i ≠ y i) (Finset.univ : Finset (Fin n))) =        Finset.filter (fun i => ((y i = z i ∧ x i ≠ y i) ∨ (x i = z i ∧ y i ≠ x i)) ∨          (x i ≠ y i ∧ x i ≠ z i ∧ y i ≠ z i)) Finset.univ :=      Finset.filter_congr (fun i _ => prop_equiv (x i) (y i) (z i))    rw [h_congr, Finset.filter_or, Finset.filter_or]    rfl  have disj1 : Disjoint (hamming_exceptional_coords x y z) (hamming_exceptional_coords y x z) := by    rw [hamming_exceptional_coords, hamming_exceptional_coords, Finset.disjoint_filter]    intro i _ ⟨hyz, hxy⟩ ⟨hxz, _⟩    apply hxy    rw [hyz, hxz]  have disj2 : Disjoint (hamming_exceptional_coords x y z ∪ hamming_exceptional_coords y x z)      (hamming_all_distinct_coords x y z) := by    rw [Finset.disjoint_union_left]    constructor    · rw [hamming_exceptional_coords, hamming_all_distinct_coords, Finset.disjoint_filter]      intro i _ ⟨hyz, _⟩ ⟨_, _, hyz'⟩      exact hyz' hyz    · rw [hamming_exceptional_coords, hamming_all_distinct_coords, Finset.disjoint_filter]      intro i _ ⟨hxz, _⟩ ⟨_, hxz', _⟩      exact hxz' hxz  change (Finset.filter (fun i => x i ≠ y i) Finset.univ).card = _  rw [h_split, Finset.card_union_of_disjoint disj2, Finset.card_union_of_disjoint disj1]
See it in the graphDiscuss this resultChallenge it