n-digit integers can be multiplied in O(n log n) operations

You need to know: Integer multiplication, algorithm, running time of an algorithm, logarithm, big O notation.

Background (needed only for the context section): The iterated logarithm $\log^*$ is the unique function which has properties (i) $\log^*n =0$ if $n\leq 1$ and (ii) $\log^*n = 1+\log^*(\log n)$ if $n>1$ .

The Theorem: On 18th March 2019, David Harvey and Joris van der Hoeven posted online a paper in which they presented a new algorithm for multiplying integers, which, according to their analysis, has running time $O(n\log n)$ for n-digit integers.

Short context: Integer multiplication is one of the basic operations in mathematics. Usual school method requires $O(n^2)$ operations for n-digit integers. In 1971, Schönhage and Strassen presented a much faster $O(n \log n \log\log n)$ algorithm, and conjectured that $O(n \log n)$ algorithm should exist, and that this is optimal. In 2009, Fürer presented a faster algorithm with running time $n\log n 2^{O(\log^*(n))}$ for n-digit integers, see here. The Theorem improves the running time to $O(n \log n)$ , which is conjectured to be optimal.

Links: The preprint is available here.

Go to the list of all theorems

All but finitely many of the fixed degree Jensen polynomials for the Riemann zeta function are hyperbolic

You need to know: Set ${\mathbb C}$ of complex numbers, real part $\text{Re}(z)$ of complex number z, function of complex variable, infinite series, integration, meromorphic function, analytic continuation, notation ${{d}\choose{j}}=\frac{d!}{j!(n-j)!}$ .

Background: For $z \in{\mathbb C}$ with $\text{Re}(z)>1$ , let $\zeta(z)=\sum\limits_{n=1}^\infty n^{-z}$ . By analytic continuation, function $\zeta(z)$ can be extended to a meromorphic function on the whole ${\mathbb C}$ , and it is called the Riemann zeta function. Similarly, let $\Gamma(z)$ be the analytic continuation of integral $\Gamma(z)=\int\limits_0^\infty x^{z-1}e^{-x}dx$ , defined for $\text{Re}(z)>0$ . Let $\Lambda(z)=\pi^{-z/2}\Gamma(z/2)\zeta(z)$ , and let sequence $\{\gamma(n)\}_{n=0}^\infty$ be defined by $(-1+4z^2)\Lambda\left(\frac{1}{2}+z\right)=\sum\limits_{n=0}^\infty\frac{\gamma(n)}{n!}z^{2n}$ . The Jensen polynomial for the Riemann zeta function of degree d and shift n is the polynomial $J_{\gamma}^{d,n}(x)=\sum\limits_{j=0}^n {{d}\choose{j}}\gamma(n+j)x^j$ . We say that a polynomial with real coefficients is hyperbolic if all of its zeros are real.

The Theorem: On 12th February 2019, Michael Griffin, Ken Ono, Larry Rolen, and Don Zagier submitted to the Proceedings of the National Academy of Sciences a paper in which they proved that for any $d\geq 1$ there is a constant $N=N(d)$ , such that the polynomial $J_{\gamma}^{d,n}(x)$ is hyperbolic for all $n\geq N$ .

Short context: The Riemann hypothesis (RH) states that if $\zeta(z)=0$ then either $z=-2k$ for some integer $k>0$ or $\text{Re}(z)=\frac{1}{2}$ . It is one of the most important open problems in the whole mathematics, and has many equivalent formulations. One of the equivalent formulations of RH, established by Pólya in 1927, states that polynomials $J_{\gamma}^{d,n}(x)$ are hyperbolic for all integers $d\geq 0$ and $n\geq 0$ . Before 2019, this statement was known to hold only for $d\leq 3$ . The Theorem proves the hyperbolicity of $J_{\gamma}^{d,n}(x)$ for all d, assuming that n is sufficiently large (depending on d). As a corollary, the authors also proved this for all n if $d\leq 8$ .

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

Go to the list of all theorems

Random Bernoulli n by n matrix is singular with probability (1/2+o(1))^n

You need to know: Matrix, determinant $\text{det}(M)$ of square matrix M, singular square matrix (matrix with determinant $0$ ), basic probability theory, independent and identically distributed (i.i.d.) random variables, $o(1)$ notation.

Background: Let $M_n$ be a random $n \times n$ matrix whose entries are i.i.d. Bernoulli random variables (each entry is equal to $+1$ or $-1$ with probabilities $1/2$ ). Let $P_n = P(\text{det}(M_n) = 0)$ be the probability that $M_n$ is singular.

The Theorem: On 21st December 2018, Konstantin Tikhomirov submitted to arxiv a paper in which he proved that $P_n = \left(\frac{1}{2}+o(1)\right)^n$ as $n\to\infty$ .

