Can any polynomial in $\Bbb R [x]$ be written as the difference of two sum-of-squares polynomials in $\Bbb R [x]$?

Question

Let $f \in \Bbb R[x_1,\dots,x_n]$ be an arbitrary polynomial, not necessarily non-negative. Are there always two sum-of-squares (SOS) polynomials $g, h \in \Bbb R[x_1,\dots,x_n]$ such that $f=g-h$?

If so, to what extent will $\max\{\deg(g),\deg(h)\}$ increase, compared to $\deg(f)$? Linearly? Polynomially? Exponentially?

Answer 1

I claim that any $f(x_1,...,x_n)$ polynomial is a difference $g-h$ where $g,h$ are sums of square polynomials. To see this let $S$ be the set of all polys that can be written in this form. Note that

(1) For each $f\in S$, $c f\in S$ for all $c\in\Bbb R$.

(2) For $f_1,f_2\in S$, $f_1+f_2\in S$.

(3) For $f_1,f_2\in S$, $f_1f_2\in S$.

(1) and (2) are obvious. To see (3), let $f_1=g_1-h_1$ and $f_2=g_2-h_2$, $g_i,h_i$ are SOS. Then $$f_1f_2=(g_1g_2+h_1h_2)-(g_1h_2+g_2h_1).$$ But $g_1g_2,h_1h_2,g_1h_2,g_2h_1$ are SOS.

But $1=1^2-0^2$, $x_i=(x_i+1/4)^2-(x_i-1/4)^2$. So $S$ is generated by $1,x_1,x_2,...,x_n$. Therefore $S$ is the whole $\Bbb R[x_1,...,x_n]$. We can easily see that if $\deg f=d$ then we can take $g,h$ to have degrees $\le 2d$.

In fact you can also see that $x_i^{2k}=(x_i^k)^2-0^2$ and $x_i^{2k+1}=(x_i^k(x_i+1/4))^2-(x_i^k(x_i-1/4))^2$. So you can take $g,h$ to have degrees $\le$ the minimum of $2d$ and $d+n$.

This answer is possible because of Arthur's comment.

Answer 2

First fix some index $i\in[n]$. For even $k\in\mathbb{N}$, $x_i^{k}$ is already an SOS. For odd $k\in\mathbb{N}$, $x_i^{k} = (x_i^{k}+1)^2/4 - (x_i^{k}-1)^2/4$.

Now fix some monomial $x_1^{d_1} \cdots x_n^{d_n}$. For each $i\in[n]$, $x_i^{d_i} = g_i-h_i$ where $g_i,h_i$ are SOS and $\max\{\deg(g_i),\deg(h_i)\} \leq 2d_i$. Thus, $$ \prod_{i\in[n]} x_i^{d_i} = \prod_{i\in[n]}(g_i-h_i)$$ which is a difference of two SOS and the degree of RHS is at most $2(d_1+\cdots+d_n)$.

Answer 3

Actually there is a much simpler way to see this, which uses the hint from Arthur:

Let $f \in \mathbb{R}[x_1,...,x_n]$ be a real, $n$-variate polynomial. Then let $g := (f+1/4)^2$ and $h := (f-1/4)^2$. Clearly both $g$ and $h$ are sum of squares. But \begin{align} f = (f+1/4)^2 - (f-1/4)^2 = g - h. \end{align} So $f$ is the difference of two sum of squares polynomials.

And so the $\max \{ \text{deg}(g),\text{deg}(h) \} $ is twice $\text{deg}(f)$.