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 ${S}$ be a subset of ${[N]}$ without any length-three arithmetic progression, then ${|S| = o(N)}$.

A length-three arithmetic progression is ${x,x+a,x+2a}$ for some ${a>0}$.

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 ${\delta}$ of ${[N]=\{1,\dots,N\}}$ must have a length-three progression. How small can we make ${\delta}$ 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 ${\delta=1/10}$ 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 ${S}$ be a subset of ${[N]}$ without any length-three arithmetic progression, then ${|S| \le 0.97N}$ for ${N}$ large enough.

Pretty sad, but we do what we can do.

## The Proof

So let ${S}$ be a subset of ${[N]}$ that contains ${\delta N}$ elements. We can assume that it has no length-three progression. Let us define the following graph ${G}$: the vertices are the elements of the set ${S}$, and there is an edge from ${x}$ to ${y}$ provided ${x .

We will now count the number of edges of ${G}$. There are exactly

$\displaystyle {|S| \choose 2}$

edges: choose an unordered pair ${\{x,y\}}$ and there is one edge that comes from this pair.

We will show that the assumption that ${S}$ has no length-three progression implies an upper bound on the number of edges. This bound will then show that ${S}$ cannot be too large a subset of ${[N]}$.

There are two cases. If ${S \cap [N/4]}$ is less than ${N/8}$ in cardinality, then the cardinality of ${S}$ is at most ${7/8N}$ and we are done. So we can assume that ${S}$ intersect ${[N/4]}$ has cardinality at least ${N/8}$.

We now make the only insight—a trivial one—but a useful one. The graph ${G}$ can have at most

$\displaystyle N^{2}/2 - N^{2}/32$

edges. This will finish the proof of the theorem.

Consider an ${x}$ in ${[N/4]}$. If there is an edge to ${x+a}$ with ${a, then there is no edge from ${x}$ to ${x+2a}$. Therefore we “lose” at least

$\displaystyle N/8 \times N/4$

total edges. So ${G}$ has at most ${N^{2}/2 - N^{2}/32 + O(N)}$ edges. This shows that

$\displaystyle |S|^{2}/2 +O(|S|) \le \frac{15}{32}N^{2} +O(N).$

So for ${N}$ large enough we get that ${|S|}$ is at most ${\sqrt{30/32} \approx 0.968 }$.

## Extensions

The key to this simple proof is the observation that if ${x}$ points to ${x+a}$ and ${x+2a}$ 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:

$\displaystyle x, \ x + a, \ x + f(a),$

where ${2a>f(a) > a}$. 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 ${S}$ there must be ${x}$ and ${a}$ such that these are all in ${S}$:

$\displaystyle x, x+a, x+2a-\lfloor \sqrt{a} \rfloor.$

## Open Problems

Does this help? Is it fun? Can you improve ${\delta}$ via a similar simple argument? No attempt was made in the argument to optimize the ${\delta}$: I believe we can do better. How far can it be improved and still remain simple?

Are you amused?

1. February 3, 2014 1:37 pm

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$?

February 3, 2014 2:28 pm

no

3. February 3, 2014 5:39 pm

There is a simpler argument that gives a better bound. Pick two random elements $a,b$ in $\{ 0,\ldots,N-1\}$ and consider the probability that the following events both hold: (i) all three of $a$, $a+b \bmod N$, and $a+2b \bmod N$ are in S, (ii) $a + 2b < N$. If there is a positive probability, then we have a non-trivial length-3 progression in S.

We call $1-\sigma$ the density of $S$ 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 $3\sigma$; the probability of (ii) is 1/4 – O(1/N), because for every choice of $a$ we have $(N-a)/2$ choices of $b$, so, out of $N^2$ possible choices there are $\frac 12 \cdot \sum_a (N-a) = \frac {n^2}4 - O(N)$ 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 $3/4 + 3\sigma + O(1/N)$ which is less than 1 if $\latex \sigma = .08 < 1/12$ and N is large enough.

February 4, 2014 9:50 am

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”

February 5, 2014 7:44 am

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.)

4. February 3, 2014 5:40 pm

You also want the condition $b\neq 0$, which adds another $1/N$ to the union bound.

5. February 3, 2014 11:43 pm

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

February 4, 2014 5:21 am

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.

7. February 4, 2014 3:59 pm

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) …

• February 5, 2014 2:56 am

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