tgreedy_rc_two_point_five_approx_of_parts
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.
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).
obtain ⟨T, h1, h2⟩ := htThe 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).
have a := hcomp T (hT T h1) h2 have b := hsum T h1 have c := hopt T h1
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.
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
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.
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