Entropies of multidimensional shifts of finite type may be impossible to compute

You need to know: Set ${\mathbb Z}^d$ of vectors $y=(y_1, \dots, y_d)$ with integer coordinates, countable and uncountable sets, computable real number.

Background: Let $F \subset {\mathbb Z}^d$ be a finite set of $|F|$ points in ${\mathbb Z}^d$ , and let $\Sigma$ be a finite set of $|\Sigma|$ colours. Let L be any subset of $|F|^{|\Sigma|}$ colourings of F. A translate of F by $x \in {\mathbb Z}^d$ is the set $\{x + y, \,|\, y \in F\}$ . A colouring of ${\mathbb Z}^d$ in colours from $\Sigma$ is called admissible for L if all translates of F are coloured according to a pattern belonging to L. The shift of finite type (SFT) defined by L is the set X of all admissible colourings of ${\mathbb Z}^d$ .

For every positive integer n, let $F_n$ be the set of points $(y_1, \dots, y_d) \in {\mathbb Z}^d$ such that $1 \leq y_i \leq n$ for all $i=1,2,\dots, d$ . For the SFT X, let $f_X(n)$ be the number of different colourings of $F_n$ which can appear in some colouring $x \in X$ . The (topological) entropy of X is then defined as $h(X) = \lim\limits_{n \to \infty} \frac{1}{n^d}\log_2 f_X(n)$ .

The Theorem: On 7th March 2007, Michael Hochman and Tom Meyerovitch submitted to arxiv a paper in which they proved the existence of SFT X such that real number $y=h(X)$ is not computable.

Short context: Because there are uncountably many real numbers and only countably many algorithms, there exist real numbers which are not computable. However, important real numbers naturally arising in mathematics and applications, such as $\pi=3.14159...$ and $e=2.71828...$ , are computable. The Theorem provides examples of real numbers which are not computable but quite meaningful, because SFTs are important objects of study in symbolic dynamics, and the entropy is their most studied invariant. The Theorem is a corollary of a more general result stating that a real number $h\geq 0$ is the entropy of some SFT if and only if it is right recursively enumerable, that is, there is a computable sequence of rational numbers converging to h from above.

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

Go to the list of all theorems

There exists an outer billiards system with an unbounded orbit

You need to know: Euclidean plane ${\mathbb R}^2$ , convex set in ${\mathbb R}^2$ , bounded set or sequence in ${\mathbb R}^2$ , the notion of (Lebesgue) almost every point in ${\mathbb R}^2$ .

Background: Given a bounded convex set $S \subset {\mathbb R}^2$ , and a point $x_0 \in {\mathbb R}^2$ outside S, let $x_1 \in {\mathbb R}^2$ be the point such that the segment $x_0x_1$ is tangent to S at its midpoint and a person walking from $x_0$ to $x_1$ would see S on the right. Such $x_1$ exists and unique for almost every $x_0 \in {\mathbb R}^2$ , and the map $x_0 \to x_1$ is called the outer billiards map. Iterating this maps starting from $x_0$ , we get an infinite sequence $x_0 \to x_1 \to x_2 \to \dots$ , which is called an outer billiards orbit of $x_0$ .

The Theorem: On 3rd February 2007, Richard Schwartz submitted to arxiv a paper in which he proved the existence of set $S \subset {\mathbb R}^2$ and $x_0 \in {\mathbb R}^2$ such that the outer billiards orbit of $x_0$ is well-defined and unbounded.

Short context: The question whether an outer billiards orbit can be unbounded was asked by Neumann in the 1950s, and since then has been a guiding question in the field. The Theorem answers this question affirmatively. In fact, Schwartz provides an explicit example of set S in the Theorem: this is the convex quadrilateral known as the Penrose kite.

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

Go to the list of all theorems

w_1(A_n)w_2(A_n)=A_n for every non-trivial group words w_1,w_2 and every large alternating group A_n

You need to know: Group, identity element, finite group, simple group, free group, alternating group $A_n$ of degree n.

