Folded polymorphisms of (Ham_k(S), Ham_k(T)) are polymorphisms of (Ham_k(k−S), Ham_k(k−T))
ProvedSymBoolPCSP.CFixing.polOf_ham_flippolymorphismspromise-csprelaxation
Let be folded and . If is a polymorphism of , then is a polymorphism of
This is Claim 4.3 of Brakensiek–Guruswami applied with the full flip set . Flipping every coordinate maps onto . It is the precise form of "by symmetry between and " used in the proofs of Lemmas 4.5 and 4.7.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- Complementing all coordinates (Claim 4.3 with the full flip set): for folded `f`, `f ∈ Pol(Ham_k(S), Ham_k(T))` implies `f ∈ Pol(Ham_k(k - S), Ham_k(k - T))`. -/
theorem polOf_ham_flip {k L : ℕ} {S T : Set ℕ} (hST : S ⊆ T) (f : (Fin L → Bool) → Bool)
(hfold : IsFolded f) (hf : PolOf (Ham k S) (Ham k T) f) :
PolOf (Ham k {l | l ≤ k ∧ k - l ∈ S}) (Ham k {l | l ≤ k ∧ k - l ∈ T}) f := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, §4.1, Claim 4.3, p. 16