AFTD Auto-Formalizing Theoretical Domains

PMState.pot

def

The potential: (number of components − 1) + (number of alive elements − 2).

Statement

open Finset in
def PMState.pot {n : ℕ} (S : 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
  • 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 9
  • pm_init_potThe potential of the initial adversary state is 2n - 3.
  • 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…
  • 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.
  • 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).
  • 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).
  • pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.

Lean source view module on GitHub

open Finset in
/-- The potential: (number of components − 1) + (number of alive elements − 2). -/
def PMState.pot {n : ℕ} (S : PMState n) : ℤ :=
  ((Finset.univ.image S.comp).card : ℤ) - 1 + (S.alive.card : ℤ) - 2
See it in the graphDiscuss this resultChallenge it