Szemerédi's combinatorial proof of Roth's theorem: Difference between revisions
New page: To emphasise the similarity with DHJ, let us work here with Roth's theorem for <math>[3]^n</math>: '''Roth's theorem.''' If n is sufficiently large depending on <math>\delta > 0</math>, ... |
No edit summary |
||
| Line 1: | Line 1: | ||
To emphasise the similarity with DHJ, let us work here with Roth's theorem for <math>[3]^n</math>: | To emphasise the similarity with DHJ, let us work here with [[Roth's theorem]] for <math>[3]^n</math>: | ||
'''Roth's theorem.''' 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 | '''Roth's theorem.''' 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>. | ||
Szemerédi's proof is based on three observations: | Szemerédi's proof is based on three observations: | ||
| Line 7: | Line 7: | ||
1. If A is dense, then it contains a structured set Q (specifically, a medium-dimensional cube). | 1. If A is dense, then it contains a structured set Q (specifically, a medium-dimensional cube). | ||
2. If A has no | 2. If A has no algebraic lines, and contains a structured set Q, then the complement of A contains a _large_ structured set, namely 2.Q - A. | ||
3. If the complement of A contains a large structured set (or equivalently, if A is “squeezed” into the complement of a large structured set), then there is some subspace of A of increased density. | 3. If the complement of A contains a large structured set (or equivalently, if A is “squeezed” into the complement of a large structured set), then there is some subspace of A of increased density. | ||
Latest revision as of 08:51, 14 February 2009
To emphasise the similarity with DHJ, let us work here with Roth's theorem for [math]\displaystyle{ [3]^n }[/math]:
Roth's theorem. 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].
Szemerédi's proof is based on three observations:
1. If A is dense, then it contains a structured set Q (specifically, a medium-dimensional cube).
2. If A has no algebraic lines, and contains a structured set Q, then the complement of A contains a _large_ structured set, namely 2.Q - A.
3. If the complement of A contains a large structured set (or equivalently, if A is “squeezed” into the complement of a large structured set), then there is some subspace of A of increased density.
Combining 1, 2, 3 and the density increment argument one obtains Roth’s theorem.
Step 1 is known as the Szemerédi cube lemma and is an easy consequence of Cauchy-Schwarz. Step 2 is immediate for algebraic lines but seems to fail completely for combinatorial lines.
Now let's discuss Step 3. We know that the complement of A contains 2.Q - A for some medium-dimensional cube Q. We can represent Q as an increasing sequence Q_1 \subset Q_2 \subset \ldots \subset Q_d = Q as in 86, and use the pigeonhole principle to find a place where 2.Q_i - A stabilises, i.e. it has almost the same density as 2.Q_{i+h}-A for some medium-sized h. Thus the set 2.Q_i - A is almost invariant under the h steps v_i, \ldots v_{i+h}, and so is approximately equal to a union of cosets of the subspace V spanned by these h vectors. So A largely avoids a dense union of cosets of V, so by pigeonhole, it must have significantly increased density on another coset of V, and this is enough for the density increment argument to kick in.
But I do not see how to use this sort of argument to prove either DHJ or corners, the problem being that the analogue of 2.Q-A is far too sparse in either setting.
Question: Can this sort of argument be used to prove the corners theorem?
