Infinite parts of zero natural density

Welcome again to my blog. Although, I do concede that looking at the frequency of my posts and the lack of readership, it is my blog that welcomes me.

Today we are going to talk about a very counter-intuitive construction. I credit discovery of this construction to my friend Yash Singh, who came up with it during a conversation over the phone. It’s most certainly possible though that someone came up with this before.

So we’re going to talk about partitioning the set of natural numbers in a counter-intuitive manner. Suppose {\mathbb{N}=\{ 0,1,2\dots\}} is the set of all natural numbers. The task is to partition this set into infinitely many parts, each part containing infinitely many elements, and each part having a natural density zero.

Hence, this most certainly proves that natural density cannot give us a probability measure on the set of natural numbers. This can of course be proven with easier constructions (it is probably the first exercise in this topic). However, this construction takes the natural density much more further away from being a measure.

To state more formally, we are going to create sets {P_i \subset \mathbb{N}}, i = 1, 2, \dots such that {\mathbb{N}= \bigsqcup_{i \ge 1} P_i } and at the same time for each {i}, the natural density is zero, which is to say the following:

\displaystyle \limsup_{n \rightarrow \infty } \frac{| \{ 0,1,2\dots n\} \cap P_i| }{| \{ 0,1,2\dots n\}| }=0.

So the construction is the following. Consider the collection of all prime numbers {\mathbb{P}} and let {D=\bigcup_{p \in \mathbb{P}} \bigcup_{j \ge 1} \{ p^j\}}, the set of all prime powers. Note that any number in {D} is the power of at most one prime.

Define the enumeration {f:\mathbb{N}\rightarrow D} given by {f(i) =}{i}th least number in {D}”. So more formally,

\displaystyle f(i) = \begin{cases} \min \left( D\setminus \{ f(0), f(1) \dots f(i-1)\} \right) \ \ \ \ \ \hfill\text{ if } i>0 \\ 2 \hfill \text{ if } i = 0\end{cases} .

Now let {\mathbb{P}=\{ p_1, p_2, p_3 \dots\}} be the enumeration of primes in increasing order. Now just define {P_k = \{ i \ | \ f(i) \text{ is a power of } p_k \}}. So we have a partition! All that is left is to prove that the density of each partition is zero.

Take the partition {P_i} for some {i} and choose some large {n}. Let {f(n)=m}. For any {j}, how many powers of {p_j} are less than or equal to {m}? It’s clearly {\lfloor \log_{p_j}(m)\rfloor = \lfloor \frac{\log(m)}{\log(p_j)}\rfloor}. We conclude that

\displaystyle \frac{| P_i \cap \{ 0 , 1 \dots n\}|}{ | \{ 0,1\dots n\}|} = \frac{\lfloor \frac{\log(m)}{\log(p_i)}\rfloor}{\sum_{ p_j \le m}^{} \lfloor \frac{\log(m)}{\log(p_j)}\rfloor} \le \frac{\lfloor \frac{\log(m)}{\log(p_i}\rfloor}{\log(m) |\{ p_i\ | \ p_i \le m \}|} \le \frac{1}{| \{ p_i \ | \ p_i \le m\}|} \rightarrow 0.

And that’s it! I hope you enjoyed reading this short construction. Please let me know if you spot any errors by email or by comments. Have a good day!