The Catalan’s conjecture is true

You need to know: Integers, consecutive integers, notation $x^a$ for $x\times x \times \dots \times x$ ( $a$ times).

Background: An integer c is called a perfect power if $c=x^a$ for integers x and $a\geq 2$ .

The Theorem: On 9th September 2002, Preda Mihăilescu submitted to Journal für die reine und angewandte Mathematik a paper in which he proved that $8=2^3$ and $9=3^2$ are the only consecutive positive integers which are the perfect powers. In other words, $3^2-2^3=1$ is the only integer solution to the equation $x^a-y^b=1$ , such that $x,y > 0$ , $a,b > 1$ .

Short context: In 1343, Gersonides proved that 8 and 9 are the only consecutive perfect powers of 2 and 3. In 1844, Catalan conjectured that 8 and 9 are the only consecutive positive perfect powers at all. In 1976, Tijdeman reduced the Catalan’s conjecture to checking a finite but infeasibly many number of cases. The Theorem proves the conjecture in full.

Links: The original paper is available here.

Go to the list of all theorems

The size of set of simple sums and products of k distinct integers exceeds k^d

You need to know: The size $|S|$ of set S (that is, the number of elements in it), sum $\sum_{i=1}^k$ and product $\prod_{i=1}^k$ notations.

Background: Let $A=\{a_1, a_2, \dots, a_k\}$ be a set of k distinct integers, and let $S(A) = \left\{\sum_{i=1}^k \epsilon_i a_i \,|\,\epsilon_i = 0 \text{ or } 1\right\}$ and $\Pi(A) = \left\{\prod_{i=1}^k a_i^{\epsilon_i} \,|\,\epsilon_i = 0 \text{ or } 1\right\}$ be the set of all possible simple sums and products of elements of A, respectively. Let $g(k) = \min\limits_{A:|A|=k}(|S(A)|+|\Pi(A)|)$ .

The Theorem: On 27th November 2001, Mei-Chu Chang submitted to the Annals of Mathematics a paper in which she proved that for any $\epsilon>0$ there is a $k_0=k_0(\epsilon)$ such that $g(k) > k^{(1/2-\epsilon)\frac{\log k}{\log (\log k)}}$ for all $k\geq k_0$ .

Short context: In 1983, Erdős and Szemerédi conjectured that the set of sums $S(A)$ and set of products $\Pi(A)$ cannot both be small. Specifically, they conjectured that $g(k)$ grows faster than any polynomial in k, that is, for any d, there exists a constant $k_0=k_0(d)$ such that $g(k) > k^d$ for any $k \geq k_0(d)$ . The Theorem implies this conjecture and in fact provides a stronger lower bound on $g(k)$ . Because it is known that $g(k) < k^{c\frac{\log k}{\log (\log k)}}$ for some constant c, the bound in the Theorem is the best possible up to the constant factor in the exponent.

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

Go to the list of all theorems

Characterisation of linear recurrences whose ratio is integer infinitely often

You need to know: Set ${\mathbb N}$ of natural numbers, complex numbers, notation ${\mathbb C}[x]$ for the set of polynomials with complex coefficients.

Background: A linear recurrence is a sequence of complex numbers $\{G(n)\}_{n\in{\mathbb N}}$ such that $G(n+k)=c_0 G(n) + \dots + c_{k-1} G(n+k-1), \, n\in{\mathbb N}$ for some $k\geq 1$ and complex numbers $c_0, c_1, \dots, c_{k-1}$ .

The Theorem: On 12th November 2001, Pietro Corvaja and Umberto Zannier submitted to Inventiones Mathematicae a paper in which they proved that for any linear recurrences $F(n)$ and $G(n)$ such that $F(n)/G(n)$ is an integer for infinitely many values of n, there exists a nonzero polynomial $P(X) \in {\mathbb C}[X]$ and positive integers $q, r$ such that both sequences $\{P(n)F(qn+r)/G(qn+r)\}_{n\in{\mathbb N}}$ and $\{G(qn+r)/P(n)\}_{n\in{\mathbb N}}$ are linear recurrences.

Short context: In 1988, van der Poorten, confirming a conjecture of Pisot,
proved that if the ratio $F(n)/G(n)$ of linear recurrences $F(n), G(n)$ is an integer for all large n, then $F(n)/G(n)$ is itself a linear recurrence. In 1989, van der Poorten asked whether a similar result can be proved under much weaker assumption that $F(n)/G(n)$ is an integer infinitely open. This is what the Theorem achieves.

