hamming_active_coords_card
For vectors $x, y, z : \mathrm{Fin}\, n \to \alpha$, the number of active coordinates is the sum of the coordinates where $x$ is exceptional, where $y$ is exceptional, where $z$ is exceptional, and where all three symbols are distinct.
Statement
theorem hamming_active_coords_card {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) : (hamming_active_coords x y z).card = (hamming_exceptional_coords x y z).card + (hamming_exceptional_coords y x z).card + (hamming_exceptional_coords z x y).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 3
- 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,…
- Used by 1
- hamming_equilateral_triangle_local_typesSuppose $x, y, z : \mathrm{Fin}\, n \to \alpha$ satisfy $\mathrm{hammingDist}(x, y) = r$, $\mathrm{hammingDist}(x, z) = r$, and…
Read back from the Lean
For every natural number $n$, type $\alpha$ with decidable equality, and vectors $x, y, z : \mathrm{Fin}\; n \to \alpha$, the cardinality of hamming_active_coords x y z is equal to the sum of:
1. the cardinality of hamming_exceptional_coords x y z,
2. the cardinality of hamming_exceptional_coords y x z,
3. the cardinality of hamming_exceptional_coords z x y, and
4. the cardinality of 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 proceeds by reformulating the cardinality of each set of coordinates as a sum of indicator functions over all coordinates. At each coordinate, the indicator that not all three vectors agree partitions into the sum of four mutually exclusive indicators: one for each vector being the unique outlier, and one for all three entries being pairwise distinct. Combining the four sums on the right-hand side and applying this pointwise identity term by term yields the theorem.
For every coordinate i, the indicator that x i, y i, and z i are not all equal equals the sum of the indicators for the four mutually exclusive non-monochromatic configurations: x i is exceptional, y i is exceptional, z i is exceptional, or all three are pairwise distinct.
We fix a coordinate i and exhaustively split into cases based on whether x i = y i, y i = z i, and x i = z i. If all three are equal, both sides are 0. If exactly two symbols are equal, the left-hand side is 1 and exactly one of the three exceptional-coordinate indicators is 1, while all other indicators are 0. If all three symbols are pairwise distinct, the left-hand side is 1 and only the all-distinct indicator is 1. The remaining truth-value combinations violate the transitivity or symmetry of equality (using eq_comm), and all cases are closed by simplification.
uses
eq_commhave key : ∀ i : Fin n, (if ¬(x i = y i ∧ y i = z i) then (1:ℕ) else 0) = (if (y i = z i ∧ x i ≠ y i) then (1:ℕ) else 0) + (if (x i = z i ∧ y i ≠ x i) then (1:ℕ) else 0) + (if (x i = y i ∧ z i ≠ x i) then (1:ℕ) else 0) + (if (x i ≠ y i ∧ x i ≠ z i ∧ y i ≠ z i) then (1:ℕ) else 0) := by intro i by_cases h1 : x i = y i <;> by_cases h2 : y i = z i <;> by_cases h3 : x i = z i <;> simp_all [eq_comm]
The cardinality equation is rewritten as an equality between a sum of indicators on the left and a single combined sum of indicators over all coordinates on the right.
Unfolding the definitions of hamming_active_coords, hamming_exceptional_coords, and hamming_all_distinct_coords expresses each set as a filtered subset of all coordinates. Applying Finset.card_filter rewrites each cardinality as a sum over coordinates of the corresponding indicator function. Finally, applying Finset.sum_add_distrib in reverse three times combines the four sums on the right-hand side into a single sum over all coordinates.
uses
Finset.card_filter,Finset.sum_add_distribsimp only [hamming_active_coords, hamming_exceptional_coords, hamming_all_distinct_coords] rw [Finset.card_filter, Finset.card_filter, Finset.card_filter, Finset.card_filter, Finset.card_filter] rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib]
The number of active coordinates equals the sum of the three exceptional coordinate counts and the all-distinct coordinate count.
Since the left-hand side and right-hand side are sums over the same finite set of coordinates, Finset.sum_congr reduces the equality of sums to the equality of their summands at every coordinate, which was established by the pointwise key identity.
uses
Finset.sum_congrexact Finset.sum_congr rfl (fun i _ => key i)
eq_comm- Equality is symmetric: a = b is equivalent to b = a.
Finset.card_filter- The cardinality of a filtered finset {x ∈ s | p x} equals the sum over s of the indicator function of p (which is 1 if p x holds and 0 otherwise).
Finset.sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of their separate sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.sum_congr- Two sums over equal finite sets are equal if their summands agree at every index in the set.
- The pointwise indicator identity is verified formally by splitting on all eight truth-value combinations for the three pairwise equalities among x i, y i, and z i, with automation simplifying the indicator arithmetic and eliminating contradictory combinations via transitivity.
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.
/-- The size of the active support of three vectors is the sum of the three exceptional coordinate counts and the all-distinct coordinate count. -/theorem hamming_active_coords_card {n : ℕ} {α : Type*} [DecidableEq α] (x y z : Fin n → α) : (hamming_active_coords x y z).card = (hamming_exceptional_coords x y z).card + (hamming_exceptional_coords y x z).card + (hamming_exceptional_coords z x y).card + (hamming_all_distinct_coords x y z).card := by have key : ∀ i : Fin n, (if ¬(x i = y i ∧ y i = z i) then (1:ℕ) else 0) = (if (y i = z i ∧ x i ≠ y i) then (1:ℕ) else 0) + (if (x i = z i ∧ y i ≠ x i) then (1:ℕ) else 0) + (if (x i = y i ∧ z i ≠ x i) then (1:ℕ) else 0) + (if (x i ≠ y i ∧ x i ≠ z i ∧ y i ≠ z i) then (1:ℕ) else 0) := by intro i by_cases h1 : x i = y i <;> by_cases h2 : y i = z i <;> by_cases h3 : x i = z i <;> simp_all [eq_comm] simp only [hamming_active_coords, hamming_exceptional_coords, hamming_all_distinct_coords] rw [Finset.card_filter, Finset.card_filter, Finset.card_filter, Finset.card_filter, Finset.card_filter] rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib] exact Finset.sum_congr rfl (fun i _ => key i)