Symmetric sums of squares over k-subset hypercubes

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 \(k=2\), but our results extend naturally to all values of \(k \ge 2\). 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.

Several people offered valuable input to this paper. In particular, we thank Albert Atserias, Monty McGovern, Pablo Parrilo and Sasha Razborov. We especially thank Greg Blekherman for his help with several facets of the representation theory that underlies this work.

Authors and Affiliations

1. Department of Mathematics, University of Washington, Box 354350, Seattle, WA, 98195, USA

   Annie Raymond & Rekha R. Thomas

2. Department of Electrical and Computer Systems Engineering, Monash University, Melbourne, VIC, 3800, Australia

   James Saunderson

3. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30304, USA

   Mohit Singh

Corresponding author

Correspondence to Annie Raymond.

James Saunderson and Rekha R. Thomas were partially supported by the National Science Foundation under the Grants CCF-1409836 and DMS-1418728 respectively.

Appendix 1: Proof of Lemma 1

The aim of this appendix is to prove Lemma 1. The proof can already be found in [34]; we reprint it here for completeness.

Recall that any \(\mathfrak {S}_n\)-module V has an isotypic decomposition

By Maschke’s theorem, the components \(V_{\varvec{\lambda }}\) further break into a direct sum of irreducibles \(V_{\varvec{\lambda }}^i\) giving the decomposition:

Now consider the following version of Young’s Rule.

Theorem 9

(Young’s Rule) Let \(\varvec{\lambda }=(\lambda _1,\ldots , \lambda _k)\) and \(\varvec{\mu }\) be partitions of n. The multiplicity of the trivial representation of \(\mathfrak {S}_{\varvec{\lambda }} :=\mathfrak {S}_{\lambda _1}\times \ldots \times \mathfrak {S}_{\lambda _k}\) in the restriction of some irreducible representation \(V^i_{\varvec{\mu }}\) to \(\mathfrak {S}_{\varvec{\lambda }}\) is equal to the number of semistandard tableaux of shape \(\varvec{\mu }\) and type \(\varvec{\lambda }\).

Note that in most books, e.g., in [10, Corollary 4.39], this result is given in terms of induced representations, but by Frobenius reciprocity [10, Corollary 3.20], the above is an equivalent version.

Let \(\varvec{\lambda }=(\lambda _1,\lambda _2,\ldots , \lambda _k)\) be a partition and \(N_{\varvec{\lambda }}\) be the sequence containing \(\lambda _i\) copies of the number i for \(i =1,\ldots ,k\). A semistandard tableau of shape \(\varvec{\mu }\) and type \(\varvec{\lambda }\) is a tableau of \(\varvec{\mu }\) with numbers coming from \(N_{\varvec{\lambda }}\) such that the numbers are non-decreasing along rows and increasing along columns. The number of semistandard tableaux of shape \(\varvec{\mu }\) and type \(\varvec{\lambda }\) is called the Kostka number \(K_{\varvec{\mu }\varvec{\lambda }}\). We need to know when \(K_{\varvec{\mu }\varvec{\lambda }}\) is non-zero, and the following standard fact gives a necessary characterization.

Lemma 9

If \(\varvec{\lambda }\) is lexicographically greater than \(\varvec{\mu }\) or if \(\varvec{\mu }\) has more parts than \(\varvec{\lambda }\), then \(K_{\varvec{\mu }\varvec{\lambda }}=0\).

Proof

Suppose \(\varvec{\lambda }=(\lambda _1, \ldots , \lambda _k)\) and \(\varvec{\mu }=(\mu _1, \ldots , \mu _l)\). Note that since the numbers are increasing in the columns, the minimum number in row i is i.

Suppose \(\lambda _i=\mu _i\) for all \(1\le i < i^*\) and \(\lambda _{i^*}>\mu _{i^*}\), i.e., \(\varvec{\lambda }\) is lexicographically greater than \(\varvec{\mu }\). Then any semistandard tableau of shape \(\varvec{\mu }\) and type \(\varvec{\lambda }\) will have to have \(\lambda _1\) 1’s in row 1, \(\ldots \), and \(\lambda _{i^*-1}\) \((i^*-1)\)’s in row \(i^*-1\) in order to have increasing numbers along the columns. Then one would attempt to put \(\lambda _{i^*}\) \(i^*\)’s in row \(i^*\), but that is not possible since \(\mu _{i^*}<\lambda _{i^*}\), and so at least one \(i^*\) will have to be in row \(i^*+1\), meaning that we don’t have a semistandard tableau since the columns are not strictly increasing.

