op_1499_quaternary_length_two
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.
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).
uses
is_square_path_coloringsimp only [is_square_path_coloring]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.
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).
- The theorem is proved entirely by exhaustive finite calculation across all 16 quaternary words of length 2 using Lean's `decide` tactic, rather than via general combinatorial inequalities.
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.
/-- 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