AFTD Auto-Formalizing Theoretical Domains

op_1499_quaternary_length_two

theoremverifiedoriginal

For every quaternary word y of length 2 (y : Fin 2 → Fin 4), the two-deletion hinge sums satisfy qary_two_deletion_hinge 4 2 2 y ≥ 2^2 + 2 - 1 and qary_two_deletion_hinge 4 2 3 y ≥ Nat.choose 2 2, and both equalities qary_two_deletion_hinge 4 2 2 y = 2^2 + 2 - 1 and qary_two_deletion_hinge 4 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_quaternary_length_two
    (y : Fin 2 → Fin 4) :
    qary_two_deletion_hinge 4 2 2 y ≥ 2^2 + 2 - 1 ∧
    qary_two_deletion_hinge 4 2 3 y ≥ Nat.choose 2 2 ∧
    ((qary_two_deletion_hinge 4 2 2 y = 2^2 + 2 - 1 ∧
      qary_two_deletion_hinge 4 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 sequence $y : \text{Fin } 2 \to \text{Fin } 4$ (a quaternary word of length 2): 1. qary_two_deletion_hinge 4 2 2 y is at least $2^2 + 2 - 1 = 5$, 2. qary_two_deletion_hinge 4 2 3 y is at least $\binom{2}{2} = 1$, and 3. Both equalities qary_two_deletion_hinge 4 2 2 y = 2^2 + 2 - 1 and qary_two_deletion_hinge 4 2 3 y = Nat.choose 2 2 hold simultaneously if and only if $y$ is a square-path coloring (i.e., 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 theorem establishes two hinge majorization inequalities and an exact equality characterization for quaternary words of length 2. After unfolding the definition of a square-path coloring, the statement is reduced to a finite, decidable proposition over the 16 quaternary words of length 2, which Lean proves by exhaustive computational verification.

  1. The square-path coloring condition on y is unfolded into its explicit definition.

    We unfold the definition of `is_square_path_coloring y`, which states that any two indices i and j in Fin 2 whose indices differ by 1 or 2 must have distinct colors y(i) ≠ y(j).

    line 9

    uses is_square_path_coloring

      simp only [is_square_path_coloring]
  2. The hinge inequalities and the equivalence with square-path colorability hold for every quaternary word of length 2. automation

    Because y is a word of length 2 over an alphabet of size 4 (Fin 2 → Fin 4), there are only 4^2 = 16 possible words. Reverting y turns the goal into a universally quantified statement over a finite domain with decidable relations and computable sums, which Lean checks by exhaustive evaluation of all 16 cases.

    line 10

      decide +revert
is_square_path_coloring
A sequence y is a square-path coloring if any two positions at graph distance 1 or 2 in the path graph receive distinct values (colors).

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

/-- Verification of OP-1499 hinge majorization for all quaternary words of length 2. -/theorem op_1499_quaternary_length_two    (y : Fin 2 → Fin 4) :    qary_two_deletion_hinge 4 2 2 y ≥ 2^2 + 2 - 1 ∧    qary_two_deletion_hinge 4 2 3 y ≥ Nat.choose 2 2 ∧    ((qary_two_deletion_hinge 4 2 2 y = 2^2 + 2 - 1 ∧      qary_two_deletion_hinge 4 2 3 y = Nat.choose 2 2) ↔     is_square_path_coloring y) := by  simp only [is_square_path_coloring]  decide +revert
See it in the graphDiscuss this resultChallenge it