A "Physical Proof" of Symmetric Polynomial Inequalities

对称多项式不等式的“物理证明” 苏剑林 · 2011-08-13 · Mathematics inequality IMO symmetry polynomial

This post touches on the topic of symmetry again, but this time the subject isn't an "identity" but an "inequality."

In mathematical research, we often come across all kinds of functional expressions, quite a few of which are "symmetric." What is a symmetric function? There are many ways to describe symmetry, but for multivariate symmetric expressions, we define it as a function satisfying $f(x_1,x_2,...,x_n)=f(y_1,y_2,...,y_n)$, where $(y_1,y_2,...,y_n)$ is any permutation of $(x_1,x_2,...,x_n)$. In plain terms, if you swap any two of the unknowns in the expression, you get back the same expression as before. For example, take $\sin x+\sin y$: swapping $x,y$ gives $\sin y+\sin x$, which is the same as the original; or take $xy+yz+zx$: swapping y and z gives $xz+zy+yx$, again the same as the original expression; and so on. Some symmetric functions are polynomials of degree n, in which case we call them degree-n symmetric polynomials — the example $xz+zy+yx$ above is a three-variable, degree-2 symmetric polynomial.more

What's the benefit of symmetry?

BoJone has already mentioned in earlier posts that "symmetry" helps us find solutions more easily to begin with — for instance, in symmetric physical systems it is easier to find first integrals, and Noether's theorem also tells us that the symmetry of a physical system corresponds to a conservation law. Of course, these statements are all quite abstract, and only once you've studied theoretical physics will you get a deeper feel for them. So, what can symmetry do for us here? Let's look at just one example: polynomial expansion.

Suppose we want to expand $(a+b+c)^3$. Besides grinding through it step by step with the four basic operations, there's another approach: the method of undetermined coefficients, which is also the method used in computer-algebra proofs. We know that the expansion of $(a+b+c)^3$ must contain the three terms $a^3,b^3,c^3$, and since $(a+b+c)^3$ is a symmetric expression — in other words, $a,b,c$ all hold equivalent "status" — the expansion of $(a+b+c)^3$ must contain a part of the form $\lambda_1 (a^3+b^3+c^3)$. Next, we can reason that the expansion of $(a+b+c)^3$ must contain the term $a^2 b$, along with the five other terms $a^2 c,b^2 a, b^2 c, c^2 a, c^2 b$. Rather than fixating on the specific $a,b,c$ letters in these terms, we should recognize their underlying structure: each is the square of one unknown times another unknown, so all six terms have equivalent status, meaning the expansion of $(a+b+c)^3$ must contain $\lambda_2 (a^2 b+a^2 c+b^2 a+b^2 c+c^2 a+c^2 b)$. The last term is $\lambda_3 abc$, and so we get:

$$\begin{equation}\begin{aligned}&(a+b+c)^3 \\ =&\,\lambda_1 (a^3+b^3+c^3)+\lambda_2 (a^2 b+a^2 c+b^2 a+b^2 c+c^2 a+c^2 b)+\lambda_3 abc\end{aligned}\end{equation}$$

To find out what $\lambda_1,\lambda_2,\lambda_3$ actually is, we just need to plug in three sets of numbers, which gives us a system of three linear equations in three unknowns. Imagine, if $a,b,c$ were not symmetric, we would have had to assign an unknown coefficient to every single term above (ten in total), then substitute specific values, ending up with a system of ten linear equations in ten unknowns. So you can see how symmetry greatly reduces the amount of computation. In fact, there are many more benefits of symmetry — why not read on?

Symmetric inequalities

In preparing for an upcoming math competition, BoJone dug fairly deeply into inequality proofs, especially symmetric inequalities of degree $n$. We found that proofs of symmetric inequalities come up quite often in math competitions. For example, given nonnegative numbers $x,y,z$ satisfying $x+y+z=1$, the 1984 IMO asked us to prove

$$\begin{equation}0 \leq xy+yz+zx-2xyz \leq \frac{7}{27}\end{equation}$$

A similar problem appeared in last year's Guangdong Province preliminary mathematical olympiad, asking us to prove:

$$\begin{equation}9xyz \leq xy+yz+zx \leq \frac{1}{4} (1+9xyz)\end{equation}$$

In the 41st IMO, given that xyz = 1, we were asked to prove

$$\begin{equation}\left(x-1+\frac{1}{y}\right)\left(y-1+\frac{1}{z}\right)\left(z-1+\frac{1}{x}\right) \leq 1\end{equation}$$

And there are similar ones like

