Question

Let $A$ be a subset of ${\mathbb N}$ with positive upper-Banach density, and for each integer $k\geq3$, define $R_k=R_k(A)$ to be the smallest positive integer $r$ such that $A$ contains a length $k$ arithmetic progression

$$ {a, a+r, a+2r, \dots, a+(k-1)r}. $$

Thus, the finiteness of $R_k$ is Szemeredi's theorem.

What, if anything, is known about how $R_k$ grows? More precisely, the question I am most interested in, without any luck so far, is the following:

Does there exist an example of a set $A$ for which $R_k$ grows with $k$, with, if possible, a lower bound on $R_k$? This lower bound may depend on $A$, but I am hoping for an explicit dependence on $k$.

If there are results in the other direction -- upper bounds on $R_k$ -- I would be interested to hear about those as well. Such a result could be considered a quantitative strengthening of Szemeredi's theorem, so perhaps this is asking for a lot.

Answer 1

Let $$ S=\mathbb N\setminus\bigcup_{n\ge 5}\bigcup_k\lbrace 2^n(2k+1),2^n(2k+1)+1,\ldots,2^n(2k+1)+(n-1)\rbrace. $$

This has positive upper density (in fact positive density), because what you're removing has density $\sum_{n\ge 5}n/2^{n+1}<1$.

If you want to find an arithmetic progression with length $2^{n+1}$, it must have difference at least $n+1$ because it can't fit entirely between two blocks that are removed at the $n$th level, and hence must "jump over" at least one of those blocks. In particular, the common difference has to be at larger than the length of the block that it jumped over.

Answer 2

It seems that a nice example is the set $A$ of positive integers which have an even number of 1's in their binary expansion, although I don't see a reasonable lower bound on $R_k(A)$ for now. A quick computation suggests that $R_2(A) = \dots = R_8(A) = 3$, $R_9(A) = R_{10}(A) = 9$, $R_{11}(A) = \dots = R_{20}(A) = 15$, $R_{21}(A) = \dots = R_{32}(A) = 31$, $R_{33}(A) = R_{34}(A) = 33$ and $R_{35}(A) = \dots = R_{68}(A) = 63$.