Cayley graphs of symmetric groups can form explicit family of bounded-degree expanders

You need to know: Graph, graphs of bounded degree, group, symmetric group $\text{Sym}(n)$ (group of permutations of n symbols), notation $|A|$ for the number of elements in a finite set $A$ .

Background: $For a graph$ $\Gamma$ $h(\Gamma)=\min\limits_{1\leq |S|\leq |\Gamma|/2} \frac{|\partial S|}{|S|}$ $,$ $\Gamma$ An infinite family of graphs $\Gamma_1, \Gamma_2, \dots, \Gamma_n, \dots$ is a family of $\epsilon$ -expanders if $h(\Gamma_n)\geq \epsilon$ for all n.

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. The (undirected) Cayley graph $\Gamma =\Gamma (G,S)$

The Theorem: On 28th May 2005, Martin Kassabov submitted to arxiv a paper in which he proved the existence of universal constants L and $\epsilon>0$ such that the following holds. For every n there exists a generating set $S_n$ of size at most L of the symmetric group $\text{Sym}(n)$ such that the Cayley graphs $\Gamma(\text{Sym}(n), S_n)$ form a family of $\epsilon$ -expanders.

Short context: Constructing explicit families of expanders is important, for example, for algorithmic applications. Although there are some combinatorial constructions, more traditional method is based on Cayley graphs of groups. Given an infinite family of finite groups, the problem is to construct generating sets to make their Cayley graphs expanders. The Theorem solves this problem for symmetric groups.

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

Go to the list of all theorems

Uncountable set of 2-generated groups with exactly 2 conjugacy classes

You need to know: Group, identity element $e$ in a group, subgroup, isomorphic groups, conjugate elements in a group, conjugacy classes, countable and uncountable sets, notation $|S|$ for the number of elements in finite set S.

Background: A generating set of 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. In particular, it is called 2-generated if it has generating set S with $|S|=2$ . We say that group H can be embedded into group G, if G has a subgroup isomorphic to H. The order of non-identity element $a\in G$ is the lowest positive integer n such that $a^n=e$ , with the convention that the order is infinite if no such n exists. For a group G, let $\pi(G)$ be the set of all (finite) positive integers n such that there exists an element $a \in G$ of order n.

The Theorem: On 2nd November 2004, Denis Osin submitted to arxiv a paper in which he proved, among other results, that any countable group H can be embedded into a 2-generated group G such that any two elements of the same order are conjugate in G and $\pi(H) = \pi(G)$ .

Short context: Applying the Theorem to any torsion-free group H (a group is called torsion-free if all non-identity elements in it have infinite order), we obtain that any countable torsion-free group can be embedded into a torsion-free 2-generated group with exactly 2 conjugacy classes. In turn, this implies that there exist uncountably many pairwise non-isomorphic torsion-free 2-generated groups with exactly 2 conjugacy classes. Before 2004, it was an open question whether there exists any finitely generated group G with $|G|>2$ which has exactly 2 conjugacy classes. The Theorem also implies that for any integer $n \geq 2$ there are uncountably many pairwise nonisomorphic finitely generated groups with exactly n conjugacy classes.

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

Go to the list of all theorems

Quartic rings can be explicitly parametrized

You need to know: Matrix, invertible matrix, determinant of a matrix, group, abelian group, group ${\mathbb Z}^n$ , ring, commutative ring, isomorphic groups and rings.

Background: Each commutative ring R is an abelian group with respect to addition. We say that R has rank n if this group is isomorphic to ${\mathbb Z}^n$ . Rings of rank $n=4$ are called quartic rings. An integral ternary quadratic form is an expression of the form $ax^4+bx^3y+cx^2y^2+dxy^3+ey^4$ with $a,b,c,d,e \in {\mathbb Z}$ . We say that two such forms A and B are linearly independent over ${\mathbb Q}$ if $uA+vB=0$ with rational $u,v$ is possible only if $u=v=0$ . Let $GL_n({\mathbb Z})$ be the set of invertible $n \times n$ matrices with integer entries, and let $GL_2^{\pm 1}({\mathbb Q})$ be the set of $2 \times 2$ matrices with rational entries and determinant $\pm 1$ .

The Theorem: On 29th February 2004, Manjul Bhargava submitted to the Annals of Mathematics a paper in which he proved the existence of a canonical bijection between isomorphism classes of nontrivial quartic rings and $GL_3({\mathbb Z}) \times GL^{\pm 1}_2({\mathbb Q})$ -equivalence classes of pairs $(A,B)$ of integral ternary quadratic forms where A and B are linearly independent over ${\mathbb Q}$ .

Short context: Explicit parametrizations for rings of ranks $n=2$ (known as quadratic rings) and $n=3$ (cubic rings) are relatively easy and well-known. The Theorem provides such a parametrization for quartic rings. In a later work, Bhargava also obtained explicit parametrization for rings of rank $n=5$ (quintic rings).

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

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

Zero-divisor graph of a local ring with at least 33 elements is not planar

You need to know: Ring, commutative ring, zero-divisor in a ring, graph, planar graph.

