most recent 30 from http://mathoverflow.net 2013-05-24T11:10:58Z http://mathoverflow.net/feeds/question/118177 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/118177/minimal-period-of-arithmetic-progressions-occurring-in-sets-of-positive-density POJ 2013-01-06T04:06:33Z 2013-01-06T23:42:24Z

<p>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</p> <p>$$ {a, a+r, a+2r, \dots, a+(k-1)r}. $$</p> <p>Thus, the finiteness of $R_k$ is Szemeredi's theorem. </p> <p>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: </p> <blockquote> <p>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$.</p> </blockquote> <p>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. </p>

http://mathoverflow.net/questions/118177/minimal-period-of-arithmetic-progressions-occurring-in-sets-of-positive-density/118186#118186 Anthony Quas 2013-01-06T07:18:32Z 2013-01-06T07:18:32Z

<p>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. $$</p> <p>This has positive upper density (in fact positive density), because what you're removing has density $\sum_{n\ge 5}n/2^{n+1}&lt;1$.</p> <p>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.</p>

http://mathoverflow.net/questions/118177/minimal-period-of-arithmetic-progressions-occurring-in-sets-of-positive-density/118236#118236 Stefan Kohl 2013-01-06T23:42:24Z 2013-01-06T23:42:24Z

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