1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – darij grinberg Sep 16 '14 at 1:31
  • $\begingroup$ Thanks for asking for the clarification. I have done so: the linear polynomials do not have constant terms, and the field is R. $\endgroup$ – AatG Sep 16 '14 at 21:50
  • $\begingroup$ 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$. $\endgroup$ – Ilya Bogdanov Sep 16 '14 at 22:49
  • 1
    $\begingroup$ Maybe you just want the original polynomial to be homogeneous? $\endgroup$ – darij grinberg Sep 16 '14 at 23:18
  • $\begingroup$ 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$) $\endgroup$ – Pietro Majer Sep 17 '14 at 7:43
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Someone else" is most likely Krein $\endgroup$ – Alvin Sep 18 '14 at 12:59
  • $\begingroup$ 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? $\endgroup$ – AatG Sep 18 '14 at 21:29
  • $\begingroup$ @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... $\endgroup$ – Ilya Bogdanov Sep 18 '14 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.