How do we prove $x^2+2x+1 \geq 0$ by sum of squares(SOS)? Quite trivial $\text{LHS} = (x+1)^2 \geq 0$

Then, how to prove this by SOS?

Note that

What happened behind the scenes? How does mathematica get a monster like that?

Background

This problem stems back from Hilbert’s 17th problem which asks

Can a positive definite rational function always be expressed as a sum of squares of finitely many rational functions?

The answer to the problem is yes and it was proved by Emil Artin in 1927 using formally real fields. The question here is a bit different because we are asking whether it can be expressed as a sum of squares of polynomials(instead of rational functions). It is a pity that the answer is no for general cases. Motzkin polynomial $M(x,y) = x^4 y ^2 + x^2 y^4 -3x^2y^2 + 1 $ is an counterexample because

$(x^4 y ^2 + x^2 y^4 + 1)/3 \geq \sqrt[3]{x^4 y ^2 x^2 y^4 1}=x^2y^2$ but you cannot write it as a sum of squares of polynomials(have it a try by undetermined coefficients).

But we can prove that some useful conclusions hold for polynomials in one variable with rational coefficients.

Existence of Polynomial SOS for Semidefinite Univariate Polynomials

Prop 1. Positive semidefinite univariate polynomial $f(x)$ of degree $2n$ with rational coefficients can always be expressed as a sum of squares of polynomials.

Proof. According to the fundamental theorem of algebra, $f(x)$ can be factored as

where $c,r_i,a_j,b_j\in \mathbb{Q}$ and $c, b_j>0$. Note that a sum of squares multiplied by a sum of squares is still a sum of squares. $\quad \blacksquare$

Prop 2. A univariate polynomial $ f(x) $ of degree $ 2n $ is nonnegative if and only if there exists a positive semidefinite \((n+1) \times (n+1)\) matrix \( A \) such that \( u^T A u = f(x) \), where \( u = [1, x, x^2, \cdots, x^n]^T \). That is, there exists a positive semidefinite \((n+1) \times (n+1)\) matrix \( A \) satisfying

where \( k = 0, 1, \cdots, 2n \), and \( a_k \) denotes the coefficient of \( x^k \).

Hint: Use the last prop.

Similarly, it follows that

Prop 3. A univariate polynomial $ f(x) $ of degree $ 2n $ is positive definite if and only if there exists a positive definite \((n+1) \times (n+1)\) matrix \( A \) such that \( u^T A u = f(x) \), where \( u = [1, x, x^2, \cdots, x^n]^T \). That is, there exists a positive definite \((n+1) \times (n+1)\) matrix \( A \) satisfying

where \( k = 0, 1, \cdots, 2n \), and \( a_k \) denotes the coefficient of \( x^k \).

Algorithm

First Attempt

From Prop 2, we have converted the problem to the existence of a semidefinite matrix $A$ satisfying some linear constraints. This can be translated to a semidefinite programming problem. The goal is zero since we only care about the feasible set.

But it is also reasonable to use $tr(A)$ as the objective function preventing the entries of $A$ from being too large.

There are a lot of methods to solve this semidefinite optimization problem. Only the simplest one is demonstrated here. Making $A = B^T B$ ensures $A\succeq 0$. Then minimize the following relaxed objective using gradient descent

where the first term $\mu\sum B_{ij}^2 $ is a regularization initially set to $μ =0$ and gradually increased to promote small entries in $B$.

Then we get a numerical matrix $A$. Rationalize all the entries of $A$ with sufficient accuracy. (You may want to try continued fractions to achieve the best rational approximation with as small numerators and denominators as possible.)

At this moment, $\sum_k(\sum_{\substack{i+j=k+2\\i,j\geq1}} A_{ij} -a_k)^2$ is a small number but is not necessarily $0$. But we can expect $A$ is still semidefinite after nudging some elements a little bit in $A$ to satisfy the linear constraints. (A loophole here. We will fix it in the next subsection.) At present, $A$ is a semidefinite matrix with rational entries and satisfies those linear constraints. Let $A=CC^T$ be the Cholesky decomposition where $C$ is a lower triangular matrix. Then the entries in $C^T u$ give the terms for polynomial SOS. But $C$ is not necessarily a rational matrix.

It only leaves to prove that every column of $C$ is in the same quadratic field, that is, for any $k=1,2,\cdots,n+1$, there exists $p_k\in\mathbb{N}_+$ such that $C_{1k},C_{2k}, \cdots,C_{n+1,k}\in \mathbb{Z} [\sqrt{p_k}]$. If this holds, the SOS can be written as

Every coefficient in it is rational.

So let’s prove this. Well, it is quite obvious from the following example, right?

Second Attempt

Remember the loophole in the last subsection? Nudging entries of a positive semidefinite can possibly make the matrix non-positive semidefinite because strictly semidefiniteness is a property on the boundary – a little distribution shall make the eigenvalue of the matrix change from 0 to a negative value. Our method in the last subsection may fail when the input polynomial is $x^2-2x+1$. What makes it worse is, numerical calculation has trouble finding $(x-1)^2$ as the SOS for $x^2 - 2x + 1$ because the feasible solution $A$ has to be precisely $ \begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix} $ which is quite impossible for a floating point type in programming. (e.g. 0.1 + 0.2 != 0.3 in cpp)

All in all, we prefer positive definiteness over positive semidefiniteness in computational optimization. Fortunately, the following prop helps us wipe out semidefinite situations.

Prop 4. If $f(x)\in\mathbb{Q}[x]$ is a positive semidefinite polynomial, then $f(x)$ can be factored as $g^2(x)h(x)$ where $g,h\in\mathbb{Q} [x]$ and $h(x)$ is positive definite.

