op_1503_canonical_spaced_word_is_spaced
For any natural numbers t, q, and n with t + 1 ≤ q, the canonical spaced word qary_canonical_spaced_word t q n htq is t-spaced.
Statement
theorem op_1503_canonical_spaced_word_is_spaced (t q n : ℕ) (htq : t + 1 ≤ q) :
is_t_spaced_word t (qary_canonical_spaced_word t q n htq)- Source
- knowledgebase, OP-1503
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.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.
- qary_canonical_spaced_wordFor natural numbers t, q, and n with t + 1 ≤ q, the canonical spaced word of length n is the word sending each index i : Fin n to (i.val %…
Read back from the Lean
For all natural numbers $t$, $q$, and $n$, given a proof that $t + 1 \le q$, the canonical $q$-ary word of length $n$ (which maps each index $i \in \{0, \dots, n-1\}$ to $i \bmod (t + 1) \in \{0, \dots, q-1\}$) is a $t$-spaced word: any two positions separated by at least 1 and at most $t$ receive different symbols.
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 canonical q-ary word maps each index i to i mod (t + 1). To show it is t-spaced, we assume for contradiction that two distinct indices i < j within distance t (so j ≤ i + t) have the same value. This equality implies i ≡ j mod (t + 1), which forces t + 1 to divide the positive difference j - i, and hence t + 1 ≤ j - i. That requires j ≥ i + t + 1, contradicting j ≤ i + t.
Assume for contradiction that two indices within distance t evaluate to the same value.
By definition, a word is t-spaced if any two distinct indices within distance at most t take distinct values. We introduce indices i < j with j ≤ i + t and assume that the canonical word assigns them the same symbol, reducing the goal to deriving a contradiction.
intro i j hij hjt heqi ≡ j [MOD t + 1].
Since the word values at i and j are identical, their underlying natural number values are equal. Simplifying with the definition of qary_canonical_spaced_word, which assigns each index k the remainder k % (t + 1), gives i % (t + 1) = j % (t + 1).
have h_val : (qary_canonical_spaced_word t q n htq i).val = (qary_canonical_spaced_word t q n htq j).val := by rw [heq] dsimp [qary_canonical_spaced_word] at h_val
t + 1 ≤ j - i.
Because i ≡ j [MOD t + 1], the modulus t + 1 divides j - i by Nat.ModEq.dvd'. Since i < j, the difference j - i is strictly positive by Nat.sub_pos_of_lt. Therefore, Nat.le_of_dvd implies that t + 1 ≤ j - i.
uses
Nat.ModEq.dvd',Nat.sub_pos_of_lt,Nat.le_of_dvdhave hdvd : t + 1 ∣ j.val - i.val := Nat.ModEq.dvd' h_val have hpos : 0 < j.val - i.val := Nat.sub_pos_of_lt hij have hle : t + 1 ≤ j.val - i.val := Nat.le_of_dvd hpos hdvd
A contradiction is derived. automation
The inequality t + 1 ≤ j - i means j ≥ i + t + 1, contradicting the assumption j ≤ i + t. Linear integer arithmetic (omega) detects this contradiction and closes the goal.
omega
Nat.ModEq.dvd'- If two natural numbers are congruent modulo n, then n divides their difference.
Nat.sub_pos_of_lt- If m < n for natural numbers m and n, then n - m > 0.
Nat.le_of_dvd- If a positive natural number is divisible by m, then m is less than or equal to that number.
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.
/-- The canonical periodic word is t-spaced. -/theorem op_1503_canonical_spaced_word_is_spaced (t q n : ℕ) (htq : t + 1 ≤ q) : is_t_spaced_word t (qary_canonical_spaced_word t q n htq) := by intro i j hij hjt heq have h_val : (qary_canonical_spaced_word t q n htq i).val = (qary_canonical_spaced_word t q n htq j).val := by rw [heq] dsimp [qary_canonical_spaced_word] at h_val have hdvd : t + 1 ∣ j.val - i.val := Nat.ModEq.dvd' h_val have hpos : 0 < j.val - i.val := Nat.sub_pos_of_lt hij have hle : t + 1 ≤ j.val - i.val := Nat.le_of_dvd hpos hdvd omega