K_d,d maximises the normalised number of q-colourings over all d-regular graphs

You need to know: Graph, proper colouring of vertices of a graph, bipartite graph, complete bipartite graph, degree of a vertex in a graph, d-regular graph (graph in which all vertices have the same degree d).

Background: Let $c_q(G)$ be the number of proper colourings of graph G. Also, let $|V(G)|$ denote the number of vertices of G. Finally, let $K_{d,d}$ denote the complete bipartite graph on $2d$ vertices.

The Theorem: On 25th September 2018, Ashwin Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao submitted to arxiv a paper in which they proved that for every d-regular graph G and every positive integer q, one has $c_q(G)^{1/|V(G)|}\leq c_q(K_{d,d})^{1/2d}$ .

Short context: Given graph G, quantity $c_q(G)^{1/|V(G)|}$ is called the normalised number of q-colourings of G. This normalisation is a natural choice, because replacing G by a disjoint union of copies of itself does not change the quantity $c_q(G)^{1/|V(G)|}$ . In 2004, Galvin and Tetali initiated the study of the following question: given positive integers d and q, what d-regular graph G maximises $c_q(G)^{1/|V(G)|}$ ? The Theorem proves that the answer is $K_{d,d}$ .

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

Go to the list of all theorems

Non-collision singularities exist in a planar Newtonian 4-body problem

You need to know: Euclidean plane ${\mathbb R}^2$ , (second) derivative of a function $x:{\mathbb R}\to {\mathbb R}^2$ .

Background: Let n point particles with masses $m_i > 0$ and positions $x_i \in {\mathbb R}^2$ are moving according to Newton’s laws of motion: $m_j \frac{d^2 x_j}{dt^2} = \sum\limits_{i \neq j} \frac{m_i m_j(x_i - x j)}{r_{ij}^3}, \, 1 \leq j \leq n$ , where $r_{ij}$ is the distance between $x_i$ and $x_j$ . The motion of particles is determined by the initial conditions: their masses and their positions and velocities at time $t=0$ .

The Theorem: On 29th August 2014, Jinxin Xue submitted to Acta Mathematica a paper in which he proved that, for $n=4$ , there is a non-empty set of initial conditions, such that all four points escape to infinity in a finite time, avoiding collisions.

Short context: The problem of describing motion of n bodies under gravitation (n-body problem) in space or plane is a fundamental problem in physics and mathematics, studied by many authors, see, for example, here. In general, the motion can be very complicated even for $n=3$ , but can we at least understand under what initial conditions the solution to the system of Newton equations (presented above) is well-defined for all $t\geq 0$ ? This may be not the case for two reasons: (a) collision happened, and (b) there are no collisions but a point escape to infinity in a finite time. Case (b) is known as non-collision singularity. In 1897, Painlevé proved that there are no such singularities for $n=3$ , but conjectured their existence for all $n>3$ . In 1992, Xia proved this conjecture (for motions in ${\mathbb R}^3$ ) for $n\geq 5$ . The Theorem establishes the remaining (and the hardest) case $n=4$ .

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

Go to the list of all theorems

Characterisation of polyhedral types inscribed in the hyperboloid or cylinder

You need to know: Euclidean space ${\mathbb R}^3$ , convex polyhedron in ${\mathbb R}^3$ , vertices of a polyhedron, graph, planar graph, closed path in a graph, 3-connected graph.

Background: Let $S \subset {\mathbb R}^3$ be either unit sphere (that is, set of all points $x=(x_1,x_2,x_3)\in {\mathbb R}^3$ such that $x_1^2+x_2^2+x_3^2=1$ ), or hyperboloid (defined by equation $x_1^2+x_2^2-x_3^2=1$ ), or cylinder (defined by $x_1^2+x_2^2=1$ with $x_3$ free). We say that a convex polyhedron P is inscribed in S if $P \cap S$ is exactly the set of vertices of P. A 1-skeleton of a convex polyhedron P is the set of vertices and edges of P, considered as a graph. A Hamiltonian cycle in a graph is a closed path visiting each vertex exactly once.

The Theorem: On 13th October 2014, Jeffrey Danciger, Sara Maloni, and Jean-Marc Schlenker submitted to arxiv a paper in which they proved that, for a planar graph G, the following conditions are equivalent: (i) G is the 1-skeleton of some convex polyhedron inscribed in the cylinder; (ii) G is the 1-skeleton of some convex polyhedron inscribed in the hyperboloid; and (iii) G is the 1-skeleton of some convex polyhedron inscribed in the sphere and G admits a Hamiltonian cycle.

