In Vicsek model, all agents will eventually move in the same direction

You need to know: Basic geometry (distance in the plane, vector addition), limits, connected graph.

Background: Consider n autonomous agents (points) which are moving in the plane with the same speed but with different directions. Fix constant $r>0$ . The agents are called neighbours at time t if the distance between them is at most r. At discrete time moments $t=0,1,2,\dots$ each agent’s direction is updated and become the average of its own direction and the directions of its neighbours. At any time moment t, let $G(t)$ be a graph with vertices being agents, in which neighbours connected by edges.

The Theorem: On 4th March 2002, Ali Jadbabaie, Jie Lin, and Stephen Moore submitted to IEEE Transactions on Automatic Control a paper in which they proved the following result. Assume that, in the model described above, there exists an infinite sequence of continuous, non-empty, bounded, non-intersecting time-intervals $[t_i, t'_i)$ , $i=0,1,2\dots$ , starting at $t_0 = 0$ , in which graph $G(t)$ is connected. Then in the limit all agents will eventually move in the same direction.

Short context: Coordination of groups of mobile autonomous agents in an important topic which attracted a lot of attention in the literature. It has applications in physics (e.g. the study of active matter), machine learning, etc. In 1995, Vicsek, Czirok, Ben Jacob, Cohen, and Schochet suggested the model described above, and performed a number of numerical simulations demonstrating that, after some time, the agents start moving in the same direction, despite the absence of central coordination. The Theorem provides a theoretical explanation for this observation.

Links: The original paper is available here.

Go to the list of all theorems

(log t)^(2/3) law holds for the two dimensional asymmetric simple exclusion process

You need to know: Set ${\mathbb Z}^2$ of points $x=(x_1, x_2)$ with integer coefficients, probability, independent random variables, exponential distribution, covariance $\text{cov}(X,Y)$ of random variables X and Y.

Background: At time $t=0$ , let us put, for each $x\in {\mathbb Z}^2$ , a particle in site x, independently and with probability $1/2$ . Then, for each particle p, independently generate a random variable $t_p$ from exponential distribution, wait for time $t_p$ , and then jump to an adjacent site up, down, or right, with probabilities $1/4, 1/4, 1/2$ , respectively, provided that the target site is unoccupied (and otherwise stay). This action is then repeated and performed in parallel for all particles. We call this asymmetric simple exclusion process (ASEP). For any $x\in {\mathbb Z}^2$ , let $\eta_x(t)$ be the number of particles (which can be $0$ or $1$ ) in position x at time t. Next define $D(t) = \frac{4}{t}\sum\limits_{x \in {\mathbb Z}^2} x_1^2 \cdot \text{cov}(\eta_x(t), \eta_{(0,0)}(0))$ , where $x_1$ is the first coordinate of x.

The Theorem: On 31st January 2002, Horng-Tzer Yau submitted to the Annals of Mathematics a paper in which he proved the existence of a constant $\gamma>0$ such that, for sufficiently small $\lambda>0$ , $\lambda^{-2}|\log \lambda|^{2/3}e^{-\gamma|\log\log\log \lambda|^2} \leq \int_0^{\infty}e^{-\lambda t}t D(t)dt \leq \lambda^{-2}|\log \lambda|^{2/3}e^{\gamma|\log\log\log \lambda|^2}.$

Short context: ASEP is one of the simplest models for modelling diffusion process, function $D(t)$ defined above is known as diffusion coefficient, and understanding how fast $D(t)$ grows with t is important for estimating the speed of diffusion process. The Theorem implies that $D(t)$ grows approximately as $(\log t)^{2/3}$ for large t, and can therefore be called “ $(\log t)^{2/3}$ law for ASEP”.

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

Go to the list of all theorems

The covering number of a uniformly bounded set of functions is exponential in its shattering dimension

You need to know: Probabilty measure $\mu$ on set $\Omega$ , norm $L_2(\mu)$ for functions on $\Omega$ .

Background: Let $\Omega$ be a set, and let $\mu$ be a probability measure on $\Omega$ . Let $B_1$ be the set of all functions $f:\Omega \to [-1,1]$ , and let A be any subset of $B_1$ . Denote $N(A,t,\mu)$ the covering number of A, that is, the minimal number of functions whose linear combination can approximate any function in A within an error t in the $L_2(\mu)$ norm.

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 shattering (or combinatorial) dimension $vc(A,t)$ of A is the maximal cardinality of a set t-shattered by A.

The Theorem: On 10th December 2001, Shahar Mendelson and Roman Vershynin submitted to Inventiones Mathematicae a paper in which they proved that $N(A, t,\mu) \leq \left(\frac{2}{t}\right)^{K \cdot vc(A,ct)}, \, 0<t<1,$ where K and c are positive absolute constants.

Short context: It is well-known that the covering numbers of a set are exponential in its linear algebraic dimension. The Theorem extends this result to shattering dimension, solving so-called Talagrand’s entropy problem. This result is especially useful because shattering dimension never exceeds linear algebraic dimension, and is often much smaller than it.

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

Go to the list of all theorems

Probability that Wiener sausages intersection volume is large decays fast

You need to know: d-dimensional Euclidean space ${\mathbb R}^d$ , volume in ${\mathbb R}^d$ , limits, basic probability theory, stochastic processes, independent stochastic processes, Wiener process in ${\mathbb R}^d$

Background: Let $W(t)$ be standard Wiener process in ${\mathbb R}^d$ . For $a>0$ and $t \geq 0$ , let $W_a(t) = \{ x \in {\mathbb R}^d \,|\,\exists s \in [0,t] : \rho(x,W(s)) \leq a \}$ , where $\rho$ is the distance in ${\mathbb R}^d$ . $W_a(t)$ is known as Wiener sausage. Let $S^a(t) = W_1^a(t) \cap W_2^a(t)$ be the intersection of two Wiener sausages corresponding to two independent Wiener processes starting at origin, and let $|S^a(t)|$ be its (d-dimensional) volume.

The Theorem: On 28th November 2001, Michiel van den Berg, Erwin Bolthausen and Frank den Hollander submitted to Annals of Mathematics a paper in which they proved that for every $a>0$ and $b>0$ , $\lim\limits_{t\to\infty}\frac{1}{t^{(d-2)/d}}\log P(|S^a(bt)|\geq t) = -C_{a,d,b}, \, d \geq 3$ where P denotes the probability, and $C_{a,d,b}>0$ is some constant depending on a, d, and b. Similarly, $\lim\limits_{t\to\infty}\frac{1}{\log t}\log P(|S^a(bt)|\geq t/\log t) = -C_b, \, d=2$ .

Short context: Let $a$ be fixed and denote $V_t=|S^a(t)|$ . The Theorem implies that, for large t, $P(V_{bt} \geq t)$ decays as $\text{exp}\left(-C t^{(d-2)/d}\right)$ for $d \geq 3$ . In other words, the probability that Wiener sausages intersection volume is large (larger than t after time bt) decays exponentially fast in t, with constant in the exponent $\frac{d-2}{d}$ . This gives us a good idea how the distribution of $V_t$ looks like. The Theorem resolves open questions asked by Khanin, Mazel, Shlosman, and Sinai in 1994.

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

Go to the list of all theorems

The size of set of simple sums and products of k distinct integers exceeds k^d

You need to know: The size $|S|$ of set S (that is, the number of elements in it), sum $\sum_{i=1}^k$ and product $\prod_{i=1}^k$ notations.

Background: Let $A=\{a_1, a_2, \dots, a_k\}$ be a set of k distinct integers, and let $S(A) = \left\{\sum_{i=1}^k \epsilon_i a_i \,|\,\epsilon_i = 0 \text{ or } 1\right\}$ and $\Pi(A) = \left\{\prod_{i=1}^k a_i^{\epsilon_i} \,|\,\epsilon_i = 0 \text{ or } 1\right\}$ be the set of all possible simple sums and products of elements of A, respectively. Let $g(k) = \min\limits_{A:|A|=k}(|S(A)|+|\Pi(A)|)$ .

The Theorem: On 27th November 2001, Mei-Chu Chang submitted to the Annals of Mathematics a paper in which she proved that for any $\epsilon>0$ there is a $k_0=k_0(\epsilon)$ such that $g(k) > k^{(1/2-\epsilon)\frac{\log k}{\log (\log k)}}$ for all $k\geq k_0$ .

Short context: In 1983, Erdős and Szemerédi conjectured that the set of sums $S(A)$ and set of products $\Pi(A)$ cannot both be small. Specifically, they conjectured that $g(k)$ grows faster than any polynomial in k, that is, for any d, there exists a constant $k_0=k_0(d)$ such that $g(k) > k^d$ for any $k \geq k_0(d)$ . The Theorem implies this conjecture and in fact provides a stronger lower bound on $g(k)$ . Because it is known that $g(k) < k^{c\frac{\log k}{\log (\log k)}}$ for some constant c, the bound in the Theorem is the best possible up to the constant factor in the exponent.

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

Go to the list of all theorems

The simplex algorithm has polynomial smoothed complexity

You need to know: The notion of an algorithm and its complexity (number of steps it needs to solve a problem), basic probability theory (expectation, standard deviation, Gaussian random variable), linear programming problem, simplex algorithm.

Background: Let A be an algorithm which solves some problem whose input $x$ is a vector in ${\mathbb R}^m$ for some m, with norm $||x||$ . Let $C_A(x)$ be the number of steps A works at input $x$ . The worst-case complexity of A is $f(n)=\max\limits_{x\in X_n}C_A(x)$ , where $X_n$ is the set of all possible inputs of bit-length n. The smoothed complexity of A is $f(n,\sigma) = \max\limits_{x\in X_n} E_g[C_A(x+(\sigma||x||)g]$ , where $(\sigma||x||)g$ is a vector of Gaussian random variables of mean $0$ and standard deviation $\sigma||x||$ , and $E_g$ is the corresponding expectation. We say that an algorithm A has polynomial smoothed complexity if $f(n,\sigma)$ is bounded by a polynomial in n and $1/\sigma$ .

The Theorem: On 19th November 2001, Daniel Spielman and Shang-Hua Teng submitted to arxiv a paper in which they introduced the notion of smoothed complexity and proved that simplex algorithm for linear programming problem has polynomial smoothed complexity.

Short context: The performance of algorithms are usually measured by their worst-case complexity. However, there are algorithms whose worst-case complexity grows exponentially fast, but which work fast for all inputs arising in practice. A prominent example of such an algorithm is the simplex method for linear programming problem. Spielman and Teng introduced smoothed complexity to measure worst-case expected performance of an algorithm under small random perturbations of its input. Because in practise input data are often subject to random noise, the Theorem provides theoretical explanation of good practical performance of the simplex method.

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

Go to the list of all theorems

Characterisation of linear recurrences whose ratio is integer infinitely often

You need to know: Set ${\mathbb N}$ of natural numbers, complex numbers, notation ${\mathbb C}[x]$ for the set of polynomials with complex coefficients.

Background: A linear recurrence is a sequence of complex numbers $\{G(n)\}_{n\in{\mathbb N}}$ such that $G(n+k)=c_0 G(n) + \dots + c_{k-1} G(n+k-1), \, n\in{\mathbb N}$ for some $k\geq 1$ and complex numbers $c_0, c_1, \dots, c_{k-1}$ .

The Theorem: On 12th November 2001, Pietro Corvaja and Umberto Zannier submitted to Inventiones Mathematicae a paper in which they proved that for any linear recurrences $F(n)$ and $G(n)$ such that $F(n)/G(n)$ is an integer for infinitely many values of n, there exists a nonzero polynomial $P(X) \in {\mathbb C}[X]$ and positive integers $q, r$ such that both sequences $\{P(n)F(qn+r)/G(qn+r)\}_{n\in{\mathbb N}}$ and $\{G(qn+r)/P(n)\}_{n\in{\mathbb N}}$ are linear recurrences.

Short context: In 1988, van der Poorten, confirming a conjecture of Pisot,
proved that if the ratio $F(n)/G(n)$ of linear recurrences $F(n), G(n)$ is an integer for all large n, then $F(n)/G(n)$ is itself a linear recurrence. In 1989, van der Poorten asked whether a similar result can be proved under much weaker assumption that $F(n)/G(n)$ is an integer infinitely open. This is what the Theorem achieves.

Links: The original paper is available here.

Go to the list of all theorems

Any sphere packing in R^8 has density at most 1.000001 pi^4/384

You need to know: Space ${\mathbb R}^n$ , notation $\|.\|$ for norm in ${\mathbb R}^n$ , origin $0=(0,0,\dots,0)\in{\mathbb R}^n$ , ball $B_n(0,R)$ with centre in the origin and radius R, volume $|B_n(0,R)|$ of this ball, notation $|A|$ for the number of elements in finite set A, scalar product $\langle x,t \rangle:=\sum_{i=1}^n x_it_i$ in ${\mathbb R}^n$ , set ${\mathbb C}$ of complex numbers, $i=\sqrt{-1}$ , Fourier transform $\hat{f}(t)=\int\limits_{{\mathbb R}^n} f(x) e^{-2\pi i \langle x,t \rangle}dx$ of an integrable function $f:{\mathbb R}^n \to {\mathbb C}$ .

Background: A set S of points in ${\mathbb R}^n$ such that $\|x-y\|\geq 2$ for all distinct $x,y \in S$ is called a sphere packing. The center density of a sphere packing S is $\delta(S) := \limsup\limits_{R\to\infty} \frac{|S\cap B_n(0,R)|}{|B_n(0,R)|}$ . The upper density of S is $\Delta(S) = \delta(S)|B_n(0,1)|$ .

A function $f:{\mathbb R}^n \to {\mathbb R}$ is called admissible if there exist positive constants $\epsilon$ , $C_1$ , $C_2$ such that $|f(x)|\leq \frac{C_1}{(1+\|x\|)^{n+\epsilon}}$ and $|\hat{f}(x)|\leq \frac{C_2}{(1+\|x\|)^{n+\epsilon}}$ for all $x\in{\mathbb R}^n$ .

The Theorem: On 1st October 2001, Henry Cohn and Noam Elkies submitted to the arxiv and Annals of Mathematics a paper in which they proved the following result. Suppose $f:{\mathbb R}^n \to {\mathbb R}$ is an admissible function, is not identically zero, and such that (i) $f(x)\leq 0$ for $\|x\|\geq 1$ , and (ii) $\hat{f}(t) \geq 0$ (which implies that $\hat{f}(t)$ is real) for all $t\in{\mathbb R}^n$ . Then the center density of any sphere packing in ${\mathbb R}^n$ is bounded above by $\frac{f(0)}{2^n\hat{f}(0)}$ .

Short context: Finding the densest possible sphere packing in ${\mathbb R}^n$ is a fundamental problem in geometry, which, before 2001, was solved only in dimensions $n\leq 3$ . The Theorem provides a general method for proving upper bounds for sphere packing densities. In the same paper, Cohn and Elkies used the Theorem to derive improved upper bounds in dimensions $4 \leq n \leq 36$ . In particular, for $n=8$ , they derive bound $1.000001\Delta_8$ , where $\Delta_8=\frac{\pi^4}{384}$ is the density of densest known packing. In later works (see here and here), the Theorem was used to fully solve the sphere packing problem in dimensions 8 and 24.

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

Go to the list of all theorems

The analytic capacity is semiadditive

You need to know: Compact set, notation $A\setminus B = \{x: x \in A, \, x\not\in B\}$ for set difference, $\sup$ notation for supremum, complex plane ${\mathbb C}$ , absolute value $|.|$ of a complex number, analytic function, notation $f(\infty)$ for $\lim\limits_{z\to\infty} f(z)$ .

Background: The analytic capacity of a compact subset E of complex plane ${\mathbb C}$ is defined as $\gamma(E) = \sup|f'(\infty)|$ where the supremum is taken over all analytic functions $f:C\setminus E \to C$ such that $|f|\leq 1$ on $C\setminus E$ , and $f'(\infty)=\lim\limits_{z\to\infty} z(f(z)-f(\infty))$ .

The Theorem: On 13th September 2001, Xavier Tolsa submitted to Acta Mathematica a paper in which he proved the existence of an absolute constant C such that $\gamma(E \cup F) \leq C(\gamma(E) + \gamma(F))$ for all compact sets E and F. In other words, the analytic capacity is semiadditive.

Short context: The question whether analytic capacity is semiadditive was raised by Vitushkin in 1960’s, who showed that a positive answer to this question would have important applications to the theory of rational approximation. The Theorem answers this question affirmatively. More generally, Tolsa proved that semiadditivity holds for any countable collection of sets $E_i$ with compact union.

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

Go to the list of all theorems

5n Minkowski symmetrizations transform convex body in R^n into near ball

You need to know: Space ${\mathbb R}^n$ , origin $(0,0,\dots,0)$ in ${\mathbb R}^n$ , ball in ${\mathbb R}^n$ , hyperplane in ${\mathbb R}^n$ , reflection of a point with respect to a hyperplane, convex body in ${\mathbb R}^n$

Background: For any convex body S in ${\mathbb R}^n$ , its Minkowski symmetrization $M_H(S)$ with respect to a hyperplane H going through the origin is the set of all midpoints of line segments $AB$ with $A\in S$ and $B$ being a reflection of some point in S with respect to H.

The Theorem: On 13th September 2001, Boáz Klartag submitted to the Annals of Mathematics a paper in which he proved that, for any $n \geq 2$ and any convex body $S \subset {\mathbb R}^n$ , there exist $5n$ Minkowski symmetrizations $M_1, M_2, \dots M_{5n}$ such that the convex body $S'=M_{5n}(M_{5n-1}(...M_2(M_1(S))\dots))$ contains a ball of radius $r_1$ , but is contained in a ball of radius $r_2$ , with $\frac{r_1}{r_2} = \left(1-c\frac{|\ln\ln n|}{\sqrt{\ln n}}\right)/\left(1+c\frac{|\ln\ln n|}{\sqrt{\ln n}}\right)$ , where c is a universal constant, independent of n and S.

Short context: The idea of symmetrization – taking a subset S of ${\mathbb R}^n$ and transform it to become “more symmetric” – is widely used in mathematics. Minkowski symmetrization, introduced by Blaschke in 1916, is a prominent example. In 1988, Bourgain, Lindenstrauss, and Milman proved that a sequence of $cn\log n$ Minkowski symmetrizations selected at random suffices to transform any convex body in ${\mathbb R}^n$ into an approximate ball. For random symmetrizations, this bound is the best possible. The Theorem states, however, that with carefully selected non-random symmetrizations, we can do this in only $5n$ steps.

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

Go to the list of all theorems