Fix $\epsilon>0$.
For all large $N$, does there exist $A\subset [N]:=\{1,\dots,N\}$ such that both $A+A$ and $A^c:=[N]\setminus A$ lack arithmetic progressions of length $N^\epsilon$?
I am aware Rusza used “niveau sets” to create dense subsets of $[N]$ whose sumsets lack progressions of length $\exp(\log^{2/3+o(1)}N)$ (see https://eudml.org/doc/206433). But I don’t understand the construction well enough to know if it lacks long progressions in the complement (and thus satisfies the above).
My motivation is that I read that it was an open problem to determine for $r\ge 2$ if there exists $\epsilon_r> 0$, so any $r$-coloring $c:[N]\to [r]$ has some color class $A$ where $A+A$ contains a progression of length $N^{\epsilon_r}$. If one could find some $\epsilon>0$ where my question is false, then we could inductively take $\epsilon_r =(r-1)\epsilon$. So I am hoping to learn if this approach is viable.
Best Answer
I don't know of a reference where this has been worked out for niveau sets in $[N]$, but I would guess that niveau sets do not work, by considering the 'finite field model' of niveau sets in $\mathbb{F}_2^n$ (as discussed by Ben Green in https://arxiv.org/pdf/math/0409420.pdf).
The 'niveau set' here is $A\subset \mathbb{F}_2^n$ consisting of all vectors with at least $n/2+\sqrt{n}/2$ ones. Green shows (Theorem 9.4 of the above paper) that $A+A$ does not contain any large cosets of subspaces, but the complement of $A$ (which is the set of all vectors with at least $n/2-\sqrt{n}/2$ zeros) trivially contains a subspace of dimension $n/2+\sqrt{n}/2$. (One can show by Green's argument that this is also best possible.)
This does not directly answer your question, but generally we expect $\mathbb{F}_2^n$ to behave similarly to $[N]$ and cosets of subspaces to be analogous to arithmetic progressions, and niveau sets behave similarly in both settings. So I would guess that the complements of Ruzsa's niveau sets in $[N]$ probably do contain arithmetic progressions of length $N^c$ for some $c>0$.