If d>=3, exists convex body in R^d, not a ball, with same-volume maximal hyperplane sections

You need to know: Euclidean space ${\mathbb R}^d$ , origin $0=(0,\dots,0)$ , Euclidean ball in ${\mathbb R}^d$ , unit sphere ${\mathbb S}^{d-1}\subset{\mathbb R}^d$ , hyperplane orthogonal to a vector, notation $\text{vol}_k$ for k-dimensional volume, convex body in ${\mathbb R}^d$ (compact, convex set $K\subset{\mathbb R}^d$ with a non-empty interior $\text{int}(K)$ ), origin-symmetric convex bodies.

Background: For a convex body $K \subset {\mathbb R}^d$ with $0\in\text{int}(K)$ , and $u\in {\mathbb S}^{d-1}$ , let $M_k(u)=\max\limits_{t \in {\mathbb R}} \text{vol}_{d-1}\left(K \cap (u^{\perp} + tu) \right)$ , where $u^{\perp}$ is the hyperplane containing the origin and orthogonal to u, and $K \cap (u^{\perp} + tu)$ is the section of K by the affine hyperplane $u^{\perp} + tu$ .

The Theorem: On 1st January 2012, Fedor Nazarov, Dmitry Ryabogin, and Artem Zvavitch submitted to arxiv a paper in which they proved that in all dimensions $d\geq 3$ , there exists a convex body $K\subset{\mathbb R}^d$ that is not a Euclidean ball such that $M_k(u)=c_K$ for some constant $c_K$ independent of u.

Short context: It is known that for origin-symmetric convex bodies $K_1,K_2 \subset {\mathbb R}^d$ the condition $M_{K_1}(u) = M_{K_2}(u) \, \forall u\in {\mathbb S}^{d-1}$ implies that $K_1=K_2$ . In particular, if $M_K(u) = c$ is a constant, then K must be an Euclidean ball in ${\mathbb R}^d$ . In 1969, Klee asked whether the same is true for general (not necessary origin-symmetric) convex bodies. The Theorem gives a negative answer to this question.

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

Go to the list of all theorems

Erdős conjecture on square-free values of f(p), f cubic, p prime, is true

You need to know: Set ${\mathbb Z}$ of integers, greatest common divisor $\text{gcd}(a,b)$ of integers $a,b$ , notation $|S|$ for the number of elements in finite set S, primes, infinite product, cubic polynomial and its roots, big O notation, small o notation.

Background: For integer $m>0$ , let $P(m)$ be the set of integers $0<k<m$ such that $\text{gcd}(k,m)=1$ . For function $f:{\mathbb Z} \to {\mathbb Z}$ , let $P_f(m)$ be the set of $k\in P(m)$ such that $f(k)$ is divisible by m. Let $c_f = \prod\limits_{p\in {\cal P}} \left(1-\frac{|P_f(p^2)|}{|P(p^2)|}\right)$ , where ${\cal P}=\{2,3,5,\dots\}$ is the set of all primes. An integer is called square-free if it is not divisible by the square $d^2$ of any integer $d>1$ .

The Theorem: On 16th December 2011, Harald Helfgott submitted to arxiv a paper in which he proved the following result. Let $f$ be a cubic polynomial with integer coefficients without repeated roots. Then the number of prime numbers $p\leq N$ such that $f(p)$ is square-free is $(1+o(1))c_f \frac{N}{\log N} + O(1)$ .

Short context: For linear polynomial $f(x)=mx+a$ , $f(n)$ is square-free for infinitely many integers n provided that $\text{gcd}(a,m)$ is square-free. In 1931, Estermann proved that $f(n)$ is square-free infinitely often (subject to easy-to-check necessary conditions on f) for quadratic polynomials f. In 1953, Erdős did the same for cubic polynomials. Erdős also conjectured that if cubic polynomial f has no repeated roots and for every prime q there exists $k\in P(q^2)$ such that $f(k)$ is not divisible by $q^2$ , then $f(p)$ is square-free for infinitely many primes p. The Theorem confirms this conjecture.

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

Go to the list of all theorems

Two n by n matrices can be multiplied using O(n^2.3737) operations

You need to know: Matrix, matrix multiplication, big O notation

Background: Not needed

The Theorem: On 14th November 2011, Andrew Stothers and Alexander Davie submitted to Proceedings of the Royal Society of Edinburgh a paper in which they proved that $n\times n$ matrices can be multiplied using $O(n^{2.3737})$ operations.

