On Symmetric Pseudo-Boolean Functions: Factorization, Kernels and Applications

Abstract

A symmetric pseudo-Boolean function is a map from Boolean tuples to real numbers which is invariant under input variable interchange. We prove that any such function can be equivalently expressed as a power series or factorized. The kernel of a pseudo-Boolean function is the set of all inputs that cause the function to vanish identically. Any $n$-variable symmetric pseudo-Boolean function $f(x_1,x_2,\dots ,x_n)$ has a kernel corresponding to at least one $n$-affine hyperplane, each hyperplane is given by a constraint ${\sum }_{l=1}^n{x}_l=\lambda$ for $\lambda \in \mathbb{C}$ constant. We use these results to analyze symmetric pseudo-Boolean functions appearing in the literature of spin glass energy functions (Ising models), quantum information and tensor networks.

10 pages