There exists an exhaustive submeasure that is not equivalent to a measure

You need to know: Boolean algebra of sets.

Background: Let ${\cal B}$ be a Boolean algebra of sets. A map $\nu:{\cal B} \to {\mathbb R}$ is called a submeasure if the following holds: (i) $\nu(\emptyset) = 0$ , (ii) $\nu(A) \leq \nu(B)$ for every $A,B \in {\cal B}$ such that $A \subset B$ , and (iii) $\nu(A \cup B) \leq \nu(A) + \nu(B)$ for every $A,B \in {\cal B}$ . A submeasure $\nu$ is called a (finitely additive) measure if $\nu(A \cup B) = \nu(A) + \nu(B)$ whenever sets $A,B \in {\cal B}$ are disjoint. A submeasure $\nu$ is called exhaustive if $\lim\limits_{n\to \infty}\nu(E_n)=0$ for every sequence $\{E_n\}_{n=1}^\infty$ of elements of ${\cal B}$ such that $E_n \cap E_m = \emptyset$ whenever $n\neq m$ . We say that submeasure $\nu_1$ is absolutely continuous with respect to a submeasure $\nu_2$ if for every $\epsilon>0$ there exists an $\alpha>0$ such that $\nu_1(A) \leq \epsilon$ for every $A \in {\cal B}$ with $\nu_2(A) \leq \alpha$ .

The Theorem: On 27th January 2006, Michel Talagrand submitted to arxiv a paper in which he proved the existence of a Boolean algebra ${\cal B}$ of sets, and a nonzero exhaustive submeasure $\nu$ on it, which is not absolutely continuous with respect to any measure.

Short context: Any measure is exhaustive. Moreover, if a submeasure is absolutely continuous with respect to a measure, it is exhaustive. One of the many equivalent formulations of famous Maharam’s problem is whether the converse is true. The Theorem gives a negative answer to this question.

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

Go to the list of all theorems

w(G)^3=G for every non-trivial group word w and every large finite simple group G

You need to know: Group, identity element, finite group, notation $|G|$ for the number of elements in a finite group G, simple group, free group.

Background: Let $w = w(x_1,\dots,x_d)$ be a non-trivial group word, that is, a non-identity element of the free group $F_d$ on $x_1,\dots,x_d$ . For a group G, denote $w(G)$ the set of all elements $g \in G$ which can be obtained by substitution of some $g_1, g_2, \dots, g_d \in G$ into w instead of $x_1, x_2, \dots, x_d$ , respectively, and performing the group operation. For subsets $A,B$ of group G, let $A\cdot B=\{g \in G: g=a\cdot b, \, a\in A, \, b\in B\}$ . Denote $A^3=A \cdot A \cdot A$ .

The Theorem: On 24th January 2006, Aner Shalev submitted to the Annals of Mathematics a paper in which he proved that for any non-trivial group word w there exists a positive integer $N=N(w)$ such that for every finite simple group G with $|G|\geq N(w)$ we have $w(G)^3=G$ .

Short context: Given a non-trivial group word w, is there a constant $c=c(w)$ such that $w(G)^c=G$ for every large finite simple group G? This was proved for the commutator word $w=x_1^{-1}x_2^{-1}x_1x_2$ by Wilson in 1994, and for the power word $w=x_1^k$ by Martinez and Zelmanov in 1996. In 2001, Liebeck and Shalev deduced from this theorem that this is true for all non-trivial group words. However, the exact value of constant $c=c(w)$ was unknown. The Theorem proves that one can take $c=3$ , independently of w.

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

Go to the list of all theorems

The set of all integer solutions of ad-bc=1 is a polynomial family

You need to know: Polynomials in k variables, notation ${\mathbb Z}^n$ for the set of vectors $x=(x_1, x_2, \dots, x_n)$ with integer $x_i$ .

Background: We say that a set $A \subset {\mathbb Z}^n$ is a polynomial family with k parameters if there are exist n polynomials $P_1, P_2, \dots, P_n$ in k variables with integer coefficients such that $x=(x_1, x_2, \dots, x_n)$ belongs to A if and only if there exists integers $y_1, y_2, \dots, y_k$ such that $x_i = P_i(y_1, y_2, \dots, y_k), \, i=1,2,\dots,n$ .

