PMState.step
def
The adversary's move on query (a, b): the answer, and the new state.
Statement
def PMState.step {n : ℕ} (S : PMState n) (a b : Fin n) : PMAns × PMState n- 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
- none listed
- Built on 4
- 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…
- 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…
- Used by 3
- pm_step_factsThe adversary only appends the query and its answer to the list of facts.
- pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
- pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.
Lean source view module on GitHub
/-- The adversary's move on query `(a, b)`: the answer, and the new state. -/ def PMState.step {n : ℕ} (S : PMState n) (a b : Fin n) : PMAns × PMState n := if a = b then (PMAns.inc, { S with facts := (a, b, PMAns.inc) :: S.facts }) else if S.comp a ≠ S.comp b then (PMAns.inc, { S with col := fun x => if S.comp x = S.comp b then (if S.col a = S.col b then !S.col x else S.col x) else S.col x comp := fun x => if S.comp x = S.comp b then S.comp a else S.comp x facts := (a, b, PMAns.inc) :: S.facts }) else if S.col a ≠ S.col b then (PMAns.inc, { S with facts := (a, b, PMAns.inc) :: S.facts }) else if a ∈ S.alive ∧ b ∈ S.alive then (if a.val < b.val then (PMAns.lt, { S with rk := Function.update S.rk b ((n : ℤ) + S.alive.card - 1) alive := S.alive.erase b facts := (a, b, PMAns.lt) :: S.facts }) else (PMAns.gt, { S with rk := Function.update S.rk a ((n : ℤ) + S.alive.card - 1) alive := S.alive.erase a facts := (a, b, PMAns.gt) :: S.facts })) else ((pmFam S.col S.rk).ans a b, { S with facts := (a, b, (pmFam S.col S.rk).ans a b) :: S.facts })