Short context: The question of estimating $P_n$ has attracted considerable attention in literature. There is an obvious lower bound $P_n \geq \left(\frac{1}{2}+o(1)\right)^n$ , and it has been conjectured by many authors that equality holds. For an upper bound, Komlós proved in 1967 that $\lim\limits_{n\to\infty} P_n = 0$ . In 1995, Kahn, Komlós, and Szemerédi proved that $P_n=O(0.999^n)$ . This was later improved by Tao and Vu to $P_n=O(0.958^n)$ and then to $P_n \leq \left(\frac{3}{4}+o(1)\right)^n$ , see here. In 2010, Bourgain, Vu and Wood improved it to $P_n \leq \left(\frac{1}{\sqrt{2}}+o(1)\right)^n$ . Finally, the Theorem establishes the upper bound $P_n \leq \left(\frac{1}{2}+o(1)\right)^n$ , which matches the lower bound up to $o(1)$ term and proves the conjecture.

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

Go to the list of all theorems

The h*-bound for the minimum number of triangles in n-vertex e-edge graph is tight if n>n0(a), e<n(n-1)/2-an^2

You need to know: Set ${\mathbb N}$ of positive integers, graph, clique in a graph, triangle (3-vertex clique).

Background: Let $n>0$ and $0<e\leq \frac{n(n-1)}{2}$ be integers. Let $g_3(n,e)$ be the minimum number of triangles a graph with n verities and e edges can have. We have an upper bound $g_3(n,e)\leq h^*(n,e)$ , called “the h*-bound”, where $h^*(n,e)$ is the explicit function.

The definition of $h^*(n,e)$ (which you may skip) is: for any integer $r>0$ , we can write $n=d_rr+b_r$ for integers $d_r$ and $0\leq b_r<r$ . Define $t_r(n)=\frac{n(n-1)}{2}-b_r\frac{d_r(d_r+1)}{2}-(r-b_r)\frac{d_r(d_r-1)}{2}$ . Let $k=k(n,e)$ be the unique positive integer with $t_{k-1}(n)<e\leq t_k(n)$ . Let $a^*=a^*(n,e)$ be the unique integer vector $a^*=(a_1^*,\dots, a_k^*)$ such that (i) $a_k^*=\min\{a\in{\mathbb N}:a(n-a)+t_{k-1}(n-a)\leq e\}$ and (ii) $a_1^*+\dots+a_{k-1}^*=n-a_k^*$ and $a_1^*\geq \dots \geq a_{k-1}^* \geq a_1^*-1$ . Then let $m^*=\sum\limits_{1\leq i < j \leq k}a_i^*a_j^*-e$ , and finally $h^*(n,e)=\sum\limits_{1\leq h<i < j \leq k}a_h^*a_i^*a_j^*-m^*\sum\limits_{i=1}^{k-2}a_i^*$ .

The Theorem: On 2nd December 2017, Hong Liu, Oleg Pikhurko, and Katherine Staden submitted to arxiv and the Forum of Mathematics, Pi a paper in which they proved that for any $\epsilon>0$ , there exists $n_0=n_0(\epsilon)>0$ such that for all positive
integers $n \geq n_0$ and $e\leq \frac{n(n-1)}{2}-\epsilon n^2$ , we have that $g_3(n,e)=h^*(n,e)$ .

Short context: Famous Turán’s theorem, proved in 1941, states that for any integer $r\geq 3$ , every graph on n vertices with more than $t_r(n)$ edges contains a clique of size r. A natural question arises to estimate the minimum number $g_r(n,e)$ of r-cliques a graph with n vertices and e edges must contain. In 2016, Reiher proved a lower bound on $g_r(n,e)$ , which, together with the known upper bound, allows to estimate $g_r(n,e)$ asymptotically in the limit. The Theorem establishes the exact value of $g_r(n,e)$ in the case $r=3$ , n large, and $e\leq {{n}\choose{2}}-\epsilon n^2$ .

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

Go to the list of all theorems

A universally measurable homomorphism between Polish groups is automatically continuous

You need to know: Groups and homomopshisms between them, topological spaces and homeomopshisms between them, continuous function on a topological space, probability measure on a topological space, metric space, complete metric space, dense subset of a metric space.

Background: A topological group G is a topological space that is also a group such that the group operations of product $G\times G \to G: (x,y) \to xy$ and taking inverses $G \to G: x \to x^{-1}$ are continuous. A topological space is called Polish space if it is homeomorphic to a complete metric space that has a countable dense subset. A Polish group is a topological group G that is also a Polish space. A Borel probability measure on a topological space is a probability measure that is defined on all open sets. A subset of a Polish group G is called universally measurable if it is measurable with respect to
every Borel probability measure on G. A homomorphism $\phi: G\to H$ between Polish groups G and H is called universally measurable if $\phi^{-1}(U)$ is a universally measurable set in G for every open set $U \subseteq H$ .

