AFTD Auto-Formalizing Theoretical Domains

scs_rc_opt_singleton_le

theoremverified

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`.

  1. $\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`).

    line 3

    uses Nat.sInf_le

      Nat.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

theorem scs_rc_opt_singleton_le {Γ : Type*} (cm : Γ → Γ) (s : List Γ) :    scs_rc_opt cm {s} ≤ s.length :=  Nat.sInf_le ⟨s, rfl, by simp⟩
See it in the graphDiscuss this resultChallenge it