# Decomposition of symmetric homogeneous polynomials

Can every symmetric polynomial of degree $r$ in $d$ variables that has no constant term be written as a sum of the $r$th powers of linear polynomials in $d$ variables and a homogeneous polynomial of degree $r$ each of whose terms involves at most $d−1$ variables?

The linear polynomials are truly linear functions: e.g. $p(x) = w^T x,$ so have no constant terms. And the field is $\mathbb{R}.$

As an example, this is true for degree two polynomials, because you can show that given an arbitrary $A$, there exists a nonnegative matrix $B$ and a diagonal matrix $D$ such that the quadratic forms corresponding to $A$ and $B+D$ are identical.

• Please elaborate more, as it seems that your question is ambiguous or misstated. For $r=2$ and base field $\mathbb{R}$, an $r$-th power of a linear polynomial always has nonnegative constant term (provided that your notion of a "linear polynomial" allows constant terms to begin with), so a polynomial like $x^2+x+y^2+y$ cannot be obtained in this way. – darij grinberg Sep 16 '14 at 1:31
• Thanks for asking for the clarification. I have done so: the linear polynomials do not have constant terms, and the field is R. – AatG Sep 16 '14 at 21:50
• Still, for $x^2+y^2+x+y$ it is impossible: $x$ and $y$ cannot appear in neither of your summands since all of them are homogeneous of degree $2$. – Ilya Bogdanov Sep 16 '14 at 22:49
• Maybe you just want the original polynomial to be homogeneous? – darij grinberg Sep 16 '14 at 23:18
• Even assuming that the polynomial $P$ is homogeneous, at least for even $r$ the statement can't be true. If it were true ,one could iterate , and eventually write $P$ as a sum of r-powers without remainder (thus getting $P\ge0$) – Pietro Majer Sep 17 '14 at 7:43

This is true if $r$ is odd or $r<2d$, and false otherwise. I assume, when you say a polynomial is symmetric you mean in fact it is homogeneous.

1. Let $r=2d$ and take $P(x)=-x_1^2x_2^2\dots x_d^2$. The term $x_1^2\dots x_d^2$ appears in every $r$th power of a linear form with a nonnegative coefficient, so their sum plus monomials in $d-1$ variables cannot get a negative coefficient at $x_1^2\dots x_d^2$. A similar reasoning works for all even $r\geq 2d$.

2. Now assume that $r$ is odd or $r<2d$. In the former case we will even show that each appropriate polynomial is even a sum of $r$th powers.

Firstly, notice that $$(-1)^rr!y_1y_2\dots y_r=\sum_{I\subset\{1,\dots,r\}}(-1)^{|I|} \left(\sum_{i\in I}y_i\right)^r.$$ So the monomial $y_1\dots y_r$ is a linear combination of $r$th powers. By substitution, the same holds for every $r$th degree monomial in $x_1,\dots,x_d$. So the linear hull of all $r$th powers is the whole space of all homogeneous polynomials of degree $d$.

Let $S^{d-1}$ be a unit sphere in $\mathbb R^d$, and let $\mu$ be the usual measure on it. If $r$ is odd, then $$\int_{S^{d-1}}(a^Tx)^r\,d\mu(a)=0,$$ so $0$ lies in the convex hull of all the polynomials $(a^Tx)^r$. By Caratheodory's theorem, $0$ is a finite convex combination of some of them, and (due to symmetry of the sphere) each $r$th power is involved in some such combination. This yields that $0$ lies in the (relative) interior of the cone generated by $r$th powers, so this cone is the whole space. This is exactly what we claimed.

(Some time ago I was told that this Caratheodory trick appeared in a paper by Milman and someone else; sorry for not presenting the exact reference.)

If $r$ is even but $r<2d$, then the same integral is a nonzero polynomial $Q$, but it contains only monomials of even degree in each variable; so it is a linear combination of monomials in at most $d-1$ variables (and it is invariant under sphere rotations). Then the same arguments can be applied to the factor space by $\langle Q\rangle$. We will represent each polynomial as a sum of $r$th powers plus a multiple of $Q$, which is again what we need.

• "Someone else" is most likely Krein – Alvin Sep 18 '14 at 12:59
• Great! I like the Caratheodory trick. I asked this question to understand two different models for polynomial interpolation in machine learning. I'm writing a paper that I plan to submit to a conference, so space is tight, but I would love to include this argument with attribution to you as its source if possible. Do I have your permission to do so? – AatG Sep 18 '14 at 21:29
• @Alvin: What I am almost sure about is it was not Krein, otherwise I would remember it. Alex: I think the only interesting part is that trick attributed surely not to myself, so it would be better to perform some search... – Ilya Bogdanov Sep 18 '14 at 22:11