AT(P) contains the positivity patterns of the affine integer lattice spanned by P
ProvedSymBoolPCSP.CFixing.mem_ATImage_of_mem_diffClosureLet and identify a Boolean tuple with the integer vector . For odd let iff , and let , where is the set of tuples obtained by applying column-wise to rows from .
Let be the subgroup generated by all differences with . Then for every and every , the positivity pattern of , namely
lies in .
So contains the positivity patterns of the whole affine integer lattice spanned by . The proof appends pairs of rows to an odd-length matrix, which adds to the vector of alternating column sums. The statement holds for arbitrary Boolean relations; the Hamming-weight case drives Claim 4.6 of Brakensiek–Guruswami, and the same lattice is the one behind affine (AIP-type) relaxations.
Formalization Note is AT L with 0-based indices (coordinate has sign ), and is ATImage P. The lattice is AddSubgroup.closure of the set of difference vectors in Fin k → ℤ.
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- The AT-image `AT(P) = ⋃_{L odd} AT_L(P)` contains the positivity pattern of every point `x + z`, where `x ∈ P` and `z` lies in the subgroup of `ℤ^k` generated by the differences `v - u` (`u, v ∈ P`). -/
theorem mem_ATImage_of_mem_diffClosure {k : ℕ} (P : Set (Fin k → Bool)) {x : Fin k → Bool}
(hx : x ∈ P) {z : Fin k → ℤ}
(hz : z ∈ AddSubgroup.closure {d : Fin k → ℤ | ∃ u ∈ P, ∃ v ∈ P,
d = fun c => (if v c then 1 else 0) - (if u c then 1 else 0)}) :
(fun c => decide (0 < (if x c then (1 : ℤ) else 0) + z c)) ∈ ATImage P := by sorry
end SymBoolPCSP.CFixing