2) is subcomplete

You need to know: Notation ${\mathbb N}$ for the set of natural numbers, notation $|B|$ for the number of elements in set B, arithmetic progression.

Background: Let ${\cal A}\subset {\mathbb N}$ be an infinite set of natural numbers (without repetitions). We say that ${\cal A}$ has density at least $f(n)$ if $|{\cal A}\cap\{1,2,\dots,n\}|\geq f(n)$ for all sufficiently large n. Let $S_A=\{\sum\limits_{x\in B} x\,|\,B\subset {\cal A}, |B|<\infty\}$ be the set of all possible sums of finite number of elements of ${\cal A}$ . We say that ${\cal A}$ is subcomplete if $S_A$ contains an infinite arithmetic progression.

The Theorem: On 19th March 2003, Endre Szemerédi and Van Vu submitted to the Annals of Mathematics a paper in which they proved the existence of constant $c>0$ such that every set ${\cal A}\subset {\mathbb N}$ with density at least $c\sqrt{n}$ is subcomplete.

Short context: We say that set ${\cal A}$ is complete if $S_A$ contains all sufficiently large integers. This notion was introduced by Erdős in the sixties. It is well studied, the central problem being to find sufficient conditions for completeness. In 1962, Erdős conjectured the existence of $c>0$ such that if (i) ${\cal A}$ has density at least $c\sqrt{n}$ and (ii) $S_A$ contains an element of every infinite arithmetic progression, then ${\cal A}$ is complete. In 1966, Folkman conjectured that every ${\cal A}$ satisfying (i) is subcomplete and deduced the Erdős conjecture from this. The Theorem confirms the Folkman conjecture and hence the Erdős conjecture.

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

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

Perfect graphs can be recognised in polynomial time

You need to know: Polynomial-time algorithms, basic graph theory: graph, size of a graph (number of its vertices), induced subgraph, complete sugraph, cycle, length of the cycle, complement of a graph, chromatic number of a graph, big O notation.

Background: A graph G is perfect if for every induced subgraph H, the chromatic
number of H equals to the size of the largest complete subgraph of H. The problem of perfect graph recognition is: given a graph as an input, determine whether it is perfect or not.

The Theorem: On 26th February 2003, Maria Chudnovsky, Gérard Cornuéjols, Xinming Liu, Paul Seymour, and Kristina Vušković submitted to Combinatorica a paper in which they proved that the problem of perfect graph recognition for n-vertex graphs can be solved in time $O(n^9)$ .

Short context: An odd hole is a cycle of odd length $n\geq 5$ and odd antihole is the complement of odd hole. A graph G is Berge if it does not contain an odd hole or an odd antihole as an induced subgraph. The Theorem in fact provides an algorithm for recognising Begre graphs. However, by an earlier result of Chudnovsky, Robertson, Seymour, and Thomas, a graph G is perfect if and only if it is Begre. This gives the first polynomial-time algorithm for recognising perfect graphs.

Links: The original paper is available here.

Go to the list of all theorems

Any positive proportion of primes contains a 3-term arithmetic progression

You need to know: Prime numbers, notation $|A|$ for size of set A, arithmetic progression, limit superior $\limsup$ .

Background: Let ${\mathbb N}$ be the set of positive integers, and let ${\cal P}$ be the set of primes. For $n\in {\mathbb N}$ , let $S_n=\{1,2,\dots,n\}$ , and let ${\cal P}_n = {\cal P}\cap S_n$ be the set of primes not exceeding n. We say that subset $A\subset N$ of integers has positive upper density if $\limsup\limits_{n\to\infty}\frac{|A \cap S_n|}{n} > 0$ . Similarly, we say that subset $A\subset {\cal P}$ of primes has positive upper density if $\limsup\limits_{n\to\infty}\frac{|A \cap {\cal P}_n|}{|{\cal P}_n|} > 0$ .

The Theorem: On 25th February 2003, Ben Green submitted to arxiv a paper in which he proved that every subset of ${\cal P}$ of positive upper density contains a 3-term arithmetic progression (3AP).

Short context: In 1939, Van der Corput proved that the set of primes contains infinitely many 3APs. In 1953, Roth proved that any subset of integers of positive upper density contains a 3AP. The Theorem provides a common generalisation of these two results. In a later work, Green and Tao proved that the same is true for arithmetic progressions of any length.

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

Go to the list of all theorems

The Erdős–Szemerédi sum-product theorem holds in finite fields

You need to know: Field, finite field $F_q$ with q elements, size $|A|$ of set A.

Background: For $A\subset F_q$ , denote $A+A=\{a+b, \, a\in A, b\in A\}$ and $A\cdot A=\{a\cdot b, \, a\in A, b\in A\}$ .

The Theorem: On 29th January 2003, Jean Bourgain, Nets Katz, and Terence Tao submitted to arxiv a paper in which they proved, among other results, that for any $\delta>0$ there exist positive constants c and $\epsilon$ such that for any prime q, and any $A\subset F_q$ such that $q^\delta<|A|<q^{1-\delta}$ , we have $\max(|A+A|, |A \cdot A|) \geq c|A|^{1+\epsilon}$ .