$$\begin{equation}\frac{1}{\sqrt{1+8x}}+\frac{1}{\sqrt{1+8y}}+\frac{1}{\sqrt{1+8z}} \geq 1\end{equation}$$

Simpler examples include the familiar mean inequality $x^3+y^3+z^3-3xyz \geq 0$, and so on. There are plenty more examples, too many to list one by one. Below I'll introduce a "physical proof" for inequalities. Generally speaking, it isn't a particularly elegant method of proof — one might even call it an "ugly proof" — but it is effective in a great many situations.

Unifying dimensions

Let's now treat all the unknowns as quantities with the dimension of length, and all constants as dimensionless quantities. In mathematics we often see expressions like $a-1$, but in physics such a thing could never appear, because it would mean subtracting a dimensionless quantity from a quantity with dimensions — which doesn't make sense. And if we look back at some of the examples above, such as $4(xy+yz+zx)-9xyz \leq 1$, the left-hand side is "a sum of squares of lengths minus a cube of length," while the right-hand side is dimensionless — this clearly doesn't hold up. So we need to "unify the dimensions." How do we do that? Using the given condition $x+y+z=1$, let

$$\begin{equation}\left\{\begin{aligned} x=\frac{a}{a+b+c}\\y=\frac{b}{a+b+c}\\ z=\frac{c}{a+b+c} \end{aligned}\right.\qquad(a,b,c\text{is any positive number})\end{equation}$$

Substituting this in, we get:

$$\begin{equation}4(a+b+c)(ab+bc+ca)-9abc \leq (a+b+c)^3\end{equation}$$

Now we need to prove that this holds for arbitrary $a,b,c$, and we can see that every term here now has the dimension of length cubed.

What if the given condition is instead $xyz=1$? Then we could let $x=\frac{a}{b},y=\frac{b}{c},z=\frac{c}{a}$ or $x=\frac{a^2}{bc},y=\frac{b^2}{ac},z=\frac{c^2}{ab}$, and so on. When proving inequalities, "unifying the dimensions" is often a useful step, even though it may not be strictly necessary or the simplest approach.

Breaking the symmetry

This is the heart of this post! The reason symmetric systems have relatively simple solution methods is that we have an "ultimate weapon": transforming a symmetric system into an asymmetric one often simplifies the problem. Remember how we originally solved quadratic equations? Given $xy=p,x+y=q$, this is a symmetric system; by letting $x=a+b,y=a-b$, it becomes the asymmetric $a^2-b^2=p,2a=q$ — the problem doesn't get more complicated, it actually becomes easier to solve. There's an analogous trick for inequalities.

For instance, suppose we want to prove $4(a+b+c)(ab+bc+ca)-9abc \leq (a+b+c)^3$, where $a,b,c$ have equivalent status. We break that equivalence: without loss of generality, let $ a \geq b \geq c$. To further highlight the inequality of status among the three, we can set

$$\begin{equation}b=c+u,a=b+v=c+u+v\end{equation}$$

where $u,v$ are all non-negative.

Substituting this into $(a+b+c)^3-4(a+b+c)(ab+bc+ca)+9abc$, what do we get? Expanding, we obtain:

$$\begin{equation}\begin{aligned}(3c+2u+v)^3 \\ -4(3c+2u+v)[(c+u+v)(c+u)+(c+u)c+(c+u+v)c] \\ +9(c+u+v)(c+u)c \\ =v^3+2uv^2+cv^2+cuv+cu^2\end{aligned}\end{equation}$$

As you can see, every term is non-negative, so the inequality holds. Here we've expanded an asymmetric polynomial, and the process turns out to be quite tedious — as I've already stressed, this will never be a beautiful method of proof.

Let's take another example: to prove $a^3+b^3+c^3-3abc \geq 0$, we need to expand

$(c+u+v)^3+(c+u)^3+c^3-3(c+u+v)(c+u)c$, giving

$$\begin{equation}3 c u^2+3 c u v+3 c v^2+2 u^3+3 u^2 v+3 u v^2+v^3\end{equation}$$

This expression is clearly non-negative, so the inequality holds.

Closing notes

This post is a record of BoJone's exploration of inequalities. Of course, none of this is anything new — I'm simply jotting it down here in the hope that it will be useful to others. I've used some physics terminology to frame the discussion, partly because BoJone himself is a physics enthusiast, and partly because I feel that physics and mathematics are fundamentally intertwined — using physics to understand mathematics can sometimes produce beautifully elegant results! ^_^ Of course, this post only scratches the surface of proving inequalities, and since the computation involved can get quite heavy, it's at best a kind of "machine proof." For higher-degree cases, the computational cost becomes enormous, making this approach impractical.