A fixed point theorem holds for alpha–psi-contractive type mappings

You need to know: Metric space, complete metric space, notation $\psi^n$ for the n-th iterate of $\psi$ .

Background: Let $\Psi$ be the set of all non-decreasing functions $\psi:[0,+\infty)\to[0,+\infty)$ such that $\sum\limits_{n=1}^{\infty}\psi^n(t)<+\infty$ for all $t>0$ . Let $(X,d)$ be a complete metric space. A mapping $T:X \to X$ is called an $\alpha$ – $\psi$ -contractive if there exist two functions $\alpha: X \times X \to [0,+\infty)$ and $\psi\in \Psi$ such that $\alpha(x,y)d(Tx,Ty)\leq \psi(d(x,y))$ for all $x,y \in X$ . We say that T is $\alpha$ -admissible if for $x,y \in X$ , $\alpha(x,y) \geq 1$ implies that $\alpha(Tx,Ty)\geq 1$ .

The Theorem: On 17th April 2011, Bessem Samet, Calogero Vetro, and Pasquale Vetro submitted to Nonlinear Analysis: Theory, Methods & Applications a paper in which they proved the following result. Let $(X,d)$ be a complete metric space and $T:X \to X$ be an $\alpha$ – $\psi$ -contractive mapping satisfying the following conditions: (i) T is $\alpha$ -admissible; (ii) there exists $x_0 \in X$ such that $\alpha(x_0,Tx_0)\geq 1$ ; and (iii) T is continuous. Then, T has a fixed point, that is, there exists $x^* \in X$ such that $Tx^*=x^*$ .

Short context: The 1922 Banach’s Fixed Point Theorem states that, if $(X,d)$ is a non-empty complete metric space and $f:X\to X$ is such that (*) $d(f(x),f(y))\leq c\cdot d(x,y), \, \forall x,y$ for some $c\in(0,1)$ , then f has a fixed point $x^*$ . It is a fundamental result in mathematics with countless applications. However, in some other applications condition (*) does not hold. The Theorem replaces (*) with a weaker condition which reduces to (*) in the special case $\alpha(x,y)=1$ and $\psi(t)=ct$ . As an example, the authors provide applications to the theory of differential equations when the Theorem is applicable while Banach’s result is not. See here and here for other versions of fixed point theorems.

Links: The original paper is available here.

Go to the list of all theorems

The Szemerédi–Trotter estimate holds for subspaces in R^d, with epsilon loss

You need to know: Euclidean space ${\mathbb R}^d$ , affine subspace in ${\mathbb R}^d$ , dimension of an affine subspace, notation $|S|$ for the number of elements in finite set S.

Background: Let P be a finite set of points in ${\mathbb R}^d$ , and let L be a finite set of k-dimensional affine subspaces in ${\mathbb R}^d$ , such that any two distinct spaces in L intersect in at most one point. Let $I(P,L) := \{(p,l)\in P\times L : p \in l\}$ be the set of incidences.

The Theorem: On 15th March 2011, Jozsef Solymosi and Terence Tao submitted to arxiv and Discrete & Computational Geometry a paper in which they proved that for every real $\epsilon>0$ , and all integers $k\geq 1$ and $d\geq 2k$ , there exists a constant $A=A(\epsilon,k)> 0$ such that $|I(P,L)| \leq A |P|^{2/3+\epsilon}|L|^{2/3}+\frac{3}{2}|P|+\frac{3}{2}|L|$

Short context: Famous Szemerédi–Trotter Theorem, proved in 1983, states that if P is a finite set of distinct points in the plane and L is a finite set of distinct lines, then $|I(P,L)| \leq C(|P|^{2/3}|L|^{2/3}+|P|+|L|)$ for some absolute constant C. This bound is the best possible up to the constant factor. In a paper submitted in 2005, Tóth conjectured that the same bound holds for k-dimensional affine subspaces of ${\mathbb R}^{2k}$ in place of lines on the plane. The Theorem confirms this conjecture, up to $\epsilon$ loss.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

zeta(2,…,2,3,2,…,2) is a rational linear combination of products zeta(m)pi^(2n) with m odd

You need to know: Sum of infinite series, factorial $n!=1\cdot 2 \cdot \dots \cdot n$ with convention that $0!=1$ , notation ${n}\choose{k}$ for $\frac{n!}{k!(n-k)!}$ , with convention that ${{n}\choose{k}}=0$ if $n<k$ .

