# 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{align*} a^2+b^2-2ab &\;=\;(a-b)^2\;\geqslant\;0\,, \\[2ex] a^3+b^3+c^3-3abc &\;=\;(a+b+c)\cdot\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 &\;=\;\left(a^2-b^2\right)^2 +\left(c^2-d^2\right)^2 + 2(ab-cd)^2\;\geqslant\;0\,, \end{align*} and for $\,n=5\,$ cf this math.SE answer.

Now fix some $n\in\mathbb{N}$, let $\,a_1,a_2,\cdots,a_n\geqslant 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 readings:
(1) 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
(2) Computing sum of squares decompositions with rational coefficients
by Helfried Peyrl and Pablo A. Parrilo, Theor. Comp. Sci. 409 (2008), pp 269-281

• The cases $n=2$ and $n=3$ look pretty different to me. It would be easier to extrapolate a guess with more examples. – Joonas Ilmavirta Apr 21 '17 at 5:52
• Maybe you could follow the Cauchy induction proof to get an expression for $n=2^k$ and then in general? – stewbasic Apr 21 '17 at 6:00
• Do you have any specific reason for being convinced? Consider the case $n=5$. A sum of squares (of homogeneous terms) will give even powers only and hence you won't get terms in $a^5$. You would have to take out a linear factor first as you have done for $n=3$. Unfortunately, the expression with $n=5$ doesn't have any linear factors, at any rate not according to Maple. So, sorry to sound negative - and maybe someone else can think of some smart idea that I've missed - but it seems to me that this method is unlikely to work. – David Apr 21 '17 at 6:02
• The keyword here is 'positivity certificate', which you can probably google and read about. I found these slides when doing so. – Pedro Tamaroff Aug 2 '17 at 5:08
• @PedroTamaroff Your comment is a smash hit: It pathed me the way to a short certificate in the 4-variable case; cf the edit. – Hanno Aug 15 '17 at 14:51

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$.
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.
• Even not grasping it in full, you convinced me that the transformation into an SOS expression is always possible, in principle $\,\Rightarrow$ Upvote & thanks for that! The resulting expressions rapidly getting monstrous doesn't come as a surprise, SOS then acqires its well-known standard meaning ;-) – Hanno Apr 21 '17 at 17:17