op_1503_spaced_word_two_iff
For any word y : Fin n → Fin q, y is 2-spaced if and only if y is a proper coloring of the square of the path (is_square_path_coloring y).
Statement
theorem op_1503_spaced_word_two_iff {n q : ℕ} (y : Fin n → Fin q) :
is_t_spaced_word 2 y ↔ is_square_path_coloring y- Source
- knowledgebase, OP-1503
- Verified
- 12 Nov 2026
- Axioms
Quot.soundpropext- Built on 2
- is_t_spaced_wordA word y : Fin n → Fin q is t-spaced if y i ≠ y j for all indices i, j : Fin n satisfying i.val < j.val and j.val ≤ i.val + t.
- 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 any natural numbers $n$ and $q$, and any function $y : \mathrm{Fin}\ n \to \mathrm{Fin}\ q$, $y$ is a $2$-spaced word if and only if $y$ is a square path coloring.
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 states that a word $y$ is 2-spaced if and only if it is a proper coloring of the square of the path. By definition, 2-spacing requires $y(i) \ne y(j)$ whenever $i < j \le i + 2$, while square-path coloring requires $y(i) \ne y(j)$ whenever $j = i + 1$ or $j = i + 2$. The proof splits into both implications, each of which follows directly from the hypothesis because linear arithmetic over the natural numbers equates the condition $i < j \le i + 2$ with $j = i + 1 \lor j = i + 2$.
The equivalence is split into two implications.
To prove the "if and only if" statement, we reduce the goal to proving both directions: that any 2-spaced word is a proper square-path coloring, and conversely that any proper square-path coloring is 2-spaced.
constructorEvery 2-spaced word is a proper coloring of the square of the path.
Assume that $y$ is a 2-spaced word, and consider indices $i, j$ such that $i + 1 = j$ or $i + 2 = j$. From this disjunction, linear arithmetic on natural numbers (discharged by `omega`) implies both $i < j$ and $j \\le i + 2$. Applying the 2-spacing hypothesis to $i$ and $j$ then shows that $y(i) \\ne y(j)$.
· intro h i j hij exact h i j (by omega) (by omega)
Every proper coloring of the square of the path is a 2-spaced word.
Assume that $y$ is a proper coloring of the square of the path, and consider indices $i, j$ with $i < j$ and $j \\le i + 2$. For natural numbers, these two inequalities imply that either $i + 1 = j$ or $i + 2 = j$, which is verified by linear arithmetic (`omega`). Applying the square-path coloring hypothesis to $i$ and $j$ then gives $y(i) \\ne y(j)$.
· intro h i j hlt hle exact h i j (by omega)
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.
/-- Equivalence of 2-spacing and square-path proper coloring. -/theorem op_1503_spaced_word_two_iff {n q : ℕ} (y : Fin n → Fin q) : is_t_spaced_word 2 y ↔ is_square_path_coloring y := by constructor · intro h i j hij exact h i j (by omega) (by omega) · intro h i j hlt hle exact h i j (by omega)