AFTD Auto-Formalizing Theoretical Domains

hamming_active_coords_card

theoremverified

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

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.

  1. 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.

    lines 8–16

    uses eq_comm

      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]
  2. 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.

    lines 17–19

    uses Finset.card_filter, Finset.sum_add_distrib

      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]
  3. 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.

    line 20

    uses Finset.sum_congr

      exact 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.

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 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)
See it in the graphDiscuss this resultChallenge it