unit_hamming_max_triangle_free_eq
For 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 subset of (Fin n → Fin q) in the unit-distance Hamming graph equals 2 * q ^ (n - 1).
Statement
theorem unit_hamming_max_triangle_free_eq (n q : ℕ) (hq : 2 ≤ q) (hn : 1 ≤ n) :
unit_hamming_max_triangle_free n q = 2 * q ^ (n - 1)- Formalizes
- arXiv:2610.32789 Theorem 1.3
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- unit_hamming_max_triangle_freeThe maximum cardinality unit_hamming_max_triangle_free n q of a finite set A : Finset (Fin n → Fin q) satisfying…
- unit_hamming_triangle_free_card_leFor every integer q ≥ 2 and every integer n ≥ 1, every finite set A : Finset (Fin n → Fin q) satisfying unit_hamming_triangle_free A…
- exists_unit_hamming_triangle_free_card_eqFor every integer q ≥ 2 and every integer n ≥ 1, there exists a finite set A : Finset (Fin n → Fin q) satisfying…
- 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 ≠…
Read back from the Lean
For all natural numbers $n$ and $q$, if $2 \le q$ and $1 \le n$, then unit_hamming_max_triangle_free n q equals $2 \cdot q^{n - 1}$. That is, the maximum cardinality of a subset of the Hamming space $(\mathrm{Fin}\ n \to \mathrm{Fin}\ q)$ containing no three mutually distinct points at pairwise Hamming distance $1$ is $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 proof unfolds the definition of `unit_hamming_max_triangle_free` as the supremum of all cardinalities achieved by triangle-free vertex subsets, and applies `csSup_eq_of_forall_le_of_forall_lt_exists_gt` to evaluate it. It verifies the supremum by showing the set of cardinalities is nonempty, bounded above by 2 * q^(n - 1) via `unit_hamming_triangle_free_card_le`, and that this upper bound is attained by a concrete triangle-free subset from `exists_unit_hamming_triangle_free_card_eq`.
To show the supremum of the cardinalities of triangle-free sets equals 2 * q^(n - 1), it suffices to show that the set of cardinalities is nonempty, bounded above by 2 * q^(n - 1), and that no strictly smaller number is an upper bound.
Unfolding the definition expresses the maximum size as the supremum (sSup) of the set S of all cardinalities of triangle-free sets. Applying `csSup_eq_of_forall_le_of_forall_lt_exists_gt` reduces the equality to three goals: showing S is nonempty, showing every element of S is at most 2 * q^(n - 1), and showing that every number strictly less than 2 * q^(n - 1) is exceeded by some element of S.
uses
csSup_eq_of_forall_le_of_forall_lt_exists_gtunfold unit_hamming_max_triangle_free apply csSup_eq_of_forall_le_of_forall_lt_exists_gt
The set of cardinalities of triangle-free sets is nonempty.
By `exists_unit_hamming_triangle_free_card_eq`, there exists a triangle-free set A with cardinality 2 * q^(n - 1). Hence 2 * q^(n - 1) belongs to the set of cardinalities, witnessing that it is nonempty.
uses
exists_unit_hamming_triangle_free_card_eq· obtain ⟨A, hA, hcard⟩ := exists_unit_hamming_triangle_free_card_eq n q hq hn exact ⟨2 * q ^ (n - 1), A, hA, hcard⟩
Every cardinality of a triangle-free set is at most 2 * q^(n - 1).
Given an element a in the set, it is the cardinality of some triangle-free set A. Applying `unit_hamming_triangle_free_card_le` confirms that |A| ≤ 2 * q^(n - 1).
uses
unit_hamming_triangle_free_card_le· rintro a ⟨A, hA, rfl⟩ exact unit_hamming_triangle_free_card_le n q hq hn A hA
For every w < 2 * q^(n - 1), there is an achievable cardinality strictly greater than w.
Given w < 2 * q^(n - 1), the witness A provided by `exists_unit_hamming_triangle_free_card_eq` has cardinality 2 * q^(n - 1), which belongs to the set and strictly exceeds w.
uses
exists_unit_hamming_triangle_free_card_eq· intro w hw obtain ⟨A, hA, hcard⟩ := exists_unit_hamming_triangle_free_card_eq n q hq hn exact ⟨2 * q ^ (n - 1), ⟨A, hA, hcard⟩, hw⟩
csSup_eq_of_forall_le_of_forall_lt_exists_gt- In a conditionally complete lattice, the supremum of a set s equals b if s is nonempty, b is an upper bound for s, and no value strictly smaller than b is an upper bound for s.
exists_unit_hamming_triangle_free_card_eq- For q ≥ 2 and n ≥ 1, there exists a triangle-free subset of vertices in the unit-distance Hamming graph with cardinality exactly 2 * q^(n - 1).
unit_hamming_triangle_free_card_le- For q ≥ 2 and n ≥ 1, every triangle-free subset of vertices in the unit-distance Hamming graph has cardinality at most 2 * q^(n - 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
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.
/-- Maximum size of a triangle-free set in the unit-distance Hamming graph: T_q(n, 1) = 2 * q^(n-1). -/theorem unit_hamming_max_triangle_free_eq (n q : ℕ) (hq : 2 ≤ q) (hn : 1 ≤ n) : unit_hamming_max_triangle_free n q = 2 * q ^ (n - 1) := by unfold unit_hamming_max_triangle_free apply csSup_eq_of_forall_le_of_forall_lt_exists_gt · obtain ⟨A, hA, hcard⟩ := exists_unit_hamming_triangle_free_card_eq n q hq hn exact ⟨2 * q ^ (n - 1), A, hA, hcard⟩ · rintro a ⟨A, hA, rfl⟩ exact unit_hamming_triangle_free_card_le n q hq hn A hA · intro w hw obtain ⟨A, hA, hcard⟩ := exists_unit_hamming_triangle_free_card_eq n q hq hn exact ⟨2 * q ^ (n - 1), ⟨A, hA, hcard⟩, hw⟩