AFTD Auto-Formalizing Theoretical Domains

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 })
See it in the graphDiscuss this resultChallenge it