The Kadison-Singer problem has a positive solution

You need to know: Set ${\mathbb C}$ of complex numbers, complex conjugate $\bar{z}$ and absolute value $|z|$ of $z\in {\mathbb C}$ .

Background: Let ${\mathbb C}^d$ be the set of vectors $x=(x_1,\dots,x_d)$ with complex components $x_i$ . Denote $\langle x,y \rangle = \sum\limits_{i=1}^d x_i \bar{y_i}$ the inner product in ${\mathbb C}^d$ . Let $||x||=\sqrt{\langle x,x \rangle}$ be the norm in ${\mathbb C}^d$ . We say that $u\in {\mathbb C}^d$ is a unit vector if $||u||=1$ .

The Theorem: On 17th June 2013, Adam Marcus, Daniel Spielman, and Nikhil Srivastava submitted to arxiv a paper in which they proved the following result. There exist universal constants $\eta\geq 2$ and $\theta>0$ so that the following holds. Let $w_1,\dots,w_m \in {\mathbb C}^d$ satisfy $||w_i|| \leq 1$ for all i and suppose $\sum\limits_{i=1}^m |\langle u,w_i \rangle|^2=\eta$ for every unit vector $u\in {\mathbb C}^d$ . Then there exists a partition $S_1, S_2$ of $\{1,\dots,m\}$ so that $\sum\limits_{i\in S_j} |\langle u,w_i \rangle|^2 \leq \eta - \theta$ , for every unit vector $u\in {\mathbb C}^d$ and each $j\in\{1,2\}$ .

Short context: The statement of the Theorem is one of many equivalent formulations of famous Kadison-Singer problem. In was posed in 1959 in the language of functional analysis. Later, it was discovered that numerous open problems in pure mathematics, applied mathematics, engineering and computer science are all equivalent to this problem. Hence, it was sufficient to solve one of these problems to solve them all. This is what the Theorem achieves!

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

For any finite subset S of R^n, there exists a quasiregular map from R^n onto R^n\S

You need to know: Euclidean space ${\mathbb R}^n$ , norm $||x|| = \sqrt{\sum_{i=1}^n x_i^2}$ in ${\mathbb R}^n$ , linear map $D: {\mathbb R}^n \to {\mathbb R}^n$ , matrix, determinant $\text{det}(A)$ of $n\times n$ matrix A, map from set $S_1$ onto set $S_2$ , notation $S_1 \setminus S_2$ for set difference.

Background: A function $f:{\mathbb R}^n \to {\mathbb R}^n$ is called differentiable at $x\in{\mathbb R}^n$ if there exists a linear map $D_{f.x}: {\mathbb R}^n \to {\mathbb R}^n$ such that $\lim\limits_{h\to 0}\frac{||f(x+h)-f(x)-D_{f,x}(h)||}{||h||}=0$ . Let $||D_{f.x}||=\max\limits_{y\in{\mathbb R}^n}\frac{||D_{f.x}(y)||}{||y||}$ be the norm of $D_{f.x}$ . Function f can be written as $f=(f_1,\dots,f_n)$ with $f_i:{\mathbb R}^n \to {\mathbb R}$ , $1\leq i \leq n$ . If f is differntiable at $x=(x_1,\dots, x_n)$ then all partial derivatives $\frac{\partial f_i}{\partial x_j}$ exist for $1\leq i,j \leq n$ . Let $J_{f,x}$ be the $n\times n$ matrix with entries $\frac{\partial f_i}{\partial x_j}$ . A function $f:{\mathbb R}^n \to {\mathbb R}^n$ , differentiable at every $x\in{\mathbb R}^n$ , is called K-quasiregular if $||D_{f.x}||^n \leq K|\text{det}(J_{f,x})|$ for all $x\in {\mathbb R}^n$ . f is called quasiregular if it is K-quasiregular for some $K\geq 1$ .

The Theorem: On 25th April 2013, David Drasin and Pekka Pankka submitted to arxiv a paper in which they proved that, given integer $n\geq 3$ , and any finite set $S\subset {\mathbb R}^n$ , there exists a quasiregular map from ${\mathbb R}^n$ onto ${\mathbb R}^n \setminus S$ .

Short context: Quasiregular mappings are natural higher dimensional analogues for
holomorphic functions (differentiable functions in complex variables). In 1980, Rickman proved that given any $K>1$ and $n\geq 2$ there exists q depending only on K and n so that a non-constant K-quasiregular mapping $f:{\mathbb R}^n \to {\mathbb R}^n$ omits at most q points. The Theorem states that this result is sharp in all dimensions $n\geq 3$ . Earlier, the Theorem was known to hold only for $n=3$ , and also for all $n$ if S is a one-element set.

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

Go to the list of all theorems

The converse to the Rademacher theorem holds if and only if m>=n

