The primes contain arbitrarily long arithmetic progressions

You need to know: Prime numbers.

Background: A (non-trivial) arithmetic progression of length n is a sequence $a_1, a_2, \dots, a_n$ of real numbers such that $a_i = a_1 + (i-1)d, \, i=1,2,\dots,n$ for some $d\neq 0$ .

The Theorem: On 8th April 2004, Ben Green and Terence Tao submitted to arxiv a paper in which they proved that for every positive integer n there exist an arithmetic progression of length n consisting of only prime numbers.

Short context: In 1939, Van der Corput proved that the set of primes contains infinitely many arithmetic progressions of length $n=3$ . The Theorem proves this for all n. Before 2004, this was open even for $n=4$ . Moreover, Green and Tao proved that even any positive proportion of primes contains infinitely many arithmetic progressions of length n for all n. This generalises an earlier theorem of Green, which proves this for $n=3$ .

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

Go to the list of all theorems

The Leech lattice gives the densest lattice packing of spheres in 24-dimensional space

You need to know: Euclidean space ${\mathbb R}^n$ , basis for ${\mathbb R}^n$ , volume in ${\mathbb R}^n$ , limit superior $\limsup$ , open ball $B(O,r)\subset {\mathbb R}^n$ with center O and radius r

Background: A lattice $\Lambda$ in ${\mathbb R}^n$ is a set of the form $\Lambda =\left\{\left.\sum\limits_{i=1}^n a_i v_i\,\right\vert\, a_i \in {\mathbb Z}\right\}$ , where $v_1, \dots, v_n$ is a basis for ${\mathbb R}^n$ . By sphere packing in ${\mathbb R}^n$ we mean set E of (infinitely many) non-overlapping open balls with the same radii. For a fixed point $O \in {\mathbb R}^n$ , denote $\delta(O,E) = \limsup\limits_{r\to\infty}\frac{|B(O,r) \cap E|}{|B(O,r)|},$ where $|.|$ denotes volume in ${\mathbb R}^n$ . It can be shown that $\delta(O,E)$ depends only on E but not on O and is called upper density of E. Sphere packing E is called lattice packing if the centres of the balls form a lattice.

The Theorem: On 16th March 2004, Henry Cohn and Abhinav Kumar submitted to arxiv a paper in which they proved that no lattice sphere packing in ${\mathbb R}^{24}$ has upper density greater than $\frac{\pi^{12}}{12!}=0.001929...$ .

Short context: There exists a lattice sphere packing in ${\mathbb R}^{24}$ with density $\frac{\pi^{12}}{12!}$ . The centres of the balls in this packing form a lattice which is called Leech lattice. The Theorem proves that this is the densest possible lattice sphere packing in ${\mathbb R}^{24}$ . Before 2004, the optimal lattice sphere packings in ${\mathbb R}^n$ were known only for $n\leq 8$ . In a later work, Cohn, Kumar, Miller, Radchenko, and Viazovska proved that in fact Leech lattice sphere packing is the densest among all sphere packings in ${\mathbb R}^{24}$ , not necessarily lattice ones.

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

Go to the list of all theorems

Quartic rings can be explicitly parametrized

You need to know: Matrix, invertible matrix, determinant of a matrix, group, abelian group, group ${\mathbb Z}^n$ , ring, commutative ring, isomorphic groups and rings.

Background: Each commutative ring R is an abelian group with respect to addition. We say that R has rank n if this group is isomorphic to ${\mathbb Z}^n$ . Rings of rank $n=4$ are called quartic rings. An integral ternary quadratic form is an expression of the form $ax^4+bx^3y+cx^2y^2+dxy^3+ey^4$ with $a,b,c,d,e \in {\mathbb Z}$ . We say that two such forms A and B are linearly independent over ${\mathbb Q}$ if $uA+vB=0$ with rational $u,v$ is possible only if $u=v=0$ . Let $GL_n({\mathbb Z})$ be the set of invertible $n \times n$ matrices with integer entries, and let $GL_2^{\pm 1}({\mathbb Q})$ be the set of $2 \times 2$ matrices with rational entries and determinant $\pm 1$ .

