A positive answer for Bergelson-Håland question on values of generalized polynomials

You need to know: Polynomial, operation of taking the integer part, limit, complex numbers, complex exponent.

Background: A generalized polynomial is a real-valued function which is obtained from conventional polynomials in one or several variables and applying in arbitrary order the operations of taking the integer part, addition, and multiplication.

The Theorem: On 17th October 2005, Vitaly Bergelson and Alexander Leibman submitted to the Acta Mathematica a paper in which they proved, among other results, that the limit $\lim\limits_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^N e^{2\pi i u(n)}$ exists for any bounded generalized polynomial $u$ .

Short context: The Theorem gives a positive answer to a 1996 question of Bergelson and Håland. It is just one of the many corollaries of deep theory on the distribution of values of bounded generalized polynomials developed by authors.

Links: The original paper is available here.

Go to the list of all theorems

Dyson’s rank partition functions satisfy congruences of Ramanujan type

You need to know: Prime numbers, notation $a\equiv b \,(\text{mod } q)$ if $a-b$ is a multiple of q.

Background: A partition $\lambda$ of an integer $m>0$ is a sequence $0<\lambda_1\leq \lambda_2 \leq \dots \leq \lambda_k$ of integers such that $\sum\limits_{i=1}^k \lambda_i = m$ . The difference $r(\lambda)=\lambda_k - k$ is called the rank (or Dyson’s rank) of $\lambda$ . Let $N(r,q; m)$ denote the number of partitions $\lambda$ of m such that $r(\lambda)\equiv r \,(\text{mod } q)$ .

The Theorem: On 10th October 2005, Kathrin Bringmann and Ken Ono submitted to the Annals of Mathematics a paper in which they proved the following result. Let t be a positive odd integer, and let $q$ be a prime such that $6t$ is not divisible by $q$ . If j is a positive integer, then there are infinitely many non-nested arithmetic progressions $An+B$ such that for every $0\leq r < t$ we have $N(r,t; An+B) \equiv 0 \, (\text{mod } q^j) \,\, n = 0,1,2,\dots$ .

Short context: A partition function $p(m)$ is the number of partitions of integer $m>0$ . In 1920, Ramanujan proved that $p(5n+4)$ always divisible by 5, $p(7n+5)$ – by 7, $p(11n+6)$ – by 11. In 2000, Ono proved that for any prime $q \geq 5$ there exist positive integers A and B such that $p(An+B) \equiv 0 \, (\text{mod } q)$ for all $n \geq 0$ (however, there are no prime $q \neq 5, 7, 11$ for which we can take $A=q$ , see here). The Theorem proves that function $N(r,q; m)$ (known as Dyson’s rank partition function) satisfies similar congruences of Ramanujan type.

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

Go to the list of all theorems

Menger’s theorem holds for infinite digraphs

You need to know: Graph, bipartite graph, directed graph (digraph), infinite digraph, path in a digraph.

Background: Let A and B be two sets of vertices in a possibly infinite digraph G. A path from some $a\in A$ to some $b\in B$ will be called A–B-path. We say that set S of vertices of G separates A from B if every A–B-path contains at least one vertex $s \in S$ .

The Theorem: On 18th September 2005, Ron Aharoni and Eli Berger submitted to arxiv a paper in which they proved that, given two sets of vertices, A and B, in a (possibly infinite) digraph, there exists a family P of disjoint A–B-paths, and a set S separating A from B, such that S consists of a choice of precisely one vertex from each path in P.

Short context: For any two sets A and B in a finite digraph G, let $\sigma(A,B)$ be the minimal size of set S which separates A from B, and let $\nu(A,B)$ be the maximal size of a family of vertex-disjoint paths from A to B. Obviously, $\sigma(A,B) \geq \nu(A,B)$ . In 1931, König proved that equality $\sigma(A,B) = \nu(A,B)$ holds for every finite bipartite graph G. By an earlier 1927 theorem of Menger, this implies that $\sigma(A,B) = \nu(A,B)$ in every finite digraph G (not necessary bipartite). This implies the existence of a family of disjoint paths and separating set with the one-to-one correspondence. In 1936, Erdős conjectured that the same remains true for infinite digraphs. The Theorem proves this conjecture.

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

