# Theorem on natural density

In this answer to a question about a series, a theorem was stated:

if $A= \{a_i \}$ is a set such that $\sum_{i = 1}^{\infty} \frac{1}{a_i}$ converges, then $d(A) = 0$, where $d(A)$ is the natural density of the set.

My background in number theory is basically zero and all my attempts to prove this have been utterly unseccessful; would anyone please help me, or at least provide me with a hint to prove it?

-

If the natural density of $A = \{a_i\}$ exists, then we can show that it must be zero.

Let $\displaystyle S_{n} = \frac{|A \cup [1,n]|}{n}$

Now $\displaystyle \{\frac{n}{a_n}\}$ is a subsequence of $S_{n}$ and so if the limit is $\displaystyle 2\delta > 0$ then we have that for all $\displaystyle n > N_0$, $\displaystyle \frac{n}{a_n} > \delta$ and so $\displaystyle \frac{1}{a_n} > \frac{\delta}{n}$ for all $\displaystyle n > N_0$ and so $\displaystyle \sum \frac{1}{a_n}$ diverges.

The main problem is actually showing that the limit exists.

It is easy to show that $\liminf$ is zero: If the limit was $\displaystyle 2\delta > 0$ then for all $n > N_{0}$, $S_{n} > \delta$ and an argument similar to above works.

Now suppose $\displaystyle \limsup S_n = 2\delta > 0$. Then there is a subsequence $\displaystyle S_{N_1}, S_{N_2}, ..., S_{N_k}, \dots$ which converges to $\displaystyle 2\delta$.

Now we can choose the subsequence so that $\displaystyle S_{N_i} > \delta$ and $\displaystyle N_{k+1} > \frac{2N_{k}}{\delta}$

Now the number of elements of $\displaystyle A$ in the interval $\displaystyle (N_{k}, N_{k+1}]$ is atleast $\displaystyle \delta N_{k+1} - N_k \ge \delta N_{k+1} - \frac{\delta N_{k+1}}{2} \ge \frac{\delta N_{k+1}}{2}$ and so the sum of reciprocals in that interval is atleast $\displaystyle \frac{\delta N_{k+1}}{2} \frac{1}{N_{k+1}} = \displaystyle \frac{\delta}{2}$

And so the sum of reciprocals must diverge.

Hence $\displaystyle \limsup S_n = 0 = \liminf S_n$ and thus $\displaystyle \lim S_n = 0$ and thus the natural density is zero.

-

Given a set $A = (\cup a_i) \subset N$ with positive lim-sup density, it is possible to partition $N$ into intervals on which $A$ has density $\geq d$. If the intervals grow in size at a suitable rate (for this problem, exponential growth is enough), there will be a positive number $C>0$ such that on each interval, $\Sigma_{a \in A} 1/a \geq C$, and this makes the sum over all intervals infinite.

In more detail,

1. There is a partition of the positive integers into intervals $[1,n_1], [n_1 + 1, n_2], [n_2 + 1,n_3], \dots$ such that the density of $A$ is at least $d > 0$ on each interval. This can be done for any $d < L$ where $L$ is the lim sup density of $A$.

2. By joining together adjacent intervals, one can also require that the sequence $n_k$ grows fast enough that density in $[1,n_i]$ is not strongly affected by what happens in preceding intervals $[1,n_j]$ with $j < i$. In particular, one can keep or remove the subinterval $[1,n_{i-1}]$ with small effect on density questions in $[1,n_i]$. For this problem, fast enough growth will mean strictly exponential growth, i.e., $n_{i+1} / n_i > p$ for constant $p > 1$.

3. The most efficient packing of a given number of integers into an interval $[m,n]$ (where efficiency means minimim sum of $1/a$ with $a$ ranging over the subset) is to place the whole subset as close as possible to $n$. If the density is at least $d$, the number of integers to be placed is at least $d(n-m+1)$, and then $\Sigma 1/a$ is at least $d(n-m)/n = d(1-m/n)$.

4. For the exponentially growing intervals with $m/n < 1/p$ the sum in each interval of the partition of $N$ is bounded below by $C=d(1-1/p) > 0$, so the sum of all $1/a_i$ is infinite.

-

EDIT nr 2: Please forget about this answer; as pointed out in the comments, it wasn't correct! (I've removed the text it here; see the edit history for the embarrasing details. Next time, I'll try to think properly before I post...)

-
Hmm, I was a bit sloppy there. The argument is not quite right, althought I think the basic idea works. I'll see if I can fix it before someone else gives a better answer. ;) – Hans Lundmark Oct 3 '10 at 12:41
There, that's better (I hope). – Hans Lundmark Oct 3 '10 at 13:01
Thanks for re-elaborating. I'll wait a bit still to accept the answer to see if somebody else wants to give it a shot. :) – Andy Oct 3 '10 at 14:58
I am not sure this is right. 1) Existence of $d(A)$ has to be shown. 2) What if $d(A)/2 - |A\cup[1,N]|/(N+k) < 0$?. – Aryabhata Oct 3 '10 at 19:56
1) Good point. 2) I thought I had ruled this out somehow, but looking back at what I wrote, I don't know what I was thinking! – Hans Lundmark Oct 4 '10 at 3:24