AFTD Auto-Formalizing Theoretical Domains

pm_alg_run

theoremverifiedformalization

Correctness of the candidate-list algorithm on width-2 posets.

Statement

open Finset in
theorem pm_alg_run {n : ℕ} (P : PMPoset n) (hP : P.Width2) : ∀ (m k : ℕ) (cs : List (Fin n)),
    k + m = n → cs.length ≤ 2 → cs.Nodup → cs.toFinset = pmMinPre P k →
    (pmAlg m k cs).run P = pmMinPre P n
Formalizes
Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4, Theorem 11 (correctness of the candidate-set algorithm); special case width 2
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12
  • 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.
  • 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.
  • pm_ans_ltIf the oracle answers a < b then a < b holds and b < a does not.
  • pm_ans_gtIf the oracle answers b < a then b < a holds and a < b does not.
  • pm_ans_incIf the oracle answers that a and b are incomparable, neither a < b nor b < a holds.
  • pmMinPreMinimal elements of the prefix {0, …, k−1}.
  • pmAlgThe candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal…
  • pm_step_eqOne scanning step of the candidate algorithm maintains the invariant that its candidate list is exactly the set of minimal elements of the…
  • pm_mem_minPreEvery minimal element of the prefix of length k has index below k and no element of index below k lies below it.
Used by 1

Lean source view module on GitHub

open Finset in/-- Correctness of the candidate-list algorithm on width-2 posets. -/theorem pm_alg_run {n : ℕ} (P : PMPoset n) (hP : P.Width2) : ∀ (m k : ℕ) (cs : List (Fin n)),    k + m = n → cs.length ≤ 2 → cs.Nodup → cs.toFinset = pmMinPre P k →    (pmAlg m k cs).run P = pmMinPre P n := by  intro m  induction m with  | zero =>    intro k cs hkm _ _ hcs    simp only [Nat.add_zero] at hkm    subst hkm    simp only [pmAlg, PMTree.run]    exact hcs  | succ m ih =>    intro k cs hkm hlen hnd hcs    have hk : k < n := by omega    set x : Fin n := ⟨k, hk⟩ with hx    rcases cs with _ | ⟨t, _ | ⟨t2, _ | ⟨t3, rest⟩⟩⟩    · simp only [pmAlg, dif_pos hk]      refine ih (k + 1) [x] (by omega) (by simp) (by simp)        (pm_step_eq P k hk [] [x] hcs (fun a => ?_))      simp [hx]    · have ht := pm_mem_minPre P k t (by rw [← hcs]; simp)      have hxt : x ≠ t := fun e => by rw [← e, hx] at ht; simp at ht      simp only [pmAlg, dif_pos hk, PMTree.run]      cases hr : P.ans x t      · obtain ⟨f1, f2⟩ := pm_ans_lt P x t hr        refine ih (k + 1) [x] (by omega) (by simp) (by simp)          (pm_step_eq P k hk [t] [x] hcs (fun a => ?_))        clear ih hcs hP        rw [← hx]        by_cases e1 : a = x <;> by_cases e2 : a = t <;> simp_all      · obtain ⟨f1, f2⟩ := pm_ans_gt P x t hr        refine ih (k + 1) [t] (by omega) (by simp) (by simp)          (pm_step_eq P k hk [t] [t] hcs (fun a => ?_))        clear ih hcs hP        rw [← hx]        by_cases e1 : a = x <;> by_cases e2 : a = t <;> simp_all      · obtain ⟨f1, f2⟩ := pm_ans_inc P x t hr        refine ih (k + 1) [t, x] (by omega) (by simp) (by simp [Ne.symm hxt])          (pm_step_eq P k hk [t] [t, x] hcs (fun a => ?_))        clear ih hcs hP        rw [← hx]        by_cases e1 : a = x <;> by_cases e2 : a = t <;> simp_all    · have ht := pm_mem_minPre P k t (by rw [← hcs]; simp)      have ht2 := pm_mem_minPre P k t2 (by rw [← hcs]; simp)      have hxt : x ≠ t := fun e => by rw [← e, hx] at ht; simp at ht      have hxt2 : x ≠ t2 := fun e => by rw [← e, hx] at ht2; simp at ht2      have h12 : t ≠ t2 := by simpa using hnd      have l12 : P.lt t t2 = false := ht2.2 t ht.1      have l21 : P.lt t2 t = false := ht.2 t2 ht2.1      simp only [pmAlg, dif_pos hk, PMTree.run]      cases hr : P.ans x t      · -- x ≺ t        obtain ⟨f1, f2⟩ := pm_ans_lt P x t hr        simp only [PMTree.run]        cases hr2 : P.ans x t2        · obtain ⟨g1, g2⟩ := pm_ans_lt P x t2 hr2          refine ih (k + 1) [x] (by omega) (by simp) (by simp)            (pm_step_eq P k hk [t, t2] [x] hcs (fun a => ?_))          clear ih hcs hP          rw [← hx]          by_cases e1 : a = x <;> by_cases e2 : a = t <;> by_cases e3 : a = t2 <;> simp_all        · obtain ⟨g1, g2⟩ := pm_ans_gt P x t2 hr2          have := P.trans _ _ _ g2 f1          rw [l21] at this          exact absurd this (by simp)        · obtain ⟨g1, g2⟩ := pm_ans_inc P x t2 hr2          refine ih (k + 1) [t2, x] (by omega) (by simp) (by simp [Ne.symm hxt2])            (pm_step_eq P k hk [t, t2] [t2, x] hcs (fun a => ?_))          clear ih hcs hP          rw [← hx]          by_cases e1 : a = x <;> by_cases e2 : a = t <;> by_cases e3 : a = t2 <;> simp_all      · -- t ≺ x        obtain ⟨f1, f2⟩ := pm_ans_gt P x t hr        have g1 : P.lt x t2 = false := by          cases h : P.lt x t2          · rfl          · have := P.trans _ _ _ f2 h            rw [l12] at this            exact absurd this (by simp)        refine ih (k + 1) [t, t2] (by omega) (by simp) (by simp [h12])          (pm_step_eq P k hk [t, t2] [t, t2] hcs (fun a => ?_))        clear ih hcs hP        rw [← hx]        by_cases e1 : a = x <;> by_cases e2 : a = t <;> by_cases e3 : a = t2 <;> simp_all      · -- x ∥ t        obtain ⟨f1, f2⟩ := pm_ans_inc P x t hr        simp only [PMTree.run]        cases hr2 : P.ans x t2        · obtain ⟨g1, g2⟩ := pm_ans_lt P x t2 hr2          refine ih (k + 1) [t, x] (by omega) (by simp) (by simp [Ne.symm hxt])            (pm_step_eq P k hk [t, t2] [t, x] hcs (fun a => ?_))          clear ih hcs hP          rw [← hx]          by_cases e1 : a = x <;> by_cases e2 : a = t <;> by_cases e3 : a = t2 <;> simp_all        · obtain ⟨g1, g2⟩ := pm_ans_gt P x t2 hr2          refine ih (k + 1) [t, t2] (by omega) (by simp) (by simp [h12])            (pm_step_eq P k hk [t, t2] [t, t2] hcs (fun a => ?_))          clear ih hcs hP          rw [← hx]          by_cases e1 : a = x <;> by_cases e2 : a = t <;> by_cases e3 : a = t2 <;> simp_all        · obtain ⟨g1, g2⟩ := pm_ans_inc P x t2 hr2          exfalso          rcases hP x t t2 hxt h12 hxt2 with h | h | h | h | h | h <;> simp_all    · simp at hlen
See it in the graphDiscuss this resultChallenge it