Replica predictions hold for the minimum matching problem in the pseudo-dimension d mean field model for d>=1.

You need to know: Graph, complete graph, matching in a graph, minimum matching, limits, notation $P$ for probability, random variable, independent random variables, distribution, density.

Background: Let $d>0$ be a real number, and let $n>0$ be an even integer. In a complete graph $G_n$ on n vertices, let each edge $e$ be assigned independent random cost $C_e$ from a fixed distribution on the non-negative real numbers with density $\rho(t)$ , such that $\lim\limits_{t \to 0^+} \frac{\rho(t)}{dt^{d-1}} = 1$ . Let $M(n,d)$ be the (random) cost of a minimum matching in $G_n$ .

The Theorem: On 1st July 2009, Johan Wästlund submitted to the Annals of Mathematics a paper in which he proved that for any $d \geq 1$ there exists a number $\beta(d)$ such that for any $\epsilon>0$ , $\lim\limits_{n\to \infty}P\left[\left|M(n,d) - \beta(d)\right|>\epsilon\right] = 0.$

Short context: Minimum matching problem in a graph is one of the fundamental problems in graph theory. A model in which the edge costs are randomly chosen as described above is known as the mean field model of pseudo-dimension d. In 1985, Mézard and Parisi introduced non-rigorous analysis with physical origin (called replica analysis) which allowed them to predict that the statement of the Theorem holds for any $d>0$ , write down a conjectured analytic formula for $\beta(d)$ , and compute it numerically. However, before 2009, these predictions were rigorously confirmed only for $d=1$ . The Theorem did this for all $d\geq 1$ .

Links: The original paper is available here.

Go to the list of all theorems

The Khorunzhiy conjecture on the norms of random band matrices is true

You need to know: Eucledean space ${\mathbb R}^n$ , norm $||x||=\sqrt{\sum_{i=1}^n x_i^2}$ of vector $x=(x_1, \dots, x_n)\in{\mathbb R}^n$ , matrix, multiplication of matrix by a vector, norm $\|A\| = \sup\limits_{||x||=1}||Ax||$ of $n\times n$ matrix A, basic probability theory, independence, convergence in distribution.

Background: Fix a sequence $w_1, w_2, \dots, w_n, \dots$ of positive numbers. For every positive integer n, let $A_n$ be a random $n \times n$ matrix whose entries $a_{ij}$ are such that (i) $a_{ij}=a_{ji}$ for all i and j; (ii) $a_{ij}=0$ if either $i=j$ or $\min(|i-j|, n-|i-j|)>w_n$ ; and (iii) all $a_{ij}$ such that $0<\min((i-j), n-(i-j)) \leq w_n$ are selected independently at random, each equal to $1$ or $-1$ with equal probabilities. Random matrices $A_n$ selected in accordance to these rules are called random band matrices.

The Theorem: On 22nd June 2009, Sasha Sodin submitted to arxiv a paper in which he proved that if $\lim\limits_{n\to\infty}\frac{w_n}{\log n}= +\infty$ then $\|A_n/2\sqrt{2w_n}\|$ converges in distribution to $1$ .

Short context: The study of random matrices is one of the central topics in probability theory, and random band matrices is an important model having physical applications. In 2008, Khorunzhiy proved the statement of the Theorem under stronger assumption that $\lim\limits_{n\to\infty}\frac{w_n}{\log^{3/2} n} = +\infty$ , and conjectured that weaker assumption $\lim\limits_{n\to\infty}\frac{w_n}{\log n} = +\infty$ suffices. The Theorem proves this conjecture. This result is sharp, because Bogachev, Molchanov, and Pastur proved in 1991 that the conclusion of the Theorem fails if $\lim\limits_{n\to\infty}\frac{w_n}{\log n} = 0$ .

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

Go to the list of all theorems

The Ore conjecture is true: every element of every finite non-abelian simple group is a commutator

You need to know: Group, finite group, identity element e of a group, notation $g^{-1}$ for the inverse of group element g, subgroup.

Background: A subgroup S of group G is called normal, if $g\cdot a\cdot g^{-1}\in S$ for any $a \in S$ and $g \in G$ . A group G is called simple if it does not have any normal subgroup, except of itself and $\{e\}$ , where $\{e\}$ is the set consisting on identity element only. A group G is called abelian if $g\cdot h = h \cdot g$ for every $g \in G$ and $h \in G$ , and non-abelian otherwise. An element $a \in G$ is called a commutator if $a=g^{-1}h^{-1}gh$ for some $g \in G$ and $h \in G$ .

The Theorem: On 18th June 2009, Martin Liebeck, Eamonn O’Brien, Aner Shalev, and Pham Huu Tiep submitted to the Journal of the European Mathematical Society a paper in which they proved that every element of every finite non-abelian simple group is a commutator.