Short context: Matrix multiplication is a basic operation which lies in the core of many algorithms, so doing it faster makes a big impact. A trivial algorithm for multiplying $n\times n$ matrices takes $O(n^3)$ operations. In 1968 Strassen described a faster method requiring only $O(n^{\log_2 7}) \approx O(n^{2.81})$ operations. Then many authors developed faster and faster methods, but, after 1990 algorithm of Coppersmith and Winograd running in time $O(n^{2.375477\dots})$ , the progress stopped for almost 20 years. The Theorem provides a better algorithm. It opens the road for further progress, with the current record being $O(n^{2.3728639\dots})$ . A big open question is whether this can be improved to $O(n^2)$ , which would be optimal.

Links: The original paper is available here.

Go to the list of all theorems

The diameter of the symmetric group Sym(n) is at most exp(O[(log n)^4 log(log n)])

You need to know: Group, finite group, symmetric group $\text{Sym}(n)$ (group of permutations of n symbols), big O notation, small o notation.

Background: A generating set of a group G is a subset $S \subset G$ such that every $g\in G$ can be written as a finite product of elements of S and their inverses. For a finite group G with generating set S, let $d(G,S)$ be the minimal integer m such that every $g\in G$ can be expressed as a product of at most m elements of S and their inverses. The diameter $\text{diam}(G)$ of group G is the maximal value of $d(G,S)$ over all choices of the generating set S.

The Theorem: On 16th September 2011, Harald Helfgott and Akos Seress submitted to arxiv a paper in which they proved the existence of constant C such that $\text{diam}(\text{Sym}(n)) \leq \exp(C(\log n)^4\log\log n)$ for all n.

Short context: It has long been conjectured that the diameter of the symmetric group
$\text{Sym}(n)$ is polynomially bounded in n. However, before 2011, the best upper bound was $\text{diam}(\text{Sym}(n)) \leq \exp((1+o(1))\sqrt{n\log n})$ proved by Babai and Seress in 1988. The Theorem provides a much better upper bound.

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

Go to the list of all theorems

Fast recovery of n-component vector from O(n log n) random magnitude measurements

You need to know: Set of complex numbers ${\mathbb C}$ , absolute value $|z|$ of $z \in {\mathbb C}$ , set ${\mathbb C}^n$ of vectors with n complex coordinates, inner product $(x,y)=\sum\limits_{i=1}^n x_iy_i$ in ${\mathbb C}^n$ , unit sphere in ${\mathbb C}^n$ , polynomial-time algorithm, probability, sampling independently and uniformly from a set, big O notation.

Background: Let $x \in {\mathbb C}^n$ , and let $z_1, \dots z_m$ be vectors independently and uniformly sampled from the unit sphere in ${\mathbb C}^n$ . Numbers $b_i=|(x,z_i)|^2, \, i=1,2,\dots,m$ are called magnitude measurements of x.

The Theorem: In September 2011, Emmanuel Candes, Thomas Strohmer, and Vladislav Voroninski submitted to Communications on Pure and Applied Mathematics a paper in which they proved the existence of positive constants $c_0$ and $\gamma$ such that an arbitrary $x \in {\mathbb C}^n$ can be exactly recovered from $m \geq c_0 n \log n$ magnitude measurements in polynomial time with probability at least $1-3e^{-\gamma m/n}$ .

Short context: In applications, x represents a signal, and $(x,z_i)$ represent measurements. In many applications, only the absolute value of $(x,z_i)$ can be measured – this is called “magnitude measurements”. If vectors $z_i$ are fixed and given, the problem of recovering x from $b_i$ may be computationally infeasible. The Theorem states, however, that we can select $z_i$ at random, and recover x efficiently with high probability after the number of measurements not much higher than the dimension.

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

Go to the list of all theorems

The chromatic threshold of a graph H with chromatic number r>=3 can be (r-3)/(r-2), (2r-5)/(2r-3), or (r-2)/(r-1)

You need to know: Graph, isomorphic graphs, subgraph, degree of a vertex of graph G, chromatic number $\chi(G)$ of graph G.

