AFTD Auto-Formalizing Theoretical Domains

op_1537_binary_length_two_one_deletion

theoremverifiedoriginal

For any nonconstant binary word y : Fin 2 → Fin 2 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 2 2 r y ≤ qary_multiple_deletion_hinge 1 2 2 r y' for all r ≥ 1, with strict inequality for at least one r ≥ 1.

Statement

theorem op_1537_binary_length_two_one_deletion
    (y : Fin 2 → Fin 2) (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 2 2 r y ≤ qary_multiple_deletion_hinge 1 2 2 r y') ∧
      (∃ r : ℕ, 1 ≤ r ∧ qary_multiple_deletion_hinge 1 2 2 r y < qary_multiple_deletion_hinge 1 2 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_binary_length_two_one_deletionFor every binary word y of length 2 (y : Fin 2 → Fin 2), 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 binary word $y$ of length 2 (a function $y : \mathrm{Fin}\ 2 \to \mathrm{Fin}\ 2$) that is not constant (i.e., not all of its characters are equal), there exist natural numbers $a, b$, a proof that $[a, b)$ is a longest maximal run of identical symbols in $y$, natural numbers $a', b'$, a proof that $[a', b')$ is a maximal run of identical symbols in $y$, a proof that the two runs are adjacent ($b' = a$ or $b = a'$), and a bound $a < 2$, such that: defining $y' : \mathrm{Fin}\ 2 \to \mathrm{Fin}\ 2$ as the word obtained from $y$ by replacing the characters at indices in $[a', b')$ with $y(a)$, 1. for all natural numbers $r \ge 1$, the 1-deletion $r$-hinge sum of $y$ is at most that of $y'$, and 2. for some natural number $r \ge 1$, the 1-deletion $r$-hinge sum of $y$ is strictly less than that of $y'$.

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

For any nonconstant binary word y of length 2, the two letters y(0) and y(1) are distinct, so the intervals [0, 1) and [1, 2) form adjacent runs of length 1, with [0, 1) being a longest run. Absorbing the adjacent run [1, 2) into the letter y(0) produces a constant word y'. The deletion hinge values are determined by exhaustive evaluation: for any nonconstant word of length 2 they are 2, 0, 0 for r = 1, 2, ≥ 3, whereas for any constant word they are 2, 1, 0. Comparing these values proves that the hinge function is nondecreasing for all r ≥ 1 and strictly increases at r = 2.

  1. For nonconstant binary words of length 2, the deletion hinge values at r = 1 and r = 2 are 2 and 0 respectively; for constant words, they are 2 and 1. automation

    Because there are only four binary words of length 2 and eight potential supersequences of length 3, the deletion hinge values for r = 1 and r = 2 on both constant and nonconstant words are evaluated directly by exhaustive computation via boolean reflection.

    lines 9–12

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

    Any word of length 3 has only (3 choose 2) = 3 subsequences of length 2, so the number of embeddings of any length-2 word into any length-3 word is at most 3. For r ≥ 3, every term in the hinge summation is at most 3 - r = 0, so each term vanishes and the entire sum over supersequences is 0.

    lines 13–21

    uses Finset.sum_eq_zero, Nat.sub_eq_zero_of_le, le_trans

      have hzero : ∀ (z : Fin 2 → Fin 2) (r : ℕ), 3 ≤ r → qary_multiple_deletion_hinge 1 2 2 r z = 0 := by
        intro z r hr
        have hbound : ∀ (x : Fin 3 → Fin 2) (w : Fin 2 → Fin 2),
            q_ary_subsequence_num_embeddings 2 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 positions of y have distinct letters: y(0) ≠ y(1).

    If y(0) = y(1), then checking all four pairs of indices in {0, 1} shows that y(i) = y(j) everywhere, making y constant and contradicting the hypothesis that y is nonconstant.

    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 the word y.

    The single-element interval [0, 1) is a valid run because its boundary conditions hold: the left boundary is 0, and the right adjacent letter y(1) differs from y(0) since y(0) ≠ y(1). Furthermore, it is a longest run: any run [a', b') has length b' - a' ≤ 1, because if b' - a' > 1 with 0 ≤ a' < b' ≤ 2, we would have a' = 0 and b' = 2, which would imply y(1) = y(0), a contradiction.

    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 the word y.

    The single-element interval [1, 2) is a valid run: it is contained in the range [0, 2], its only index is 1, its left adjacent letter y(0) differs from y(1), and its right boundary reaches the length of the word.

    lines 51–59

    uses Or.inl, Or.inr, 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. Choosing [0, 1) as the longest run and [1, 2) as the adjacent run, absorbing [1, 2) into the symbol y(0) yields a constant word y'.

    The runs [0, 1) and [1, 2) meet the adjacency condition b = a' = 1. In the absorbed word y', the letter at index 1 is replaced by y(0), while the letter at index 0 remains y(0). Evaluating y' at both indices gives y(0), so y' is a constant word.

    lines 60–67

    uses Or.inr

      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]
  7. For all r ≥ 1, the deletion hinge value of y is less than or equal to that of y'.

    We split into cases based on r. If r < 3, then r is either 1 or 2: at r = 1, both y (nonconstant) and y' (constant) have hinge value 2; at r = 2, y has hinge value 0 and y' has hinge value 1, so 0 ≤ 1. If r ≥ 3, the hinge value of y is 0, which is at most any natural number.

    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 _
  8. There exists r ≥ 1 (specifically r = 2) where the deletion hinge value of y is strictly less than that of y'.

    At r = 2, the nonconstant word y has hinge value 0 while the constant word y' has hinge value 1; since 0 < 1, the inequality is strict.

    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 of terms is zero if every term in the sum is zero.
Nat.sub_eq_zero_of_le
For natural numbers, if n ≤ m, then truncated subtraction n - m equals 0.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Or.inl
A disjunction a ∨ b holds if the left disjunct a holds.
Or.inr
A disjunction a ∨ b holds if the right disjunct b holds.
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 a natural number leaves it unchanged: n - 0 = n.
not_le.mp
In a linear order, if a is not less than or equal to b, then b is strictly less than a.
lt_or_ge
In a linear order, for any two elements a and b, 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 binary words of length 2 with one deletion (n = 2, q = 2, t = 1). -/theorem op_1537_binary_length_two_one_deletion    (y : Fin 2 → Fin 2) (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 2 2 r y ≤ qary_multiple_deletion_hinge 1 2 2 r y') ∧      (∃ r : ℕ, 1 ≤ r ∧ qary_multiple_deletion_hinge 1 2 2 r y < qary_multiple_deletion_hinge 1 2 2 r y') := by  have hnc_vals : ∀ (z : Fin 2 → Fin 2), ¬ is_constant_word z →      qary_multiple_deletion_hinge 1 2 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 2 2 2 z = 0 := by decide  have hc_vals : ∀ (z : Fin 2 → Fin 2), is_constant_word z →      qary_multiple_deletion_hinge 1 2 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 2 2 2 z = 1 := by decide  have hzero : ∀ (z : Fin 2 → Fin 2) (r : ℕ), 3 ≤ r → qary_multiple_deletion_hinge 1 2 2 r z = 0 := by    intro z r hr    have hbound : ∀ (x : Fin 3 → Fin 2) (w : Fin 2 → Fin 2),        q_ary_subsequence_num_embeddings 2 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