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 large grids. 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.

Remark

This proof is clearly very similar to the proof of Ajtai and Szemerédi. However, it is not quite identical, because we take correlation with a 12-set as our starting point. This streamlines the argument considerably, because it is not necessary to keep track of the density of A inside grids: we just have to partition the 12-set into large grids and an averaging argument at the end finishes things off. (Note that in the above proof we did not have a lemma that said that if A often has reduced density in certain subsets then it must sometimes have increased density: all that was contained in the final trivial averaging argument.)

Aside from this simplification, the main motivation for this argument is that it is now in a form that is much more easily transferable to DHJ(3). See this page for details.