AFTD Auto-Formalizing Theoretical Domains

pm_inv_diffcol

theoremverified

Adversary case: same component, different colours (answer ∥, forced).

Statement

theorem pm_inv_diffcol {n : ℕ} (S : PMState n) (hI : S.Inv) (a b : Fin n)
    (hcomp : S.comp a = S.comp b) (hcol : S.col a ≠ S.col b) :
    ({ S with facts := (a, b, PMAns.inc) :: S.facts } : PMState n).Inv ∧
    S.pot ≤ ({ S with facts := (a, b, PMAns.inc) :: 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
  • PMAnsThe three possible answers of a comparison query (a, b) on a poset: a ≺ b, b ≺ a, or a ∥ b (incomparable). Setting of arXiv 0707.1532…
  • pm_ans_famExplicit form of the oracle on a two-chain poset.
  • 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

/-- Adversary case: same component, different colours (answer `∥`, forced). -/theorem pm_inv_diffcol {n : ℕ} (S : PMState n) (hI : S.Inv) (a b : Fin n)    (hcomp : S.comp a = S.comp b) (hcol : S.col a ≠ S.col b) :    ({ S with facts := (a, b, PMAns.inc) :: S.facts } : PMState n).Inv ∧    S.pot ≤ ({ S with facts := (a, b, PMAns.inc) :: 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    · have hcol' : ¬ S.col b = S.col a := fun e => hcol e.symm      simp [pm_ans_fam, hcol, hcol']    · exact h2 f hf  · intro f hf    rcases List.mem_cons.1 hf with rfl | hf    · intro _ _ _; exact hcol    · exact h3 f hf  · simp [PMState.pot]
See it in the graphDiscuss this resultChallenge it