AFTD Auto-Formalizing Theoretical Domains

op_1537_ternary_length_two_one_deletion

theoremverifiedoriginal

For any nonconstant ternary word y : Fin 2 → Fin 3 of length 2, there exists a longest run [a, b) of y and an immediately adjacent run [a', b') of y such that the word y' obtained by changing every letter in [a', b') to y a satisfies qary_multiple_deletion_hinge 1 3 2 r y ≤ qary_multiple_deletion_hinge 1 3 2 r y' for all r ≥ 1, with strict inequality for at least one r ≥ 1.

Statement

theorem op_1537_ternary_length_two_one_deletion
    (y : Fin 2 → Fin 3) (hy : ¬ is_constant_word y) :
    ∃ (a b : ℕ) (hR : is_longest_word_run y a b) (a' b' : ℕ) (hR' : is_word_run y a' b')
      (hadj : b' = a ∨ b = a') (ha : a < 2),
      let y' := word_absorb_run y a' b' (y ⟨a, ha⟩)
      (∀ r : ℕ, 1 ≤ r → qary_multiple_deletion_hinge 1 3 2 r y ≤ qary_multiple_deletion_hinge 1 3 2 r y') ∧
      (∃ r : ℕ, 1 ≤ r ∧ qary_multiple_deletion_hinge 1 3 2 r y < qary_multiple_deletion_hinge 1 3 2 r y')
Related work
knowledgebase (OP-1537, OP-1534)
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • is_word_runA pair of indices 0 ≤ a < b ≤ n forms a run [a, b) of a word y : Fin n → α if all symbols y i for a ≤ i < b are equal, and the block…
  • is_longest_word_runA run [a, b) of a word y : Fin n → α is a longest run if its length b - a is greater than or equal to the length b' - a' of every run [a',…
  • word_absorb_runThe word obtained from y : Fin n → α by changing every letter in the index interval [a', b') to c, leaving all letters outside the…
  • qary_multiple_deletion_hingeFor natural numbers t, q, n, and r, and a q-ary word y of length n (y : Fin n → Fin q), the t-deletion hinge sum is the sum over all words…
  • is_constant_wordA word y on the finite index set Fin n is constant if all its symbols are equal, that is, y i = y j for all i and j in Fin n.
  • op_1534_ternary_length_two_one_deletionFor every ternary word y of length 2 (y : Fin 2 → Fin 3), the one-deletion hinge sums at thresholds r = 1 and r = 2 satisfy…
  • decidable_is_constant_wordDecidability instance for the predicate that a word on Fin n over a type with decidable equality is constant.
  • q_ary_subsequence_num_embeddingsFor words u of length m and w of length n over an alphabet of size q represented by Fin q, q_ary_subsequence_num_embeddings q m n u w is…

Read back from the Lean

For every ternary word $y : \mathrm{Fin}\ 2 \to \mathrm{Fin}\ 3$ of length 2 that is not constant (i.e. not all its symbols are equal), there exist natural numbers $a$ and $b$ such that the interval $[a, b)$ is a longest maximal run of identical symbols in $y$, and there exist natural numbers $a'$ and $b'$ such that $[a', b')$ is a maximal run of identical symbols in $y$, such that: 1. The two runs are adjacent (either $b' = a$ or $b = a'$); 2. $a < 2$; and 3. Letting $y'$ be the word obtained by replacing the symbols of $y$ on the index interval $[a', b')$ with the symbol $y(a)$ (the "absorbed" word): - For all natural numbers $r \ge 1$, the 1-deletion ternary hinge sum of $y$ with threshold $r$ is less than or equal to that of $y'$, i.e., $$\sum_{x \in (\mathrm{Fin}\ 3)^3} \max(0, \mathrm{emb}(y, x) - r) \le \sum_{x \in (\mathrm{Fin}\ 3)^3} \max(0, \mathrm{emb}(y', x) - r),$$ where $\mathrm{emb}(u, x)$ is the number of strictly monotone functions $f : \mathrm{Fin}\ 2 \to \mathrm{Fin}\ 3$ such that $x \circ f = u$; and - There exists a natural number $r \ge 1$ for which this inequality is strict ($<$).

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 proves OP-1537 in the base case of length-2 ternary words with 1 deletion (n = 2, q = 3, t = 1). Because y is nonconstant of length 2, its two letters must differ, meaning y decomposes into two adjacent singleton runs [0, 1) and [1, 2). Absorbing the second run into the letter y(0) produces a constant word y'. By exhaustive finite evaluation, the deletion hinge values for nonconstant versus constant words are identical at r = 1 (both equal 2), strictly greater for constant words at r = 2 (0 versus 1), and vanish for both when r ≥ 3 because embedding counts cannot exceed 3. Consequently, the hinge value never decreases and strictly increases at r = 2.

  1. For any ternary word of length 2, the deletion hinge at r = 1 is 2; at r = 2, the hinge is 0 if the word is nonconstant and 1 if the word is constant. automation

    Since the domain Fin 2 → Fin 3 consists of only 3² = 9 words, Lean verifies both characterizations (`hnc_vals` and `hc_vals`) by exhaustive evaluation using the `decide` tactic.

    lines 9–12

      have hnc_vals : ∀ (z : Fin 2 → Fin 3), ¬ is_constant_word z →
          qary_multiple_deletion_hinge 1 3 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 3 2 2 z = 0 := by decide
      have hc_vals : ∀ (z : Fin 2 → Fin 3), is_constant_word z →
          qary_multiple_deletion_hinge 1 3 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 3 2 2 z = 1 := by decide
  2. For any ternary word z of length 2 and any r ≥ 3, the deletion hinge value at r is 0.

    Any supersequence x of length 3 can contain a length-2 word w as a subsequence at most (3 choose 2) = 3 times (`hbound`, checked by `decide`). In the definition of the hinge function, each term in the sum over all x is the truncated natural difference (embeddings - r). Since the number of embeddings is at most 3 ≤ r, each difference is 0 by `Nat.sub_eq_zero_of_le` and `le_trans`, so the entire sum is 0 by `Finset.sum_eq_zero`.

    lines 13–21

    uses Finset.sum_eq_zero, Nat.sub_eq_zero_of_le, le_trans

      have hzero : ∀ (z : Fin 2 → Fin 3) (r : ℕ), 3 ≤ r → qary_multiple_deletion_hinge 1 3 2 r z = 0 := by
        intro z r hr
        have hbound : ∀ (x : Fin 3 → Fin 3) (w : Fin 2 → Fin 3),
            q_ary_subsequence_num_embeddings 3 2 3 w x ≤ 3 := by decide
        unfold qary_multiple_deletion_hinge
        apply Finset.sum_eq_zero
        intro x _
        apply Nat.sub_eq_zero_of_le
        exact le_trans (hbound x z) hr
  3. The two characters of y are distinct: y(0) ≠ y(1).

    Assume for contradiction that y(0) = y(1). Then y(i) = y(j) for all i, j ∈ {0, 1}, meaning y is a constant word. This contradicts the hypothesis that y is nonconstant (`hy`).

    lines 22–26

      have hne : y ⟨0, by norm_num⟩ ≠ y ⟨1, by norm_num⟩ := by
        intro h
        apply hy
        intro i j
        fin_cases i <;> fin_cases j <;> simp_all
  4. The interval [0, 1) is a longest run of y.

    First, [0, 1) is a valid run (`is_word_run`): its only index is 0, it starts at 0, and its right endpoint 1 has a distinct symbol y(1) ≠ y(0) by `hne`. Second, it is a longest run: any run [a', b') of y has length b' - a' ≤ 2. If b' - a' > 1, then a' = 0 and b' = 2, which would imply y(1) = y(0), contradicting `hne`. Hence every run has length at most 1 - 0 = 1.

    lines 27–50

    uses Or.inl, Or.inr, Ne.symm, Fin.ext, Nat.sub_zero, not_le.mp

      have hR : is_longest_word_run y 0 1 := by
        have hrun : is_word_run y 0 1 := by
          refine ⟨by norm_num, by norm_num, ?_, Or.inl rfl, Or.inr ⟨by norm_num, Ne.symm hne⟩⟩
          intro i hi
          obtain ⟨-, hi2⟩ := hi
          have hi0 : i = ⟨0, by norm_num⟩ := by
            apply Fin.ext
            simp only
            omega
          rw [hi0]
        refine ⟨hrun, ?_⟩
        intro a' b' hr'
        obtain ⟨hab, hbn, hconst, -, -⟩ := hr'
        simp only [Nat.sub_zero]
        by_contra h
        have h2 : 1 < b' - a' := not_le.mp h
        have ha' : a' = 0 := by omega
        have hb' : b' = 2 := by omega
        subst ha'
        subst hb'
        have h1 : y ⟨1, by norm_num⟩ = y ⟨0, by norm_num⟩ := by
          have := hconst ⟨1, by norm_num⟩ ⟨by norm_num, by norm_num⟩
          simpa using this
        exact hne h1.symm
  5. The interval [1, 2) is a run of y.

    The interval [1, 2) contains only the index 1, its left endpoint is preceded by y(0) ≠ y(1), and its right endpoint is the end of the word (n = 2). Thus [1, 2) satisfies all conditions of `is_word_run`.

    lines 51–59

    uses Or.inr, Or.inl, Fin.ext

      have hR' : is_word_run y 1 2 := by
        refine ⟨by norm_num, by norm_num, ?_, Or.inr ⟨by norm_num, hne⟩, Or.inl rfl⟩
        intro i hi
        obtain ⟨hi1, -⟩ := hi
        have hii : i = ⟨1, by norm_num⟩ := by
          apply Fin.ext
          simp only
          omega
        rw [hii]
  6. Instantiate the existential witnesses with a = 0, b = 1 (the longest run) and a' = 1, b' = 2 (the adjacent run).

    We supply the witnesses a = 0, b = 1, the proof `hR` that [0, 1) is a longest run, a' = 1, b' = 2, the proof `hR'` that [1, 2) is a run, the adjacency b = a' = 1 via `Or.inr rfl`, and the bound a < 2.

    lines 60–61

    uses Or.inr

      refine ⟨0, 1, hR, 1, 2, hR', Or.inr rfl, by norm_num, ?_⟩
      dsimp only
  7. The word y' obtained by absorbing run [1, 2) into y(0) is a constant word.

    For every index i ∈ {0, 1}, y'(i) = y(0): at index 0, it falls outside [1, 2) so it retains y(0); at index 1, it falls inside [1, 2) so it is overwritten with y(0). Therefore, y'(i) = y'(j) = y(0) for all i, j, showing y' is constant.

    lines 62–67

      have hy'const : is_constant_word (word_absorb_run y 1 2 (y ⟨0, by norm_num⟩)) := by
        intro i j
        have hi : ∀ i : Fin 2, word_absorb_run y 1 2 (y ⟨0, by norm_num⟩) i = y ⟨0, by norm_num⟩ := by
          intro i
          fin_cases i <;> simp [word_absorb_run]
        rw [hi i, hi j]
  8. For every r ≥ 1, the deletion hinge value satisfies hinge(y) ≤ hinge(y').

    Split into cases using `lt_or_ge r 3`: if r < 3, then r = 1 or r = 2. For r = 1, both words give hinge value 2 by `hnc_vals` and `hc_vals`, so 2 ≤ 2. For r = 2, hinge(y) = 0 ≤ 1 = hinge(y'). For r ≥ 3, `hzero` shows hinge(y) = 0, which is ≤ hinge(y') by `Nat.zero_le`.

    lines 68–77

    uses lt_or_ge, Nat.zero_le

      constructor
      · intro r hr
        rcases lt_or_ge r 3 with h3 | h3
        · have : r = 1 ∨ r = 2 := by omega
          rcases this with rfl | rfl
          · rw [(hnc_vals y hy).1, (hc_vals _ hy'const).1]
          · rw [(hnc_vals y hy).2, (hc_vals _ hy'const).2]
            norm_num
        · rw [hzero y r h3]
          exact Nat.zero_le _
  9. There exists r ≥ 1 such that hinge(y) < hinge(y'), specifically at r = 2.

    Taking r = 2, we have 1 ≤ 2, and the hinge values are hinge(y) = 0 and hinge(y') = 1 by `hnc_vals` and `hc_vals`. Since 0 < 1, the strict inequality holds.

    lines 78–80

      · refine ⟨2, by norm_num, ?_⟩
        rw [(hnc_vals y hy).2, (hc_vals _ hy'const).2]
        norm_num
Finset.sum_eq_zero
A finite sum is zero if every term in the sum is zero.
Nat.sub_eq_zero_of_le
For natural numbers n and m, if n ≤ m, then their truncated difference n - m is 0.
le_trans
The order relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Or.inl
Proves a disjunction a ∨ b from a proof of its left conjunct a.
Or.inr
Proves a disjunction a ∨ b from a proof of its right conjunct b.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Fin.ext
Two elements of Fin n are equal if their underlying natural values are equal.
Nat.sub_zero
Subtracting zero from any natural number leaves it unchanged (n - 0 = n).
not_le.mp
For natural numbers, if a ≰ b, then b < a.
lt_or_ge
In any linear order, either a < b or b ≤ a.
Nat.zero_le
Zero is less than or equal to any natural number (0 ≤ n).

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

/-- OP-1537 for ternary words of length 2 with one deletion (n = 2, q = 3, t = 1). -/theorem op_1537_ternary_length_two_one_deletion    (y : Fin 2 → Fin 3) (hy : ¬ is_constant_word y) :    ∃ (a b : ℕ) (hR : is_longest_word_run y a b) (a' b' : ℕ) (hR' : is_word_run y a' b')      (hadj : b' = a ∨ b = a') (ha : a < 2),      let y' := word_absorb_run y a' b' (y ⟨a, ha⟩)      (∀ r : ℕ, 1 ≤ r → qary_multiple_deletion_hinge 1 3 2 r y ≤ qary_multiple_deletion_hinge 1 3 2 r y') ∧      (∃ r : ℕ, 1 ≤ r ∧ qary_multiple_deletion_hinge 1 3 2 r y < qary_multiple_deletion_hinge 1 3 2 r y') := by  have hnc_vals : ∀ (z : Fin 2 → Fin 3), ¬ is_constant_word z →      qary_multiple_deletion_hinge 1 3 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 3 2 2 z = 0 := by decide  have hc_vals : ∀ (z : Fin 2 → Fin 3), is_constant_word z →      qary_multiple_deletion_hinge 1 3 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 3 2 2 z = 1 := by decide  have hzero : ∀ (z : Fin 2 → Fin 3) (r : ℕ), 3 ≤ r → qary_multiple_deletion_hinge 1 3 2 r z = 0 := by    intro z r hr    have hbound : ∀ (x : Fin 3 → Fin 3) (w : Fin 2 → Fin 3),        q_ary_subsequence_num_embeddings 3 2 3 w x ≤ 3 := by decide    unfold qary_multiple_deletion_hinge    apply Finset.sum_eq_zero    intro x _    apply Nat.sub_eq_zero_of_le    exact le_trans (hbound x z) hr  have hne : y ⟨0, by norm_num⟩ ≠ y ⟨1, by norm_num⟩ := by    intro h    apply hy    intro i j    fin_cases i <;> fin_cases j <;> simp_all  have hR : is_longest_word_run y 0 1 := by    have hrun : is_word_run y 0 1 := by      refine ⟨by norm_num, by norm_num, ?_, Or.inl rfl, Or.inr ⟨by norm_num, Ne.symm hne⟩⟩      intro i hi      obtain ⟨-, hi2⟩ := hi      have hi0 : i = ⟨0, by norm_num⟩ := by        apply Fin.ext        simp only        omega      rw [hi0]    refine ⟨hrun, ?_⟩    intro a' b' hr'    obtain ⟨hab, hbn, hconst, -, -⟩ := hr'    simp only [Nat.sub_zero]    by_contra h    have h2 : 1 < b' - a' := not_le.mp h    have ha' : a' = 0 := by omega    have hb' : b' = 2 := by omega    subst ha'    subst hb'    have h1 : y ⟨1, by norm_num⟩ = y ⟨0, by norm_num⟩ := by      have := hconst ⟨1, by norm_num⟩ ⟨by norm_num, by norm_num⟩      simpa using this    exact hne h1.symm  have hR' : is_word_run y 1 2 := by    refine ⟨by norm_num, by norm_num, ?_, Or.inr ⟨by norm_num, hne⟩, Or.inl rfl⟩    intro i hi    obtain ⟨hi1, -⟩ := hi    have hii : i = ⟨1, by norm_num⟩ := by      apply Fin.ext      simp only      omega    rw [hii]  refine ⟨0, 1, hR, 1, 2, hR', Or.inr rfl, by norm_num, ?_⟩  dsimp only  have hy'const : is_constant_word (word_absorb_run y 1 2 (y ⟨0, by norm_num⟩)) := by    intro i j    have hi : ∀ i : Fin 2, word_absorb_run y 1 2 (y ⟨0, by norm_num⟩) i = y ⟨0, by norm_num⟩ := by      intro i      fin_cases i <;> simp [word_absorb_run]    rw [hi i, hi j]  constructor  · intro r hr    rcases lt_or_ge r 3 with h3 | h3    · have : r = 1 ∨ r = 2 := by omega      rcases this with rfl | rfl      · rw [(hnc_vals y hy).1, (hc_vals _ hy'const).1]      · rw [(hnc_vals y hy).2, (hc_vals _ hy'const).2]        norm_num    · rw [hzero y r h3]      exact Nat.zero_le _  · refine ⟨2, by norm_num, ?_⟩    rw [(hnc_vals y hy).2, (hc_vals _ hy'const).2]    norm_num
See it in the graphDiscuss this resultChallenge it