pm_conjecture_false
The conjecture of arXiv 0707.1532 (Section 4) that the deterministic lower bound (w+1)n/2 − w for finding the minimal elements is tight fails already for w = 2: there is no constant C such that for every n some correct deterministic algorithm uses at most (w+1)n/2 − w + C = 3n/2 − 2 + C queries on every width-2 poset.
Statement
theorem pm_conjecture_false :
¬ ∃ C : ℕ, ∀ n : ℕ, ∃ T : PMTree n, T.Correct2 ∧
∀ P : PMPoset n, P.Width2 → 2 * (T.cost P : ℤ) ≤ 3 * (n : ℤ) - 4 + 2 * C- 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
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
Read back from the Lean
The theorem asserts the negation of the claim that there exists a natural number C such that for every natural number n, there exists a tree T : PMTree n satisfying T.Correct2 such that for every poset P : PMPoset n satisfying P.Width2, 2 * (T.cost P : ℤ) ≤ 3 * (n : ℤ) - 4 + 2 * C.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
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.
/-- **The conjecture of arXiv 0707.1532 (Section 4) that the deterministic lower bound `(w+1)n/2 − w` for finding the minimal elements is tight fails already for `w = 2`:** there is no constant `C` such that for every `n` some correct deterministic algorithm uses at most `(w+1)n/2 − w + C = 3n/2 − 2 + C` queries on every width-2 poset. -/theorem pm_conjecture_false : ¬ ∃ C : ℕ, ∀ n : ℕ, ∃ T : PMTree n, T.Correct2 ∧ ∀ P : PMPoset n, P.Width2 → 2 * (T.cost P : ℤ) ≤ 3 * (n : ℤ) - 4 + 2 * C := by rintro ⟨C, hC⟩ obtain ⟨T, hT, hle⟩ := hC (2 * C + 3) obtain ⟨P, hP, hlow⟩ := pm_lower_bound T hT have := hle P hP push_cast at hlow this linarith