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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

## 2 Answers

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

-

It took me a bit to understand this since I thought you meant the set of sums of powers of 3 with numbers 1 mod 3. – Harry Altman Dec 17 2010 at 7:30
Much better than my construction! This also shows that the exceptional set in the question can be as large as a set without $3$-APs (if $B$ has no $3$-APs, let $A=3B \cup (3\mahthbb{Z}+1)$. Then no element in $3B$ is part of a $3$-AP in $A$). – Pablo Shmerkin Dec 17 2010 at 11:32

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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?

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 57, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9501940011978149, "perplexity_flag": "head"}