Background: Let R be a commutative ring. Element $u \in R$ is a unit if there is $v \in R$ such that $uv = vu = 1$ . Ring R is called local if $1 \neq 0$ and the sum of any two non-units in R is a non-unit. Let $Z(R)$ be the set of zero-divisors of R. The zero-divisor graph $\Gamma(R)$ of R is the graph with vertices $Z(R)\setminus\{0\}$ such that there is an (undirected) edge between vertices $a$ and $b$ if and only if $a \neq b$ and $ab=0$ .

The Theorem: On 15th September 2002, Saieed Akbari, Hamid Maimani, and Siamak Yassemi submitted to the Journal of Algebra a paper in which they proved, among other results, that if R is a local ring with at least 33 elements, and $\Gamma(R)\neq \emptyset$ , then $\Gamma(R)$ is not planar.

Short context: Studying properties of zero-divisor graphs of rings is important for understanding the structure of rings and their zero divisors. In particular, Anderson, Frazier, Lauve, and Livingston asked in 2001 an interesting question: which finite commutative rings have planar zero-divisor graphs? The Theorem answers this question for local rings.

Links: The original paper is available here.

Go to the list of all theorems

A group with exponential growth but not uniform exponential growth

You need to know: Group, finitely generated group, generating set.

Background: Let G be a finitely generated group. For any finite generating set S of G, let $\gamma_S(k)$ be the number of elements of G which are the product of at most k elements in $S \cup S^{-1}$ . Let $e_S(G)=\lim\limits_{k \to \infty}\sqrt[k]{\gamma_S(k)}$ . It is known that if $e_S(G)>1$ for some S then in fact $e_S(G)>1$ for all S, and, in this case, we say that G has exponential growth. If, moreover, $\inf_S e_S(G) > 1$ , where the infimum is taken over all finite generating sets S of G, we say that G has uniform exponential growth.

The Theorem: On 22nd June 2002, John Wilson submitted to Inventiones Mathematicae a paper in which he proved the existence of a finitely generated group G which has exponential growth but not uniform exponential growth.

Short context: In 1981, Gromov asked whether every group of exponential growth have uniform exponential growth. The question was answered affirmatively in many special cases, for example, for linear groups. The Theorem, however, shows that in general the answer is negative.

Links: The original paper is available here.

Go to the list of all theorems

Linear groups of exponential growth have uniform exponential growth

You need to know: Complex numbers, matrix with complex entries, matrix multiplication, invertible matrix, group, subgroup, finitely generated group, generating set.

Background: Let G be a finitely generated subgroup of $GL_n({\mathbb C})$ (the group of $n \times n$ invertible matrices with complex entries). For any finite generating set S of G, let $\gamma_S(k)$ be the number of elements of G which are the product of at most k matrices in $S \cup S^{-1}$ . Let $e_S(G)=\lim\limits_{k \to \infty}\sqrt[k]{\gamma_S(k)}$ .

The Theorem: On 23rd August 2001, Alex Eskin, Shahar Mozes, and Hee Oh submitted to arxiv a paper in which they proved that if G is a finitely generated subgroup of $GL_n({\mathbb C})$ and $e_S(G)>1$ for some S then $\inf_S e_S(G) > 1$ , where the infimum is taken over all finite generating sets S of G.

Short context: Subgroups of $GL_n({\mathbb C})$ are examples of linear groups. For any finitely generated group (not necessary linear), it is known that if $e_S(G)>1$ for some S then in fact $e_S(G)>1$ for all S, and, in this case, we say that G has exponential growth. If $\inf_S e_S(G) > 1$ , we say that G has uniform exponential growth. In 1981, Gromov asked whether every group of exponential growth has uniform exponential growth. The Theorem answers this question affirmatively for subgroups of $GL_n({\mathbb C})$ . In a later work, Wilson proved that in general the answer to Gromov’s question is negative.

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

Go to the list of all theorems

A polynomial is matrix-positive if and only if it is the sum of squares

You need to know: Matrix, transpose $A^T$ of matrix $A$ , matrix addition and multiplication, positive semidefinite matrix.

Background: Consider a set of $2n$ variables, which we denote $x_1, x_2, \dots, x_n, x_1^T, x_2^T, \dots, x_n^T$ . A noncommutative monomial in these variables is any expression of the form $ay_1y_2\dots y_m$ , where $a$ is a real coefficient and each $y_i$ is equal to either $x_j$ or $x_j^T$ for some j. A noncommutative polynomial Q(.) is the sum of any number of such monomials. If we substitute into Q(.) any real matrices $A_1, \dots, A_n$ of any dimension $r \times r$ instead of variables $x_1, x_2, \dots, x_n$ , and their transposes $A^T_1, \dots, A^T_n$ instead of variables $x_1^T, \dots, x_n^T$ , then $Y=Q(A_1, \dots, A_n,A^T_1, \dots, A^T_n)$ is an $r \times r$ matrix. Let S(Q) be the set of all matrices Y which can be obtained in this way. If all matrices in S(Q) are symmetric, we call Q(.) symmetric. If all matrices in S(Q) are positive semidefinite, we call Q(.) matrix-positive. Finally, we say that Q(.) is the sum of squares if $Q(.)=\sum_{i=1}^k h_i(.)^Th_i(.)$ , where $h_i(.), \, i=1,2,\dots,k$ are noncommutative polynomials in the same variables.

