Every position of Rubik’s Cube can be solved in 20 moves or less

You need to know: Rubik’s Cube

Background: A move in the Rubik’s Cube is defined as any twist of any face. By solution of a position of Rubik’s Cube we mean the sequence of moves after which each face of Rubik’s Cube has only one colour.

The Theorem: On 24th February 2012, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge submitted to the SIAM Journal on Discrete Mathematics a paper in which they gave an exposition of their computational proof that every starting position of Rubik’s Cube can be solved in 20 moves or less.

Short context: Rubik’s Cube, invented by Ernő Rubik in 1974, is widely considered to be the world’s best-selling toy. The least integer n such that every position can be solved in at most n moves is known as God’s number. The problem of determining the God’s number (let us denote it $g$ ) has been of interest ever since the Rubik’s Cube is invented. A simple counting argument proves that $g\geq 18$ . The first upper bound $g\leq 52$ was proved by Thistlethwaite in 1981. Then many researches proved better and better lower and upper bounds. The Theorem culminates this line of research and determines the God’s number exactly: $g=20$ .

Links: The original paper is available here.

Go to the list of all theorems

Every measure preserving word is primitive

You need to know: Group, finite group, free group, free generating set in a free group.

Background: Let $F_k$ be the free group with k generators $x_1, \dots x_k$ . Any element $w\in F_k$ (which we call word) can be written as $w=\prod\limits_{j=1}^r x_{i_j}^{\epsilon_j}$ for some $1 \leq i_1 < \dots < i_r \leq k$ and $\epsilon_j = \pm 1$ , $j=1,\dots,r$ . For every group G, w induces a word map from $w:G^k \to G$ given by $w(g_1, \dots, g_k)=\prod\limits_{j=1}^r g_{i_j}^{\epsilon_j}$ . If G is a finite group and $g\in G$ , let $N_G^w(g)$ be the number of $(g_1, \dots, g_k)\in G^k$ such that $w(g_1, \dots, g_k)=g$ . The word w is called measure preserving with respect to G if $N_G^w(g)=N_G^w(h)$ for every $g,h \in G$ . We say that w is measure preserving if it is measure preserving with respect to any every finite group G. The word w is called primitive if it belongs to some basis (free generating set) of $F_k$ .

The Theorem: On 15th February 2012, Doron Puder and Ori Parzanchevski submitted to arxiv a paper in which they proved that every measure preserving word is primitive.

Short context: Word maps in groups are the subject of intensive study with lots of nice recent results, see, for example, here. It is not difficult to check that every primitive word is measure preserving, and several authors have conjectured that the converse is also true. In a paper submitted in 2011, Puder proved this conjecture for words in $F_2$ . The Theorem confirms 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 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

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

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

The absolute values of the coefficients of the chromatic polynomial form a log-concave sequence

You need to know: Graph, proper colouring of vertices of a graph, polynomial.

Background: A sequence $x_0, x_1, \dots, x_n$ of real numbers is called log-concave if $x_{i-1}x_{i+1} \leq x_i^2$ for all $0<i<n$ . For a finite graph G and integer $q>0$ , let $\chi_G(q)$ be the number of proper colouring of vertices of G with q colours. It is known that $\chi_G(q)$ is in fact a polynomial $\chi_G(q)=\sum\limits_{k=0}^n (-1)^{n-k}a_k q^k$ , where $a_0, a_1 \dots, a_n$ are non-negative integers.

The Theorem: On 27th August 2010, June Huh submitted to arxiv a paper in which he proved that if $\chi_G(q)=\sum\limits_{k=0}^n (-1)^{n-k}a_k q^k$ is the chromatic polynomial of a graph G, then the sequence $a_0, a_1 \dots, a_n$ is log-concave.

Short context: The chromatic polynomial was introduced by Birkhoff in 1912, and is one of the most beautiful objects of study in graph theory. In 1968, Read conjectured that the sequence of the absolute values of the coefficients of the chromatic polynomial is unimodal (that is, $a_0 \leq a_1 \leq \dots \leq a_{i-1} \leq a_i \geq a_{i+1} \geq \dots \geq a_n$ for some $0 \leq i \leq n$ ). In 1971, Rota conjectured that this sequence is in fact log-concave and observed that this would imply the Read’s conjecture. The Theorem confirms this prediction. In fact, Rota conjectured an even more general statement, which was also proved in a later work.

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

Go to the list of all theorems

The least squares mean for positive definite matrices is monotone

You need to know: Matrix, square matrix, symmetric matrix, eigenvalue of a square matrix, matrix multiplication, inverse $A^{-1}$ of matrix A.