Links: The original paper is available here.

Go to the list of all theorems

There exist non-isotrivial elliptic curves over F_p(t) with arbitrarily large rank

You need to know: Field, elliptic curve over field, rank of elliptic curve, finite field ${\mathbb F}_p$ (field of integers modulo prime p)

Background: The j-invariant of an ellipltic curve E given in the form $y^2=x^3+ax+b$ is $j(E)=1728\frac{4a^3}{4a^3+27b^2}$ . Let ${\mathbb F}_p(t)$ be the field of rational functions of the form $f(t)=\frac{a_mt^m+a_{m-1}t^{m-1}+a_1t+a_0}{b_nt^n+b_{n-1}t^{n-1}+b_1t+b_0},$ where $a_m,\dots,a_1,a_0,b_n,\dots,b_1,b_0 \in {\mathbb F}_p$ . Elliptic curve E over field ${\mathbb F}_p(t)$ is called isotrivial if $j(E) \in {\mathbb F}_p$ , and non-isotrivial otherwise.

The Theorem: On 19th May 2001, Douglas Ulmer submitted to the Annals of Mathematics arxiv a paper in which he proved that elliptic curve E defined over the field ${\mathbb F}_p(t)$ by the equation $y^2 + xy = x^3 - t^d,$ where $d = p^n + 1$ for some positive integer n, is non-isotrivial and has the rank at least $(p^n - 1)/2n$ .

Short context: For elliptic curves over rationals, the question whether rank can be arbitrary large is important and open. By 2001, the largest known rank was 24 (later, in 2006, Elkies discovered an elliptic curve over ${\mathbb Q}$ with a rank at least 28). In contrast, Shafarevitch and Tate produced in 1967 elliptic curves over ${\mathbb F}_p(t)$ of arbitrarily large rank. These curves are isotrvial. The Theorem produces first non-isotrivial examples of elliptic curves over ${\mathbb F}_p(t)$ of arbitrarily large rank.

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

Go to the list of all theorems

For any r-colouring of integers, there is a monochromatic set S with sum of reciprocals 1

You need to know: Basic arithmetic, notation $b^r$ for b to the power r, notation $[x,y]$ for integers between x and y.

Background: By r-colouring of integers we mean assigning to each integer one of r colours, or, equivalently, partition all integers into r classes. Then set S of integers is called monochromatic if all integers $k\in S$ are coloured in the same colour, or, equivalently, belong to the same class in the partition.

The Theorem: On 16th May 2001, Ernie Croot submitted to the Annals of Mathematics a paper in which he proved the existence of a constant b such that for every partition of the integers in $[2, b^r]$ into r classes, there is always one class containing a subset S with the property $\sum\limits_{n\in S}\frac{1}{n}=1$ .

Short context: In 1980, Erdős and Graham asked if for any division of the integers $2, 3, 4, \dots$ into $r \geq 2$ classes, we can always represent 1 as a sum of distinct unit fractions using denominators from one class only. The Theorem gives a positive answer to this question. Moreover, it says we can do this using only denominators from 2 to $b^r$ . This bound is the best possible up to the value of b. Croot also proved that, for sufficiently large r, one may choose $b = 10^{72527}$ .

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

Go to the list of all theorems

Ellipsoid rE in R^d, d>=5, contains Vol(rE)+O(r^(d-2)) lattice points

You need to know: Euclidean space ${\mathbb R}^d$ of vectors $x=(x_1, \dots, x_d)$ , (coordinate-wise) addition of vectors, their multiplication by constants, scalar product $(x,y)=\sum_{i=1}^d x_iy_i$ , matrices, matrix multiplication, invertible matrix, (Lebesgue) volume in ${\mathbb R}^d$ , big $O()$ notation.

Background: For a (measurable) set $S \subset {\mathbb R}^d$ , let $\text{Vol}(S)$ be its (Lebesgue) volume in ${\mathbb R}^d$ , and let $\text{Vol}_{\mathbb Z}(S)$ be the number of points $x \in S$ with all coordinates $x_i$ being integers. For $S \subset {\mathbb R}^d$ , $a\in {\mathbb R}^d$ , and $r>0$ , denote $rS + a$ the set of points $y \in {\mathbb R}^d$ , such that $y=rx+a$ for some $x \in S$ .