The Theorem: On 8th December 2018, Christian Rosendal submitted to the Forum of mathematics, Pi a paper in which he proved that every universally measurable homomorphism between Polish groups is automatically continuous.

Short context: The Theorem resolves a longstanding problem posed by Christensen in 1971. It can be viewed as a generalisation of old classical theorem stating that any Lebesgue measurable function $f:{\mathbb R}\to{\mathbb R}$ satisfying the functional equation $f(x+y)=f(x)+f(y), \, x,y \in {\mathbb R}$ must be continuous.

Links: The original paper is available here.

Go to the list of all theorems

Local Fourier Uniformity conjecture is true for s = 1 at scale X^θ

You need to know: Prime factorisation of positive integers, complex numbers, integration, supremum $\sup$ , small o notation,

Background: For a positive integer n, let $\Omega(n)$ be the number of prime factors of n, counted with multiplicity. Function $\lambda(n)=(-1)^{\Omega (n)}$ is known as the Liouville function. Also, denote $e(t)=\exp(2\pi i t)$ .

The Theorem: On 4th December 2018, Kaisa Matomäki, Maksym Radziwiłł, and Terence Tao submitted to arxiv a paper in which they proved the following result. Let $\theta\in(0,1)$ be given and set $H = X^\theta$ . Then $\int\limits_X^{2X}\sup\limits_{\alpha} \left|\sum\limits_{x<n\leq x+H} \lambda(n)e(-\alpha n)\right|dx = o(XH)$ as $X\to\infty$ .

Short context: The Theorem confirms the first non-trivial case of a conjecture which is called the Local Fourier Uniformity conjecture. In turn, this conjecture is needed to prove the general case of the logarithmically averaged version of the Chowla conjecture, see here for its formulation and partial progress.

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

Go to the list of all theorems

The logarithmically averaged Chowla conjecture for two-point correlations is true

You need to know: Prime factorisation of positive integers, small o notation.

Background: For a positive integer n, let $\Omega(n)$ be the number of prime factors of n, counted with multiplicity. Function $\lambda(n)=(-1)^{\Omega (n)}$ is known as the Liouville function.

The Theorem: On 17th September 2015, Terence Tao submitted to arxiv and the Forum of mathematics, Pi a paper in which he proved the following result. Let $a_1, a_2$ be natural numbers, and let $b_1, b_2$ be integers such that $a_1b_2 - a_2b_1 \neq 0$ . Let $1 \leq w(x) \leq x$ be a quantity depending on x that goes to infinity as $x \to \infty$ . Then one has $\sum\limits_{x/w(x)<n\leq x} \frac{\lambda(a_1n+b_1)\lambda(a_2n+b_2)}{n}=o(\log w(x))$ as $x\to\infty$ .

Short context: Famous Chowla conjecture predicts that for any sequence of distinct integers $h_1, h_2, \dots, h_k$ , one has $\sum\limits_{n \leq x}\lambda(n+h_1)\dots\lambda(n+h_k)=o(x)$ as $x\to\infty$ . It is open for all $k\geq 2$ . The $k=2$ case (also called Chowla conjecture for two-point correlations) states that $\sum\limits_{n \leq x}\lambda(n)\lambda(n+h)=o(x)$ as $x\to\infty$ . With $w(x)=x$ , $a_1=a_2=1$ , $b_1=0$ and $b_2=h$ , the Theorem implies that $\sum\limits_{n \leq x}\frac{\lambda(n)\lambda(n+h)}{n}=o(\log x)$ . The author called the Theorem “logarithmically averaged version” of the $k=2$ case of the Chowla conjecture.

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

Go to the list of all theorems

Any finite subgroup of GL_n(C) has a semi-invariant of degree at most Cn

You need to know: Set ${\mathbb C}$ of complex numbers, set ${\mathbb C}^n$ of vectors $z=(z_1,\dots,z_n)$ with complex entries, homoheneous polynomial in n variables, degree of a polynomial, group, subgroup, matrix, determinant of a matrix, group $\text{GL}_n({\mathbb C})$ (group of $n\times n$ matrices with complex entries and non-zero determinant).

Background: Let $H_{n}({\mathbb C})$ be the set of homogeneous polynomials in n complex variables with complex coefficients. Let G be a finite subgroup of $\text{GL}_n({\mathbb C})$ . A polynomial $P \in H_{n}({\mathbb C})$ is called semi-invariant of G if for every matrix $A\in G$ we have $P(Az)=B_A P(z),\, \forall z \in {\mathbb C}^n$ , where $B_A\in {\mathbb C}$ is a constant depending on A. Let $d(G)$ be the minimum integer k such that G has a semi-invariant of degree k.

