4)log n random entries

You need to know: Euclidean space ${\mathbb R}^n$ , orthonormal vectors in ${\mathbb R}^n$ , matrix, transpose $A^T$ of matrix A, matrix multiplication, eigenvalue of a square matrix, rank of a matrix, basic probability theory, selecting uniformly at random.

Background: The singular value of matrix X is an eigenvalue of $XX^T$ , and denote $||X||_*$ the sum of all singular values of X. For positive integers $n_1,n_2$ , and $0<r \leq \min\{n_1,n_2\}$ , let $u_1,\dots u_r$ be a family of orthonormal vectors in ${\mathbb R}^{n_1}$ sampled uniformly at random among all such families. Let $v_1,\dots v_r$ be a similar random family of orthonormal vectors in ${\mathbb R}^{n_2}$ . Then $M=\sum\limits_{i=1}^r \sigma_i u_i v_i^T$ , where $\sigma_i$ are some (non-random) positive numbers, is a $n_1\times n_2$ matrix of rank r, which we call a random matrix from random orthogonal model.

The Theorem: On 29th May 2008, Emmanuel Candès and Benjamin Recht submitted to arxiv a paper in which they proved the following result. Let M be an $n_1\times n_2$ matrix of rank r sampled from the random orthogonal model, and put $n=max(n_1,n_2)$ . Suppose we observe m entries of M with locations $\Omega$ sampled uniformly at random. Then there are constants C and c such that if $m\geq Crn^{5/4}\log n$ , the minimizer to the problem $\min ||X||_* \,\,\, \text{s.t.} X_{ij}=M_{ij}, \, (i,j)\in \Omega$ is unique and equal to M with probability at least $1-cn^{-3}\log n$ .

Short context: Recovery of missing entries of low-rank matrices is central in many applications. The Theorem states that when we have only a small portion of random entries of random matrix of rank r, we can recover all other entries with high probability, by solving a simple convex optimisation problem, which can be done fast using existing software.

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

Go to the list of all theorems

Centered Hardy–Littlewood maximal inequality in R^d has no uniform bound

You need to know: Euclidean space ${\mathbb R}^d$ , integration in ${\mathbb R}^d$ , supremum $\sup$ , notation $|V|$ for the volume (Lebesgue measure) of set $V \subset {\mathbb R}^d$ .

Background: For $x=(x_1,\dots,x_d) \in {\mathbb R}^d$ , denote $||x||_\infty=\max\limits_{1\leq i \leq d}|x_i|$ . For $x\in {\mathbb R}^d$ and $r>0$ , let $Q(x,r)=\{y\in {\mathbb R}^d : ||y-x||_\infty \leq r\}$ . Let ${\cal L}^1({\mathbb R}^d)$ be the set of all functions $f:{\mathbb R}^d\to {\mathbb R}$ such that $\|f\|_1=\int_{{\mathbb R}^d} |f(x)| dx <\infty$ . For any $f \in {\cal L}^1({\mathbb R}^d)$ , let $M_f (x) = \sup\limits_{r>0}\frac{1}{|Q(x,r)|}\int_{Q(x,r)} |f(y)| dy$ . Let $c_d$ be the lowest constant $c$ such that inequality $\alpha|\{x\in {\mathbb R}^d : M_f(x) > \alpha\}| \leq c \|f\|_1$ holds for all ${\cal L}^1({\mathbb R}^d)$ and all $\alpha>0$ .

The Theorem: On 11th May 2008, Jesus Aldaz submitted to arxiv a paper in which he proved that $\lim\limits_{d\to\infty}c_d = \infty$ .

Short context: Inequality $\alpha|\{x\in {\mathbb R}^d : M_f(x) > \alpha\}| \leq c \|f\|_1$ is known as the centered Hardy–Littlewood maximal inequality for cubes in ${\mathbb R}^d$ , and has various applications in the theories of differentiation and integration. In 1983, Stein and Strömberg asked if it holds with the uniform bound, that is, with some constant c independent of the dimension. The Theorem gives negative answer to this question. Before 2008, it was only known that $c_1=\frac{11+\sqrt{61}}{12}$ and that $c_d \geq \left(\frac{1+2^{1/d}}{2}\right)^d$ for all d (note that $\left(\frac{1+2^{1/d}}{2}\right)^d<2$ for all d).

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

Go to the list of all theorems

The cost L_n of the mean-field TSP on n-vertex graph converges to 2.04…