Short context: In 1832, Steiner asked which graphs are 1-skeletons of (a) an arbitrary convex polyhedron in ${\mathbb R}^3$ , (b) a convex polyhedron inscribed in the sphere, (c) inscribed in the cylinder, and (d) inscribed in the hyperboloid. Question (a) was answered by a famous Theorem of Steinitz, which states that a graph G is the 1-skeleton of a convex polyhedron in ${\mathbb R}^3$ if and only if G is planar and 3-connected. In 1992, Hodgson et al. gave a full characterisation of possible 1-skeletons of convex polyhedra inscribed in the sphere, thus answering question (b). The Theorem solves the remaining parts (c) and (d) of the Steiner’s question by reducing them to the already solved part (b).

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

Go to the list of all theorems

The Julia set of the Feigenbaum polynomial has zero Lebesgue measure

You need to know: Basic complex analysis, set ${\mathbb C}$ of complex numbers, absolute value $|z|$ of complex number z, boundary of a set, area (that is, Lebesgue measure) of a set $A \subset {\mathbb C}$ , notation $f^n$ for the n-th iterate of function $f:{\mathbb C}\to {\mathbb C}$ .

Background: For polynomial $f:{\mathbb C} \to {\mathbb C}$ , let $K_f \subset {\mathbb C}$ be the set of points $z_0\in {\mathbb C}$ such that the sequence $z_0, z_1=f(z_0), \dots, z_{n}=f(z_{n-1})=f^n(z_0), \dots$ is bounded, that is, $|z_n|\leq B, \, \forall n$ for some $B \in {\mathbb R}$ . The boundary $J_f$ of $K_f$ is called the Julia set of f.

We say that point $z_0\in {\mathbb C}$ is periodic if $f^n(z_0)=f(z_0)$ for some positive integer n, and the smallest n such that this holds is called the period of $z_0$ . For each n, let $r_n$ be the (unique) real number such that $0$ is a periodic point with period $2^n$ of polynomial $f(z)=z^2+r_n$ . It is known that the limit $r_\infty=\lim\limits_{n\to\infty} r_n$ exists and numerically equal to $-1.401155...$ . The polynomial $f(z)=z^2+r_\infty$ is called the Feigenbaum polynomial.

The Theorem: On 22nd December 2017, Artem Dudko and Scott Sutherland submitted to arxiv a paper in which they proved that the Julia set of the Feigenbaum polynomial has zero Lebesgue measure.

Short context: Julia set is a fundamental concept in the theory of complex dynamics, because it consists of values $z_0$ such that an arbitrarily small perturbation can cause significant changes in the sequence of iterated function values. The Julia set is known to have zero area for almost all but not all quadratic polynomials. The Feigenbaum polynomial is important in so-called renormalization theory in dynamics, and the question whether its Julia set has zero area was a long-standing open question. The Theorem resolves it affirmatively.

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

Go to the list of all theorems

The Schinzel-Zassenhaus conjecture on integer polynomials is true

You need to know: Polynomials, degree of a polynomial, constant polynomial (the one of degree $0$ ), leading coefficient of a polynomial (the nonzero coefficient of highest degree), monic polynomial (polynomial with leading coefficient $1$ ), roots of a polynomial, set ${\mathbb C}$ of complex numbers, absolute value $|z|$ of complex numbers $z\in{\mathbb C}$ .

Background: Let ${\mathbb Z}[x]$ be the set of polynomials in one variable x with integer coefficients. Polynomial $Q(x) \in {\mathbb Z}[x]$ is called a divisor of $P(x) \in {\mathbb Z}[x]$ if $P(x)=Q(x)R(x)$ for some $R(x)\in {\mathbb Z}[x]$ . If $P(x) \in {\mathbb Z}[x]$ cannot be written as $P(x)=Q(x)R(x)$ for non-constant $Q(x),R(x) \in {\mathbb Z}[x]$ , we say that $P(x)$ is irreducible. An irreducible polynomial $P \in {\mathbb Z}[x]$ is called cyclotomic if $P$ is a divisor of $x^n-1$ for some integer $n \geq 1$ .

The Theorem: On 28th December 2019, Vesselin Dimitrov submitted to arxiv a paper in which he proved that every non-cyclotomic monic irreducible polynomial $P(x) \in {\mathbb Z}[x]$ of degree $n>1$ has at least one root $\alpha\in{\mathbb C}$ satisfying $|\alpha|\geq 2^{1/4n}$ .

