Progressions in sumset or complement

Question

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.

Answer 1

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$.

Answer 2

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}$.