Lemma 4.9 sum conditions from the relaxation (Ham_k{0,b}, Ham_k{0..k-1})
ProvedSymBoolPCSP.CFixing.sum_conditions_of_relax_zerobooleanpolymorphismspromise-csp
Let , put , and let be a folded polymorphism of the promise relation . Fix and, for , let be the set of such that for every with , where is the indicator vector of . Then:
- if , then ;
- if and , then .
These are conditions (1) and (2) of Lemma 4.9 for the second relaxation produced by Lemma 4.5 (Case 2 of the proof of Lemma 4.10).
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- Sum conditions from the second relaxation of Lemma 4.5: let `1 ≤ b ≤ k − 1`, `n = k − b + 1`, and let `f` be a folded polymorphism of `(Ham_k({0, b}), Ham_k({0,…,k−1}))`. Fix `T ⊆ [L]` and let `S_β` (`β ∈ {0,1}`) be the set of `s` such that `f(e_X) = β` for every `X ⊆ T` with `|X| = s`. Then any sum of `n` elements of `S₁` lies in `S₀`, and `a + b₁ + ⋯ + b_{n−1} ∈ S₁` whenever `a ∈ S₀` and all `bᵢ ∈ S₁`. -/
theorem sum_conditions_of_relax_zero {k b L : ℕ} (hb1 : 1 ≤ b) (hbk : b ≤ k - 1)
(f : (Fin L → Bool) → Bool) (hfold : IsFolded f)
(hf : PolOf (Ham k {0, b}) (Ham k (Set.Iic (k - 1))) f)
(T : Finset (Fin L)) (S₀ S₁ : Set ℕ)
(hS₀ : ∀ s, s ∈ S₀ ↔ ∀ X ⊆ T, X.card = s → f (indicator X) = false)
(hS₁ : ∀ s, s ∈ S₁ ↔ ∀ X ⊆ T, X.card = s → f (indicator X) = true) :
(∀ β : Fin (k - b + 1) → ℕ, (∀ i, β i ∈ S₁) → ∑ i, β i ∈ S₀) ∧
(∀ a ∈ S₀, ∀ β : Fin (k - b + 1 - 1) → ℕ, (∀ i, β i ∈ S₁) → a + ∑ i, β i ∈ S₁) := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, proof of Lemma 4.10, Case 2, pp. 22–23