pm_leaf
theoremverified
At a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can be correct for both).
Statement
open Finset in theorem pm_leaf {n : ℕ} (S : PMState n) (hI : S.Inv) (hpos : 0 < S.pot) : ∃ P₁ P₂ : PMPoset n, P₁.Width2 ∧ P₂.Width2 ∧ PMSat P₁ S.facts ∧ PMSat P₂ S.facts ∧ P₁.minSet ≠ P₂.minSet
- 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 11
- PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
- PMPoset.minSetThe set of minimal elements of P (the output of the 1-selection problem).
- 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).
- 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"…
- pm_recolorRecolouring that preserves colour-equality on every fact preserves all answers.
- PMPoset.Width2The poset has width at most 2: among any three distinct elements some two are comparable.
- Used by 1
- pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
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/-- At a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can be correct for both). -/theorem pm_leaf {n : ℕ} (S : PMState n) (hI : S.Inv) (hpos : 0 < S.pot) : ∃ P₁ P₂ : PMPoset n, P₁.Width2 ∧ P₂.Width2 ∧ PMSat P₁ S.facts ∧ PMSat P₂ S.facts ∧ P₁.minSet ≠ P₂.minSet := by have hI' := hI obtain ⟨h1, h2, h3, h4, h5, h6, h7⟩ := hI -- a "bad pair" of alive elements that can be put in the same chain have hbad : ∃ a ∈ S.alive, ∃ b ∈ S.alive, a ≠ b ∧ (S.comp a = S.comp b → S.col a = S.col b) := by by_contra hno push Not at hno have hA : S.alive.card ≤ 2 := by by_contra hc obtain ⟨x, hx, y, hy, z, hz, hxy, hxz, hyz⟩ := Finset.two_lt_card.1 (by omega : 2 < S.alive.card) have e1 := (hno x hx y hy hxy).2 have e2 := (hno x hx z hz hxz).2 have e3 := (hno y hy z hz hyz).2 cases hcx : S.col x <;> cases hcy : S.col y <;> cases hcz : S.col z <;> simp_all have hC : (Finset.univ.image S.comp).card ≤ 1 := by apply Finset.card_le_one.2 intro u hu v hv obtain ⟨x, _, rfl⟩ := Finset.mem_image.1 hu obtain ⟨y, _, rfl⟩ := Finset.mem_image.1 hv obtain ⟨a, ha, hax⟩ := h7 x obtain ⟨b, hb, hby⟩ := h7 y rw [← hax, ← hby] by_cases hab : a = b · rw [hab] · exact (hno a ha b hb hab).1 simp only [PMState.pot] at hpos have : ((Finset.univ.image S.comp).card : ℤ) ≤ 1 := by exact_mod_cast hC have : (S.alive.card : ℤ) ≤ 2 := by exact_mod_cast hA linarith obtain ⟨a, ha, b, hb, hab, hcab⟩ := hbad 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' have hceq : ∀ f ∈ S.facts, (c' f.1 = c' f.2.1 ↔ S.col f.1 = S.col f.2.1) := by intro f hf have hxy := h1 f hf simp only [hc', hxy] split_ifs <;> simp have hca : c' a = S.col a := by simp only [hc'] by_cases h : S.comp a = S.comp b · rw [if_pos h, if_pos (hcab h)] · rw [if_neg h] have hcb : c' b = S.col a := by simp only [hc'] cases hx : S.col a <;> cases hy : S.col b <;> simp have hsame : c' a = c' b := by rw [hca, hcb] have hnn : ∀ x, (0 : ℤ) ≤ S.rk x := by intro x by_cases hx : x ∈ S.alive · rw [h4 x hx]; exact Int.natCast_nonneg _ · have := h5 x hx have : (0 : ℤ) ≤ (n : ℤ) := Int.natCast_nonneg _ have : (0 : ℤ) ≤ (S.alive.card : ℤ) := Int.natCast_nonneg _ linarith have hneg : (-1 : ℤ) < (n : ℤ) + S.alive.card := by have : (0 : ℤ) ≤ (n : ℤ) := Int.natCast_nonneg _ have : (0 : ℤ) ≤ (S.alive.card : ℤ) := Int.natCast_nonneg _ linarith have hinj : ∀ z, Function.Injective (Function.update S.rk z (-1)) := by intro z x y hxy 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 have := hnn y; linarith · by_cases hy : y = z · subst hy simp only [Function.update_self, Function.update_of_ne hx] at hxy have := hnn x; linarith · simp only [Function.update_of_ne hx, Function.update_of_ne hy] at hxy exact h6 hxy have hsat : ∀ z ∈ S.alive, PMSat (pmFam c' (Function.update S.rk z (-1))) S.facts := by intro z hz f hf rw [pm_rerank S hI' c' hceq z hz (-1) hneg f hf, pm_recolor S.facts S.col c' S.rk (fun g hg => hceq g hg) f hf] exact h2 f hf refine ⟨pmFam c' (Function.update S.rk a (-1)), pmFam c' (Function.update S.rk b (-1)), pm_fam_width2 _ _ (hinj a), pm_fam_width2 _ _ (hinj b), hsat a ha, hsat b hb, ?_⟩ intro heq have hb1 : b ∉ (pmFam c' (Function.update S.rk a (-1))).minSet := by simp only [PMPoset.minSet, Finset.mem_filter, Finset.mem_univ, true_and, not_forall] refine ⟨a, ?_⟩ simp only [pmFam, Function.update_self, Function.update_of_ne (fun e => hab e.symm)] have := hnn b simp only [hsame, true_and, Bool.not_eq_false, decide_eq_true_eq] linarith have hb2 : b ∈ (pmFam c' (Function.update S.rk b (-1))).minSet := by simp only [PMPoset.minSet, Finset.mem_filter, Finset.mem_univ, true_and] intro y simp only [pmFam, Function.update_self, decide_eq_false_iff_not, not_and, not_lt] intro _ by_cases hy : y = b · rw [hy, Function.update_self] · rw [Function.update_of_ne hy]; have := hnn y; linarith rw [heq] at hb1 exact hb1 hb2