## Abstract

Let G be a ﬁnite abelian group. This paper is concerned with nonnegative functions on G that are

nonnegative quadratic form in

of the cone of positive semideﬁnite matrices of size

*sparse*with respect to the Fourier basis. We establish combinatorial conditions on subsets**and***S**of Fourier basis elements under which nonnegative functions with Fourier support***T****are sums of squares of functions with Fourier support***S**. Our combinatorial condition involves constructing a chordal cover of a graph related to***T****and***G***(the Cayley graph Cay(***S***,***Gˆ***)) with maximal cliques related to***S**. Our result relies on two main ingredients: the decomposition of sparse positive semideﬁnite matrices with a chordal sparsity pattern, as well as a simple but key observation exploiting the structure of the Fourier basis elements of***T****(the characters of***G***). We apply our general result to two examples. First, in the case where***G***=***G**Z*^{n}_{2}, by constructing a particular chordal cover of the half-cube graph, we prove that anynonnegative quadratic form in

*binary variables is a sum of squares of functions of degree at most I***n****/***n***2**1, establishing a conjecture of Laurent. Second, we consider nonnegative functions of degree d on**(when***Z*_{N}**divides***d**). By constructing a particular chordal cover of the***N****th power of the***d***-cycle, we prove that any such function is a sum of squares of functions with at most***N***3**log(*d***/***N***) nonzero Fourier coefﬁcients. Dually this shows that a certain cyclic polytope in***d***with***R*^{2}^{d}**vertices can be expressed as a projection of a section***N*of the cone of positive semideﬁnite matrices of size

**3**log(*d***/***N**). Putting***d****=***N***gives a family of polytopes in***d*2**with linear programming extension complexity***R*2*d***Ω**(**) and semideﬁnite programming extension complexity***d*^{2}**(***O**log(***d****)). To the best of our knowledge, this is the ﬁrst explicit family of polytopes (***d***) in increasing dimensions where***P*_{d}**xc**(_{PSD}**) =***Pd***(***o***xc**(_{LP}**)), where***P*_{d}**xc**and_{PSD}**xc****LP**are respectively the**SDP**and**LP**extension completely.Original language | English |
---|---|

Pages (from-to) | 149-191 |

Number of pages | 43 |

Journal | Mathematical Programming |

Volume | 160 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - Nov 2016 |

Externally published | Yes |