Background: Let $w = w(x_1,\dots,x_d)$ be a non-trivial group word, that is, a non-identity element of the free group $F_d$ on $x_1,\dots,x_d$ . For a group G, denote $w(G)$ the set of all elements $g \in G$ which can be obtained by substitution of some $g_1, g_2, \dots, g_d \in G$ into w instead of $x_1, x_2, \dots, x_d$ , respectively, and performing the group operation. For subsets $A,B$ of group G, let $A\cdot B=\{g \in G: g=a\cdot b, \, a\in A, \, b\in B\}$ .

The Theorem: On 11th January 2007, Michael Larsen and Aner Shalev submitted to arxiv a paper in which they proved that (i) for each pair of non-trivial words $w_1$ , $w_2$ there exists $N =N(w_1, w_2)$ such that for all integers $n \geq N$ we have $w_1(A_n)w_2(A_n) = A_n$ , and (ii) for every triple of non-trivial group words $w_1, w_2, w_3$ , there exists $N =N(w_1, w_2,w_3)$ such that $w_1(G)w_2(G)w_3(G) = G$ for every finite simple group with at least N elements.

Short context: In an earlier paper, Shalev proved that $w^3(G)=G$ for every non-trivial group word w, and every sufficiently large finite simple group $G$ . Part (ii) of the Theorem generalises this result (and implies it with $w_1=w_2=w_3=w$ ). Moreover, the authors conjectured that the same is true for just 2 group words! Part (i) of the Theorem proves this conjecture for the alternating groups.

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

Go to the list of all theorems

Moments M_k(T) of the Riemann zeta function are at most CT(log T)^(k^2+e)

You need to know: Complex number, absolute value $|z|$ and real part $\text{Re}(z)$ of complex number z, function of complex variable, meromorphic function, analytic continuation, integration.

Background: For a complex number $z$ with $\text{Re}(z)>1$ , let $\zeta(z)=\sum\limits_{n=1}^\infty \frac{1}{n^z}$ . By analytic continuation, function $\zeta(z)$ can be extended to a meromorphic function on the whole complex plane, and it is called a Riemann zeta function. The Riemann hypothesis states that if $\zeta(z)=0$ then either $z=-2k$ for some integer $k>0$ or $\text{Re}(z)=\frac{1}{2}$ . For $k>0$ , function $M_k(T) = \int_0^T |\zeta(1/2+it)|^{2k} dt$ is called a 2k-th moment of $\zeta$ .

The Theorem: On 4th December 2006, Kannan Soundararajan submitted to the Annals of Mathematics a paper in which he, assuming the Riemann hypothesis, proved that for every $k>0$ and $\epsilon>0$ there is a constant $C=C(k,\epsilon)$ such that inequality $M_k(T) \leq C T(\log T)^{k^2+\epsilon}$ holds for all $T>2$ .

Short context: Riemann zeta function $\zeta$ is one of the most studied functions in mathematics, and the Riemann hypothesis (RH) is one of the most important open problems. One line of study related to $\zeta$ is understanding the growth of moments $M_k(T)$ . It was known that (assuming RH) $c_k T(\log T)^{k^2} \leq M_k(T)$ for some $c_k>0$ and the Theorem provides an almost (up to $\epsilon$ ) matching upper bound. In a later work, Harper (again assuming RH) improved the upper bound to $M_k(T) \leq C_k T(\log T)^{k^2}$ , matching with the lower bound up to the constant factor.

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

Go to the list of all theorems

Littlewood’s question about zeros of cosine polynomials has a negative answer

You need to know: Cosine function $\cos$ , logarithm $\log$ .

Background: For integer $N>0$ , let $f(N)$ be the minimal number of solutions in $[0,2\pi)$ of the equation $\sum\limits_{i=1}^{N} \cos(n_ix)=0$ , where $n_1, n_2,\dots, n_N$ are integers which are all different.

The Theorem: On 26th November 2006, Peter Borwein, Tamás Erdélyi, Ron Ferguson, and Richard Lockhart submitted to the Annals of Mathematics a paper in which they proved the existence of a constant $C>0$ , a sequence of integers $N_1<N_2<\dots<N_m<\dots$ , such that $f(N_m) \leq CN_m^{5/6}\log N_m$ for all m.

