I have been reading about Additive Combinatorics and in particular Roth's theorem which states any positive upper density set has infinitely many 3-step arithmetic progressions.
Let $A \subset \mathbb{Z}$ be a subset of positive upper density, i.e. $\limsup \tfrac{|A \cap [-N,N]|}{2N+1} > 0$.
Then $A$ contains infinitely many arithmetic progressions $a, a+r, a+2r \in A$.
In fact, I have found numerous expositions on Roth's theorem in recent hears highlighting on technique or another. Fourier analysis, sumset theory, dynamical systems, etc. Here's one of the more peculiar ones:
- A Probabilistic Technique for Finding Almost-Periods of Convolutions
- On Roth's Theorem on Progressions
- Roth's Theorem in the Primes
- Improving Roth's Theorem in the Primes
- On Improving Roth's Theorem in the Primes
I am not attacking the merit of these subjects - my colleagues, not mathematicians, do that already. I am enjoying the time I have spent reading about these various techniques, but I want to understand better why there is so much effort in this particular area.
These days I work in industry and every day I see large subsets of $\mathbb{Z}$ in my office, but I am not sure where Additive Combinatorics fits into the picture. Occasionally I have taken an FFT, but I have not computed $A+A$ or anothing, since I am not sure what set $A$ should be.
I am guessing these technical estimates arise in other problems in Number Theory or in the Theoretical CS literature.
In order to make the question focused - and get better answers - I am restricting my attention to Roth's theorem.
Examples could be in a strange places. On a different occasion, I was learning some combinatorial game theory however, in order to implement the algorithms mentioned in that article I had to read about communication complexity lower bound