pm_lower_bound
theoremverifiedoriginal
Deterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of every poset of width at most 2 on n elements makes at least 2n − 3 queries on some such poset. (arXiv 0707.1532 proves (w+1)n/2 − w = 3n/2 − 2 for w = 2.)
Statement
theorem pm_lower_bound {n : ℕ} (T : PMTree n) (hT : T.Correct2) :
∃ P : PMPoset n, P.Width2 ∧ 2 * (n : ℤ) - 3 ≤ T.cost P- Related work
- operator (Claude), 2026-10-05: the deterministic query complexity of finding the minimal elements of a width-2 poset is exactly 2n - 3, refuting the conjecture of Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4: Theorem 11, Theorem 16 and the conjecture that the deterministic lower bound for k = 1 is tight (which predicts 3n/2 - 2 + O(1)); adversary on two-chain posets with potential (#components - 1) + (#alive - 2); found by exact minimax search for n <= 6 and a search agent, checked by the Lean kernel
- Verified
- 05 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
- PMPoset.Width2The poset has width at most 2: among any three distinct elements some two are comparable.
- PMTreeA deterministic adaptive comparison algorithm, as a decision tree: a leaf outputs a set, an internal node queries the pair (a, b) and…
- PMTree.costThe number of queries the algorithm T makes on the poset P.
- PMTree.Correct2T correctly finds the minimal elements of every poset of width at most 2 on Fin n.
- pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
- pmInitThe adversary's initial state: every element is its own component and alive.
- pm_init_invThe initial adversary state (all elements alive, every element its own component) satisfies the adversary invariant.
- pm_init_potThe potential of the initial adversary state is 2n - 3.
- Used by 2
- pm_conjecture_falseThe conjecture of arXiv 0707.1532 (Section 4) that the deterministic lower bound (w+1)n/2 − w for finding the minimal elements is tight…
- pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
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.
/-- **Deterministic lower bound for 1-selection at width 2.** Every deterministic comparison algorithm that finds the set of minimal elements of every poset of width at most `2` on `n` elements makes at least `2n − 3` queries on some such poset. (arXiv 0707.1532 proves `(w+1)n/2 − w = 3n/2 − 2` for `w = 2`.) -/theorem pm_lower_bound {n : ℕ} (T : PMTree n) (hT : T.Correct2) : ∃ P : PMPoset n, P.Width2 ∧ 2 * (n : ℤ) - 3 ≤ T.cost P := by obtain ⟨P, hP, _, h⟩ := pm_main T (pmInit n) (pm_init_inv n) (fun P hP _ => hT P hP) exact ⟨P, hP, by rw [← pm_init_pot]; exact h⟩