AFTD Auto-Formalizing Theoretical Domains

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

/-- 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']
See it in the graphDiscuss this resultChallenge it