References on density of subsets of $\mathbb{N}$

I'm interested in books (maybe chapter(s) of a book), articles, results or whatever on the concept of density of subsets $A \subset \mathbb{N}$, often defined as:

$$\lim_{n \rightarrow \infty} \frac{|A \cap I_{n}|}{n}$$

where $I_{n} = \{1, 2, ..., n\}$. I've also seen the $\limsup$ being taken instead, defined as upper density. I know a few basic results (that I could prove myself) plus some famous results like Szemerédi's theorem. Is there any sort of reference where I could learn about this in greater detail and scheme?

$\newcommand{\N}{\mathbb N} \newcommand{\emps}{\emptyset} \newcommand{\sm}{\setminus} \newcommand{\abs}[1]{|#1|} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\ol}[1]{\overline{#1}} $This notion is called asymptotic density or natural density. If you are using limsup and liminf, it is upper and lower asymptotic density, see e.g. Wikipedia.

Let me start by mentioning some properties of asymptotic density, which I consider useful. Of course any such list is necessarily incomplete, and the choice is matter of opinion. Then I will give several references and I will mention which of these results are contained there.

I will not speak about Szemerédi's theorem - perhaps someone who knows more about this topic will suggest suitable references.

Basic properties

The following results are obtained easily from the definition and properties of limit inferior and limit superior.

$0\leq \ul d(A) \leq \ol d(A) \leq 1$
If $A\subseteq B\subseteq\N$, then $\ul d(A)\leq \ul d(B)$ and $\ol d(A)\leq \ol d(B)$.
If $A,B\subseteq\N$, $A\cap B=\emps$, then $$\ul d(A)+\ul d(B) \leq \ul d(A\cup B) \leq \ul d(A)+\ol d(B) \leq \ol d(A\cup B) \leq \ol d(A)+\ol d(B).$$ Consequently, the asymptotic density is finitely additive.
$\ol d(\N\sm A)=1-\ul d(A)$, $\ul d(\N\sm A)=1-\ol d(A)$ For any $a\in\langle0,1\rangle$ there is a set $A\subseteq\N$ such that $d(A)=a$.

Alternative definitions

As you already mentioned, the asymptotic density is defined by $\underline d(A):=\liminf_{n\to\infty} \frac{A(n)}n$, $\overline d(A):=\limsup_{n\to\infty} \frac{A(n)}n$ and $d(A):=\lim_{n\to\infty} \frac{A(n)}n$, where $A(n):=\abs{A\cap\{1,2,\ldots,n\}}$.

Sometimes it is useful to know, that there are different expressions. The first one is about a set given by an increasing sequence of positive integers.

Proposition 1. If $A=\{a_1<a_2<\ldots<a_k<\ldots\}\subseteq\N$, then $$ \begin{gather*} \ul d(A)=\liminf_{k\to\infty} \frac k{a_k}\\ \ol d(A)=\limsup_{k\to\infty} \frac k{a_k}\\ d(A)=\lim_{k\to\infty} \frac k{a_k} \end{gather*} $$

Sometimes it is useful to be able to compute densities of set consisting of intervals. For example, this is useful when constructing an example of a set which does not have asymptotic density, i.e., a set $A$ such that $\ul d(A) < \ol d(A)$.

Proposition 2. Let $a_n$, $b_n$ be increasing sequences of positive integers such that $a_n<b_n<a_{n+1}$ for each $n\in\N$. Then for the set $A=\N\cap\bigcup\limits_{n=1}^\infty (a_n,b_n\rangle$ we have \begin{gather*} \ol d(A):=\limsup_{n\to\infty} \frac{A(b_n)}{b_n}\\ \ul d(A):=\liminf_{n\to\infty} \frac{A(a_n)}{a_n} \end{gather*}

However, both these results are relatively easy to show.

Density of some special sets

Theorem 3. If $A=\{a_1<a_2<\ldots<a_n<\ldots\}\subseteq\N$ and the series $\sum_{k=1}^\infty \frac 1{a_k}$ converges, then the set $A$ has asymptotic density and $d(A)=0$.

A proof of this result can be found at this site, see this question.

Theorem 4. Let $\mathbb P$ denote the set of all prime numbers. Then $d(\mathbb P)=0$.

A very nice proof of can be found in Pete L. Clark's and robjohn's answers here.

Comparison with other densities

Some other densities are often studied in number theory. I will mention two of them: logarithmic density and Banach density (also called uniform density).

Let us denote $S(n):=\sum\limits_{k=1}^n \frac 1k$ for any $n\in\N$. Let $A\subseteq\N$. Then the values $$\ul \delta(A)=\liminf_{n\to\infty} \frac{\sum\limits_{k\in A; k\leq n} \frac 1k}{S(n)} \qquad \ol \delta(A) = \limsup_{n\to\infty} \frac{\sum\limits_{k\in A; k\leq n} \frac 1k}{S(n)}$$ are called upper and lower logarithmic density of the set $A$. If $\ol\delta(A)=\ul\delta(A)$, then this value is denoted by $\delta(A)$ and called the logarithmic density of the set $A$.

Theorem 5. For any subset $A\subseteq\N$ the inequality $$\ul d(A) \leq \ul \delta (A) \leq \ol \delta(A) \leq \ol d(A)$$ holds. Consequently, if a set has asymptotic density, it also has logarithmic density.

See e.g. the proof at Planetmath.

Banach (uniform) density is defined as follows: $$\overline u(A)=\lim_{s\to\infty} \max_{t\ge 0}\frac{A(t+1,t+s)}{s}$$ $$\underline u(A)=\lim_{s\to\infty} \min_{t\ge 0}\frac{A(t+1,t+s)}{s}$$ where $A(m,k)=|A\cap\{m,m+1,\dots,k\}|$.

If these values are the same, then $u(A)=\ol u(A)=\ul u(A)$.

Theorem 6. The inequalities $$\underline u(A)\le \underline d(A) \le \overline d(A) \le \overline u(A)$$ hold for every $A\subseteq\N$. (Consequently, every set that has uniform density also has asymptotic density.)

The proof of these inequalities can be found e.g. in: Z. Gáliková, B. Lászlo and T. Šalát: Remarks on uniform density of sets of integers (Wayback Machine).

Note: Several equivalent definitions of Banach density appear in literature.

Niven's result

The following result is from the paper Ivan Niven. The asymptotic density of sequences. Bull. Amer. Math. Soc., 57(6):420-434, 1951. Often it can be used to show that asymptotic density of some set is $0$.

Theorem 7. If for a set of primes $\{p_i\}$ we have $d(A_{p_i})=0$ for every $i$, and if $\sum p_i^{-1}=\infty$ then $d(A)=0$.

Here, for any $A\subseteq\mathbb N$ and a prime $p$, the set $A_p$ is defined as $$A_p=\{n\in A; p\mid n, p^2\nmid n\}.$$

Note: If we defined $A_p=\{n\in A; p\mid n\}$ instead of the above result, we would get a weaker result, but the proof is much simpler.

Some references:

• J. Steuding: Probabilistic number theory. Contains Proposition 1, Theorem 5 (CiteSeerX and Wayback Machine)

• Niven I., Zuckerman H.S., Montgomery H.L. An introduction to the theory of numbers (5ed., Wiley, 1991). Chapter 11 is devoted to asymptotic and Schnirelmann density. It contains Proposition 1 and several basic facts on asymptotic density are left as exercises.

• Halberstam H., Roth K.F. Sequences. Asymptotic density and logarithmic are studied in Chapter V. Theorem 3 and Theorem 5 and many further results on asymptotic density are shown here. This books was mentioned in Matthew Conroy's comment above. The Schnirelmann's density, which is connected to some results in additive number theory, is studied here too.

• G. Tenenbaum: Introduction to analytic and probabilistic number theory. Contains e.g. Proposition 1, Theorem 5. Several results on asymptotic density (e.g. Theorem 3) are left as exercises. This books was mentioned in Matthew Conroy's comment above.

• Erdos P., Suranyi J. Topics in the Theory of Numbers (Springer 2003). Some basic facts on asymptotic density are mentioned here, mostly left as exercises. E.g. Theorem 3, Theorem 4.

• A. Geroldinger, I. Ruzsa: Combinatorial Number Theory and Additive Group Theory. The authors work mostly with Schnirelmann's density. However, asymptotic density is briefly mentioned, too.