41
$\begingroup$

After seeing the question Important formulas in combinatorics, I thought it might be of interest to have a similar list of inequalities, although not restricted to combinatorics. As with that list, there should be some rules. 

  1. The inequality should not be too well known. This is to rule out things like Cauchy-Schwarz or the Sobolev inequalities. The inequality should be unfamiliar to a majority of mathematicians. 
  2. The inequality should represent research level mathematics. This is taken straight from the other list, and feels like a good rule. 
  3. The inequality should be important.  Since it is easier to come up with inequalities versus exact formulas, this should be more restrictive than in the other list. The idea is to have inequalities which played an important role in the development of some field.
  4. An answer can be a class of inequalities. As noted in the comments, often what is important is a family of inequalities which all convey the same idea but where no single result is the fundamental example. This is perfectly acceptable, and perhaps even encouraged since any such examples will likely have lots of applications.

To give an idea of what I mean, let me give an example which I think satisfies the first three criteria; the Li-Yau estimate.

The Li-Yau inequality is the estimate $$ \Delta \ln u \geq - \frac{ n}{ 2t}.$$

Here $u: M \times \mathbb{R} \to \mathbb{R}^+ $ is a non-negative solution to the heat equation $ \frac{\partial u}{\partial t} = \Delta u, $ $(M^n,g)$ is a compact Riemannian manifold with non-negative Ricci curvature and $\Delta$ is the Laplace-Beltrami operator.

This inequality plays a very important role in geometric analysis. It provides a differential Harnack inequality to solutions to the heat equation, which integrates out to the standard Harnack estimate. There are many results strengthening the original inequality or adapting it to a different setting. There are also results which are not generalizations of the original inequality but which bear its influence. For instance, Hamilton proved a tensor version of the Li-Yau inequality for a manifold which has non-negative sectional curvature and evolves by Ricci flow. Furthermore, one of Perelman's important breakthroughs was to prove a version of the Hamilton-Li-Yau inequality for a solution to time-reversed heat flow when the metric evolves by Ricci flow. These results are not at all corollaries of the original Li-Yau estimate, but they are similar in spirit. 

$\endgroup$
  • 9
    $\begingroup$ Often in analysis it is a class of inequalities that is important, rather than a specific inequality from that class. For instance, the class of concentration of measure inequalities (Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid, Levy, Talagrand, etc.) is extremely important in modern probability, combinatorics, random matrix theory, high dimensional geometry, and theoretical computer science, but I wouldn't single out a single inequality in this class as being particularly pivotal. $\endgroup$ – Terry Tao Jun 19 at 22:11
  • $\begingroup$ Thanks for the remark. Concentration of measure is definitely the sort of thing I had in mind when I asked this question, so I'll edit the question to allow for classes of inequalities. $\endgroup$ – Gabe K Jun 19 at 22:37
  • 1
    $\begingroup$ @GabeK the Li-Yau inequality would be an example of all four criteria, not just the first three, wouldn't it? From scalar equations to Ricci flow and mean curvature flow, and also including the original Yau and Cheng-Yau gradient estimates in the elliptic setting $\endgroup$ – Quarto Bendir Jun 20 at 4:55
  • 2
    $\begingroup$ @kodlu That only works for answers, not questions. Making a question community wiki requires a moderator. $\endgroup$ – Rand al'Thor Jun 20 at 8:57
  • 2
    $\begingroup$ @kodlu, I believe that users can no longer make their questions CW, and must flag for moderator attention. I have done so. $\endgroup$ – LSpice Jun 20 at 15:53

11 Answers 11

26
$\begingroup$

The class of concentration of measure inequalities is a fundamental tool in modern probability (and any field that uses probability, e.g., random matrix theory, theoretical computer science, statistics, high-dimensional geometry, combinatorics, etc.). As explained in this blog post of Scott Aaronson, these are basic ways in which one "upper bounds the probability of something bad", and often the bounds are exponential or even gaussian in nature when one is far away from the mean (or median) and there are many independent (or somewhat independent) variables involved. Examples of such inequalities include

