Uniform prefix deletion costs equal prefix size times the last-edge cost
ProvedStabilityDichotomies.Bijunctive.uniform_prefix_deletion_sum_eq_last_edgeLet a finite set of positions be uniformly permuted, and let be a nonempty set of retained positions with distinguished last position . For any real cost depending on the retained image set and the selected element, the sum over permutations and retained positions of the deletion cost equals times the sum over permutations of the cost of deleting the element at . This is the symmetry identity used in the outside-first-mask part of Theorem 4.9.
Preamble
import Mathlib open scoped Classical BigOperators
Formal statement
theorem StabilityDichotomies.Bijunctive.uniform_prefix_deletion_sum_eq_last_edge {α : Type} [Fintype α] [DecidableEq α]
(S : Finset α) (j : α) (hj : j ∈ S) (cost : Finset α → α → ℝ) :
(∑ π : Equiv.Perm α, ∑ i ∈ S, cost (S.image π) (π i)) =
S.card * ∑ π : Equiv.Perm α, cost (S.image π) (π j) := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, outside-mask deletion symmetry.