Let Q be an invertible $d \times d$ matrix with real entries such that (a) $(Qx,y)=(x,Qy)$ for all $x,y \in {\mathbb R}^d$ , and (b) $(Qx,x)>0$ for every non-zero $x \in {\mathbb R}^d$ . For $s>0$ , let $E_s$ be the set of points $x \in {\mathbb R}^d$ such that $(Qx,x) \leq s$ . Any set of the form $rE_1 + a$ (for $a\in {\mathbb R}^d$ , and $r>0$ ) is called ellipsoid.

The Theorem: On 12th December 2000, Friedrich Götze submitted to the Inventiones Mathematicae a paper in which he proved that for any $d\geq 5$ and any Q as above, $\sup\limits_{a\in {\mathbb R}^d}\left|\frac{\text{Vol}_{\mathbb Z}(rE_1 + a)-\text{Vol}(rE_1)}{\text{Vol}(rE_1)}\right|=O(r^{-2})$ as $r\to\infty$ .

Short context: Set $rE_1 + a$ is just the ellipsoid $E_1$ scaled by r and shifted by a. The Theorem states that the number of integer points (also called lattice points) in such an ellipsoid can be approximated by its volume up to the relative error, decreasing at rate $O(r^{-2})$ as $r\to\infty$ , whenever $d\geq 5$ . Previously, this result was known only for $d\geq 9$ . The condition $d\geq 5$ is the best possible, because, for $d\leq 4$ , the error rate is known to decrease slower than $O(r^{-2})$ , even if $E_1$ is the unit sphere.

Links: The original paper is available here.

Go to the list of all theorems

Irreducible form F(x,y,z) of degree d has at most O(B^(2/d+e)) simple B-bounded roots

You need to know: Greatest common divisor (gcd), multivariate polynomial, absolutely irreducible multivariate polynomial, homogeneous polynomial (or form), degree of a form.

Background: For an absolutely irreducible form $F(x_1, x_2, \dots, x_n)$ of degree d with integer coefficients, we call solution $\textbf{x}=(x_1, x_2, \dots, x_n)$ to the equation $F(x_1, x_2, \dots, x_n)=0$ (or $F(\textbf{x})=0$ in short) simple if $\text{gcd}(x_1, x_2, \dots, x_n)=1$ and the first non-zero component of $(x_1,x_2,\dots x_n)$ is positive. Let $N_F(B)$ be the number of simple solutions to $F(\textbf{x})=0$ such that $\max\limits_{1 \leq i \leq n}|x_i| \leq B$ .

The Theorem: On 17th November 2000, Roger Heath-Brown submitted to the Annals of Mathematics a paper in which he proved that, for any absolutely irreducible form $F(x,y,z)$ of degree d in $n=3$ variables, and any $\epsilon>0$ , we have $N_F(B) \leq C(d, \epsilon)B^{2/d+\epsilon}$ , where $C(d, \epsilon)$ is a constant depending only on d and $\epsilon$ .

Short context: Counting integer solutions to polynomial equations is one of the basic and most-studied problems in mathematics, which is easy for forms in $n=1$ and $n=2$ variables. For (irreducible) forms in $n=3$ variables, Pila showed in 1995 that $N_F(B) \leq C(d, \epsilon)B^{1+1/d+\epsilon}$ . The Theorem improves the exponent in this estimate from $1+1/d+\epsilon$ to $2/d+\epsilon$ , which is in fact optimal.

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

Go to the list of all theorems

Set of m n-variate degree-d polynomials has at most (emd/n)^n zero patterns

You need to know: Field, polynomial over field, multivariate polynomials and their degrees, factorial $n!= 1\cdot 2 \cdot \dots \cdot n$ , notation ${N}\choose{M}$ $= \frac{N!}{M! (N-M)!}$ , base of natural logarithms $e$ .

Background: Let $f_1,...,f_m$ be a sequence of polynomials in n variables of degree at most d over a field F, where $m \geq n$ . The zero-pattern of this sequence at $u\in F^n$ is the set of indexes i ( $1 \leq i \leq m$ ) for which $f_i(u) = 0$ .