Log-Sobolev inequalites are, strictly speaking, not concentration of measure inequalities, but are often closely related to them, thanks to techniques such as the Herbst argument.

A standard reference in the subject for these topics is

Ledoux, Michel, The concentration of measure phenomenon, Mathematical Surveys and Monographs. 89. Providence, RI: American Mathematical Society (AMS). x, 181 p. (2001). ZBL0995.60002.

I also have a blog post on this topic here.

$\endgroup$
  • $\begingroup$ These are certainly very important inequalities! Would you describe them all as "unfamiliar to the majority of mathematicians"? Anyone who has done a masters level probability or theoretical statistics course is going to know the Chernoff and Azuma inequalities -- even an undergraduate course I attended did Chernoff and McDiarmid (aka bounded differences). Maybe as a young probabilist myself I am not in a good place to judge how well-known these are, though! $\endgroup$ – Sam T Jun 20 at 14:27
  • $\begingroup$ If I may add a suggestion to McDiarmid's inequality, which can be found in his survey On the Method of Bounded Differences, various authors have considered 'typical' bounded differences (as opposed to worst-case). See, for example, On the Method of Typical Bounded Differences [cont...] $\endgroup$ – Sam T Jun 20 at 14:43
  • $\begingroup$ [...cont] Various people who desire these bounded difference inequalities may not be aware of such 'typical' bounded difference inequalities where the bounds do not hold for all points in the space, but only for 'typical' ones, in some precise manner $\endgroup$ – Sam T Jun 20 at 14:44
  • $\begingroup$ Some individual inequalities in this class (e.g., the Chernoff inequality) may be fairly well known, but my sense is that the broader concentration of measure phenomenon (in particular, its applicability to nonlinear (but still Lipschitz or convex) functions of independent variables) is not widely known outside of the fields of mathematics that rely heavily on probability. $\endgroup$ – Terry Tao Jun 21 at 1:12
  • 1
    $\begingroup$ The DKW inequality on deviation of an empirical CDF from the ground truth is a very nice one. $\endgroup$ – usul Jun 21 at 4:31
16
$\begingroup$

Gaussian Jensen's inequality:

Let $\boldsymbol{X}=(X_{1}, \ldots, X_{n})\sim \mathcal{N}(\boldsymbol{\mu}, \boldsymbol\Sigma)$ be a gaussian vector. The inequality $$ \mathbb{E} B(f_{1}(X_{1}), \ldots, f_{n}(X_{n})) \leq B(\mathbb{E}f_{1}(X_{1}), \ldots, \mathbb{E}f_{n}(X_{n})) $$ holds for all real valued (test functions) $f_{1}, \ldots, f_{n}$ if and only if $\mathrm{Hess}\, B\, \bullet \boldsymbol{\Sigma} \leq 0$.

Remarks: here $\bullet$ denotes Hadamard product; $B : \Omega \subset \mathbb{R}^{n} \to \mathbb{R}$ is a smooth function given on a rectangular domain $\Omega = J_{1}\times\ldots \times J_{n}$ for some intervals (rays, real line) $J_{k}$, and test functions map $f_{k} :\mathbb{R} \to J_{k}$. Inequality $\mathrm{Hess}\, B(s)\, \bullet \boldsymbol{\Sigma} \leq 0$ is required to hold for all $s \in \Omega$ and it means that the matrix is negative semidefinite.

