The tau_n=n conjecture in approximation by algebraic integers is false

You need to know: Polynomial, degree of a polynomial, leading coefficient, irreducible polynomial over the integers, supremum.

Background: A real number $\alpha$ is called algebraic number if there exists a polynomial P with integer coefficients such that $P(\alpha)=0$ . Real numbers which are not algebraic are called transcendental. Below, we may and will assume that P is irreducible over the integers. The largest absolute value of the coefficients of P is called the height of $\alpha$ and denoted $H(\alpha)$ . If the leading coefficient of P is 1, $\alpha$ is called algebraic integer. The degree of an algebraic integer $\alpha$ is the degree of P. Also, let $\gamma=\frac{1+\sqrt{5}}{2}$ denote the golden ratio.

The Theorem: On 11th October 2002, Damien Roy submitted to arxiv and Annals of Mathematics a paper in which he proved the existence of a transcendental real number $\xi$ and constant $c>0$ such that, for any algebraic integer $\alpha$ of degree at most 3, we have $|\xi-\alpha| \geq c H(\alpha)^{-\gamma^2}$ .

Short context: For a positive integer n, let $\tau_n$ be the supremum of all $\tau \in {\mathbb R}$ such that for any transcendental $\xi \in {\mathbb R}$ there exist infinitely many algebraic integers $\alpha$ of degree at most n such that $|\xi-\alpha| \leq H(\alpha)^{-\tau}$ . $\tau_n$ measures the quality of approximation of real numbers by algebraic integers. It is known that $\tau_2=2$ and has been conjectured that $\tau_n=n$ for all $n\geq 2$ . In 1969, Davenport and Schmidt proved that $\tau_3\geq \gamma^2$ . The Theorem implies that $\tau_3\leq \gamma^2$ . Hence $\tau_3=\gamma^2=\frac{3+\sqrt{5}}{2}<3$ , and the $\tau_n=n$ conjecture is false.

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

Go to the list of all theorems

Minimum vertex cover is NP-hard to approximate within any factor c < 1.3606…

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

Background: A vertex cover of graph G is the set S of vertices of G such that for each edge $(u,v)$ of G either $u \in S$ or $v\in S$ (or both). Let $\tau(G)$ be the size of the smallest vertex cover of G. The minimum vertex cover problem is: given graph G, compute $\tau(G)$ . Its approximation with factor $c>1$ is: given graph G, compute number k such that $\tau(G) \leq k \leq c\tau(G)$ .

The Theorem: On 7th October 2002, Irit Dinur and Samuel Safra submitted to the Annals of Mathematics a paper in which they proved that the minimum vertex cover problem is NP-hard to approximate to within any constant factor smaller than $10\sqrt{5}-21 = 1.3606...$

Short context: Because the minimum vertex cover problem is well-known to be NP-hard to solve exactly, it is natural to look for approximate algorithms. A simple algorithm, discovered independently by Gavril and Yannakakis, gives approximation with factor $c=2$ , and this is the best known. In the opposite direction, Håstad proved in 2001 that the problem is NP-hard to approximate to within any factor $c<\frac{7}{6} = 1.1666...$ . The Theorem proves the same result with better factor $10\sqrt{5}-21 = 1.3606...$ in place of $\frac{7}{6}$ . See here for further progress in a later work.

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

Go to the list of all theorems

For partition function p(.), no prime q other than 5,7,11 divides p(qn+b) for all n

You need to know: Integers, divisibility, prime numbers.

Background: Let $p(n)$ be the partition function, that is, the number of representations of positive integer n as a sum of positive integers (representations which differ by order of terms only are considered the same). By convention, we also put $p(0) = 1$ and $p(n) = 0$ for $n < 0$ .

The Theorem: On 22nd September 2002, Scott Ahlgren and Matthew Boylan submitted to Inventiones mathematicae a paper in which they proved that there are no prime $q \neq 5, 7, 11$ , and integer b such that $p(qn+b)$ is divisible by q for all integers n.

Short context: In 1920, Ramanujan proved that $p(5n+4)$ always divisible by 5, $p(7n+5)$ – by 7, $p(11n+6)$ – by 11, and conjectured that “there are no equally simple properties for any moduli involving primes other than these three”. The Theorem confirms (a natural formalisation of) this conjecture.

Links: The original paper is available here.

Go to the list of all theorems

Zero-divisor graph of a local ring with at least 33 elements is not planar

You need to know: Ring, commutative ring, zero-divisor in a ring, graph, planar graph.

Background: Let R be a commutative ring. Element $u \in R$ is a unit if there is $v \in R$ such that $uv = vu = 1$ . Ring R is called local if $1 \neq 0$ and the sum of any two non-units in R is a non-unit. Let $Z(R)$ be the set of zero-divisors of R. The zero-divisor graph $\Gamma(R)$ of R is the graph with vertices $Z(R)\setminus\{0\}$ such that there is an (undirected) edge between vertices $a$ and $b$ if and only if $a \neq b$ and $ab=0$ .