Short context: In any abelian group, $g^{-1}h^{-1}gh = g^{-1}(h^{-1}h)g = g^{-1}eg=e$ , hence only identity element is a commutator. In general, the size of set of commutators can be viewed as an indicator “how far” the group is from being abelian. In 1951, Ore made a conjecture that in every finite non-abelian simple group the set of commutators is the whole group, which makes such groups as “far” from being abelian as they possibly can. Despite substantial efforts, the conjecture remained open for 58 years. The Theorem proves this conjecture.

Links: The original paper is available here.

Go to the list of all theorems

Wigner Hermitian matrices have universal eigenvalue gap distribution

You need to know: Complex numbers, $n \times n$ matrix with complex entries, eigenvalues, Hermitian matrix, probability, random variable, mean, variance, notation P for probability, E for expectation, i.i.d. for independent identically distributed random variables, notation $|A|$ for the number of elements in finite set A.

Background: A Wigner Hermitian $n \times n$ matrix $M_n$ is a random Hermitian matrix with upper triangular complex entries $\psi_{ij}=\xi_{ij}+\tau_{ij}\sqrt{-1}$ , $1 \leq i < j \leq n$ , and diagonal real entries $\xi_{ii}$ , $1\leq i \leq n$ , where (i) for $1 \leq i < j \leq n$ , $\xi_{ij}$ and $\tau_{ij}$ are i.i.d. copies of a real random variable $\xi$ with mean zero and variance $1/2$ ; (ii) for $1\leq i \leq n$ , $\xi_{ii}$ are i.i.d. copies of a real random variable $\xi'$ with mean zero and variance 1; and (iii) $\xi$ and $\xi'$ have exponential decay, i.e., there exist constants $C$ and $C_0$ such that $P(|\xi|\geq t^C) \leq e^{-t}$ and $P(|\xi'|\geq t^C) \leq e^{-t}$ for all $t > C_0$ . $\xi$ and $\xi'$ are called the atom distributions of $M_n$ . Let $\lambda(M_n\sqrt{n})=(\lambda_1, \dots, \lambda_n)$ be the vector of eigenvalues $\lambda_i$ of matrix $M_n\sqrt{n}$ , arranged in the non-increasing order: $\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$ . Let $S_n(s; \lambda(M_n\sqrt{n})) = \frac{1}{n}|\{1\leq i \leq n-1: \, \lambda_{i+1}-\lambda_i \leq s\}|$ .

The Theorem: On 2nd June 2009, Terence Tao and Van Vu submitted to arxiv a paper in which they proved the following result. Let $M_n$ be a Wigner Hermitian matrix whose atom distributions $\xi, \xi'$ have support on at least three points, and $s>0$ . The the limit $G(s)=\lim\limits_{n\to\infty}E[S_n(s; \lambda(M_n\sqrt{n}))]$ exists and depends only on s but not on $\xi, \xi'$ .

Short context: The study of eigenvalues of large random matrices (largest eigenvalues, smallest, gaps between them, etc.) is one of the central themes in probability theory. In 1967, Mehta computed the limit $G(s)$ assuming that $\xi$ and $\xi'$ have normal distribution. The Theorem states that $E[S_n(s; \lambda(M_n\sqrt{n}))]$ converges to the same limit $G(s)$ , no matter how $\xi$ and $\xi'$ are distributed. In fact, the Theorem is just one out of many corollaries of a much more general “Four moment theorem” proved by authors, which, informally, states that many properties of the eigenvalues of a random Hermitian matrix are determined by the first four moments of the atom distributions. In a later work, the authors also treated a non-Hermitian case.

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

Go to the list of all theorems

There exists a fully homomorphic encryption scheme

You need to know: Basic cryptography: circuits, encryption, decryption, etc.

Background: A fully homomorphic encryption scheme is a procedure that allows one to evaluate circuits over encrypted data without being able to decrypt.

The Theorem: On 31th May 2009, Craig Gentry submitted to the Proceedings of the forty-first annual ACM symposium a paper in which he showed that fully homomorphic encryption scheme exists and can be actually constructed.

Short context: The notion of a fully homomorphic encryption (FHE) scheme was introduced by Rivest, Adleman, and Dertouzos in 1978. FHE would allow to perform arbitrary computations on encrypted data without decripting them, and would therefore lead to the possibility of more secure cloud computing. For example, a program could help with preparation of tax return forms using encrypted financial information. However, the existence of FHE was a long standing open problem, and many experts believed that it does not exist. The Theorem proves that FTE exists and can be actually constructed. This makes a revolution in cryptography.

Links: The original paper is available here.

Go to the list of all theorems

Any semigroup in Z^n is asymptotically approximated by its regularisation

You need to know: Euclidean space ${\mathbb R}^n$ , subspace of ${\mathbb R}^n$ , subspace spanned by a set, cone, convex cone, closed cone, apex of a cone, groups, group ${\mathbb Z}^n$ of vectors with integer coordinates, subgroup, subgroup generated by a set, semigroup.

Background: Let $S \subset {\mathbb Z}^n$ be a semigroup. Let G be the subgroup of ${\mathbb Z}^n$ generated by S, L the subspace of ${\mathbb R}^n$ spanned by S, and C the smallest closed convex cone (with apex at the origin) containing S.

The Theorem: On 21st April 2009, Kiumars Kaveh and Askold Khovanskii submitted to arxiv a paper in which they proved the following result. Let $C' \subset C$ be a closed strongly convex cone that intersects the boundary (in the topology of the linear space L) of the cone C only at the origin. Then there exists a constant $N>0$ (depending on $C'$ ) such that any point in the group G that lies in $C'$ and whose distance from the origin is bigger than N belongs to S.

