# Average number of divisors of a certain type

• Aug 18th 2009, 08:00 AM
Bruno J.
Average number of divisors of a certain type
This problem is my own invention. I hope you enjoy it.

Suppose the infinite set $S$ has zero density in $\mathbb{N}$ (so that the proportion of elements of $S$ less than $n$ goes to 0 as $n \rightarrow \infty$).

Let $\omega(n)$ be the number of elements of $S$ which divide $n$.

Show that $\frac{1}{n}\sum_{j=1}^n\omega(j) = \sum_{s \in S, s\leq n}\frac{1}{s} + O(1)$.

For instance the average number of prime divisors of $1,2,...,n$ is asymptotically equal to $\sum_{p\leq n}\frac{1}{p}$. The average number of square divisors is asymptotically equal to $\zeta(2)$.
• Aug 18th 2009, 10:17 AM
PaulRS
Simply note that in the sum $
\sum\limits_{k = 1}^n {\omega \left( k \right)}
$
each $s\in S$ is counted as many times as multiples it has in $
\left\{ {1,...,n} \right\}
$
, which is exactly: $
\left\lfloor {\tfrac{n}
{s}} \right\rfloor
$
.

Thus: $
\sum\limits_{k = 1}^n {\omega \left( k \right)} = \sum\limits_{s \in S} {\left\lfloor {\tfrac{n}
{s}} \right\rfloor }
$

Let $S_n=
\left\{ {s \in S/1 \leqslant s \leqslant n} \right\}
$
then of course: $
\sum\limits_{s \in S} {\left\lfloor {\tfrac{n}
{s}} \right\rfloor } = \sum\limits_{s \in S_n } {\left\lfloor {\tfrac{n}
{s}} \right\rfloor }
$
. By the definition of the floor function: $
\sum\limits_{s \in S_n } {\left\lfloor {\tfrac{n}
{s}} \right\rfloor } \leqslant \sum\limits_{s \in S_n } {\tfrac{n}
{s}} < \sum\limits_{s \in S_n } {\left( {\left\lfloor {\tfrac{n}
{s}} \right\rfloor + 1} \right)}
$

Hence: $
\sum\limits_{k = 1}^n {\omega \left( k \right)} \leqslant n \cdot \sum\limits_{s \in S_n } {\tfrac{1}
{s}} < \sum\limits_{k = 1}^n {\omega \left( k \right)} + \left| {S_n } \right|
$
$
\therefore \left| {\sum\limits_{s \in S_n } {\tfrac{1}
{s}} - \tfrac{1}
{n} \cdot \sum\limits_{k = 1}^n {\omega \left( k \right)} } \right| < \tfrac{1}
{n} \cdot \left| {S_n } \right| \leq 1
$
and assertion is proven. $\square$

- If we also had $
\frac{{\left| {S_n } \right|}}
{n} \to 0
$
then $
\left| {\sum\limits_{s \in S_n } {\tfrac{1}
{s}} - \tfrac{1}
{n} \cdot \sum\limits_{k = 1}^n {\omega \left( k \right)} } \right| = o\left( 1 \right)
$
(little O) -