There exist 1-dependent 4-colouring and 2-dependent 3-colouring of the integers

You need to know: Notation ${\mathbb Z}$ for the set of integers, basic probability theory, independence, random variable, stochastic process, almost surely.

Background: We say that a stochastic process $(X_i)_{i\in{\mathbb Z}}$ is k-dependent if the random sequences $(\dots, X_{i-2}, X_{i-1})$ and $(X_{i+k}, X_{i+k+1}, \dots)$ are independent of each other, for each $i \in {\mathbb Z}$ . We call a stochastic process $(X_i)_{i\in{\mathbb Z}}$ a q-coloring (of ${\mathbb Z}$ ) if each $X_i$ takes values in $\{1,\dots,q\}$ , and almost surely we have $X_i \neq X_{i+1}$ for all $i\in{\mathbb Z}$ .

The Theorem: On 11th March 2014, Alexander Holroyd and Thomas Liggett submitted to arxiv a paper in which they proved the existence of 1-dependent 4-colouring and of 2-dependent 3-colouring of the integers.

Short context: An important research direction in probability theory is the study of stochastic processes with little or no dependence between random variables at distant locations. k-dependent process indexed by integers is one of the simplest examples of this phenomenon. In 2008, Schramm proved that no stationary 1-dependent 3-colouring of the integers exists, and asked whether a k-dependent q-coloring exists for any positive integers $k$ and $q$ . The Theorem gives a complete 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

If a, b, c, and a+b are non-zero squares, then equation ax^2 + by^2 = c l^2 is partition regular

You need to know: Set ${\mathbb Z}$ of integers, ${\mathbb N}$ of positive integers.

Background: We say that integer n is non-zero perfect square if $n=k^2$ for some integer $k\neq 0$ . We say that equation $p(x, y, \lambda) = 0$ is partition regular if for every partition of ${\mathbb N}$ into finitely many classes, one of the classes contains distinct x, y that satisfy the equation for some $\lambda \in {\mathbb Z}$ . Note that $\lambda$ is a special variable which is allowed to take any integer values.

The Theorem: On 4th March 2014, Nikos Frantzikinakis and Bernard Host submitted to arxiv a paper in which they proved, among other results, the following theorem. Let $p(x, y, z) = ax^2 + by^2 + cz^2 + dxy + exz + fyz$ , where $a, b, c$ are non-zero and $d, e, f$ are arbitrary integers. Suppose that the three integers $e^2-4ac$ , $f^2-4bc$ and $(e+f)^2-4c(a+b+d)$ are all non-zero perfect squares. Then the equation $p(x, y, \lambda)=0$ is partition regular.

Short context: A classical theorem of Furstenberg and Sarközy from 1970-th states that if we partition ${\mathbb N}$ into finitely many classes, we can always find $x,y$ from the same class such that $x-y$ is a (non-zero) perfect square. In other words, equation $x-y=\lambda^2$ is partition regular. In 2006, Khalfalah and Szemerédi proved the same for equation $x+y=\lambda^2$ . The Theorem proves a similar result for a large family of quadratic equations. In particular, it implies that the equation $ax^2 + by^2 = c\lambda^2$ is partition regular whenever integers $a, b, c$ , and $a+b$ are non-zero perfect squares. For example, this holds for the equation $16x^2+9y^2=\lambda^2$ .

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

Go to the list of all theorems

The existence conjecture for combinatorial designs is true

You need to know: Factorial $n!=1\cdot 2 \cdot \dots \cdot n$ with convention that $0!=1$ , notation ${n}\choose{k}$ for $\frac{n!}{k!(n-k)!}$ .

Background: We say that a family S of q-elements subsets of an n-element set X is a (combinatorial) design with parameters $(n, q, r, \lambda)$ if every r-element subset of X belongs to exactly $\lambda$ sets in S. We say that positive integers $(n, q, r, \lambda)$ satisfy the divisibility conditions if $r\leq q \leq n$ and ${{q-i}\choose{r-i}}$ divides $\lambda{{n-i}\choose{r-i}}$ for every $0\leq i \leq r-1$ .

