Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
A version of this question is also discussed at mathoverflow.net/questions/87923/… (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" (math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/szemeredi.html ) might also be of interest. –  Kevin P. Costello Jan 7 '13 at 23:01
add comment

2 Answers 2

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.