The Theorem: On 25th July 2000, Lajos Rónyai, László Babai, and Murali Ganapathy submitted to the Journal of the AMS a paper in which they proved that the number of zero-patterns (as u ranges over $F ^n$ ) is at most ${md-(d-2)n}\choose{n}$ for all $d\geq 1$ and $m \geq n$ .

Short context: Estimates for the number of zero-patterns are useful, for example, in the complexity analysis of so-called “quantifier elimination algorithms”. Motivated by this application, Heintz proved in 1983 that this number is at most $(1+md)^n$ . The Theorem implies upper bound $\left(\frac{emd}{n}\right)^n$ , which is better by a factor of $(n/e)^n$ . In fact, the authors show that, under some reasonable conditions, the bound in the Theorem is optimal up to the factor of $(7.25)^n$ .

Links: The original paper can be found here.

Go to the list of all theorems

Szemeredi’s theorem holds with doubly exponential bound

You need to know: Integers, addition, multiplication, power, logarithm, set, subset, size of set.

Background: Here, by arithmetic progression of length k we mean a sequence $a_1, a_2, \dots, a_k$ such that $a_n = a_1 + (n-1)d$ , $n=1,2,\dots, k$ , for some $d \neq 0$ .

The Theorem: In March 2000, Timothy Gowers submitted to Geometric and Functional Analysis (GAFA) a paper in which he proved that, for every positive integer k, every subset of $\{1, 2, \dots ,N\}$ of size at least $N(\log \log N)^{-c}$ , where $c=2^{-2^{k+9}}$ , contains an arithmetic progression of length k.

Short context: In 1975, Szemerédi proved that for any positive integer k and any $\delta > 0$ , there exists a positive integer $N = N(k, \delta)$ such that every subset of the set $\{1, 2, \dots ,N\}$ of size at least $\delta N$ contains an arithmetic progression of length k. This famous theorem is one of the milestones of combinatorics. However, the bound for N which follows from Szemerédi’s proof is huge. The Theorem proves that Szemeredi’s theorem holds with $N=\exp(\exp(\delta^c))$ .

Links: The original paper can be found here.

Go to the list of all theorems

Pair correlation densities of squared distances sequences

You need to know: Rational and irrational numbers, limits, constant $\pi=3.1415...$ . In addition, you need to know Poisson process and almost sure convergence to understand the context.

Background: For fixed real numbers $\alpha,\beta\in[0,1]$ , consider an infinite sequence $0 \leq \lambda_1 \leq \lambda_2 \leq \dots$ formed by the numbers $(m-\alpha)^2 + (n-\beta)^2$ for integer $m,n$ , arranged in the non-decreasing order. For interval $[a,b] \subset {\mathbb R}$ , the pair correlation function is $R_2[a,b](\lambda):=\frac{1}{\pi\lambda}|\{j \neq k\,|\,\lambda_j\leq \lambda, \, \lambda_k \leq \lambda, a \leq \lambda_j-\lambda_k\leq b\}|,$ where $|S|$ denotes the number of elements in set S.

Real numbers $\alpha_1, \alpha_2, \dots \alpha_k$ are linearly independent over ${\mathbb Q}$ if there are no rational numbers $r_1, r_2, \dots r_k$ , not all $0$ , such that $\sum_{i=1}^k r_i \alpha_i = 0$ . An irrational number $\alpha$ is called diophantine if there exist constants $k, C > 0$ such that $\left|\alpha - \frac{p}{q}\right| > \frac{C}{q^k}$ for every pair of integers p and $q\neq 0$ .

The Theorem: On 10th May 2000 Jens Marklof submitted to Annals of Mathematics a paper in which he proved that, if $\alpha, \beta, 1$ are linearly independent over ${\mathbb Q}$ , $\alpha$ is diophantine, and $a<b$ , then $\lim\limits_{\lambda \to \infty} R_2[a,b](\lambda) = \pi(b-a).$

Short context: In 1991, Cheng and Lebowitz observed numerically that, somewhat surprisingly, non-random sequence $0 \leq \lambda_1 \leq \lambda_2 \leq \dots$ as defined above share many properties with random sequence of event times in the Poisson process with mean $\pi$ . Because it is known that $\lim\limits_{\lambda \to \infty} R_2[a,b](\lambda) = \pi(b-a)$ almost surely for Poisson process, the Theorem confirms this numerical observation.

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

Go to the list of all theorems