The Theorem: On 15th January 2015, Peter Keevash submitted to arxiv a paper in which he proved that for any fixed positive integers q, r, and $\lambda$ , there exist $n_0=n_0(q, r, \lambda)$ such that if $n \geq n_0$ and $(n, q, r, \lambda)$ satisfy the divisibility conditions then a design with parameters $(n, q, r, \lambda)$ exists.

Short context: The statement of the Theorem was known as the existence conjecture for combinatorial designs and was the central open question in design theory. In 1975, Wilson proved this conjecture for $r=2$ , which already was recognised as a major achievement. The Theorem proves the conjecture in general. The result is new even for $\lambda=1$ , in which case combinatorial design is called Steiner system. Steiner systems are studied since work of Plücker (1835), Kirkman (1846) and Steiner (1853), but, before the Theorem was proved, there was not even known if any single Steiner system with $r>5$ exists. See here for a related resent result.

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

Go to the list of all theorems

Every odd integer greater than 5 is the sum of three primes

You need to know: Even and odd integers, prime numbers.

Background: An integer n is the sum of three primes, if there exist prime numbers $p_1, p_2, p_3$ such that $n=p_1+p_2+p_3$ .

The Theorem: On 30th December 2013, Harald Helfgott submitted to arxiv a paper in which he proved that every odd integer $n>5$ is the sum of three primes.

Short context: In 1742, Goldbach conjectured that every integer $n>5$ is the sum of three primes. Goldbach’s conjecture became one of the best-known unsolved problems in number theory and all of mathematics. In 1937, Vinogradov proved the conjecture for all odd integers greater than some (large) constant $n_0$ . In 1956, Borozdkin proved that one can take $n_0=e^{e^{16038}}$ . In 2002, Ming-Chit improved this to $n_0=e^{3100}$ . The Theorem proves the conjecture for all odd integers. The case of even integers remains open.

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

Go to the list of all theorems

Every point in an nd-polytope is the barycenter of n points in its d-faces

You need to know: Euclidean space ${\mathbb R}^m$ , barycenter $\frac{1}{n}\sum\limits_{i=1}^n p_i$ of n points $p_1, \dots, p_n$ in ${\mathbb R}^m$ , k-polytope (k-dimensional polytope) in ${\mathbb R}^m$ , face of a polytope, dimension of a face.

Background: The d-dimensional skeleton of a k-polytope P is the set of all faces of the polytope of dimension at most d.

The Theorem: On 16th December 2013, Michael Dobbins submitted to arxiv a paper in which he proved that for any nd-polytope P and for any point $p\in P$ , there are points $p_1, \dots, p_n$ in the d-dimensional skeleton S of P with barycenter $p$ .

Short context: The Theorem verifies a conjecture made by Tokuyama. In author’s words, the conjecture was originally motivated by the engineering problem of determining how counterweights can be attached to some 3-dimensional object to adjust its center of mass to reduce vibrations when the object moves.

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

Go to the list of all theorems

For any k, there exist infinitely many bounded intervals containing k primes

You need to know: Prime numbers.

Background: Let $p_n$ denotes the n-th prime number.

The Theorem: On 19th November 2013, James Maynard submitted to arxiv a paper in which he proved that for any positive integer k, there exists a constant $C_k<\infty$ , such that $p_{n+k}-p_n \leq C_k$ for infinitely many values of n. In particular, one can take $C_1=600$ .

Short context: In April 2013, Zhang made a breakthrough by proving the $k=1$ case of the Theorem with constant $C_1=7\cdot 10^7$ . After this, a large group of mathematicians, working online, tried to prove Zhang’s theorem with as small $C_1$ as possible, and, by October 2013, achieved together $C_1=4422$ . On 23rd October, Maynard announced that he, working alone, achieved $C_1=700$ . By the time he submitted the paper to arxiv in November, he improved this to $C_1=600$ . In a later work, group of mathematicians achieved $C_1=246$ . Even more importantly, Maynard’s Theorem works for all k.

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

