# 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:

Theorem:

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:

Theorem:

Let be a subset of without any length-three arithmetic progression, then for large enough.

Pretty sad, but we do what we can do.

## The Proof

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 .

## Extensions

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 :

## Open Problems

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?

I am certainly amused but also confused – why did you choose this proof instead of the much simpler one that shows $\delta\le 2/3+\epsilon$?

no

There is a simpler argument that gives a better bound. Pick two random elements in and consider the probability that the following events both hold: (i) all three of , , and are in S, (ii) . If there is a positive probability, then we have a non-trivial length-3 progression in S.

We call the density of in {0,…,N-1} and we use a union bound to upper bound the probability that the two events do not both happen. Regarding (i), a, a+b mod N, and a+2b mod N are all uniform in {1,…,N}, and so the probability that they are not all in S is at most ; the probability of (ii) is 1/4 – O(1/N), because for every choice of we have choices of , so, out of possible choices there are good ones. So the probability that (ii) does not happen is 3/4 + O(1/N).

The probability that not both conditions are satisfied is which is less than 1 if $\latex \sigma = .08 < 1/12$ and N is large enough.

luca

Thanks and to others for better proofs. How far can we go with easy arguments? Also do these generalize to strange notions of other types of “progressions”

rjlipton asked: “How far can we go with easy arguments?”

From any eight-tuple 8k-7, 8k-6, …, 8k, one cannot pick more than four elements without creating a length-three arithmetic progression. This yields that (asymptotically) the density of S is at most 1/2.

Analogous observations centered around longer and longer blocks yield an “easy argument” for the following: For every eps>0, the density of S must eventually go below eps.

(The existence of these easy arguments is guaranteed by Roth’s theorem.)

You also want the condition , which adds another to the union bound.

It’s astounding to me how many posts you have written that land within days of my thinking about the very same topic.

Any triple 3k-2, 3k-1, 3k with k>=1 forms a length-three arithmetic progression.

Hence your set S can contain at most 2 numbers from each such triple.

This yields |S|/N<=2/3.

See also T. Sanders, On Roth’s theorem on progressions, Ann. of Math. (2), to appear, arXiv: http://arxiv.org/abs/1011.0104 … We show that if A is a subset of {1,…,N} and contains no non-trivial three-term arithmetic progressions then |A|=O(N/ log^{1-o(1)} N) …

Sorry, delete my unuseful comment (the proof on the paper is far from being simple :-)

You can get a bound by 2/3N:

The set cannot contain any three consecutive numbers or else we get a progression…

Ah!