Any nondegenerate analytic submanifold of R^n is of Khintchine type for divergence

You need to know: Notation ${\mathbb R}^+$ for positive real numbers, Euclidean space ${\mathbb R}^n$ of vectors $x=(x_1,\dots,x_n)$ , norm $||x||_\infty = \max_i |x_i|$ , set ${\mathbb Z}^n$ of vectors with integer coordinates, affine subspace of ${\mathbb R}^n$ , proper subspace of ${\mathbb R}^n$ , open subset U of ${\mathbb R}^n$ , analytic map $f: U \to {\mathbb R}^m$ , the notion of (Lebesgue) almost all.

Background: For $y\in {\mathbb R}^n$ , let $||y||=\min\limits_{x \in {\mathbb Z}^n}||y-x||_\infty$ . For a decreasing function $\psi: {\mathbb R}^+ \to {\mathbb R}^+$ , let $S_n(\psi)$ be the set of points $y\in {\mathbb R}^n$ such that inequality $||m\cdot y||<\psi(m)$ holds for infinitely many positive integers m. Let $M=\{(x_1, \dots, x_d, f_1(x), \dots, f_m(x)) \in {\mathbb R}^n: x=(x_1, \dots, x_d) \in U)\}$ , where U is an open subset of ${\mathbb R}^d$ and $f=(f_1, \dots, f_m): U \to {\mathbb R}^m$ is an analytic map. We will call M analytic submanifold of ${\mathbb R}^n$ . M is called nondegenerate if it is not contained in a proper affine subspace of ${\mathbb R}^n$ . M is called of Khintchine type for divergence if for any $\psi$ such that $\sum\limits_{k=1}^\infty \psi(k)^n = \infty$ , almost all points on M belong to $S_n(\psi)$ .

The Theorem: On 2nd April 2009, Victor Beresnevich submitted to arxiv a paper in which he proved that any nondegenerate analytic submanifold of ${\mathbb R}^n$ is of Khintchine type for divergence.

Short context: If $x\in S_n(\psi)$ , then all coordinates of x can be simultanuously approximated by rational numbers with the same denominator, where function $\psi$ controls the error of approximation. In 1924, Khintchin proved that almost all points in ${\mathbb R}^n$ belong to $S_n(\psi)$ . However, submanifolds of ${\mathbb R}^n$ has measure $0$ , so Khintchin’s theorem says nothing about points on them. The Theorem states that coordinates of almost all points of any nondegenerate analytic submanifold of ${\mathbb R}^n$ can be simultanuously approximated. This result was known earlier only for $n=2$ .

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

Go to the list of all theorems

Any C^(2) nondegenerate planar curve is of Khintchine type for convergence

You need to know: Differentiable function, (k times) continuously differentiable function, sets of measure $0$ in ${\mathbb R}$ and ${\mathbb R}^2$ , notion of “almost all”, sum of infinite series, standard notations ${\mathbb R}^+$ for positive real numbers, ${\mathbb Z}$ for integers, ${\mathbb N}$ for natural numbers, $f'(x)$ for derivative, $f''(x)$ for the second derivative.

Background: Let $\psi: {\mathbb R}^+ \to {\mathbb R}^+$ be a decreasing function. Pair $(\alpha,\beta) \in {\mathbb R}^2$ is called simultaneously $\psi$ -approximable if there are infinitely many $n \in {\mathbb N}$ such that $\max\{||n\alpha||,||n\beta||\} < \psi(n)$ , where $||x||=\min\{|x-m|: m \in {\mathbb Z}\}$ denotes the distance from x to the nearest integer.

The Theorem: On 13th December 2005, Robert Vaughan and Sanju Velani submitted to the Inventiones mathematicae a paper in which they proved the following result. Let $\psi: {\mathbb R}^+ \to {\mathbb R}^+$ be a decreasing function with $\sum\limits_{n=1}^\infty \psi(n)^2 < \infty$ . Let f be a twice continuously differentiable function on some interval $(a, b)$ , such that $f''(x) \neq 0$ for almost all $x\in(a,b)$ . Then for almost all $x\in(a,b)$ the pair $(x, f(x))$ is not simultaneously $\psi$ -approximable.