Background: Let $\lambda_i(A), i=1,\dots,n$ denote the eigenvalues of $n \times n$ symmetric matrix A. If all $\lambda_i(A)$ are non-negative, A is called positive semidefinite, while if all $\lambda_i(A)$ are positive, A is called positive definite. Let $P_n$ be the set of all positive definite $n \times n$ matrices. For $A,B \in P_n$ , we write $A\geq B$ if $A-B$ is positive semidefinite. The trace metric distance between $A,B \in P_n$ is $\delta(A,B)=\sqrt{\sum\limits_{i=1}^n \log^2 \lambda_i(A^{-1}B)}$ . The least squares mean (also known as Karcher mean) of k matrices $A_1, \dots, A_k \in P_n$ is $\sigma(A_1, \dots, A_k)=\arg \min\limits_{X\in P_n}\sum\limits_{i=1}^k \delta^2(X,A_i)$ .

The Theorem: On 27th June 2010, Jimmie Lawson and Yongdo Lim submitted to arxiv and Mathematische Annalen a paper in which they proved that if $B_i \leq A_i$ , $i=1,\dots,k$ , then $\sigma(B_1, \dots, B_k) \leq \sigma(A_1, \dots, A_k)$ .

Short context: The concept of least squares mean is a natural generalisation of the geometric mean that has been developed by Grove and Karcher in 1973 for general metric spaces, and applied to positive definite matrices by Moakher in 2005. The property proved in the Theorem is called monotonicity of the least squares mean, and was conjectured by Bhatia and Holbrook in 2006.

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

Go to the list of all theorems

w_1(G)w_2(G)=G for any nontrivial group words w_1,w_2 and any large finite non-abelian simple group G

You need to know: Group, identity element, finite group, notation $|G|$ for the number of elements in a finite group G, abelian and non-abelian groups, 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^2=A \cdot A$ .

The Theorem: On 10th February 2010, Michael Larsen, Aner Shalev, and Pham Tiep submitted to the Annals of Mathematics a paper in which they proved that for each pair of non-trivial words $w_1$ , $w_2$ there exists $N =N(w_1, w_2)$ such that for every finite non-abelian simple group G with $|G|\geq N$ we have $w_1(G)\cdot w_2(G) = G$ .

Short context: In 2001, Liebeck and Shalev deduced from this theorem that for any 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. In 2006, Shalev proved that this holds with $c=3$ , independently of w. In 2007, Larsen and Shalev proved that, for some groups (called alternating groups), one can even take $c=2$ . The Theorem states that one can in fact take $c=2$ for all w and all large G. This is clearly the best possible in general, but see here and here for the proof that $c=1$ works for some specific words w.

Links: The original paper is available here.

Go to the list of all theorems

When n>=5, the Dehn function of SL(n;Z) is quadratic

You need to know: Notation ${\mathbb Z}$ for the set of integers, ${\mathbb N}$ for the set of positive integers, matrix, determinant of a matrix, group, group $SL(n;{\mathbb Z})$ of $n\times n$ matrices with integer entries and determinant 1, presentation of a group in the form $<S|R>$ where S is a set of generators and R is a set of relations, finitely presented group.

Background: For functions $f; g : {\mathbb N} \to {\mathbb N}$ , we write $g \succeq f$ if there is a c such that $f(n) \leq cg(cn + c) + c$ for all n, and $f \sim g$ if $g \succeq f$ and $g \succeq f$ . A word in a finitely presented group G is any product of generators and their inverse elements. For any word w representing the identity element e, there is a sequence of steps that reduces w to the empty word, where each step is a free reduction or insertion or the application of a relator. We call the number of applications of relators in a sequence its cost, and let T(w) be the minimum cost of a sequence that transforms w into e. The Dehn function is $\delta_G(n) =\max\limits_{w:l(w)\leq n} T(w)$ , where the maximum is taken over words of length at most n representing the identity. We say that the Dehn function is quadratic if $\delta_G(n) \sim n^2$ . This property depends only on G but not on set of generators.

The Theorem: On 14th December 2009, Robert Young submitted to arxiv a paper in which he proved that, for any $n\geq 5$ , the Dehn function of $SL(n;{\mathbb Z})$ is quadratic.

Short context: The growth rate of the Dehn function is a fundamental invariant of a finitely presented group, which connects group theory, theory of algorithms, and geometry. For $SL(n;{\mathbb Z})$ , the Dehn function grows linearly for $n=2$ , and exponentially fast for $n=3$ . For $n\geq 4$ , Thurston conjectured that it grows quadratically. The Theorem confirms this conjecture for $n\geq 5$ .

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

Go to the list of all theorems