# SOS: Proof of the AM-GM inequality

“A basic strategy in tackling inequalities of few variables is to write things into sum of squares…” is a quote from an answer, intended as commenting the post entitled “Can this inequality proof be demystified?”.
I’d like to know what the Sum Of Squares strategy yields for the AM-GM inequality with $n$ variables.
In the low-dimensional cases $\,n=2,3,4\,$ one has
$$\begin{eqnarray} a^2+b^2-2ab\quad = &(a-b)^2\;\geqslant 0 \\[2ex] a^3+b^3+c^3-3abc\quad = &\quad(a+b+c)\:\underbrace{\frac 12\left((a-b)^2+(b-c)^2+(c-a)^2\right)}_{a^2+b^2+c^2-ab-bc-ca}\;\geqslant 0 \\[2ex] a^4+b^4+c^4+d^4-4abcd\quad = &\;\left(a^2-b^2\right)^2 +\left(c^2-d^2\right)^2 + 2(ab-cd)^2\;\geqslant 0\:, \end{eqnarray}$$
and for $\,n=5\,$ cf this math.SE answer.

Now fix some $n\in\mathbb{N}$, let $\,a_1,a_2,\ldots,a_n\geq 0$, and consider
$$\sum_{k=1}^n a_k^n\, -\, n\prod_{k=1}^n a_k\tag{AM-GM}$$
which, I’m pretty convinced, can be expressed involving Sums Of Squares and then recognised to be non-negative.

• But how does such an expression look like?
• Can it be derived in a (a sort of) uniform procedure?

There’s the post Proofs of AM-GM inequality (tagged as ‘big-list’) with 14 answers currently, but none of them would answer this question.

I’ve considered to add the ‘computer-algebra-systems’ tag.

Pedro Tamaroff introduced the central keyword Certificate of positivity in his comment which, amongst further insights, led me to rediscover the above $n=4$ expression.

$\exists$ recommended reading: An algorithm for sums of squares of real polynomials, J. Pure & Appl. Alg. 127 (1998), pp 99–104, is a nice paper by Victoria Powers and Thorsten Wörmann.

#### Solutions Collecting From Web of "SOS: Proof of the AM-GM inequality"

Yes, we can write $x_1^n+x_2^n+…+x_n^n-nx_1x_2…x_n$ in the SOS form, but I think it’s very ugly and it’s not useful for big $n$.

We can make the following.

For $n=3$:
$$a^3+b^3+c^3-3abc=\sum_{cyc}\left(a^3-\frac{1}{2}a^2b-\frac{1}{2}a^2c\right)+\sum_{cyc}\left(\frac{1}{2}a^2b+\frac{1}{2}a^2c-abc\right)=$$
$$=\frac{1}{2}\sum_{cyc}(a-b)^2(a+b)+\frac{1}{2}\sum_{cyc}c(a-b)^2=\frac{1}{2}(a+b+c)\sum_{cyc}(a-b)^2.$$

For $n=4$:
$$a^4+b^4+c^4+d^4-4abcd=\sum_{cyc}\left(a^4-\frac{1}{3}(a^3b+a^3c+a^3d)\right)+$$
$$+\frac{1}{6}\sum_{sym}(a^3b-a^2b^2)+\frac{1}{6}\sum_{sym}(a^2b^2-a^2bc)+\frac{1}{3}\sum_{cyc}(a^2bc+a^2cd+a^2bd-3abcd)=$$
$$=\frac{1}{6}\left(\sum_{sym}(a^4-a^3b)+\sum_{sym}(a^3b-a^2b^2)+\sum_{sym}(a^2b^2-a^2bc)+\sum_{sym}(a^2bc-abcd)\right)=$$
$$=\frac{1}{12}\left(\sum_{sym}(a^4-a^3b-ab^3+b^4)+\sum_{sym}(a^3b-2a^2b^2+ab^3)+\sum_{sym}(c^2a^2-2c^2ab+c^2b^2)+\sum_{sym}(a^2cd-2abcd+b^2cd)\right)=$$
$$=\frac{1}{12}\sum_{sym}(a-b)^2(a^2+b^2+c^2+2ab+cd)=$$
$$=\tfrac{(a-b)^2(2(a+b)^2+(c+d)^2)+(a-c)^2(2(a+c)^2+(b+d)^2)+(a-d)^2(2(a+d)^2+(b+c)^2)}{6}+$$
$$+\tfrac{(b-c)^2(2(b+c)^2+(a+d)^2)+(b-d)^2(2(b+d)^2+(a+c)^2)+(c-d)^2(2(c+d)^2+(a+b)^2)}{6}.$$
Here $$\sum\limits_{sym}a=6(a+b+c+d)$$ $$\sum\limits_{sym}a^2b^2=4(a^2b^2+a^2c^2+b^2c^2+a^2d^2+b^2d^2+c^2d^2),…$$
For $n=5$:
$$a^5+b^5+c^5+d^5+e^5-5abcde=\frac{1}{24}\sum_{sym}(a^5-abcde)=$$
$$=\frac{1}{24}\left(\sum_{sym}(a^5-a^4b)+\sum_{sym}(a^4b-a^3b^2)+\sum_{sym}(a^3b^2-a^3bc)\right)+$$
$$+\frac{1}{24}\left(\sum_{cyc}(a^3bc-a^2b^2c)+\sum_{sym}(a^2b^2c-a^2bcd)+\sum_{sym}(a^2bcd-abcde)\right)=$$
$$=\frac{1}{48}\left(\sum_{sym}(a^5-a^4b-ab^4+b^5)+\sum_{sym}(a^4b-a^3b^2-a^2b^3+ab^4)+\sum_{sym}(c^3a^2-2c^3ab+c^3b^2)\right)+$$
$$+\frac{1}{48}\left(\sum_{cyc}(a^3bc-2a^2b^2c+b^3ac)+\sum_{sym}(a^2c^2d-2c^2abd+b^2c^2d)+\sum_{sym}(a^2cde-2abcde+b^2cde)\right)=$$
$$=\frac{1}{48}\sum_{sym}(a-b)^2(a^3+2a^2b+2ab^2+b^3+c^3+abc+c^2d+cde).$$
The rest is the same.