Short context: Let $S(\psi)$ be the set of all pairs $(\alpha,\beta) \in {\mathbb R}^2$ that are simultaneously $\psi$ -approximable. A planar curve is called of Khintchine type for divergence if almost all points on it belong to $S(\psi)$ whenever $\sum\limits_{n=1}^\infty \psi(n)^2 = \infty$ . It is called of Khintchine type for convergence if almost all points on it does not belong to $S(\psi)$ whenever $\sum\limits_{n=1}^\infty \psi(n)^2 < \infty$ . The Theorem proves that all smooth nondegenerate planar curves are of Khintchine type for convergence, complementing an earlier result that they are of Khintchine type for divergence.

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

Go to the list of all theorems

For large n, if set I of n-element permutations is k-intersecting, then its size is at most (n-k)!

You need to know: Notation $n!$ for $1 \cdot 2 \cdot \dots \cdot n$ , notation $|I|$ for the number of elements in finite set I, notation $[n]$ for the set $\{1,2,\dots,n\}$ .

Background: A permutation of $[n]$ is a function $\sigma:[n] \to [n]$ such that $\sigma(i) \neq \sigma(j)$ if $i\neq j$ . Let $S_n$ be the set of all permutations of $[n]$ . We say that two permutations $\sigma, \tau \in S_n$ k-intersect if there exist distinct $i_1, i_2,\dots i_k \in [n]$ such that $\sigma(i_t) = \tau (i_t)$ for $t = 1, 2,\dots,k$ . A subset $I \subset S_n$ is said to be k-intersecting if any two permutations in I k-intersect.

The Theorem: On 9th March 2009, David Ellis, Ehud Friedgut, and Haran Pilpel submitted to the Journal of the AMS a paper in which they proved that for any positive integer k, and any n sufficiently large depending on k, if $I \subset S_n$ is k-intersecting, then $|I| \leq (n-k)!$ .

Short context: Let us fix $\sigma \in S_n$ , fix $i_1, i_2,\dots i_k \in [n]$ , and let I be the set of all $\tau \in S_n$ such that $\sigma(i_t) = \tau (i_t)$ for $t = 1, 2,\dots,k$ . Then I is k-intersecting and $|I|=(n-k)!$ . If $n\leq 2k$ , we can construct large k-intersecting sets. However, the theorem states that if n sufficiently large depending on k, the construction above is optimal. The authors also proved that equality $|I|=(n-k)!$ holds only for the construction described above. This confirms conjecture of Frankl and Deza made in 1977.

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

Go to the list of all theorems

An explicit construction of a 2^((log n)^o(1))-Ramsey graph over n vertices

You need to know: Graph, clique, independent set, small o notation, polynomial time algorithm.

Background: A graph on n vertices is called a k-Ramsey graph if it contains no clique or independent set of size k. By an explicit construction of a k-Ramsey graph we mean a polynomial time algorithm that, given the labels of two vertices in the graph, determines whether there is an edge between them. For n-vertex graph, the input of such algorithm has $2\log n$ bits, hence the running time should be polynomial in $\log n$ .

The Theorem: On 4th March 2009, Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson submitted to the Annals of Mathematics a paper in which they proved the existence of absolute constants $\epsilon>0$ and $n_0$ such that there is an explicit construction of a $2^{2^{{(\log \log n)}^{1-\epsilon}}}$ -Ramsey graph over $n$ vertices for every integer $n>n_0$ .

Short context: In 1947 Erdős used the probabilistic method to show that most graphs on $n$ vertices are $(2+o(1))\log n$ -Ramsey. Interestingly, there is no known explicit example of such a graph for large n. Before 2009, the best explicit construction was achieved in 1981 by Frankl and Wilson, who constructed k-Ramsey $2^n$ -vertex graphs for $k \approx 2^{\sqrt{\log n}}$ . Because $2^{2^{{(\log \log n)}^{1-\epsilon}}}=2^{(\log n)^{o(1)}}$ , the Theorem significantly improves this result. In a later work, Cohen presented an even better $2^{(\log \log n)^c}$ -Ramsey construction.

