pm_inv_merge
theoremverified
Adversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components drops by at most one.
Statement
open Finset in theorem pm_inv_merge {n : ℕ} (S : PMState n) (hI : S.Inv) (a b : Fin n) (hcomp : S.comp a ≠ S.comp b) : ({ S with col := fun x => if S.comp x = S.comp b then (if S.col a = S.col b then !S.col x else S.col x) else S.col x comp := fun x => if S.comp x = S.comp b then S.comp a else S.comp x facts := (a, b, PMAns.inc) :: S.facts } : PMState n).Inv ∧ S.pot ≤ ({ S with col := fun x => if S.comp x = S.comp b then (if S.col a = S.col b then !S.col x else S.col x) else S.col x comp := fun x => if S.comp x = S.comp b then S.comp a else S.comp x facts := (a, b, PMAns.inc) :: 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 8
- 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…
- pm_ans_famExplicit form of the oracle on a two-chain poset.
- 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_recolorRecolouring that preserves colour-equality on every fact preserves all answers.
- 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
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.
open Finset in/-- Adversary case: two different components are merged (answer `∥`); the second component is recoloured if necessary. The number of components drops by at most one. -/theorem pm_inv_merge {n : ℕ} (S : PMState n) (hI : S.Inv) (a b : Fin n) (hcomp : S.comp a ≠ S.comp b) : ({ S with col := fun x => if S.comp x = S.comp b then (if S.col a = S.col b then !S.col x else S.col x) else S.col x comp := fun x => if S.comp x = S.comp b then S.comp a else S.comp x facts := (a, b, PMAns.inc) :: S.facts } : PMState n).Inv ∧ S.pot ≤ ({ S with col := fun x => if S.comp x = S.comp b then (if S.col a = S.col b then !S.col x else S.col x) else S.col x comp := fun x => if S.comp x = S.comp b then S.comp a else S.comp x facts := (a, b, PMAns.inc) :: S.facts } : PMState n).pot + 1 := by obtain ⟨h1, h2, h3, h4, h5, h6, h7⟩ := hI set c' : Fin n → Bool := fun x => if S.comp x = S.comp b then (if S.col a = S.col b then !S.col x else S.col x) else S.col x with hc' set k' : Fin n → Fin n := fun x => if S.comp x = S.comp b then S.comp a else S.comp x with hk' -- colour equality is preserved inside a component have hceq : ∀ x y : Fin n, S.comp x = S.comp y → (c' x = c' y ↔ S.col x = S.col y) := by intro x y hxy simp only [hc', hxy] split_ifs <;> simp have hca : c' a = S.col a := by simp [hc', hcomp] have hcb : c' b ≠ S.col a := by simp only [hc'] cases h : S.col a <;> cases h' : S.col b <;> simp [h, h'] refine ⟨⟨?_, ?_, ?_, h4, h5, h6, ?_⟩, ?_⟩ · intro f hf rcases List.mem_cons.1 hf with rfl | hf · simp [hk', hcomp] · have := h1 f hf simp only [hk', this] · intro f hf rcases List.mem_cons.1 hf with rfl | hf · show (pmFam c' S.rk).ans a b = PMAns.inc have hne : ¬ c' a = c' b := by rw [hca]; exact fun e => hcb e.symm have hne' : ¬ c' b = c' a := fun e => hne e.symm simp [pm_ans_fam, hne, hne'] · show (pmFam c' S.rk).ans f.1 f.2.1 = f.2.2 rw [pm_recolor S.facts S.col c' S.rk (fun g hg => hceq _ _ (h1 g hg)) f hf] exact h2 f hf · intro f hf rcases List.mem_cons.1 hf with rfl | hf · intro _ _ _ show c' a ≠ c' b rw [hca]; exact fun e => hcb e.symm · intro hx hy hxy show c' f.1 ≠ c' f.2.1 rw [Ne, hceq _ _ (h1 f hf)] exact h3 f hf hx hy hxy · intro x obtain ⟨a', ha', hax⟩ := h7 x exact ⟨a', ha', by simp only [hk', hax]⟩ · simp only [PMState.pot] have hsub : Finset.univ.image S.comp ⊆ insert (S.comp b) (Finset.univ.image k') := by intro t ht obtain ⟨x, _, rfl⟩ := Finset.mem_image.1 ht by_cases hx : S.comp x = S.comp b · rw [hx]; exact Finset.mem_insert_self _ _ · apply Finset.mem_insert_of_mem exact Finset.mem_image.2 ⟨x, Finset.mem_univ _, by simp [hk', hx]⟩ have := (Finset.card_le_card hsub).trans (Finset.card_insert_le _ _) have : ((Finset.univ.image S.comp).card : ℤ) ≤ (Finset.univ.image k').card + 1 := by exact_mod_cast this linarith