There is a convergent algorithm for minimising the total variation

You need to know: Matrix, norm $||u||$ of a matrix u, convergence of sequence of matrices to a limit.

Background: For $N \times N$ matrix u with entries $u_{i,j}$ define its total variation as $J(u) = \sum\limits_{i=1}^N \sum\limits_{j=1}^N \sqrt{(u_{i+1,j}-u_{i,j})^2 + (u_{i,j+1}-u_{i,j})^2},$ where $u_{N+1,j}=u_{N,j}$ and $u_{i,N+1}=u_{i,N}$ by convention. For given $N \times N$ matrix g and $\lambda>0$ , consider optimization problem $\min\limits_u \left(\frac{||u-g||}{2\lambda}+J(u)\right)$ looking for matrix u close to g but with small total variation $J(u)$ .

The Theorem: In January 2004, Antonin Chambolle published in the Journal of Mathematical Imaging and Vision a paper in which he presented an algorithms for constructing a sequence $u_n$ of matrices which is guaranteed to converge to the optimal solution $u^*$ of this problem.

Short context: The optimisation problem described above arises in various applications including image denoising, zooming, and the computation of the mean curvature motion of interfaces. The algorithm presented in the paper is guaranteed to converge and works quite fast in practical applications.

Links: The original paper is available here.

Go to the list of all theorems

The Trudinger-Moser inequality with Sobolev norm holds for all domains in R^2

You need to know: Euclidean space ${\mathbb R}^2$ of pairs $x=(x_1, x_2)$ with norm $|x|=\sqrt{x_1^2+x_2^2}$ , differentiable function on ${\mathbb R}^2$ , its gradient $\nabla u(x)=\left(\frac{\partial u}{\partial x_1}(x), \frac{\partial u}{\partial x_2}(x) \right)$ , integral over $\Omega \subset {\mathbb R}^2$ .

Background: Let $\Omega \subset {\mathbb R}^2$ . The Sobolev norm of a differentiable function $u:\Omega \to {\mathbb R}$ is $||u||_S := \left(\int_\Omega\left(|\nabla u(x)|^2 + |u(x)|^2\right)dx\right)^{1/2}.$

The Theorem: On 25th September 2003, Berdhard Ruf submitted to the Journal of Functional Analysis a paper in which he proved the existence of constant $d > 0$ such that for any $\Omega \subset {\mathbb R}^2$ , $\sup\limits_{||u||_S\leq 1}\int_\Omega \left(e^{4\pi u^2}-1\right)dx \leq d.$

Short context: Let $\Omega \subset {\mathbb R}^2$ be bounded, and let $||u||_D := \left(\int_\Omega\left(|\nabla u(x)|^2 \right)dx\right)^{1/2}$ denote the Dirichlet norm of function $u:\Omega \to {\mathbb R}$ . In analysis, it is important to understand what is the fastest-growing function g such that $\sup\limits_{||u||_D\leq 1}\int_\Omega g(u(x)) dx < \infty$ . The answer is given by classical Trudinger-Moser inequality, stating that $\sup\limits_{||u||_D\leq 1}\int_\Omega \left(e^{\alpha u^2}-1\right) dx = c(\Omega)< \infty$ for $\alpha\leq 4\pi$ , but the supremum becomes infinite for $\alpha>4\pi$ . However, constant $c(\Omega)$ depends on the domain, grows to infinity if area of $\Omega$ grows, and becomes infinite for unbounded domains. The Theorem proves that with the Sobolev norm in place of the Dirichlet norm, the Trudinger-Moser inequality holds with constant independent of $\Omega$ , and therefore is valid for all domains, including the unbounded ones.

Links: The original paper is available here.

Go to the list of all theorems

Whitney extension theorem holds in sharp form

You need to know: Polynomials and functions on n variables, higher order partial derivatives, Lipschitz function.