You need to know: Graph, complete graph, limits, integration, notation $P$ for probability, random variable, distribution.

Background: In a complete graph on n vertices, let each edge $e$ be assigned independent random cost $C_e$ from a fixed distribution $\mu$ on the non-negative real numbers, such that $\lim\limits_{t \to 0^+} \frac{P(C_e<t)}{t} = 1$ . Let $L_n$ be the minimum sum of the edge costs of a cycle that visits each vertex precisely once. For any $x>0$ , let $y=y(x)$ be the unique real number such that $\left(1+\frac{x}{2}\right)e^{-x} + \left(1+\frac{y}{2}\right)e^{-y}=1$ . Let $L^*=\frac{1}{2}\int_0^\infty y(x)dx = 2.0415...$ .

The Theorem: On 3rd April 2008, Johan Wästlund submitted to Acta Mathematica a paper in which he proved that for any $\epsilon>0$ , $\lim\limits_{n\to \infty}P\left[\left|L_n - L^*\right|>\epsilon\right] = 0.$

Short context: Computing the minimum sum of the edge costs of a cycle that visits each vertex of a graph is a famous and important problem known as travelling salesman problem (TSP). A model in which the edge costs are random, chosen independently from a fixed distribution, is known as the mean field model of distance. The Theorem finds the limit of the optimal cost of the mean-field TSP for a general class of distributions, which contains, for example, uniform distribution on $[0, 1]$ or exponential with mean $1$ .

Links: The original paper is available here.

Go to the list of all theorems

The size of every Kakeya set in F^n, where F is a finite field, is at least C_n|F|^n

You need to know: Field, finite field, vector space over a field, dimension of a vector space. In addition, you need the concept of Hausdorff dimension of subsets of Euclidean space ${\mathbb R}^n$ for the context section.

Background: Let ${\mathbb F}$ be a finite field with $|{\mathbb F}|$ elements, and let ${\mathbb F}^n$ be a vector space over ${\mathbb F}$ of dimension n. A Kakeya set in ${\mathbb F}^n$ is a subset $K \subset {\mathbb F}^n$ such that for every $x\in {\mathbb F}^n$ there exists a point $y\in {\mathbb F}^n$ such that the set $L=\{y+a\cdot x\,|\,a\in {\mathbb F}\}$ (called a line) is contained in K.

The Theorem: On 16th March 2008, Zeev Dvir submitted to arxiv a paper in which he proved that the size of every Kakeya set in ${\mathbb F}^n$ is at least $C_n \cdot |{\mathbb F}|^{n}$ , where $C_n$ is a constant that depends only on $n$ .

Short context: Famous Kakeya conjecture states that every compact set $K \subset {\mathbb R}^n$ , which contains a line segment of unit length in every direction, must have Hausdorff dimension equal to n. This conjecture has connections to problems in number theory, harmonic analysis, and the analysis of partial differential equations, but remains open for all $n>2$ . In 1999, Wolff suggested to study its finite field analogue. The Theorem resolves the Kakeya conjecture is finite fields.

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

Go to the list of all theorems

De Giorgi’s conjecture fails in dimensions at least 9

You need to know: Euclidean space ${\mathbb R}^n$ , hyperplane in ${\mathbb R}^n$ , function $u:{\mathbb R}^n \to {\mathbb R}$ (function in n variables), partial derivatives of such function, differential equation.

Background: A level set of a function $u:{\mathbb R}^n \to {\mathbb R}$ is a set of the form $L_c(f)=\{(x_1, \dots, x_n)\,|\,u(x_1, \dots, x_n)=c\}$ for some constant $c\in{\mathbb R}$ . For a twice-differentiable function $u:{\mathbb R}^n \to {\mathbb R}$ , its Laplacian $\Delta u$ is $\Delta u = \frac{\partial^2 u}{\partial x_1^2} + \frac{\partial^2 u}{\partial x_2^2} + \dots + \frac{\partial^2 u}{\partial x_n^2}$ .

The Theorem: On 23rd January 2008, Manuel del Pino, Michał Kowalczyk, and Juncheng Wei submitted to the Annals of Mathematics a paper in which they proved that, for any $n\geq 9$ , there exists a solution $u:{\mathbb R}^n \to {\mathbb R}$ to differential equation $\Delta u=u^3-u$ such that (i) $|u|<1$ ; (ii) $\frac{\partial u}{\partial x_n}>0$ for every $x=(x_1, \dots, x_n)\in{\mathbb R}^n$ ; but (iii) the level sets of u are not hyperplanes.

