Modification of the Ajtai-Szemerédi argument

Introduction

This page is devoted to a detailed outline of a proof of the corners theorem. It is closely related to the proof of Ajtai and Szemerédi, but it is not quite identical. Their proof feels a bit like a clever trick: it is possible to regard this proof as an explanation of why theirs works. Here, for completeness, is a statement of the theorem.

Theorem. (Ajtai and Szemerédi) For every [math]\displaystyle{ \delta\gt 0 }[/math] there exists n such that every subset A of [math]\displaystyle{ [n]^2 }[/math] of size at least [math]\displaystyle{ \delta n^2 }[/math] contains a triple of points [math]\displaystyle{ (x,y),(x+d,y),(x,y+d) }[/math] with [math]\displaystyle{ d\gt 0. }[/math]

Notation and terminology

A corner is a subset of [math]\displaystyle{ [n]^2 }[/math] of the form [math]\displaystyle{ \{(x,y),(x+d,y),(x,y+d)\} }[/math] with [math]\displaystyle{ d\gt 0. }[/math] A corner-free subset of [math]\displaystyle{ [n]^2 }[/math] is a subset that contains no corners. A grid is a subset of [math]\displaystyle{ [n]^2 }[/math] of the form [math]\displaystyle{ P\times Q }[/math] where P and Q are arithmetic progressions with the same common difference. A diagonal is a set of the form [math]\displaystyle{ \{(x,y):x+y=t\} }[/math] for some t.

A 1-set is a subset of [math]\displaystyle{ [n]^2 }[/math] of the form [math]\displaystyle{ X\times [n]. }[/math] A 2-set is a set of the form [math]\displaystyle{ [n]\times Y. }[/math] A 12-set is a set of the form [math]\displaystyle{ X\times Y. }[/math] The 12-set [math]\displaystyle{ X\times Y }[/math] is the intersection of the 1-set [math]\displaystyle{ X\times[n] }[/math]with the 2-set [math]\displaystyle{ [n]\times Y. }[/math] These definitions localize to grids in an obvious way: for example, a 1-subset of the grid [math]\displaystyle{ P\times Q }[/math] is a set of the form [math]\displaystyle{ R\times Q }[/math] where R is a subset of P.

We shall use words like "long" and "large" to mean "of size that tends to infinity with n". For instance, if P and Q are arithmetic progressions with the same common difference and length [math]\displaystyle{ \log\log\log\log\log\log n, }[/math] then [math]\displaystyle{ P\times Q }[/math] is a large grid and P and Q are long arithmetic progressions. Also, if A is the set inside which we are trying to find a corner and X is some subset of [math]\displaystyle{ [n]^2, }[/math], then we shall refer to the number [math]\displaystyle{ |A\cap X|/|X| }[/math] both as the density of A inside X, and also as the density of X. We shall use the latter wording only when there is no question of our being interested in the number [math]\displaystyle{ |X|/n^2. }[/math]

The proof

Step 1: finding a dense diagonal

There are only 2n-1 diagonals, and each diagonal has length at most n. Therefore, if A has size [math]\displaystyle{ \delta n^2, }[/math] then there must be a diagonal that contains at least [math]\displaystyle{ \delta n/2 }[/math] points of A, and inside this diagonal A must have density at least [math]\displaystyle{ \delta/2. }[/math]

Step 2: a dense 12-set disjoint from A

Pick a dense diagonal. That is, pick t such that the set [math]\displaystyle{ \{(x,y):x+y=t\} }[/math] has density at least [math]\displaystyle{ \delta/2. }[/math] Enumerate the points of this diagonal as [math]\displaystyle{ (x_1,y_1),\dots,(x_{2m},y_{2m}), }[/math] in increasing order of x. (If there are an odd number, then remove one.) Let [math]\displaystyle{ X=\{x_1,\dots,x_m\} }[/math] and let [math]\displaystyle{ Y=\{y_{m+1},\dots,y_{2m}\}. }[/math] If [math]\displaystyle{ (x_i,y_j)\in A }[/math] for some [math]\displaystyle{ i\lt j, }[/math] then the three points [math]\displaystyle{ (x_i,y_j),(x_i,t-x_i),(t-y_j,y_j) }[/math] form a corner. (The d in this corner is [math]\displaystyle{ t-x_i-y_j, }[/math] which is greater than zero because [math]\displaystyle{ y_j\lt y_i=t-x_i.) }[/math] Therefore the set [math]\displaystyle{ X\times Y, }[/math] which has density at least [math]\displaystyle{ \delta^2/16 }[/math] in [math]\displaystyle{ [n]^2, }[/math] is disjoint from A.