Background: Zeta function is the sum of infinite series $\zeta(s) = \sum\limits_{n=1}^\infty \frac{1}{n^s}$ for $s>1$ . Multiple zeta function is $\zeta(k_1, k_2, \dots k_n) = \sum\limits_{0<m_1<\dots<m_n} \frac{1}{m_1^{k_1} m_2^{k_2} \dots m_n^{k_n}}$ . Let $H(n)=\zeta(\underbrace{2,\dots, 2}_{n})=\frac{\pi^{2n}}{(2n+1)!}$ . Let $H(a,b)=\zeta(\underbrace{2,\dots, 2,}_{a},3,\underbrace{2,\dots, 2}_{b})$ .

The Theorem: On 3rd March 2011, Don Zagier submitted to the Annals of Mathematics a paper in which he proved that for all integers $a,b \geq 0$ , we have $H(a,b)=\sum\limits_{r=1}^{a+b+1}(-1)^r \left[{{2r}\choose{2a+2}}-(1-2^{-2r}){{2r}\choose{2b+1}} \right] H(a+b-r+1)\zeta(2r+1)$ .

Short context: Zeta function in one variable $\zeta(s)$ is one of the central functions in the whole mathematics which is studied for centuries. Multiple zeta functions are natural generalisations which are also well-studied, see, for example, here. It is a rare achievement to derive an exact analytical expression for $\zeta(k_1, k_2, \dots k_n)$ . The Theorem achieves this for $\zeta(2,\dots,2,3,2,\dots,2)$ .

Links: The original paper is available here.

Go to the list of all theorems

There exist e>0 and C such that if A is a cap set in F_3^N, then |A|/3^N < C/N^(1+e)

You need to know: Addition modulo 3, vectors, notation $|A|$ for the number of elements in finite set A.

Background: Let ${\mathbb F}_3$ be the set $\{0,1,2\}$ with addition defined modulo 3. Let ${\mathbb F}_3^N$ be the set of N-component vectors $x=(x_1, \dots, x_N)$ with each $x_i \in {\mathbb F}_3$ , and with addition defined component-wise. We say that three different points $x,y,z\in {\mathbb F}_3^N$ form a line if $x+y=z+z$ . A set $A \subseteq {\mathbb F}_3^N$ is called a cap set if it contains no lines.

The Theorem: On 31st January 2011, Michael Bateman and Nets Katz submitted to arxiv a paper in which they proved the existence of $\epsilon>0$ and $C<\infty$ such that if $A \subseteq {\mathbb F}_3^N$ is a cap set, then $\frac{|A|}{3^N} \leq \frac{C}{N^{1+\epsilon}}$ .

Short context: What can the maximal size of a cap set in ${\mathbb F}_3^N$ ? This problem is interesting in its own, but also studied because of hope that methods to solve it may be useful for the similar problem of finding dense sets of integers without 3-term arithmetic progressions, see here. A cap set conjecture predicts the existence of constant $c<3$ such that $|A|<c^N$ for every cap set $A \subseteq {\mathbb F}_3^N$ . However, before 2011, the best upper bound was $\frac{|A|}{3^N} \leq \frac{C}{N}$ , proved by Meshulam in 1995. The Theorem improves this bound.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

A convergent algorithm for non-smooth convex saddle-point problems

You need to know: Euclidean space ${\mathbb R}^n$ , inner product $(x,y)$ for $x,y\in {\mathbb R}^n$ , norm $||x||=\sqrt{(x,x)}$ , proper convex lower-semicontinuous (l.s.c.) function $F:{\mathbb R}^n \to [0,+\infty]$ , continuous linear operator $K:{\mathbb R}^n \to {\mathbb R}^m$ , its norm $||K||=\max\limits_{x\in{\mathbb R}^n}\frac{||Kx||}{||x||}$ .

Background: Let $G:{\mathbb R}^n \to [0,+\infty]$ and $F:{\mathbb R}^m \to [0,+\infty]$ be proper convex l.s.c. functions, and let $F^*(y)=\sup\limits_{x\in{\mathbb R}^m}((y,x)-F(x))$ be the convex conjugate of F. Let $K:{\mathbb R}^n \to {\mathbb R}^m$ be a continuous linear operator, and let $K^*:{\mathbb R}^m \to {\mathbb R}^n$ be such that $(Kx,y)=(x,K^*y)$ for all $x\in {\mathbb R}^n$ , $y\in {\mathbb R}^m$ . Let $H(x,y)=(Kx,y)+G(x)-F^*(y)$ . By saddle-point problem we mean the problem of the form $\min\limits_{x\in {\mathbb R}^n}\max\limits_{y\in {\mathbb R}^m}H(x,y)$ . A pair $(x^*,y^*)$ is called a saddle-point of this problem if $H(x,y^*)\geq H(x^*,y^*)$ for all $x\in{\mathbb R}^n$ and $H(x^*,y)\leq H(x^*,y^*)$ for all $y\in{\mathbb R}^m$ . For any $V:{\mathbb R}^n \to [0,+\infty]$ , $y\in{\mathbb R}^n$ , and $\tau>0$ , denote $d_{V,\tau}(x)=\arg\min\limits_{x\in{\mathbb R}^n}\left(\frac{||x-y||^2}{2\tau}+V(x)\right)$ . For $\tau>0$ , $\sigma>0$ , $\theta\in[0,1]$ , initial points $x^0 \in {\mathbb R}^n$ , $y^0 \in {\mathbb R}^m$ , and $\bar{x}^0=x^0$ , define sequences $x^n, y^n, \bar{x}^n$ iteratively as follows: $y^{n+1}=d_{F^*,\sigma}(y^n+\sigma K \bar{x}^n)$ , $x^{n+1}=d_{G,\tau}(x^n-\tau K^* y^{n+1})$ , $\bar{x}^{n+1} = x^{n+1}+\theta(x^{n+1}-x^n)$ , $n \geq 0$ .