Go to the list of all theorems

Elements of SL_2(F_p) have representations of length O((log p)^c)

You need to know: Arithmetic modulo p, field, field ${\mathbb F}_p$ (field with elements $0,1,\dots,p-1$ and operations modulo p, p prime), matrices, matrix multiplication, determinant of a $2 \times 2$ matrix, group, finite group, group $\text{SL}_2({\mathbb F}_p)$ (group of $2 \times 2$ matrices over ${\mathbb F}_p$ with determinant 1) , set of generators of a group. Also, non-abelian simple groups and their normal subsets (see here) are needed for the “context” section.

Background: For a finite group G with set of generators A, let $d(G,A)$ be the minimal integer m such that every $g\in G$ can be expressed as a product of at most m elements of A and their inverses.

The Theorem: On 1st September 2005, Harald Helfgott submitted to arxiv a paper in which he proved the existence of constants M and c such that $d(\text{SL}_2({\mathbb Z}/p{\mathbb Z}), A) \leq M (\log p)^c$ for every prime p and every set A of generators of $\text{SL}_2({\mathbb F}_p)$ .

Short context: Famous conjecture of Babai from 1992 states that $d(G,A) \leq M(\log |G|)^c$ for every set A of generators of a non-abelian finite simple group G with $|G|$ elements. The conjecture is open. See here for the solution of the special case when A is a normal set. The Theorem proves it for $G=\text{SL}_2({\mathbb F}_p)$ . The crucial contribution is that constants M and c in the Theorem does not depend neither on A nor on p.

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

Go to the list of all theorems

There exist consecutive primes which are closer than any arbitrarily small multiple of the average spacing

You need to know: Prime numbers, logarithm, limit inferior $\liminf$ .

Background: Let $p_n$ denotes the n-th prime number.

The Theorem: On 10th August 2005, Daniel Goldston, János Pintz, and Cem Yíldírím submitted to arxiv a paper in which they proved that $\liminf\limits_{n\to\infty}\frac{p_{n+1}-p_n}{\log p_n} = 0$ .

Short context: Famous twin prime conjecture states that $p_{n+1}-p_n=2$ for infinitely many n, and is wide open. The 1896 prime number theorem implies that the average size of $p_{n+1}-p_n$ is about $\log n$ , hence $\Delta=\liminf\limits_{n\to\infty}\frac{p_{n+1}-p_n}{\log p_n}$ is at most 1. In 1940, Erdős proved that $\Delta < 1-c$ for some small $c>0$ . This bound was then improved by many authors. In 1988, Maier proved that $\Delta \leq 0.2484...$ , and this remained the best bound until 2005. The Theorem proves that $\Delta=0$ . See here for further progress.

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

Go to the list of all theorems

Every n-point metric space of negative type embeds into an Euclidean space with distortion O((log n)^0.5 log log n)

You need to know: Euclidean space ${\mathbb R}^d$ , metric space $(X,\rho)$ with metric $\rho$ , big O notation.

Background: We say that a metric space $(X,\rho_X)$ can be embedded into metric space $(Y,\rho_Y)$ with distortion at most $\alpha$ if there exists a function $f:X\to Y$ such that $m \rho_X(x,y) \leq \rho_Y(f(x),f(y)) \leq M \rho_X(x,y), \, \forall x,y \in X$ , where $m,M>0$ are constants such that $\frac{M}{m}\leq \alpha$ . We say that a finite metric space $(X,\rho)$ with elements $x_1, x_2, \dots, x_n$ is of negative type if for any real numbers $c_1, \dots, c_n$ with $\sum\limits_{i=1}^n c_i = 0$ we have $\sum\limits_{i=1}^n\sum\limits_{j=1}^n c_i c_j \rho(x_i, x_j) \leq 0$ .

The Theorem: On 8th August 2005, Sanjeev Arora, James Lee, and Assaf Naor submitted to the Journal of the AMS a paper in which they proved that every n-point metric space of negative type can be embedded into an Euclidean space with distortion $O(\sqrt{\log n}\log\log n)$ .