Applications: (the list is far from complete!)

  • Prekopa--Leindler.
  • Ehrhard inequality - this might be not well-known. It is sharp analog of Brunn--Minkowski for Gaussian measure which implies Gaussian isoperimetric inequality
  • Hypercontractivity for the Ornstein--Uhlenbeck semigroup.
  • Brascamp--Lieb inequality (including Young's conviolution inequality etc). There is a very nasty limit passage from Gaussian to Lebesgue case.
  • Gaussian noise stability (it is better to google it).

How to think about this inequality:

If $X_{1}, ..., X_{n}$ are independent then $\mathrm{Hess}\, B\, \bullet \boldsymbol{\Sigma} \leq 0$ simply means that $B$ is separately concave. If $X_{1}=X_{2}=...=X_{n}$ then $\mathrm{Hess}\, B\, \bullet \boldsymbol{\Sigma} \leq 0$ is just concavity of $B$. The inequality improves on classical Jensen's inequality because $\mathrm{Hess} B \leq 0 \Rightarrow \mathrm{Hess}\, B\, \bullet \boldsymbol{\Sigma} \leq 0$ for any covariance matrix $\boldsymbol{\Sigma}$. If $\boldsymbol{X}$ is a random vector (with smooth density and different than Gaussian) then the "infinitesimal condition" $\mathrm{Hess}\, B\, \bullet \boldsymbol{\Sigma} \leq 0$ is always necessary for the "Jensen's inequality" but not always sufficient. So Gaussian vector is somehow universal.

$\endgroup$
6
$\begingroup$

This is from Garding.

Let $P\in{\mathbb R}[X_1,\ldots,X_d]$ be a homogeneous polynomial. Assume that it is hyperbolic in some direction $e\in{\mathbb R}^d$ (with say the normalisation $P(e)=1$) and let $\Gamma$ be its cone of future, that is the connected component of $e$ in the complement of $\{P=0\}$. It is known that $\Gamma$ is convex. Then we have the inverse Hölder inequality: for every $v_1,\ldots,v_n\in\Gamma$, $$M(v_1,\ldots,v_n)\ge(P(v_1)\cdots P(v_n))^{\frac1n},$$ where $M$ is the symmetric multiplinear form such taht $M(x,\ldots,x)=P(x)$.

Consequences occur in convex geometry, combinatorics, PDEs, ...

As a matter of fact, $P^{\frac1n}$ is concave over $\Gamma$. A simple example is that of quadratic forms of signature $(1,d-1)$. Another nice example is $P=\det$, where ${\mathbb R}^d={\bf M}_n({\mathbb R})$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very interesting. Is there a reference for further reading? $\endgroup$ – Vadim Ogranovich Jun 22 at 19:14
  • 1
    $\begingroup$ @VadimOgranovich. Well, there is the original paper by Garding in Acta Math., circa 1960. Otherwise, there are plenty of articles about hyperbolic polynomials. Still an active subject. I wrote a paper in Chinese Annals of Maths B (2009) DOI 10.1007/s11401-009-0169-3 . $\endgroup$ – Denis Serre Jun 22 at 19:31
6
$\begingroup$

Strichartz estimates, which originated from

Strichartz, Robert S., Restrictions of Fourier transforms to quadratic surfaces and decay of solutions of wave equations, Duke Math. J. 44, 705-714 (1977). ZBL0372.35001,

are a family of inequalities that provide $L^p$ (or Sobolev) type control of solutions of linear dispersive or wave equations (such as the Schrodinger equation) in terms of the size of the initial data (usually measured in some sort of $L^2$-based Sobolev norm) as well as an inhomogeneous forcing term (also usually measured in some sort of $L^p$ or Sobolev norm). Through perturbative techniques (e.g., the contraction mapping theorem), Strichartz estimates can often be extended to nonlinear dispersive or wave equations, at least if the data and forcing term is small and/or one is working locally in time instead of globally. As such, Strichartz estimates form the backbone of modern local well-posedness theory for such equations, and often also play an important role in the global theory (e.g., scattering theory, or blowup analysis) of these equations. As a very crude measure of their impact, MathSciNet reports over a thousand papers devoted to the topic of Strichartz estimates. Very roughly speaking, Strichartz estimates are to dispersive and wave equations as Sobolev estimates are to elliptic equations.

Morawetz inequalities, which originated from the work of Cathleen Morawetz, and in particular

Morawetz, C. S., Time decay for the nonlinear Klein-Gordon equation, Proc. R. Soc. Lond., Ser. A 306, 291-296 (1968). ZBL0157.41502.

give global control of $L^p$ type on nonlinear dispersive or wave equations, and are usually proved using integration by parts arguments. In contrast to Strichartz estimates, they are often global in time and work in non-perturbative situations; on the other hand, they tend to be more restricted in the range of $L^p$ type quantities that can be controlled, and are also senstive to the focusing or defocusing nature of the nonlinearity. (The closest elliptic analogue to Morawetz inequalities would be Pohozaev type identities. There are also a useful variant of Morawetz inequalities known as viriel identities.)

Much of the modern global theory of nonlinear dispersive and wave equations (particularly for "critical" choices of exponents) relies heavily on a intricate combination of both Strichartz estimates and Morawetz inequalities (as well as other tools, such as conservation laws, Littlewood-Paley theory, and concentration compactness methods). See for instance my book on the subject.

$\endgroup$
  • $\begingroup$ Thanks for this excellent answer. It's interesting how the fundamental tools for hyperbolic equations versus elliptic/parabolic equations are so different. It really illustrates how different they are. $\endgroup$ – Gabe K Jun 21 at 7:13
5
$\begingroup$

I came across this inequality on the Gaussian space recently. I was not aware of its existence since it is not really a classical one in comparison to the Poincaré inequality or the Logarithmic Sobolev inequality but it seems to be useful in order to prove the analyticity of the Ornstein-Uhlenbeck semigroup in $L^p(\gamma)$. Let $\gamma$ be the standard Gaussian measure on $\mathbb{R}^d$. Let $p \in (1,+\infty)$, let $f\in \mathcal{S}(\mathbb{R}^d)$ and let $k \in \{1, \dots, d\}$. Then, \begin{align*} \|x_kf\|_{L^p(\gamma)} \leq C_{p,d} \left(\|f\|_{L^p(\gamma)}+\|\partial_k(f)\|_{L^p(\gamma)}\right), \end{align*} where $C_{p,d}>0$ only depending on $d$ and on $p$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Another inequality which has not been mentioned but which is very useful is the Carbery-Wright inequality which gives anti-concentration bound for polynomials of Gaussian random variables. $\endgroup$ – user69642 Jun 23 at 16:11
  • $\begingroup$ Do you happen to have a reference with applications to analyticity of the OU semigroup? $\endgroup$ – Paata Ivanishvili Jun 23 at 17:01
  • 1
    $\begingroup$ It is well hidden. Lemma 2.3 of this paper: sciencedirect.com/science/article/pii/S0022123602939789. Regarding the analyticity, it follows from Bismut formula together with this inequality. $\endgroup$ – user69642 Jun 23 at 17:11
4
$\begingroup$

Esseen's anti concentration inequality is the basis of a lot of relatively recent (past 10-15 years) work on non asymptotic random matrix theory, particularly results on the smallest singular values of many random matrix models. It states that if $Y$ is a real valued random variable, then $$\sup_{t \in \mathbb{R}} \mathbb{P}(|Y-t| \le 1)\le \int_{-2}^2 |\phi_Y(\theta)| \ d \theta $$ where $\phi_Y$ is the characteristic function of $Y$. It is mainly used to derive 'small ball' probability estimates where you want to control the dot product of a vector with another random vector. For a reference, see the excellent notes by Mark Rudelson here.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

A really simple but powerful inequality is the so-called improved Kato inequality. I first learned about it when I was studying Uhlenbeck's removable singularity theorem for self-dual Yang-Mills connections. However, when I explained the inequality to Duong Phong and Eli Stein in Phong's office, Stein reacted with "It's in my book! It's in my book!"

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

The expander Chernoff bound is a particularly nice generalization of the Chernoff inequality that is not so well known. It states the following: Let $G = (V,E)$ be a regular graph and consider a function $f : V \rightarrow [0,1]$. Perform a random walk $v_1, \cdots, v_t$ on $G$ by first picking $v_1$ uniformly at random. Then $$ \mathbb{P}\left(\frac{1}t \sum_{i=1}^t f(v_i) \ge \mathbb{E}f + \epsilon + \lambda \right) \le e^{-\Omega(\epsilon^2 t)}$$ where $\lambda$ is the spectral gap of $G$.

Heuristically, this inequality is roughly stating that the random variables $f(v_i)$ satisfy a Chernoff like tail bound even though they are not independent! The major application of this inequality is in theoretical computer science where it can be used to replace multiple trials of a randomized algorithm with a walk on an expander graph which reduces the number of random bits needed.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

I am not a professional mathematician, thus feel free (you or your colleagues/professors of the site) tell me if my answer doesn't fit with your requirements that I can to delete it.

An important inequality in complex analysis and functional analysis is the statement of Hadamard three-lines theorem, see the section Statement from this link of the Wikipedia with title Hadamard three-lines theorem, also I add as a comment other inequality that I like, unrelated to my answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I tried do specializations for the nice Young inequality of the article Takayuki Furuta, The Hölder-McCarthy and the Young Inequalities Are Equivalent for Hilbert Space Operators, The American Mathematical Monthly, Vol. 108, No. 1 (Jan., 2001), pp. 68-69. One can to do the specialization $\lambda=1/n$ and after multipliying the inequality by a positive sequence, let's say $|G_n|$ with $G_n$ the Gregory coefficients or for example by $\psi(n)/n^3$ with $\psi(n)$ the Deedkind psi function, one gets a resulting inequality taking the sum $\sum_{n=1}^\infty$ from both sides of the inequality. $\endgroup$ – user142929 Jun 21 at 13:52
  • 1
    $\begingroup$ The Hadamard three-lines theorem counts as "well known", in my opinion, and therefore does not fit what the question is asking for $\endgroup$ – Yemon Choi Jun 21 at 15:31
  • $\begingroup$ Many thanks @YemonChoi then if there are no more feedback in next few hours I think/agree that I should delete my answer. Also you're an excellent functional analyst, thus it makes sense (from my view) that you know it (there are few posts in MathOverflow dedicated to it). $\endgroup$ – user142929 Jun 21 at 15:37
  • $\begingroup$ I'm sorry @YemonChoi I've decided undelete the post. Many thanks for the feedback. In my opinion there are literature and lecture notes about Hadamard three-lines theorem, but I feel that this theorem isn't well-known (if I'm right there are five or six posts in this site MathOverflow for professional mathematicians about it). $\endgroup$ – user142929 Jun 23 at 8:04
