Lemma 4.5 — an Alternating-Threshold-excluding relaxation
ProvedSymBoolPCSP.CFixing.lemma_4_5booleanp2o-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 is a relaxation of (that is, ) for one of
- , , with ; or
- , , with and .
The relaxation depends only on , not on the arity of the polymorphism, and supplies the combinatorial constraint used in Lemma 4.10.
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.5 (p. 17): if `Γ` is symmetric, folded and idempotent and `AT_L ∉ Pol(Γ)` for some
odd `L`, then `Γ′ = {(P, Q)}` is a relaxation of `Γ` for either
`P = Ham_k({1})`, `Q = Ham_k({0, 1, …, k − 2, k})`, `k ≥ 3`, or
`P = Ham_k({0, b})`, `Q = Ham_k({0, …, k − 1})`, `k ≥ 2`, `b ∈ {1, …, k − 1}`. -/
theorem lemma_4_5 {τ : Type} [Fintype τ] {ar : τ → ℕ} (𝔸 𝔹 : RelStruct τ ar Bool)
(hPF : IsPromiseFamily 𝔸 𝔹) (hsym : IsSymmetricFamily 𝔸 𝔹) (hfold : IsFoldedFamily 𝔸 𝔹)
(hidem : IsIdempotentFamily 𝔸 𝔹) (L : ℕ) (hL : Odd L) (hAT : ¬ IsPolymorphism 𝔸 𝔹 (AT L)) :
∃ k : ℕ,
(3 ≤ k ∧ IsRelaxation 𝔸 𝔹 (Ham k {1}) (Ham k (Set.Iic (k - 2) ∪ {k}))) ∨
(2 ≤ k ∧ ∃ b : ℕ, 1 ≤ b ∧ b ≤ k - 1 ∧
IsRelaxation 𝔸 𝔹 (Ham k {0, b}) (Ham k (Set.Iic (k - 1)))) := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 17, Lemma 4.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.