The Theorem: On 29th February 2004, Manjul Bhargava submitted to the Annals of Mathematics a paper in which he proved the existence of a canonical bijection between isomorphism classes of nontrivial quartic rings and $GL_3({\mathbb Z}) \times GL^{\pm 1}_2({\mathbb Q})$ -equivalence classes of pairs $(A,B)$ of integral ternary quadratic forms where A and B are linearly independent over ${\mathbb Q}$ .

Short context: Explicit parametrizations for rings of ranks $n=2$ (known as quadratic rings) and $n=3$ (cubic rings) are relatively easy and well-known. The Theorem provides such a parametrization for quartic rings. In a later work, Bhargava also obtained explicit parametrization for rings of rank $n=5$ (quintic rings).

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

Go to the list of all theorems

The metric entropy is equivalent to the combinatorial dimension under minimal regularity

You need to know: Logarithm, supremum.

Background: Let $\Omega$ be a set, ${\cal A}$ be the set of all functions $f:\Omega \to {\mathbb R}$ , and let A be any subset of ${\cal A}$ . For k points $x_1, x_2, \dots, x_k \in \Omega$ and two functions f and g in ${\cal A}$ , define $d_{x_1,\dots x_k}(f,g)=\sqrt{\frac{1}{k}\sum\limits_{i=1}^k(f(x_i)-g(x_i))^2}$ . For any $t>0$ , let $N_{x_1,\dots x_k}(A,t)$ be the maximal n for which there exists functions $f_1,f_2,\dots f_n \in A$ such that $d_{x_1,\dots x_k}(f_i,f_j) \geq t$ for all $i \neq j$ . The quantity $D(A,t) := \log\left( \sup\limits_{k} \sup\limits_{x_1,\dots x_k} N_{x_1,\dots x_k}(A,t)\right)$ is called the Koltchinskii–Pollard entropy, or just metric entropy of A.

We say that a subset $\sigma$ of $\Omega$ is t-shattered by A if there exists a function h on $\sigma$ such that, given any decomposition $\sigma=\sigma_1 \cup \sigma_2$ with $\sigma_1 \cap \sigma_2 = \emptyset$ , one can find a function $f \in A$ with $f(x) \leq h(x)$ if $x \in \sigma_1$ but $f(x) \geq h(x) + t$ if $x \in \sigma_2$ . The combinatorial dimension $v(A,t)$ of A is the maximal cardinality of a set t-shattered by A.

The Theorem: On 26th January 2004, Mark Rudelson and Roman Vershynin submitted to the Annals of Mathematics a paper in which they proved that if there exists $b>1$ such that $v(A,bt) \leq \frac{1}{2}v(A,t), \, \forall t>0$ , then inequalities $c \cdot v(A, 2t) \leq D(A, t) \leq C \cdot v(A, ct)$ hold for all $t > 0$ , where $c > 0$ is an absolute constant, and C depends only on b.

Short context: The condition $v(A,bt) \leq \frac{1}{2}v(A,t), \, \forall t>0$ in the Theorem is known as the minimal regularity condition, and it is known that the conclusion of the Theorem does not hold without it. The Theorem shows that, under this condition, two ways of measuring “how large the set of functions is” are equivalent, up to the constant factors.

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

Go to the list of all theorems

The number of distinct products in N by N multiplication table

You need to know: Basic arithmetic, logarithm.

Background: For positive integer N, let $M(N)$ denote the number of distinct integers n which can be written as $n=a\cdot b$ , where a and b are positive integers not exceeding N.

The Theorem: On 18th January 2004, Kevin Ford submitted to arxiv a paper in which he proved, among other results, the existence of positive constants $c_1$ and $c_2$ such that inequality $c_1\frac{N^2}{(\log N)^\delta(\log\log N)^{3/2}} \leq M(N) \leq c_2\frac{N^2}{(\log N)^\delta(\log\log N)^{3/2}}$ holds for all N, where $\delta=1-\frac{1+\log\log 2}{\log 2}=0.08607...$ .

Short context: The number $M(N)$ of distinct products in $N\times N$ multiplication table has been studied starting since 1955, when Erdős proved that $\lim\limits_{N\to\infty}\frac{M(N)}{N^2}=0$ . However, exactly how fast $M(N)$ grows was an open question, answered by the Theorem. In fact, this result is only one out of many corollaries of a deep theory developed by Ford for estimating the number $H(x,y,z)$ of positive integers $n \leq x$ having a divisor in $(y,z]$ and the number $H_r(x,y,z)$ of positive integers $n \leq x$ having exactly r such divisors.

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