Now suppose that \(\varvec{\mu }\) has more parts than \(\varvec{\lambda }\), i.e., \(l>k\). Look at the first column of a semistandard tableau: there needs to be at least l distinct numbers in it, but \(N_{\varvec{\lambda }}\) contains only k distinct numbers and so there is no semistandard tableau. \(\square \)

Using Theorem 9 and Lemma 9, we can determine which irreducibles contribute components to a given \(\mathfrak {R}_{\tau _{\varvec{\lambda }}}\)-invariant polynomial.

Theorem 10

A \(\mathfrak {R}_{\tau _{\varvec{\lambda }}}\)-invariant polynomial \(\mathsf {f}\) in \(V = \mathbb {R}[\mathbf x]_{\le d}\) lies in \(\bigoplus _{\varvec{\mu } \unrhd \varvec{\lambda }} V_{\varvec{\mu }}\).

Proof

Note that \(\mathsf {f}\) is equivalently \(\mathfrak {S}_{\varvec{\lambda }}=\mathfrak {S}_{\lambda _1}\times \ldots \times \mathfrak {S}_{\lambda _k}\)-invariant where we now take \(\mathfrak {S}_{\lambda _i}\) to be the symmetric group on the entries in \(\tau _{\varvec{\lambda }}\) in row i. Thus, by Theorem 9, the multiplicity of the trivial representation of \(\mathfrak {S}_{\varvec{\lambda }}\) in \(V_{\varvec{\mu }}^i\) restricted to \(\mathfrak {S}_{\varvec{\lambda }}\) is the number of semistandard tableaux of shape \(\varvec{\mu }\) and type \(\varvec{\lambda }\). By Lemma 9, this multiplicity is zero if \(\varvec{\mu }\) is lexicographically smaller than \(\varvec{\lambda }\) or if it has more parts than \(\varvec{\lambda }\). Therefore, \(\mathsf {f}\in \bigoplus _{\varvec{\mu } \unrhd \varvec{\lambda }} V_{\varvec{\mu }}\). \(\square \)

As a consequence, since \(V^{\mathfrak {R}_{\tau _{\varvec{\lambda }}}}\) corresponds to the span of polynomials of degree at most d invariant under \(\mathfrak {R}_{\tau _{\varvec{\lambda }}}\), we obtain Lemma 1.

Appendix 2: Proof of Theorem 1

The aim of this appendix is to prove Theorem 1, describing the structure of symmetry-reduced certificates of non-negativity for \(\mathfrak {S}_n\)-invariant polynomials that are d-sos. Rather than proving Theorem 1 directly, we establish a slightly more general result (Theorem 11 to follow) and then specialize to give Theorem 1. This more general result is essentially the main result of Gatermann and Parrilo [16]. In Sect. 1, we summarize some basic facts about real representations needed for the appendix. In Sect. 1, we examine what happens when we symmetrize products and squares of polynomials under a finite group action, leading to a proof of Theorem 11 and of Theorem 1.

1.1 Preliminaries on real representations

Let G be a finite group and let U be a finite-dimensional \(\mathbb {R}G\)-module, (i.e., a real vector space with an action of G by linear transformations). An \(\mathbb {R}G\)-module U is irreducible if the only real vector subspaces of U invariant under the action of G are \(\{0\}\) and U. Given any pair U, W of \(\mathbb {R}G\)-modules, let \(\text {Hom}_G(U,W)\) be the vector space of \(\mathbb {R}\)-linear maps \(\phi :U\rightarrow W\) such that \(\phi (g\cdot u) = g\cdot \phi (u)\) for all \(u\in U\). If U, W are \(\mathbb {R}G\)-modules, then the tensor product (over \(\mathbb {R}\)), \(U\otimes W\), is a \(\mathbb {R}G\)-module with the action \(g\cdot (u\otimes w) = (g\cdot u)\otimes (g\cdot w)\). If U is a \(\mathbb {R}G\)-module, then the space \(U^*\) of \(\mathbb {R}\)-valued linear functionals on U is a \(\mathbb {R}G\)-module via \((g\cdot \ell )(u) = \ell (g^{-1}\cdot u)\).

