# Partition of the natural numbers to arithmetic sequences

Let $\mathcal{S}$ be a collection of infinite arithmetic progression that forms a partition of $\mathbb{N}$. If $|\mathcal{S}|<\infty$ then $$\sum_{s\in\mathcal{S}:~d~\mbox{ is the difference of }s}{1/d}=1$$

Is the above still correct when $|\mathcal{S}|=\infty$?

I could prove that the sum is $\leq 1$

-
In your summation the $d$'s are counted with multiplicity, correct? – J. Loreaux Jul 5 '12 at 23:05
@J.Loreaux: Yes – Shay Moran Jul 5 '12 at 23:06
If it helps formulate the proof, the statement is essentially stating that an arithmetic progression with difference $d$ contains 1/$d^\text{th}$ of the mass of the natural numbers. – Eugene Shvarts Jul 5 '12 at 23:35
@EugeneShvarts, I agree with this statement which is essentially the proof I have for the finite case. However, I don't see how to use it when the number of sequences is infinite – Shay Moran Jul 5 '12 at 23:39
I'm not convinced it is true anymore if $S$ is infinite. Consider what happens if you start plastering $\mathbb N$ with $4\mathbb N, 4^2\mathbb N+1,4^3\mathbb N+2,4^4\mathbb N+3,4^5\mathbb N+5,4^6\mathbb N+6,\dots$ Looks like a counter example to me. The sum of densities would be $\sum_{i\geq 1} 4^{-i}$. I might be wrong, and apparantly Brian M. Scott disagrees ^^ – Olivier Bégassat Jul 5 '12 at 23:55

Here is an expansion of Olivier's answer. Let $d_1,d_2,\ldots$ be a sequence of integers satisfying $d_i|d_j$ whenever $i \leq j$ and $$\sum_{i \geq 1} \frac{1}{d_i} \leq 1. \qquad (1)$$ We construct the covering sequence greedily. The $i$th set is $S_i = a_i + d_i \mathbb{N}$, where $a_i$ is the minimal number not covered so far (there must be such a number because of (1)). Clearly all of $\mathbb{N}$ is eventually covered. In order to see that no number is covered twice, suppose that $a_i + d_i x_i = a_j + d_j x_j$ for some $i < j$. By construction, $a_j > a_i$ and $a_j - a_i$ is divisible by $d_i$. But then $a_j$ is covered by $S_i$.

Let $x \in (0,1]$. We can expand $x$ in binary to get $$x = \sum_{i \geq 1} 2^{-a_i}.$$ (If $x$ is dyadic, choose the infinite expansion.) Taking $d_i = 2^{a_i}$, we see that there is a covering where the left-hand side of (1) evaluates to $x$.

To complete the picture, Brian's argument shows that (1) holds for any partition, and so our results are tight.

-

Converting my comment to an answer.

It is wrong for infinite $S$. Consider the following partition of $\mathbb N=\lbrace 0,1,2,\dots\rbrace$. Define $P_1=4^1\mathbb N, P_2=4^2\mathbb N+1,P_3=4^3\mathbb N+3,P_4=4^4\mathbb N+5,P_5=4^5\mathbb N+6,\dots$ and more generally $P_k=4^k\mathbb N+m_k$ where $m_k$ is the smallest integer not in $P_1\cup\dots\cup P_{k-1}$ (with $m_1=0$.) By construction, the $P_k$ cover $\mathbb N$, and it remains to show that they don't overlap.

The sequence $m_k$ is easily seen to be increasing. If $P_a\cap P_b$ were non-empty for some $a<b$, there would be non negative integers $r,s$ such that $m_a+ r4^a=m_b+s4^b=m_b+s4^{b-a}4^a$. Since $m_a<m_b$, this would imply $r>s4^{b-a}$ and $m_b=m_a+(r-s4^{b-a})4^a\in P_a$ contradicting the definition of $m_b$. Thus $$\mathbb N =P_1\sqcup P_2\sqcup P_3\sqcup\cdots$$

However, $$\sum_{i\geq 1}\frac{1}{4^i}=\frac{1}{4}\cdot\frac{1}{1-1/4}=\frac{1}{3}<1.$$

-