6
$\begingroup$

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$

  • 0
    @ShayMoran I give the argument in my answer below.2012-07-06

2 Answers 2

1

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.

5

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