pm_main
theoremverified
Main adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary forces at least pot further queries.
Statement
theorem pm_main {n : ℕ} (T : PMTree n) : ∀ S : PMState n, S.Inv →
(∀ P : PMPoset n, P.Width2 → PMSat P S.facts → T.run P = P.minSet) →
∃ P : PMPoset n, P.Width2 ∧ PMSat P S.facts ∧ S.pot ≤ (T.cost P : ℤ)- 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 17
- 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.
- PMPoset.ansThe comparison oracle: the answer to query (a, b) on the poset P.
- PMPoset.minSetThe set of minimal elements of P (the output of the 1-selection problem).
- PMTreeA deterministic adaptive comparison algorithm, as a decision tree: a leaf outputs a set, an internal node queries the pair (a, b) and…
- PMTree.runThe output of the algorithm T on the poset P.
- PMTree.costThe number of queries the algorithm T makes on the poset P.
- 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.
- pm_fam_width2Two-chain posets with injective rank have width at most 2.
- 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.InvThe adversary invariant.
- PMState.potThe potential: (number of components − 1) + (number of alive elements − 2).
- PMState.stepThe adversary's move on query (a, b): the answer, and the new state.
- pm_step_factsThe adversary only appends the query and its answer to the list of facts.
- pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.
- pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…
- 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.
/-- Main adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary forces at least `pot` further queries. -/theorem pm_main {n : ℕ} (T : PMTree n) : ∀ S : PMState n, S.Inv → (∀ P : PMPoset n, P.Width2 → PMSat P S.facts → T.run P = P.minSet) → ∃ P : PMPoset n, P.Width2 ∧ PMSat P S.facts ∧ S.pot ≤ (T.cost P : ℤ) := by induction T with | leaf s => intro S hI hC by_cases hp : S.pot ≤ 0 · refine ⟨pmFam S.col S.rk, pm_fam_width2 _ _ hI.2.2.2.2.2.1, hI.2.1, ?_⟩ simp only [PMTree.cost, Nat.cast_zero]; exact hp · obtain ⟨P₁, P₂, hw1, hw2, hs1, hs2, hne⟩ := pm_leaf S hI (by linarith) have e1 := hC P₁ hw1 hs1 have e2 := hC P₂ hw2 hs2 simp only [PMTree.run] at e1 e2 exact absurd (e1.symm.trans e2) hne | node a b k ih => intro S hI hC obtain ⟨hI', hpot⟩ := pm_step_inv S a b hI have hF : (S.step a b).2.facts = (a, b, (S.step a b).1) :: S.facts := pm_step_facts S a b have hans : ∀ P : PMPoset n, PMSat P (S.step a b).2.facts → P.ans a b = (S.step a b).1 := by intro P hP have := hP _ (by rw [hF]; exact List.mem_cons.2 (Or.inl rfl)) simpa using this have hold : ∀ P : PMPoset n, PMSat P (S.step a b).2.facts → PMSat P S.facts := by intro P hP f hf exact hP f (by rw [hF]; exact List.mem_cons.2 (Or.inr hf)) have hC' : ∀ P : PMPoset n, P.Width2 → PMSat P (S.step a b).2.facts → (k (S.step a b).1).run P = P.minSet := by intro P hP hS have := hC P hP (hold P hS) simp only [PMTree.run, hans P hS] at this exact this obtain ⟨P, hP, hS, hcost⟩ := ih (S.step a b).1 (S.step a b).2 hI' hC' refine ⟨P, hP, hold P hS, ?_⟩ simp only [PMTree.cost, hans P hS] push_cast linarith