Lemma 4.12 — idempotent case: avoiding Par, AT and Maj forces C(Γ)-fixing polymorphisms
ProvedSymBoolPCSP.CFixing.lemma_4_12booleanp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Let be a finite, symmetric, folded, idempotent family of Boolean promise relations such that for some odd . Then there is such that every polymorphism of is -fixing: there is a set of at most coordinates such that
The constant does not depend on the arity of . This is the idempotent case of Theorem 4.13.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic open PCSPBLPAff.Symmetric
Formal statement
namespace SymBoolPCSP.CFixing
/-- Lemma 4.12 (p. 24): if `Γ` is finite, symmetric, folded and idempotent and
`Par_{L₁}, AT_{L₂}, Maj_{L₃} ∉ Pol(Γ)` for some odd `L₁, L₂, L₃`, then there is `C(Γ) ∈ ℕ` such
that every polymorphism of `Γ` is `C(Γ)`-fixing. -/
theorem lemma_4_12 {τ : Type} [Fintype τ] {ar : τ → ℕ} (𝔸 𝔹 : RelStruct τ ar Bool)
(hPF : IsPromiseFamily 𝔸 𝔹) (hsym : IsSymmetricFamily 𝔸 𝔹) (hfold : IsFoldedFamily 𝔸 𝔹)
(hidem : IsIdempotentFamily 𝔸 𝔹) (L₁ L₂ L₃ : ℕ) (hL₁ : Odd L₁) (hL₂ : Odd L₂)
(hL₃ : Odd L₃) (hPar : ¬ IsPolymorphism 𝔸 𝔹 (Par L₁)) (hAT : ¬ IsPolymorphism 𝔸 𝔹 (AT L₂))
(hMaj : ¬ IsPolymorphism 𝔸 𝔹 (Maj L₃)) :
∃ C : ℕ, ∀ (L : ℕ) (f : (Fin L → Bool) → Bool), IsPolymorphism 𝔸 𝔹 f → IsCFixing C f := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 24, Lemma 4.12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.