AFTD Auto-Formalizing Theoretical Domains

hamming_equilateral_triangle_local_types

theoremverifiedformalization

Suppose $x, y, z : \mathrm{Fin}\, n \to \alpha$ satisfy $\mathrm{hammingDist}(x, y) = r$, $\mathrm{hammingDist}(x, z) = r$, and $\mathrm{hammingDist}(y, z) = r$. If $a_x, a_y, a_z$ count the coordinates where $x, y, z$ respectively are exceptional and $d$ counts the coordinates where all three symbols are distinct, then $a_x = a_y$, $a_x = a_z$, $2a_x + d = r$, $a_x \le r / 2$, $d = r - 2a_x$, and the size of the active support is $r + a_x$.

Statement

theorem hamming_equilateral_triangle_local_types {n : ℕ} {α : Type*} [DecidableEq α]
    (x y z : Fin n → α) (r : ℕ)
    (hxy : hammingDist x y = r)
    (hxz : hammingDist x z = r)
    (hyz : hammingDist y z = r) :
    let ax := (hamming_exceptional_coords x y z).card
    let ay := (hamming_exceptional_coords y x z).card
    let az := (hamming_exceptional_coords z x y).card
    let d := (hamming_all_distinct_coords x y z).card
    ax = ay ∧ ax = az ∧ 2 * ax + d = r ∧ ax ≤ r / 2 ∧ d = r - 2 * ax ∧
      (hamming_active_coords x y z).card = r + ax
Formalizes
arXiv:2610.32789 "Triangle-Free Sets in Exact-Distance Hamming Graphs", Proposition 2.2
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • hamming_active_coordsFor vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$ over an alphabet $\alpha$ with decidable equality,…
  • hamming_exceptional_coordsFor vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$ over an alphabet $\alpha$ with decidable equality,…
  • hamming_all_distinct_coordsFor vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$ over an alphabet $\alpha$ with decidable equality,…
  • hamming_dist_eq_exceptional_add_all_distinctFor vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$, the Hamming distance $\mathrm{hammingDist}(x, y)$ equals the number of coordinates…
  • hamming_active_coords_cardFor vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$, the number of active coordinates is the sum of the coordinates where $x$ is…

Read back from the Lean

For any natural number $n$, any type $\alpha$ with decidable equality, any three vectors $x, y, z \in \alpha^n$ (represented as functions Fin n → α), and any natural number $r$: Assume that all pairwise Hamming distances between $x$, $y$, and $z$ are equal to $r$ (that is, $\text{hammingDist}(x, y) = r$, $\text{hammingDist}(x, z) = r$, and $\text{hammingDist}(y, z) = r$). Define: - $a_x$ to be the number of coordinates $i \in \{0, \dots, n-1\}$ where $y(i) = z(i)$ and $x(i) \ne y(i)$, - $a_y$ to be the number of coordinates $i \in \{0, \dots, n-1\}$ where $x(i) = z(i)$ and $y(i) \ne x(i)$, - $a_z$ to be the number of coordinates $i \in \{0, \dots, n-1\}$ where $x(i) = y(i)$ and $z(i) \ne x(i)$, and - $d$ to be the number of coordinates $i \in \{0, \dots, n-1\}$ where $x(i)$, $y(i)$, and $z(i)$ are mutually distinct. Then all of the following hold: 1. $a_x = a_y$, 2. $a_x = a_z$, 3. $2 \cdot a_x + d = r$, 4. $a_x \le \lfloor r / 2 \rfloor$ (natural number division), 5. $d = r - 2 \cdot a_x$, and 6. the number of coordinates $i \in \{0, \dots, n-1\}$ where not all three elements $x(i), y(i), z(i)$ are equal (i.e., $\neg(x(i) = y(i) \wedge y(i) = z(i))$) equals $r + a_x$.

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

