While working on this question, I found another, a significantly harder and cute one. Consider only the specific partition such that the indicator function of one of the partitions follows the pattern $0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1, \ldots$ To elaborate on what the exact pattern is: 1) Take a string $0110$ 2) Flip it (i.e. replace each character $x$ of the string by $1-x$) to get $1001$ 3) Attach it to the previous string to get $01101001$ 4) Flip this and attach to get $0110100110010110$ 5) Repeat this forever Is there an infinite AP in any of these partitions?

MathPassionForever wrote: Is there an infinite AP in any of these partitions? If I'm understanding this correctly, this claims that this is very false: for any infinite AP $\mathcal{A}$ and any $N$, the difference between the number of elements of $\mathcal{A} \cap \{1, \dots, N\}$ in the two sets is $\mathcal{O}(N^\lambda)$ for some $\lambda < 1$.

It's possible in both cases. We may interpret the partitioning as coloring the natural number in two colors, say black, white. The second condition just says the difference between consecutive black (white) numbers is bounded. So, I don't see how the referenced paper could contradict the claim. All arithmetic progressions are countable, so order them in a row, $P_1, P_2,\dots$. Start consecutively choosing from each progression $P_i, i=1,2,\dots$ two appropriate elements (not already colored) and color them in different colors - one black, the other white. All the remaining non colored naturals may be colored arbitrary. That's it. We just must watch out not to breach the given condition, but we can choose numbers from each progression as big as we want, so it's mot a problem. EDIT. In fact, we can construct a coloring, such that the difference between any two consecutive monochromatic numbers is at most $3$.

A direct way to answer post #2's question, which is that no such AP exists. First, note that the partition is based on the parity of the sum of the digits of the number in binary (where we start at 0). Suppose an infinite arithmetic progression lies in one set of the partition. Let it be $a, a+d, a+2d, \ldots$. Suppose $d$ has $m$ digits in binary. There is a term of the progression $b$ that begins with a 1 followed by $2m$ zeroes in binary (just take the first term above a large power of two). Consider $b + 2^k d$, where $k$ is such that the leading 1 in $d$ aligns with the leading 1 in $b$, and also consider $b + 2^{k-1}d$. One of these additions has one carry, and the other has zero. This means their sum of digits in binary differs by one.

CantonMathGuy wrote: MathPassionForever wrote: Is there an infinite AP in any of these partitions? If I'm understanding this correctly, this claims that this is very false: for any infinite AP $\mathcal{A}$ and any $N$, the difference between the number of elements of $\mathcal{A} \cap \{1, \dots, N\}$ in the two sets is $\mathcal{O}(N^\lambda)$ for some $\lambda < 1$. Yes, you do understand it right. And thanks for the pdf! @above, yes, I tried something along your lines but couldn't finish. Thank you!