Short context: It is easy to see that all roots of cyclotomic polynomials have absolute value 1. In 1965, Schinzel and Zassenhaus conjectured that any other monic irreducible polynomial of degree n must have a root $\alpha$ satisfying $|\alpha|\geq 1+\frac{c}{n}$ , where $c>0$ is a universal constant. The conjecture attracted a lot of attension, but, before 2019, was proved only in special cases, e.g. for polynomials with odd coefficients, as a corollary of this Theorem. Because $2^{1/4n} \geq 1+\frac{\log 2}{4n}$ , the Theorem confirms this conjecture in full generality, with $c=\frac{\log 2}{4}$ .

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

Go to the list of all theorems

MIP*=RE

You need to know: Computer program and number of operations it takes to run, quantum computer, entangled qubits, probability.

Background: Let $\Sigma=\{0,1\}$ , ${\Sigma}^n$ be the set of words $\sigma_1\dots\sigma_n$ with each $\sigma_i$ being $0$ or $1$ , and let $\Sigma^*=\bigcup\limits_{n=0}^\infty \Sigma^n$ . Let $|x|$ denote the length of any word $x\in \Sigma^*$ . A language is any set of words $L\subset\Sigma^*$ . A language L is called recursively enumerable if there is a computer program such that its output is a full list $x_1, x_2, \dots$ of the words in L (in any order). Note that if L is infinite, such a program will run forever. The set of all recursively enumerable languages is denoted RE.

Imagine two quantum computers, which we call provers, that are all-powerful, that is, can do ANY (even infinite!) number of operations in, say, one second. The provers can share any number of entangled qubits, but any other communication between them is prohibited. Also, we have a standard (not quantum and not all-powerfull) computer, called verifier, which can do everything a regular computer can do, but, in addition, can ask any questions to the provers. Let MIP* be the set of all languages L, for which there exists a polynomial P and a computer program on such computer, which, for any input $x\in \Sigma^*$ , and with probability greater than (say) $\frac{3}{4}$ : (i) performs at most $P(|x|)$ operations, then stops and output Yes or No, (ii) outputs Yes if $x\in L$ and the provers give correct answers, and (iii) outputs No if $x\not\in L$ even if the provers are trying to cheat.

The Theorem: On 29th September 2020, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen submitted to arxiv a paper in which they proved that MIP*=RE.

Short context: A language L is called decidable if there is a program which, for any input $x\in \Sigma^*$ , runs a finite time and then correctly outputs whether $x\in L$ or not. The set RE contains languages which are not decidable. The Theorem, however, states that any language L in RE, even undecidable, belongs to MIP*. This means that, by interaction with two all-powerful quantum provers which share entangled qubits, we can check whether $x\in L$ after performing at most $P(|x|)$ operations. The Theorem has important consequences in pure mathematics. In particular, it implies that the Connes’ embedding conjecture, a central conjecture in the theory of von Neumann algebras, is false.

Links: The free version of the original paper is available here.

A comment: In fact, the first proof of the Theorem appeared 13th January 2020, but it used a published result whose proof turned out to be incorrect.

Go to the list of all theorems

Almost all orbits of the Collatz map attain almost bounded value

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

Background: The Collatz map $\text{Col}: {\mathbb N}\to {\mathbb N}$ is defined by (i) $\text{Col}(n)=3n+1$ when $n$ is odd and (ii) $\text{Col}(n) = n/2$ when n is even. For any $n\in{\mathbb N}$ , let $\text{Col}^k(n)$ denote the k-th iterate of $\text{Col},$ let $\text{Col}^{\mathbb N}(n)=\{n, \text{Col}(n), \text{Col}^2(n), \dots\}$ be the Collatz orbit, and let $\text{Col}_{\text{min}}(n) = \inf\limits_{k \in {\mathbb N}} \text{Col}^k(n)$ denote the minimal element of the Collatz orbit $\text{Col}^{\mathbb N}(n)$ .

We say that subset $A\subseteq {\mathbb N}$ has logarithmic density 1, if $\lim\limits_{x\to \infty}\left(\frac{1}{\log x}\sum\limits_{k\in A, k\leq x}\frac{1}{k}\right)=1$ . We say that a property P holds for almost all $n \in {\mathbb N}$ (in the sense of logarithmic density) if the subset of ${\mathbb N}$ for which P holds has logarithmic density 1.

The Theorem: On 8th September 2019, Terence Tao submitted to arxiv a paper in which he proved that for any function $f: {\mathbb N} \to {\mathbb N}$ such that $\lim\limits_{n\to \infty} f(n)=+\infty$ , one has $\text{Col}_{\text{min}}(n) < f(n)$ for almost all $n \in {\mathbb N}$ (in the sense of logarithmic density).

