There exist finitely generated simple groups of intermediate growth

You need to know: Group, simple 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 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}$ . We say that group G (i) has a polynomial growth rate if $\gamma_S(n) \leq C(n^k+1)$ for some constants $C,k < \infty$ ; (ii) has an exponential growth rate if $\gamma_S(n) \geq a^n$ for some $a>1$ , and (iii) is of intermediate growth if neither (i) nor (ii) is true. Properties (i)-(iii) does not depend on S.

The Theorem: On 6th January 2016, Volodymyr Nekrashevych submitted to arxiv a paper in which he, among other results, proved the existence of finitely generated simple groups of intermediate growth.

Short context: The rate of growth of $\gamma_S(n)$ can tell a lot about structure of the underlying group G, and is one of the central research directions in group theory. The existence of groups of intermediate growth was an open question, until the first examples were constructed by Grigorchuk in 1980. Since then, other constructions have been discovered, but all known groups of intermediate growth were not simple. The Theorem provides the first examples of simple groups of intermediate growth, affirnatively answering the 1984 question of Grigorchuk. In particular, the Theorem generalises (and implies) this previous result about existence of finitely generated simple amenable groups (because every group of intermediate growth is amenable).

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

Go to the list of all theorems

All Robbins conjectures on the number of ASMs with symmetries are true

You need to know: Notation $n!=1\cdot 2 \cdot \dots \cdot n$ , 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 diagonally and antidiagonally symmetric (DASASM) if $a_{ij} = a_{ji} = a_{n+1-j,n+1-i}$ for all $1\leq i,j \leq n$ .

The Theorem: On 18th December 2015, Roger Behrend, Ilse Fischer, and Matjaž Konvalinka submitted to arxiv a paper in which they proved that, for any positive integer n, the number of $(2n+1)\times(2n+1)$ DASASMs is given by $\prod\limits_{i=0}^{n} \frac{(3i)!}{(n+i)!}$ .

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 the total number of ASMs 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. For many years, these conjecture served as a roadmap, stimulating progress in the area. Starting from work of Kuperberg, see here, several groups of researchers resolved by 2006 all these conjectures except one: the formula for the number of $(2n+1)\times(2n+1)$ DASASMs. The Theorem resolves this remaining conjecture.

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

Go to the list of all theorems

The graph isomorphism problem can be solved in quasipolynomial time

You need to know: Graph, finite graph, isomophic graphs, algoruthm, running time of an algorithm, big O notation.

Background: The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

The Theorem: On 11th December 2015, László Babai submitted to arxiv a paper in which he proved the existence of an algorithm for the graph isomorphism problem for n-vertex graphs with running time $2^{O((\log n)^c)}$ for some fixed $c>0$ .

Short context: The graph isomorphism problem is one of the fundamental problems in the theory of algorithms on graphs. The isomorphism problems for many other objects, such as groups, can be reduced to it. It has been intensively studied for decades, and efficient algorithms for many families of graphs are known. However, despite substantial efforts, the $2^{O(\sqrt{n \log n})}$ time algorithm discovered by Babai and Luks in 1983 remained the fastest one working for all n-vertex graphs. The Theorem provides a much faster algorithm. Algorithms with running time $2^{O((\log n)^c)}$ are called quasipolynomial time algorithms.

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

Go to the list of all theorems

The main conjecture in Vinogradov’s Mean Value Theorem is true

You need to know: Just basic arithmetic for the Theorem. You may like to learn what is Vinogradov’s Mean Value Theorem to better understand the context.

Background: For positive integers s,k, and N, let $J_{s,k}(N)$ be the number of integral solutions of the system of equations $x_1^j+\dots+x_s^j = y_1^j+\dots+y_s^j$ , $1 \leq j \leq k$ , such that $1\leq x_i,y_i \leq N$ for $1\leq i \leq s$ .

The Theorem: On 4th December 2015, Jean Bourgain, Ciprian Demeter, and Larry Guth submitted to arxiv and the Annals of Mathematics a paper in which they proved that for any natural numbers $s\geq 1$ and $k\geq 2$ , and any real $\epsilon>0$ , there exist a constant $C=C(s,k,\epsilon)$ such that $J_{s,k}(N) \leq C N^\epsilon(N^s+N^{2s-\frac{1}{2}k(k+1)})$ for all $N\geq 2$ .

Short context: The Theorem confirms a famous conjecture, known as the main conjecture in Vinogradov’s Mean Value Theorem. The estimate is optimal up to constant and $N^\epsilon$ factors. Before 2015, the conjecture was proved if $s \geq k(k + 1)$ , and, more recently, for $k\leq 3$ . The Theorem confirms the conjecture in general.

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

