Can any polynomial in $\Bbb R [x]$ be written as the difference of two sum-of-squares polynomials in $\Bbb R [x]$? 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?
 A: 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.
A: 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)$.
A: 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)$.