Background: For a function $f:{\mathbb R}^n\to{\mathbb R}$ and vector $\beta=(\beta_1, \beta_2 \dots, \beta_n)$ of non-negative integers, denote $\partial^\beta f$ the partial derivative $\frac{\partial^{|\beta|}f}{\partial x_1^{\beta_1} \partial x_2^{\beta_2} \dots \partial x_n^{\beta_n}}$ of order $|\beta|=\beta_1 + \beta_2 + \dots + \beta_n$ . Let $C^m({\mathbb R}^n)$ denote the space of functions $f:{\mathbb R}^n\to{\mathbb R}$ whose derivatives of order $\leq m$ are continuous and bounded on ${\mathbb R}^n$ . Also, let $C^{m-1,1}({\mathbb R}^n)$ denote the space of functions whose derivatives of order $m-1$ are Lipschitz with constant 1.

The Theorem: On 14th May 2003, Charles Fefferman submitted to the Annals of Mathematics a paper in which he proved that for any integers $m\geq 1$ and $n\geq 1$ there exists an integer k, depending only on m and n, for which the following holds. Let $f:E\to{\mathbb R}$ be a function defined on an arbitrary subset $E$ of ${\mathbb R}^n$ . Suppose that, for any k distinct points $x_1,\dots, x_k \in E$ there exist polynomials $P_1,\dots, P_k$ on ${\mathbb R}^n$ of degree $m-1$ satisfying (a) $P_i(x_i)=f(x_i)$ for $i=1,\dots, k$ ; (b) $|\partial^\beta P_i(x_i)| \leq\ M$ for $i=1,\dots, k$ and $|\beta|\leq m-1$ ; and (c) $|\partial^\beta (P_i-P_j)(x_i)| \leq M|x_i-x_j|^{m-|\beta|}$ for $i,j=1,\dots, k$ and $|\beta|\leq m-1$ , where M is a constant independent of $x_1,\dots, x_k$ . Then $f$ extends to $C^{m-1,1}$ function on ${\mathbb R}^n$ .

Short context: Given a function $f:E\to{\mathbb R}$ , where E is a subset of ${\mathbb R}^n$ , how can we decide whether f extends to a $C^m({\mathbb R}^n)$ function F on ${\mathbb R}^n$ ? This is a classical question which has been answered by Whitney in 1934, and the result is known as Whitney extension theorem. The Theorem solves a version of this problem in which F is required to be $C^{m-1,1}({\mathbb R}^n)$ .

Links: The original paper is available here. See also Section 5.2 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Every separable infinite dimensional Banach space has infinite diameter

You need to know: Bijection, infimum, supremum, Banach space B, notation $\|.\|_B$ for norm in B, dimension of a Banach space, infinite-dimensional Banach space.

