Question

It is a famous theorem of Roth, which Szemerédi famously generalized, that if a set of natural numbers has positive upper density then it contains arithmetic progressions of length $k$. The famous Green-Tao Theorem generalized this property to the primes. My question is, is there any progress on the 'inverse' problem?

First Question: Suppose $A \subset \mathbb{N}$ has positive upper density. Does it follow that with at most finitely many exceptions, all elements $a \in A$ is in an arithmetic progression of length at least $3$ in elements of $a$? That is, with at most finitely many exceptions, is it true that for each $a \in A$ there exists $k > 0$ such that $a, a+k, a+2k \in A$?

Edit: This question has been answered; see below by two constructions. However a second question may be asked.

A related problem (which I believe to be harder) is the same question for the primes, which has been asked here before:

http://mathoverflow.net/questions/34197/are-all-primes-in-a-pap-3

Another related problem is found here (the constructions given all have density less than 1/2. Is it possible to find counterexamples with large density?)

http://mathoverflow.net/questions/49977/do-there-exist-sets-of-integers-with-arbitrarily-large-upper-density-which-contai

Answer 1

Or just take all powers of $3$ and add to them all numbers that are congruent to $1$ modulo $3$.

Answer 2

This is false. We construct $A$ inductively, so that the following holds:

• $A$ contains all powers of two larger or equal than $4$ and no other even numbers.
• The number of odd numbers in $A$ between $2^j$ and $2^{j+1}$ is $2^{j-2}$.
• No power of two is in a 3-AP contained in $A$.

We start by specifying that $4\in A, 5\in A, 6\notin A,7\notin A$. Suppose $A\cap\{1,\ldots, 2^m-1\}$ has been defined so that the above properties hold. We next define $A\cap\{ 2^m,\ldots, 2^{m+1}-1\}$ as follows: $2^m\in A$. There are $1+2+\ldots+2^{m-3}<2^{m-2}$ odd numbers smaller than $2^m$ in $A$; let $O_m$ be the set of all of them. We choose $2^{m-2}$ odd numbers in $$ \{2^m,\ldots, 2^{m+1}\} \backslash (2^{m+1}-O_m). $$ and add them to $A$. We can do this since $|O_m|< 2^{m-2}$.

The first two properties are clear from the construction. To check the last (the one we care about), note that $2^m$ can't be the first/last term of a $3$-AP in $A$, since then the last/first term would also be even, hence another power of $2$, and then the middle one would be even, and a power of $2$ as well. But $2^m$ can't be the middle term of a $3$-AP either: for the same reason as before, the other two terms must be odd. Let $(a,2^m,c)$ be the AP. Then $a\in O_m$ by definition, but this implies $c-2^m=2^m-a$, or $c\in 2^{m+1}-O_m$, a case which was excluded in the construction.

Clearly $A$ has density $1/4$ so this completes the proof.

---

If $A$ has positive upper density, one can still ask what is the largest possible size of the set $B$ of all elements of $A$ which are not in any $3$-AP contained in $A$. Clearly $B$ has density $0$ by Roth's Theorem (and we get better bounds from the quantitative bounds in Roth's Theorem). Is it possible to do better?