Conservative functions map relations of constant tuples into themselves
ProvedSymBoolPCSP.CFixing.image_subset_of_conservativepolymorphismspromise-csp
Call conservative if for every the value equals one of the entries . Let , i.e. every tuple of is constant ( or ). Then
Indeed, all columns of a matrix with constant rows equal one vector , so the output is the constant tuple with value , which is one of the rows. Odd-arity majority and alternating-threshold functions are conservative; this gives the cases and for in Claims 4.6 and 4.8 of Brakensiek–Guruswami. The lemma applies to any conservative operation, e.g. any symmetric threshold function of odd arity.
Formalization Note is image f P (Definition 2.7); conservativity is ∀ v, ∃ l, f v = v l.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- A conservative function (`f(v)` is always one of the entries of `v`) maps every relation consisting of constant tuples into itself: `f(P) ⊆ P` whenever `P ⊆ Ham_k({0, k})`. -/
theorem image_subset_of_conservative {k L : ℕ} (f : (Fin L → Bool) → Bool)
(hf : ∀ v, ∃ l, f v = v l) (P : Set (Fin k → Bool)) (hP : P ⊆ Ham k {0, k}) :
image f P ⊆ 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, Claim 4.6 (parts 1–3) and Claim 4.8 (first case), pp. 17–19