Hales-Jewett theorem

We consider some classical theorems in arithmetic Ramsey theory, where one wants to find some monochromatic arithmetic structure (an arithmetic progression, for example) when a large set of integers or lattice points in $\mathbb{Z}^d$ is colored with several colors. Many such results follow from the Hales-Jewett theorem from 1963, stating that given any $k$ and $r$, there is a dimension $N$ such that when the lattice points of a cube of side length $k$ and dimension $N$ are colored with $r$ colors, there is a monochromatic combinatorial line. A combinatorial line is a line of length $k$ which is constant in some coordinates and increases with slope $1$ in the others.

We will prove the Hales-Jewett theorem, as its corollary the van der Waerden theorem, and a generalization of the latter, the Gallai-Witt theorem. The van der Waerden theorem from 1927 states that, given $k$ and $r$, there is $N$ such that if $\{1,2,...,N\}$ is colored with $r$ colors, there is a monochromatic arithmetic progression of length $k$. The smallest such $N$ is the van der Waerden number $W(k,r)$, and although they seem to grow fairly rapidly, the bounds given by the traditional double induction proofs are unimaginably large compared to what is expected. However, in 1988, Shelah found a one variable induction proof of the Hales-Jewett theorem in Primitive Recursive Bounds for Van Der Waerden Numbers, and this implied a bound that is still large but nothing compared to the previous bounds, which were functions that grow faster than any function defined by primitive recursion. We present in this post a proof of the Hales-Jewett theorem similar to Shelah's proof, and consider its consequences to the van der Waerden theorem and related results.

Geometric problems in Ramsey theory

In the previous post, we considered Ramsey theory for graphs. Graphs are however not the only combinatorial structures that are guaranteed to contain some regularity; another important example are sets of points in the plane or in a general Euclidean space. There are numerous theorems at the intersection of geometry and Ramsey theory, stating that such sets of points, whenever they are large enough, contain some geometrical structure. As examples of such results we consider the Erdös problem on the minimum number of distinct distances between $n$ points in the plane and the Hadwiger-Nelson problem on finding two points of the same color at unit distance when all points in $\mathbb{R}^2$ are colored with $k$ colors. We also give a more geometrical solution of the Happy Ending problem, which gives essentially the best known upper and lower bounds (the graph theoretic solution from the previous post gives very poor bounds).

Ramsey's theorem

Ramsey theory is a branch of combinatorics in which theorems typically state that any sufficiently large structure (e.g. a graph, a set of integers or a set of points in the plane) contains some large substructure (e.g. a complete graph, an arithmetic progression or a convex polygon). The starting point for this theory is Ramsey's theorem from 1930, stating that if the edges of a large enough graph are colored red and blue, there is a red clique of size $k$ or a blue clique of size $\ell$. The smallest size of a graph that guarantees this is the Ramsey number $R(k,\ell)$. The finiteness of the Ramsey numbers can be proved in an elementary way, but it is curious that the bounds given by simple arguments are almost the best that are known, despite that the upper and lower bounds are far from each other.

We will prove Ramsey's theorem, including its generalizations for multicolored graphs and hypergraphs. As corollaries we will prove Schur's theorem on the solvability of Fermat's equation $x^n+y^n=z^n, xyz\neq 0$ modulo any number, and the Happy Ending problem on finding convex polygons in an arbitrary set of points. We will also derive a lower bound due to Erdös for the Ramsey numbers. The bound is based on Erdös' probabilistic method, which has proved to be a very fruitful tool in combinatorics despite its simplicity. It is quite remarkable that the lower bound from 1947 that we are going to prove is the best one known up to a constant factor. Furthermore, so far all lower bounds that do not appeal to the probabilistic method (in particular constructive bounds) are considerably weaker than the probabilistic bound -- they do not even grow exponentially.

A refined Brun sieve

We improve the Brun sieve from the previous post to allow us to consider almost primes of various forms. We will prove for example the result that there are infinitely many $n$ such that $n$ and $n+2$ both have at most $7$ prime factors, and that every large enough even integer is the sum of two numbers both having at most $7$ prime factors.

Roth's theorem on arithmetic progressions

In this post, we give an application of Fourier analysis to combinatorics, more precisely to Ramsey theory. In Ramsey theory, a typical result tells that certain large but otherwise arbitrary objects (sets of integers, graphs, collections of points, etc.) are forced to contain some structure in them, thus implying intuitively that there is no complete randomness. The desired structure in these objects could mean for example large cliques or independent sets of vertices in the case of graphs, or some arithmetic structure in the case of sets of integers. One of the most basic arithmetic structures is of course an arithmetic progression, and there are several Ramsey theoretic results about their occurrence. We mention the following two theorems.

Theorem 1 (van der Waerden). Let $k$ and $\ell$ be positive integers. Then there exists a number $W(k,\ell)$ such that whenever the numbers in $\{1,2,...,N\}$ with $N\geq W(k,\ell)$ are colored using $\ell$ colors, there is a monochromatic arithmetic progression of length $k$ .

Theorem 2 (Szemerédi). Let $\delta>0$, and let $k$ be a positive integer. Then, if $A$ is any subset of $\{1,2,...,N\}$ with $N\geq N(k,\delta)$ and having density at least $\delta$ (that is, $|A|\geq \delta N$), the set $A$ contains an arithmetic progression of length $k$.

The first result was proved by van der Waerden in 1927 (back then, the result was an open problem that many famous mathematicians attempted to resolve, but it was the young van der Waerden who solved it). The latter result is a very deep and important result of Szemerédi from 1975 (the proof was so complicated that Szemerédi refused to write it down himself). Szemerédi's proof was based on his graph regularity lemma, and virtually every proof of the theorem has started a fruitful new research direction. For instance, Furstenberg proved the theorem using ergodic theory in 1977, and Gowers using Fourier analytic methods and his uniformity norms in 2001, and the latter proof also improved bounds on $W(k,\ell)$ enormously.

It is easy to see that van der Waerden's theorem is a special case of Szemerédi's; indeed, if $\{1,2,...,N\}$ is colored with $\ell$ colors, there is at least one monochromatic subset of density at least $\frac{1}{\ell}$. In addition, both theorems allow immediately an infinite version. For Szemerédi's theorem, the infinite version is that any subset of the natural numbers with a positive lower density contains arbitrarily long arithmetic progressions. In fact, there is a nice compactness argument that can be used to deduce the finite versions of the theorems from their infinite versions, but that is a different story.

We will not try to prove Szemerédi's theorem in this post, but we will prove its special case $k=3$ due to Roth from 1953. This case is an elegant and relatively short application of Fourier analysis into combinatorics. For convenience, we also formulate this claim.