AFTD Auto-Formalizing Theoretical Domains

op_1503_canonical_spaced_word_is_spaced

theoremverified

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.

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

    line 4

      intro i j hij hjt heq
  2. i ≡ 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).

    lines 5–7

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

    lines 8–10

    uses Nat.ModEq.dvd', Nat.sub_pos_of_lt, Nat.le_of_dvd

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

    line 11

      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

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