pm_init_pot
theoremverified
The potential of the initial adversary state is 2n - 3.
Statement
open Finset in theorem pm_init_pot (n : ℕ) : (pmInit n).pot = 2 * (n : ℤ) - 3
- 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
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- PMState.potThe potential: (number of components − 1) + (number of alive elements − 2).
- pmInitThe adversary's initial state: every element is its own component and alive.
- Used by 1
- pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finset intheorem pm_init_pot (n : ℕ) : (pmInit n).pot = 2 * (n : ℤ) - 3 := by simp only [PMState.pot, pmInit, Finset.image_id, Finset.card_univ, Fintype.card_fin] ring