Theorem 4.13 — folded symmetric Γ avoiding Par, AT, Maj and their antis has only C(Γ)-fixing polymorphisms
ProvedSymBoolPCSP.CFixing.theorem_4_13Let be a finite, folded, symmetric family of Boolean promise relations. Assume that there are odd such that
are not polymorphisms of , where . Then there is a constant such that every polymorphism of , of every arity , is -fixing: for each such there is with and whenever vanishes on .
Here , and . Combined with the Label Cover reduction of §5 (Theorem 5.3), this structural statement gives the NP-hardness half of the paper's dichotomy for folded symmetric Boolean PCSPs (Theorem 2.16).
Formalization Note Only the structural statement is formalized; the NP-hardness conclusion of Theorems 2.16 and 5.3 is out of scope. Polymorphisms of every arity are quantified, as in the published IsPolymorphism; a folded family has no nullary polymorphisms, so this changes nothing. The constant precedes and .
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- Theorem 4.13 (p. 25): let `Γ` be a finite, folded, symmetric family of Boolean promise
relations, and assume there are odd `L₁, …, L₆` such that `Par_{L₁}`, `AT_{L₂}`, `Maj_{L₃}`,
`¬Par_{L₄}`, `¬AT_{L₅}` and `¬Maj_{L₆}` are not polymorphisms of `Γ`. Then there is `C(Γ)` such that
all polymorphisms of `Γ` (of every arity) are `C(Γ)`-fixing. -/
theorem theorem_4_13 {τ : Type} [Fintype τ] {ar : τ → ℕ} (𝔸 𝔹 : RelStruct τ ar Bool)
(hPF : IsPromiseFamily 𝔸 𝔹) (hfold : IsFoldedFamily 𝔸 𝔹) (hsym : IsSymmetricFamily 𝔸 𝔹)
(L₁ L₂ L₃ L₄ L₅ L₆ : ℕ) (hL₁ : Odd L₁) (hL₂ : Odd L₂) (hL₃ : Odd L₃) (hL₄ : Odd L₄)
(hL₅ : Odd L₅) (hL₆ : Odd L₆)
(h₁ : ¬ IsPolymorphism 𝔸 𝔹 (Par L₁)) (h₂ : ¬ IsPolymorphism 𝔸 𝔹 (AT L₂))
(h₃ : ¬ IsPolymorphism 𝔸 𝔹 (Maj L₃))
(h₄ : ¬ IsPolymorphism 𝔸 𝔹 (fun x : Fin L₄ → Bool => !Par L₄ x))
(h₅ : ¬ IsPolymorphism 𝔸 𝔹 (fun x : Fin L₅ → Bool => !AT L₅ x))
(h₆ : ¬ IsPolymorphism 𝔸 𝔹 (fun x : Fin L₆ → Bool => !Maj L₆ x)) :
∃ C : ℕ, ∀ (L : ℕ) (f : (Fin L → Bool) → Bool), IsPolymorphism 𝔸 𝔹 f → IsCFixing C f := by sorry
end SymBoolPCSP.CFixing
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.