You need to know: Euclidean space ${\mathbb R}^n$ , norm $||x||_n = \sqrt{\sum_{i=1}^n x_i^2}$ in ${\mathbb R}^n$ , linear map $D: {\mathbb R}^n \to {\mathbb R}^m$ , Lebesgue null set (set of Lebesgue measure $0$ ) in ${\mathbb R}^n$ .

Background: Let n and m be positive integers. A function of several real variables $f:{\mathbb R}^n \to {\mathbb R}^m$ is called differentiable at a point $x_0\in{\mathbb R}^n$ if there exists a linear map $D: {\mathbb R}^n \to {\mathbb R}^m$ such that $\lim\limits_{h\to 0}\frac{||f(x_0+h)-f(x_0)-D(h)||_m}{||h||_n}=0$ . A function $f:{\mathbb R}^n \to {\mathbb R}^m$ is called Lipschitz if there exists a constant $K\geq 0$ such that $||f(x)-f(y)||_m \leq K ||x-y||_n$ for all $x,y \in {\mathbb R}^n$ .

The Theorem: On 25th April 2013, David Preiss and Gareth Speight submitted to arxiv and Inventiones Mathematicae a paper in which they proved that, for every integer $n>1$ , there exists a Lebesgue null set $N \subseteq {\mathbb R}^n$ such that every Lipschitz function $f:{\mathbb R}^n \to {\mathbb R}^{n-1}$ is differentiable at some point $x_0\in N$ .

Short context: The classical Rademacher theorem states that if a Lipschitz function $f:{\mathbb R}^n \to {\mathbb R}^m$ is differentiable at no point of a set $A \subset {\mathbb R}^n$ , then A must be Lebesgue null. The natural converse of this statement asks: given a Lebesgue null set $A \subset {\mathbb R}^n$ , does there exist a Lipschitz function $f:{\mathbb R}^n \to {\mathbb R}^m$ which is differentiable at no point of A? After efforts of many researchers, it was known by 2013 that the answer is “Yes” if $m\geq n$ and “No” if $m\leq n-2$ , leaving open only the case $m=n-1$ . The Theorem solves this remaining case: the answer is “No”. Hence, the the answer is “Yes” if and only if $m\geq n$ .

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

Go to the list of all theorems

There exist constant C and infinitely many pairs of primes p,q with 0<q-p<C

You need to know: Prime numbers.

Background: Let $p_n$ denotes the n-th prime number.

The Theorem: On 17th April 2013, Yitang Zhang submitted to the Annals of Mathematics a paper in which he proved the existence of constant $C<\infty$ , such that $p_{n+1}-p_n \leq C$ for infinitely many values of n. The proof implies that one can take $C=7\cdot 10^7$ .

Short context: Famous twin prime conjecture states that $p_{n+1}-p_n=2$ for infinitely many n, and is wide open. Before 2013, it was not even known that $p_{n+1}-p_n\leq C$ infinitely often for any finite constant C. See here and here for best previous upper bounds on $p_{n+1}-p_n$ . The Theorem proves that $p_{n+1}-p_n \leq C$ infinitely often for $C=7\cdot 10^7$ . It initiated work of many researchers to improve the constant C in it. In a reasonably short time, the constant has been improved to $C=600$ and then to $C=246$ .

Links: The original paper is available here.

Go to the list of all theorems

There exist infinite families of regular bipartite Ramanujan graphs of every degree d>=3

You need to know: Graph, bipartite graph, d-regular graph, adjacency matrix of a graph, eigenvalue of a matrix, limits.

Background: Let G be a d-regular bipartite graph and let A be its adjacency matrix. It is known that $d$ and $-d$ are always eigenvalues of A, which are called the trivial eigenvalues. We say that a d-regular bipartite graph is Ramanujan if all of its nontrivial eigenvalues lie between $-2\sqrt{d-1}$ and $2\sqrt{d-1}$ .

The Theorem: On 15th April 2013, Adam Marcus, Daniel Spielman, and Nikhil Srivastava submitted to arxiv a paper in which they proved that for every $d\geq 3$ there exists an infinite sequence of d-regular bipartite Ramanujan graphs.

Short context: Ramanujan graphs have various good properties, like being sparse but “highly connected”. Infinite families of d-regular Ramanujan graphs have been constructed by many authors, but, before 2013, such families where known to exist only if $d-1$ is a power of a prime number. The Theorem proves the existence of infinitely many d-regular bipartite Ramanujan graphs for every degree $d\geq 3$ .

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

Go to the list of all theorems

There exist nontrivial q-Steiner systems with t >= 2.

You need to know: field, vector space over a field, subspace of a vector space, dimension of a vector space, finite field ${\mathbb F}_q$ .

