  Let G be a finite abelian group. This paper is concerned with nonnegative
functions on G that are sparse with respect to the Fourier basis. We establish
combinatorial conditions on subsets S and T of Fourier basis elements under
which nonnegative functions with Fourier support S are sums of squares of
functions with Fourier support T. Our combinatorial condition involves
constructing a chordal cover of a graph related to G and S (the Cayley graph
Cay($\hat{G}$,S)) with maximal cliques related to T. Our 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.
  We apply our general result to two examples. First, in the case where $G =
\mathbb{Z}_2^n$, by constructing a particular chordal cover of the half-cube
graph, we prove that any nonnegative quadratic form in n binary variables is a
sum of squares of functions of degree at most $\lceil n/2 \rceil$, establishing
a conjecture of Laurent. Second, we consider nonnegative functions of degree d
on $\mathbb{Z}_N$ (when d divides N). By constructing a particular chordal
cover of the d'th power of the N-cycle, we prove that any such function is a
sum of squares of functions with at most $3d\log(N/d)$ nonzero Fourier
coefficients. Dually this shows that a certain cyclic polytope in
$\mathbb{R}^{2d}$ with N vertices can be expressed as a projection of a section
of the cone of psd matrices of size $3d\log(N/d)$. Putting $N=d^2$ gives a
family of polytopes $P_d \subset \mathbb{R}^{2d}$ with LP extension complexity
$\text{xc}_{LP}(P_d) = \Omega(d^2)$ and SDP extension complexity
$\text{xc}_{PSD}(P_d) = O(d\log(d))$. To the best of our knowledge, this is the
first explicit family of polytopes in increasing dimensions where
$\text{xc}_{PSD}(P_d) = o(\text{xc}_{LP}(P_d))$.
