Sparse sums of squares on finite abelian groups and improved semidefinite lifts (Q344935)

The paper is concerned with nonnegative functions on a finite abelian group \(G\) that are sparse with respect to the Fourier basis. The authors establish combinatorial conditions on subsets \(\mathcal{S}\) and \(\mathcal{T}\) of Fourier basis elements under which nonnegative functions with Fourier support \(\mathcal{S}\) are sums of squares of functions with Fourier support \(\mathcal{T}\). Their combinatorial condition involves constructing a chordal cover of a graph related to \(G\) and \(\mathcal{S}\) (Cayley graph Cay(\(\widehat{G},\mathcal{S}\))) with maximal cliques related to \(\mathcal{T}\). Their result relies on two main ingredients: the decomposition of sparse positive semidefinite matrices with a chordal sparsity pattern, as well as a simple but key observation exploiting the structure of the Fourier basis elements of \(G\). They apply their main result to two important special cases, namely \(G=\mathbb{Z}^n_2\) (the Boolean hypercube) and \(G=\mathbb{Z}_N\).