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:
Letbe a subset of
without any length-three arithmetic progression, then
.
A length-three arithmetic progression is 
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 
![{[N]=\{1,\dots,N\}}](https://s0.wp.com/latex.php?latex=%7B%5BN%5D%3D%5C%7B1%2C%5Cdots%2CN%5C%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
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:
Letfor
large enough.
Pretty sad, but we do what we can do.
The Proof
So let 
![{[N]}](https://s0.wp.com/latex.php?latex=%7B%5BN%5D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
We will now count the number of edges of
edges: choose an unordered pair 
We will show that the assumption that
There are two cases. If ![{S \cap [N/4]}](https://s0.wp.com/latex.php?latex=%7BS+%5Ccap+%5BN%2F4%5D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
![{[N/4]}](https://s0.wp.com/latex.php?latex=%7B%5BN%2F4%5D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
We now make the only insight—a trivial one—but a useful one. The graph
edges. This will finish the proof of the theorem.
Consider an 
total edges. So 
So for 
Extensions
The key to this simple proof is the observation that if
where 
For example, we could show that any for any sufficiently dense 
Open Problems
Does this help? Is it fun? Can you improve
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!