Roth's theorem: Difference between revisions
No edit summary |
No edit summary |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
'''Roth's theorem''' (<math>{\Bbb Z}/N{\Bbb Z}</math> version) If N is sufficiently large depending on <math>\delta > 0</math>, then any subset A of <math>[N]</math> of density at least <math>\delta</math> contains an arithmetic progression x, x+r, x+2r with <math>r > 0</math>. | '''Roth's theorem''' (<math>{\Bbb Z}/N{\Bbb Z}</math> version) If N is sufficiently large depending on <math>\delta > 0</math>, then any subset A of <math>[N]</math> of density at least <math>\delta</math> contains an arithmetic progression x, x+r, x+2r with <math>r > 0</math>. | ||
'''Roth | '''Roth-Meshulam theorem''' (<math>[3]^n</math> version) If n is sufficiently large depending on <math>\delta > 0</math>, then any subset of <math>[3]^n</math> of density at least <math>\delta</math> contains an [[algebraic line]], i.e. a triple (x,x+r,x+2r) where r is non-zero and we identify <math>[3]^n</math> with <math>({\Bbb Z}/3{\Bbb Z})^n</math>. | ||
Roth's theorem is a special case of [[Szemerédi's theorem]]. | Roth's theorem is a special case of [[Szemerédi's theorem]]. See also [[Szemerédi's combinatorial proof of Roth's theorem]]. | ||
Roth's theorem is implied by the [[corners theorem]], which in turn is implied by the k=3 case of the [[IP-Szemerédi theorem]], which is in turn implied by k=3 case of the [[density Hales-Jewett theorem]]. | Roth's theorem is implied by the [[corners theorem]], which in turn is implied by the k=3 case of the [[IP-Szemerédi theorem]], which is in turn implied by k=3 case of the [[density Hales-Jewett theorem]]. | ||
Latest revision as of 15:18, 19 March 2009
Roth's theorem ([math]\displaystyle{ {\Bbb Z}/N{\Bbb Z} }[/math] version) If N is sufficiently large depending on [math]\displaystyle{ \delta \gt 0 }[/math], then any subset A of [math]\displaystyle{ [N] }[/math] of density at least [math]\displaystyle{ \delta }[/math] contains an arithmetic progression x, x+r, x+2r with [math]\displaystyle{ r \gt 0 }[/math].
Roth-Meshulam theorem ([math]\displaystyle{ [3]^n }[/math] version) If n is sufficiently large depending on [math]\displaystyle{ \delta \gt 0 }[/math], then any subset of [math]\displaystyle{ [3]^n }[/math] of density at least [math]\displaystyle{ \delta }[/math] contains an algebraic line, i.e. a triple (x,x+r,x+2r) where r is non-zero and we identify [math]\displaystyle{ [3]^n }[/math] with [math]\displaystyle{ ({\Bbb Z}/3{\Bbb Z})^n }[/math].
Roth's theorem is a special case of Szemerédi's theorem. See also Szemerédi's combinatorial proof of Roth's theorem.
Roth's theorem is implied by the corners theorem, which in turn is implied by the k=3 case of the IP-Szemerédi theorem, which is in turn implied by k=3 case of the density Hales-Jewett theorem.
