AFTD Auto-Formalizing Theoretical Domains

pm_step_inv

theoremverified

Every adversary move keeps the invariant and lowers the potential by at most one.

Statement

open Finset in
theorem pm_step_inv {n : ℕ} (S : PMState n) (a b : Fin n) (hI : S.Inv) :
    (S.step a b).2.Inv ∧ S.pot ≤ (S.step a b).2.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 13
  • 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…
  • 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…
  • 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).
  • PMState.stepThe adversary's move on query (a, b): the answer, and the new state.
  • pm_inv_sameAdversary case a = b: invariant kept, potential unchanged.
  • pm_inv_diffcolAdversary case: same component, different colours (answer ∥, forced).
  • pm_inv_deadAdversary case: same component and colour, not both alive (answer read off the current two-chain realisation).
  • pm_inv_mergeAdversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components…
  • pm_inv_killAdversary case: comparison of two alive elements of the same component and colour; the larger one (z) dies and is re-ranked just below all…
Used by 1
  • pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…

Lean source view module on GitHub

open Finset in/-- Every adversary move keeps the invariant and lowers the potential by at most one. -/theorem pm_step_inv {n : ℕ} (S : PMState n) (a b : Fin n) (hI : S.Inv) :    (S.step a b).2.Inv ∧ S.pot ≤ (S.step a b).2.pot + 1 := by  unfold PMState.step  by_cases hab : a = b  · subst hab; rw [if_pos rfl]; exact pm_inv_same S hI a  rw [if_neg hab]  by_cases hcomp : S.comp a ≠ S.comp b  · rw [if_pos hcomp]; exact pm_inv_merge S hI a b hcomp  rw [if_neg hcomp]  have hcomp' : S.comp a = S.comp b := not_not.1 hcomp  by_cases hcol : S.col a ≠ S.col b  · rw [if_pos hcol]; exact pm_inv_diffcol S hI a b hcomp' hcol  rw [if_neg hcol]  have hcol' : S.col a = S.col b := not_not.1 hcol  by_cases hal : a ∈ S.alive ∧ b ∈ S.alive  · rw [if_pos hal]    have h4 := hI.2.2.2.1    have hcard : (1 : ℤ) ≤ S.alive.card := by      have : 0 < S.alive.card := Finset.card_pos.2 ⟨a, hal.1⟩      exact_mod_cast this    by_cases hv : a.val < b.val    · rw [if_pos hv]      apply pm_inv_kill S hI b a hal.2 hal.1 (fun e => hab e.symm) hcomp'      · show (pmFam S.col (Function.update S.rk b ((n : ℤ) + S.alive.card - 1))).ans a b          = PMAns.lt        rw [pm_ans_fam, Function.update_of_ne hab, Function.update_self, h4 a hal.1]        have : (a.val : ℤ) < n := by exact_mod_cast a.isLt        rw [if_pos ⟨hcol', by linarith⟩]      · exact hcomp'      · exact Or.inr rfl    · rw [if_neg hv]      have hv' : b.val < a.val := by        rcases Nat.lt_or_ge b.val a.val with h | h        · exact h        · exact absurd (Fin.ext (le_antisymm (not_lt.1 hv) h)).symm hab      apply pm_inv_kill S hI a b hal.1 hal.2 hab hcomp'.symm      · show (pmFam S.col (Function.update S.rk a ((n : ℤ) + S.alive.card - 1))).ans a b          = PMAns.gt        rw [pm_ans_fam, Function.update_of_ne (fun e => hab e.symm), Function.update_self,          h4 b hal.2]        have : (b.val : ℤ) < n := by exact_mod_cast b.isLt        rw [if_neg (fun h => by linarith [h.2]), if_pos ⟨hcol'.symm, by linarith⟩]      · exact hcomp'      · exact Or.inl rfl  · rw [if_neg hal]; exact pm_inv_dead S hI a b hcomp' hal
See it in the graphDiscuss this resultChallenge it