Corners theorem

From Polymath1Wiki

Jump to: navigation, search

Corners theorem: ({\Bbb Z}/N{\Bbb Z} version) If N is sufficiently large depending on δ, then any δ-dense subset of [N]2 must contain a "corner" (x,y), (x+r,y), (x,y+r) with r > 0.

Corners theorem: (({\Bbb Z}/3{\Bbb Z})^n version) If n is sufficiently large depending on δ, then any δ-dense subset of {}(({\Bbb Z}/3{\Bbb Z})^n)^2 must contain a "corner" (x,y), (x+r,y), (x,y+r) with r \neq 0.

This result was first proven by Ajtai and Szemerédi. A simpler proof, based on the triangle removal lemma, was obtained by Solymosi. The corners theorem implies Roth's theorem and is in turn implied by the IP-Szemerédi theorem, which in turn follows from DHJ(3).

One consequence of the corners theorem is that any subset of the triangular grid

\Delta_n = \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n\}

of density at least δ will contain an equilateral triangle (a + r,b,c),(a,b + r,c),(a,b,c + r) with r > 0, if n is sufficiently large depending on δ.

A special case of the corners theorem is of interest in connection with DHJ(1,3).

Personal tools