inequality of logarithmic and asymptotic density

For any $A\subseteq \mathbb{N}$ we denote$A(n):=|A\cap \{1,2,\mathrm{\dots },n\}|$ and $S(n):=\sum _{k=1}^n\frac{1}{k}$.

Recall that the values

$$\underset{¯}{d}(A)=\underset{n\to \mathrm{\infty }}{lim\; inf}\frac{A(n)}{n}\mathit{\hspace{1em}\hspace{1em}}\overline{d}(A)=\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{A(n)}{n}$$

are called lower and upper asymptotic density of $A$.

The values

$$\underset{¯}{\delta }(A)=\underset{n\to \mathrm{\infty }}{lim\; inf}\frac{\sum _{k\in A;k\le n}\frac{1}{k}}{S(n)}\mathit{\hspace{1em}\hspace{1em}}\overline{\delta }(A)=\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{\sum _{k\in A;k\le n}\frac{1}{k}}{S(n)}$$

are calledlower and upper logarithmic density of $A$.

We have $S(n)\sim \ln n$ (we use the Landau notation). Thisfollows from the fact that $\underset{n\to \mathrm{\infty }}{lim}S(n)-\ln n=\gamma$ is Euler’sconstant. Therefore we can use $\ln n$ instead of $S(n)$ in thedefinition of logarithmic density as well.

The sum in the definition of logarithmic density can be rewrittenusing Iverson’s convention as ${\sum }_{k=1}^n\frac{1}{k}[k\in A]$.(This means that we only add elements fulfilling the condition$k\in A$. This notation is introduced in [1, p.24].)

Theorem 1.

For any subset $A\mathrm{\subseteq }\mathrm{N}$

$$\underset{¯}{d}(A)\le \underset{¯}{\delta }(A)\le \overline{\delta }(A)\le \overline{d}(A)$$

holds.

Proof.

We first observe that

$$\frac{1}{k}[k\in A]=\frac{A(k)-A(k-1)}{k},$$

$$D(n):=\sum _{k=1}^n\frac{1}{k}[k\in A]=\frac{A(n)}{n}+\sum _{k=1}^{n-1}\frac{A(k)}{k(k+1)}$$

There exists an $n_0\in \mathbb{N}$ such that for each $n\ge n_0$ it holds$\underset{¯}{d}(A)-\epsilon \le \frac{A(n)}{n}\le \overline{d}(A)+\epsilon$.

We denote $C:=1+S(n_0)$. For $n\ge n_0$ we get

$$D(n)\le C+\sum _{k=n_0}^{n-1}\frac{A(k)}{k}\cdot \frac{1}{k+1}\le C+(\overline{d}(A)+\epsilon )\sum _{k=n_0}^{n-1}\frac{1}{k+1}\sim (\overline{d}(A)+\epsilon )\ln n,$$

$$\overline{\delta }(A)=\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{D(n)}{\ln n}\le \overline{d}(A)+\epsilon .$$

This inequality holds for any $\epsilon >0$, thus $\overline{\delta }(A)\le \overline{d}(A)$.

For the proof of the inequality for lower densities we put$C^{\prime }:={\sum }_{k=1}^{n_0-1}\frac{A(k)}{k(k+1)}-(\underset{¯}{d}(A)-\epsilon )S(n_0)$.We get

$$\begin{array}{c}D(n)\ge C^{\prime }+(\underset{¯}{d}(A)-\epsilon )S(n_0)+(\underset{¯}{d}(A)-\epsilon )\sum _{k=n_0}^n\frac{1}{k+1}=\hfill \\ \hfill C^{\prime }+(\underset{¯}{d}(A)-\epsilon )S(n)\sim (\underset{¯}{d}(A)-\epsilon )\ln n\end{array}$$

and this implies $\underset{¯}{\delta }(A)\ge \underset{¯}{d}(A)$.∎

For the proof using Abel’s partial summation see [4]or [5].

Corollary 1.

If a set has asymptotic density, then it has logarithmic density,too.

A well-known example of a set having logarithmic density but nothaving asymptotic density is the set of all numbers with the firstdigit equal to 1.

It can be moreover proved, that for any real numbers $0\le \underset{¯}{\alpha }\le \underset{¯}{\beta }\le \overline{\beta }\le \overline{\alpha }\le 1$ thereexists a set $A\subseteq \mathbb{N}$ such that $\underset{¯}{d}(A)=\underset{¯}{\alpha }$,$\underset{¯}{\delta }(A)=\underset{¯}{\beta }$, $\overline{\delta }(A)=\overline{\beta }$ and $\overline{d}(A)=\overline{\alpha }$ (see [2]).