1
$\begingroup$

Let $r(z)$ denotes the number of solutions in positive integers to $x+y\leq z$ with the unknown $x,y$ belonging to a set $S$ satisfying the following: the number of elements in $S$ less or equal to $x$ is asymptotically

$$N_S(x) \sim \frac{a x^b}{(\log x)^c}, \mbox{ with } 0<a, 0<b<1, \mbox{ and } c>0.$$

Then we have:

$$r(z) \sim \frac{a^2b z^{2b}}{(\log z)^{2c}}\cdot \int_0^1 (1-v)^b v^{b-1}dv = \frac{a^2b z^{2b}}{(\log z)^{2c}}\cdot \frac{\Gamma(b)\Gamma(b+1)}{\Gamma(2b+1)}$$

This covers sums of two squares and sums of two primes. It has implications about the possibility to solve Goldbach's conjecture, see the third answer in my previous MathOverflow question, here.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This very post reminds me of the infamous Waring's problem (which has a solution due to Hilbert), and two infamous inequalities namely Weyl's inequality and Hua's inequality about which I have mentioned below. $\endgroup$ – adityaguharoy Jul 19 at 12:56
1
$\begingroup$

Weyl's inequality, and Hua's inequality.

They are quite important from the viewpoint of analytic number theory.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I was interested in hearing about some number theoretic inequalities. Could you give more background in what these inequalities are and how they are used? $\endgroup$ – Gabe K Jul 19 at 0:43
  • $\begingroup$ Hi, I shall ask you to read the book titled : "Analytic methods in Diophantine equations and inequalities" authored by Harold Davenport. In chapter 3 (it may differ across different editions) you can see Weyl's inequality followed by Hua's inequality. $\endgroup$ – adityaguharoy Jul 19 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.