Background: Let ${\mathbb F}_q^n$ be a vector space of dimension n over the finite field ${\mathbb F}_q$ . A q-Steiner system, denoted $S_q(t,k,n)$ , is a set S of k-dimensional subspaces of ${\mathbb F}_q^n$ such that each t-dimensional subspace of ${\mathbb F}_q^n$ is contained in exactly one element of S. A q-Steiner system is called trivial if $t=k$ or $k=n$ and non-trivial otherwise.

The Theorem: On 4th April 2013, Michael Braun, Tuvi Etzion, Patric Ostergard, Alexander Vardy, and Alfred Wassermann submitted to arxiv a paper in which they proved the existence of non-trivial q-Steiner systems with $t>2$ . In fact, they proved the existence of over 500 different $S_2(2,3,13)$ q-Steiner systems.

Short context: Let V be a set with n elements, and let $k\geq 2$ . A Steiner system $S(t,k,n)$ is a collection of k-subsets of V, called blocks, such that each t-subset of V is contained in exactly one block. Steiner systems are among the most beautiful and well-studied structures in combinatorics, see here. In 1974, Cameron suggested to study $S_q(t,k,n)$ , a natural analogue of Steiner system over finite fields. However, despite efforts of many researchers, such systems has been known only for $t=1$ , and in the trivial cases $t=k$ and $k=n$ . The Theorem provides us with first examples of non-trivial q-Steiner systems with $t\geq 2$ .

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

Go to the list of all theorems

Multidimensional generalisation of the Schmidt conjecture is true

You need to know: Euclidean space ${\mathbb R}^n$ , notation ${\mathbb N}$ for the set of positive integers. In addition, you need to know the concept of Hausdorff dimension of set $A\subset {\mathbb R}^n$ to understand the “moreover” part of the Theorem.

Background: For $x\in{\mathbb R}$ , let $||x||$ denote the distance from x to the nearest integer. Let ${\cal R}_n \subset {\mathbb R}^n$ be the set of $r=(r_1, \dots, r_n)$ such that $r_i\geq 0, \, i=1,\dots,n$ and $\sum\limits_{i=1}^n r_i=1$ . Given $\textbf{r}\in {\cal R}_n$ , we say that point $\textbf{y}=(y_1,\dots, y_n) \in {\mathbb R}^n$ is $\textbf{r}$ -badly approximable if there exists $c=c(\textbf{y})>0$ such that $\max\limits_{1 \leq i \leq n}||qy_i||^{1/r_i} \geq c/q$ for all $q \in {\mathbb N}$ , with convention that $||qy_i||^{1/0}=0$ . Let Bad(r) be be set of all $\textbf{r}$ -badly approximable points in ${\mathbb R}^n$ .

The Theorem: On 2nd April 2013, Victor Beresnevich submitted to arxiv a paper in which he proved that for any finite subset $W\subset {\cal R}_n$ , the set $\bigcap\limits_{\textbf{r}\in W} \textbf{Bad(r)}$ is non-empty. Moreover, this set has Hausdorff dimension n.

Short context: A real number x is said to be badly approximable if there exists a constant $c(x)>0$ such that $||qx|| > c(x)/q$ for all $q \in {\mathbb N}$ . Sets Bad(r) are natural generalisations containing n-tuples $(y_1, \dots, y_n)$ of simultaneously badly approximable numbers. In 1983, Schmidt conjectured that $\textbf{Bad}\left(\frac{1}{3}, \frac{2}{3}\right) \cap \textbf{Bad}\left(\frac{2}{3}, \frac{1}{3}\right) \neq \emptyset$ . In 2011, Badziahin, Pollington, and Velani proved the $n=2$ case of the Theorem, which implies the Schmidt’s conjecture as a special case. The Theorem is a generalisation of this result to all dimensions.

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

Go to the list of all theorems

The Triangulation Conjecture is false in all dimensions n >= 5

You need to know: Polytope, vertex of a polytope, face of a polytope, n-dimensional topological manifold, closed manifold, homeomorphism.

Background: A k-simplex is a k-dimensional polytope which is the convex hull of its $k+1$ vertices. A simplicial complex K is a set of simplices such that (i) every face of a simplex from K is also in K, and (ii) the non-empty intersection of any two simplices in K is a face of both of them. A simplicial complex K is called locally finite if each vertex of K belongs only to finitely many simplices in K. A simplicial triangulation is a homeomorphism to a locally finite simplicial complex.

The Theorem: On 10th March 2013, Ciprian Manolescu submitted to arxiv a paper in which he proved that for every $n\geq 5$ , there exists a closed n-dimensional topological manifold that does not admit a simplicial triangulation.

Short context: It is known that any two-dimensional surface can be approximated by gluing together triangles. The Triangulation Conjecture (in dimension n) states that every n-dimensional topological manifold has a simplicial triangulation. The conjecture is true for $n\leq 3$ , was known to be false in dimension four, and was open for $n\geq 5$ . The Theorem states that the conjecture is false for every $n\geq 5$ .

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

Go to the list of all theorems