Links: The original paper is available here.

Go to the list of all theorems

The Bennett–Carbery–Tao multilinear Kakeya conjecture is true

You need to know: Euclidean space ${\mathbb R}^n$ , lines in ${\mathbb R}^n$ , volume $\text{Vol}(S)$ of $S\subset {\mathbb R}^n$ . In addition, you need the concept of Hausdorff dimension of subsets of ${\mathbb R}^n$ for the context section.

Background: A cylinder of radius R around a line $L \subset {\mathbb R}^n$ is the set of all points $x \in {\mathbb R}^n$ within a distance R of the line L. The line L is called the core of the cylinder. Suppose that we have a finite collection of cylinders $T_{j,a}\subset{\mathbb R}^n$ , where $1 \leq j \leq n$ , and $1\leq a \leq A$ for some integer A. Each cylinder $T_{j,a}$ has radius 1 and the angle between the core of $T_{j,a}$ and the $x_j$ -axis is at most $(100n)^{-1}$ . Let $I=\bigcap\limits_{j=1}^{n}\bigcup\limits_{a=1}^{A}T_{j,a}$ be the set of points that belong to at least one cylinder in each direction.

The Theorem: On 14th November 2008, Larry Guth submitted to arxiv a paper in which he proved that for each dimension n there is a constant $C=C(n)$ such that $\text{Vol}(I) \leq CA^{n/(n-1)}$ for any collection of cylinders as above.

Short context: Famous Kakeya conjecture states that every compact set $K \subset {\mathbb R}^n$ , which contains a line segment of unit length in every direction, must have Hausdorff dimension equal to n. This conjecture is important but difficult, and researchers study various “easier” versions first. In 1999, Wolff suggested to study its finite field analogue, which is then proved by Dvir, see here. In 2006, Bennett, Carbery, and Tao formulated “mutlilinear” analogue of the Kakeya conjecture, which says that cylinders pointing in different directions cannot overlap too much. The Theorem (more exactly, its generalisation proved by Guth in the same paper) finishes the proof of this conjecture.

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

Go to the list of all theorems

Any bounded Apollonian circle packing has asymptotically cT^a circles of radius at least 1/T

You need to know: Circles in the plane, radius of a circle, tangent circles, point of tangency, notation $f(T) \sim g(T)$ if $\lim\limits_{T\to\infty}\frac{f(T)}{g(T)}=1$ .

Background: A set of four mutually tangent circles in the plane with distinct points of tangency is called a Descartes configuration. Given a Descartes configuration, one
can construct four new circles, each of which is tangent to three of the given ones.
Continuing to repeatedly fill the interstices between mutually tangent circles with
further tangent circles, we arrive at an infinite circle packing. It is called a bounded Apollonian circle packing. Given a bounded Apollonian circle packing ${\cal P}$ and number $T>0$ , let $N^{\cal P}(T)$ be the number of circles in ${\cal P}$ of radius at least $\frac{1}{T}$ .

The Theorem: On 14th November 2008, Alex Kontorovich and Hee Oh submitted to arxiv a paper in which they proved that for every bounded Apollonian circle packing ${\cal P}$ there exists a constant $c=c({\cal P})>0$ such that $N^{\cal P}(T) \sim c\cdot T^\alpha$ as $T\to\infty$ , where $\alpha=1.30568...$ is an absolute constant.

Short context: Apollonian circle packing is named after Apollonius of Perga, who lived more than 2000 years ago, and is studied by many researchers since that. One of the central research direction in this area is to count circles in the packing with radius bounded from below. In 1982, Boyd showed, confirming Wilker’s prediction, that $\lim\limits_{T\to\infty}\frac{\log N^{\cal P}(T)}{\log T}=\alpha$ , where $\alpha=1.30568...$ is a constant independent of ${\cal P}$ . The Theorem establishes the exact asymptotic grow of $N^{\cal P}(T)$ .

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

Go to the list of all theorems

The threshold for making squares is sharp up to a factor of 4/pi

You need to know: Perfect square, limits, notation P for the probability, independent events, selection uniformly at random.