Short context: Differential equation $\Delta u=u^3-u$ originates in the theory of phase transition, is important and well-studied. In 1978, De Giorgi conjectured that if $u:{\mathbb R}^n \to {\mathbb R}$ is a solution to this equation satisfying (i) and (ii), then all level sets of u are hyperplanes, at least if $n \leq 8$ . This conjecture, when true, allows to write down a formula for u easily. It is known to hold in dimensions $n\leq 3$ , and, under some additional conditions, in all dimensions $n \leq 8$ , see here. The Theorem proves that it fails in all dimensions $n \geq 9$ .

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

Go to the list of all theorems

n-digit integers can be multiplied in n log n 2^O(log*n) operations

You need to know: Integer multiplication, algorithm, running time of an algorithm, logarithm, big O notation.

Background: The iterated logarithm $\log^*$ is the unique function which has properties (i) $\log^*n =0$ if $n\leq 1$ and (ii) $\log^*n = 1+\log^*(\log n)$ if $n>1$ .

The Theorem: On 27th December 2007, Martin Fürer submitted to SIAM Journal on Computing a paper in which he presented a new algorithm for multiplying integers and proved that its running time is $n\log n 2^{O(\log^*(n))}$ for n-digit integers.

Short context: Integer multiplication is one of the basic operations in mathematics. Usual school method requires $O(n^2)$ operations for n-digit integers. In 1971, Schönhage and Strassen presented a much faster $O(n \log n \log\log n)$ algorithm, and conjectured that $O(n \log n)$ algorithm should exist. This algorithm remained the fastest one for 36 years. The Theorem presents a faster method whose running time is very close to $O(n \log n)$ . In a later work, David Harvey and Joris van der Hoeven removed the $2^{O(\log^*(n))}$ factor and presented the $O(n \log n)$ algorithm.

Links: The original paper is available here.

Go to the list of all theorems

First moment concentration of log-concave measures implies exponential concentration

You need to know: Euclidean space ${\mathbb R}^n$ , norm $\|x\|$ of $x\in{\mathbb R}^n$ , convex set $D\subset {\mathbb R}^n$ , convex function on D, probability measure $\mu$ on ${\mathbb R}^n$ , integration with respect to $\mu$ .

Background: A probability measure $\mu$ on ${\mathbb R}^n$ is called absolutely continuous if there exists function $g:{\mathbb R}^n \to {\mathbb R}$ such that $\mu(A)=\int_A g(x)dx$ for every measurable $A\subset {\mathbb R}^n$ . If set $D=\{x\in{\mathbb R}^n\,|\,g(x)>0\}$ is convex, and $-\log(g(x))$ is a convex function on D, then $\mu$ is called log-concave. Given a function $f:{\mathbb R}^n \to {\mathbb R}$ , we write $E_\mu(f)=\int_{{\mathbb R}^n}f d\mu$ , and $||f||_{L^1(\mu)} = E_\mu(|f|)$ . Function f is called 1-Lipschitz if $|f(x)-f(y)| \leq \|x-y\|$ for all $x,y \in {\mathbb R}^n$ . We say that $\mu$ satisfies First-Moment concentration if there exists $D>0$ such that for every 1-Lipschitz f we have $||f-E_\mu(f)||_{L^1(\mu)} \leq \frac{1}{D}$ .

The Theorem: On 26th December 2007, Emanuel Milman submitted to arxiv a paper in which he proved that for every absolutely continuous log-concave probability measure $\mu$ on ${\mathbb R}^n$ satisfying First-Moment concentration, and every 1-Lipschitz $f:{\mathbb R}^n \to {\mathbb R}$ , inequality $\mu(|f-E_\mu(f)| \geq t) \leq c \exp(-CDt)$ holds for all $t>0$ , where c and C are universal constants.

Short context: Let $x\in{\mathbb R}^n$ be selected at random with respect to measure $\mu$ , and f be some useful function we want to compute. In general, because x is random, $f(x)$ is also random and unpredictable. However, if the conclusion of the theorem (known as exponential concentration) holds, then $f(x) \approx E_\mu(f)$ with very high probability. This property looks much stronger than “just” first moment concentration. The Theorem states, however, that these concentrations are in fact equivalent! In fact, in the same paper authors studied several other notions of concentrations, some looks very week and some very strong, and proved that they are all equivalent for the log-concave $\mu$ .

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