The Theorem: On 16th January 2006, Leonid Vaserstein submitted to the Annals of Mathematics a paper in which he proved that the set of all integer solutions of equation $x_1x_4-x_2x_3=1$ is a polynomial family with 46 parameters.

Short context: What do you mean by “solving” an equation if it has infinitely many solutions? We cannot list all solutions one by one, so the best we can hope for is to present some formulas with parameters which represent all solutions. The Theorem achieves this for the equation $x_1x_4-x_2x_3=1$ , solving a problem which goes back to 1938 paper of Skolem. It immediately implies the existence of polynomial families describing the solutions of some other, more complicated equations.

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

Go to the list of all theorems

The Bobkov–Nazarov concentration of mass inequality holds for all isotropic convex bodies

You need to know: Euclidean space ${\mathbb R}^n$ , inner product $(x,y)=\sum\limits_{i=1}^n x_iy_i$ in ${\mathbb R}^n$ , norm $||x||_2 = \sqrt{(x,x)}$ , integration in ${\mathbb R}^n$ , unit sphere $S^{n-1} \subset {\mathbb R}^n$ , convex body in ${\mathbb R}^n$ , centre of mass of a convex body, probability.

Background: A convex body $K \subset {\mathbb R}^n$ is called isotropic if it has volume 1, its centre of mass is at the origin, and there exists a positive constant $L_K$ such that $\int_K (x,\theta) dx = L_K^2$ for every $\theta \in S^{n-1}$ .

The Theorem: In January 2006, Grigoris Paouris submitted to the Geometric and Functional Analysis a paper in which he proved the existence of an absolute constant $c>0$ such that if x is selected uniformly at random inside an isotropic convex body K in ${\mathbb R}^n$ , then $P(||x||_2 \geq c\sqrt{n}L_Kt) \leq \exp(-\sqrt{n}t)$ for every $t \geq 1$ .

Short context: In 2003, Bobkov and Nazarov established inequality as in the Theorem for special isotropic convex bodies called 1-uncoditional. The Theorem proves that the Bobkov–Nazarov estimate holds in full generality. There are many applications of this result. For example, in combination with a theorem of Klartag, it implies that $L_K \leq c \sqrt[4]{n}$ for every isotropic convex body K in ${\mathbb R}^n$ . This is a step towards proving the famous hyperplane conjecture, which predicts that $L_K \leq c$ for some constant c independent of n.

Links: The original paper is available here.

Go to the list of all theorems

The optimal exponent in the quantitative isoperimetric inequality is 1/2

You need to know: Notations $A \setminus B = \{x: x\in A \,\text{and}\,x\not\in B\}$ for set difference and $A\Delta B = (A \setminus B)\cap (B \setminus A)$ for the symmetric difference of sets A and B, Euclidean space ${\mathbb R}^n$ , ball in ${\mathbb R}^n$ , Borel sets in ${\mathbb R}^n$ (sets for which volume is well-defined), volume $|E|$ of a Borel set $E \subset {\mathbb R}^n$ , boundary $\partial E$ of $E$ , distributional perimeter $P(E)$ of $E$ (which coincides with the classical (n − 1)-dimensional measure of $\partial E$ when $E$ has a smooth boundary).

Background: The isoperimetric deficit $D(E)$ of a Borel $E \subset {\mathbb R}^n$ with $0<|E|<\infty$ is $D(E)=\frac{P(E)-P(B)}{P(B)}$ , where $P(.)$ is perimeter and B is a ball such that $|B|=|E|$ . The Fraenkel asymmetry $\lambda(E)$ of a $E$ is $\lambda(E) = \min\limits_{B \in {\cal B}} \frac{|E\Delta B|}{r(B)^n}$ where ${\cal B}$ is the set of all balls B with $|B|=|E|$ and $r(B)$ is the radius of ball B.

The Theorem: On 17th December 2005, Nicola Fusco, Francesco Maggi, and Aldo Pratelli submitted to the Annals of Mathematics a paper in which they proved that for every $n \geq 2$ there exists a constant $C_n$ such that inequality $\lambda(E) \leq C_n \sqrt[2]{D(E)}$ holds for every Borel set $E$ in ${\mathbb R}^n$ with $0 < |E| < \infty$ .

