Littlewood conjecture holds outside of a set of Hausdorff dimension 0

You need to know: For the Theorem: logarithm, limit, notations $|x|$ for the absolute value of $x$ , ${\mathbb R}^2$ for the Euclidean plane, and $\cup$ for the set union. In addition, you need to know $\liminf$ notation, Lebesgue measure, and Hausdorff dimension to understand the context.

Background: We say set set $S\subset {\mathbb R}^2$ has box dimension $0$ if $\lim\limits_{\epsilon\to 0+}\frac{\log N_S(\epsilon)}{\log(1/\epsilon)}=0$ , where $N_S(\epsilon)$ is the minimal number of squares of side length $\epsilon$ needed to cover S.

Let $T\subset {\mathbb R}^2$ be the set of all pairs $(\alpha, \beta)$ , for which there exists an $\epsilon>0$ such that inequality $\left|\alpha-\frac{a}{c}\right|\cdot \left|\beta-\frac{b}{c}\right| \geq \frac{\epsilon}{c^3}$ holds for all integers $a, b$ and $c\neq 0$ .

The Theorem: On 5th September 2003, Manfred Einsiedler, Anatole Katok, and Elon Lindenstrauss submitted to the Annals of Mathematics a paper in which they proved that $T$ can be written as a union of sets $S_1 \cup S_2 \cup S_3 \cup \dots$ , where each $S_i$ has box dimension $0$ .

Short context: In the 1930s, Littlewood conjectured that for any two real numbers $\alpha$ and $\beta$ , $\liminf\limits_{n\to\infty} n ||n\alpha|| ||n\beta|| = 0$ , where $||x||$ denotes the distance from real number x to the nearest integer. It is easy to see that set T is exactly the set of pairs $(\alpha, \beta)$ for which this conjecture does not hold. Hence, the conjecture predicts that T is an empty set. This remains open, but it follows from the 1909 Borel theorem that T has Lebesgue measure $0$ in ${\mathbb R}^2$ . The Theorem proves much stronger result on how “small” is T. In particular, it implies that T must have Hausdorff dimension $0$ .

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

Go to the list of all theorems

An asymptotic form of the Satisfiability Threshold Conjecture is true

You need to know: Supremum, infinum, big O and small o notations, boolean variables, their disjunction, conjunction, and negation, satisfiable and unsatisfiable formulas, basic probability theory: select objects from finite set uniformly, independently and with replacement.

Background: A k-clause is a disjunction of k Boolean variables, some of which may be negated. For a set $V_n$ of n Boolean variables, let $C_k(V_n)$ denote the set of all $2^kn^k$ possible k-clauses on $V_n$ . A random k-CNF formula $F_k(n, m)$ is formed by selecting uniformly, independently and with replacement m k-clauses from $C_k(V_n)$ and taking their conjunction. For each $k \geq 2$ , let $r_k$ be the supremum of r such that $F_k(n, rn)$ is satisfiable with probability tending to 1 as $n\to\infty$ .

The Theorem: On 4th September 2003, Dimitris Achlioptas and Yuval Peres submitted to the Journal of the AMS a paper in which they proved the existence of a sequence $\delta_k$ convergent to $0$ such that for all $k \geq 3$ , $r_k \geq 2^k \log 2 - (k + 1)\frac{\log 2}{2} - 1 - \delta_k.$

Short context: For each $k \geq 2$ , let $r^*_k$ be the infinum of r such that $F_k(n, rn)$ is unsatisfiable with probability tending to 1 as $n\to\infty$ . Obviously, $r_k \leq r_k^*$ . The Satisfiability Threshold Conjecture predicts that in fact $r_k = r_k^*$ for all $k\geq 3$ . Because it is known that $r_k^* \leq 2^k\log 2$ , the Theorem implies that $r_k = r_k^*(1-o(1))$ , which is an asymptotic form of the Satisfiability Threshold Conjecture.

Links: The original paper is available here.

Go to the list of all theorems

The Lieb conjecture on the monotonicity of Shannon’s entropy is true

You need to know: Basic probability theory: random variable, its support, probability density function, expectation (denoted $E[.]$ ), independent random variables, identically distributed random variables.

Background: For a random variable X with probability density function f and support $S\subset{\mathbb R}$ , its Shannon entropy is $\text{Ent}(X) = -\int_S f(x) \log f(x) dx$ . Random variable X is square-integrable if $E[X^2]<\infty$ .