Go to the list of all theorems

The Riemann zeta function can be computed at 1/2+it to within t^(-a) in time t^(4/13+o(1))

You need to know: Complex number, real part $\text{Re}(z)$ of complex number z, function of complex variable, meromorphic function, analytic continuation.

Background: For a complex number $z$ with $\text{Re}(z)>1$ , let $\zeta(z)=\sum\limits_{n=1}^\infty \frac{1}{n^z}$ . By analytic continuation, function $\zeta(z)$ can be extended to a meromorphic function on the whole complex plane, and it is called the Riemann zeta function.

The Theorem: On 30th November 2007, Ghaith Hiary submitted to arxiv a paper in which he proved that, given any constant $\lambda$ , there is an effectively computable constant $C=C(\lambda)$ and absolute constant k, such that for any $t>1$ the value of $\zeta\left(\frac{1}{2}+it\right)$ can be computed to within $\pm t^{-\lambda}$ using at most $C(\log t)^k t^{4/13}$ operations.

Short context: Riemann zeta function $\zeta$ is one of the most studied functions in mathematics, and is central to, for example, understanding the distribution of prime numbers. The values $\zeta(z)$ at line $z=\frac{1}{2}+it$ are particularly important. Before 2007, the fastest algorithm to approximately compute $\zeta\left(\frac{1}{2}+it\right)$ had running time $t^{1/3}=t^{0.333...}$ . The Theorem improves the exponent to $\frac{4}{13}\approx 0.307$ .

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

Go to the list of all theorems

The full list of connected properly embedded minimal planar domains in R^3

You need to know: Euclidean space ${\mathbb R}^3$ , rotation in ${\mathbb R}^3$ , rigid motion in ${\mathbb R}^3$ , surface in ${\mathbb R}^3$ , surface area, neighbourhood of a point in the surface, boundary, surface with and without self-intersections, compact subset of ${\mathbb R}^3$ , compact subset of a surface, connected surface.

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. We say that surface has genus $0$ if cutting it along any closed curve makes it disconnected. A planar domain is a connected surface that is noncompact and has genus $0$ .

The Theorem: On 8th November 2007, William Meeks III, Joaquin Perez, and Antonio Ros submitted to Annals of Mathematics a paper in which they proved that any connected properly embedded minimal planar domain M in ${\mathbb R}^3$ can be rotated such that, after rotation, it intersects every horizontal plane in a circle or in a line.

Short context: Minimal surfaces, ones that locally minimizes their areas, are among the most studied objects in geometry and topology. A trivial example of minimal surface is the plain. One of the simplest non-trivial examples, described by Euler in 1774, is a helicoid, see here. There are other examples like catenoid and one-parameter family $R_t$ of Riemann minimal examples. We will not define these surfaces here but mention that the main result in the paper of Meeks, Perez, and Ros is that, up to scaling and rigid motion, any connected properly embedded minimal planar domain M in ${\mathbb R}^3$ must be one of the examples listed above! Because the concusion of the Theorem was known to hold in all these examples, the Theorem follows.

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

Go to the list of all theorems

There exist pairs of primes at distance less than C(log p_n)^(0.5)(log log p_n)^2

You need to know: Prime numbers, logarithm, limit inferior $\liminf$ .

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

The Theorem: On 15th October 2007, Daniel Goldston, János Pintz, and Cem Yíldírím submitted to arxiv a paper in which they proved that $\liminf\limits_{n\to\infty}\frac{p_{n+1}-p_n}{\sqrt{\log p_n}(\log \log p_n)^2}<\infty$ .

Short context: Famous twin prime conjecture states that $p_{n+1}-p_n=2$ for infinitely many n, and is wide open. In an earlier work, Goldston, Pintz, and Yíldírím proved that $\liminf\limits_{n\to\infty}\frac{p_{n+1}-p_n}{\log p_n}=0$ , that is, there exist consecutive primes which are closer than $\epsilon\log p_n$ for any $\epsilon>0$ . The Theorem improves $\epsilon\log p_n$ to $\sqrt{\log p_n}(\log \log p_n)^2$ . Using methods developed in these papers, Zhang proved in 2013 that $p_{n+1}-p_n \leq B = 7\cdot 10^7$ infinitely often. This result was then improved to $B=246$ .