AFTD Auto-Formalizing Theoretical Domains

pm_conjecture_false

theoremverifiedoriginal

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

/-- **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
See it in the graphDiscuss this resultChallenge it