Go to the list of all theorems

Rota’s and Mason’s log-concavity conjectures are true for all matroids

You need to know: Notations: $\emptyset$ for the emply set, $|X|$ for the number of elements in finite set X (also called the cardinality of X), $2^X$ for the set of all subsets of X, $A \setminus B$ for the set $\{x: x\in A \,\text{and}\,x\not\in B\}$ .

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' \subseteq 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$ . The rank of M is $r(M)=\max\limits_{B\in I}|B|$ . Similarly, the rank of any subset $A \subset X$ is $r(A)=\max\limits_{B\in I, \, B\subseteq A}|B|$ . Polynomial $\chi_M(\lambda)=\sum\limits_{A\subseteq X}(-1)^{|A|}\lambda^{r(M)-r(A)}$ is called the characteristic polynomial of matroid M. For $k=0,1,\dots,r(M)$ , let $w_k(M)$ be the absolute value of the coefficient of $\lambda^{r(M)-k}$ in $\chi_M(\lambda)$ . Also, let $f_k(M)$ be the number of sets $A \in I$ with $|A|=k$ . A sequence $a_0, \dots, a_n$ of non-negative real numbers in called log-concave if $a_{k-1}a_{k+1} \leq a_k^2$ for $0<k<n$ .

The Theorem: On 9th November 2015, Karim Adiprasito, June Huh, and Eric Katz submitted to arxiv a paper in which they proved that for any matroid M (i) the sequence $w_0(M), \dots, w_{r(M)}(M)$ is log-concave, and (ii) the sequence $f_0(M), \dots, f_{r(M)}(M)$ is log-concave.

Short context: Part (i) of the Theorem confirms a famous conjecture of Rota made in 1971. This conjecture generalises many important conjectures and theorems. For example, this theorem of Huh about log-concavity of the coefficients of chromatic polynomials of graphs is a very special case of part (i) of the Theorem when M is so-called graphic matroid. Part (ii) of the Theorem confirms a related conjecture of Mason made in 1972.

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

Go to the list of all theorems

Any infinite sequence of +1s and -1s has infinite discrepancy

You need to know: Notation ${\mathbb N}$ for the set of natural numbers, notation $\sup$ for the supremum.

Background: Let $f:{\mathbb N}\to\{-1,+1\}$ be an infinite sequence such that each $f(i)$ is either $+1$ or $-1$ . The discrepancy of f is $\sup\limits_{n,d\in{\mathbb N}}\left|\sum\limits_{j=1}^n f(jd)\right|$ .

The Theorem: On 17th September 2015, Terence Tao submitted to arxiv a paper in which he proved that the discrepancy of any $f:{\mathbb N}\to\{-1,+1\}$ is infinite.

Short context: Around 1932, Erdős conjectured that for any infinite sequence $f:{\mathbb N}\to\{-1,+1\}$ of $+1$ s and $-1$ s and any integer C, there exist positive integers n and d such that $\left|\sum\limits_{j=1}^n f(jd)\right|>C$ . The problem asking to prove or disprove this conjecture became known as the Erdős discrepancy problem. It is one of Erdős’s most famous problems, attracted a lot of attention, but, before 2014, was open even for $C=2$ . In 2014, Konev and Lisitsa solved the $C=2$ case with enormous computer-assisted proof whose output takes up 13 gigabytes of data. The Theorem proves the conjecture for all C.

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

Go to the list of all theorems

For non-square a, x^4-ay^4+ 4axy^2z-2ax^2z^2+a^2z^4 is prime infinitely often

You need to know: Prime numbers.

Background: An integer a is called perfect square if $a=k^2$ for some integer k.

The Theorem: On 17th July 2015, James Maynard submitted to arxiv a paper in which he proved a theorem which implies, in particular, that for any integer $a$ that is not a perfect square, there are infinitely many prime numbers of the form $x^4-ay^4+4axy^2z-2ax^2z^2+a^2z^4$ with integer $x,y,z$ .

Short context: Let P be a polynomial with integer coefficients in one or more variables. If we substitute integer values instead of variables, will we get infinitely many primes as values of P? This problem is wide open even for simple polynomials like $P(x)=x^2+1$ . Friedlander and Iwaniec in 1998 resolves this question affirmatively for polynomial $x^2+y^4$ , Heath-Brown in 2001 – for $x^3+2y^3$ , see here. Instead of considering polynomials one by one, Maynard developed a method for resolving it for many infinite families of polynomials. The Theorem, as stated above, is just one example of application of this method.

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