Go to the list of all theorems

There exists an embedded genus-one helicoid in R^3

You need to know: Surface, boundary of a surface, area of a surface, compact surface, total curvature of a surface, homeomorphic surfaces.

Background: A surface $M \subset {\mathbb R}^3$ is called a minimal surface if every point $p \in M$ has a neighbourhood S, with boundary B, such that S has a minimal area out of all surfaces S’ with the same boundary B. A surface $M \subset {\mathbb R}^3$ is called properly embedded in ${\mathbb R}^3$ , if it has no boundary, no self-intersections, and its intersection with any compact subset of ${\mathbb R}^3$ is compact. A helicoid is the surface defined by equations $x = s \cos (\alpha t), \,\, y = s \sin (\alpha t), \,\, z=t,$ where $\alpha$ is a constant, and $s,t$ are real parameters, ranging from $-\infty$ to $\infty$ . A surface is said to have finite topology if it is homeomorphic to a compact surface with a finite number of points removed.

The Theorem: On 8th January 2004, Matthias Weber, David Hoffman, and Michael Wolf submitted to arxiv a paper in which they proved the existence of a properly embedded minimal surface in ${\mathbb R}^3$ with finite topology and infinite total curvature, which is not a helicoid.

Short context: Helicoid, described by Euler in 1774, is one of the simplest non-trivial examples of minimal surfaces, and it is unique in many ways. In particular, Meeks III and Rosenberg proved that it, together with a plane, are the only examples of properly embedded simply connected minimal surfaces in ${\mathbb R}^3$ . Before 2004, there was a possibility that helicoid is also the only properly embedded minimal surface in ${\mathbb R}^3$ with finite topology and infinite total curvature. The Theorem, however, proves the existence of at least one more such surface. It looks like a helicoid with a hole and have got a name “embedded genus one helicoid”.

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

Go to the list of all theorems

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

Shape theorem holds in Kesten-Sidoravicius model for the infection spread

You need to know: Integer lattice ${\mathbb Z}^d$ , continuous time simple random walk on ${\mathbb Z}^d$ , jump rate, independent identically distributed (i.i.d.) random variables, Poisson distribution, almost sure convergence, compact convex set.

Background: At time $0$ , let us put $n_x$ “A-particles” at each $x\in{\mathbb Z}^d$ , where $n_x$ are i.i.d. random variables following Poisson distribution with mean $\mu$ . We also put a finite number of “B-particles” in arbitrary (non-random) positions on ${\mathbb Z}^d$ . Then each A-particle and each B-particle performs a continuous time simple random walk on ${\mathbb Z}^d$ , with jump rates $D_A$ and $D_B$ , respectively. The walks are independent, except that when a B-particle and an A-particle coincide, the latter turns into the former. Bet $B'(t)$ be the set of all locations $x\in{\mathbb Z}^d$ visited by a B-particle during $[0,t]$ , and let $B(t) = B'(t)+[-1/2, 1/2]^d$ .

The Theorem: On 31st December 2003, Harry Kesten and Vladas Sidoravicius submitted to arxiv a paper in which they proved the existence of a nonrandom, compact, convex set $B_0 \subset {\mathbb R}^d$ such that for all $\epsilon > 0$ , inclusion $(1-\epsilon)B_0 \subset \frac{1}{t}B(t) \subset (1+\epsilon)B_0$ holds almost surely as $t\to\infty$ .

Short context: In the model above, B-particles model organisms affected by an infection, A-particles model unaffected organisms, and the Theorem proves that in the limit the region affected by infection converges to a non-random shape growing at linear rate.

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

Go to the list of all theorems

The Füredi-Hajnal Conjecture and the Stanley–Wilf Conjecture are true

You need to know: Matrix, submatrix, $O(n)$ notation, permutation of $\{1,2,\dots,n\}$ .

Background: Let A and P be $0$ – $1$ matrices (that is, matrices with all entries $0$ or $1$ ). We say that A contains the $k \times l$ matrix P with entries $p_{ij}$ if there exists a $k \times l$ submatrix D of A with entries $d_{ij}$ such that $d_{ij} = 1$ whenever $p_{ij} = 1$ . Otherwise we say that A avoids P. Let $f(n, P)$ be the maximum number of 1-entries in an $n \times n$ $0$ – $1$ matrix avoiding P. A $0$ – $1$ matrix P is called a permutation matrix if it has exactly one entry of $1$ in each row and each column and $0$ -s elsewhere.