Go to the list of all theorems

No algorithm can decide if a finitely presented group has a proper finite-index subgroup

You need to know: Group, subgroup, proper subgroup, presentation of a group in the form $<S|R>$ , where S is a set of generators and R is a set of relations.

Background: Let G be a group and H be a subgroup. A (left) coset of H in G with respect to $g\in G$ is the set $\{gh: \, h\in H\}$ . We say that subgroup H is of a finite index is there are only finitely many different cosets of H in G. A group G is called finitely presented if it has a presentation $<S|R>$ with finite number of generators and finite set of relations.

The Theorem: On 1st November 2013, Martin Bridson and Henry Wilton submitted to Inventiones Mathematicae a paper in which they proved that there is no algorithm that can determine whether or not a finitely presented group has a proper subgroup of finite index.

Short context: A word in group G is any product of generators and their inverse elements. The word problem in G is the problem to decide whether a given word represents an identity element. In 1955, Novikov proved that there is no algorithm that can solve the word problem in all finitely presented groups. The problems that no algorithm can solve are called undecidable. After Novikov’s result, many other basic problems for finitely presented groups have been proved to be undecidable. However, the status of the problem to decide if such a group has a proper subgroup of finite index remained open. The Theorem proves that this problem is undecidable as well.

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

Go to the list of all theorems

Replica prediction holds for the limiting independence ratio in random regular graphs

You need to know: Graph, independent set in a graph, maximum independent set, d-regular graph, probability, selection uniformly at random, convergence in probability.

Background: The independence ratio $\text{IR}(G)$ of n-vertex graph G is the size of its maximum independent set divided by n. For positive integers $n,d$ with $nd$ even, let $G_{n,d}$ denote the uniformly random d-regular graph on n vertices, sampled as follows: start with n isolated vertices each equipped with d labelled half-edges, and form the graph by taking a uniformly random matching on the $nd$ half-edges. For fixed d, let $\text{IR}_n=\text{IR}(G_{n,d})$ .

For positive integer d, consider functions $\lambda_d(q)=q\frac{1-(1-q)^{d-1}}{(1-q)^d}$ , $\alpha_d(q)=q\frac{1-q+dq/(2\lambda_d(q))}{1-q^2(1-1/\lambda_d(q))}$ , and $f_d(q)=-\log\left[1-q\left(1-\frac{1}{\lambda_d(q)}\right)\right]-\left(\frac{d}{2}-1\right)\log\left[1-q^2\left(1-\frac{1}{\lambda_d(q)}\right)\right]-\alpha_d(d)\log \lambda_d(q)$ . Let $q^*(d)$ be the largest $q \leq 2(\log d)/d$ such that $f_d(q)=0$ , and let $\alpha^*(d)=\alpha_d(q^*(d))$ .

The Theorem: On 17th October 2013, Jian Ding, Allan Sly, and Nike Sun submitted to arxiv a paper in which they proved the existence of constant $d_0$ such that for all $d\geq d_0$ the independence ratio $\text{IR}_n$ of the random d-regular graph $G_{n,d}$ converges in probability to $\alpha^*(d)$ .

Short context: Determining the size of maximum independent set in random d-regular graph is not only a problem interesting in its own, but also has connection to statistical physics. In fact, the Theorem, including explicit formula for $\alpha^*(d)$ , has been derived in 2005 using non-rigorous analysis with physical origin (called replica symmetry breaking heuristics). The Theorem confirms this prediction rigorously.

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

Go to the list of all theorems

Integer superharmonic matrices have the Apollonian structure

