Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
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
2  
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.