The Theorem: On 8th January 2016, Pham Huu Tiep submitted to Forum of Mathematics, Pi a paper in which he proved the existence of constant $C<\infty$ such that $d(G) \leq Cn$ for every finite subgroup G of $\text{GL}_n({\mathbb C})$ . In fact, $C=1,184,036$ works.

Short context: In 1981, Thompson proved that, if $n>1$ is any integer and G is any finite subgroup of $\text{GL}_n({\mathbb C})$ , then $d(G)\leq 4n^2$ . He further conjectured that this quadratic upper bound can be improved to a linear one. The Theorem confirms this conjecture.

Links: The original paper is available here.

Go to the list of all theorems

The Grothendieck constant is strictly smaller than Krivine’s bound

You need to know: Euclidean space ${\mathbb R}^n$ , inner product $\langle x,y\rangle=\sum\limits_{i=1}^n x_i y_i$ in ${\mathbb R}^n$ , unit vector in ${\mathbb R}^n$ , matrix, big O notation.

Background: In 1953, Grothendieck proved the existence of a universal constant $K<\infty$ such that, given any $m\times n$ matrix with real entries $a_{ij}$ and arbitrary unit vectors $x_1,\dots, x_m,y_1,\dots, y_n$ in ${\mathbb R}^{m+n}$ , there are signs $\epsilon_1,\dots,\epsilon_m,\delta_1,\dots,\delta_n \in \{-1, +1\}$ such that inequality $\sum\limits_{i=1}^m \sum\limits_{j=1}^n a_{ij}\langle x_i, y_j \rangle \leq K \sum\limits_{i=1}^m \sum\limits_{j=1}^n a_{ij}\epsilon_i \delta_j$ holds. This is called the Grothendieck’s inequality. The minimal constant K for which it holds is called the Grothendieck constant, and is denoted $K_G$ . See here for a version of the Grothendieck constant of a graph.

The Theorem: On 31st March 2011, Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor submitted to arxiv a paper in which they proved the existence of a constant $\epsilon_0>0$ such that $K_G < \frac{\pi}{2\log(1+\sqrt{2})}-\epsilon_0$ .

Short context: The Grothendieck’s inequality, despite being innocent-looking at the first glance, turned out to be important in many areas of mathematics and applications, such as functional analysis, harmonic analysis, operator theory, quantum mechanics, and computer science. For many applications, it is important to have it with the best possible constant. However, despite substantial efforts, even the second digit of $K_G$ remains unknown. The best lower bound is $K_G\geq 1.67696...$ proved by Davie in 1984. For the upper bound, Krivine proved in 1979 that $K_G \leq \frac{\pi}{2\log(1+\sqrt{2})}=1.7822...$ , and conjectured that $K_G$ is actually equal to this value. This conjecture was well-believed, and many researchers focused on proving the matching lower bound. The Theorem states that Krivine’s conjecture is false.

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

Go to the list of all theorems

The group of boundary fixing homeomorphisms of the disc is not left-orderable

You need to know: Euclidean space ${\mathbb R}^2$ , norm $|x|=\sqrt{x_1^2+x_2^2}$ of $x=(x_1,x_2)\in {\mathbb R}^2$ , continuous functions on ${\mathbb R}^2$ , bijection (function which is one-to-one and onto), inverse function, group.

Background: Let $B=\{x\in {\mathbb R}^2 : |x|\leq 1\}$ and $S^1=\{x\in {\mathbb R}^2 : |x|=1\}$ be the unit disk and the unit circle in ${\mathbb R}^2$ , respectively. A function $f:B\to B$ is called a homeomorphism if (i) f is a bijection, (ii) f is continuous, and (iii) the inverse function $f^{-1}$ is continuous. We say that function $f:B\to B$ is boundary fixing if $f(x)=x$ for all $x\in S^1$ . We say that function $h:B\to B$ is the composition of functions $f:B\to B$ and $g:B\to B$ , if $h(x)=f(g(x))$ for all $x\in B$ . It is known that the set of all boundary fixing homeomorphisms $f:B\to B$ with composition operation forms a group which we denote $\text{Homeo}(B,S^1)$ . In general, group G with operation $\cdot$ is called left orderable if there exists a total order $\leq$ on G such that $a\leq b$ implies $c\cdot a \leq c\cdot b$ for all $a,b,c \in G$ .

The Theorem: On 30th October 2018, James Hyde submitted to arxiv a paper in which he proved that the group $\text{Homeo}(B,S^1)$ of boundary fixing homeomorphisms of B is not left-orderable.

Short context: The question whether the group $\text{Homeo}(B,S^1)$ is left-orderable has been asked by many researchers and has been included in several collections of the open problems in group theory. The Theorem resolves this question affirnatively.

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

Go to the list of all theorems