Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 11 down vote accepted

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

share|improve this answer
    
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 '10 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 '10 at 11:32
add comment

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.