Ajtai-Szemerédi's proof of the corners theorem

Introduction

Ajtai and Szemerédi proved the corners theorem with a clever use of three basic principles: the density-increment strategy, which allowed them to assume that the set A was of density almost [math]\displaystyle{ \delta }[/math] in almost all subgrids; averaging arguments, which implied that any dense structured set in which A was sparse must be compensated for by a structured set in which it was of increased density, and Szemerédi's theorem, which allowed them to pass from dense subsets of [n] to long arithmetic progressions. Their original paper does not seem to be available online, but here you can find a quantitative version of their argument due to Van Vu. On this page, we give a detailed sketch of the argument: the aim is to present the key ideas in enough detail that the reader who wishes to can go away and make it fully precise.

Statement of the theorem and some basic definitions

For every [math]\displaystyle{ \delta\gt 0 }[/math] there exists n such that every subset [math]\displaystyle{ A\subset [n]^2 }[/math] of density at least [math]\displaystyle{ \delta }[/math] (i.e., of cardinality at least [math]\displaystyle{ \delta n^2 }[/math]) contains three points of the form (x,y), (x+d,y) and (x,y+d) with [math]\displaystyle{ d\gt 0. }[/math]

Definition. A grid of side m is a Cartesian product [math]\displaystyle{ P\times Q, }[/math] where P and Q are arithmetic progressions of length m with the same common difference.

First step: A is dense on almost all grids

This is a very standard move in density-increment arguments. We are trying to do an iteration in which we pass to a subgrid where A has increased density. Suppose we aim for a density increase from [math]\displaystyle{ \delta }[/math] to [math]\displaystyle{ \delta+\eta. }[/math] Then if we find a subgrid (of width tending to infinity with n) where the density is at least [math]\displaystyle{ \delta+\eta }[/math] then we have our density increase, obviously enough. But if we do not have such a subgrid, then we can argue as follows. Pick a random point in [math]\displaystyle{ [n]^2 }[/math] by first picking a random grid of width m, and then picking a random point in that grid. If m is small enough, then it is easy to argue that the distribution of the resulting point is approximately uniform, from which it follows that the average density in a random subgrid is approximately [math]\displaystyle{ \delta. }[/math] But if the average density in a subgrid is approximately [math]\displaystyle{ \delta }[/math] and the maximum density is at most [math]\displaystyle{ \delta+\eta, }[/math] then there can be only a small proportion of subgrids inside which A has density substantially smaller than [math]\displaystyle{ \delta. }[/math] (Roughly, the proportion where the density is less than [math]\displaystyle{ \delta-\mu }[/math] is at most [math]\displaystyle{ \eta/\mu, }[/math] by a simple averaging argument).

[math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math]

To be continued.

An old blog comment that used to be the main article

Ajtai and Szemerédi found a clever proof of the corners theorem that used Szemerédi’s theorem as a lemma. This gives us a direction to explore that we have hardly touched on. Very roughly, to prove the corners theorem you first use an averaging argument to find a dense diagonal (that is, subset of the form x+y=r that contains many points of your set A). For any two such points (x,r-x) and (y,r-y) you know that the point (x,r-y) does not lie in A (if A is corner free), which gives you some kind of non-quasirandomness. (The Cartesian semi-product arguments discussed in the 400s thread are very similar to this observation.) Indeed, it allows you to find a large Cartesian product [math]\displaystyle{ X\times Y }[/math] in which A is a bit too dense. In order to exploit this, Ajtai and Szemerédi used Szemerédi’s theorem to find long arithmetic progressions [math]\displaystyle{ P\subset X }[/math] and [math]\displaystyle{ Q\subset Y }[/math] of the same common difference such that A has a density increment in [math]\displaystyle{ P\times Q }[/math]. (I may have misremembered, but I think this must have been roughly what they did.) So we could think about what the analogue would be in the DHJ setting. Presumably it would be some kind of multidimensional Sperner statement of sufficient depth to imply Szemerédi’s theorem. A naive suggestion would be that in a dense subset of [math]\displaystyle{ [2]^n }[/math] you can find a large-dimensional combinatorial subspace in which all the variable sets have the same size. If you apply this to a union of layers, then you find an arithmetic progression of layer-cardinalities. But this feels rather artificial, so here’s a question we could think about.

Question 1. Can anyone think what the right common generalization of Szemerédi’s theorem and Sperner’s theorem ought to be? (Sperner’s theorem itself would correspond to the case of progressions of length 2.)