unit_hamming_triangle_free_card_le
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- 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).
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.
uses
Fin.cases,congr_funhave 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
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.
uses
Fin.cases,Fin.succ_ne_zero,Finset.mem_filter,Finset.mem_singleton,Finset.mem_univ,congr_fun,true_andhave 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]
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.
uses
Finset.card_singletonunfold hammingDist rw [h_set, Finset.card_singleton]
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.
uses
Finset.nonempty_iff_ne_emptyhave hne : s.Nonempty := by rw [Finset.nonempty_iff_ne_empty] rintro rfl simp at h obtain ⟨x, hx⟩ := hne
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.
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.symmhave 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⟩
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.
uses
Finset.mem_filter,unit_hamming_triangle_free_card_le_exists_threeby_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
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.
uses
unit_hamming_triangle_free_card_le_hammingDist_onehave 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⟩
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.
uses
Nat.exists_eq_succ_of_ne_zero,ne_of_gthave _ := hq obtain ⟨m, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (ne_of_gt hn)
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.
uses
Finset.card_le_mul_card_image,unit_hamming_triangle_free_card_le_fiber_card_le_twohave 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)
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.
uses
Finset.card_le_univhave 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
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.
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.
- The hypothesis hq (2 ≤ q) is retained on line 58 via `have _ := hq` but is not actively needed in the arithmetic bounding |A|, since q ^ m is valid for any q.
- On line 67, `simp` computes the cardinality of the function type Fin m → Fin q as q ^ m using Mathlib's cardinality instances for function types.
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.
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