View source for 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 [[Ajtai-Szemer&eacute;di's_proof_of_the_corners_theorem|proof of Ajtai and Szemer&eacute;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&eacute;di)  For every <math>\delta>0</math> there exists n such that every subset A of <math>[n]^2</math> of size at least <math>\delta n^2</math> contains a triple of points <math>(x,y),(x+d,y),(x,y+d)</math> with <math>d>0.</math>

==Notation and terminology==

A [[corner]] is a subset of <math>[n]^2</math> of the form <math>\{(x,y),(x+d,y),(x,y+d)\}</math> with <math>d>0.</math> A ''corner-free'' subset of <math>[n]^2</math> is a subset that contains no corners. A ''grid'' is a subset of <math>[n]^2</math> of the form <math>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>\{(x,y):x+y=t\}</math> for some t.

A ''1-set'' is a subset of <math>[n]^2</math> of the form <math>X\times [n].</math> A ''2-set'' is a set of the form <math>[n]\times Y.</math> A ''12-set'' is a set of the form <math>X\times Y.</math> The 12-set <math>X\times Y</math> is the intersection of the 1-set <math>X\times[n]</math>with the 2-set <math>[n]\times Y.</math> These definitions localize to grids in an obvious way: for example, a ''1-subset'' of the grid <math>P\times Q</math> is a set of the form <math>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>\log\log\log\log\log\log n,</math> then <math>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>[n]^2,</math>, then we shall refer to the number <math>|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>|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>\delta n^2,</math> then there must be a diagonal  that contains at least <math>\delta n/2</math> points of A, and inside this diagonal A must have density at least <math>\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>\{(x,y):x+y=t\}</math> has density at least <math>\delta/2.</math> Enumerate the points of this diagonal as <math>(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>X=\{x_1,\dots,x_m\}</math> and let <math>Y=\{y_{m+1},\dots,y_{2m}\}.</math> If <math>(x_i,y_j)\in A</math> for some <math>i<j,</math> then the three points <math>(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>t-x_i-y_j,</math> which is greater than zero because <math>y_j<y_i=t-x_i.)</math> Therefore the set <math>X\times Y,</math> which has density at least <math>\delta^2/16</math> in <math>[n]^2,</math> is disjoint from A.

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

Now partition <math>[n]^2</math> into the four sets <math>X\times Y, X\times Y^c, X^c\times Y</math> and <math>X^c\times Y^c.</math> Let f be the balanced function of A. (That is, <math>f(x,y)=1-\delta</math> when <math>(x,y)\in A</math> and <math>-\delta</math> otherwise.) Then <math>\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>\delta^3n^2/48.</math> This gives us a 12-set <math>U\times V</math> such that the density of A inside <math>U\times V</math> is at least <math>\delta+\delta^3/48.</math> And trivially the set must have density at least <math>\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>X\times[n]</math> be a dense 1-set. By Szemer&eacute;di's theorem we can find a long arithmetic progression <math>P_1</math> inside X, then a long arithmetic progression <math>P_2</math> inside <math>X\setminus P_1,</math> and so on. We can continue this process until what is left of X has density at most <math>\eta.</math> This partitions almost all of X into sets of the form <math>P_i\times[n].</math> If we have also ensured that the widths of these progressions <math>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>[n]</math> into translates <math>Q_{i1},\dots,Q_{ir_i}</math> of <math>P_i.</math> And then the sets <math>P_i\times Q_{ij}</math> partition almost all of <math>X\times[n].</math>

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

Let <math>X\times Y</math> be a dense 12-set. Use the previous step to partition almost all of <math>X\times[n]</math> into large grids. Throw away any of these grids<math>P\times Q</math> if Y has very small density inside <math>Q:</math> the total number of points of <math>[n]\times Y</math> in the discarded grids is a very small fraction of <math>n^2.</math> For all the remaining grids  <math>P\times Q,</math> <math>P\times(Y\cap Q)</math> is a dense 2-subset of <math>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>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>\delta.</math> By Step 3 we can find a dense 12-set <math>X\times Y</math> inside which A has density at least <math>\delta+c\delta^3.</math> By Step 5, we can partition almost all of <math>X\times Y</math> into large grids. Therefore, by averaging we have a large grid inside which the density is at least <math>\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&eacute;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 [[A_second_outline_of_a_density-increment_argument|this page]] for details.