If U is a \(\mathbb {R}G\)-module, define the linear map \(\text {sym}_{G}:U\rightarrow U\) by

Clearly, the image of \(\text {sym}_G\) is the set of elements of U fixed by the action of G, i.e., \(U^G:=\{u\in U:\; g\cdot u = u\;\;\text {for all }g\in G\}\). We omit the subscript G from \(\text {sym}_G\) if the group is clear from the context. We also note that \(\text {sym}_{G}\in \text {Hom}_G(U,U^G)\) where \(U^G\) carries the trivial action of G.

We now recall the the isotypic decomposition of a \(\mathbb {R}G\)-module V. Let \((S_{\lambda })_{\lambda \in {\varLambda }}\) be an enumeration of inequivalent irreducible \(\mathbb {R}G\)-modules and let \(n_\lambda = \dim (S_\lambda )\). For each \(\lambda \in {\varLambda }\), let \(\text {Hom}_{G}(S_\lambda ,V)\) denote the \(m_\lambda \)-dimensional multiplicity space of \(S_\lambda \) in V. Let

denote the isotypic component of V corresponding to \(S_{\lambda }\). The decomposition \(V = \bigoplus _{\lambda \in {\varLambda }} V_{\lambda }\) is the isotypic decomposition of V.

There are two natural ways to construct subspaces of the isotypic components \(V_{\lambda }\). If we fix a non-zero \(\phi \in \text {Hom}_G(S_\lambda ,V)\) and consider \(\{\phi (s): s\in S_\lambda \}\), we obtain a G-invariant subspace of \(V_{\lambda }\) that is isomorphic to \(S_{\lambda }\) and has dimension \(n_\lambda \). On the other hand, if we fix a non-zero \(s_\lambda \in S_{\lambda }\), we can define

This is a vector subspace of \(V_{\lambda }\) of dimension \(m_\lambda \), but is not G-invariant. It is however isomorphic to the multiplicitly space \(\text {Hom}_G(S_\lambda ,V)\) as a vector space.

Lemma 10

Fix some non-zero \(s_\lambda \in S_\lambda \). Then the map \({\varPhi }_{s_\lambda }: \text {Hom}_G(S_\lambda ,V)\rightarrow W_{s_{\lambda }}\) defined by \({\varPhi }_{s_\lambda }(\phi ) = \phi (s_\lambda )\) is an isomorphism of vector spaces.

Proof

The map \({\varPhi }_{s_\lambda }\) is clearly linear. It is surjective by the definition of \(W_{s_\lambda }\). It remains to show that \({\varPhi }_{s_\lambda }\) is injective. Let \(\phi \in \text {Hom}_G(S_\lambda ,V)\) and suppose that \({\varPhi }_{s_\lambda }(\phi ) = \phi (s_\lambda ) = 0\). Since \(\phi \in \text {Hom}_G(S_\lambda ,V)\), the kernel of \(\phi \) is an invariant subspace of \(S_\lambda \) that contains the non-zero element \(s_\lambda \). Since \(S_\lambda \) is irreducible, the kernel of \(\phi \) must then be all of \(S_\lambda \), and so \(\phi =0\). Hence \({\varPhi }_{s_\lambda }\) is injective and so an isomorphism of vector spaces. \(\square \)

The following standard fact about invariant bilinear forms on \(\mathbb {R}G\)-modules, is central to our discussion. We include a proof for completeness.

Lemma 11

If G is a finite group and U is a finite-dimensional \(\mathbb {R}G\)-module then U has a non-degenerate, G-invariant, symmetric, bilinear form \(B:U\times U\rightarrow \mathbb {R}\) satisfying \(B(u,u)>0\) for all non-zero \(u\in U\). Moreover, if U is irreducible, then any G-invariant bilinear form on U is a scalar multiple of B.

