AFTD Auto-Formalizing Theoretical Domains

unit_hamming_triangle_free_card_le

theoremverified

For every integer q ≥ 2 and every integer n ≥ 1, every finite set A : Finset (Fin n → Fin q) satisfying unit_hamming_triangle_free A satisfies A.card ≤ 2 * q ^ (n - 1).

Statement

theorem unit_hamming_triangle_free_card_le (n q : ℕ) (hq : 2 ≤ q) (hn : 1 ≤ n)
    (A : Finset (Fin n → Fin q)) (hA : unit_hamming_triangle_free A) :
    A.card ≤ 2 * q ^ (n - 1)
Source
arXiv:2610.32789 Section 3.1
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • unit_hamming_triangle_freeA finite set A : Finset (Fin n → Fin q) is unit_hamming_triangle_free if for all x, y, z : Fin n → Fin q, if x ∈ A, y ∈ A, z ∈ A, and x ≠…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1
  • unit_hamming_max_triangle_free_eqFor every fixed integer q ≥ 2 and every integer n ≥ 1, the maximum size unit_hamming_max_triangle_free n q of a triangle-free vertex…

Read back from the Lean

For all natural numbers n and q with q ≥ 2 and n ≥ 1, and for any finite subset A of (Fin n → Fin q), if A is unit Hamming triangle-free (i.e., A contains no three pairwise distinct elements whose pairwise Hamming distances are all 1), then the cardinality of A is at most 2 * q^(n - 1).

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 upper bound is proved by projecting the set A of words in Fin n → Fin q onto the last n - 1 coordinates using the tail map Fin.tail. Two distinct words with identical tails differ only at coordinate 0, so their Hamming distance is exactly 1. Consequently, if any fiber of the tail map contained three or more words, they would form a unit-distance triangle in A, contradicting triangle-freeness; thus each fiber has size at most 2. Bounding the size of A by twice the number of possible tails (at most q^(n-1)) yields |A| ≤ 2 * q^(n-1).

  1. Two distinct words with identical tails must differ at coordinate 0.

    Assume for contradiction that x(0) = y(0). Since their tails also coincide, x and y agree on every successor coordinate as well, hence on all coordinates by Fin.cases, contradicting the assumption that x ≠ y.

    lines 4–10

    uses Fin.cases, congr_fun

      have h0 : x 0 ≠ y 0 := by
        intro h
        apply hne
        funext i
        induction' i using Fin.cases with j
        · exact h
        · exact congr_fun h_tail j
  2. The set of indices where x and y differ is precisely {0}.

    Coordinate 0 belongs to the set because x(0) ≠ y(0). For any successor coordinate j + 1, x(j + 1) = y(j + 1) because their tails match, so no non-zero coordinate belongs to the set.

    lines 11–18

    uses Fin.cases, Fin.succ_ne_zero, Finset.mem_filter, Finset.mem_singleton, Finset.mem_univ, congr_fun, true_and

      have h_set : Finset.filter (fun i => x i ≠ y i) Finset.univ = {0} := by
        ext i
        induction' i using Fin.cases with j
        · simp [h0]
        · simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]
          have hj : Fin.tail x j = Fin.tail y j := congr_fun h_tail j
          change x j.succ = y j.succ at hj
          simp [hj, Fin.succ_ne_zero]
  3. The Hamming distance between x and y is 1.

    Hamming distance is by definition the cardinality of the set of coordinates where x and y differ. Since that set is {0}, its cardinality is 1.

    lines 19–20

    uses Finset.card_singleton

      unfold hammingDist
      rw [h_set, Finset.card_singleton]
  4. Any finset s with |s| > 2 is nonempty and contains an element x.

    If s were empty its size would be 0, contradicting |s| > 2. Hence s is nonempty and contains some element x.

    lines 25–29

    uses Finset.nonempty_iff_ne_empty

      have hne : s.Nonempty := by
        rw [Finset.nonempty_iff_ne_empty]
        rintro rfl
        simp at h
      obtain ⟨x, hx⟩ := hne
  5. Any finset s with |s| > 2 contains three pairwise distinct elements x, y, z.

    Removing {x} leaves a set of size |s| - 1 > 1. A set of size greater than 1 contains two distinct elements y and z. Since both lie in s \ {x}, neither equals x, giving three pairwise distinct elements in s.

    lines 30–36

    uses Finset.card_sdiff_of_subset, Finset.card_singleton, Finset.mem_sdiff, Finset.mem_singleton, Finset.one_lt_card, Finset.singleton_subset_iff.mpr, Ne.symm

      have hcard : 1 < (s \ {x}).card := by
        rw [Finset.card_sdiff_of_subset (Finset.singleton_subset_iff.mpr hx), Finset.card_singleton]
        omega
      rw [Finset.one_lt_card] at hcard
      obtain ⟨y, hy, z, hz, hyz⟩ := hcard
      rw [Finset.mem_sdiff, Finset.mem_singleton] at hy hz
      exact ⟨x, hx, y, hy.1, z, hz.1, Ne.symm hy.2, hyz, Ne.symm hz.2⟩
  6. If a tail fiber in A had size greater than 2, it would contain three pairwise distinct words x, y, z.

    We argue by contradiction. If {a ∈ A | Fin.tail a = b} had cardinality greater than 2, the previous lemma would yield three pairwise distinct elements x, y, z in this fiber.

    lines 42–45

    uses Finset.mem_filter, unit_hamming_triangle_free_card_le_exists_three

      by_contra! h
      obtain ⟨x, hx, y, hy, z, hz, hxy, hyz, hxz⟩ :=
        unit_hamming_triangle_free_card_le_exists_three h
      simp only [Finset.mem_filter] at hx hy hz
  7. Every fiber of the tail map restricted to A has cardinality at most 2.

    Because x, y, z all share the same tail b and are pairwise distinct, the Hamming distance between each pair is 1 by the first lemma. This means x, y, z form a unit-distance triangle in A, directly contradicting the hypothesis that A is unit-Hamming triangle-free.

    lines 46–52

    uses unit_hamming_triangle_free_card_le_hammingDist_one

      have dxy : hammingDist x y = 1 :=
        unit_hamming_triangle_free_card_le_hammingDist_one m q x y (hx.2.trans hy.2.symm) hxy
      have dyz : hammingDist y z = 1 :=
        unit_hamming_triangle_free_card_le_hammingDist_one m q y z (hy.2.trans hz.2.symm) hyz
      have dxz : hammingDist x z = 1 :=
        unit_hamming_triangle_free_card_le_hammingDist_one m q x z (hx.2.trans hz.2.symm) hxz
      exact hA hx.1 hy.1 hz.1 hxy hyz hxz ⟨dxy, dyz, dxz⟩
  8. We can write n = m + 1 for some natural number m.

    Since n ≥ 1, n is non-zero, so it is the successor of some natural number m.

    lines 58–59

    uses Nat.exists_eq_succ_of_ne_zero, ne_of_gt

      have _ := hq
      obtain ⟨m, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (ne_of_gt hn)
  9. The cardinality of A is bounded by twice the cardinality of its image under Fin.tail.

    By Finset.card_le_mul_card_image, the size of A is at most 2 times the size of its image under Fin.tail, because every fiber has cardinality at most 2 by the fiber lemma.

    lines 60–62

    uses Finset.card_le_mul_card_image, unit_hamming_triangle_free_card_le_fiber_card_le_two

      have h_bound := Finset.card_le_mul_card_image (f := Fin.tail) A 2 (by
        intro b _
        exact unit_hamming_triangle_free_card_le_fiber_card_le_two m q A hA b)
  10. The image of A under Fin.tail has cardinality at most q ^ m.

    The image of A is a subset of the full function space Fin m → Fin q, which has cardinality q ^ m.

    lines 63–67

    uses Finset.card_le_univ

      have h_img : (Finset.image Fin.tail A).card ≤ q ^ m := by
        calc (Finset.image Fin.tail A).card ≤ (Finset.univ : Finset (Fin m → Fin q)).card :=
              Finset.card_le_univ _
          _ = Fintype.card (Fin m → Fin q) := rfl
          _ = q ^ m := by simp
  11. The cardinality of A is at most 2 * q ^ (n - 1).

    Since n - 1 = m, combining |A| ≤ 2 * |image| with |image| ≤ q ^ m via linear arithmetic completes the proof.

    lines 68–70

      have hm : m + 1 - 1 = m := rfl
      rw [hm]
      linarith
