# Modification of the Ajtai-Szemerédi argument

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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 $\delta\gt0$ there exists n such that every subset A of $[n]^2$ of size at least $\delta n^2$ contains a triple of points $(x,y),(x+d,y),(x,y+d)$ with $d\gt0.$

## Notation and terminology

A corner is a subset of $[n]^2$ of the form $\{(x,y),(x+d,y),(x,y+d)\}$ with $d\gt0.$ A corner-free subset of $[n]^2$ is a subset that contains no corners. A grid is a subset of $[n]^2$ of the form $P\times Q$ 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]^2$ of the form $X\times [n].$ A 2-set is a set of the form $[n]\times Y.$ A 12-set is a set of the form $X\times Y.$ The 12-set $X\times Y$ is the intersection of the 1-set $X\times[n]$with the 2-set $[n]\times Y.$ These definitions localize to grids in an obvious way: for example, a 1-subset of the grid $P\times Q$ is a set of the form $R\times Q$ 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 $\log\log\log\log\log\log n,$ then $P\times Q$ 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]^2,$, then we shall refer to the number $|A\cap X|/|X|$ 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^2.$

## 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 $\delta n^2,$ then there must be a diagonal that contains at least $\delta n/2$ points of A, and inside this diagonal A must have density at least $\delta/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 $\delta/2.$ Enumerate the points of this diagonal as $(x_1,y_1),\dots,(x_{2m},y_{2m}),$ in increasing order of x. (If there are an odd number, then remove one.) Let $X=\{x_1,\dots,x_m\}$ and let $Y=\{y_{m+1},\dots,y_{2m}\}.$ If $(x_i,y_j)\in A$ for some $i\ltj,$ 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\lty_i=t-x_i.)$ Therefore the set $X\times Y,$ which has density at least $\delta^2/16$ in $[n]^2,$ is disjoint from A.

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

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

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

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