Short context: Semigroup $S' = C \cap G$ is called regularization of S. From the definition, S’ contains S. The Theorem states that the regularization S’ asymptotically approximates the semigroup S. The authors call this the approximation theorem. It is not very difficult to prove, but the authors showed that it has many applications in convex and algebraic geometry, intersection theory, and other areas of mathematics.

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

Go to the list of all theorems

Every tensor has a tensor-train decomposition

You need to know: Matrix, rank $\text{rank}(M)$ of a matrix M.

Background: Let $n_1, n_2, \dots, n_d$ be positive integers. Let ${\cal I}$ be the set of vectors $i=(i_1, i_2, \dots, i_d)$ such that all $i_j$ are integers and $1 \leq i_j \leq n_j$ for $j=1,2,\dots, d$ . A function $A:{\cal I} \to {\mathbb R}$ is called a d-dimensional $n_1 \times n_2 \times \dots \times n_d$ tensor. Let $r_k, k=0,1,2,\dots,d$ be positive integers such that $r_0=r_d=1$ . We say that A has tensor-train decomposition (TT decomposition in short) with TT-ranks $r_k$ if $A(i_1, i_2, \dots, i_d) = G_1(i_1)G_2(i_2) \dots G_d(i_d),$ where $G_k(i_k)$ is an $r_{k-1} \times r_k$ matrix. For $k=0,1,\dots,d$ , the unfolding matrix $A_k$ of A is an $(\prod\limits_{s=1}^k n_s) \times (\prod\limits_{s=k+1}^d n_s)$ matrix with rows indexed by $(i_1, \dots, i_k)$ and columns indexed by $(i_{k+1}, \dots, i_d)$ such that $A_k( (i_1, \dots, i_k), (i_{k+1}, \dots, i_d)) = A(i_1, \dots, i_d)$ .

The Theorem: On 10th March 2009, Ivan Oseledets submitted to the SIAM Journal on Scientific Computing a paper in which he proved that for each d-dimensional tensor A there exists a TT decomposition with TT-ranks $r_k \leq \text{rank}(A_k)$ , $k=0,1,\dots, d$ .

Short context: Tensors are natural generalizations of matrices and are central in many applications. However, storing a d-dimensional tensor requires memory which grows exponential in d, and performing any operations requires exponential time. TT decomposition with low TT-ranks allows to store tensors and do computations on them with significantly less time and memory resources.

Links: The original paper is available here.

Go to the list of all theorems

Fast (1-1/e)-approximation to monotone submodular maximization with matroid constraint

You need to know: Algorithm, randomized algorithm, approximation algorithm, $P\neq NP$ conjecture, notations: $e=2.718...$ for the base of natural logarithm, ${\mathbb R}_+$ for non-negative real numbers, $\emptyset$ for the emply set, $|X|$ for the number of elements in finite set X, $2^X$ for the set of all subsets of X.

Background: A (finite) matroid is a pair $(X,I)$ , where X is a finite set and $I \subset 2^X$ is a family of its subsets, such that (i) $\emptyset \in I$ ; (ii) if $A \in I$ and $A' \subset A$ then $A' \in I$ ; and (iii) if $A \in I$ , $B \in I$ , and $|A|>|B|$ , then there exists $x \in A \setminus B$ such that $B \cup \{x\} \in I$ . A function $f:2^X \to {\mathbb R}_+$ is called monotone if $f(A) \leq f(B)$ whenever $A \subseteq B$ . We also assume that $f(\emptyset)=0$ . f is called submodular if $f(A \cup B) + f(A \cap B) \leq f(A)+f(B)$ for all $A,B \subseteq X$ .