The Theorem: On 18th December 2003, Adam Marcus and Gábor Tardos submitted to the Journal of Combinatorial Theory, Series A a paper in which they proved that for all permutation matrices P we have $f(n, P) = O(n)$ .

Short context: A permutation of $\{1,2,\dots,n\}$ is called an n-permutation. We say that an n-permutation $\sigma$ contains a k-permutation $\pi$ if there exist integers $1\leq x_1 < \dots < x_k \leq n$ such that for all $1 \leq i,j \leq k$ we have $\sigma(x_i) < \sigma(x_j)$ if and only if $\pi(i) < \pi(j)$ . Otherwise, we say that $\sigma$ avoids $\pi$ . For a fixed permutation $\pi$ , let $S_n(\pi)$ be the number of n-permutations avoiding $\pi$ . In the late 1980-s, Stanley and Wilf conjectured that for all $\pi$ there exists a constant $c_\pi$ such that $S_n(\pi) \leq c_\pi^n$ for all n. In 2000, Klazar proved that this conjecture follows from the 1992 conjecture of Füredi and Hajnal that $f(n, P) = O(n)$ for permutation matrices P. The Theorem confirms the Füredi-Hajnal Conjecture and hence the Stanley–Wilf Conjecture.

Links: The original paper is available here.

Go to the list of all theorems

Translation invariant SL(n) equivariant valuations are difference operators

You need to know: Euclidean space ${\mathbb R}^n$ , matrix, determinant of a matrix, set $SL(n)$ of $n\times n$ matrices with determinant 1, viewed as operators in ${\mathbb R}^n$ , Minkowski addition of sets in ${\mathbb R}^n$ : $A+B=\{a+b\,|\,a\in A, b\in B\}$ , their multiplication by real constants $cA=\{ca\,|\,a\in A\}$ , convex body in ${\mathbb R}^n$ , convex polytope in ${\mathbb R}^n$ .

Background: Let ${\cal K}^n$ and ${\cal P}^n$ denote the sets of convex bodies and convex polytopes in ${\mathbb R}^n$ , respectively. Operator $Z:{\cal K}^n \to {\cal K}^n$ is called a Minkowski valuation if $Z(K_1) + Z(K_2) = Z(K_1 \cup K_2) + Z(K_1 \cap K_2)$ , whenever $K_1, K_2, K_1 \cup K_2 \in {\cal K}^n$ and + denotes Minkowski addition. $Z$ is called $SL(n)$ equivariant, if $Z(\phi K) = \phi Z(K)$ for all $\phi \in SL(n)$ , and it is called translation invariant, if $Z(K+x)=Z(K)$ for all $x\in {\mathbb R}^n$ . The difference operator $D:{\cal K}^n \to {\cal K}^n$ is the one which transforms every $K \in {\cal K}$ into $D(K) = K + (-K)$ .

The Theorem: On 17th December 2003, Monika Ludwig submitted to the Transactions of the American Mathematical Society a paper in which she proved, among other results, that if $Z:{\cal P}^n \to {\cal K}^n$ , $n\geq 2$ is a translation invariant, $SL(n)$ equivariant Minkowski valuation, then there exists a constant $c\geq 0$ such that $Z(P)=cD(P)$ for every $P\in {\cal P}^n$ .

Short context: Valuations played central role in Dehn 1901 solution of Hilbert 3rd problem. In 1957, Hadwiger gave a complete characterisation of continuous and rigid motion invariant valuations. The Theorem characterises translation invariant, $SL(n)$ equivariant Minkowski valuations. Operator $Z:{\cal K}^n \to {\cal K}^n$ is called homogeneous of degree $r \in {\mathbb R}$ if $Z(s K) = s r Z(K)$ for $s \geq 0$ . In fact, the Theorem is a consequence of a more general result which gives a complete characterisation of all homogeneous $SL(n)$ equivariant Minkowski valuations, not necessary translation invariant.

Links: The original paper is available here.

Go to the list of all theorems