Corners theorem: Difference between revisions
added link to DHJ(1,3) page |
No edit summary |
||
| Line 1: | Line 1: | ||
'''Corners theorem''': (<math>{\Bbb Z}/N{\Bbb Z}</math> version) If N is sufficiently large depending on <math>\delta</math>, then any subset | '''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 > 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 subset | '''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-Szemerédi's proof of the corners theorem|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)]]. | This result was first proven by [[Ajtai-Szemerédi's proof of the corners theorem|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)]]. | ||
Revision as of 19:52, 8 May 2009
Corners theorem: ([math]\displaystyle{ {\Bbb Z}/N{\Bbb Z} }[/math] version) If N is sufficiently large depending on [math]\displaystyle{ \delta }[/math], then any [math]\displaystyle{ \delta }[/math]-dense subset of [math]\displaystyle{ {}[N]^2 }[/math] must contain a "corner" (x,y), (x+r,y), (x,y+r) with [math]\displaystyle{ r \gt 0 }[/math].
Corners theorem: ([math]\displaystyle{ ({\Bbb Z}/3{\Bbb Z})^n }[/math] version) If n is sufficiently large depending on [math]\displaystyle{ \delta }[/math], then any [math]\displaystyle{ \delta }[/math]-dense subset of [math]\displaystyle{ {}(({\Bbb Z}/3{\Bbb Z})^n)^2 }[/math] must contain a "corner" (x,y), (x+r,y), (x,y+r) with [math]\displaystyle{ 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]\displaystyle{ \Delta_n = \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n\} }[/math]
of density at least [math]\displaystyle{ \delta }[/math] will contain an equilateral triangle [math]\displaystyle{ (a+r,b,c),(a,b+r,c),(a,b,c+r) }[/math] with [math]\displaystyle{ r\gt 0 }[/math], if n is sufficiently large depending on [math]\displaystyle{ \delta }[/math].
A special case of the corners theorem is of interest in connection with DJH(1,3).
