Symmetric sums of squares over k-subset hypercubes

Annie Raymond, James Saunderson, Mohit Singh, Rekha R. Thomas

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)315-354
Number of pages40
JournalMathematical Programming
Volume167
Issue number2
DOIs
Publication statusPublished - 1 Feb 2018

Cite this

Raymond, Annie ; Saunderson, James ; Singh, Mohit ; Thomas, Rekha R. / Symmetric sums of squares over k-subset hypercubes. In: Mathematical Programming. 2018 ; Vol. 167, No. 2. pp. 315-354.
@article{1081dcd2128648fba43fc91c59f530e6,
title = "Symmetric sums of squares over k-subset hypercubes",
abstract = "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.",
author = "Annie Raymond and James Saunderson and Mohit Singh and Thomas, {Rekha R.}",
year = "2018",
month = "2",
day = "1",
doi = "10.1007/s10107-017-1127-6",
language = "English",
volume = "167",
pages = "315--354",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "2",

}

Symmetric sums of squares over k-subset hypercubes. / Raymond, Annie; Saunderson, James; Singh, Mohit; Thomas, Rekha R.

In: Mathematical Programming, Vol. 167, No. 2, 01.02.2018, p. 315-354.

Research output: Contribution to journalArticleResearchpeer-review

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

VL - 167

SP - 315

EP - 354

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -