Upper bound 2^(n+o(n)) holds in the Erdős-Szekeres “Happy Ending” conjecture

You need to know: Elementary geometry, convex n-gon, notation $\log_2 n$ for logarithm of n with base 2, $o(n)$ notation.

Background: We say that m points on the plane are in general position if no three of them are on a line. For every integer $n\geq 3$ , let $\text{ES}(n)$ be the minimal integer m, such that any set of m points in the plane in general position contains n points which are the vertices of a convex n-gon.

The Theorem: On 29th April 2016, Andrew Suk submitted to arxiv a paper in which he proved the existence of absolute constant $n_0$ such that $\text{ES}(n)\leq 2^{n+6n^{2/3}\log_2 n}$ for all $n\geq n_0$ .

Short context: In 1935, Erdős and Szekeres proved that $ES(n)$ is finite for $n\geq 3$ . In fact, they proved an explicit upper bound for $ES(n)$ growing as $4^{n+o(n)}$ . In 1960, they proved the lower bound $ES(n)>2^{n-2}$ and conjectured that in fact $ES(n)=2^{n-2}+1$ . This became known as the Erdős-Szekeres conjecture, or the “Happy Ending” conjecture. It is known to hold for $n\leq 6$ but is open for all $n>6$ . The Theorem dramatically improves the upper bound for $ES(n)$ from $4^{n+o(n)}$ to $2^{n+o(n)}$ , thus establishing the conjecture up to the $o(n)$ term in the exponent.

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

Go to the list of all theorems

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

You need to know: Euclidean space ${\mathbb R}^n$ , norm $\|x\|=\sqrt{\sum_{i=1}^nx_i^2}$ of $x=(x_1,\dots,x_n)\in {\mathbb R}^n$ , open ball ball $B(x,R)=\{y\in {\mathbb R}^n: ||y-x||<R\}$ with centre $x\in {\mathbb R}^n$ and radius $R>0$ , origin $O=(0,0,\dots,0)\in{\mathbb R}^n$ , notation $|V|$ for the volume of set $V\subset {\mathbb R}^n$ , limit superior $\limsup$ , notation $n!=1\cdot 2 \cdot \dots \cdot n$ .

Background: Packing of congruent balls (also called sphere packing) in ${\mathbb R}^n$ is an (infinite) set S of non-overlapping open balls with the same radii. The upper density of a sphere packing S is $\Delta(S) := \limsup\limits_{R\to\infty} \frac{|S\cap B(O,R)|}{|B(O,R)|}$ . If the limit (as opposite to limsup) exists, $\Delta(S)$ is called the density of S.

The Theorem: On 21st March 2016, Henry Cohn, Abhinav Kumar, Stephen Miller, Danylo Radchenko, and Maryna Viazovska submitted to arxiv a paper in which they proved that no packing of congruent balls in ${\mathbb R}^{24}$ can have upper density greater than $\frac{\pi^{12}}{12!}$ .

Short context: Finding the densest possible packing of congruent balls in ${\mathbb R}^n$ is a fundamental problem in geometry. Because there is a packing in ${\mathbb R}^{24}$ (called the Leech lattice packing) with density $\frac{\pi^{12}}{12!}$ , the Theorem completely solves this problem in dimension $n=24$ . Earlier, it was only known that the Leech lattice is optimal among lattice packings. For general packings, the densest one was known, before 2016, only in dimensions $n\leq 3$ . Earlier in 2016, Viazovska solved this problem in dimension $n=8$ . The proof of the Theorem extends Viazovska’s arguments to the case $n=24$ .

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

Go to the list of all theorems

The E8 lattice gives the densest packing of congruent balls in 8-dimensional space

The Theorem: On 14th March 2016, Maryna Viazovska submitted to arxiv a paper in which she proved that no packing of congruent balls in ${\mathbb R}^8$ can have upper density greater than $\frac{\pi^4}{384}$ .

Short context: Finding the densest possible packing of congruent balls in ${\mathbb R}^n$ is a fundamental problem in geometry, which, before 2016, was solved only in dimensions $n\leq 3$ . Because there is a packing in ${\mathbb R}^8$ (called the $E_8$ -lattice packing) with density $\frac{\pi^4}{384}$ , the Theorem completely solves this problem in dimension $n=8$ . The proof is based on this theorem of Cohn and Elkies. In a later work, a similar method was used to solve this problem in dimension $n=24$ as well.

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

Go to the list of all theorems

The topological Tverberg conjecture is false

You need to know: Eucledean space ${\mathbb R}^d$ , continuous map $f: {\mathbb R}^m \to {\mathbb R}^d$ , image of a set under map f, polytope, face of a polytope, convex hull, prime numbers, power of a prime.

Background: An m-simplex, denoted $\Delta_m$ , is an m-dimensional polytope which is the convex hull of its $m+1$ vertices. The “topological Tverberg conjecture” states that for given integers $r\geq 2$ , $d \geq 1$ , $m \geq (r-1)(d+1)$ , and for any continuous map $f: \Delta_m \to {\mathbb R}^d$ , there are r pairwise disjoint faces of $\Delta_m$ whose images have a point in common.

The Theorem: On 1st February 2015, Florian Frick submitted to arxiv a paper in which he proved that the topological Tverberg conjecture is false for any r that is not a power of a prime and any dimension $d \geq 3r+1$ .

Short context: The topological Tverberg conjecture was formulated by Bárány, Shlosman and Szűcs in 1981, and was considered by many experts as a major open problem, a holy grail of topological combinatorics. The case when f is an affine map is equivalent to Tverberg’s 1966 theorem (hence the name of the conjecture). The conjecture was also known to hold when r is a prime or a power of a prime, and was commonly believed to be true in general. The Theorem refutes the conjecture.

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

Go to the list of all theorems

A compact, embedded self-similar shrinker in R^3 of genus 0 is a round sphere

You need to know: Euclidean space ${\mathbb R}^3$ , origin $O=(0,0,0)$ , inner product $\langle x,y \rangle$ in ${\mathbb R}^3$ , unit vector in ${\mathbb R}^3$ (the one with $\langle u,u \rangle = 1$ ), round sphere in ${\mathbb R}^3$ of radius r centred at $A \in {\mathbb R}^3$ (set of points on distance r from $A$ ), surface in ${\mathbb R}^3$ , connected surface, compact surface, curvature of a curve.

Background: Let $S$ be a surface embedded into ${\mathbb R}^3$ . For any point $x\in S$ , we can build a unit vector $u(x)$ perpendicular to S, choose any plain P containing $u(x)$ (called a normal plain), and measure the curvature $\kappa(x,P)$ at x of a curve which is the intersection of S and P. Let $k_1(x)$ and $k_2(x)$ be the minimum and maximum values of $\kappa(x,P)$ over all choices of normal plain P. The mean curvature of S at x is $H(x)=\frac{1}{2}(k_1(x)+k_2(x))$ . Surface S is called a self-similar shrinker if it satisfies the equation $H(x) = \frac{1}{2}\langle x,u(x) \rangle$ for every $x\in S$ . We say that surface S has genus $0$ if it is connected but cutting it along any closed curve makes it disconnected.

The Theorem: On 17th November 2014, Simon Brendle submitted to arxiv a paper in which he proved that the only compact, embedded self-similar shrinker in ${\mathbb R}^3$ of genus $0$ is the round sphere of radius 2 centred at the origin.

Short context: The classication of self-similar shrinkers is an important problem with implications for the analysis of singularities. The simplest example of a compact self-similar shrinker in ${\mathbb R}^3$ is the round sphere of radius 2 centred at the origin. The Theorem confirms a well-known conjecture that this is in fact the only example of a compact, embedded self-similar shrinker in ${\mathbb R}^3$ of genus $0$ . It is known that the assumptions that the surface is embedded and has genus $0$ are both necessary: if we remove any of them, we get more examples.

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

Go to the list of all theorems

The set of points in a rational polygon P not illuminated by any x in P is finite

You need to know: Polygon, angles measured in radians, angle of incidence, angle of reflection.

Background: Let P be a rational polygon, that is, polygon whose angles measured in radians are rational multiples of $\pi$ . For any point $x \in P$ (called a light source), consider a light ray starting from x and moving inside P, with the usual rule that the angle of incidence equals the angle of reflection. A point $x \in P$ is called illuminated if there is a light ray starting from x which passes through y.

The Theorem: On 10th July 2014, Samuel Lelievre, Thierry Monteil, and Barak Weiss
submitted to arxiv a paper in which they proved that in any rational polygon P, and for any point $x\in P$ there are at most finitely many points $y\in P$ which are not illuminated from light source x.

Short context: In 1969, Klee asked whether any point x in any polygon P illuminates the whole P. In 1995, Tokarsky answered this question negatively by constructing an example in which one point y is not illuminated. The Theorem states that, at least for rational polygons, only finitely many points can remain unilluminated. It is just one out of many corollaries of deep “Magic Wand Theorem” proved in 2013 by Eskin and Mirzakhani.

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

Go to the list of all theorems

Every point in an nd-polytope is the barycenter of n points in its d-faces

You need to know: Euclidean space ${\mathbb R}^m$ , barycenter $\frac{1}{n}\sum\limits_{i=1}^n p_i$ of n points $p_1, \dots, p_n$ in ${\mathbb R}^m$ , k-polytope (k-dimensional polytope) in ${\mathbb R}^m$ , face of a polytope, dimension of a face.

Background: The d-dimensional skeleton of a k-polytope P is the set of all faces of the polytope of dimension at most d.

The Theorem: On 16th December 2013, Michael Dobbins submitted to arxiv a paper in which he proved that for any nd-polytope P and for any point $p\in P$ , there are points $p_1, \dots, p_n$ in the d-dimensional skeleton S of P with barycenter $p$ .

Short context: The Theorem verifies a conjecture made by Tokuyama. In author’s words, the conjecture was originally motivated by the engineering problem of determining how counterweights can be attached to some 3-dimensional object to adjust its center of mass to reduce vibrations when the object moves.

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

Go to the list of all theorems

Integer superharmonic matrices have the Apollonian structure

You need to know: Matrix, matrix multiplication, transpose $A^T$ of matrix A, notation ${\mathbb Z}^2$ for the set of $2\times 1$ matrices $x=\begin{bmatrix}x_1\\x_2\end{bmatrix}$ with integer entries, norm $||x||=\sqrt{x_1^2+x_2^2}$ of $x\in{\mathbb Z}^2$ , real matrix (matrix with real entries), square matrix, symmetric matrix, trace of a square matrix (sum of its diagonal entries), positive semidefinite matrix, Euclidean plane ${\mathbb R}^2$ , lines and circles in the plane, tangent circles, notation $x=x_0$ for vertical line through the point $(x_0, 0)$ , notation $C((x,y),r)$ for the circle with centre $(x,y)\in{\mathbb R}^2$ and radius r, small o notation.

Background: For $x,y\in{\mathbb Z}^2$ we write $x\sim y$ if $||x-y||=1$ . For a function $g:{\mathbb Z}^2\to {\mathbb Z}$ , let $\Delta g(x) = \sum\limits_{y\sim x}(g(y)-g(x))$ . A $2\times 2$ matrix A is called integer superharmonic if there exists a function $g:{\mathbb Z}^2\to {\mathbb Z}$ such that $g(x) = \frac{1}{2}x^TAx+o(||x||^2)$ and $\Delta g(x) \leq 1$ for all $x\in {\mathbb Z}^2$ . Let $S_2$ be the set of all $2\times 2$ real symmetric matrices.

By general circle on the plane we mean circle or line. Every triple T of pairwise tangent general circles has exactly two general circles (called Soddy general circles) tangent to all three. An Apollonian circle packing (ACP) generated by T is a minimal collection of general circles containing T that is closed under the addition of Soddy general circles. For $k\in{\mathbb Z}$ , let ${\cal B}_k$ be the ACP generated by lines $x=2k$ , $x=2k+2$ and circle $C((2k+1,0),1)$ . Let ${\cal B}=\bigcup\limits_{k\in{\mathbb Z}}{\cal B}_k$ . To each circle $C((x,y),r) \in {\cal B}$ we associate the matrix $A_C =\frac{1}{2}\begin{bmatrix}r+x & y \\y & r-x\end{bmatrix}$ .

The Theorem: On 12th September 2013, Lionel Levine, Wesley Pegden, and Charles Smart submitted to arxiv a paper in which they proved that matrix $A\in S_2$ is integer superharmonic if and only if either $\text{trace}(A)\leq 2$ or there exists a circle $C\in{\cal B}$ such that matrix $A_C-A$ is positive semidefinite.

Short context: Integer superharmonic matrices arise from the theory of partial differential equations (PDE), and it was on open question to characterise them. The Theorem achieves this via connection to Apollonian circle packing, which, for non-specialist, looks like a totally unrelated area of mathematics. Such theorems are useful because they allow to apply methods and results from one area to a different one.

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

Go to the list of all theorems

For any C, not every finite metric space of negative type C-embeds into l1

You need to know: Metric space $(X,\rho)$ with metric $\rho$ , Euclidean space ${\mathbb R}^d$ , notation $l_1({\mathbb R}^d)$ for ${\mathbb R}^d$ with metric $\rho(x,y)=\sum\limits_{i=1}^n|x_i-y_i|$ .

Background: We say that a metric space $(X,\rho_X)$ can be embedded into metric space $(Y,\rho_Y)$ with distortion at most $\alpha$ (or $\alpha$ -embeds in short) if there exists a function $f:X\to Y$ such that $m \rho_X(x,y) \leq \rho_Y(f(x),f(y)) \leq M \rho_X(x,y), \, \forall x,y \in X$ , where $m,M>0$ are constants such that $\frac{M}{m}\leq \alpha$ . We say that metric space $(X,\rho)$ $\alpha$ -embeds in $l_1$ if it $\alpha$ -embeds in $l_1({\mathbb R}^d)$ for some d. We say that a finite metric space $(X,\rho)$ with elements $x_1, x_2, \dots, x_n$ is of negative type if for any real numbers $c_1, \dots, c_n$ with $\sum\limits_{i=1}^n c_i = 0$ we have $\sum\limits_{i=1}^n\sum\limits_{j=1}^n c_i c_j \rho(x_i, x_j) \leq 0$ .

The Theorem: On 20th May 2013, Subhash Khot and Nisheeth Vishnoi submitted to arxiv a paper in which they proved that for any $\delta>0$ and all sufficiently large n, there is an n-point metric space of negative type which cannot be embedded into $l_1$ with distortion less than $(\log \log n)^{1/6-\delta}$ .

Short context: Embeddings of metric spaces into each other with minimal distortion is and old well-studied topic. Embedding of finite metric spaces of negative type is especially important, see here for almost optimal distortion for embedding into ${\mathbb R}^d$ with usual $l_2$ metric. Goemans (in 1997) and Linial (in 2002) conjectured that every finite metric space of negative type embeds into $l_1$ with constant distortion. This became known as $(l_2^2, l_1, O(1))$ -conjecture, and, if true, would imply efficient constant-factor approximation algorithms for some important combinatorial problems. The Theorem disproves this conjecture.

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

Go to the list of all theorems

Finitely many rotations of any pyjama stripe can cover the plane

You need to know: Coordinate plane ${\mathbb R}^2$ , origin $O=(0,0)$ , rotation of the plane around a point.

Background: Let $||x||$ denote the distance from real number x to the nearest integer. For every $\epsilon>0$ , a “pyjama stripe” $S_\epsilon$ is the set of points $(x,y)\in{\mathbb R}^2$ such that $||x||\leq\epsilon$ . For any $\phi\in[0,\pi)$ , let $T_\phi$ be the rotation of ${\mathbb R}^2$ around the origin by angle $\phi$ , and let $T_\phi(S_\epsilon)$ be the image of pyjama stripe $S_\epsilon$ after this rotation.

The Theorem: On 7th May 2013, Freddie Manners submitted to arxiv a paper in which he proved that for every $\epsilon>0$ there exist a finite sequence $0\leq \phi_1 < \dots < \phi_k < \pi$ such that $\bigcup\limits_{i=1}^k T_{\phi_i}(S_\epsilon) = {\mathbb R}^2$ .

Short context: For any $\epsilon\in(0,1/2)$ , set $S_\epsilon$ consists of vertical strips of width $2\epsilon$ around every integer x-coordinate. It resemble the pattern on a pair of stripy pyjamas, hence the name “pyjama stripe”. The problem asking whether it is possible to cover the whole plane by finitely many rotations of the pyjama stripe around the origin is known as the pyjama problem. The Theorem answers this question in the affirmative.

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

Go to the list of all theorems