In a Hamming graph, the distance between any two vertices decomposes into the sum of their individual exceptional coordinate counts and the count of coordinates where all three vertices differ. Applying this decomposition to the three pairs of an equilateral triangle with side length $r$ yields the symmetric linear system $a_x + a_y + d = r$, $a_x + a_z + d = r$, and $a_y + a_z + d = r$. Subtracting these equations gives $a_x = a_y = a_z$, from which $2a_x + d = r$, $a_x \le r/2$, and $d = r - 2a_x$ follow by linear arithmetic. Finally, the active support size decomposes as $a_x + a_y + a_z + d = (a_x + a_y + d) + a_z = r + a_x$.

  1. The set of exceptional coordinates is invariant under swapping the other two vectors.

    Three helper lemmas (`hamming_equilateral_triangle_local_types_exceptional_swap`, `hamming_equilateral_triangle_local_types_exceptional_swap'`, and `hamming_equilateral_triangle_local_types_exceptional_swap23`) establish that `hamming_exceptional_coords` is symmetric in its second and third arguments. By definition, a coordinate $i$ belongs to `hamming_exceptional_coords a b c` when $b(i) = c(i)$ and $a(i) \ne b(i)$; by symmetry of equality and transitivity, this condition is equivalent to $c(i) = b(i)$ and $a(i) \ne c(i)$.

    lines 1–21

    private lemma hamming_equilateral_triangle_local_types_exceptional_swap {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :
        hamming_exceptional_coords x z y = hamming_exceptional_coords x y z := by
      simp only [hamming_exceptional_coords]
      congr 1
      ext i
      constructor <;> rintro ⟨h1, h2⟩ <;> exact ⟨h1.symm, fun h => h2 (h.trans h1.symm)⟩
    
    private lemma hamming_equilateral_triangle_local_types_exceptional_swap' {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :
        hamming_exceptional_coords y z x = hamming_exceptional_coords y x z := by
      simp only [hamming_exceptional_coords]
      congr 1
      ext i
      constructor <;> rintro ⟨h1, h2⟩ <;> exact ⟨h1.symm, fun h => h2 (h.trans h1.symm)⟩
    
    private lemma hamming_equilateral_triangle_local_types_exceptional_swap23 {n : ℕ} {α : Type*} [DecidableEq α] (a b c : Fin n → α) :
        hamming_exceptional_coords a b c = hamming_exceptional_coords a c b := by
      simp only [hamming_exceptional_coords]
      congr 1
      ext i
      constructor <;> rintro ⟨h1, h2⟩ <;> exact ⟨h1.symm, fun h => h2 (h.trans h1.symm)⟩
    
  2. The set of coordinates where all three vectors differ is invariant under swapping the last two vectors and under cyclic permutation.

    Two helper lemmas (`hamming_equilateral_triangle_local_types_all_distinct_swap` and `hamming_equilateral_triangle_local_types_all_distinct_swap'`) show that `hamming_all_distinct_coords` is unchanged under swapping its second and third arguments or under cyclic shift. In each case, the condition that $x(i), y(i), z(i)$ are pairwise distinct is symmetric under permutations of the vectors.

    lines 22–43

    private lemma hamming_equilateral_triangle_local_types_all_distinct_swap {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :
        hamming_all_distinct_coords x z y = hamming_all_distinct_coords x y z := by
      simp only [hamming_all_distinct_coords]
      congr 1
      ext i
      constructor
      · rintro ⟨h1, h2, h3⟩
        exact ⟨h2, h1, fun h => h3 h.symm⟩
      · rintro ⟨h1, h2, h3⟩
        exact ⟨h2, h1, fun h => h3 h.symm⟩
    
    private lemma hamming_equilateral_triangle_local_types_all_distinct_swap' {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :
        hamming_all_distinct_coords y z x = hamming_all_distinct_coords x y z := by
      simp only [hamming_all_distinct_coords]
      congr 1
      ext i
      constructor
      · rintro ⟨h1, h2, h3⟩
        exact ⟨fun h => h2 h.symm, fun h => h3 h.symm, h1⟩
      · rintro ⟨h1, h2, h3⟩
        exact ⟨h3, fun h => h1 h.symm, fun h => h2 h.symm⟩
    
  3. Introduce shorthand names $a_x, a_y, a_z$ for the exceptional coordinate counts and $d$ for the all-distinct coordinate count.

    The proof simplifies the goal and defines $a_x, a_y, a_z$ as the sizes of the sets of coordinates where $x, y, z$ respectively are the unique differing vector, and $d$ as the size of the set where all three vectors are mutually distinct.

    lines 44–60

    /-- Classification of local types in equilateral triangles of Hamming graphs: equal exceptional counts a, 2a + d = r, a ≤ r / 2, d = r - 2a, and active support size r + a. -/
    theorem hamming_equilateral_triangle_local_types {n : ℕ} {α : Type*} [DecidableEq α]
        (x y z : Fin n → α) (r : ℕ)
        (hxy : hammingDist x y = r)
        (hxz : hammingDist x z = r)
        (hyz : hammingDist y z = r) :
        let ax := (hamming_exceptional_coords x y z).card
        let ay := (hamming_exceptional_coords y x z).card
        let az := (hamming_exceptional_coords z x y).card
        let d := (hamming_all_distinct_coords x y z).card
        ax = ay ∧ ax = az ∧ 2 * ax + d = r ∧ ax ≤ r / 2 ∧ d = r - 2 * ax ∧
          (hamming_active_coords x y z).card = r + ax := by
      dsimp only
      set ax := (hamming_exceptional_coords x y z).card with hax
      set ay := (hamming_exceptional_coords y x z).card with hay
      set az := (hamming_exceptional_coords z x y).card with haz
      set d := (hamming_all_distinct_coords x y z).card with hd
  4. $a_x + a_y + d = r$.

    By `hamming_dist_eq_exceptional_add_all_distinct`, the Hamming distance $\mathrm{hammingDist}(x, y)$ equals the sum of the counts of coordinates where $x$ is exceptional, where $y$ is exceptional, and where all three vectors differ. Since $\mathrm{hammingDist}(x, y) = r$, this yields $a_x + a_y + d = r$.

    lines 61–63

    uses hamming_dist_eq_exceptional_add_all_distinct

      have h1 : ax + ay + d = r := by
        rw [hax, hay, hd, ← hxy]
        exact (hamming_dist_eq_exceptional_add_all_distinct x y z).symm
  5. $a_x + a_z + d = r$.

    Applying `hamming_dist_eq_exceptional_add_all_distinct` to the triple $(x, z, y)$ expresses $\mathrm{hammingDist}(x, z)$ as the sum of coordinates where $x$ is exceptional, coordinates where $z$ is exceptional, and coordinates where all three differ. Using `hamming_equilateral_triangle_local_types_exceptional_swap` and `hamming_equilateral_triangle_local_types_all_distinct_swap` to rewrite these counts as $a_x$ and $d$, and using $\mathrm{hammingDist}(x, z) = r$, we obtain $a_x + a_z + d = r$.

    lines 64–69

    uses hamming_dist_eq_exceptional_add_all_distinct, hamming_equilateral_triangle_local_types_exceptional_swap, hamming_equilateral_triangle_local_types_all_distinct_swap

      have h2 : ax + az + d = r := by
        have e1 : (hamming_exceptional_coords x z y).card = ax := by
          rw [hax, hamming_equilateral_triangle_local_types_exceptional_swap x y z]
        have e2 : (hamming_all_distinct_coords x z y).card = d := by
          rw [hd, hamming_equilateral_triangle_local_types_all_distinct_swap x y z]
        rw [← hxz, hamming_dist_eq_exceptional_add_all_distinct x z y, e1, e2]
  6. $a_y + a_z + d = r$.

    Applying `hamming_dist_eq_exceptional_add_all_distinct` to $(y, z, x)$ expresses $\mathrm{hammingDist}(y, z)$ as the sum of coordinates where $y$ is exceptional, coordinates where $z$ is exceptional, and coordinates where all three differ. Using `hamming_equilateral_triangle_local_types_exceptional_swap'`, `hamming_equilateral_triangle_local_types_exceptional_swap23`, and `hamming_equilateral_triangle_local_types_all_distinct_swap'`, these three counts equal $a_y$, $a_z$, and $d$ respectively. Since $\mathrm{hammingDist}(y, z) = r$, this gives $a_y + a_z + d = r$.

    lines 70–77

    uses hamming_dist_eq_exceptional_add_all_distinct, hamming_equilateral_triangle_local_types_exceptional_swap', hamming_equilateral_triangle_local_types_exceptional_swap23, hamming_equilateral_triangle_local_types_all_distinct_swap'

      have h3 : ay + az + d = r := by
        have e1 : (hamming_exceptional_coords y z x).card = ay := by
          rw [hay, hamming_equilateral_triangle_local_types_exceptional_swap' x y z]
        have e2 : (hamming_exceptional_coords z y x).card = az := by
          rw [haz, hamming_equilateral_triangle_local_types_exceptional_swap23 z y x]
        have e3 : (hamming_all_distinct_coords y z x).card = d := by
          rw [hd, hamming_equilateral_triangle_local_types_all_distinct_swap' x y z]
        rw [← hyz, hamming_dist_eq_exceptional_add_all_distinct y z x, e1, e2, e3]
  7. $a_x = a_y = a_z$, $2a_x + d = r$, $a_x \le r / 2$, and $d = r - 2a_x$.

    From the three equations $a_x + a_y + d = r$, $a_x + a_z + d = r$, and $a_y + a_z + d = r$, linear integer arithmetic (`omega`) deduces $a_x = a_y$ and $a_x = a_z$. Substituting $a_x$ for $a_y$ gives $2a_x + d = r$, which implies $a_x \le r/2$ and $d = r - 2a_x$. This settles the first five conjuncts of the theorem.

    lines 78–80

      have hab : ax = ay := by omega
      have hac : ax = az := by omega
      refine ⟨hab, hac, by omega, by omega, by omega, ?_⟩
  8. The size of the active support is $r + a_x$.

    By `hamming_active_coords_card`, the active coordinates partition into the exceptional coordinate sets for $x, y, z$ and the all-distinct set, so its cardinality is $a_x + a_y + a_z + d$. Since $a_x + a_y + d = r$ and $a_z = a_x$, this sum simplifies to $r + a_x$, as verified by linear arithmetic (`omega`).

    lines 81–82

    uses hamming_active_coords_card

      rw [hamming_active_coords_card, ← hax, ← hay, ← haz, ← hd]
      omega
hamming_dist_eq_exceptional_add_all_distinct
For any three vectors $x, y, z$, the Hamming distance between $x$ and $y$ equals the number of coordinates where $x$ is exceptional, plus the number of coordinates where $y$ is exceptional, plus the number of coordinates where $x, y, z$ all differ.
hamming_equilateral_triangle_local_types_exceptional_swap
Swapping the second and third arguments preserves the set of coordinates where the first vector is exceptional with respect to the other two.
hamming_equilateral_triangle_local_types_all_distinct_swap
Swapping the second and third arguments preserves the set of coordinates where all three vectors are pairwise distinct.
hamming_equilateral_triangle_local_types_exceptional_swap'
Swapping the second and third arguments ($z$ and $x$) preserves the set of coordinates where $y$ is exceptional.
hamming_equilateral_triangle_local_types_exceptional_swap23
For any vectors $a, b, c$, swapping the second and third arguments leaves the set of exceptional coordinates for $a$ unchanged.
hamming_equilateral_triangle_local_types_all_distinct_swap'
Cyclically permuting the three vectors preserves the set of coordinates where all three vectors are pairwise distinct.
hamming_active_coords_card
The number of active coordinates among $x, y, z$ equals the sum of the numbers of coordinates where each vector is individually exceptional, plus the number of coordinates where all three vectors differ.

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

private lemma hamming_equilateral_triangle_local_types_exceptional_swap {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :    hamming_exceptional_coords x z y = hamming_exceptional_coords x y z := by  simp only [hamming_exceptional_coords]  congr 1  ext i  constructor <;> rintro ⟨h1, h2⟩ <;> exact ⟨h1.symm, fun h => h2 (h.trans h1.symm)⟩private lemma hamming_equilateral_triangle_local_types_exceptional_swap' {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :    hamming_exceptional_coords y z x = hamming_exceptional_coords y x z := by  simp only [hamming_exceptional_coords]  congr 1  ext i  constructor <;> rintro ⟨h1, h2⟩ <;> exact ⟨h1.symm, fun h => h2 (h.trans h1.symm)⟩private lemma hamming_equilateral_triangle_local_types_exceptional_swap23 {n : ℕ} {α : Type*} [DecidableEq α] (a b c : Fin n → α) :    hamming_exceptional_coords a b c = hamming_exceptional_coords a c b := by  simp only [hamming_exceptional_coords]  congr 1  ext i  constructor <;> rintro ⟨h1, h2⟩ <;> exact ⟨h1.symm, fun h => h2 (h.trans h1.symm)⟩private lemma hamming_equilateral_triangle_local_types_all_distinct_swap {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :    hamming_all_distinct_coords x z y = hamming_all_distinct_coords x y z := by  simp only [hamming_all_distinct_coords]  congr 1  ext i  constructor  · rintro ⟨h1, h2, h3⟩    exact ⟨h2, h1, fun h => h3 h.symm⟩  · rintro ⟨h1, h2, h3⟩    exact ⟨h2, h1, fun h => h3 h.symm⟩private lemma hamming_equilateral_triangle_local_types_all_distinct_swap' {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) :    hamming_all_distinct_coords y z x = hamming_all_distinct_coords x y z := by  simp only [hamming_all_distinct_coords]  congr 1  ext i  constructor  · rintro ⟨h1, h2, h3⟩    exact ⟨fun h => h2 h.symm, fun h => h3 h.symm, h1⟩  · rintro ⟨h1, h2, h3⟩    exact ⟨h3, fun h => h1 h.symm, fun h => h2 h.symm⟩/-- Classification of local types in equilateral triangles of Hamming graphs: equal exceptional counts a, 2a + d = r, a ≤ r / 2, d = r - 2a, and active support size r + a. -/theorem hamming_equilateral_triangle_local_types {n : ℕ} {α : Type*} [DecidableEq α]    (x y z : Fin n → α) (r : ℕ)    (hxy : hammingDist x y = r)    (hxz : hammingDist x z = r)    (hyz : hammingDist y z = r) :    let ax := (hamming_exceptional_coords x y z).card    let ay := (hamming_exceptional_coords y x z).card    let az := (hamming_exceptional_coords z x y).card    let d := (hamming_all_distinct_coords x y z).card    ax = ay ∧ ax = az ∧ 2 * ax + d = r ∧ ax ≤ r / 2 ∧ d = r - 2 * ax ∧      (hamming_active_coords x y z).card = r + ax := by  dsimp only  set ax := (hamming_exceptional_coords x y z).card with hax  set ay := (hamming_exceptional_coords y x z).card with hay  set az := (hamming_exceptional_coords z x y).card with haz  set d := (hamming_all_distinct_coords x y z).card with hd  have h1 : ax + ay + d = r := by    rw [hax, hay, hd, ← hxy]    exact (hamming_dist_eq_exceptional_add_all_distinct x y z).symm  have h2 : ax + az + d = r := by    have e1 : (hamming_exceptional_coords x z y).card = ax := by      rw [hax, hamming_equilateral_triangle_local_types_exceptional_swap x y z]    have e2 : (hamming_all_distinct_coords x z y).card = d := by      rw [hd, hamming_equilateral_triangle_local_types_all_distinct_swap x y z]    rw [← hxz, hamming_dist_eq_exceptional_add_all_distinct x z y, e1, e2]  have h3 : ay + az + d = r := by    have e1 : (hamming_exceptional_coords y z x).card = ay := by      rw [hay, hamming_equilateral_triangle_local_types_exceptional_swap' x y z]    have e2 : (hamming_exceptional_coords z y x).card = az := by      rw [haz, hamming_equilateral_triangle_local_types_exceptional_swap23 z y x]    have e3 : (hamming_all_distinct_coords y z x).card = d := by      rw [hd, hamming_equilateral_triangle_local_types_all_distinct_swap' x y z]    rw [← hyz, hamming_dist_eq_exceptional_add_all_distinct y z x, e1, e2, e3]  have hab : ax = ay := by omega  have hac : ax = az := by omega  refine ⟨hab, hac, by omega, by omega, by omega, ?_⟩  rw [hamming_active_coords_card, ← hax, ← hay, ← haz, ← hd]  omega
See it in the graphDiscuss this resultChallenge it