Lemma 4.7 for a single relation: a Maj-violation yields a pinned relaxation
ProvedSymBoolPCSP.CFixing.lemma_4_7_singlemajoritypolymorphismspromise-csprelaxation
Let . Suppose some has . Then there is such that every idempotent folded polymorphism of is a polymorphism of one of the following:
- , with odd;
- , with and .
This is the single-relation core of Lemma 4.7 of Brakensiek–Guruswami. Let , and .
- By Claim 4.8, .
- If : reduce to and pin, giving arity .
- If : flip and apply the previous case.
- Otherwise lies strictly between two weights of with (after flipping if necessary). Pinning ones and zeros gives the second form.
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.7 for a single symmetric promise relation: if `S ⊆ T ⊆ {0,…,k}` and some `y ∈ Maj(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'}({(k'+1)/2}), Ham_{k'}({0,…,k'-1}))` for some odd `k' ≥ 3`, or of `(Ham_{k'}({1,k'}), Ham_{k'}({0,…,k'} ∖ {b}))` for some `k' ≥ 3`, `2 ≤ b ≤ k'-1`. -/
theorem lemma_4_7_single {k : ℕ} {S T : Set ℕ} (hST : S ⊆ T) (hT : T ⊆ Set.Iic k)
{y : Fin k → Bool} (hy : y ∈ MajImage (Ham k S)) (hyT : hw y ∉ T) :
∃ k' : ℕ,
(3 ≤ k' ∧ Odd k' ∧ ∀ (L : ℕ) (f : (Fin L → Bool) → Bool), IsIdempotent f → IsFolded f →
PolOf (Ham k S) (Ham k T) f →
PolOf (Ham k' {(k' + 1) / 2}) (Ham k' (Set.Iic (k' - 1))) f) ∨
(3 ≤ k' ∧ ∃ b : ℕ, 2 ≤ 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' {1, k'}) (Ham k' (Set.Iic k' \ {b})) 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.7 and its proof, p. 19