# Ways to prove an inequality

It seems that there are three basic ways to prove an inequality eg $x>0$.

1. Show that x is a sum of squares.
2. Use an entropy argument. (Entropy always increases)
3. Convexity.

Are there other means?

Edit: I was looking for something fundamental. For instance Lagrange multipliers reduce to convexity. I have not read Steele's book, but is there a way to prove monotonicity that doesn't reduce to entropy? And what is the meaning of positivity?

Also, I would not consider the bootstraping method, normalization to change additive to multiplicative inequalities, and changing equalities to inequalities as methods to prove inequalities. These method only change the form of the inequality, replacing the original inequality by an (or a class of) equivalent ones. Further, the proof of the equivalence follows elementarily from the definition of real numbers.

As for proofs of fundamental theorem of algebra, the question again is, what do they reduce too? These arguments are high level concepts mainly involving arithmetic, topology or geometry, but what do they reduce to at the level of the inequality?

Further edit: Perhaps I was looking too narrowly at first. Thank you to all contributions for opening to my eyes to the myriad possibilities of proving and interpreting inequalities in other contexts!!

-
How would you call bootstrapping arguments where, for example, to prove $A\le B$ you show $A\le B+\epsilon$ for all $\epsilon$? Or (what Tao refers to as the tensor product trick) you show that for all $n$, $A^n\le CB^n$ for some constant $C$ independent of $n$? –  Andres Caicedo Jul 7 '10 at 15:27

I don't think your question is a mathematical one, for the question about what do all inequalities eventually reduce to has a simple answer: axioms. I interpret it as a metamathematical question and still I believe the closest answer is the suggestion above about using everything you know.

An inequality is a fairly general mathematical term, which can be attributed to any comparison. One example is complexity hierarchies where you compare which of two problems has the highest complexity, can be solved faster etc. Another one is studying convergence of series, that is comparing a quantity and infinity, here you find Tauberian theory etc. Even though you did not specify in your question which kind of inequalities are you interested in primarily, I am assuming that you are talking about comparing two functions of several real/complex variables. I would be surprised if there is a list of exclusive methods that inequalities of this sort follow from. It is my impression that there is a plethora of theorems/principles/tricks available and the proof of an inequality is usually a combination of some of these. I will list a few things that come to my mind when I'm trying to prove an inequality, I hope it helps a bit.

First I try to see if the inequality will follow from an equality. That is to recognize the terms in your expression as part of some identity you are already familiar with. I disagree with you when you say this shouldn't be counted as a method to prove inequalities. Say you want to prove that $A\geq B$, and you can prove $A=B+C^2$, then, sure, the inequality follows from using "squares are nonnegative", but most of the time it is the identity that proves to be the hardest step. Here's an example, given reals $a_1,a_2,\dots, a_n$, you want to prove that $$\sum_{i,j=1}^n \frac{a_ia_j}{1+|i-j|} \geq 0.$$ After you realize that sum is just equal to $$\frac{1}{2\pi}\cdot\int_{0}^{2\pi}{\int_{0}^{1}{\frac{1-r^{2}}{1-2r\cos(x)+r^{2}}\cdot |\sum_{k=1}^{n}{a_{k}e^{-ikx}}|^{2}dx dr}}$$ then, yes, everything is obvious, but spotting the equality is clearly the nontrivial step in the proof.

In some instances it might be helpful to think about combinatorics, probability, algebra or geometry. Is the quantity $x$ enumerating objects you are familiar with, the probability of an event, the dimension of a vector space, or the area/volume of a region? There is plenty of inequalities that follow this way. Think of Littlewood-Richardson coeficients for example.

Another helpful factor is symmetry. Is your inequality invariant under permuting some of its variables? While I don't remember right now the paper, Polya has an article where he talks about the "principle of nonsufficient reason", which basically boils down to the strategy that if your function is symmetric enough, then so are it's extremal points (there is no sufficient reason to expect assymetry in the maximal/minimal points, is how he puts it). This is similar in vein to using Langrange multipliers. Note however that sometimes it is the oposite of this that comes in handy. Schur's inequality, for example is known to be impossible to prove using "symmetric methods", one must break the symmetry by assuming an arbitrary ordering on the variables. (I think it was sent by Schur to Hardy as an example of a symmetric polynomial inequality that doesn't follow from Muirhead's theorem, see below.)

Majorization theory is yet another powerful tool. The best reference that comes to mind is Marshall and Olkin's book "Inequalities: Theory of Majorization and Its Applications". This is related to what you call convexity and some other notions. Note that there is a lot of literature devoted to inequalities involving "almost convex" functions, where a weaker notion than convexity is usually used. Also note the concepts of Schur-convexity, quasiconvexity, pseudoconvexity etc. One of the simplest applications of majorization theory is Muirhead's inequality which generalizes already a lot of classical inequalities and inequalities such as the ones that appear in competitions.

