Symmetric sums of squares over k-subset hypercubes

• 成果类型: Article
• 署名作者: Raymond, Annie; Saunderson, James; Singh, Mohit; Thomas, Rekha R.
• 署名单位: University of Washington; University of Washington Seattle; Monash University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1127-6
• 发表日期: 2018
• 页码: 315-354
• 关键词: exploiting group symmetry; upper-bounds; terwilliger algebra; semidefinite; optimization; numbers; CODES

摘要

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 , but our results extend naturally to all values of . 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.