The Theorem: On 21st December 2010, Antonin Chambolle and Thomas Pock published in the Journal of Mathematical Imaging and Vision a paper in which they proved that if $\theta=1$ and $\tau\sigma(||K||)^2<1$ , then there exist a saddle-point $(x^*,y^*)$ such that $\lim\limits_{n\to\infty}x^n = x^*$ and $\lim\limits_{n\to\infty}y^n = y^*$ .

Short context: Saddle-point problems of the form as above arise in many applications, for example in image denoising and segmentation. The Theorem proves that a simple algorithm converges to a saddle-point. Practical experiments suggests that the convergence is in fact fast, which makes the algorithm widely applicable.

Links: The original paper is available here.

Go to the list of all theorems

For any bounded subset A of L^1 space, exists x fixed by every isometry of L^1 preserving A

You need to know: Banach space B with norm $||.||$ , linear map $f:B\to B$ , bounded subset of B, $L^1$ space.

Background: Let B be a Banach space. A linear map $f:B\to B$ is called an isometry if $||f(x)||=||x||$ for all $x \in B$ . For a subset $A \subset B$ , we say that f preserves A if $f(x) \in A$ for all $x \in A$ . A point $x\in B$ is called a fixed point of $f$ if $f(x)=x$ .

The Theorem: On 7th December 2010, Uri Bader, Tsachik Gelander, and Nicolas Monod submitted to arxiv and Inventiones Mathematicae a paper in which they proved the following result. Let A be a non-empty bounded subset of an $L^1$ space B. Then there is a point in B fixed by every isometry of B preserving A. Moreover, one can choose a fixed point which minimises $\sup\limits_{a\in A}||v-a||$ over all $v \in B$ .

Short context: Starting with famous Banach’s Fixed Point Theorem, mathematicians developed fixed point theorems in various contexts, useful in different applications, see here for an example. The Theorem is a version of fixed point theorem for L1 spaces. The authors demonstrated that it has many applications. For example, it can be used to derive the optimal solution to so-called “derivation problem”, see the original paper for details.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

The main conjecture in Vinogradov’s Mean Value Theorem is true if s>=k(k+1)

You need to know: Just basic arithmetic for the Theorem. You may like to learn what is Vinogradov’s Mean Value Theorem and Waring’s problem to better understand the context.

Background: For positive integers s,k, and X, let $J_{s,k}(X)$ be the number of integral solutions of the system of equations $x_1^j+\dots+x_s^j = y_1^j+\dots+y_s^j$ , $1 \leq j \leq k$ , such that $1\leq x_i,y_i \leq X$ for $1\leq i \leq s$ .

The Theorem: On 3rd December 2010, Trevor Wooley submitted to the Annals of Mathematics a paper in which he proved that for any natural numbers $k\geq 2$ and $s \geq k(k + 1)$ , and any real $\epsilon>0$ , there exist a constant C such that $J_{s,k}(X) \leq C X^{2s-\frac{1}{2}k(k+1)+\epsilon}$ .

Short context: A famous conjecture, known as the main conjecture in Vinogradov’s Mean Value Theorem, predicts that $J_{s,k}(X) \leq C X^\epsilon(X^s+X^{2s-\frac{1}{2}k(k+1)})$ for any $s\geq 1$ and $k\geq 2$ . This estimate, if true, would be optimal up to constant and $X^\epsilon$ factors. The Theorem implies that it holds if $s \geq k(k + 1)$ . In the same paper, Wooley demonstrated several applications of the Theorem, for example, to Waring’s problem. In a later work, Bourgain, Demeter, and Guth proved the conjecture in general.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Szemerédi’s theorem holds almost surely inside sparse random sets

You need to know: A (nontrivial) k-term arithmetic progression, notation $|I|$ for the number of elements in finite set I, notation P for probability, independence.

