Lemma 4.5 for a single relation: an AT-violation yields a pinned relaxation
ProvedSymBoolPCSP.CFixing.lemma_4_5_singlealternating-thresholdpolymorphismspromise-csprelaxation
Let . Suppose some has , i.e. some odd alternating threshold function fails to be a polymorphism of . Then there is such that every idempotent folded polymorphism of is a polymorphism of one of the following:
- , with ;
- , with and .
This is the single-relation core of Lemma 4.5 of Brakensiek–Guruswami. Let .
- By conservativity, contains some with .
- If : reduce to and pin zeros and ones. When , flip all coordinates first.
- If : Claim 4.6 forces a second weight , and pinning ones gives the second form.
- If : flip to the case .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- Lemma 4.5 for a single symmetric promise relation: if `S ⊆ T ⊆ {0,…,k}` and some `y ∈ AT(Ham_k(S))` has weight outside `T`, then every idempotent folded polymorphism of `(Ham_k(S), Ham_k(T))` is a polymorphism of `(Ham_{k'}({1}), Ham_{k'}({0,…,k'-2,k'}))` for some `k' ≥ 3`, or of `(Ham_{k'}({0,b}), Ham_{k'}({0,…,k'-1}))` for some `k' ≥ 2`, `1 ≤ b ≤ k'-1`. -/
theorem lemma_4_5_single {k : ℕ} {S T : Set ℕ} (hST : S ⊆ T) (hT : T ⊆ Set.Iic k)
{y : Fin k → Bool} (hy : y ∈ ATImage (Ham k S)) (hyT : hw y ∉ T) :
∃ k' : ℕ,
(3 ≤ k' ∧ ∀ (L : ℕ) (f : (Fin L → Bool) → Bool), IsIdempotent f → IsFolded f →
PolOf (Ham k S) (Ham k T) f → PolOf (Ham k' {1}) (Ham k' (Set.Iic (k' - 2) ∪ {k'})) f) ∨
(2 ≤ k' ∧ ∃ b : ℕ, 1 ≤ b ∧ b ≤ k' - 1 ∧ ∀ (L : ℕ) (f : (Fin L → Bool) → Bool),
IsIdempotent f → IsFolded f → PolOf (Ham k S) (Ham k T) f →
PolOf (Ham k' {0, b}) (Ham k' (Set.Iic (k' - 1))) 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.2, Lemma 4.5 and its proof, pp. 17–18