AFTD Auto-Formalizing Theoretical Domains

pm_inv_kill

theoremverified

Adversary case: comparison of two alive elements of the same component and colour; the larger one (z) dies and is re-ranked just below all previously dead elements.

Statement

open Finset in
theorem pm_inv_kill {n : ℕ} (S : PMState n) (hI : S.Inv) (z w : Fin n)
    (hz : z ∈ S.alive) (hw : w ∈ S.alive) (hzw : z ≠ w)
    (hcz : S.comp w = S.comp z)
    (f : Fin n × Fin n × PMAns)
    (hfsat : (pmFam S.col (Function.update S.rk z ((n : ℤ) + S.alive.card - 1))).ans
        f.1 f.2.1 = f.2.2)
    (hfcomp : S.comp f.1 = S.comp f.2.1) (hfz : f.1 = z ∨ f.2.1 = z) :
    ({ S with
        rk := Function.update S.rk z ((n : ℤ) + S.alive.card - 1)
        alive := S.alive.erase z
        facts := f :: S.facts } : PMState n).Inv ∧
    S.pot ≤ ({ S with
        rk := Function.update S.rk z ((n : ℤ) + S.alive.card - 1)
        alive := S.alive.erase z
        facts := f :: S.facts } : PMState n).pot + 1
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 7
  • PMAnsThe three possible answers of a comparison query (a, b) on a poset: a ≺ b, b ≺ a, or a ∥ b (incomparable). Setting of arXiv 0707.1532…
  • PMPoset.ansThe comparison oracle: the answer to query (a, b) 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…
  • 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).
  • pm_rerankChanging an alive element's rank to anything below n + #alive does not change any recorded answer (used both for the adversary's "kill"…
Used by 1
  • pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.

Lean source view module on GitHub

open Finset in/-- Adversary case: comparison of two alive elements of the same component and colour; the larger one (`z`) dies and is re-ranked just below all previously dead elements. -/theorem pm_inv_kill {n : ℕ} (S : PMState n) (hI : S.Inv) (z w : Fin n)    (hz : z ∈ S.alive) (hw : w ∈ S.alive) (hzw : z ≠ w)    (hcz : S.comp w = S.comp z)    (f : Fin n × Fin n × PMAns)    (hfsat : (pmFam S.col (Function.update S.rk z ((n : ℤ) + S.alive.card - 1))).ans        f.1 f.2.1 = f.2.2)    (hfcomp : S.comp f.1 = S.comp f.2.1) (hfz : f.1 = z ∨ f.2.1 = z) :    ({ S with        rk := Function.update S.rk z ((n : ℤ) + S.alive.card - 1)        alive := S.alive.erase z        facts := f :: S.facts } : PMState n).Inv ∧    S.pot ≤ ({ S with        rk := Function.update S.rk z ((n : ℤ) + S.alive.card - 1)        alive := S.alive.erase z        facts := f :: S.facts } : PMState n).pot + 1 := by  have hI' := hI  obtain ⟨h1, h2, h3, h4, h5, h6, h7⟩ := hI  set r : ℤ := (n : ℤ) + S.alive.card - 1 with hr  have hcard2 : 2 ≤ S.alive.card := by    have : ({z, w} : Finset (Fin n)) ⊆ S.alive := by      intro x hx      rcases Finset.mem_insert.1 hx with rfl | hx      · exact hz      · rw [Finset.mem_singleton.1 hx]; exact hw    have h := Finset.card_le_card this    rwa [Finset.card_pair hzw] at h  have hcardE : ((S.alive.erase z).card : ℤ) = S.alive.card - 1 := by    rw [Finset.card_erase_of_mem hz]    have : 1 ≤ S.alive.card := by omega    push_cast [Nat.cast_sub this]    ring  refine ⟨⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩, ?_⟩  · intro g hg    rcases List.mem_cons.1 hg with rfl | hg    · exact hfcomp    · exact h1 g hg  · intro g hg    rcases List.mem_cons.1 hg with rfl | hg    · exact hfsat    · show (pmFam S.col (Function.update S.rk z r)).ans g.1 g.2.1 = g.2.2      rw [pm_rerank S hI' S.col (fun _ _ => Iff.rfl) z hz r (by rw [hr]; linarith) g hg]      exact h2 g hg  · intro g hg    rcases List.mem_cons.1 hg with rfl | hg    · intro hx hy _      rcases hfz with e | e      · rw [e] at hx; exact absurd hx (Finset.notMem_erase _ _)      · rw [e] at hy; exact absurd hy (Finset.notMem_erase _ _)    · intro hx hy hxy      exact h3 g hg (Finset.mem_of_mem_erase hx) (Finset.mem_of_mem_erase hy) hxy  · intro x hx    have hxz : x ≠ z := Finset.ne_of_mem_erase hx    show Function.update S.rk z r x = x.val    rw [Function.update_of_ne hxz]    exact h4 x (Finset.mem_of_mem_erase hx)  · intro x hx    show (n : ℤ) + (S.alive.erase z).card ≤ Function.update S.rk z r x    rw [hcardE]    by_cases hxz : x = z    · subst hxz; rw [Function.update_self, hr]; linarith    · rw [Function.update_of_ne hxz]      have hxa : x ∉ S.alive := fun h => hx (Finset.mem_erase.2 ⟨hxz, h⟩)      have := h5 x hxa      linarith  · have hfresh : ∀ y, y ≠ z → S.rk y ≠ r := by      intro y hy e      by_cases hya : y ∈ S.alive      · rw [h4 y hya] at e        have : (y.val : ℤ) < n := by exact_mod_cast y.isLt        have : (2 : ℤ) ≤ S.alive.card := by exact_mod_cast hcard2        rw [hr] at e; linarith      · have := h5 y hya        rw [hr] at e; linarith    intro x y hxy    show x = y    by_cases hx : x = z    · by_cases hy : y = z      · rw [hx, hy]      · subst hx        simp only [Function.update_self, Function.update_of_ne hy] at hxy        exact absurd hxy.symm (hfresh y hy)    · by_cases hy : y = z      · subst hy        simp only [Function.update_self, Function.update_of_ne hx] at hxy        exact absurd hxy (hfresh x hx)      · simp only [Function.update_of_ne hx, Function.update_of_ne hy] at hxy        exact h6 hxy  · intro x    obtain ⟨a', ha', hax⟩ := h7 x    by_cases haz : a' = z    · refine ⟨w, Finset.mem_erase.2 ⟨fun e => hzw e.symm, hw⟩, ?_⟩      show S.comp w = S.comp x      rw [hcz, ← haz, hax]    · exact ⟨a', Finset.mem_erase.2 ⟨haz, ha'⟩, hax⟩  · simp only [PMState.pot]    rw [hcardE]    linarith
See it in the graphDiscuss this resultChallenge it