Corners theorem

From Polymath1Wiki
Jump to: navigation, search

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

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

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

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

of density at least [math]\delta[/math] will contain an equilateral triangle [math](a+r,b,c),(a,b+r,c),(a,b,c+r)[/math] with [math]r\gt0[/math], if n is sufficiently large depending on [math]\delta[/math].

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