Proof

Let \(\langle \cdot ,\cdot \rangle \) be any inner product on U, i.e., \(\langle \cdot , \cdot \rangle \) is a symmetric, non-degenerate, positive definite, bilinear form. Then \(B:U\times U \rightarrow \mathbb {R}\), defined by

is G-invariant, and is a convex combination of non-degenerate, symmetric, positive definite, bilinear forms. Hence, B also has these properties. Now suppose U is irreducible and \(B'\) is another G-invariant bilinear form on U. Since \(B(\cdot ,\cdot )\) is positive definite, we can choose \(\lambda \) such that the subspace \(\{v\in U: \lambda B(u,v) = B'(u,v)\;\;\text {for all }u\in U\}\) is non-zero. (Here, we can take \(\lambda \) to be any generalized eigenvalue for the pair of symmetric matrices representing the bilinear forms.) Since B and \(B'\) are both G-invariant, this is a G-invariant subspace of U. Since U is irreducible, we must have \(\{v\in U: \lambda B(u,v) = B'(u,v)\;\;\text {for all }u\in U\} = U\). Hence \(\lambda B = B'\), as required. \(\square \)

We now record basic facts about G-invariant elements of tensor products.

Lemma 12

If G is a finite group and U and W be non-isomorphic irreducible finite-dimensional \(\mathbb {R}G\)-modules, then \((U\otimes W)^G = \{0\}\).

Proof

Suppose W and U are irreducible and not isomorphic. By Schur’s lemma (see, for instance, [38, Section 2.2]), \(\text {Hom}_{G}(W,U) = \{0\}\). Since U is a finite-dimensional \(\mathbb {R}G\)-module, by Lemma 11 it has a non-degenerate, G-invariant, bilinear form \(B: U\times U\rightarrow \mathbb {R}\). Hence the map \(U\ni u \mapsto B(u,\cdot )\in U^*\) gives an isomorphism between U and \(U^*\). Then \((U\otimes W)^G \cong (U^* \otimes W)^G \cong \text {Hom}_G(U,W) = \{0\}\). \(\square \)

The following result tells us that if U is irreducible, then \((U\otimes U)^G\) is one-dimensional. It also explicitly describes the map \(\text {sym}:U\otimes U\rightarrow (U\otimes U)^G\).

Lemma 13

If G is a finite group and U is a finite-dimensional irredcuible \(\mathbb {R}G\)-module then for all \(s\in U\) and all \(u,u'\in U\),

where \(B(\cdot ,\cdot )\) is the (unique up to scale) non-zero G-invariant bilinear form on U.

Proof

If \(s=0\) then the statement clearly holds. Assume \(s\ne 0\) and let \(\eta \in (U\otimes U)^*\) be an arbitrary linear functional on \(U\otimes U\). Then the map \((u,u')\mapsto \eta (\text {sym}(u\otimes u'))\) is a G-invariant bilinear form on U. By Lemma 11, \(\eta (\text {sym}(u\otimes u')) = \kappa (\eta )B(u,u')\) for some \(\kappa (\eta )\in \mathbb {R}\). By putting \(u=u'=s\), we see that \(\kappa (\eta ) = \eta (\text {sym}(s\otimes s))/B(s,s)\). Together these imply that

Since \(\eta \) was arbitrary, it follows that \(B(s,s)\,\text {sym}(u\otimes u') = B(u,u')\, \text {sym}(s\otimes s)\) for all \(u,u'\in U\). \(\square \)

1.2 Symmetrizing sums of squares

Let \(\mathbb {R}[{\mathsf {x}}]\) be the polynomial ring in q indeterminates and let G be a finite group acting linearly on \(\mathbb {R}^q\). Then G acts on \(\mathbb {R}[{\mathsf {x}}]\) via \((g\cdot \mathsf {p})({\mathsf {x}}) = \mathsf {p}(g^{-1}\cdot {\mathsf {x}})\). If \(\mathcal {I}\) be an ideal invariant under the action of G, then the action of G descends to the quotient \(\mathbb {R}[{\mathsf {x}}]/\mathcal {I}\). Let V be a finite-dimensional G-invariant subspace of \(\mathbb {R}[{\mathsf {x}}]/\mathcal {I}\). Let \(V\otimes V\) be the tensor product (over \(\mathbb {R}\)) of V with itself. Given \(\mathsf {f}_1,\,\mathsf {f}_2\in V\), their product \(\mathsf {f}_1\mathsf {f}_2\in \mathbb {R}[{\mathsf {x}}]/\mathcal {I}\) is a \(\mathbb {R}\)-bilinear map \(V\times V\rightarrow \mathbb {R}[{\mathsf {x}}]/\mathcal {I}\). Hence there is a linear map \(M_V: V\otimes V\rightarrow \mathbb {R}[{\mathsf {x}}]/\mathcal {I}\) such that

The actions of G on \(V\otimes V\) and on \(\mathbb {R}[{\mathsf {x}}]/\mathcal {I}\) are such that \(M_V\) is a \(\mathbb {R}G\)-module homomorphism.

As before, let \((S_{\lambda })_{\lambda \in {\varLambda }}\) be an enumeration of inequivalent irreducible \(\mathbb {R}G\)-modules. Let \(V = \bigoplus _{\lambda \in {\varLambda }} V_\lambda \) be the isotypic decomposition of V. We now show that if we take functions from two different isotypic components of V and symmetrize their product, the result is zero.

Lemma 14

If \(\lambda \ne \mu \), \(\mathsf {f}_\lambda \in V_\lambda \), and \(\mathsf {f}_\mu \in V_\mu \), then \(\text {sym}(\mathsf {f}_\lambda \mathsf {f}_\mu ) = 0\).

Proof

First, let \(\phi _{\mu }\in \text {Hom}_{G}(S_\mu ,V)\) and \(\phi _\lambda \in \text {Hom}_G(S_\lambda ,V)\), and let \(u_\mu \in S_\mu \) and \(u_{\lambda }\in S_{\lambda }\). Then, since \(M_V\) and \(\phi _\mu \otimes \phi _\lambda \) are both \(\mathbb {R}\)-linear and commute with the action of G, we have that

Since \(\mu \ne \lambda \), Lemma 12 tells us that \(\text {sym}(u_\mu \otimes u_\lambda )\in (S_\mu \otimes S_\lambda )^G = \{0\}\) and so \(\text {sym}(\phi _\mu (u_\mu )\phi _\lambda (u_\lambda )) = 0\). Finally, because any \(\mathsf {f}_\mu \in V_{\mu }\) is a linear combination of elements of the form \(\phi _\mu (u_\mu )\) for \(\phi _{\mu }\in \text {Hom}_{G}(S_\mu ,V)\) and \(u_\mu \in S_\mu \) (and similarly for any \(\mathsf {f}_\lambda \in V_{\lambda }\)), we have that \(\text {sym}(\mathsf {f}_\mu \mathsf {f}_\lambda )=0\) by bilinearity. \(\square \)

We now investigate what happens when we symmetrize products of certain elements of \(V_{{\lambda }}\).

Lemma 15

Let \(\phi ,\psi \in \text {Hom}_G(S_\lambda ,V)\) and \(u,u'\in S_\lambda \). Let B be the unique (up to scale), G-invariant bilinear form on \(S_\lambda \). Then, for any \(s_\lambda \in S_{\lambda }\),

Proof

Since \(M_V\) and \(\phi \otimes \psi \) are both \(\mathbb {R}\)-linear and commute with the action of G,

By substituting \(u=u'=s_\lambda \), we have

Relating \(\text {sym}(u\otimes u')\) and \(\text {sym}(s_\lambda \otimes s_\lambda )\) via Lemma 13, and using the fact that \(M_V\) and \(\phi \otimes \psi \) are both \(\mathbb {R}\)-linear, we obtain the stated result. \(\square \)

Our next aim is to describe the structure of \(\text {sym}(\mathsf {f}^2)\) for \(\mathsf {f}\in V_{\varvec{\lambda }}\).

Proposition 5

Let \(\phi _1,\phi _2,\ldots ,\phi _{m_\lambda }\) be a basis for \(\text {Hom}_{G}(S_\lambda ,V)\), let \(s_\lambda \in S_\lambda \) be non-zero, and let

for all \(j,\ell \in [m_\lambda ]\). If \(\mathsf {f}\in V_\lambda \), then there exists a \(m_\lambda \times m_\lambda \) psd matrix \(Q^\lambda \) such that

Proof

Let \(\mathsf {f}\in V_{\lambda } = \{ \phi (u): \phi \in \text {Hom}_G(S_\lambda ,V),\; u\in S_\lambda \}\). Then a straightforward argument shows that there are \(u_1,u_2,\ldots ,u_{m_\lambda }\in S_\lambda \) such that

We expand \(\text {sym}(\mathsf {f}^2)\) in terms of \(\text {sym}(\phi _i(u_i)\phi _j(u_j))\) and apply Lemma 15 to get

Since \(u\mapsto B(u,u)\) is a positive definite quadratic form and \(s_\lambda \ne 0\), if we define \(Q_{ij}^\lambda := B(u_i,u_j)/B(s_\lambda ,s_\lambda )\), we see that \(Q^\lambda \) is psd. Since \(Y_{ij}^\lambda = \text {sym}(\phi _i(s_\lambda )\phi _j(s_\lambda ))\), we have obtained an expression for \(\text {sym}(\mathsf {f}^2)\) in the required form. \(\square \)

We have seen how to symmetrize products from different isotypic components of V and how to symmetrize squares of polynomials from the same isotypic component. We can now combine these earlier arguments in a straightforward way to desribe symmetry-reduced non-negativity certificates for sos that are invariant under the action of G. This is the main result of the appendix (which is essentially the main result of [16]).

Theorem 11

Let V be a finite-dimensional G-invariant subspace of \(\mathbb {R}[{\mathsf {x}}]/\mathcal {I}\) with isotypic decomposition \(V = \bigoplus _{\lambda \in {\varLambda }} V_\lambda \) and corresponding multiplicities \(m_\lambda \). For each \(\lambda \in {\varLambda }\), fix a non-zero element \(s_\lambda \in S_\lambda \). Let \(\mathsf {b}_1,\ldots ,\mathsf {b}_{m_\lambda }\) be a basis for the subspace \(W_{s_\lambda }\). Define for each \(\lambda \in {\varLambda }\)

for \(i,j\in [m_\lambda ]\). Suppose \(\mathsf {p}\in \mathbb {R}[{\mathsf {x}}]/\mathcal {I}\) is invariant under the action of G and is V-sos. Then there exist \(m_\lambda \times m_\lambda \) psd matrices \(Q^\lambda \) such that

Proof

Fix \(\lambda \in {\varLambda }\). By Lemma 10, the map \(\phi \mapsto \phi (s_\lambda )\) gives an isomorphism between \(W_{s_\lambda }\) and \(\text {Hom}_G(S_\lambda ,V)\). Hence, for each \(i\in [m_\lambda ]\), there is \(\phi _i\in \text {Hom}_G(S_\lambda ,V)\) such that \(\mathsf {b}_i = \phi _i(s_\lambda )\). Moreover, the \(\phi _i\) for \(i\in [m_\lambda ]\) form a basis for \(\text {Hom}_G(S_\lambda ,V)\). As such,

for \(i,j\in [m_\lambda ]\). Now suppose that \(\mathsf {p}\) is G-invariant and V-sos. Then, since \(V = \bigoplus _\lambda V_\lambda \), we have that \(\mathsf {f}_k = \sum _{\lambda \in {\varLambda }} \mathsf {f}_{k\lambda }\) where each \(\mathsf {f}_{k\lambda }\in V_{\lambda }\). Hence

From Lemma 14, we have that \(\text {sym}(\mathsf {f}_{k\lambda }\mathsf {f}_{k\mu }) = 0\) whenever \(\lambda \ne \mu \). Using the fact that \(\mathsf {p}\) is fixed by the action of G,

where each \(\mathsf {f}_{k\lambda }\in V_\lambda \). Applying Proposition 5 for each \(\lambda \) and each k, we see that there exist psd matrices \(Q^{\lambda ,k}\) such that

Defining \(Q^\lambda = \sum _k Q^{\lambda ,k}\), which is again psd, gives an expression for \(\mathsf {p}\) as

as we require. \(\square \)

1.3 Specialization to Theorem 1

This specializes to give Theorem 1 as follows. Let \(q = \left( {\begin{array}{c}n\\ 2\end{array}}\right) \) and let \(\mathcal {I}_n = \langle \mathsf {x}_{ij}^2 = \mathsf {x}_{ij}\;\;1\le i<j\le n\rangle \) denote the square-free ideal in \(\mathbb {R}[{\mathsf {x}}]\). Let \(\mathbb {R}[{\mathsf {x}}]/\mathcal {I}_n = \mathbb {R}[\mathcal {V}_n]\) be the corresponding quotient of the polynomial ring. Let \(G = \mathfrak {S}_n\) and suppose that \(\mathfrak {S}_n\) acts on monomials by \(\mathfrak {s}\cdot \mathsf {x}_{ij} = \mathsf {x}_{\mathfrak {s}(i)\mathfrak {s}(j)}\). Let \(V = \mathbb {R}[\mathcal {V}_n]_{\le d}\) be the \(\mathfrak {S}_n\)-invariant subspace of square-free polynomials of degree at most d.

To relate Theorem 1 to Theorem 11, we need to show that the subspaces \(W_{\tau _{\varvec{\lambda }}}\) defined in Sect. 2.1 are isomorphic as vector spaces to \(W_s\) for some non-zero \(s\in S_{\varvec{\lambda }}\), and hence to the multiplicity space \(\text {Hom}_{\mathfrak {S}_n}(S_{\varvec{\lambda }},V)\) (via Lemma 10). The argument requires the following fact, which follows from Young’s rule (see, e.g., Theorem 9 for a statement of Young’s rule in the required form) and the fact that the diagonal Kostka numbers \(K_{\varvec{\lambda }\varvec{\lambda }}\) are one (see, e.g., [35, Example 2.11.4]).

Lemma 16

If \(\tau _{\varvec{\lambda }}\) is a tableau of shape \(\varvec{\lambda }\), then \(\dim (S_{\varvec{\lambda }}^{\mathfrak {R}_{\tau _{\varvec{\lambda }}}})=1\).

Lemma 17

Fix a standard tableau \(\tau _{\varvec{\lambda }}\) of shape \(\varvec{\lambda }\). If \(s_{\tau _{\varvec{\lambda }}}\in S_{\varvec{\lambda }}^{\mathfrak {R}_{\tau _\lambda }}\) is non-zero, then

Proof

If \(w\in W_{s_{\tau _{\varvec{\lambda }}}}\) then there is \(\phi \in \text {Hom}_{\mathfrak {S}_n}(S_{\varvec{\lambda }},V)\) such that \(\phi (s_{\tau _{\varvec{\lambda }}}) = w\). If \(\mathfrak {s}\in \mathfrak {R}_{\tau _{\varvec{\lambda }}}\) then

Hence \(W_{s_{\varvec{\lambda }}}\subseteq V_{\varvec{\lambda }}^{\mathfrak {R}_{\tau _{\varvec{\lambda }}}} = W_{\tau _{\varvec{\lambda }}}\). On the other hand, if \(w\in W_{\tau _{\varvec{\lambda }}}\), then there are \(v_1,\ldots ,v_{m_{\varvec{\lambda }}}\in S_{\varvec{\lambda }}\) and \(\phi _{1},\ldots ,\phi _{m_{\varvec{\lambda }}}\) such that \(w = \sum _{i\in [m_{\varvec{\lambda }}]} \phi _i(v_i)\in V_{\varvec{\lambda }}\) and \(w = \text {sym}_{\mathfrak {R}_{\tau _{\varvec{\lambda }}}}(w)\). Then

Since \(S_{\varvec{\lambda }}^{\mathfrak {R}_{\tau _{\varvec{\lambda }}}}\) is one-dimensional, it is spanned by \(s_{\tau _{\varvec{\lambda }}}\). Hence for any \(v_i\in S_{\varvec{\lambda }}\), we have that \(\text {sym}_{\mathfrak {R}_{\tau _{\varvec{\lambda }}}}(v_i)\) is a scalar multiple of \(s_{\tau _{\varvec{\lambda }}}\). It then follows that \(w \in W_{s_{\tau _{\varvec{\lambda }}}}\), giving the reverse inclusion. \(\square \)

Applying Theorem 11 in this setting, and choosing \(s_{\varvec{\lambda }}:= s_{\tau _{\varvec{\lambda }}}\) (defined in Lemma 17) for each \(\varvec{\lambda }\), yields the statement of Theorem 1.

Appendix 3: Ramsey number R(3, 3)

In this section, we prove the following lemma.

Lemma 18

Recall that the ideal in Sect. 5.2 was

The following fact saves us from duplicating all of our arguments.

Lemma 19

\(\mathsf {p}((\mathsf {x}_{ij})_{1\le i < j \le 6}) \in \mathcal {I}\) if and only if \(\mathsf {p}((1-\mathsf {x}_{ij})_{1\le i < j \le 6}) \in \mathcal {I}\).

Proof

This follows by exchanging the colors of the edges. This can also be observed algebraically by working with the ideal. \(\square \)

We now note that claws are in the ideal, allowing us to relate certain degree two and degree one elements of the ideal.

Lemma 20

For \(i\in [6]\), and \(j<k<l \in [6]\backslash \{i\}\),

Consequently,

Proof

Indeed, combinatorially, if \(\mathsf {x}_{ij}\mathsf {x}_{ik}\mathsf {x}_{il}\) were one for some i, j, k, l, then edges \(\{i,j\}\), \(\{i,k\}\), and \(\{i,l\}\) would be colored red. Then if we color any of \(\{j,k\}\), \(\{k,l\}\) and \(\{j,l\}\) red, we would have a red triangle spanned by that edge and vertex i, but if we color all of them blue, then we would have a blue j, k, l-triangle. We can observe the same thing symmetrically for blue edges.

Algebraically, observe that \(\mathsf {x}_{jk}\mathsf {x}_{jl}\mathsf {x}_{kl} \in \mathcal {I}\) and \((1-\mathsf {x}_{jk})(1-\mathsf {x}_{jl})(1-\mathsf {x}_{kl}) \in \mathcal {I}\) implies that

Hence

since every monomial on the right hand side contains either \(\mathsf {x}_{ij}\mathsf {x}_{ik}\mathsf {x}_{jk}\) or \(\mathsf {x}_{ij}\mathsf {x}_{il}\mathsf {x}_{jl}\) or \(\mathsf {x}_{ik}\mathsf {x}_{il}\mathsf {x}_{kl}\), each of which is in the ideal. Thus \(\mathsf {x}_{ij}\mathsf {x}_{ik}\mathsf {x}_{il} \in \mathcal {I}\). By Lemma 19, \((1-\mathsf {x}_{ij})(1-\mathsf {x}_{ik})(1-\mathsf {x}_{il}) \in \mathcal {I}\) as well.

Since \((1-\mathsf {x}_{1i})(1-\mathsf {x}_{1j})(1-\mathsf {x}_{1l}) \in \mathcal {I}\) whenever \(1<i<j<k \le 6\), we have that

Expanding the right hand side and using the fact that \(\mathsf {x}_{1i}\mathsf {x}_{1j}\mathsf {x}_{1k} \in \mathcal {I}\) whenever \(1<i<j<k \le 6\), we obtain

since all of the higher order terms must vanish. \(\square \)

Proof of Lemma 18

By Lemma 19, \(\left( 2-\sum _{2\le i \le 6} (1-\mathsf {x}_{1i})\right) ^2 \equiv 2-\sum _{2\le i \le 6} (1-\mathsf {x}_{1i})\). Therefore,

\(\square \)

For completeness, we explicitly wrote out how we used the ideal in the above sum of squares, putting the elements of the ideal in red. These calculations can be found online: http://www.math.washington.edu/~thomas/ramsey_calculations.pdf.

Reprints and permissions