MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
A version of this question is also discussed at… (the Thue-Morse sequence mentioned in the original question there corresponds to Stefan's answer). Raff and Zeilberger's "Finite Analogs of Szemeredi's Theorem" ( ) might also be of interest. – Kevin P. Costello Jan 7 '13 at 23:01
up vote 6 down vote accepted

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.

share|cite|improve this answer
Nice! So there exists an infinite set of $k$ (namely powers of two) for which $R_k\geq\log_2 k$. – POJ Jan 7 '13 at 3:22

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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