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 called lower and upper logarithmic density of $A$.

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

The sum in the definition of logarithmic density can be rewritten using 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 not having asymptotic density is the set of all numbers with the first digit 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$ there exists 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]).

Title	inequality of logarithmic and asymptotic density
Canonical name	InequalityOfLogarithmicAndAsymptoticDensity
Date of creation	2014-03-24 9:16:11
Last modified on	2014-03-24 9:16:11
Owner	kompik (10588)
Last modified by	kompik (10588)
Numerical id	8
Author	kompik (10588)
Entry type	Theorem
Classification	msc 11B05
Related topic	AsymptoticDensity
Related topic	LogarithmicDensity