Background: We say that a finite sequence S of positive integers has a square dependence if it has a subset $A\subset S$ such that the product $\prod\limits_{n\in A}n$ of all integers in A is a perfect square. For $x>1$ , let us select integers $a_1,a_2,\dots$ independently uniformly at random from $[1,x]$ , and let T be the smallest integer such that the sequence $a_1,a_2,\dots, a_T$ has a square dependence.

The Euler-Mascheroni constant is the limit $\gamma=\lim\limits_{n\to\infty}\left(-\log n+\sum\limits_{k=1}^n\frac{1}{k}\right) = 0.577...$ . Integer n is called y-smooth if all of its prime factors are at most y. Let $\Psi(x,y)$ be the number of y-smooth integers up to x, $\pi(y)$ be the number of primes up to y, and let $J(x) = \min\limits_{2\leq y \leq x} \frac{\pi(y)x}{\Psi(x, y)}$ .

The Theorem: On 3rd November 2008, Ernie Croot, Andrew Granville, Robin Pemantle, and Prasad Tetali submitted to arxiv a paper in which they proved that for any $\epsilon>0$ , $\lim\limits_{x\to\infty} P\left(\frac{\pi}{4}(e^{-\gamma}-\epsilon)J(x) \leq T \leq (e^{-\gamma}+\epsilon)J(x)\right) = 1$ , where $\gamma$ is the Euler-Mascheroni constant.

Short context: How many random integers between 1 and x we should select such that the product of some selected integers is a perfect square? This question is important for understanding the performance of fastest known factorisation algorithms. In 1994, Pomerance conjectured that the number T of integers needed for this exhibits a sharp threshold, that is, $\lim\limits_{x\to\infty} P\left((1-\epsilon)f(x) \leq T \leq (1+\epsilon)f(x)\right) = 1$ for some function $f(x)$ and any $\epsilon>0$ . The authors of the Theorem further conjectured that this holds with $f(x)=e^{-\gamma}J(x)$ . The Theorem proves the upper bound exactly, and the lower bound up to the constant $\frac{\pi}{4}$ .

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

Go to the list of all theorems

The inhomogeneous uniform Littlewood’s conjecture is true for almost any pair of real numbers

You need to know: Notation $|n|$ for the absolute value of $n$ , limit inferior $\liminf$ , the notion of (Lebesgue) “almost any”.

Background: For real number $x\in{\mathbb R}$ , let $||x||$ denotes the distance from x to the nearest integer.

The Theorem: On 14th October 2008, Uri Shapira submitted to the Annals of Mathematics a paper in which he proved that for almost any pair of real numbers $\alpha,\beta \in {\mathbb R}$ , and for all $\gamma,\delta \in {\mathbb R}$ , $\liminf\limits_{|n|\to\infty}|n|\,\,||n\alpha-\gamma||\,\,||n\beta-\delta||=0$ .

Short context: In the 1930s Littlewood conjectured that for any two real numbers $\alpha$ and $\beta$ , $\liminf\limits_{n\to\infty} n ||n\alpha|| ||n\beta|| = 0$ . This remains open, but it follows from 1909 Borel theorem that the conjecture is true for (Lebesgue) almost any pair of $\alpha,\beta \in {\mathbb R}$ (see here for a stronger result). This corresponds to the special case $\gamma=\delta=0$ of the Theorem. The statement $\forall \gamma,\delta \in {\mathbb R}, \liminf\limits_{|n|\to\infty}|n|\,\,||n\alpha-\gamma||\,\,||n\beta-\delta||=0$ can therefore be called an inhomogeneous uniform version of the Littlewood’s conjecture. Before 2008, it was not know to hold even for a single pair of $\alpha,\beta$ . The Theorem proves it for almost any pair.

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

Go to the list of all theorems

The hypergraph Ramsey numbers r_3(s,n) are at most 2^(n^(s-2) log n)

You need to know: Factorial $n!=1\cdot 2 \cdot \dots \cdot n$ , logarithm $\log$ , limit, $o(1)$ notation.

Background: The hypergraph Ramsey number $r_k(s, n)$ is the minimum N such that every red-blue colouring of the unordered k-tuples of an N-element set contains a red set of size s or a blue set of size n, where a set is called red (blue) if all k-tuples from this set are red (blue).

