# Polynomial identity in positive terms, including AM-GM bound

Consider $n$ nonnegative numbers $x_1 \cdots x_n$. An easy consequence of the AM-GM inequality $$\frac{x_1 + x_2 + \cdots + x_n}{n} \geq \sqrt[n]{x_1 x_2 \cdots x_n}$$ is a lower bound on a polynomial $$(x_1 + x_2 + \cdots + x_n)^n \geq n^n (x_1 x_2 \cdots x_n)$$ which holds with equality iff $x_1 = x_2 = \cdots = x_n$.

Question 1 (existence):
Can one write the LHS polynomial as an identity which is a sum of only nonnegative terms, including the RHS? These terms can again be composites (other than the considered difference LHS - RHS itself), if it can be guaranteed that they are nonnegative.

Question 2 ($n=4$):
What's a formula for $n=4$?

Question 3 (general $n$):
Is there a principle for composing a formula for general $n$?

First solutions / remarks:

Here are ways of doing that for $n=2$: $$(x + y)^2 = 4 x y + (x - y)^2$$ and $n=3$: $$(x+y+z)^3 = 27 x y z + (x^3 + y^3 + z^3 - 3 x y z) + 3 (z-y)^2 x + 3 (x-z)^2 y+ 3 (y-x)^2 z$$ where the second term (in brackets) is nonnegative again by AM-GM: $(x^3 + y^3 + z^3)/3 \geq \sqrt{x^3 y^3 z^3} = x y z$.

Remark:
The obvious advantage of such a procedure would be that one could determine lower bounds of the LHS by any term on the RHS or weighted sum of terms on the RHS, with weights between 0 and 1. In particular, these lower bounds could be chosen according to prior knowledge: if all $x_i$ are known to be roughly equal, the AM-GM bound is a good one. If the $x_i$ are known to differ much, one would choose other terms on the RHS as lower bound.

Yes, we can.

We can do it by Bricks Throwing Method.

It's very ugly but it works.

For four variables we need to work with $(a+b+c+d)^4-256abcd$.

$3(a^4+b^4+c^4+d^4)\geq\sum\limits_{cyc}a^3(b+c+d)$ because we throw one brick:

$\sum\limits_{cyc}(3a^4-a^3(b+c+d))=\frac{1}{2}\sum\limits_{sym}(a^4-a^3b-ab^3+b^4)=\frac{1}{2}\sum\limits_{sym}(a-b)^2(a^2+ab+b^2)$.

More brick trowing:

$\sum\limits_{cyc}a^3(b+c+d)\geq\frac{1}{2}\sum\limits_{sym}a^2b^2$ gives

$\sum\limits_{cyc}a^3(b+c+d)-\frac{1}{2}\sum\limits_{sym}a^2b^2=\frac{1}{2}\sum\limits_{sym}(a^3b-2a^2b^2+ab^3)=\frac{1}{2}\sum\limits_{sym}ab(a-b)^2$ and so on...

I'll write a full proof.

More brick trowing:

$\frac{1}{2}\sum\limits_{sym}a^2b^2-\sum\limits_{cyc}a^2(bc+bd+cd)=\frac{1}{2}\sum\limits_{sym}(a-b)^2(c^2+d^2)$

The last brick trowing:

$\sum\limits_{cyc}a^2(bc+bd+cd)-12abcd=\frac{1}{4}\sum\limits_{sym}(a-b)^2cd$.

After using these bricks throwing we'll write $(a+b+c+d)^4-256abcd$ like a sum of squares.

• Pardon my ignorance, but what is "Bricks Throwing Method"? – Martin R Jul 3 '16 at 17:50
• @Martin R see my proof. I wrote a full proof for you. – Michael Rozenberg Jul 3 '16 at 18:09
• @Michael: some reference to "Brick Throwing" would still be appreciated. – Andreas Jul 3 '16 at 18:28
• @Andreas it's just $(4,0,0)\succ(3,1,0)\succ(2,2,0)\succ(2,1,1)\succ(1,1,1,1)$, where all $\succ$ gives sum of squares. See my proof. The general is the same! – Michael Rozenberg Jul 3 '16 at 19:09
• @Michael: ok I see it. Still I wonder where the term "brick throwing" is used or did you invent it? -- btw an inequality where the OP says that you pointed out it's still unsolved has been solved recently at math.stackexchange.com/questions/1444352 – Andreas Jul 3 '16 at 20:49