PMState.Inv
def
The adversary invariant.
Statement
def PMState.Inv {n : ℕ} (S : PMState n) : Prop
- 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 3
- 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…
- PMSatA list of query/answer facts is satisfied by P.
- 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 10
- 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_invThe initial adversary state (all elements alive, every element its own component) satisfies the adversary invariant.
- 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
/-- The adversary invariant. -/ def PMState.Inv {n : ℕ} (S : PMState n) : Prop := (∀ f ∈ S.facts, S.comp f.1 = S.comp f.2.1) ∧ PMSat (pmFam S.col S.rk) S.facts ∧ (∀ f ∈ S.facts, f.1 ∈ S.alive → f.2.1 ∈ S.alive → f.1 ≠ f.2.1 → S.col f.1 ≠ S.col f.2.1) ∧ (∀ x ∈ S.alive, S.rk x = (x.val : ℤ)) ∧ (∀ x, x ∉ S.alive → (n : ℤ) + S.alive.card ≤ S.rk x) ∧ Function.Injective S.rk ∧ (∀ x, ∃ a ∈ S.alive, S.comp a = S.comp x)