The Theorem: On 4th September 2003, Shiri Artstein, Keith Ball, Franck Barthe, and Assaf Naor submitted to the Journal of the AMS a paper in which they proved that, for any sequence $X_1, X_2, \dots$ of independent and identically distributed square-integrable random variables, the entropy of the normalised sum $\text{Ent} \left(\frac{X_1 + \dots + X_n}{\sqrt{n}}\right)$ is a non-decreasing function of n.

Short context: For sequence $X_1, X_2, \dots$ as above, it is known that normalised sums $Y_n = \frac{1}{\sqrt{n}}\sum\limits_{i=1}^n X_i$ converge to normal distribution. In 1949 Shannon proved that $\text{Ent}(Y_2) \geq \text{Ent}(Y_1)$ . In 1978, Lieb conjectured that in fact $\text{Ent}(Y_{n+1}) \geq \text{Ent}(Y_n)$ for all n, which could be interpreted that $Y_n$ becomes closer and closer to the normal distribution (the one with maximal entropy) at every step. This conjecture was open even for $n=2$ . The Theorems proves it in full.

Links: The original paper is available here.

Go to the list of all theorems

For any b>0 exists k>0 such that for any finite set A of integers either|kA|>|A|^b or|A^k|>|A|^b

You need to know: Notation ${\mathbb Z}$ for the set of integers, notation $|A|$ for the size of set A.

Background: For $A,B\subset {\mathbb Z}$ , denote $A+B=\{a+b, \, a\in A, b\in B\}$ and $A\times B=\{a\cdot b, \, a\in A, b\in B\}$ . For $A\subset {\mathbb Z}$ and positive integer k, denote $kA= A + A + \dots + A$ and $A^k = A \times A \times \dots \times A$ , where A in the sum and in the product is repeated k times.

The Theorem: On 3rd September 2003, Jean Bourgain and Mei-Chu Chang submitted to arxiv a paper in which they proved that for any integer $b>0$ there is an integer $k = k(b) > 0$ such that $\max(|kA|,|A^k|)\geq|A|^b$ holds for any non-empty finite set $A \subset {\mathbb Z}$ .

Short context: In 1983, Erdős and Szemerédi proved the existence of positive constants c and $\epsilon$ such that inequality $\max(|A+A|, |A \cdot A|) \geq c|A|^{1+\epsilon}$ holds for any non-empty finite set $A \subset {\mathbb Z}$ (see here for a finite field analogue of this result). The Theorem states that if we consider k-fold sums and products for sufficiently large k, then exponent $1+\epsilon$ in the Erdős-Szemerédi theorem can be replaced by an arbitrary large constant.

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

Go to the list of all theorems

There exists FPRAS for the permanent of a matrix with nonnegative entries

You need to know: Permutation of $\{1, 2,\dots, n\}$ , notation $P[B]$ for the probability of event B, polynomial algorithm, randomised algorithm.

Background: Let A be an $n\times n$ matrix with entries $a(i,j), \, i=1,\dots, n, \, j=1,\dots, n$ . The permanent of A is $\text{per}(A) = \sum\limits_\sigma \prod\limits_{i=1}^n a(i, \sigma(i))$ , where the sum is over all permutations $\sigma$ of $\{1, 2,\dots, n\}$ . A fully polynomial randomised approximation scheme (FPRAS) for the permanent is a randomised algorithm which, given $n\times n$ matrix A and $\epsilon\in(0,1]$ as an input, runs in time polynomial in n and $\epsilon^{-1}$ , and outputs a (random) number Z such that $P[\exp(-\epsilon) Z \leq \text{per}(A) \leq \exp(\epsilon)Z] \geq \frac{3}{4}$ .

The Theorem: In August 2003, Mark Jerrum, Alistair Sinclair, and Eric Vigoda submitted to the Journal of the ACM a paper in which they proved the existence of a fully polynomial randomised approximation scheme (FPRAS) for the permanent of an arbitrary $n \times n$ matrix A with non-negative entries.

Short context: The evaluation of the permanent of a matrix is an old well-studied problem going back as far as, at least, the 1812 memoirs of Binet and Cauchy. In 1979, Valiant proved that the permanent cannot be computed exactly and efficiently (unless a well-believed conjecture is false). The Theorem, however, states that if entries of matrix A are non-negative, then we can compute an arbitrarily close approximation to its permanent in time that depends polynomially on the input size and the desired error. Given the Valiant’s result, this is the best we could hope for.

