pm_recolor
theoremverified
Recolouring that preserves colour-equality on every fact preserves all answers.
Statement
theorem pm_recolor {n : ℕ} (F : List (Fin n × Fin n × PMAns)) (c c' : Fin n → Bool)
(ρ : Fin n → ℤ) (hc : ∀ f ∈ F, (c' f.1 = c' f.2.1 ↔ c f.1 = c f.2.1)) :
∀ f ∈ F, (pmFam c' ρ).ans f.1 f.2.1 = (pmFam c ρ).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 4
- 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.
- Used by 2
- pm_inv_mergeAdversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components…
- 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.
/-- Recolouring that preserves colour-equality on every fact preserves all answers. -/theorem pm_recolor {n : ℕ} (F : List (Fin n × Fin n × PMAns)) (c c' : Fin n → Bool) (ρ : Fin n → ℤ) (hc : ∀ f ∈ F, (c' f.1 = c' f.2.1 ↔ c f.1 = c f.2.1)) : ∀ f ∈ F, (pmFam c' ρ).ans f.1 f.2.1 = (pmFam c ρ).ans f.1 f.2.1 := by intro f hf have h := hc f hf rw [pm_ans_fam, pm_ans_fam] have h' : (c' f.2.1 = c' f.1 ↔ c f.2.1 = c f.1) := by constructor <;> intro e <;> exact (by first | exact (h.1 e.symm).symm | exact (h.2 e.symm).symm) simp only [h, h']