Short context: In 1968, Littlewood asked to estimate $f(N)$ and guessed that the answer is “Possibly $f(N)=N-1$ , or not much less”. The Theorem proves that in fact $f(N)$ can be much less that $N-1$ .

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

Go to the list of all theorems

For any e>0, approximating max clique and chromatic number to within n^(1-e) are NP-hard

You need to know: Class P, class NP, NP-hard problems, graph, vertices, edges, clique.

Background: Given graph G, let $c(G)$ be the size of the largest clique in G, and $\chi(G)$ be the chromatic number of G (the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color). The MAX CLIQUE problem is: given graph G, compute $c(G)$ . The CHROMATIC NUMBER problem is: given graph G, compute $\chi(G)$ . We say that algorithm approximates the MAX CLIQUE (respectively, CHROMATIC NUMBER) to within $f(n)$ if it, given graph G with n vertices, returns number k such that $\frac{c(G)}{f(n)} \leq k \leq f(n)c(G)$ (respectively, $\frac{\chi(G)}{f(n)} \leq k \leq f(n)\chi(G)$ ).

The Theorem: On 7th November 2006, David Zuckerman submitted to the Theory of Computing a paper in which he proved that (i) for any $\epsilon>0$ , it is NP-hard to approximate MAX CLIQUE to within $n^{1-\epsilon}$ , and (ii) for any $\epsilon>0$ , it is NP-hard to approximate CHROMATIC NUMBER to within $n^{1-\epsilon}$ .

Short context: MAX CLIQUE and CHROMATIC NUMBER are examples of problems which are NP-hard to solve exactly. Some other NP-hard problems can at least be efficiently approximated. However, the Theorem states that these two problems are NP-hard to approximate to within $n^{1-\epsilon}$ . Note that trivial “algorithm” outputting $n$ for any graph is an approximation to within $n$ , so the Theorem states that we cannot even improve this trivial “algorithm” by $\epsilon$ in the exponent.

Links: The original paper is available here.

Go to the list of all theorems

Systems of polynomial equations can be solved in expected polynomial time

You need to know: Complex numbers, polynomials in complex variable, notation ${\mathbb C}^n$ for set of vectors $z=(z_1, \dots, z_n)$ with complex $z_i$ , algorithm, probabilistic algorithm, average running time of an algorithm.

Background: Let $n>0$ be a positive integer. Let H be the space of all systems $f = [f_1,\dots ,f_n]:{\mathbb C}^n \to {\mathbb C}^n$ on n polynomial equations in n unknowns. For $f \in H$ , denote $V_{\mathbb C}(f) = \{x \in {\mathbb C}^n : f_i(x) = 0, \, 1 \leq i \leq n\} \subset {\mathbb C}^n$ the set of solutions of $f$ .

The Theorem: On 2nd November 2006, Carlos Beltrán and Luis Pardo submitted to the Journal of the AMS a paper in which they described an explicit probabilistic algorithm that computes an approximate solution of any given $f \in H$ with any given accuracy (with probability 1), and proved that the average number of arithmetic operations of this algorithm is polynomial in the size of the input.

Short context: Solving polynomial equations and systems of such equations is one of the fundamental problems in the whole mathematics. In 1998, Smale presented a list of problems he considered as the most important ones for the 21st century. Smales 17th problem asks for the algorithm which could solve systems of polynomial equations with polynomial average running time. The Theorem provides a probabilistic algorithm which achieves this. See here and here for further progress in later works.

Links: The original paper is available here.

Go to the list of all theorems

The primes contain arbitrarily long polynomial progressions

You need to know: Prime numbers, polynomials, arithmetic progression.

Background: Let ${\mathbb Z}[m]$ denote the set of polynomials in one variable m with integer coefficients.

The Theorem: On 1st October 2006, Terence Tao and Tamar Ziegler submitted to arxiv a paper in which they proved that given any polynomials $P_1,\dots , P_k\in {\mathbb Z}[m]$ with $P_1(0)=\dots=P_k(0)=0$ , there are infinitely many pairs of positive integers $x$ and $m$ such that numbers $x+P_1(m),\dots , x+P_k(m)$ are simultaneously prime.

