AT(Ham_k(S)) contains every positivity pattern whose total is ≡ ℓ (mod ℓ′ − ℓ)
ProvedSymBoolPCSP.CFixing.mem_ATImage_ham_of_sign_sumalternating-thresholdpolymorphismspromise-csp
Let , , and suppose with and . Let have Hamming weight , and let satisfy
and
Then , where with the alternating-threshold function.
The second condition says exactly that some integer vector with total has positivity pattern . The first says that is a possible total of a vector in the affine lattice spanned by .
This gives the inclusions "" in parts 4 and 5 of Claim 4.6 of Brakensiek–Guruswami: take and for , or for a two-element . The bound is used to move single units between coordinates while keeping the row weight .
Formalization Note The disjunction is stated with ∃ c, y c = true / ∃ c, y c = false and casts of hw y to ℤ.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- `AT(Ham_k(S))` contains every `y ∈ {0,1}^k` that is the positivity pattern of an integer vector with total `T`, whenever `T ≡ ℓ (mod ℓ' - ℓ)` for some `ℓ, ℓ' ∈ S` with `1 ≤ ℓ ≤ k - 1`, `ℓ' ≤ k`; the condition on `(y, T)` is exactly that such an integer vector exists. -/
theorem mem_ATImage_ham_of_sign_sum {k : ℕ} {S : Set ℕ} {l l' : ℕ} (hl : l ∈ S) (hl1 : 1 ≤ l)
(hlk : l + 1 ≤ k) (hl' : l' ∈ S) (hl'k : l' ≤ k) (y : Fin k → Bool) (T : ℤ)
(hT : ((l' : ℤ) - l) ∣ T - l)
(h : ((∃ c, y c = true) ∧ (hw y : ℤ) ≤ T) ∨ ((∃ c, y c = false) ∧ T ≤ hw y)) :
y ∈ ATImage (Ham k S) := 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, Claim 4.6 (parts 4–5) and its proof, p. 17