Modification of the Ajtai-Szemerédi argument

From Polymath1Wiki

Contents 1 Introduction 2 Notation and terminology 3 The proof 3.1 Step 1: finding a dense diagonal 3.2 Step 2: a dense 12-set disjoint from A 3.3 Step 3: a dense 12-set that correlates with A 3.4 Step 4: a dense 1-set can be almost entirely partitioned into large grids 3.5 Step 5: a dense 12-set can be almost entirely partitioned into large grids 3.6 Step 6: obtaining a density increment on a large grid 4 Remark

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 δ > 0 there exists n such that every subset A of [n]² of size at least δn² contains a triple of points (x,y),(x + d,y),(x,y + d) with d > 0.

Notation and terminology

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

A 1-set is a subset of [n]² of the form A 2-set is a set of the form A 12-set is a set of the form The 12-set is the intersection of the 1-set with the 2-set These definitions localize to grids in an obvious way: for example, a 1-subset of the grid is a set of the form 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 loglogloglogloglogn, then 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 [n]²,, then we shall refer to the number 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 | X | / n².

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 δn², then there must be a diagonal that contains at least δn / 2 points of A, and inside this diagonal A must have density at least δ / 2.

Step 2: a dense 12-set disjoint from A

Pick a dense diagonal. That is, pick t such that the set {(x,y):x + y = t} has density at least δ / 2. Enumerate the points of this diagonal as in increasing order of x. (If there are an odd number, then remove one.) Let and let If for some i < j, then the three points (x_i,y_j),(x_i,t − x_i),(t − y_j,y_j) form a corner. (The d in this corner is t − x_i − y_j, which is greater than zero because y_j < y_i = t − x_i.) Therefore the set which has density at least δ² / 16 in [n]², is disjoint from A.

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

Now partition [n]² into the four sets and Let f be the balanced function of A. (That is, f(x,y) = 1 − δ when and − δ otherwise.) Then so on one of the other three sets the sum must be at least δ³n² / 48. This gives us a 12-set such that the density of A inside is at least δ + δ³ / 48. And trivially the set must have density at least δ³ / 48 (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 be a dense 1-set. By Szemerédi's theorem we can find a long arithmetic progression P₁ inside X, then a long arithmetic progression P₂ inside and so on. We can continue this process until what is left of X has density at most η. This partitions almost all of X into sets of the form If we have also ensured that the widths of these progressions P_i 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 [n] into translates of P_i. And then the sets partition almost all of

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

Let be a dense 12-set. Use the previous step to partition almost all of into large grids. Throw away any of these grids if Y has very small density inside Q: the total number of points of in the discarded grids is a very small fraction of n². For all the remaining grids is a dense 2-subset of and hence, by the previous step, can be almost entirely partitioned into large grids. The result is a partition of almost all of 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 δ. By Step 3 we can find a dense 12-set inside which A has density at least δ + cδ³. By Step 5, we can partition almost all of into large grids. Therefore, by averaging we have a large grid inside which the density is at least δ + cδ³ / 2. 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.