Background: We say that graph G has minimum degree at least M if the degree of each vertex of G is at least M. A graph G is called H-free, if it does not have a subgraph isomorphic to H. The chromatic threshold $\delta_\chi(H)$ of a graph H is the infimum of $d>0$ such that there exists $C=C(H,d)$ for which every H-free graph G with minimum degree at least $d|G|$ satisfies $\chi(G) \leq C$ .

The Theorem: On 8th August 2011, Peter Allen, Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa, and Robert Morris submitted to arxiv a paper in which they proved that the chromatic threshold of every graph H with $\chi(H)=r\geq 3$ must be either $\frac{r-3}{r-2}$ , or $\frac{2r-5}{2r-3}$ , or $\frac{r-2}{r-1}$ .

Short context: In 1940th, Zykov and Tutte constructed triangle-free graphs
with arbitrarily large chromatic number. In 1959, Erdős did the same for H-free graphs for any graph H containing a cycle. In 1973, Erdős and Simonovits suggested to investigate this question for graphs with large minimum degree, defined the chromatic threshold $\delta_\chi(H)$ , and asked to determine $\delta_\chi(H)$ for every graph H. The Theorem lists 3 possible values for $\delta_\chi(H)$ for every graph H with $\chi(H)\geq 3$ . The authors also determined exactly for which graphs H $\delta_\chi(H)$ is equal to each value. Together with known fact that $\delta_\chi(H)=0$ if $\chi(H)\leq 2$ , this answers the question of Erdős and Simonovits for all graphs H.

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

Go to the list of all theorems

There exist groups of oscillating intermediate growth

You need to know: Notations ${\mathbb N}$ for the set of positive integers, ${\mathbb R}_+$ for the set of positive real numbers, basic group theory.

Background: A generating set of a group G is a subset $S \subset G$ such that every $g\in G$ can be written as a finite product of elements of S and their inverses. Group G is called finitely generated if it has a finite generating set S. Let $\gamma_S(n)$ be the number of elements of G which are the product of at most n elements in $S \cup S^{-1}$ .

The Theorem: On 1st August 2011, Martin Kassabov and Igor Pak submitted to arxiv a paper in which they proved that for every increasing function $\mu:{\mathbb N}\to {\mathbb R}_+$ such that $\lim\limits_{n\to\infty}\frac{\mu(n)}{n}=0$ , there exists a finitely generated group G and its finite generating set S such that (i) $\gamma_S(n) < \exp(n^{4/5})$ for infinitely many $n\in {\mathbb N}$ , but (ii) $\gamma_S(n') > \exp(\mu(n'))$ for infinitely many $n'\in {\mathbb N}$ .

Short context: The rate of growth of $\gamma_S(n)$ can tell a lot about structure of the underlying group G. Groups with $\gamma_S(n)$ bounded from above by some polynomial are called virtually nilpotent. If $\lim\limits_{n \to \infty}\sqrt[n]{\gamma_S(n)}>1$ , we say that G has exponential growth, see here. In 1980, Grigorchuk constructed first examples of groups of intermediate growth, that is, ones for which $\gamma_S(n)$ grows faster than polynomial but slower than exponent. The Theorem proves the existence of groups whose growth is not only intermediate but oscillating: $\gamma_S(n)$ is smaller than $\exp(n^{4/5})$ for some values of n, but is higher than, say, $\exp(n/\log \log \log n)$ for other values of n.

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

Go to the list of all theorems

The BMV (Bessis-Moussa-Villani) conjecture is true

You need to know: Complex number, conjugate $\bar{z}$ of complex number z, matrix with complex entries, matrix multiplication, eigenvalues of an $n\times n$ matrix, infinite series, positive measure, integration.

Background: Let A be $n\times n$ matrix with complex entries $a_{ij}$ . The trace of A is $\text{tr}[A]=\sum\limits_{i=1}^n a_{ii}$ . An exponent $\exp(A)$ of matrix A is $n\times n$ matrix given by $\exp(A)=\sum\limits_{k=0}^\infty \frac{1}{k!}A^k$ . Matrix A is called Hermitian if $a_{ij}=\bar{a}_{ji}$ for all $i,j$ . A Hermitian matrix is called positive semidefinite if all its eigenvalues are non-negative real numbers.

The Theorem: On 25th July 2011, Herbert Stahl submitted to arxiv a paper in which he proved the following result. Let A and B be two $n\times n$ Hermitian matrices and let B be positive semidefinite. For $t\geq 0$ , let $f(t) = \text{Tr}[\exp(A-tB)]$ . Then there exists a positive measure $\mu$ on $[0,\infty)$ (which may depend on A and B), such that $f(t)=\int_0^\infty e^{-ts}d\mu(s)$ for all t.

