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

[math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math]