The Theorem: On 15th September 2002, Saieed Akbari, Hamid Maimani, and Siamak Yassemi submitted to the Journal of Algebra a paper in which they proved, among other results, that if R is a local ring with at least 33 elements, and $\Gamma(R)\neq \emptyset$ , then $\Gamma(R)$ is not planar.

Short context: Studying properties of zero-divisor graphs of rings is important for understanding the structure of rings and their zero divisors. In particular, Anderson, Frazier, Lauve, and Livingston asked in 2001 an interesting question: which finite commutative rings have planar zero-divisor graphs? The Theorem answers this question for local rings.

Links: The original paper is available here.

Go to the list of all theorems

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

A group with exponential growth but not uniform exponential growth

You need to know: Group, finitely generated group, generating set.

Background: Let G be a finitely generated group. For any finite generating set S of G, let $\gamma_S(k)$ be the number of elements of G which are the product of at most k elements in $S \cup S^{-1}$ . Let $e_S(G)=\lim\limits_{k \to \infty}\sqrt[k]{\gamma_S(k)}$ . It is known that if $e_S(G)>1$ for some S then in fact $e_S(G)>1$ for all S, and, in this case, we say that G has exponential growth. If, moreover, $\inf_S e_S(G) > 1$ , where the infimum is taken over all finite generating sets S of G, we say that G has uniform exponential growth.

The Theorem: On 22nd June 2002, John Wilson submitted to Inventiones Mathematicae a paper in which he proved the existence of a finitely generated group G which has exponential growth but not uniform exponential growth.

Short context: In 1981, Gromov asked whether every group of exponential growth have uniform exponential growth. The question was answered affirmatively in many special cases, for example, for linear groups. The Theorem, however, shows that in general the answer is negative.

Links: The original paper is available here.

Go to the list of all theorems

A version of Banach’s fixed point theorem holds for partially ordered sets

You need to know: Complete metric space X, continuous map $f:X \to X$ , notation $f^n(x)$ for $f(f(\dots f(x)\dots))$ with f repeated n times, partially ordered set.

Background: Let $(T, \leq)$ be a partially ordered set. A map $f:T \to T$ is called monotone if it is either order-preserving ( $x \leq y$ implies $f(x) \leq f(y)$ ) or order-reversing ( $x \leq y$ implies $f(y) \leq f(x)$ ). A point $x\in T$ is called a fixed point of f if $f(x)=x$ .

The Theorem: On 19th June 2002, André Ran and Martine Reurings submitted to the Proceedings of the AMS a paper in which they proved the following result. Let T be a partially ordered set such that for every pair $x,y \in T$ there exist $u,v \in T$ such that $u\leq x \leq v$ and $u\leq y \leq v$ . Furthermore, let d be a metric on T such that $(T, d)$ is a complete metric space. If $f:T \to T$ is a continuous, monotone map such that (i) $\exists c\in(0,1): d(f(x),f(y))\leq c\cdot d(x,y), \, \forall x \geq y$ , and (ii) $\exists x_0\in T:\, x_0 \leq f(x_0) \,\text{or}\,x_0 \geq f(x_0)$ , then f has a unique fixed point $x^*$ . Moreover, $\lim\limits_{n\to\infty} f^n(x) = x^*$ for every $x\in T$ .

Short context: The 1922 Banach’s Fixed Point Theorem states that, if $(X,d)$ is a non-empty complete metric space and $f:X\to X$ is such that (*) $d(f(x),f(y))\leq c\cdot d(x,y), \, \forall x,y$ for some $c\in(0,1)$ , then f has a unique fixed point $x^*$ , and $\lim\limits_{n\to\infty} f^n(x) = x^*$ for every $x\in X$ . It is a fundamental result in mathematics with countless applications. The Theorem proves a version of it for partially ordered sets, in which condition (*) is required to hold only for ordered pairs $x,y$ . It has applications to, for example, matrix equations.

Links: The original paper is available here.

Go to the list of all theorems

Ergodic averages, taken along cubes whose sizes tend to infinity, converge in L^2

You need to know: Set ${\mathbb Z}^k$ of vectors $x=(x_1,\dots,x_k)$ with integer coordinates, addition in ${\mathbb Z}^k$ , set ${\mathbb N}$ of natural numbers, $\limsup$ notation.

Background: The upper density $d(A)$ of set $A \subset {\mathbb N}$ is $d(A)=\limsup\limits_{N\to \infty} \frac{1}{N}|A \cap \{1,2,\dots,N\}|$ . For any $A \subset {\mathbb Z}^k$ and $x\in {\mathbb Z}^k$ the translate $A+x$ is $\{y: \, y=a+x, \, a\in A \}$ . Let $t(A)$ be the minimal number of translates of A needed to fully cover ${\mathbb Z}^k$ . Set A is called syndetic if $t(A)<\infty$ . Also, denote $V_k \subset {\mathbb Z}^k$ the set of vectors $x=(x_1,\dots,x_k)$ with all coordinates $0$ or $1$ .