You need to know: Matrix, matrix multiplication, transpose $A^T$ of matrix A, notation ${\mathbb Z}^2$ for the set of $2\times 1$ matrices $x=\begin{bmatrix}x_1\\x_2\end{bmatrix}$ with integer entries, norm $||x||=\sqrt{x_1^2+x_2^2}$ of $x\in{\mathbb Z}^2$ , real matrix (matrix with real entries), square matrix, symmetric matrix, trace of a square matrix (sum of its diagonal entries), positive semidefinite matrix, Euclidean plane ${\mathbb R}^2$ , lines and circles in the plane, tangent circles, notation $x=x_0$ for vertical line through the point $(x_0, 0)$ , notation $C((x,y),r)$ for the circle with centre $(x,y)\in{\mathbb R}^2$ and radius r, small o notation.

Background: For $x,y\in{\mathbb Z}^2$ we write $x\sim y$ if $||x-y||=1$ . For a function $g:{\mathbb Z}^2\to {\mathbb Z}$ , let $\Delta g(x) = \sum\limits_{y\sim x}(g(y)-g(x))$ . A $2\times 2$ matrix A is called integer superharmonic if there exists a function $g:{\mathbb Z}^2\to {\mathbb Z}$ such that $g(x) = \frac{1}{2}x^TAx+o(||x||^2)$ and $\Delta g(x) \leq 1$ for all $x\in {\mathbb Z}^2$ . Let $S_2$ be the set of all $2\times 2$ real symmetric matrices.

By general circle on the plane we mean circle or line. Every triple T of pairwise tangent general circles has exactly two general circles (called Soddy general circles) tangent to all three. An Apollonian circle packing (ACP) generated by T is a minimal collection of general circles containing T that is closed under the addition of Soddy general circles. For $k\in{\mathbb Z}$ , let ${\cal B}_k$ be the ACP generated by lines $x=2k$ , $x=2k+2$ and circle $C((2k+1,0),1)$ . Let ${\cal B}=\bigcup\limits_{k\in{\mathbb Z}}{\cal B}_k$ . To each circle $C((x,y),r) \in {\cal B}$ we associate the matrix $A_C =\frac{1}{2}\begin{bmatrix}r+x & y \\y & r-x\end{bmatrix}$ .

The Theorem: On 12th September 2013, Lionel Levine, Wesley Pegden, and Charles Smart submitted to arxiv a paper in which they proved that matrix $A\in S_2$ is integer superharmonic if and only if either $\text{trace}(A)\leq 2$ or there exists a circle $C\in{\cal B}$ such that matrix $A_C-A$ is positive semidefinite.

Short context: Integer superharmonic matrices arise from the theory of partial differential equations (PDE), and it was on open question to characterise them. The Theorem achieves this via connection to Apollonian circle packing, which, for non-specialist, looks like a totally unrelated area of mathematics. Such theorems are useful because they allow to apply methods and results from one area to a different one.

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

Go to the list of all theorems

The least modulus of a distinct covering system is at most 10^16

You need to know: Notation $n\equiv m (\text{mod\,} s)$ if $n-m$ is a multiple of s.

Background: A finite set S of distinct positive integers $0<s_1<s_2<\dots<s_k$ is called a distinct covering system (or just “covering system” for short) if there exist integers $m_1, m_2, \dots, m_k$ such that each integer n satisfies at least one of the congruences $n\equiv m_i (\text{mod\,} s_i), \, i=1,2,\dots,k$ .

The Theorem: On 2nd July 2013, Bob Hough submitted to arxiv a paper in which he proved that in every distinct covering system $0<s_1<s_2<\dots<s_k$ we have $s_1 \leq 10^{16}$ .

Short context: A famous problem of Erdős from 1950, known as the minimum modulus problem for covering systems, asks whether for every N there is a distinct covering system S with all $s_i$ greater than N. Despite some partial results, the problem remained open for over 60 years. In 2009, Nielsen constructed a distinct covering system with $s_1=40$ , but conjectured that this cannot be done for arbitrary large N, and the answer to the minimum modulus problem is negative. 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