Regression On Arithmetic Progressions
How far can trivial ideas go?
Klaus Roth is famous for many results, but two stand out above all others.
One sets limits on Diophantine approximations to algebraic numbers, and the other sets limits on how dense a set can be and have no length-three arithmetic progression. He has won many awards for his work, including a Fields Medal and the Sylvester Medal.
Today I want to try and amuse you with a simple proof that is related to his work on progressions.
I will sketch a really simple argument that shows a vastly weaker result than Roth’s famous theorem. Recall Roth proved:
Let be a subset of without any length-three arithmetic progression, then .
A length-three arithmetic progression is for some .
There are now many variations of his proof, some combinatorial, some Fourier-based, some that use ergodic theory. There is of course the major generalization by Endre Szemerédi, who extended the result to any length progression.
A 97% Solution
Suppose we want to prove that any subset of density of must have a length-three progression. How small can we make and keep the proof really really simple? I set out to do this, more for amusement than any attempt to find a new proof of Roth’s result. But I do think that finding a really simple argument for even would be a cool result.
Such weaker theorems could shed light on what makes Roth’s theorem work. They also could yield new generalizations, or they could help us in complexity theory. Or they could be of no value at all. Just an amusement. Just fun. We will see.
I can prove this:
Let be a subset of without any length-three arithmetic progression, then for large enough.
Pretty sad, but we do what we can do.
So let be a subset of that contains elements. We can assume that it has no length-three progression. Let us define the following graph : the vertices are the elements of the set , and there is an edge from to provided .
We will now count the number of edges of . There are exactly
edges: choose an unordered pair and there is one edge that comes from this pair.
We will show that the assumption that has no length-three progression implies an upper bound on the number of edges. This bound will then show that cannot be too large a subset of .
There are two cases. If is less than in cardinality, then the cardinality of is at most and we are done. So we can assume that intersect has cardinality at least .
We now make the only insight—a trivial one—but a useful one. The graph can have at most
edges. This will finish the proof of the theorem.
Consider an in . If there is an edge to with , then there is no edge from to . Therefore we “lose” at least
total edges. So has at most edges. This shows that
So for large enough we get that is at most .
The key to this simple proof is the observation that if points to and then there is a progression. Note, we could change this rule to allow different type of progressions. Call three points a special three-progression if they are of the form:
where . Then we can prove the same type of bound for this type of “progression.” Is that of any interest?
For example, we could show that any for any sufficiently dense there must be and such that these are all in :
Does this help? Is it fun? Can you improve via a similar simple argument? No attempt was made in the argument to optimize the : I believe we can do better. How far can it be improved and still remain simple?
Are you amused?