AFTD Auto-Formalizing Theoretical Domains

PMState

structure

The state of the adversary: a colouring (which of the two chains), ranks, a component label, the set of "alive" elements (not yet shown to have anything below them), and the list of answered queries.

Statement

structure 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 1
  • 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…
Used by 15
  • pm_rerankChanging an alive element's rank to anything below n + #alive does not change any recorded answer (used both for the adversary's "kill"…
  • pm_init_potThe potential of the initial adversary state is 2n - 3.
  • pm_step_factsThe adversary only appends the query and its answer to the list of facts.
  • 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…
  • PMState.InvThe adversary invariant.
  • pm_inv_mergeAdversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components…
  • pm_inv_sameAdversary case a = b: invariant kept, potential unchanged.
  • PMState.stepThe adversary's move on query (a, b): the answer, and the new state.
  • 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_inv_deadAdversary case: same component and colour, not both alive (answer read off the current two-chain realisation).
  • pmInitThe adversary's initial state: every element is its own component and alive.
  • pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…
  • pm_inv_diffcolAdversary case: same component, different colours (answer ∥, forced).
  • PMState.potThe potential: (number of components − 1) + (number of alive elements − 2).
  • pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.

Lean source view module on GitHub

/-- The state of the adversary: a colouring (which of the two chains), ranks, a component label, the set of "alive" elements (not yet shown to have anything below them), and the list of answered queries. -/
structure PMState (n : ℕ) where
  col : Fin n → Bool
  rk : Fin n → ℤ
  comp : Fin n → Fin n
  alive : Finset (Fin n)
  facts : List (Fin n × Fin n × PMAns)
See it in the graphDiscuss this resultChallenge it