AFTD Auto-Formalizing Theoretical Domains

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

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