Step 3: a dense 12-set that correlates with A

Now partition [math]\displaystyle{ [n]^2 }[/math] into the four sets [math]\displaystyle{ X\times Y, X\times Y^c, X^c\times Y }[/math] and [math]\displaystyle{ X^c\times Y^c. }[/math] Let f be the balanced function of A. (That is, [math]\displaystyle{ f(x,y)=1-\delta }[/math] when [math]\displaystyle{ (x,y)\in A }[/math] and [math]\displaystyle{ -\delta }[/math] otherwise.) Then [math]\displaystyle{ \sum_{(x,y)\in X\times Y}f(x,y)\leq-\delta^3n^2/16, }[/math] so on one of the other three sets the sum must be at least [math]\displaystyle{ \delta^3n^2/48. }[/math] This gives us a 12-set [math]\displaystyle{ U\times V }[/math] such that the density of A inside [math]\displaystyle{ U\times V }[/math] is at least [math]\displaystyle{ \delta+\delta^3/48. }[/math] And trivially the set must have density at least [math]\displaystyle{ \delta^3/48 }[/math] (though with a bit more effort one can do better than this).

Step 4: a dense 1-set can be almost entirely partitioned into large grids

Let [math]\displaystyle{ X\times[n] }[/math] be a dense 1-set. By Szemerédi's theorem we can find a long arithmetic progression [math]\displaystyle{ P_1 }[/math] inside X, then a long arithmetic progression [math]\displaystyle{ P_2 }[/math] inside [math]\displaystyle{ X\setminus P_1, }[/math] and so on. We can continue this process until what is left of X has density at most [math]\displaystyle{ \eta. }[/math] This partitions almost all of X into sets of the form [math]\displaystyle{ P_i\times[n]. }[/math] If we have also ensured that the widths of these progressions [math]\displaystyle{ P_i }[/math] are not too large (which is easy to do -- I am defining the width to be the difference between the maximal element and the minimal element), then for each i one can partition almost all of [math]\displaystyle{ [n] }[/math] into translates [math]\displaystyle{ Q_{i1},\dots,Q_{ir_i} }[/math] of [math]\displaystyle{ P_i. }[/math] And then the sets [math]\displaystyle{ P_i\times Q_{ij} }[/math] partition almost all of [math]\displaystyle{ X\times[n]. }[/math]

Step 5: a dense 12-set can be almost entirely partitioned into large grids

Let [math]\displaystyle{ X\times Y }[/math] be a dense 12-set. Use the previous step to partition almost all of [math]\displaystyle{ X\times[n] }[/math] into large grids. Throw away any of these grids[math]\displaystyle{ P\times Q }[/math] if Y has very small density inside [math]\displaystyle{ Q: }[/math] the total number of points of [math]\displaystyle{ [n]\times Y }[/math] in the discarded grids is a very small fraction of [math]\displaystyle{ n^2. }[/math] For all the remaining grids [math]\displaystyle{ P\times Q, }[/math] [math]\displaystyle{ P\times(Y\cap Q) }[/math] is a dense 2-subset of [math]\displaystyle{ P\times Q }[/math] and hence, by the previous step, can be almost entirely partitioned into large grids. The result is a partition of almost all of [math]\displaystyle{ X\times Y }[/math] into large grids.

Step 6: obtaining a density increment on a large grid

We are almost finished. Let A be a corner-free set of density [math]\displaystyle{ \delta. }[/math] By Step 3 we can find a dense 12-set [math]\displaystyle{ X\times Y }[/math] inside which A has density at least [math]\displaystyle{ \delta+c\delta^3. }[/math] By Step 5, we can partition almost all of [math]\displaystyle{ X\times Y }[/math] into [math]\displaystyle{ large grids. }[/math] Therefore, by averaging we have a large grid inside which the density is at least [math]\displaystyle{ \delta+c\delta^3/2. }[/math] That density increase allows us to iterate, so the corners theorem is proved.