AFTD Auto-Formalizing Theoretical Domains

op_1503_spaced_word_two_iff

theoremverified

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$.

  1. 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.

    line 4

      constructor
  2. Every 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)$.

    lines 5–6

      · intro h i j hij
        exact h i j (by omega) (by omega)
  3. 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)$.

    lines 7–8

      · 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

/-- 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)
See it in the graphDiscuss this resultChallenge it