op_1499_ternary_length_two
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$.
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.
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
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.
uses
op_1499_ternary_length_two_dectheorem 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
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$.
uses
op_1499_ternary_length_two_alltheorem 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$.
- The universal statement `op_1499_ternary_length_two_all` is proved entirely by computational evaluation (`decide`), exhaustively checking all $3^2 = 9$ ternary words of length 2 and their two-deletion subsequence counts across all $3^4 = 81$ ternary words of length 4.
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.
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