Folded functions commute with negating a relation: f(¬P) = ¬f(P)
ProvedSymBoolPCSP.CFixing.image_negRel_of_foldedpolymorphismspromise-csp
Let be folded, i.e. for all . Then for every relation ,
where and is the coordinate-wise negation.
This is the formal version of "reversing the notions of 0 and 1" at the end of the proof of Claim 4.8 of Brakensiek–Guruswami. For odd the majority function is folded, so . Since , any statement about the large-weight part of transfers to the small-weight part. The same applies to alternating threshold and parity of odd arity, and to every polymorphism of a folded family.
Formalization Note IsFolded f is ∀ x, f x = !f (neg x), which is equivalent to the displayed property; negRel P = neg '' P.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- For a folded `f` (`f(x) = ¬f(x̄)`), images commute with negation: `f(¬P) = ¬f(P)`. -/
theorem image_negRel_of_folded {k L : ℕ} (f : (Fin L → Bool) → Bool) (hf : IsFolded f)
(P : Set (Fin k → Bool)) : image f (negRel P) = negRel (image f P) := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, §4.2, end of the proof of Claim 4.8, p. 19; Definition 2.6, p. 9