show/hide this revision's text 3 added 340 characters in body

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?

show/hide this revision's text 2 added 9 characters in body

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.

show/hide this revision's text 1

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

  • $A$ contains all powers of two larger 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.