A symmetric Boolean relation is the Hamming relation of its weights
ProvedSymBoolPCSP.CFixing.isSymmetricRel_eq_hampromise-cspsymmetric-relations
Let be symmetric, meaning it is closed under all permutations of coordinates. Then
That is, a symmetric Boolean relation is determined by its set of Hamming weights. Any two tuples of the same weight differ by a coordinate permutation. This is the identification used throughout §4 of Brakensiek–Guruswami.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- A symmetric Boolean relation is the Hamming relation of its set of weights: `P = Ham_k({|x| : x ∈ P})`. -/
theorem isSymmetricRel_eq_ham {k : ℕ} {P : Set (Fin k → Bool)} (hP : IsSymmetricRel P) :
P = Ham k {s | ∃ x ∈ P, hw x = s} := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, §2.4 and §4, p. 12 (symmetric relations as Ham_k(S))