Go to the list of all theorems

The perfect matching polytope has exponential extension complexity

You need to know: Graph, complete n-vertex graph, notation $|S|$ for the number of elements in finite set S, Euclidean space ${\mathbb R}^m$ , polytope, convex hull.

Background: Let $G=(V,E)$ be a graph with vertex set V and edge set E. A set $M \subseteq E$ of edges of G is called matching if no two edges in M share a common vertex. A matching is called perfect if $|M|=|V|/2$ . Let us enumerate the edges of G from $1$ to $|E|$ . For any subset $S\subset E$ , let $\chi_S \in {\mathbb R}^{|E|}$ be the characteristic vector of S, that is, i-th coordinate of $\chi_S$ is $1$ if the edge number i belongs to S, and $0$ otherwise. The perfect matching polytope $P(G)$ in graph G is the convex hull of all characteristic vectors of perfect matchings in G. An extension complexity of any polytope P is the smallest number of inequalities necessary to describe a higher-dimensional polytope Q that can be linearly projected on P.

The Theorem: On 11th November 2013, Thomas Rothvoss submitted to arxiv a paper in which he proved that for all even n, the extension complexity of the perfect matching polytope in the complete n-vertex graph is at least $2^{cn}$ for some constant c.

Short context: A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. The extension complexity describes the minimal size of linear program needed for this method. The Theorem states that the perfect matching polytope has exponential extension complexity. It resolves a long-standing open question in the field. This is a rare example when we have a proof that some powerful method (in this case linear programming) cannot efficiently solve a problem.

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

Go to the list of all theorems

An explicit construction of a 2^((log log n)^c)-Ramsey graph over n vertices

You need to know: Graph, clique, independent set, small o notation, polynomial time algorithm.

Background: A graph on n vertices is called a k-Ramsey graph if it contains no clique or independent set of size k. By an explicit construction of a k-Ramsey graph we mean a polynomial time algorithm that, given the labels of two vertices in the graph, determines whether there is an edge between them. For n-vertex graph, the input of such algorithm has $2\log n$ bits, hence the running time should be polynomial in $\log n$ .

The Theorem: On 14th June 2015, Gil Cohen submitted to arxiv a paper in which he proved the existence of an absolute constant $c$ such that there is an explicit construction of a $2^{(\log \log n)^c}$ -Ramsey graph over $n$ vertices.

Short context: In 1947 Erdős used the probabilistic method to show that most graphs on $n$ vertices are $(2+o(1))\log n$ -Ramsey. Interestingly, there is no known explicit example of such a graph for large n. Before 2015, the best explicit construction was achieved by Barak, Rao, Shaltiel, and Wigderson, who constructed k-Ramsey $n$ -vertex graphs for $k = 2^{2^{{(\log \log n)}^{1-\epsilon}}}$ , see here. The Theorem provides a significantly better construction. The same result was achieved independently by Chattopadhyay and Zuckerman, who posted their paper online on 23rd July 2015. In a later work (submitted in 2018), Li gave an even better explicit construction achieving $k=(\log n)^{o(\log \log \log n)}$ .

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

Go to the list of all theorems

The Ramsey number of any n-vertex d-degenerate graph is at most c_d n

You need to know: Graph, subgraph, degree of a vertex in a graph, notation $K_n$ for the complete graph on n vertices.

Background: For a graph H, the Ramsey number of H, denoted $r(H)$ , is the minimum integer m such that in every edge two-colouring of $K_m$ there exists a monochromatic copy of H. A graph H is called d-degenerate if all its subgraphs contain a vertex of degree at most d.

The Theorem: On 18th May 2015, Choongbum Lee submitted to arxiv a paper in which he proved that for every positive integer d there is a constant $c=c(d)$ such that every d-degenerate graph H on n vertices satisfies $r(H) \leq cn$ .

Short context: In 1930, Ramsey proved that $r(K_n)$ are finite for all positive integers n. This result originated a large body of research, which is now considered as one of the most important research directions in combinatorics, see here and here for some resent results. In 1973, Burr and Erdős initiated the study of Ramsey numbers of sparse graphs, suggested d-degeneracy as a measure of sparseness, and conjectured that, for any fixed d, the Ramsey numbers of n-vertex d-degenerate graphs is bounded by a linear function of n. This is in striking contrast with the case of complete graphs where $r(K_n)$ grows exponentially in n. 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