scs_rc_opt_singleton_le
The SCS-RC optimum of a single string is at most its length.
Statement
theorem scs_rc_opt_singleton_le {Γ : Type*} (cm : Γ → Γ) (s : List Γ) : scs_rc_opt cm {s} ≤ s.length
- Source
- Sanity check of scs_rc_opt (arXiv:2611.16573)
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- rev_compThe reverse complement rc(s) of a string s = a_1…a_m under a complement map cm is cm(a_m)…cm(a_1).
The proof, explained
To show that the shortest common superstring with reverse complements for a singleton $\{s\}$ has length at most $|s|$, the proof exhibits $s$ itself as a valid superstring. Since $s$ contains itself as an infix and has length $|s|$, its length belongs to the set defining the optimum, so the infimum is at most $|s|$ by `Nat.sInf_le`.
$\operatorname{scs\_rc\_opt}(cm, \{s\}) \le |s|$
The optimum $\operatorname{scs\_rc\_opt}(cm, \{s\})$ is defined as the infimum of the lengths of strings containing either $t$ or its reverse complement as an infix for all $t \in \{s\}$. By `Nat.sInf_le`, it suffices to exhibit a valid candidate string of length $|s|$. Choosing $u = s$, its length is $|s|$ by definition (`rfl`), and every element in the singleton $\{s\}$ is $s$ itself, which is an infix of $s$ by reflexivity (verified by `simp`).
uses
Nat.sInf_leNat.sInf_le ⟨s, rfl, by simp⟩
Nat.sInf_le- If a natural number $m$ belongs to a set $s \subseteq \mathbb{N}$, then $\inf s \le m$.
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 scs_rc_opt_singleton_le {Γ : Type*} (cm : Γ → Γ) (s : List Γ) : scs_rc_opt cm {s} ≤ s.length := Nat.sInf_le ⟨s, rfl, by simp⟩