Polynomials as sum of squares

Question

Sometimes I have seen some math's competition problem solutions made by completing the expression as sum of squares. What is the intuition/computer program behind these solutions? For example,

Prove that for all $x\in\mathbb{R}$ we have $x^8-x^7+x^2-x+15>0.$

Proof. We have that $$x^8-x^7+x^2-x+15=\frac{(128x^4-64x^3-16x^2-8x-9)^2+4(16x^2-11x+121)^2+60(x-49)^2+43055}{2^{14}}>0.$$

Answer 1

This is probably because of following theorem on positive polynomials.

Every real polynomial $p(x)$ in one variable is non-negative over $\mathbb{R}$, i.e.

$$p(x) \ge 0 \quad\text{ for all } x \in \mathbb{R}$$ if and only if it is a sum of two squares of real polynomials.

Please note that the corresponding statement is false for polynomials in two or more variables. e.g. the Motzkin polynomial

$$ x^4y^2 + x^2y^4 - 3x^2y^2 + 1$$

is non-negative over $\mathbb{R}^2$ and yet it cannot be expressed as a sum of two real polynomials.

The question whether any non-negative real polynomials in $n > 1$ variables can be expressed as a sum of squares of real rational functions is the famous Hilbert's seventeen problem. Follow the wiki links for more details and inspirations.