Fin.cases
Proof by cases on Fin (n + 1): any index is either 0 or the successor of an index in Fin n.
Fin.succ_ne_zero
The successor of any element in Fin n is non-zero.
Finset.card_le_univ
The cardinality of any finset in a finite type α is at most the total cardinality of α.
Finset.card_le_mul_card_image
If every fiber of a map f on a finset s has cardinality at most n, then |s| ≤ n * |f(s)|.
Finset.card_sdiff_of_subset
If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.card_singleton
The cardinality of a singleton finset {a} is 1.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_sdiff
An element belongs to the set difference s \ t if and only if it is in s and not in t.
Finset.mem_singleton
An element belongs to {a} if and only if it equals a.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.nonempty_iff_ne_empty
A finset is nonempty if and only if it is not the empty set.
Finset.one_lt_card
A finset has cardinality strictly greater than 1 if and only if it contains at least two distinct elements.
Finset.singleton_subset_iff.mpr
A singleton {x} is a subset of s if x belongs to s.
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a.
Nat.exists_eq_succ_of_ne_zero
Every nonzero natural number is the successor of some natural number.
congr_fun
Equal functions take equal values on identical inputs.
ne_of_gt
A strictly greater element is not equal to the smaller element.
true_and
Conjunction with True simplifies to the proposition itself.
unit_hamming_triangle_free_card_le_fiber_card_le_two
In a unit-Hamming triangle-free set A, any fiber of the tail map has size at most 2.
unit_hamming_triangle_free_card_le_exists_three
Any finset with cardinality strictly greater than 2 contains three pairwise distinct elements.
unit_hamming_triangle_free_card_le_hammingDist_one
Two distinct words whose tails agree have Hamming distance 1.

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