Short context: In 1983, Erdős and Szemerédi proved the existence of positive constants c and $\epsilon$ such that inequality $\max(|A+A|, |A \cdot A|) \geq c|A|^{1+\epsilon}$ holds for any finite non-empty set A of real numbers. The Erdős–Szemerédi theorem can be viewed as an assertion that it is not possible for a large set to behave like an arithmetic progression and as a geometric progression simultaneously. The Theorem establishes a finite field analogue of this fundamental result.

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

Go to the list of all theorems

Primality testing can be done in deterministic polynomial time

You need to know: Prime numbers, polynomial-time algorithms, deterministic and randomised algorithms, class P.

Background: The primality testing problem is, given integer n as an input, determine whether n is prime or not.

The Theorem: On 24th January 2003, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena submitted to the Annals of Mathematics a paper in which they proved the existence of deterministic polynomial-time algorithm for the primality testing problem. In other words, they proved that this problem belongs to the class P.

Short context: The primality testing problem is interesting in its own right, but also has practical applications in, for example, cryptography. In 1980, Rabin, based on earlier paper of Miller, developed an efficient randomised algorithm for this problem. However, the question whether primality testing can be done in deterministic polynomial time remained a major open problem is the field. The Theorem resolves it affirmatively.

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

Go to the list of all theorems

The strong perfect graph conjecture is true: all Berge graphs are perfect

You need to know: Basic graph theory: graph, size of a graph (number of its vertices), induced subgraph, complete sugraph, cycle, length of the cycle, complement of a graph, chromatic number of a graph.

Background: A graph G is perfect if for every induced subgraph H, the chromatic
number of H equals to the size of the largest complete subgraph of H. An odd hole is a cycle of odd length $n\geq 5$ and odd antihole is the complement of odd hole.

The Theorem: On 4th December 2002, Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas submitted to arxiv a paper in which they proved that a graph G is perfect if and only if it does not contain an odd hole or an odd antihole as an induced subgraph.

Short context: In 1961, Berge observed that every perfect graph G does not contain an odd hole or an odd antihole, and conjectured that the converse is true. This conjecture became known as the strong perfect graph conjecture and attracted a lot of attention. Graphs with no odd hole or antihole got the name Berge graphs and the conjecture then states that all Berge graphs are perfect (which implies that the perfect graphs and the Berge graphs define the same class of graphs). The Theorem proves this conjecture and have got the name strong perfect graph theorem. The proof of the strong perfect graph theorem won for its authors several prizes including the 2009 Fulkerson Prize.

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

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

Polynomials small at N equidistant points in (-1,1) are small on subinterval

You need to know: Polynomial, degree of a polynomial, inverse tangent function $\arctan(x)$ .

Background: Let $P_{n,N}$ be the set of polynomials P of degree at most n with $|P(x_k)|\leq 1, k=1,2,\dots,N$ , where $x_k = -1 + (2k-1)/N, \, k=1,2,\dots,N$ is the sequence of N equidistant points on $(-1,1)$ . Let $K_{n,N}(x) = \max\limits_{P\in P_{n,N}}|P(x)|$ .

The Theorem: On 22nd November 2002, Evguenii Rakhmanov submitted to the Annals of Mathematics a paper in which he proved the existence of constant C such that inequality $K_{N,n}(x) \leq C \log \frac{\pi}{\arctan \left(\frac{N}{n}\sqrt{r^2-x^2}\right)}$ holds for all $n<N$ and all $x\in(-r,r)$ , where $r=\sqrt{1-\frac{n^2}{N^2}}$ .

Short context: The Theorem implies that if a degree n polynomial is bounded at N pre-specified discrete points then its maximal possible absolute value $K_{N,n}(x)$ is bounded on any compact subinterval of $(-r,r)$ . The bound is essentially sharp. It is useful in approximation theory, where we approximate a function by a polynomial at some discrete points and need to prove that this approximation works well on some interval.

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

Go to the list of all theorems

Fast algorithm for the number of solutions in the coin problem with fixed n

You need to know: Coprime integers, algorithm working in polynomial time, NP-hard problem.

Background: Given positive coprime integers $a_1, a_2, \dots, a_n$ , denote $S(a_1, a_2, \dots, a_n)$ the (always finite) set of positive integers which cannot be represented as $\sum\limits_{i=1}^n m_i a_i$ for some non-negative integers $m_1, m_2, \dots m_n$ .

The Theorem: On 8th November 2002, Alexander Barvinok and Kevin Woods submitted to arxiv a paper in which they, among other results, proved the existence of an algorithm, which, given $a_1, a_2, \dots, a_n$ , computes the number of integers in $S(a_1, a_2, \dots, a_n)$ in polynomial time for any fixed n.

Short context: The Frobenius coin problem, studied at least from 1882, asks to compute the largest integer in $S(a_1, a_2, \dots, a_n)$ . The problem is known to be NP-hard if n is part of the input. However, Kannan presented in 1992 a polynomial algorithm to solve it for every fixed n. The Theorem states that, for fixed n, the number of elements in $S(a_1, a_2, \dots, a_n)$ can also be computed efficiently.

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

Go to the list of all theorems