AFTD Auto-Formalizing Theoretical Domains

unit_hamming_triangle_free

def

A 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 ≠ y, y ≠ z, and x ≠ z, then it is not the case that hammingDist x y = 1, hammingDist y z = 1, and hammingDist x z = 1.

Statement

def unit_hamming_triangle_free {n q : ℕ} (A : Finset (Fin n → Fin q)) : Prop
Defined in
arXiv:2610.32789 Definition 1.1
Verified
26 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

Given implicit natural numbers n and q, and a finset A of functions from Fin n to Fin q, unit_hamming_triangle_free A asserts that for all x, y, z : Fin n → Fin q, if x ∈ A, y ∈ A, z ∈ A, and x ≠ y, y ≠ z, and x ≠ z, then it is not the case that hammingDist x y = 1, hammingDist y z = 1, and hammingDist x z = 1 (i.e., A contains no triangle in the unit Hamming distance graph).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Predicate that a finite set of words in [q]^n induces a triangle-free subgraph in the unit-distance Hamming graph. -/
def unit_hamming_triangle_free {n q : ℕ} (A : Finset (Fin n → Fin q)) : Prop := ∀ ⦃x y z : Fin n → Fin q⦄, x ∈ A → y ∈ A → z ∈ A →
    x ≠ y → y ≠ z → x ≠ z →
    ¬(hammingDist x y = 1 ∧ hammingDist y z = 1 ∧ hammingDist x z = 1)
See it in the graphDiscuss this resultChallenge it