Background: A Banach space B is called separable if it contains a sequence $x_1, x_2,\dots, x_n,\dots$ such that for any $x \in B$ and any $\epsilon>0$ there exists an n such that $||x-x_n||_B<\epsilon$ . Banach spaces $B$ and $B'$ are isomorphic if there exist a bijection $f:B\to B'$ , which preserves addition and multiplication by constants, and constants $m>0$ and $M>0$ such that $m\|x\|_B\leq \|f(x)\|_{B'} \leq M\|x\|_B, \, \forall x\in B$ . Assuming that constants m and M are chosen to be best possible, we denote by $d_f(B,B')$ the ratio $M/m$ . Let $d(B,B')$ be the infimum of $d_f(B,B')$ over all f satisfying the conditions above. Finally, diameter $D(B)$ of the Banach space $B$ is the supremum of $d(B',B'')$ over all Banach spaces $B'$ and $B''$ isomorphic to $B$ .

The Theorem: On 23rd September 2003, William Johnson and Edward Odell submitted to the Annals of Mathematics a paper in which they proved that if B is a separable infinite-dimensional Banach space, then $D(B)=\infty$ .

Short context: In 1981, Gluskin proved the existence of constant $c>0$ such that inequality $cN \leq D(B)$ holds for every Banach space $B$ of finite dimension N (it is also known that $D(B) \leq N$ ). From this, it is natural to conjecture that if dimension N is infinite, then $D(B)$ should be infinite as well. In fact, this problem was raised by Schäffer in 1976, even before the Gluskin’s result. The Theorem resolves this problem for separable Banach spaces.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 5.6 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Littlewood conjecture holds outside of a set of Hausdorff dimension 0

You need to know: For the Theorem: logarithm, limit, notations $|x|$ for the absolute value of $x$ , ${\mathbb R}^2$ for the Euclidean plane, and $\cup$ for the set union. In addition, you need to know $\liminf$ notation, Lebesgue measure, and Hausdorff dimension to understand the context.

Background: We say set set $S\subset {\mathbb R}^2$ has box dimension $0$ if $\lim\limits_{\epsilon\to 0+}\frac{\log N_S(\epsilon)}{\log(1/\epsilon)}=0$ , where $N_S(\epsilon)$ is the minimal number of squares of side length $\epsilon$ needed to cover S.

Let $T\subset {\mathbb R}^2$ be the set of all pairs $(\alpha, \beta)$ , for which there exists an $\epsilon>0$ such that inequality $\left|\alpha-\frac{a}{c}\right|\cdot \left|\beta-\frac{b}{c}\right| \geq \frac{\epsilon}{c^3}$ holds for all integers $a, b$ and $c\neq 0$ .

The Theorem: On 5th September 2003, Manfred Einsiedler, Anatole Katok, and Elon Lindenstrauss submitted to the Annals of Mathematics a paper in which they proved that $T$ can be written as a union of sets $S_1 \cup S_2 \cup S_3 \cup \dots$ , where each $S_i$ has box dimension $0$ .

Short context: In the 1930s, Littlewood conjectured that for any two real numbers $\alpha$ and $\beta$ , $\liminf\limits_{n\to\infty} n ||n\alpha|| ||n\beta|| = 0$ , where $||x||$ denotes the distance from real number x to the nearest integer. It is easy to see that set T is exactly the set of pairs $(\alpha, \beta)$ for which this conjecture does not hold. Hence, the conjecture predicts that T is an empty set. This remains open, but it follows from the 1909 Borel theorem that T has Lebesgue measure $0$ in ${\mathbb R}^2$ . The Theorem proves much stronger result on how “small” is T. In particular, it implies that T must have Hausdorff dimension $0$ .

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 6.5 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Duality conjecture for entropy numbers is true if one of the bodies is a ball

You need to know: Euclidean space ${\mathbb R}^n$ , scalar product $\langle x,y \rangle$ in ${\mathbb R}^n$ , origin $(0,0,\dots,0)$ in ${\mathbb R}^n$ , ball in ${\mathbb R}^n$ , convex body in ${\mathbb R}^n$ , translate of a convex body by a vector.

Background: We say that convex body $K \subset {\mathbb R}^n$ is symmetric with respect the origin, or just symmetric in short, if $x\in K$ implies that $-x\in K$ . Set $K^\circ = \{ y\in{\mathbb R}^n \,:\, \sup\limits_{x\in K} \langle x,y \rangle \leq 1 \}$ is called the polar body of K. For two convex bodies K and T in ${\mathbb R}^n$ , the covering number of K by T, denoted N(K, T), is the minimal number of translates of T needed to cover K. Also, let D be the euclidean unit ball in ${\mathbb R}^n$ .

The Theorem: On 29th May 2003, Shiri Artstein, Vitali Milman, and Stanisław Szarek submitted to the Annals of Mathematics a paper in which they proved the existence of two universal constants $\alpha$ and $\beta$ such that for any dimension n and any symmetric convex body $K \subset {\mathbb R}^n$ , $N(D, \alpha^{-1} K^\circ)^{\frac{1}{\beta}} \leq N(K, D) \leq N(D, \alpha K^\circ)^\beta$ .

Short context: In 1972, Pietsch conjectured the existence of two constants $a, b \geq 1$ such that for any dimension n, and for any two symmetric convex bodies K and T in ${\mathbb R}^n$ , we have $\log N(T^\circ, a K^\circ) \leq b \log N(K, T)$ (this is one of many equivalent formulations of the conjecture). The conjecture is originated in operator theory and became known as the “duality conjecture for entropy numbers”. The Theorem implies that it holds in a special but important case when either K or T is an euclidean ball.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 4.6 of this book for an accessible description of the Theorem.

Go to the list of all theorems

The weak form of De Giorgi’s conjecture is true in dimensions at most 8

You need to know: Euclidean space ${\mathbb R}^n$ , hyperplane in ${\mathbb R}^n$ , function $u:{\mathbb R}^n \to {\mathbb R}$ (function in n variables), partial derivatives of such function, differential equation.

Background: A level set of a function $u:{\mathbb R}^n \to {\mathbb R}$ is a set of the form $L_c(f)=\{(x_1, \dots, x_n)\,|\,u(x_1, \dots, x_n)=c\}$ for some constant $c\in{\mathbb R}$ . For a twice-differentiable function $u:{\mathbb R}^n \to {\mathbb R}$ , its Laplacian $\Delta u$ is $\Delta u = \frac{\partial^2 u}{\partial x_1^2} + \frac{\partial^2 u}{\partial x_2^2} + \dots + \frac{\partial^2 u}{\partial x_n^2}$ .

The Theorem: On 25th April 2003, Ovidiu Savin submitted to the Annals of Mathematics a paper in which he proved the following result. Suppose $u:{\mathbb R}^n \to {\mathbb R}$ is a solution to differential equation $\Delta u=u^3-u$ such that (i) $|u|<1$ ; (ii) $\frac{\partial u}{\partial x_n}>0$ for every $x=(x_1, \dots, x_n)\in{\mathbb R}^n$ ; and (iii) $\lim\limits_{x_n\to\pm \infty} u(x_1, \dots, x_{n-1}, x_n)=\pm 1$ for every fixed $x_1, \dots, x_{n-1}$ . If $n \leq 8$ , then all level sets of u are hyperplanes.

Short context: Differential equation $\Delta u=u^3-u$ originates in the theory of phase transition, is important and well-studied. In 1978, De Giorgi conjectured that if $u:{\mathbb R}^n \to {\mathbb R}$ is a solution to this equation satisfying (i) and (ii), then all level sets of u are hyperplanes, at least if $n \leq 8$ . This conjecture, if true, would allow you to write down a formula for u easily. In 1998, Ghoussoub and Gui proved this conjecture for $n=2$ , while in 2000 Ambrosio and Cabre proved it for $n=3$ . The Theorem confirms this conjecture in a weak form (that is, under the additional assumption (iii)), in all dimensions $n \leq 8$ .

Links: The original paper is available here. See also Section 9.1 of this book for an accessible description of the Theorem.

Go to the list of all theorems

The set of nowhere monotone differentiable functions on R is lineable

You need to know: Monotone function, continuous function, differentiable function, vector space and its dimension, infinite-dimensional vector space.

Background: Let $C({\mathbb R})$ be the set of all functions $f:{\mathbb R}\to {\mathbb R}$ that are continuous at every $x\in{\mathbb R}$ . A subset $S\subset C({\mathbb R})$ is called lineable in $C({\mathbb R})$ if $S\cup\{0\}$ contains an infinite-dimensional vector space. A function $f:{\mathbb R}\to {\mathbb R}$ is called nowhere monotone if there are no real numbers $a<b$ such that f is monotone on $(a,b)$ .

The Theorem: On 26th March 2003, Richard Aron, Vladimir Gurariy, and Juan Seoane-Sepúlveda submitted to the Proceedings of the AMS a paper in which they proved that the set of differentiable functions $f:{\mathbb R}\to {\mathbb R}$ that are nowhere monotone is lineable in $C({\mathbb R})$ .

Short context: In 1872, Weierstrass constructed an example of a function $f:{\mathbb R}\to {\mathbb R}$ which is continuous at every $x\in{\mathbb R}$ but nowhere monotone. In fact, the Weierstrass function is also nowhere differentiable. In 1915, Denjoy constructed an example of a function $f:{\mathbb R}\to {\mathbb R}$ that are differentiable at every $x\in{\mathbb R}$ but still nowhere monotone. In 1966, Gurariy proved that the set of nowhere differentiable functions is lineable in $C({\mathbb R})$ . This shows that such functions are not some “exotic counterexamples” but in fact quite typical. The Theorem establishes the same result for differentiable but nowhere monotone functions.

Links: The original paper is available here.

Go to the list of all theorems

For convex domains of diameter d, Poincaré inequality holds with constant d/pi

You need to know: Euclidean space ${\mathbb R}^n$ , norm $||x||=\sqrt{(x,x)}$ of $x\in{\mathbb R}^n$ , convex domain $\Omega\subset {\mathbb R}^n$ , diameter of $\Omega$ , integral $\int_\Omega u(x) dx$ of function $u:\Omega \to {\mathbb R}$ , gradient $\nabla u: \Omega \to {\mathbb R}^n$ of u.

Background: For convex domain $\Omega\subset {\mathbb R}^n$ , let $H^1(\Omega)$ be the set of functions $u:\Omega \to {\mathbb R}$ for which $\nabla u$ exists on $\Omega$ and both $||u||_{L^2(\Omega)}=\sqrt{\int_\Omega u(x)^2 dx}$ and $||\nabla u||_{L^2(\Omega)}=\sqrt{\int_\Omega ||\nabla u(x)||^2 dx}$ are finite.

The Theorem: On 28th February 2003, Mario Bebendorf submitted to the Journal of Analysis and its Applications a paper in which he proved that, for any convex domain $\Omega\subset {\mathbb R}^n$ with diameter d, inequality $||u||_{L^2(\Omega)} \leq \frac{d}{\pi}||\nabla u||_{L^2(\Omega)}$ holds for all $u \in H^1(\Omega)$ such that $\int_\Omega u(x) dx = 0$ .

Short context: The inequality $||u||_{L^2(\Omega)} \leq c_\Omega||\nabla u||_{L^2(\Omega)}$ holds for any (non necessarily convex) subset $\Omega\subset {\mathbb R}^n$ , bounded at least in one direction. It is known as the Poincaré inequality. However, in this generality, it is unclear how to explicitly express constant $c_\Omega$ in terms of parameters of set $\Omega$ . In 1960, Payne and Weinberger published a theorem stating that if $\Omega\subset {\mathbb R}^n$ is convex with diameter d, then Poincaré inequality holds with $c_\Omega=\frac{d}{\pi}$ . However, their proof is correct only for $n=2$ . The Theorem proves this result for all n.

Links: The original paper is available at here.

Go to the list of all theorems

Every finite metric space has a large subset embeddable into R^d with small distortion

You need to know: Euclidean space ${\mathbb R}^d$ , metric space $(X,\rho)$ with metric $\rho$ .

Background: We say that a subset S of metric space $(X,\rho)$ can be embedded into metric space $(Y,\rho')$ with distortion at most $\alpha$ if there exists a function $f:S\to Y$ such that $m \rho(A,B) \leq \rho'(f(A),f(B)) \leq M \rho(A,B), \, \forall A,B \in S$ , where $m,M>0$ are constants such that $\frac{M}{m}\leq \alpha$ .

The Theorem: On 4th December 2002, Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor submitted to the Annals of Mathematics a paper in which they proved the existence of constant $C>0$ such that for every $\alpha>1$ , every n-point metric space has a subset of size $n^{1-C\frac{\log(2\alpha)}{\alpha}}$ which can be embedded into ${\mathbb R}^d$ with distortion at most $\alpha$ .

Short context: In 1985, Bourgain proved that every n-point metric space X can be embedded into ${\mathbb R}^d$ with distortion at most $C\log n$ (where the dimension d depends on n but the constant C does not). The bound $C\log n$ is essentially sharp. The Theorem states, however, that reasonably large subsets of X can be embedded into ${\mathbb R}^d$ with much smaller distortion. In a subsequent work Mendel and Naor showed that the Theorem holds for even larger subset of size $n^{1-\frac{C}{\alpha}}$ , and that this is optimal up to the value of the constant C.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 5.8 of this book for an accessible description of the Theorem.

Go to the list of all theorems