The Theorem: On 2nd September 2008, Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák submitted to the SIAM Journal on Computing a paper in which they proved that there is a randomized algorithm giving a $(1-1/e)$ -approximation (in expectation) to the problem $\max\limits_{S \in I} f(S)$ for any monotone submodular function f (given by a value oracle) and an arbitrary matroid (given by a membership oracle).

Short context: Maximization of a submodular function is a well-studied problem, and a number of interesting and useful combinatorial optimisation problems are its special cases. There is an easy algorithm for the problem $\max\limits_{S \in I} f(S)$ that achieves approximation ratio $1/2$ . The Theorem improves it to $1-1/e = 0.632...$ . It is known that, if $P\neq NP$ , then this approximation ratio is the best possible.

Links: The original paper is available here.

Go to the list of all theorems

Real polynomial interval maps with only real critical points have connected isentropes

You need to know: Eucledean space ${\mathbb R}^n$ , connected subset of ${\mathbb R}^n$ , polynomial, critical point of a polynomial, non-degenerate critical point, notation $f^n$ for the n-th iterate of f.

Background: Let $I=[a,b]$ be an interval in ${\mathbb R}$ , and let $\partial I = \{a,b\}$ be the set of its endpoints. Let $P^d$ be the set of real polynomials of degree d+1 mapping I (and $\partial I$ ) into itself, with precisely d non-degenerate critical points, each of which is contained in the interior of I. For $\epsilon=\pm 1$ , let $P^d_\epsilon \subset P^d$ be the set of polynomials which are increasing (respectively decreasing) at the left endpoint of I when $\epsilon=1$ (respectively $\epsilon=-1$ ). For each polynomial $P(x)=\sum\limits_{i=0}^{d+1}a_ix^i$ one can associate a point $a(P) = (a_0, \dots, a_{d+1})\in {\mathbb R}^{d+2}$ . A subset $S \subseteq P^d_\epsilon$ is called connected if $\{a(P), P \in S\}$ is a connected subset of ${\mathbb R}^{d+2}$ .

Given $f:I \to I$ , assume that I can be decomposed into finitely many subintervals $I_0,\dots, I_m$ on which f is monotone. The smallest number $m+1$ of such intervals is called the lap number $l(f)$ of f. The topological entropy $h_{top}(f)$ of f is $h_{top}(f)=\lim\limits_{n\to\infty}\frac{1}{n}\log l(f^n)$ .

The Theorem: On 20th May 2005, Henk Bruin and Sebastian van Strien submitted to arxiv and the Journal of the AMS a paper in which they proved that, for $\epsilon \in \{-1,+1\}$ , each positive integer d, and each $h_0 \geq 0$ , the set $\{f \in P^d_\epsilon: h_{top}(f) = h_0\}$ (called the isentrope) is connected.

Short context: The lap number $l(f)$ is one of the ways to measure how “complex” is f, and the topological entropy $h_{top}(f)$ measures the “dynamic complexity” of iterates of f. The isentrope $\{f \in P^d_\epsilon: h_{top}(f) = h_0\}$ is the set of polynomials with fixed dynamic complexity. In 1992, Milnor conjectured that this set is connected. Since then, the conjecture was extensively studied and proved for quadratic and cubic polynomials. The Theorem proves the conjecture in full.

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

Go to the list of all theorems

The product of typical interval exchange transformations is uniquely ergodic

You need to know: Direct product $\times$ of sets, Borel probability measure on interval $I=[0,1)$ or unit square $I \times I$ . Also, see this previous theorem description for the notion of interval exchange transformation (IET) on I, and explanation what is meant by “almost every” IET.

Background: The product of maps $f:I \to I$ and $g:I \to I$ is map $f \times g: I \times I \to I \times I$ given by $(f \times g)(x,y)=(f(x), g(y))$ . Let J be either interval $I=[0,1)$ or unit square $I \times I$ . A map $f:J \to J$ is called uniquely ergodic if there exists a unique Borel probability measure $\mu$ on J such that $\mu(f^{-1}(A))=\mu(A)$ for all measurable $A \subset J$ .

The Theorem: On 14th May 2005, Jon Chaika submitted to arxiv a paper in which he proved that, for almost every pair $f,g$ of IETs their product $f \times g$ is uniquely ergodic.

Short context: Interval exchange transformations (IETs in short) are basic examples of measure-preserving transformations $f:I \to I$ (that is, such that $\mu(f^{-1}(A))=\mu(A)$ for all measurable $A \subset I$ ), which are central objects of study in dynamical systems. The fundamental work of Masur and Veech established that almost every IET is uniquely ergodic. The Theorem extends this result to the product of almost every IETs.

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

Go to the list of all theorems