Short context: The isoperimetric theorem for the plane states that circle has the lowest length out of all plane curves which encloses a prescribed area. It was proved by Steiner in 1838 assuming that solution exists, and by Edler in 1882 unconditionally. The same is true in higher dimensions: ball has the lowest perimeter out of all bodies with the given volume. Moreover, Hall proved in 1992 that $\lambda(E) \leq C_n D(E)^{1/4}$ , that is, the perimeter of E may be close to optimal ( $D(E)$ is small) only if E is almost a ball ( $\lambda(E)$ is small). Hall further conjectured that the exponent $1/4$ in his inequality can be improved to $1/2$ , and this is optimal. The Theorem confirms this conjecture.

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

Go to the list of all theorems

The B. and M. Shapiro conjecture in real algebraic geometry is true

You need to know: Set ${\mathbb C}$ of complex numbers, polynomials in complex variable, root of a polynomial, derivative, notation $P^{(j)}(z)$ for j-th derivative of polynomial $P(z)$ , matrix, determinant of a matrix, vector space, basis of a vector space.

Background: Let ${\cal P}=\{P_1(z), P_2(z), \dots, P_k(z)\}$ be a finite set of polynomials in complex variable z with complex coefficients. The complex span S of ${\cal P}$ is the set of polynomials $P(z)$ of the form $P(z)=\sum\limits_{i=1}^k \lambda_i P_i(z)$ for some $\lambda_i \in {\mathbb C}, \, i=1,\dots,k$ . The Wronskian $W(z)$ of ${\cal P}$ is the determinant of the $k \times k$ matrix with entries $P^{(j-1)}_i(z), \, i=1,\dots,k, \, j=1,\dots,k$ .

The Theorem: On 14th December 2005, Evgeny Mukhin, Vitaly Tarasov, and Alexander Varchenko submitted to arxiv a paper in which they proved that if all roots of the Wronskian of a set ${\cal P}$ of polynomials are real, then the complex span of ${\cal P}$ has a basis consisting of polynomials with real coefficients.

Short context: The Theorem confirms the 1995 conjecture known as the B. and M. Shapiro conjecture in real algebraic geometry. Earlier, it was known only in the case $k=2$ .

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

Go to the list of all theorems

Half of primes have the even sum of digits

You need to know: Prime numbers, relatively prime integers.

Background: Let $q\geq 2$ be an integer. Any integer $n>0$ can be uniquely represented as $n=\sum\limits_{i=1}^{k} b_i q^{k-i}$ , where $k>0$ is an integer and $b_1, b_2, \dots, b_k$ are integers between $0$ and $q-1$ , which are called digits of n in the q-ary number system (if $q=10$ , these are the digits in the usual decimal system). Let $S_q(n)=\sum\limits_{i=1}^k b_i$ be the sum of digits of n. Let $\pi(n)$ be the number of primes less than n, and let $\pi_{q,m,a}(n)$ be the number of primes p less than n such that $S_q(p) - a$ is a multiple of m.

The Theorem: On 10th November 2005, Christian Mauduit and Joël Rivat submitted to the Annals of Mathematics a paper in which they proved that for all integers $m \geq 2$ and $q \geq 2$ such that $q-1$ and $m$ are relatively prime, there exist constants $C_{q,m}>0$ and $\sigma_{q,m}>0$ , such that the inequality $\left|\pi_{q,m,a}(n) - \frac{\pi(n)}{m}\right| \leq C_{q,m} n^{1-\sigma_{q,m}}$ holds for all integers $n>0$ and all integers $a$ .

Short context: Because $C_{q,m} n^{1-\sigma_{q,m}}$ is known to be negligible comparing to $\pi(n)$ for large n, the theorem states that $\pi_{q,m,a}(n) \approx\frac{\pi(n)}{m}$ , that is, the primes whose sum of digits gives any fixed reminder after division by m occupies about $1/m$ of all primes, as intuitively expected. This answers the 1968 question of Gelfond. In the special case $q=10$ and $m=2$ , it states that asymptotically half of all primes have the even sum of digits, and half of primes have the odd sum of digits.

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

Go to the list of all theorems

The norm of the inverse of n by n matrix with i.i.d. Bernoulli entries is polynomially bounded with probability 1-1/n^C, for any C>0

You need to know: Probability (denoted by P), abbreviation i.i.d. for independent identically distributed random variables, Euclidean space ${\mathbb R}^n$ , notation $|x|$ for length of $x \in {\mathbb R}^n$ , matrix multiplication, inverse matrix, norm $||A||=\sup\limits_{x \in {\mathbb R}^n}\frac{|Ax|}{|x|}$ of $n \times n$ matrix A.