Short context: The famous Collatz conjecture predicts that $\text{Col}_{\text{min}}(n)=1$ for all $n\in{\mathbb N}$ , but it remains well beyond reach of the current methods. As a partial progress, Terras proved in 1976 that $\text{Col}_{\text{min}}(n)<n$ for almost all n. In 1979, Allouche improved this to $\text{Col}_{\text{min}}(n)<n^\theta$ for almost all n, for any fixed constant $\theta>0.869$ . In 1994, Korec proved the same result for any $\theta>\frac{\log 3}{\log 4}=0.792...$ . The Theorem implies that one can take any $\theta>0$ , and, more generally, $\text{Col}_{\text{min}}(n)<f(n)$ for almost all n and any function f going to infinity with n. For example, one can take $f(n)=\log\log\log\log n$ .

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

Go to the list of all theorems

The Duffin–Schaeffer conjecture is true

You need to know: Set ${\mathbb N}$ of natural numbers, set ${\mathbb R}^+$ of positive real numbers, co-prime integers, monotonic function, infimum, Lebesgue measure, infinite sum.

Background: For a function $g:{\mathbb N}\to {\mathbb R}^+$ , let $S(g)$ be the set of all real numbers $x \in [0,1]$ such that the inequality $\left|x-\frac{a}{b}\right| < \frac{g(b)}{b}$ has infinitely many co-prime solutions $a,b$ . Also, let $\phi(n)$ denote the number of positive integers which are less than n and co-prime with it.

The Theorem: On 10th July 2019, Dimitris Koukoulopoulos and James Maynard submitted to arxiv a paper in which they proved that set $S(g) \subset [0,1]$ has Lebesgue measure 1 if and only if $\sum\limits_{n=1}^{\infty} g(n)\frac{\phi(n)}{n}=\infty$ .

Short context: The Theorem confirms a conjecture of Duffin and Schaeffer made in 1941, which was the fundamental conjecture in the theory of rational approximation. It has many important consequences. For example, this earlier theorem states that it implies an even more general conjecture of Beresnevich and Velani.

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

Go to the list of all theorems

The Sensitivity Conjecture is true

You need to know: For the Theorem: Graph, induced subgraph, degree of a vertex of a graph, notation $\Delta(H)$ for the maximum degree of graph H. In addition, you may want to go the original paper (or online) and learn what is the Sensitivity Conjecture to fully appreciate the context.

Background: The n-dimensional hypercube graph is the graph $Q^n$ , whose vertex set consists of vectors $(x_1, x_2, \dots, x_n)$ such that each $x_i$ is either $0$ or $1$ , and two vectors are adjacent if they differ in exactly one coordinate.

The Theorem: On 1st July 2019, Hao Huang submitted to arxiv a paper in which he proved that for every integer $n\geq 1$ , and every $(2^{n-1}+1)$ -vertex induced subgraph H of $Q^n$ , one has $\Delta(H) \geq \sqrt{n}$ .

Short context: The inequality $\Delta(H) \geq \sqrt{n}$ in the Theorem is the best possible, in sense that it is tight when n is a perfect square. The Theorem confirms a conjecture of Gotsman and Linial made in 1992, who proved that their conjecture, if true, would imply the celebrated Sensitivity Conjecture, one of the famous conjectures in theoretical computer science. The Theorem confirms the Gotsman-Linial conjecture and hence the Sensitivity Conjecture.

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

Go to the list of all theorems

The Hedetniemi’s conjecture is false

You need to know: Graph, finite simple graph, vertex set $V(G)$ and edge set $E(G)$ of graph G, notation $S \times T$ for the set of pairs $(s,t)$ where $s \in S$ and $t\in T$ , chromatic number $\chi(G)$ of graph G.

Background: The tensor product $G\times H$ of finite simple graphs G and H is the graph with vertex set $V (G) \times V (H)$ , such that pairs $(g,h)$ and $(g',h')$ are adjacent if and only if $\{g,g'\}\in E(G)$ and $\{h,h'\}\in E(H)$ .

The Theorem: On 6th May 2019, Yaroslav Shitov submitted to arxiv a paper in which he proved the existence of finite simple graphs G and H such that $\chi(G \times H) < \min\{\chi(G), \chi(H)\}$ .

Short context: It is easy to see that $\chi(G \times H) \leq \min\{\chi(G), \chi(H)\}$ for all graphs G,H. The classical conjecture of Hedetniemi, made in 1966, predicted that the equality holds for all G and H. The conjecture attracted a lot of attention, and has been proved in a number of special cases. The Theorem, however, states that in general this conjecture is false.

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

Go to the list of all theorems