Multivariable Inequalitys - The mechanisation method
As a method from《不等式的秘密》(Secrets In Inequalities)
Introduction
When I was studying Math Olympiad, I was struggling about inequalities. I know one method called Sum of Squares (SOS) that could give a good approach to a Homogeneous polynomial. But still, unavoidably the solver still have to examine Schurs, AM-GM, and some other inequalities to implement.
Although this approach is great, to some sense, its not universal. It does not approach all inequality problems in one way and solve it.
So I always wounder if such method exists. When I studied and undergrad math, I notice a method called the Method of Lagrange Multiplier. This works really well in most cases. Still, solving such a system of equations may be hard when the form of inequality is not pleasent.
For more complex inequalities, such as an inequality with three variables, Lagrange Multiplier is actually also quite a difficult approach.
So one day I watched this video introducing two methods: the differtiation method and the dual inequality method.
Yes, there two methods are still far from universal. However, from common inequality problems, these are sort of a mechanised method that allows a direct approach to problems.
It works especially well when the polynomial is symetric.
The Idea
Consider a polynomial \(f\), where
\[f(x_1,x_2,x_3,x_4,\cdots,x_n) \geq 0\]
is too be proved.
Then imagive the whole input as one variable, can we in some form, write \(f(x_1,x_2,x_3,\cdots,x_n)\) in \(f(t)\), and apply methods that solves a single variable inequality?
As this is a polynomial, solving \(f(t) \geq 0\) is much easier. One idea is that we have to differentiate and examine \(f'(t)\). After some analysis on \(f'(t)\), proving the inequality may actually be much easier.
This leads to the idea of writing the polynomial with one variable. This can similar to total derivative.
I will use three variables to illustrate how this algorithm work. However, this idea can be used on any number of variables.
\[ \frac{\text{d}f}{\text{d}t} = \frac{\partial f}{\partial x}\frac{\text{d}x}{\text{d}t} +\frac{\partial f}{\partial y}\frac{\text{d}y}{\text{d}t} + \frac{\partial f}{\partial z}\frac{\text{d}z}{\text{d}t} \]
Now we are able to conside this new variable \(t\) to deal with and treat the polynomial as a whole.
To let our df/dt satisfy better properties, here is most the essential idea of this method.
Let
\[ \frac{\text{d}x}{\text{d}t} = \frac{\text{d}y}{\text{d}t} = \frac{\text{d}z}{\text{d}t} = 1 \]
Then
\[ D(f) = \frac{\text{d}f}{\text{d}t} = \frac{\partial f}{\partial x} +\frac{\partial f}{\partial y} + \frac{\partial f}{\partial z} \]
Note that \(D(f)\) is a linear transform and follows all rules that normal differtiation follows.
And the symetry of the inequality (that is to be proved) can be used perfectly by this method.
\[D(f+g) = D(f)+D(g)\]
\[D(kf) = kD(f)\]
The Method
To prove \(f \geq 0\) where \(x,y,z\geq 0\), do the following:
Step 1. Show \(f \geq 0 \iff xyz = 0\)
Step 2. Show \(D(f) \geq 0\)
Why?
First, this method in many occasions work when than the Lagrange multiplier method. The reason is that Step 1 is very easy if the inequality is symetric.
Step 2 is actually also quite easy. The reason is because Step 2 can be recursive. I.E: \(f \geq 0 \iff D(f) \iff 0 \iff D(D(f)) \geq 0\).
Prove?
For
\[f(x,y,z)\]
WLOG, assume \(z\) to be the smallest.
Then, consider
\[ g(t) = f((x-z)+t,(y-z)+t,(z-z)+t)\]
\[ \frac{\text{d}g}{\text{d}t} = \frac{\partial f}{\partial(x-z+t)} +\frac{\partial f}{\partial y(y-z+t)} + \frac{\partial f}{\partial (z-z+t)}\]
\[ \frac{\text{d}f}{\text{d}t} = \frac{\partial f}{\partial (x-z+t)} \frac{d(x-z+t)}{dt}+\frac{\partial f}{\partial (y-z+t)} \frac{d(y-z+t)}{dt}+\frac{\partial f}{\partial (z-z+t)} \frac{d (z-z+t)}{d t}\]
\[ \frac{\text{d}f}{\text{d}t} = \frac{\partial f}{\partial (x-z+t)}+\frac{\partial f}{\partial (y-z+t)}+\frac{\partial f}{\partial (z-z+t)} = \frac{\text{d}g}{\text{d}t}\]
\[ g'(t) = D(f) \]
Then
\[ g(u) \geq g(0) , u \in \{ x,y,z\}\]
Hence
\[f(x,y,z)\geq f(x-z,y-z,0) \geq 0 \]
Example
I will only use this method. (Like L-Hospital)
Schur's
\[x^3+y^3+z^3 +3xyz \geq x^2y + x^2 z+ y^2z + y^2x + z^2x + z^2y\]
Step 1
\[ x^3+y^3 \geq x^2y+y^2x\]
Step 1.1 (END)
\[ x^3 \geq 0\]
Step 1.2 \[ 3x^2+3y^2 \geq x^2 + y^2 + 4xy\]
Step 1.2.1 (END) \[ 3x^2 \geq x^2\]
Step 1.2.2 (END) \[ D(3x^2+3y^2) \geq D(x^2 + y^2 + 4xy)\]
\[ 6x+6y \geq 6x+6y\]
Step 2 \[D(x^3+y^3+z^3 +3xyz) \geq D(x^2y + x^2 z+ y^2z + y^2x + z^2x + z^2y)\]
\[ 3\sum_{sym}x^2 + 3\sum_{cyc} xy \geq 2\sum_{sym} x^2 + 4\sum_{cyc} xy\]
\[ \sum_{sym}x^2 \geq \sum_{cyc} xy\]
\[ x^2+y^2+z^2 \geq xy+yz+xz\]
Step 2.1
\[ x^2+y^2 \geq xy\]
Step 2.1.1 (END)
\[x^2 \geq 0\]
Step 2.1.2 (END)
\[ D(x^2+y^2) \geq D(xy)\]
\[ 2x+2y \geq 2x+2y\]
Step 2.2 (END)
\[ D(x^2+y^2+z^2) \geq D(xy+yz+xz)\]
\[ 2x+2y+2z \geq 2x+2y+2z\]
Summary
Just apply it mechanically if the equation is symetric. If not, I will cover it in the next article.
This is a detailed notes of the following video. Really like this method because I really stuck on inequalities.
https://www.bilibili.com/video/BV1rT411h7ej/