# Modification of the Ajtai-Szemerédi argument

## 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 [math]\delta\gt0[/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\gt0.[/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\gt0.[/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\ltj,[/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\lty_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é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é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.