TY - JOUR

T1 - Symmetric sums of squares over k-subset hypercubes

AU - Raymond, Annie

AU - Saunderson, James

AU - Singh, Mohit

AU - Thomas, Rekha R.

PY - 2018/2/1

Y1 - 2018/2/1

N2 - We consider the problem of finding sum of squares (sos) expressions to establish the non-negativity of a symmetric polynomial over a discrete hypercube whose coordinates are indexed by the k-element subsets of [n]. For simplicity, we focus on the case (Formula presented.), but our results extend naturally to all values of (Formula presented.). We develop a variant of the Gatermann–Parrilo symmetry-reduction method tailored to our setting that allows for several simplifications and a connection to flag algebras. We show that every symmetric polynomial that has a sos expression of a fixed degree also has a succinct sos expression whose size depends only on the degree and not on the number of variables. Our method bypasses much of the technical difficulties needed to apply the Gatermann–Parrilo method, and offers flexibility in obtaining succinct sos expressions that are combinatorially meaningful. As a byproduct of our results, we arrive at a natural representation-theoretic justification for the concept of flags as introduced by Razborov in his flag algebra calculus. Furthermore, this connection exposes a family of non-negative polynomials that cannot be certified with any fixed set of flags, answering a question of Razborov in the context of our finite setting.

AB - We consider the problem of finding sum of squares (sos) expressions to establish the non-negativity of a symmetric polynomial over a discrete hypercube whose coordinates are indexed by the k-element subsets of [n]. For simplicity, we focus on the case (Formula presented.), but our results extend naturally to all values of (Formula presented.). We develop a variant of the Gatermann–Parrilo symmetry-reduction method tailored to our setting that allows for several simplifications and a connection to flag algebras. We show that every symmetric polynomial that has a sos expression of a fixed degree also has a succinct sos expression whose size depends only on the degree and not on the number of variables. Our method bypasses much of the technical difficulties needed to apply the Gatermann–Parrilo method, and offers flexibility in obtaining succinct sos expressions that are combinatorially meaningful. As a byproduct of our results, we arrive at a natural representation-theoretic justification for the concept of flags as introduced by Razborov in his flag algebra calculus. Furthermore, this connection exposes a family of non-negative polynomials that cannot be certified with any fixed set of flags, answering a question of Razborov in the context of our finite setting.

UR - http://www.scopus.com/inward/record.url?scp=85014554821&partnerID=8YFLogxK

U2 - 10.1007/s10107-017-1127-6

DO - 10.1007/s10107-017-1127-6

M3 - Article

AN - SCOPUS:85014554821

SN - 0025-5610

VL - 167

SP - 315

EP - 354

JO - Mathematical Programming

JF - Mathematical Programming

IS - 2

ER -