Background: Let $[n]=\{1,2,\dots,n\}$ , and let $[n]_p$ be a random subset of $[n]$ in which each element of $[n]$ is chosen independently with probability $p\in[0,1]$ . A finite set I of integers is called $(\delta; k)$ -Szemerédi if every subset of I of cardinality at least $\delta|I|$ contains a nontrivial k-term arithmetic progression.

The Theorem: On 18th November 2010, Daniel Conlon and Timothy Gowers submitted to arxiv and the Annals of Mathematics a paper in which they proved, among other results, that for any $\delta>0$ and any integer $k\geq 3$ , there exists a constant $C=C(k,\delta)$ such that $\lim\limits_{n\to\infty} P([n]_p \text{ is } (\delta; k) \text{-Szemeredi})=1$ if $p \geq \min\{1, Cn^{-1/(k-1)}\}$ .

Short context: Famous Szemerédi’s theorem, proved in 1975, states, in our terminology, that set $[n]$ itself is $(\delta; k)$ -Szemerédi for all $n\geq N(\delta,k)$ . Later, Green and Tao, on the way of proving this theorem, proved the existence of function $p=p(n)$ with $\lim\limits_{n\to\infty} p(n)=0$ such that $\lim\limits_{n\to\infty} P([n]_p \text{ is } (\delta; k) \text{-Szemeredi})=1$ . The Theorem proves that the same conclusion holds for every function $p=p(n)$ such that $p \geq Cn^{-1/(k-1)}$ . This result is optimal up to constant factor because it is known that, for some constant $c=c(k,\delta)>0$ , $\lim\limits_{n\to\infty} P([n]_p \text{ is } (\delta; k) \text{-Szemeredi})=0$ whenever $p \leq cn^{-1/(k-1)}$ . Before 2010, the Theorem was known to hold only for $k=3$ . See here for further generalisation in a later work.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

A set of N points in the plane determines at least cN/log N distinct distances

You need to know: Euclidean plane ${\mathbb R}^2$ , Euclidean distance $d(A,B)$ between points $A \in {\mathbb R}^2$ and $B \in {\mathbb R}^2$ .

Background: Let S be a finite set of points on the plane. Let $D(S)$ be the set of distinct real numbers $t>0$ such that $t=d(A,B)$ for some $A\in S$ and $B\in S$ . Let $|D(S)|$ be the number of elements in set $D(S)$ .

The Theorem: On 17th November 2010, Larry Guth and Nets Katz submitted to arxiv a paper in which they proved the existence of constant $c>0$ , such that $|D(S)| \geq c\frac{N}{\log N}$ for every set S of $N\geq 2$ points on the plane.

Short context: In 1946, Erdős posed the question what is the smallest number of distinct distances that can be determined by N points in the plane. Erdös checked that if the points are arranged in a square grid, then the number of distinct distances is proportional to $\frac{N}{\sqrt{\log N}}$ , and conjectured that this is optimal up to a constant factor. Many authors proved better and better lower bounds, with best before 2010 was $|D(S)| \geq cN^{0.8641}$ . The Theorem proves a much better lower bound, which almost matches the Erdős prediction.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Z is definable in Q by a universal first-order formula in the language of rings

You need to know: Set ${\mathbb Z}$ of integers, set ${\mathbb Q}$ of rational numbers, standard notations $\forall$ (for all) and $\exists$ (there exists), polynomials.

Background: Let ${\mathbb Z}[t, x_1, \dots, x_n]$ denote the set of polynomials in $n+1$ variable $t, x_1, \dots, x_n$ with integer coefficients.

The Theorem: On 15th October 2010, Jochen Koenigsmann submitted to arxiv a paper in which he proved the existence of positive integer n, and a polynomial $g \in {\mathbb Z}[t, x_1, \dots, x_n]$ such that, for any $t\in{\mathbb Q}$ , we have $t\in{\mathbb Z}$ if and only if $\forall x_1, \dots, \forall x_n \in {\mathbb Q}: g(t,x_1,\dots,x_n) \neq 0$ .

Short context: Hilbert’s 10th problem was to find a general algorithm for deciding, given any n and any polynomial $f \in {\mathbb Z}[x_1, \dots, x_n]$ , whether or not f has a zero in ${\mathbb Z}^n$ . In 1970, Matiyasevich proved that there can be no such algorithm. Hilbert’s 10th problem over ${\mathbb Q}$ remains open. If we could define ${\mathbb Z}$ in ${\mathbb Q}$ as in the Theorem but with existential quantifiers $\exists$ instead of universal ones $\forall$ , this together with Matiyasevich theorem would give a (negative) answer to this problem. The Theorem may be considered as a major step in this direction.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems