hamming_equilateral_triangle_local_types
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$.
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)$.
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)⟩
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.
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⟩
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.
/-- 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
$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$.
uses
hamming_dist_eq_exceptional_add_all_distincthave h1 : ax + ay + d = r := by rw [hax, hay, hd, ← hxy] exact (hamming_dist_eq_exceptional_add_all_distinct x y z).symm
$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$.
uses
hamming_dist_eq_exceptional_add_all_distinct,hamming_equilateral_triangle_local_types_exceptional_swap,hamming_equilateral_triangle_local_types_all_distinct_swaphave 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]
$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$.
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]
$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.
have hab : ax = ay := by omega have hac : ax = az := by omega refine ⟨hab, hac, by omega, by omega, by omega, ?_⟩
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`).
uses
hamming_active_coords_cardrw [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.
- The proof uses private helper lemmas that establish argument-swapping symmetries for the exceptional and all-distinct coordinate sets to justify rewriting inside the distance equations.
- The deductions that $a_x = a_y = a_z$, $2a_x + d = r$, $a_x \le r/2$, and $d = r - 2a_x$ from the linear system $a_x + a_y + d = r$, $a_x + a_z + d = r$, $a_y + a_z + d = r$ are carried out by the Presburger arithmetic tactic `omega`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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