Short context: The Theorem confirms a conjecture of Bessis, Moussa, and Villani made in 1975, which was known as the BMV conjecture. The conjecture was extensively studied and had a number of equivalent formulations.

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

Go to the list of all theorems

Zaremba’s conjecture is true for a set of density one

You need to know: Notation ${\mathbb N}$ for the set of positive integers, greatest common divisor $\text{gcd}(a,b)$ for $a,b\in{\mathbb N}$ , notation $\left \lfloor{x}\right \rfloor$ for the largest integer not exceeding real number x.

Background: For a real number x, define a sequence $\{x_n\}$ by the rules: (i) $x_0=x$ , and (ii) for $n\geq 0$ , if $x_n$ is an integer then stop, otherwise let $x_{n+1}=\frac{1}{x_n-\left\lfloor{x_n}\right \rfloor}$ . This sequence may be finite or infinite depending on x. Let $a_n=\left\lfloor{x_n}\right \rfloor$ for all n. Notation $x=[a_0; a_1, a_2, \dots, a_n,\dots]$ in called continued fraction expansion of x. For $A>0$ , let $D(A)$ be the set of $d \in {\mathbb N}$ , for which there exist an integer $b$ , such that $0<b<d$ , $\text{gcd}(b,d)=1$ , and $\frac{b}{d}$ has a finite continuous fraction expansion $\frac{b}{d}=[0; a_1, \dots a_n]$ such that $a_k \leq A$ , $k=1,\dots,n$ .

The Theorem: On 19th July 2011, Jean Bourgain and Alex Kontorovich submitted to arxiv a paper in which they proved the following result. Let $K(N)$ be the number of integers less than $N$ belonging to $D(50)$ . Then $\lim\limits_{N\to\infty} \frac{K(N)}{N} = 1$ .

Short context: If we fix bound A and study rational numbers in the form $[a_0; a_1, a_2, \dots, a_n]$ such that $a_i\leq A$ , $\forall i$ , what positive integers can occur as a denominator of such a number in reduced form? Zaremba conjectured in 1971 that every number can! More formally, Zaremba’s conjecture states that there exists $A>0$ such that $D(A)={\mathbb N}$ . In fact, Zaremba suggested that $A=5$ may work. While this conjecture remains open, the Theorem states that, for $A=50$ , “almost every” positive integer belongs to $D(A)$ .

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

Go to the list of all theorems

The Hanna Neumann conjecture is true

You need to know: Group, subgroup, trivial and non-trivial subgroup, free group.

Background: A generating set of a group G is a subset $S \subset G$ such that every $g\in G$ can be written as a finite product of elements of S and their inverses. Group G is called finitely generated if it has finite generating set. The rank $\text{rank}(G)$ of a group G is the smallest cardinality of a generating set for G.

The Theorem: On 1st May 2011, Joel Friedman submitted to arxiv a paper in which he proved that if ${\cal K}, {\cal L}$ are nontrivial, finitely generated subgroups of a free group ${\cal F}$ , then ${\cal K}\cap{\cal L}$ is finitely generated, and $\text{rank}({\cal K}\cap{\cal L})-1\leq (\text{rank}({\cal K})-1)(\text{rank}({\cal L})-1)$ .

Short context: In 1954, Howson showed that, for ${\cal K}, {\cal L}$ as in the Theorem, $\text{rank}({\cal K}\cap{\cal L})-1 \leq 2 \,\text{rank}{\cal K}\,\text{rank}{\cal L}-\text{rank}{\cal K}-\text{rank}{\cal L}$ . Few years later, Hanna Neumann improved this to $\text{rank}({\cal K}\cap{\cal L})-1\leq 2 \, (\text{rank}({\cal K})-1)(\text{rank}({\cal L})-1)$ , and conjectured that factor 2 in this bound can be removed. This conjecture became known as the Hanna Neumann Conjecture, and was opened for over 50 years. The Theorem confirms this conjecture. In fact, it proves a stronger conjecture, known as Strengthened Hanna Neumann Conjecture, formulated in 1990. On 11th May 2011, Igor Mineyev submitted to the Annals of Mathematics a paper with independent proof of these results.

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

Go to the list of all theorems