pm_rerank
theoremverified
Changing an alive element's rank to anything below n + #alive does not change any recorded answer (used both for the adversary's "kill" step and for the final fooling pair).
Statement
theorem pm_rerank {n : ℕ} (S : PMState n) (hI : S.Inv) (c : Fin n → Bool)
(hc : ∀ f ∈ S.facts, (c f.1 = c f.2.1 ↔ S.col f.1 = S.col f.2.1))
(z : Fin n) (hz : z ∈ S.alive) (r : ℤ) (hr : r < (n : ℤ) + S.alive.card) :
∀ f ∈ S.facts, (pmFam c (Function.update S.rk z r)).ans f.1 f.2.1 =
(pmFam c S.rk).ans f.1 f.2.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 5
- 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.
- Used by 2
- pm_inv_killAdversary case: comparison of two alive elements of the same component and colour; the larger one (z) dies and is re-ranked just below all…
- pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…
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.
/-- Changing an alive element's rank to anything below `n + #alive` does not change any recorded answer (used both for the adversary's "kill" step and for the final fooling pair). -/theorem pm_rerank {n : ℕ} (S : PMState n) (hI : S.Inv) (c : Fin n → Bool) (hc : ∀ f ∈ S.facts, (c f.1 = c f.2.1 ↔ S.col f.1 = S.col f.2.1)) (z : Fin n) (hz : z ∈ S.alive) (r : ℤ) (hr : r < (n : ℤ) + S.alive.card) : ∀ f ∈ S.facts, (pmFam c (Function.update S.rk z r)).ans f.1 f.2.1 = (pmFam c S.rk).ans f.1 f.2.1 := by obtain ⟨_, _, hI3, hI4, hI5, _, _⟩ := hI intro f hf obtain ⟨x, y, t⟩ := f simp only at hf ⊢ have hzr : S.rk z < (n : ℤ) + S.alive.card := by rw [hI4 z hz] have : (z.val : ℤ) < n := by exact_mod_cast z.isLt have : (0 : ℤ) ≤ S.alive.card := by positivity linarith rw [pm_ans_fam, pm_ans_fam] by_cases hcol : c x = c y · by_cases hxy : x = y · subst hxy; simp have hold : S.col x = S.col y := (hc _ hf).1 hcol by_cases hx : x = z · subst hx have hy : y ∉ S.alive := fun hy => hI3 _ hf hz hy hxy hold have := hI5 y hy have hyz : y ≠ x := fun e => hxy e.symm simp [hyz, hcol] rw [if_pos (by linarith), if_pos (by linarith)] · by_cases hy : y = z · subst hy have hxa : x ∉ S.alive := fun hxa => hI3 _ hf hxa hz hxy hold have := hI5 x hxa simp [hx, hcol] rw [if_neg (by linarith), if_pos (by linarith), if_neg (by linarith), if_pos (by linarith)] · simp [Function.update_apply, hx, hy] · have hcol' : ¬ c y = c x := fun e => hcol e.symm simp [hcol, hcol']