Proof. We’ll prove it by induction for the degree $2n$ of $f(x)$. If $n=0$, it is trivial. If we have proved the prop for $n=k-1$, let’s prove it for $n=k$. If $f(x)$ has no real root, it must be positive definite, the prop proved. If $f(x)$ has real root $\alpha$, the multiplicity of $\alpha$ must be an even number $2t$. Denote the minimal polynomial of $\alpha$ as $p(x)$. Suppose $f(x) = p^m(x)q(x)$ where $p \nmid q$. It is apparent $m \leq 2t$.

If $m\lt 2t$, the $m$th derivative of $f(x)$ has a root of $\alpha$ since the multiplicity is $2t-1\geq m$. On the other hand,

among which the terms for $k=0,1,\cdots,m-1$ have a factor of $p(x)$. Thus, $0 = f^{(m)}(\alpha) = m![p'(\alpha)]^mq(\alpha)$ while $p\nmid m![p']^mq$, leading to a contradiction. Therefore $m=2t$.

$f(x)/p^{2t}(x)$ is positive semidefinite. Thus $f(x)/p^{2t}(x)$ can be expressed as $u^2 v$ where $u,v\in\mathbb{Q}[x]$ and $v$ is positive definite. The proof is finished by $f = (p^t u)^2 v$. $\quad \blacksquare$.

In algorithm, we can first decomposite the function $f(x)$ in $\mathbb{Q}[x]$ to get $p$ and $q$(check [this wiki page](https: //en.wikipedia.org/wiki/Factorization_of_polynomials) for more methods). Then find the polynomial SOS for $q$. Finally, combine $p,q$ together.

Final Algorithm

(Modified from text generated by Deepseek)

Input:
A polynomial \( f(x) \in \mathbb{Q}[x] \) that is positive semidefinite (i.e., \( f(x) \geq 0 \) for all \( x \in \mathbb{R} \)).

Output:
A rational sum-of-squares (SOS) decomposition of \( f(x) \), expressed as:

where \( g_i(x) \in \mathbb{Q}[x] \) and \( p_i \in \mathbb{Q}_+ \).

Steps:

1. Factorization Step (Prop 4):

   • Factor \( f(x) \) as \( f(x) = g^2(x) h(x) \), where:
     • \( g(x) \in \mathbb{Q}[x] \) captures all repeated roots (if any),
     • \( h(x) \in \mathbb{Q}[x] \) is positive definite (i.e., \( h(x) > 0 \) for all \( x \in \mathbb{R} \)).
   • Method:
     • Compute the square-free factorization of \( f(x) \) (e.g., using Yun’s algorithm).
     • Extract \( g(x) \) as the product of all repeated irreducible factors (with even exponents).
     • The remaining part \( h(x) = f(x)/g^2(x) \) will have no repeated roots and be positive definite.

2. Semidefinite Programming (SDP) for \( h(x) \) (First Attempt):

   • Represent \( h(x) \) in the basis \( \{1, x, x^2, \dots, x^n\} \).

   • Formulate the SDP problem:

     \[ \begin{align*} \text{Minimize} \quad & \text{tr}(A), \\ \text{s.t.} \quad & \sum_{\substack{i+j=k+2 \\ i,j \geq 1}} A_{ij} = a_k \quad \text{(coefficient matching)}, \\ & A \succeq 0 \quad \text{(positive semidefinite constraint)}. \end{align*} \]

   • Relaxed Optimization:

     • Parameterize \( A = B^T B \) to ensure \( A \succeq 0 \).

     • Solve using gradient descent on the relaxed objective:

       \[ \mu \sum B_{ij}^2 + \sum_k \left( \sum_{\substack{i+j=k+2 \\ i,j \geq 1}} A_{ij} - a_k \right)^2, \]

       where \( \mu \) is gradually increased to regularize \( B \).

     • Rationalize the entries of \( A \) (e.g., using continued fractions).

     • Nudge the entries to satisfy the linear constraints of constraint matching.

3. Cholesky Decomposition:

   • Compute the Cholesky decomposition \( A = CC^T \), where \( C \) is lower triangular.

   • Key Insight: Each column of \( C \) lies in a quadratic field \( \mathbb{Q}[\sqrt{p_k}] \).

   • Construct the SOS terms:

     \[ h(x) = \sum_{k=1}^{n+1} p_k \left( \sum_{j=1}^{n+1} \frac{C_{jk}}{\sqrt{p_k}} x^{j-1} \right)^2. \]

     All coefficients are rational.

4. Combine Results:

   • Multiply back by \( g^2(x) \) to obtain the final SOS decomposition for \( f(x) \):

     \[ f(x) = g^2(x) \sum_{k} p_k \left( g_k(x) \right)^2. \]

Appendix

The code to generate the monstrous formula in mathematica at the beginning is as follows.

f[x_] := 
  1024 x^12 + 1024 x^11 - 2304 x^10 - 2304 x^9 + 1856 x^8 + 
   1856 x^7 - 672 x^6 - 688 x^5 + 96 x^4 + 120 x^3 + x^2 - 8 x + 21;
makeMonicAndExtractLC[polys_List, var_] := 
 Module[{lcList, monicPolys}, 
  lcList = Coefficient[#, var, Exponent[#, var]] & /@ polys;
  monicPolys = MapThread[#1/#2 &, {polys, lcList}];
  {monicPolys, lcList}]
{monicPolys, lcList} = 
  makeMonicAndExtractLC[PolynomialSumOfSquaresList[f[x], x], x];
lcList^2*(monicPolys // Expand)^2 // Total

The minimum of this polynomial is very close to zero. It is about $0.000506148$ when $x \approx 0.936309$