6
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice! So there exists an infinite set of $k$ (namely powers of two) for which $R_k\geq\log_2 k$. $\endgroup$
    – POJ
    Jan 7, 2013 at 3:22
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.