Sometimes you might want to take advantage of the duality between discrete and continuous. So depending on which tools you have at your disposal you may choose to prove, say the inequality $$\sum_{n=1}^{\infty}\left(\frac{a_1+\cdots+a_n}{n}\right)^p\le \left(\frac{p}{p-1}\right)^p \sum_{n=1}^{\infty}a_n^p$$ or it's continuous/integral version $$\int_{0}^{\infty}\left(\frac{1}{x}\int_0^x f(t)dt\right)^p dx \le \left(\frac{p}{p-1}\right)^p \int_{0}^{\infty} f(x)^p dx$$ I've found this useful in different occasions (in both directions).

Other things that come to mind but that I'm too lazy to describe are "integration preserves positivity", uncertainity principle, using the mean value theorem to reduce the number of variables etc. What also comes in handy, sometimes, is searching if others have considered your inequality before. This might prevent you from spending too much time on an inequality like $$\sum_{d|n}d \le H_n+e^{H_n}\log H_n$$ where $H_n=\sum_{k=1}^n \frac{1}{k}$.

-
Minor comment about your first example, it is "easily" seen to be nonnegative, because it is the sum of all entries of the positive-definite matrix: $B = aa^T \circ L$, where $L_{ij} = 1/(1+|i-j|)$ and $\circ$ denotes the Hadamard product. The only semi-trivial part is to prove posdef of $L$, but that can be done in numerous ways, the more advanced of which might use an integral representation. –  Suvrit Sep 28 '10 at 7:47
How would you prove the posdef of L? –  Gjergji Zaimi Sep 28 '10 at 19:20
Hmm, the first idea that comes to my mind is: use $\varphi(x) = 1/(1+|x|)$ is a positive-definite function (it is in fact infinitely divisible), which itself can be proved using $|x|$ is conditionally negative-def. (though proving the latter might require a simple integral!); –  Suvrit Oct 1 '10 at 13:00

Enumerative combinatorics also provides an important source of inequalities. The most basic is that if you can show that $X$ is the cardinality (or dimension) of some set $A$, then you automatically have $X \geq 0$. This can become non-trivial if one also possesses a very different description of $X$, e.g. as an alternating sum. Similarly, if you can establish a surjection (resp. injection) from a set of cardinality (or dimension) $X$ to a set of cardinality (or dimension) $Y$, then you have proven that $X \geq Y$ (resp. $X \leq Y$). (The dimension version of this argument is the basis for the polynomial method in extremal combinatorics.)

The integrality gap is also an important way to improve an inequality by exploiting discreteness. For instance, if you know that $X > Y$, and that $X, Y$ are integers, then this automatically implies the improvement $X \geq Y+1$. More generally, if you know that $X, Y$ are both divisible by $q$, then we have the further improvement $X \geq Y+q$. A good example of this principle is in applying the Chevalley-Warning theorem, that asserts that the number $X$ of roots of a low-degree polynomial over a finite field $F_p$ is divisible by $p$. If one has one trivial solution ($X \geq 1$), then this automatically boosts to $X \geq p$, which implies the existence of at least one non-trivial solution also (and in fact gives at least $p-1$ such solutions).

-
There's a real equivalent to the enumerative combinatorics method of showing that the quantity counts something. This would be: show that the quantity represents some probability. Then it's automatically non-negative (and in fact, it's between 0 and 1, so you get two inequalities) –  Peter Shor Jul 8 '10 at 15:07

Steele in his book Cauchy-Schwarz Master Class identifies three pillars on which all inequalities rest

1. Monotonicity
2. Positivity
3. Convexity, which he says is a second-order effect (Chap 6)

These three principles apply to inequalities whether they be

1. discrete or integral or differential
3. in simple or multi-dimensional spaces (matrix inequalities).

In Chap 13 of the book, he shows how majorization and Schur's convexity unify the understanding of multifarious inequalities.

I am still not done reading the book but it also mentions a normalization method which can convert an additive inequality to a multiplicative one.

-
Steele's book should be required reading for all mathematics students regardless of level. One of the reasons calculus classes are in such a sorry state in this country is the complete inability of students to work with basic inequalities. I know it was definitely my main weakness when beginning to learn real analysis. –  Andrew L Jul 7 '10 at 16:48
@Andrew L : Can you please tone down the relentless negativity? I'd assume that by "this country" you mean the US (somehow I can't imagine a resident of Canada, Germany, China, etc assuming that everyone was from there). Calculus classes in the US are hardly "in a sorry state". Many people that post here both live in the US and teach calculus on a regular basis. I don't see why you have to insult us. –  Andy Putman Jul 7 '10 at 20:29

To prove that $A\leq B$, maximize the value of $A$ subject to the condition that $B$ is constant using, for example, Lagrange multipliers. This does wonders on most classical inequalities.