Links: The original paper is available here.

Go to the list of all theorems

Poincaré conjecture is true: simply connected closed 3-manifold is a sphere

You need to know: Basic topology: Euclidean space, topological space, homeomorphism, 3-dimensional manifold (3-manifold), simple closed curve, compact manifold, closed manifold (manifold without boundary which is compact).

Background: A 3-manifold M is called pathwise-connected if for every two points x,y in M there is a continuous function f from $[0,1]$ to M such that $f(0)=x$ and $f(1)=y$ . M is called simply connected if it is pathwise-connected and any simple closed curve in M can be shrunk to a point continuously in M. A 3-sphere is the set of points in 4-dimensional Euclidean space equidistant from a fixed point.

The Theorem: On 17th July 2003, Grigori Perelman submitted to arxiv the last in the series of three papers in which he proved, as a special case of a more general result, that every simply connected closed 3-manifold is homeomorphic to the 3-sphere.

Short context: The Theorem confirms a 1904 conjecture of Poincaré, a fundamental conjecture is 3-dimensional topology. In 2000, Clay Mathematics Institute (CMI) included this conjecture to the list of seven Millennium Prize Problems, for which they offered a million dollars prize for the first correct solution. Its proof by Perelman is considered by many as the greatest theorem of the 21-st century. It took about 3 years for his papers to be verified. In May 2006, Kleiner and Lott posted on arxiv a paper that gives more details of the proof. In 2006, Perelman was offered a Fields Medal for this work. However, he declined to accept both the Fields Medal and the million dollars prize from CMI.

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

Go to the list of all theorems

Duality conjecture for entropy numbers is true if one of the bodies is a ball

You need to know: Euclidean space ${\mathbb R}^n$ , scalar product $\langle x,y \rangle$ in ${\mathbb R}^n$ , origin $(0,0,\dots,0)$ in ${\mathbb R}^n$ , ball in ${\mathbb R}^n$ , convex body in ${\mathbb R}^n$ , translate of a convex body by a vector.

Background: We say that convex body $K \subset {\mathbb R}^n$ is symmetric with respect the origin, or just symmetric in short, if $x\in K$ implies that $-x\in K$ . Set $K^\circ = \{ y\in{\mathbb R}^n \,:\, \sup\limits_{x\in K} \langle x,y \rangle \leq 1 \}$ is called the polar body of K. For two convex bodies K and T in ${\mathbb R}^n$ , the covering number of K by T, denoted N(K, T), is the minimal number of translates of T needed to cover K. Also, let D be the euclidean unit ball in ${\mathbb R}^n$ .

The Theorem: On 29th May 2003, Shiri Artstein, Vitali Milman, and Stanisław Szarek submitted to the Annals of Mathematics a paper in which they proved the existence of two universal constants $\alpha$ and $\beta$ such that for any dimension n and any symmetric convex body $K \subset {\mathbb R}^n$ , $N(D, \alpha^{-1} K^\circ)^{\frac{1}{\beta}} \leq N(K, D) \leq N(D, \alpha K^\circ)^\beta$ .

Short context: In 1972, Pietsch conjectured the existence of two constants $a, b \geq 1$ such that for any dimension n, and for any two symmetric convex bodies K and T in ${\mathbb R}^n$ , we have $\log N(T^\circ, a K^\circ) \leq b \log N(K, T)$ (this is one of many equivalent formulations of the conjecture). The conjecture is originated in operator theory and became known as the “duality conjecture for entropy numbers”. The Theorem implies that it holds in a special but important case when either K or T is an euclidean ball.

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

Go to the list of all theorems

Vertex cover is unique-games-hard to approximate within any factor c < 2

You need to know: Graph, vertices, edges, class P, class NP, NP-hard problems, notation ${\mathbb Z}_m$ for set $\{0,1,2,\dots,m-1\}$ with addition and multiplication defined modulo m.

Background: A vertex cover of graph G is the set S of vertices of G such that for each edge $(u,v)$ of G either $u \in S$ or $v\in S$ (or both). Let $\tau(G)$ be the size of the smallest vertex cover of G. The minimum vertex cover problem is: given graph G, compute $\tau(G)$ . Its approximation with factor $c>1$ is: given graph G, compute number k such that $\tau(G) \leq k \leq c\tau(G)$ .

