pm_inv_dead
theoremverified
Adversary case: same component and colour, not both alive (answer read off the current two-chain realisation).
Statement
theorem pm_inv_dead {n : ℕ} (S : PMState n) (hI : S.Inv) (a b : Fin n) (hcomp : S.comp a = S.comp b) (hal : ¬ (a ∈ S.alive ∧ b ∈ S.alive)) : ({ S with facts := (a, b, (pmFam S.col S.rk).ans a b) :: S.facts } : PMState n).Inv ∧ S.pot ≤ ({ S with facts := (a, b, (pmFam S.col S.rk).ans a b) :: S.facts } : PMState n).pot + 1
- Source
- step towards pm_exact_complexity / pm_lower_bound (exact complexity 2n - 3 at width 2, refuting the tightness conjecture of Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- PMPoset.ansThe comparison oracle: the answer to query (a, b) on the poset P.
- pmFamThe poset that is a disjoint union of (at most) two chains: elements of the same colour c are ordered by the rank ρ, elements of different…
- PMStateThe state of the adversary: a colouring (which of the two chains), ranks, a component label, the set of "alive" elements (not yet shown to…
- PMState.InvThe adversary invariant.
- PMState.potThe potential: (number of components − 1) + (number of alive elements − 2).
- Used by 1
- pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.
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.
/-- Adversary case: same component and colour, not both alive (answer read off the current two-chain realisation). -/theorem pm_inv_dead {n : ℕ} (S : PMState n) (hI : S.Inv) (a b : Fin n) (hcomp : S.comp a = S.comp b) (hal : ¬ (a ∈ S.alive ∧ b ∈ S.alive)) : ({ S with facts := (a, b, (pmFam S.col S.rk).ans a b) :: S.facts } : PMState n).Inv ∧ S.pot ≤ ({ S with facts := (a, b, (pmFam S.col S.rk).ans a b) :: S.facts } : PMState n).pot + 1 := by obtain ⟨h1, h2, h3, h4, h5, h6, h7⟩ := hI refine ⟨⟨?_, ?_, ?_, h4, h5, h6, h7⟩, ?_⟩ · intro f hf rcases List.mem_cons.1 hf with rfl | hf · exact hcomp · exact h1 f hf · intro f hf rcases List.mem_cons.1 hf with rfl | hf · rfl · exact h2 f hf · intro f hf rcases List.mem_cons.1 hf with rfl | hf · intro ha hb _; exact absurd ⟨ha, hb⟩ hal · exact h3 f hf · simp [PMState.pot]