Short context: The sequence $x+P_1(m),\dots , x+P_k(m)$ is called a polynomial progression. In an earlier work, Green and Tao proved that primes contains arbitrary long arithmetic progressions, which corresponds to the case $P_j(m)=(j-1)m, \, j=1,\dots,k$ . The Theorem generalises this result to polynomial progressions. Moreover, the authors proved that for any $\epsilon>0$ , there are infinitely many pairs $(x,m)$ as in the Theorem with $1 \leq m \leq x^{\epsilon}$ . In addition, they proved that even any positive proportion of primes contains infinitely many polynomial progressions.

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

Go to the list of all theorems

Computing the forth moment of of Dirichlet L-functions at the central point for prime moduli with a power saving error

You need to know: Complex number, absolute value $|z|$ and real part $\text{Re}(z)$ of complex number z, function of complex variable, meromorphic function, analytic continuation, big O notation. Also, see this previous theorem description for the concept of primitive Dirichlet character modulo integer $q>0$ .

Background: For a prime $q$ , denote ${\cal P}(q)$ the set of all primitive Dirichlet characters $\chi$ modulo q, and let $\phi^*(q)$ be the number of such characters. For $\chi \in {\cal P}(q)$ , and complex number $z$ with $\text{Re}(z)>1$ , let $L(z,\chi)=\sum\limits_{n=1}^\infty \frac{\chi(n)}{n^z}$ . By analytic continuation, function $L(z,\chi)$ can be extended to a meromorphic function on the whole complex plane, and it is called a Dirichlet L-function.

The Theorem: On 22nd September 2006, Matthew Young submitted to the Annals of Mathematics a paper in which he proved that for any prime $q\neq 2$ and any $\epsilon>0$ , $\frac{1}{\phi^*(q)}\sum\limits_{\chi \in {\cal P}(q)}|L(\frac{1}{2},\chi)|^4 = \sum\limits_{i=0}^4 c_i (\log q)^i + O(q^{-\frac{5}{512}+\epsilon})$ , where $c_i$ are some explicitly computable absolute constants.

Short context: Dirichlet L-functions are generalisations of famous Riemann zeta function (which corresponds to the case $\chi(n)=1$ ), and estimating their moments, especially at point $z=\frac{1}{2}$ (which is called the central point), is an important problem in number theory with many applications. The Theorem computes the fourth moment of Dirichlet L-functions at $z=\frac{1}{2}$ for prime moduli q, with error term decreasing as a power of q. Ealier, similar formula was derived (by Heath-Brown in 1979) only for the Riemann zeta function.

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

Go to the list of all theorems

The kissing numbers in dimensions 5,6,7,9,10 are at most 45,78,135,366,567

You need to know: n-dimensional Euclidean space ${\mathbb R}^n$ , sphere in ${\mathbb R}^n$ , nonoverlapping spheres, touching spheres.

Background: The kissing number $k(n)$ is the highest number of equal nonoverlapping spheres in ${\mathbb R}^n$ that can touch another sphere of the same size.

The Theorem: On 16th August 2006, Christine Bachoc and Frank Vallentin submitted to arxiv a paper in which they developed a new method for proving upper bounds for the kissing numbers in all dimensions, which, in particular, allows them to prove that $k(5) \leq 45$ , $k(6) \leq 78$ , $k(7) \leq 135$ , $k(9) \leq 366$ , $k(10) \leq 567$ .

Short context: Determining the kissing number is an interesting long-standing problem in geometry, which, before 2006, was solved only in dimensions $k=1,2,3,4,8$ and $24$ (see here for the $k=4$ case). In other dimensions, only lower and upper bounds were known, for example, $40 \leq k(5) \leq 46$ , $72 \leq k(6) \leq 82$ , etc. The Theorem provides a methodology for computing better upper bounds in all dimensions in which the problem is open.

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

Go to the list of all theorems