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[3]{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.

1 Answer

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