AFTD Auto-Formalizing Theoretical Domains

unit_hamming_max_triangle_free_eq

theoremverifiedformalization

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

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

    lines 4–5

    uses csSup_eq_of_forall_le_of_forall_lt_exists_gt

      unfold unit_hamming_max_triangle_free
      apply csSup_eq_of_forall_le_of_forall_lt_exists_gt
  2. 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.

    lines 6–7

    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⟩
  3. 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).

    lines 8–9

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

    lines 10–12

    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

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