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.



Progressions in sumset or complement
Ah, I realized how to construct such $A$.


The idea is to just crudely mimic the construction for the off-diagonal van der Waerden numbers $w(3,k)$.


We fix parameters $D,M,\rho$ which will be optimized later.


We shall sample $M$ points $x\_1,\dots,x\_M$ from the $D$-dimensional torus $\Bbb{T}^D := \Bbb{R}^D/\Bbb{Z}^D$. We then take $A\_0\subset \Bbb{T}^D$ to be $\{x\_1,\dots,x\_M\}+B\_0$ where $B\_0$ is the box $[0,\rho]^D+\Bbb{Z}^D$.


One then chooses $\theta \in \Bbb{T}^D$ uniformly at random and takes $A=\{n\in[N]: n\theta \in A\_0\}$. I claim that we can let $D=D(N)\to \infty$ as $N\to \infty$ while ensuring $A+A$ and $A^c$ both lack progressions of length $N^{O(1/D)}$.


In short, one just modifies several calculations from my paper (<https://arxiv.org/abs/2111.01099>). I might update with further details later, but if I’m not mistaken, this blocks progressions of length $\exp(O(\sqrt{\log N \log\log N}))$.


The intuition is that this looks like a union of $M$ generalized arithmetic progressions (GAP's) of rank $D$, $G\_1,...,G\_M$ where each $G\_i$ "looks generic" and thus doesn't have any arithmetic progressions much longer than $N^{1/D}$. The $M$ GAP'S are sufficiently randomly distributed in $[N]$ that they block progressions in the complement, as was shown in the aforementioned paper.


Meanwhile, $A+A$ looks like a union of $M^2$ GAP's of rank $D$, which again all look generic. Taking $M$ much smaller than $N^{1/D}$, these $M^2$ GAP's in $A+A$ shouldn't really interact, resulting in there not being progressions dramatically longer than $N^{1/D}$.