Short context: Studying embeddings of metric spaces into each other with minimal distortion is and old topic, which has applications to algorithm development for combinatorial problems. Earlier in 2005, Chawla, Gupta, and Räcke proved that every n-point metric space of negative type can be embedded into an Euclidean space with distortion $O((\log n)^{3/4})$ . The Theorem improves this to $O(\sqrt{\log n}\log\log n)$ , which matches the lower bound $O(\sqrt{\log n})$ , established by Enflo in 1969, up to insignificant $\log\log n$ factor. The Theorem implies the existence of efficient approximation algorithm for the famous Sparsest Cut problem, which is more accurate than any previous one.

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

Go to the list of all theorems

The edge-deletion problem can be approximated in linear time

You need to know: Basic graph theory, bipartite graph, deterministic algorithm, approximation algorithm, running time of an algorithm, NP-hard problem, big O notation.

Background: A graph property is monotone if it is closed under removal of vertices and edges. The edge-deletion problem is: given a monotone property P and a graph G, compute the smallest number $E_P(G)$ of edge deletions that are needed in order to turn G into a graph satisfying P.

The Theorem: On 7th July 2005, Noga Alon, Asaf Shapira, and Benny Sudakov submitted to the Annals of Mathematics a paper in which they proved the following result. For any fixed $\epsilon>0$ and any monotone property P, there is a deterministic algorithm which, given a graph G with n vertices and m edges, approximates $E_P(G)$ in linear time $O(n+m)$ to within an additive error of $\epsilon n^2$ . On the other hand, if all bipartite graphs satisfy P, then for any fixed $\delta>0$ it is NP-hard to approximate $E_P(G)$ to within an additive error of $n^{2-\delta}$ .

Short context: How many edges we need to remove from a given graph G to make it, for example, triangle-free, or 3-colourable? The Theorem states that we can quickly solve any such problem approximately with error $\epsilon n^2$ but not with error $n^{2-\delta}$ for any $\delta>0$ . Before 2005, $\epsilon n^2$ approximation algorithm was not known even for triangle-free property, and the NP-hardness result was not known even for computing $E_P(G)$ exactly.

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

Go to the list of all theorems

The norm of the inverse of n by n matrix with i.i.d. subgaussian entries is at most Cn^1.5/e with probability 1-e, if e>c/n^0.5

You need to know: Probability (denoted by P), mean, variance, normal distribution, abbreviation i.i.d. for independent identically distributed random variables, Euclidean space ${\mathbb R}^n$ , notation $|x|$ for length of $x \in {\mathbb R}^n$ , matrix, matrix multiplication, inverse matrix, norm $||A||=\sup\limits_{x \in {\mathbb R}^n}\frac{|Ax|}{|x|}$ of $n \times n$ matrix A.

Background: A random variable X is called subgaussian if there exist constants
B and b such that $P(|X|>t) \leq Be^{-bt^2}$ for all $t>0$ . For integer $n>0$ , let $A_{n,X}$ be an $n \times n$ matrix whose entries $a_{ij}$ are i.i.d. with the same distribution as X.

The Theorem: On 30th June 2005, Mark Rudelson submitted to the Annals of Mathematics a paper in which he proved the following result. Let X be a subgaussian random variable with mean $0$ and variance $1$ . Then there are positive constants $C_1$ , $C_2$ , and $C_3$ such that for any integer $n>0$ , and any $\epsilon > C_1/\sqrt{n}$ , the inequality $\|A_{n,X}^{-1}\| \leq C_2\cdot n^{3/2}/\epsilon$ holds with probability greater than $1-\epsilon/2-4e^{-C_3n}$ .

Short context: As a special case, the Theorem applies to matrices whose i.i.d. entries are equal to $\pm 1$ with equal chances (Bernoulli matrices). It is known that such random matrix A is invertible with probability exponentially close to 1. The Theorem provides a bound for the norm $\|A^{-1}\|$ of the inverse matrix. The bound is polynomial in n and holds with probability greater than $1-\epsilon$ if n is large enough. Previously, similar bound was known only if i.i.d. entries $a_{ij}$ of A follow the normal distribution.

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

Go to the list of all theorems

For p, q > 0, L^p embeds uniformly into L^q if and only if p<=q or q<=p<=2