The Theorem: On 27th August 2008, David Conlon, Jacob Fox, and Benny Sudakov submitted to arxiv a paper in which they proved that (i) for fixed $s \geq 4$ and sufficiently large n, $\log r_3(s,n) \leq \left(\frac{s-3}{(s-2)!}+o(1)\right)n^{s-2}\log n$ , and (ii) there is a constant $c>0$ such that $\log r_3(s,n) \geq c s n \log \left(\frac{n}{s}+1\right)$ for all $4 \leq s \leq n$ .

Short context: It follows from famous 1929 Ramsey Theorem that numbers $r_k(s, n)$ exists and finite, and, since that, finding upper and lower bounds for them is an active area of research in combinatorics, see here for a progress in case $k=2$ , $s=n$ . For the upper bound, Erdős and Rado proved in 1952 that $\log r_3(s,n)$ is at most $c n^{2s-4}/\log^{2s-6}n$ . Part (i) of the Theorem improves this by factor $n^{s-2}$ , ignoring $\log n$ factors. For the lower bound, Erdős and Hajnal showed in 1972 that $\log r_3(4, n) > c n$ for some $c>0$ , and conjectured that in fact $\lim\limits_{n\to\infty}\frac{r_3(4, n)}{n}=\infty$ . Part (ii) of 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

The circular law conjecture is true

You need to know: Notation $|S|$ for the number of elements in finite set S, set ${\mathbb C}$ of complex numbers, real part $Re(z)$ and imaginary part $Im(z)$ of a complex number z, compact subsets of ${\mathbb C}$ , compactly supported function $f:{\mathbb C}\to{\mathbb R}$ , matrix with complex entries, eigenvalue of a square matrix, basic probability theory, independent identically distributed (i.i.d.) complex random variables, mean, variance, probability measure $\mu$ on ${\mathbb C}$ , integration $\int_{\mathbb C}f(z) d\mu$ , uniform distribution on the unit disk in ${\mathbb C}$ .

Background: Given an $n \times n$ matrix A, let $\mu_A(x,y) := \frac{1}{n}|\{1 \leq i \leq n, \, Re(\lambda_i) \leq x, \, Im(\lambda_i) \leq y\}|$ be the empirical spectral distribution (ESD) of its eigenvalues $\lambda_i \in {\mathbb C}$ , $i = 1,\dots,n$ . We interpret $\mu_A$ as a discrete probability measure on ${\mathbb C}$ . Let $A_n$ be a sequence of random matrices. For a probability measure $\mu_\infty$ on ${\mathbb C}$ , and continuous compactly supported function $f:{\mathbb C}\to{\mathbb R}$ , let $\Delta(\mu_\infty, f, n)=\int_{\mathbb C}f(z) d\mu_{1/\sqrt{n}A_n}(z) - \int_{\mathbb C}f(z) d\mu_\infty$ . We say that the ESD of $\frac{1}{\sqrt{n}}A_n$ converges in probability to $\mu_\infty$ if $\lim\limits_{n\to\infty}P\left(|\Delta(\mu_\infty, f, n)|\geq\epsilon\right)=0$ for every f and for every $\epsilon>0$ . Also, we say that ESD of $\frac{1}{\sqrt{n}}A_n$ converges to $\mu_\infty$ almost surely, if, with probability $1$ , $\Delta(\mu_\infty, f, n)$ converges to zero for all f.

The Theorem: On 30th July 2008, Terence Tao, Van Vu submitted to arxiv a paper in which they proved the following result. Let $A_n$ be the $n \times n$ random matrix whose entries are i.i.d. complex random variables with mean zero and variance one. Then, the ESD of $\frac{1}{\sqrt{n}}A_n$ converges (both in probability and in the almost sure sense) to the uniform distribution on the unit disk.

Short context: The statement of the Theorem was known as the circular law conjecture before 2010, and now is called the circular law. It was first established by Ginibre in 1965 for random matrices with Gaussian distribution of entries. Then many authors proved it for more and more general distributions, culminating in the Theorem that establishes it in the general case.

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

Go to the list of all theorems