AFTD Auto-Formalizing Theoretical Domains

tgreedy_rc_two_point_five_approx_of_parts

theoremverified

If t is an output of TGREEDY-RC on S, every MGREEDY-RC output T from S is RC-substring-free, GREEDY-RC from any RC-substring-free T to {t} satisfies 2|t| ≤ Σ_{u∈T}|u| + scs_rc_opt cm T, and every MGREEDY-RC output T from S has Σ_{u∈T}|u| ≤ 3·scs_rc_opt cm S and scs_rc_opt cm T ≤ 2·scs_rc_opt cm S, then 2|t| ≤ 5·scs_rc_opt cm S.

Statement

theorem tgreedy_rc_two_point_five_approx_of_parts {Γ : Type*} [DecidableEq Γ] (cm : Γ → Γ)
    (S : Finset (List Γ)) (t : List Γ) (ht : tgreedy_rc_output cm S t)
    (hT : ∀ T : Finset (List Γ), Relation.ReflTransGen (mgreedy_rc_step cm) (S, ∅) (∅, T) →
      rc_substring_free cm T)
    (hcomp : ∀ T : Finset (List Γ), rc_substring_free cm T →
      Relation.ReflTransGen (greedy_rc_step cm) T {t} →
      2 * t.length ≤ (∑ u ∈ T, u.length) + scs_rc_opt cm T)
    (hsum : ∀ T : Finset (List Γ), Relation.ReflTransGen (mgreedy_rc_step cm) (S, ∅) (∅, T) →
      (∑ u ∈ T, u.length) ≤ 3 * scs_rc_opt cm S)
    (hopt : ∀ T : Finset (List Γ), Relation.ReflTransGen (mgreedy_rc_step cm) (S, ∅) (∅, T) →
      scs_rc_opt cm T ≤ 2 * scs_rc_opt cm S) :
    2 * t.length ≤ 5 * scs_rc_opt cm S
Source
arXiv:2611.16573, Theorem 2 (TGREEDY-RC is a 2.5-approximation): the assembly of tgreedy_rc_two_point_five_approx from the four steps mgreedy_rc_output_rc_substring_free, greedy_rc_compression_half (Lemma 9), mgreedy_rc_output_length_sum_le_three_opt (Theorem 1) and mgreedy_rc_output_scs_rc_opt_le_two_opt, taken as hypotheses
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • rc_substring_freeFor a complement map cm : Γ → Γ and a finite set S : Finset (List Γ), rc_substring_free cm S holds when for all x, y ∈ S with x ≠ y, x is…
  • tgreedy_rc_outputFor cm : Γ → Γ, S : Finset (List Γ) and t : List Γ, tgreedy_rc_output cm S t holds when there is T : Finset (List Γ) such that the state…
  • mgreedy_rc_stepFor cm : Γ → Γ and states st = (S, T), st' : Finset (List Γ) × Finset (List Γ), mgreedy_rc_step cm st st' holds when, with V = S ∪…
  • scs_rc_optThe optimum of the Shortest Common Superstring with Reverse Complements problem: the least length of a string that contains s or rc(s) as…
  • greedy_rc_stepFor cm : Γ → Γ and S, S' : Finset (List Γ), greedy_rc_step cm S S' holds when S has more than one element and, with V = S ∪ rev_comp cm ''…

The proof, explained

The proof decomposes the TGREEDY-RC execution into its two phases: an MGREEDY-RC phase from S to an intermediate set T, followed by a GREEDY-RC phase from T to {t}. The hypotheses guarantee that T is reverse-complement substring-free, that GREEDY-RC on T bounds 2|t| by the sum of lengths in T plus the optimal superstring cost of T, and that the MGREEDY-RC phase bounds this sum of lengths by 3 · scs_rc_opt cm S and the cost of T by 2 · scs_rc_opt cm S. Summing these bounds yields 2|t| ≤ 5 · scs_rc_opt cm S.

  1. There exists an intermediate set of strings T such that (S, ∅) reduces to (∅, T) under MGREEDY-RC and T reduces to {t} under GREEDY-RC.

    By definition of `tgreedy_rc_output`, the hypothesis that t is an output of TGREEDY-RC on S provides an intermediate finite set T together with a sequence of MGREEDY-RC steps from (S, ∅) to (∅, T) (labeled h1) and a sequence of GREEDY-RC steps from T to {t} (labeled h2).

    line 13

      obtain ⟨T, h1, h2⟩ := ht
  2. The intermediate set T satisfies 2|t| ≤ ∑_{u ∈ T} |u| + scs_rc_opt cm T, ∑_{u ∈ T} |u| ≤ 3 · scs_rc_opt cm S, and scs_rc_opt cm T ≤ 2 · scs_rc_opt cm S.

    Applying hypothesis hT to T and the MGREEDY-RC run h1 shows that T is reverse-complement substring-free. Specializing the assumed bounds to T and the execution runs h1 and h2 gives three inequalities: hcomp yields 2|t| ≤ ∑_{u ∈ T} |u| + scs_rc_opt cm T (labeled a), hsum yields ∑_{u ∈ T} |u| ≤ 3 · scs_rc_opt cm S (labeled b), and hopt yields scs_rc_opt cm T ≤ 2 · scs_rc_opt cm S (labeled c).

    lines 14–16

      have a := hcomp T (hT T h1) h2
      have b := hsum T h1
      have c := hopt T h1
  3. 2|t| ≤ 5 · scs_rc_opt cm S

    Combining the three inequalities by linear integer arithmetic yields 2|t| ≤ ∑_{u ∈ T} |u| + scs_rc_opt cm T ≤ 3 · scs_rc_opt cm S + 2 · scs_rc_opt cm S = 5 · scs_rc_opt cm S, which omega solves directly.

    line 17

      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

theorem tgreedy_rc_two_point_five_approx_of_parts {Γ : Type*} [DecidableEq Γ] (cm : Γ → Γ)    (S : Finset (List Γ)) (t : List Γ) (ht : tgreedy_rc_output cm S t)    (hT : ∀ T : Finset (List Γ), Relation.ReflTransGen (mgreedy_rc_step cm) (S, ∅) (∅, T) →      rc_substring_free cm T)    (hcomp : ∀ T : Finset (List Γ), rc_substring_free cm T →      Relation.ReflTransGen (greedy_rc_step cm) T {t} →      2 * t.length ≤ (∑ u ∈ T, u.length) + scs_rc_opt cm T)    (hsum : ∀ T : Finset (List Γ), Relation.ReflTransGen (mgreedy_rc_step cm) (S, ∅) (∅, T) →      (∑ u ∈ T, u.length) ≤ 3 * scs_rc_opt cm S)    (hopt : ∀ T : Finset (List Γ), Relation.ReflTransGen (mgreedy_rc_step cm) (S, ∅) (∅, T) →      scs_rc_opt cm T ≤ 2 * scs_rc_opt cm S) :    2 * t.length ≤ 5 * scs_rc_opt cm S := by  obtain ⟨T, h1, h2⟩ := ht  have a := hcomp T (hT T h1) h2  have b := hsum T h1  have c := hopt T h1  omega
See it in the graphDiscuss this resultChallenge it