AFTD Auto-Formalizing Theoretical Domains

op_1499_ternary_length_two

theoremverifiedoriginal

For every ternary word y of length 2 (y : Fin 2 → Fin 3), the two-deletion hinge sums satisfy qary_two_deletion_hinge 3 2 2 y ≥ 2^2 + 2 - 1 and qary_two_deletion_hinge 3 2 3 y ≥ Nat.choose 2 2, and both equalities qary_two_deletion_hinge 3 2 2 y = 2^2 + 2 - 1 and qary_two_deletion_hinge 3 2 3 y = Nat.choose 2 2 hold simultaneously if and only if y is a proper coloring of the square of the path (is_square_path_coloring y).

Statement

theorem op_1499_ternary_length_two
    (y : Fin 2 → Fin 3) :
    qary_two_deletion_hinge 3 2 2 y ≥ 2^2 + 2 - 1 ∧
    qary_two_deletion_hinge 3 2 3 y ≥ Nat.choose 2 2 ∧
    ((qary_two_deletion_hinge 3 2 2 y = 2^2 + 2 - 1 ∧
      qary_two_deletion_hinge 3 2 3 y = Nat.choose 2 2) ↔
     is_square_path_coloring y)
Related work
OP-1499; arXiv:2611.01064
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • qary_two_deletion_hingeFor integers q, n, and r, and a q-ary word y of length n, qary_two_deletion_hinge q n r y is the sum over all words x : Fin (n + 2) → Fin…
  • is_square_path_coloringA word y : Fin n → Fin q is a square path coloring if y i ≠ y j for all i, j : Fin n with j.val = i.val + 1 or j.val = i.val + 2.

Read back from the Lean

For every function $y : \text{Fin } 2 \to \text{Fin } 3$ (i.e., every ternary word of length 2): 1. qary_two_deletion_hinge 3 2 2 y is greater than or equal to $2^2 + 2 - 1$ ($= 5$); 2. qary_two_deletion_hinge 3 2 3 y is greater than or equal to $\binom{2}{2}$ ($= 1$); 3. Both of these lower bounds hold with equality (that is, qary_two_deletion_hinge 3 2 2 y = 5 and qary_two_deletion_hinge 3 2 3 y = 1) if and only if y is a square path coloring (is_square_path_coloring y).

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 establishes OP-1499 hinge majorization for ternary words of length 2 by exhaustive finite verification. First, decidability of the square-path coloring condition is proved by unfolding its definition to a bounded quantifier over a finite domain. The universal statement across all 9 ternary words of length 2 is then verified by the `decide` tactic via exhaustive computation. Finally, the main theorem specializes this universal result to an arbitrary given word $y$.

  1. The property of being a proper coloring of the square of the path is decidable for any word $y : \text{Fin } n \to \text{Fin } q$.

    We unfold the definition of `is_square_path_coloring`, which requires that $y(i) \neq y(j)$ whenever $i, j \in \text{Fin } n$ satisfy $i+1 = j$ or $i+2 = j$. Because $\text{Fin } n$ is a finite type and equality on $\text{Fin } q$ is decidable, typeclass inference (`infer_instance`) automatically synthesizes a `Decidable` instance for this bounded universal quantification.

    lines 1–4

    instance op_1499_ternary_length_two_dec (n q : ℕ) (y : Fin n → Fin q) :
        Decidable (is_square_path_coloring y) := by
      unfold is_square_path_coloring
      infer_instance
  2. For all ternary words $y : \text{Fin } 2 \to \text{Fin } 3$, the hinge sums satisfy $\text{hinge}(3, 2, 2, y) \ge 5$ and $\text{hinge}(3, 2, 3, y) \ge 1$, with both equalities holding simultaneously if and only if $y$ is a proper coloring of $P_2^2$. automation

    Since there are only $3^2 = 9$ ternary words of length 2, and the hinge sums involve counting embeddings into the $3^4 = 81$ ternary words of length 4, the universal statement is completely finite. Using the decidability instance established above, the `decide` tactic verifies the claim by exhaustive finite computation.

    lines 6–12

    uses op_1499_ternary_length_two_dec

    theorem op_1499_ternary_length_two_all : ∀ y : Fin 2 → Fin 3,
        qary_two_deletion_hinge 3 2 2 y ≥ 2^2 + 2 - 1 ∧
        qary_two_deletion_hinge 3 2 3 y ≥ Nat.choose 2 2 ∧
        ((qary_two_deletion_hinge 3 2 2 y = 2^2 + 2 - 1 ∧
          qary_two_deletion_hinge 3 2 3 y = Nat.choose 2 2) ↔
         is_square_path_coloring y) := by
      decide
  3. The hinge sum inequalities and simultaneous equality condition hold for the given word $y : \text{Fin } 2 \to \text{Fin } 3$.

    The main theorem `op_1499_ternary_length_two` specializes the universal statement `op_1499_ternary_length_two_all` to the arbitrary input word $y$.

    lines 15–21

    uses op_1499_ternary_length_two_all

    theorem op_1499_ternary_length_two
        (y : Fin 2 → Fin 3) :
        qary_two_deletion_hinge 3 2 2 y ≥ 2^2 + 2 - 1 ∧
        qary_two_deletion_hinge 3 2 3 y ≥ Nat.choose 2 2 ∧
        ((qary_two_deletion_hinge 3 2 2 y = 2^2 + 2 - 1 ∧
          qary_two_deletion_hinge 3 2 3 y = Nat.choose 2 2) ↔
         is_square_path_coloring y) := op_1499_ternary_length_two_all y
op_1499_ternary_length_two_dec
For any word $y : \text{Fin } n \to \text{Fin } q$, the property that $y$ is a proper coloring of the square of the path $P_n^2$ is decidable.
op_1499_ternary_length_two_all
For all ternary words $y$ of length 2, the two-deletion hinge sums satisfy $\text{hinge}(3, 2, 2, y) \ge 5$ and $\text{hinge}(3, 2, 3, y) \ge 1$, with equality holding simultaneously in both bounds if and only if $y$ is a proper coloring of $P_2^2$.

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

instance op_1499_ternary_length_two_dec (n q : ℕ) (y : Fin n → Fin q) :    Decidable (is_square_path_coloring y) := by  unfold is_square_path_coloring  infer_instancetheorem op_1499_ternary_length_two_all : ∀ y : Fin 2 → Fin 3,    qary_two_deletion_hinge 3 2 2 y ≥ 2^2 + 2 - 1 ∧    qary_two_deletion_hinge 3 2 3 y ≥ Nat.choose 2 2 ∧    ((qary_two_deletion_hinge 3 2 2 y = 2^2 + 2 - 1 ∧      qary_two_deletion_hinge 3 2 3 y = Nat.choose 2 2) ↔     is_square_path_coloring y) := by  decide/-- Verification of OP-1499 hinge majorization for all ternary words of length 2. -/theorem op_1499_ternary_length_two    (y : Fin 2 → Fin 3) :    qary_two_deletion_hinge 3 2 2 y ≥ 2^2 + 2 - 1 ∧    qary_two_deletion_hinge 3 2 3 y ≥ Nat.choose 2 2 ∧    ((qary_two_deletion_hinge 3 2 2 y = 2^2 + 2 - 1 ∧      qary_two_deletion_hinge 3 2 3 y = Nat.choose 2 2) ↔     is_square_path_coloring y) := op_1499_ternary_length_two_all y
See it in the graphDiscuss this resultChallenge it