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