The Theorem: On 16th June 2002, Bernard Host and Bryna Kra submitted to the Annals of Mathematics a paper in which they proved that for any $A \subset {\mathbb N}$ with $d(A) > \delta > 0$ and integer $k \geq 1$ , the set of $n=(n_1, n_2, \dots, n_k) \in {\mathbb Z}^k$ such that $d\left(\bigcap\limits_{\epsilon\in V_k}\left(A + \sum\limits_{i=1}^k\epsilon_i n_i\right)\right) \geq \delta^{2^k}$ is syndetic.

Short context: The Theorem, as stated above, is a combinatorial reformulation of a deep theorem is the field of ergodic theory, which establishes $L^2$ -convergence of so-called “ergodic averages taken along cubes whose sizes tend to infinity”. The details of this original formulation are too difficult to be presented here.

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

Go to the list of all theorems

(2+e)n Steiner symmetrizations transform convex body in R^n into near ball

You need to know: Space ${\mathbb R}^n$ , scalar product $(x,y)$ in ${\mathbb R}^n$ , origin $(0,0,\dots,0)$ in ${\mathbb R}^n$ , ball in ${\mathbb R}^n$ , convex body in ${\mathbb R}^n$

Background: For non-zero $h\in {\mathbb R}^n$ , set $H = \{x \in {\mathbb R}^n, \, (x,h) = 0\}$ is called a hyperplane going through the origin. For every $x \in {\mathbb R}^n$ there exists a unique decomposition $x = y + th$ , where $y \in H$ , $t \in {\mathbb R}$ , and we can consider pair $(y,t)$ as “coordinates” in ${\mathbb R}^n$ . For fixed y and h, set $\{x, \, x=y+th, -\infty < t < \infty\}$ is the line which we denote $y+{\mathbb R}h$ . Steiner symmetrization of a convex body K with respect to H is the body $S_H(K) = \{(y,t): K \cap (y+{\mathbb R}h) \neq \emptyset, \, |t|\leq \frac{1}{2}|K \cap (y+{\mathbb R}h)|\}$ , where $|K \cap (y+{\mathbb R}h)|$ denotes the length of line interval $K \cap (y+{\mathbb R}h)$ .

The Theorem: On 29th May 2002, Boáz Klartag and Vitali Milman submitted to Inventiones mathematicae a paper in which they proved that, for any $\epsilon>0$ , there exists a constant $c>0$ , such that for any $n \geq 2$ and any convex body $K \subset {\mathbb R}^n$ , there exist $m\leq (2+\epsilon)n$ Steiner symmetrizations $S_1, S_2, \dots S_m$ such that the convex body $K'=S_m(S_{m-1}(...S_2(S_1(K))\dots))$ contains a ball of radius $r_1$ , but is contained in a ball of radius $r_2$ , with $\frac{r_1}{r_2} = c$ .

Short context: Steiner symmetrization was introduced by Steiner in 1838 in an attempt to prove the isoperimetric theorem (out of all bodies with given volume, the ball has minimal surface area), and, since that, become a major tool for proving many other geometric inequalities. In 1910, Caratheodory et.al. proved that for every convex body K there exists a sequence of symmetrizations of K that converges to a ball. The Theorem proves that we can obtain a body somewhat close to a ball in a surprisingly few steps.

Links: The original paper is available here.

Go to the list of all theorems

The Alon’s second eigenvalue conjecture is true

You need to know: Basic probability theory, random permutation, graph, d-regular graph, adjacency matrix of a graph, eigenvalue of a matrix, limits.

Background: For an even $d \geq 4$ , by random d-regular graph on n vertices we mean a graph formed from $d/2$ uniform, independent permutations on $\{1, . . . , n\}$ . For fixed d and fixed real $\epsilon>0$ , let $p_n$ be the probability that such a graph has the second largest eigenvalue of its adjacency matrix greater than $2 \sqrt{d-1} + \epsilon$ .

The Theorem: On 27th March 2002, Joel Friedman submitted to Memoirs of the AMS a monograph in which he proved that $\lim\limits_{n\to\infty} p_n = 0$ .

Short context: The adjacency matrix of any finite undirected graph G has only real eigenvalues, which can be written in non-increasing order $\lambda_1(G) \geq \lambda_2(G) \geq \dots \geq \lambda_n(G)$ . For d-regular G, $\lambda_1(G)=d$ . In 1986, Alon observed that graphs G with $\lambda_2(G)$ small have various nice properties, and conjectured that for any $\epsilon>0$ and any $d\geq 3$ , $\lambda_2(G) \leq 2 \sqrt{d-1} + \epsilon$ for “most” random d-regular graphs G. The constant $2 \sqrt{d-1}$ in this inequality is the best possible. This statement became known as Alon’s second eigenvalue conjecture. The Theorem, as stated above, resolves it for even d. In the same paper, Friedman also proved the conjecture for other models of random d-regular graph, including models for odd d.