The Theorem: On 31st July 2001, William Helton submitted to the Annals of Mathematics a paper in which he proved that a noncommutative symmetric polynomial is matrix positive if and only if it is the sum of squares.

Short context: For multivariate polynomials in real variables, sum of square representation is one of the main methods to prove that a polynomial is non-negative. This method, however, does not always work because there exist non-negative polynomials which have no sum of square representations. In contrast to this, the Theorem proves that in noncommutative (matrix) setting every matrix-positive polynomial has sum of squares representation.

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

Go to the list of all theorems

A finitely presented non-amenable group without free non-cyclic subgroups

You need to know: Group, subgroup, presentation of a group in the form $<S|R>$ , where S is a set of generators and R is a set of relations, group $SO(3)$ of rotations in ${\mathbb R}^3$ .

Background: A group G is called finitely presented if it has a presentation $<S|R>$ with finite number of generators and finite set of relations. A group G is called free if it has presentation $<S|\emptyset>$ , that is, with no relations. A free group is called non-cyclic if it has at least 2 generators.

A group G is called amenable if it has a left invariant finitely additive probability measure, that is, a function $\mu$ from subsets of G to $[0,1]$ such that (i) $\mu(G)=1$ , (ii) $\mu(A\cup B)=\mu(A)+\mu(B)$ whenever $A\cap B=\emptyset$ , and (iii) $\mu(gA)=\mu(A)$ for all $g\in G$ , where $gA=\{h\in G \,|\, h=ga, \, a\in A\}$ .

The Theorem: On 8th February 2001, Alexander Ol’shanskii and Mark Sapir submitted to Publications Mathématiques a paper in which they proved the existence of a finitely presented non-amenable group without free non-cyclic subgroups.

Short context: In 1924, Banach and Tarski proved that one can decompose a unit ball into a finite number of disjoint pieces, move and rotate the pieces, and construct two unit balls! This is known as Banach–Tarski paradox. In 1929, von Neumann introduced the notion of amenable groups, and proved that Banach–Tarski paradox arises because the group $SO(3)$ is not amenable. In fact, he proved that any group containing a free non-cyclic subgroup is not amenable, and asked if the converse is true. In 1980, Ol’shanskii proved the existence of counterexample to this von Neumann’s problem. The Theorem provides the first finitely presented counterexample.

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

Go to the list of all theorems

Robbins conjecture on the number of vertically symmetric ASMs is true

You need to know: Product notation $\prod\limits_{i=1}^n$ , matrices.

Background: An $n \times n$ matrix with elements $a_{ij}$ is called an alternating-sign matrix (ASM) if (i) all $a_{ij}$ are equal to -1, 0, or 1, (ii) the sum of elements in each row and column is 1, and (iii) the non-zero elements in each row and column alternate in sign. An ASM is called (a) vertically symmetric (VSASM) if $a_{ij}=a_{i,n+1-j}$ for all i,j; (b) half-turn symmetric (HTSASM) if $a_{ij}=a_{n+1-i, n+1-j}$ for all i,j; (c) quarter-turn symmetric (QTSASM) if $a_{ij} = a_{j,n+1-i}$ for all i,j. Let $A(n), A_V(n), A_{HT}(n)$ and $A_{QT}(n)$ denote the number of $n \times n$ ASMs, VSASMs, HTSASMs, and QTSASMs, respectively. It is known that $A(n) = (-3)^{\frac{n(n-1)}{2}}\prod\limits_{i=1}^n \prod\limits_{j=1}^n\frac{3(j-i)+1}{j-i+n}.$

The Theorem: On 24th August 2000, Greg Kuperberg submitted to arxiv a paper in which he proved that $A_V(2n+1) = (-3)^{n^2} \prod\limits_{i=1}^{2n+1} \prod\limits_{j=1}^n \frac{3(2j-i)+1}{2j-i+2n+1}$ . In addition, $A_{HT}(2n)=A(n) \cdot (-3)^{\frac{n(n-1)}{2}} \prod\limits_{i=1}^n \prod\limits_{j=1}^n \frac{3(j-i)+2}{j-i+n}$ , and $A_{QT}(4n) = A_{HT}(2n)\cdot A(n)^2.$

Short context: Alternating-sign matrices are important both in pure mathematics (determinant computation) and applications (so-called “six-vertex model” for ice modelling in statistical mechanics). The formula for $A(n)$ was conjectured by Robbins and Rumsey in 1986 and proved by Zeilberger in 1996. In 1991, Robbins conjectured formulas for the number of ASMs with various symmetries, including VSASMs, HTSASMs, QTSASMs, and others. The Theorem proves a large portion of these conjectures and opens the road to the resolution of the remaining ones in the subsequent work.

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

Go to the list of all theorems