-
there is an argument that such a maximization (so called fastest descend) is actually a heat flow or entropy argument. Just from what I heard. –  Colin Tan Jul 7 '10 at 15:07
I have no idea what 'heat flow' or 'entropy argument' mean in this context. Lagrange multipliers, on the other hand, are known to every undergraduate... –  Mariano Suárez-Alvarez Jul 7 '10 at 15:11
Mariano: Yes, but the question is not about how to effectively teach inequalities to undergraduates, but about the tools we have to prove them. And most classical inequalities can be deduced from sum of squares arguments, or some form of convexity results. I actually think this question shows a nice insight. –  Andres Caicedo Jul 7 '10 at 15:30
Well, most classical inequalities also follow more or less effortlessly from a little, straightforward, idealess computation using Lagrange multipliers, too. That is my point. –  Mariano Suárez-Alvarez Jul 7 '10 at 15:32
I agree with your point (not the "idealess" part). I am reading "convexity arguments" loosely, so that inequalities proved using first (and sometimes second) derivative arguments are included here. In that sense, Lagrange multipliers is part of that framework. –  Andres Caicedo Jul 7 '10 at 16:59

I don't think the question has a meaningful answer unless the OP specifies a class of inequalities he has in mind. The problem is that almost any mathematical statement can be restated as an inequality.

Take, for instance, the fundamental theorem of algebra. It is equivalent to the inequality
"the number of roots of a non-constant polynomial with complex coefficients is greater than zero". Over ten different proofs of this inequality are discussed in this thread. It seems that none of them has anything to do with positivity, convexity or entropy arguments.

-
You're right; but given the question, I think we can infer that the OP means inequalities of the form $A\leq B$ where $A$ and $B$ are functions of (possibly several) real variables written in some fixed language, e.g. $(\times, +, -, \operatorname{sin}, ...)$. –  Daniel Litt Jul 7 '10 at 15:47
Daniel, probably you are right. Still I think it would help if the question were a bit more specific. –  Andrey Rekalo Jul 7 '10 at 16:17

This doesn't seem like a real question, but here's an answer anyway. Every mathematician should pick up "Inequalities" by Hardy, Littlewood, and Polya. The book lays out a systematic approach to proving "elementary" inequalities, and it was a surprise to me just how much commonness and beauty there is in the field. It's an old book, but all the more readable for it.

-

I have recently been working on stuff related to the Golod-Shafarevich inequality. So here is a crazy way to prove an inequality. Let $G$ be a finitely generated group and $\left< X|R \right>$ a presentation of $G$ with $|X|$ finite. Let $r_i$ be the number of elements in $R$ with degree $i$ with respect to the Zassenhaus $p$-filtration. Assume $r_i$ is finite for all $i$. Let $H_R(t)=\sum_{i=1}r_it^i$.

A group is called Golod -Shafarevich (GS) if there is $0 < t_0 < 1$ such that $1-|X|t_0+H_R(t_0)<0$. Golod and Shafarevich proved that GS groups are infinite. Zelmanov proved their pro-$p$ completion contains a non-abelian free pro-$p$ group.

So suppose $G$ is a group with such a presentation and suppose you know that its pro-$p$ completion does not contain a non-abelian free pro-$p$ group or for some other reason $G$ is not GS. Then $1-|X|t+H_R(t) \geq 0$ for all $0 < t <1$.

Now, I am sure no one ever used the Golod-Shafarevich this way and I doubt anyone will. But maybe I am wrong. In any case, this does not seem to fit any of the methods that were mentioned before.

-
+1 the answer is really cute. But shouldn't one of your inequalities have an equal sign appended? The negation of $<$ is $\geq$, not $>$. –  Willie Wong Jul 8 '10 at 20:09
Thanks! I fixed it. –  Yiftach Barnea Jul 8 '10 at 22:00

Look at the proofs of known inequalities and solutions to related problems:

http://en.wikipedia.org/wiki/Category:Inequalities

http://mathworld.wolfram.com/topics/Inequalities.html

I believe the best approach to studying inequalities is proving as many of them as possible. There is a section at ArtOfProblemSolving forum that is a good source of them:

http://www.artofproblemsolving.com/Forum/viewforum.php?f=32

One may also like to read a classic book on inequalities by Hardy, Littlewood, and Pólya:

http://www.amazon.com/gp/product/0521358809

-
There's also this somewhat underdeveloped Tricki page: tricki.org/article/Techniques_for_proving_inequalities –  Mark Meckes Jul 7 '10 at 16:45
There's also Wikipedia's article titled "list of inequalities", which, unlike the category, is organized. en.wikipedia.org/wiki/List_of_inequalities –  Michael Hardy Jul 7 '10 at 21:59

Use other known inequalities. e.g. re-arrangement inequality, Cauchy-Schwartz, Jensen, Hölder.

-
There is a mild generalization of this technique: use everything you know! :) –  Mariano Suárez-Alvarez Jul 7 '10 at 15:12
But aren't these inequalities fundamentally a result of either convexity or sum of squares? –  Colin Tan Jul 7 '10 at 15:20