Background: For integer $n>0$ , let $A_n$ be an $n \times n$ matrix whose entries $a_{ij}$ are i.i.d. Bernoulli random variables (taking values $+1$ and $-1$ with probability $1/2$ each).

The Theorem: On 8th November 2005, Terence Tao and Van Vu submitted to arxiv a paper in which they proved that for any constant $C>0$ , there are constants B and N such that for any $n\geq N$ the inequality $\|A_n^{-1}\| \leq n^B$ holds with probability at least $1-n^{-C}$ .

Short context: It is known that random Bernoulli matrix $A_n$ is invertible with probability exponentially close to 1. The Theorem states that the norm $\|A^{-1}\|$ of its inverse matrix is polynomially bounded with probability at least $1-n^{-C}$ for any $C>0$ . Previously, this was known only for $C\leq 1/2$ .

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

Go to the list of all theorems

The Cayley graphs of SL_2(F_p) with random generators form a family expanders

You need to know: Group $\text{SL}_2({\mathbb F}_p)$ (group of $2 \times 2$ matrices over ${\mathbb F}_p$ with determinant 1, see here) , set of generators of a group, graph, edge expansion of a graph, family of expanders.

Background: For a finite group G with set of generators A, the (undirected) Cayley graph $\Gamma =\Gamma (G,A)$

The Theorem: On 3rd November 2005, Jean Bourgain and Alex Gamburd submitted to the Annals of Mathematics a paper in which they proved the following result. Fix $k \geq 2$ . For any prime $p$ , let $S_p$ be a $k$ -element subset of $SL_2({\mathbb F}_p)$ whose elements are chosen independently at random, and let $\Gamma_p=\Gamma (SL_2({\mathbb F}_p), S_p)$ be the corresponding Cayley graph. Then the sequence $\Gamma_2, \Gamma_3, \Gamma_5, \Gamma_7, \Gamma_{11}, \dots$ forms a family of expanders with probability $1$ .

Short context: Expanders are highly-connected sparse graphs widely used in both pure mathematics and computer science. A basic problem, posed by Lubotzky in 1990-s, is whether Cayley graphs of $SL_2({\mathbb F}_p)$ are expanders, for various choices of generating sets. The Theorem proves that they are expanders if the generating sets are chosen at random.

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

Go to the list of all theorems

Fast algorithm to approximately fit a C^m-smooth function to data

You need to know: Euclidean space ${\mathbb R}^n$ , space of functions $C^m({\mathbb R}^n)$ (see this previous theorem description), notation $||F||_{C^m({\mathbb R}^n)}$ for the norm in this space, algorithm, its running time and memory use.

Background: Let $E \subset {\mathbb R}^n$ be a finite set of cardinality N. Let $f:E \to {\mathbb R}$ and $\sigma: E \to [0, \infty)$ be given functions on E. Let $||f||_{C^m(E,\sigma)}$ denote the infimum of all $M>0$ for which there exists $F \in C^m({\mathbb R}^n)$ such that $||F||_{C^m({\mathbb R}^n)}\leq M$ and $|F(x)-f(x)| \leq M \sigma(x)$ for all $x \in E$ . We say that two numbers $X, Y \geq 0$ determined by $E, f, \sigma, m, n$ have the same order of magnitude if $cX \leq Y \leq CX$ , where constants c and C depends only on m and n. By “compute the order of magnitude of X” we mean compute some Y such that X and Y have the same order of magnitude.

The Theorem: On 6th October 2005, Charles Fefferman and Bo’az Klartag submitted to the Annals of Mathematics a paper in which they presented an algorithm and proved that it computes, given $E, f, \sigma, m, n$ , the order of magnitude of $||f||_{C^m(E,\sigma)}$ in time at most $CN \log N$ and using memory at most $CN$ , where the constant C depends only on m and n.

Short context: Function $f:E \to {\mathbb R}$ represents N data points, to which we want to feet a smooth function F with smallest possible $C^m({\mathbb R}^n)$ norm. We may want the exact feet to data (case $\sigma=0$ ), or approximate one ( $\sigma \neq 0$ ). The Theorem proves the existence of efficient algorithm which approximately computes the smallest possible $C^m({\mathbb R}^n)$ norm of F we can achieve. In the subsequent paper, we same authors also presented algorithm which computes F itself.

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

Go to the list of all theorems