Lemma 4.10 — avoiding Parity and Alternating-Threshold bounds |{i : f(e_i) = 1}|
ProvedSymBoolPCSP.CFixing.lemma_4_10booleanp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Let be a finite, symmetric, folded, idempotent family of Boolean promise relations such that and for some odd . Then there is such that for every and every polymorphism of ,
where is the -th unit vector.
The constant is uniform over all polymorphisms of all arities; this uniformity is the point of the lemma.
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.10 (p. 22): if `Γ` is finite, symmetric, folded and idempotent and
`Par_{L₁}, AT_{L₂} ∉ Pol(Γ)` for some odd `L₁, L₂`, then there is `c(Γ) ∈ ℕ` such that every
polymorphism `f` of `Γ`, of any arity `L`, has `|{i ∈ [L] : f(e_i) = 1}| ≤ c(Γ)`. -/
theorem lemma_4_10 {τ : Type} [Fintype τ] {ar : τ → ℕ} (𝔸 𝔹 : RelStruct τ ar Bool)
(hPF : IsPromiseFamily 𝔸 𝔹) (hsym : IsSymmetricFamily 𝔸 𝔹) (hfold : IsFoldedFamily 𝔸 𝔹)
(hidem : IsIdempotentFamily 𝔸 𝔹) (L₁ L₂ : ℕ) (hL₁ : Odd L₁) (hL₂ : Odd L₂)
(hPar : ¬ IsPolymorphism 𝔸 𝔹 (Par L₁)) (hAT : ¬ IsPolymorphism 𝔸 𝔹 (AT L₂)) :
∃ c : ℕ, ∀ (L : ℕ) (f : (Fin L → Bool) → Bool), IsPolymorphism 𝔸 𝔹 f →
(Finset.univ.filter (fun i : Fin L => f (indicator {i}) = true)).card ≤ c := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 22, Lemma 4.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.