You need to know: Metric space $(M,d_M)$ with distance $d_M$ , integration, $L^p$ space for $p>0$ (space of measurable functions such that $\int|f|^p dx < \infty$ ), injective function, inverse $f^{-1}$ of function $f$ .

Background: Let $(M,d_M)$ and $(N,d_N)$ be metric spaces. A function $f:M \to N$ is called uniformly continuous if for every $\epsilon>0$ there exists a $\delta>0$ such that $d_N(f(x),f(y))<\epsilon$ for every $x,y \in M$ with $d_M(x,y)<\delta$ . We say that M embeds uniformly into N if there is an injective function $f:M \to N$ such that both $f$ and $f^{-1}$ are uniformly continuous.

The Theorem: On 10th June 2005, Manor Mendel, Assaf Naor submitted to arxiv a paper in which they proved, among other results, that for $p, q > 0$ , $L^p$ embeds uniformly into $L^q$ if and only if $p \leq q$ or $q \leq p \leq 2$ .

Short context: There is a large body of literature studying which metric spaces embeds uniformly into which. However, before 2005, this problem was not solved even for $L^p$ spaces. The Theorem provides a complete answer to this question. In fact, Mendel and Naor developed a deep and general theory of “metric cotype”, and the Theorem is just one out of many corollaries from this theory.

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

Go to the list of all theorems

(1,p)-Poincaré inequality implies (1,p-e)-Poincaré inequality for some e>0

You need to know: Euclidean space ${\mathbb R}^n$ , convergence in ${\mathbb R}^n$ with norm $||x||=\sqrt{\sum\limits_{i=1}^n}x_i^2$ , limit superior $\limsup$ , ball $B(x,r)=\{y\in {\mathbb R}^n : ||y-x||<r\}$ with centre x and radius $r>0$ , integration in ${\mathbb R}^n$ , Lipschitz continuous function $f:{\mathbb R}^n \to {\mathbb R}$ .

Background: For a function $w:{\mathbb R}^n \to {\mathbb R}$ (which we call a weight function) denote $|S|_w = \int_S w(x)dx$ the “weighted volume” of set $S\subset {\mathbb R}^n$ . For a function $f:{\mathbb R}^n \to {\mathbb R}$ denote $f_{S,w}=\frac{1}{|S|_w}\int_S f(x)w(x)dx$ its weighed average on S, and $\Delta(f,S,w)=\frac{1}{|S|_w}\int_S|f(x)-f_{S,w}|w(x)dx$ its weighted deviation from the average. We say that weight function $w:{\mathbb R}^n \to {\mathbb R}$ is p-admissible, $p \geq 1$ , if (i) there is a constant $C \geq 1$ such that $|B(x,2r)|_w \leq C |B(x,r)|_w$ holds for all $x \in {\mathbb R}^n$ and $r>0$ , (ii) $0 < |B|_w < \infty$ for every ball B, and (iii) there are constants $C' \geq 1$ and $0 < t \leq 1$ such that the inequality $\Delta(f,B(x_0,tr),w) \leq 2rC' \left(\frac{1}{|B|_w}\int_B (\text{Lip} f(x))^p w(x) dx \right)^{1/p}$ holds for all balls $B=B(x_0,r)$ , and for every Lipschitz continuous function $f:{\mathbb R}^n \to {\mathbb R}$ , where $\text{Lip}f(x) = \limsup\limits_{y\to x}\frac{|f(x)-f(y)|}{||x-y||}$ (this is called the $(1, p)$ -Poincaré inequality).

The Theorem: On 8th June 2005, Stephen Keith and Xiao Zhong submitted to the Annals of Mathematics a paper in which they proved that if $w:{\mathbb R}^n \to {\mathbb R}$ is a $p$ -admissible weight for some $p>1$ , then there exists an $\epsilon > 0$ such that $w$ is $q$ -admissible for every $q > p-\epsilon$ .

Short context: $(1, p)$ -Poincaré inequality controls the size of weighted deviations of Lipschitz continuous functions f in terms of $\text{Lip}f(x)$ , and the smaller p the better control. The Theorem, however, implies that we cannot have the smallest $p^*>1$ such that it holds: the inequality either holds for all $p\geq 1$ , or for values of p from some open interval.

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

Go to the list of all theorems