Inverse Length 3 Arithmetic Progression Problem for sets with positive upper density

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:

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

Do there exist sets of integers with arbitrarily large upper density which contains infinitely many elements that are not in an arithmetic progression of length 3?

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?