lemma unit_hamming_triangle_free_card_le_hammingDist_one (m q : ℕ) (x y : Fin (m + 1) → Fin q)    (h_tail : Fin.tail x = Fin.tail y) (hne : x ≠ y) :    hammingDist x y = 1 := by  have h0 : x 0 ≠ y 0 := by    intro h    apply hne    funext i    induction' i using Fin.cases with j    · exact h    · exact congr_fun h_tail j  have h_set : Finset.filter (fun i => x i ≠ y i) Finset.univ = {0} := by    ext i    induction' i using Fin.cases with j    · simp [h0]    · simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]      have hj : Fin.tail x j = Fin.tail y j := congr_fun h_tail j      change x j.succ = y j.succ at hj      simp [hj, Fin.succ_ne_zero]  unfold hammingDist  rw [h_set, Finset.card_singleton]lemma unit_hamming_triangle_free_card_le_exists_three {α : Type*} [DecidableEq α]    {s : Finset α} (h : 2 < s.card) :    ∃ x ∈ s, ∃ y ∈ s, ∃ z ∈ s, x ≠ y ∧ y ≠ z ∧ x ≠ z := by  have hne : s.Nonempty := by    rw [Finset.nonempty_iff_ne_empty]    rintro rfl    simp at h  obtain ⟨x, hx⟩ := hne  have hcard : 1 < (s \ {x}).card := by    rw [Finset.card_sdiff_of_subset (Finset.singleton_subset_iff.mpr hx), Finset.card_singleton]    omega  rw [Finset.one_lt_card] at hcard  obtain ⟨y, hy, z, hz, hyz⟩ := hcard  rw [Finset.mem_sdiff, Finset.mem_singleton] at hy hz  exact ⟨x, hx, y, hy.1, z, hz.1, Ne.symm hy.2, hyz, Ne.symm hz.2⟩lemma unit_hamming_triangle_free_card_le_fiber_card_le_two (m q : ℕ)    (A : Finset (Fin (m + 1) → Fin q)) (hA : unit_hamming_triangle_free A)    (b : Fin m → Fin q) :    {a ∈ A | Fin.tail a = b}.card ≤ 2 := by  by_contra! h  obtain ⟨x, hx, y, hy, z, hz, hxy, hyz, hxz⟩ :=    unit_hamming_triangle_free_card_le_exists_three h  simp only [Finset.mem_filter] at hx hy hz  have dxy : hammingDist x y = 1 :=    unit_hamming_triangle_free_card_le_hammingDist_one m q x y (hx.2.trans hy.2.symm) hxy  have dyz : hammingDist y z = 1 :=    unit_hamming_triangle_free_card_le_hammingDist_one m q y z (hy.2.trans hz.2.symm) hyz  have dxz : hammingDist x z = 1 :=    unit_hamming_triangle_free_card_le_hammingDist_one m q x z (hx.2.trans hz.2.symm) hxz  exact hA hx.1 hy.1 hz.1 hxy hyz hxz ⟨dxy, dyz, dxz⟩/-- Upper bound on the size of a triangle-free subset in the unit-distance Hamming graph: |A| ≤ 2 * q^(n-1). -/theorem unit_hamming_triangle_free_card_le (n q : ℕ) (hq : 2 ≤ q) (hn : 1 ≤ n)    (A : Finset (Fin n → Fin q)) (hA : unit_hamming_triangle_free A) :    A.card ≤ 2 * q ^ (n - 1) := by  have _ := hq  obtain ⟨m, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (ne_of_gt hn)  have h_bound := Finset.card_le_mul_card_image (f := Fin.tail) A 2 (by    intro b _    exact unit_hamming_triangle_free_card_le_fiber_card_le_two m q A hA b)  have h_img : (Finset.image Fin.tail A).card ≤ q ^ m := by    calc (Finset.image Fin.tail A).card ≤ (Finset.univ : Finset (Fin m → Fin q)).card :=          Finset.card_le_univ _      _ = Fintype.card (Fin m → Fin q) := rfl      _ = q ^ m := by simp  have hm : m + 1 - 1 = m := rfl  rw [hm]  linarith
See it in the graphDiscuss this resultChallenge it