For a fixed $\epsilon \in (0,1/2)$ and integer m, consider the following problem. The input is a system of k linear equations in n variables $x_1, x_2, \dots, x_n$ over ${\mathbb Z}_m$ , each equation having the form $a \cdot x_i + b \cdot x_j = c$ , $a,b,c \in {\mathbb Z}_m$ , such that either (i) there is an assignment satisfying $(1-\epsilon) k$ of the equations, or (ii) no assignment satisfies more than $\epsilon k$ of the equations. The problem $\text{UG}(\epsilon,m)$ is to decide which of the cases (i) or (ii) is true. The Unique Games Conjecture states that for every $\epsilon \in (0,1/2)$ there exists m such that $\text{UG}(\epsilon,m)$ is NP-hard.

The Theorem: On 28th May 2003, Subhash Khot and Oded Regev submitted to the Journal of Computer and System Sciences a paper in which they proved that, assuming the Unique Games Conjecture, the minimum vertex cover problem is NP-hard to approximate to within any constant factor smaller than 2.

Short context: Because the minimum vertex cover problem is well-known to be NP-hard to solve exactly, it is natural to look for polynomial-time approximate algorithms. A simple algorithm, discovered independently by Gavril and Yannakakis, gives approximation with factor $c=2$ . The Theorem states that this approximation ratio is the best possible, subject to the Unique Games Conjecture. Unconditionally, it is known that the problem is NP-hard to approximate to within any factor $c<10\sqrt{5}-21 = 1.3606...$ . See here for further progress in later work.

Links: The original paper is available here.

Go to the list of all theorems

The weak form of De Giorgi’s conjecture is true in dimensions at most 8

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 25th April 2003, Ovidiu Savin submitted to the Annals of Mathematics a paper in which he proved the following result. Suppose $u:{\mathbb R}^n \to {\mathbb R}$ is a solution 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$ ; and (iii) $\lim\limits_{x_n\to\pm \infty} u(x_1, \dots, x_{n-1}, x_n)=\pm 1$ for every fixed $x_1, \dots, x_{n-1}$ . If $n \leq 8$ , then all level sets of u are 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, if true, would allow you to write down a formula for u easily. In 1998, Ghoussoub and Gui proved this conjecture for $n=2$ , while in 2000 Ambrosio and Cabre proved it for $n=3$ . The Theorem confirms this conjecture in a weak form (that is, under the additional assumption (iii)), in all dimensions $n \leq 8$ .

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

Go to the list of all theorems

The set of nowhere monotone differentiable functions on R is lineable

You need to know: Monotone function, continuous function, differentiable function, vector space and its dimension, infinite-dimensional vector space.

Background: Let $C({\mathbb R})$ be the set of all functions $f:{\mathbb R}\to {\mathbb R}$ that are continuous at every $x\in{\mathbb R}$ . A subset $S\subset C({\mathbb R})$ is called lineable in $C({\mathbb R})$ if $S\cup\{0\}$ contains an infinite-dimensional vector space. A function $f:{\mathbb R}\to {\mathbb R}$ is called nowhere monotone if there are no real numbers $a<b$ such that f is monotone on $(a,b)$ .

The Theorem: On 26th March 2003, Richard Aron, Vladimir Gurariy, and Juan Seoane-Sepúlveda submitted to the Proceedings of the AMS a paper in which they proved that the set of differentiable functions $f:{\mathbb R}\to {\mathbb R}$ that are nowhere monotone is lineable in $C({\mathbb R})$ .

Short context: In 1872, Weierstrass constructed an example of a function $f:{\mathbb R}\to {\mathbb R}$ which is continuous at every $x\in{\mathbb R}$ but nowhere monotone. In fact, the Weierstrass function is also nowhere differentiable. In 1915, Denjoy constructed an example of a function $f:{\mathbb R}\to {\mathbb R}$ that are differentiable at every $x\in{\mathbb R}$ but still nowhere monotone. In 1966, Gurariy proved that the set of nowhere differentiable functions is lineable in $C({\mathbb R})$ . This shows that such functions are not some “exotic counterexamples” but in fact quite typical. The Theorem establishes the same result for differentiable but nowhere monotone functions.

Links: The original paper is available here.

Go to the list of all theorems