Density

There are many different mathematical definitions of density. The most common is asymptotic density, which does not exist for all sequences. Consequently a number of other densities have been developed to fill those gaps or to serve different purposes. Although some types may generalize further, this article is about densities on subsets of the natural numbers.

Asymptotic density

Asymptotic density (or natural density) is a common way to measure the size of a subset of the natural numbers.

The lower asymptotic density $\underset{\_}{d}$ of a set $A\subset \mathbb{\mathbb{N}}$ is defined as

$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{1}{n}\sum _{i=1}^n{\chi }_A(i)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\sum _{a\in A,1\le a\le n}\frac{1}{n},$

and the upper asymptotic density $\bar{d}$ of a set $A\subset \mathbb{\mathbb{N}}$ is defined as

$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{1}{n}\sum _{i=1}^n{\chi }_A(i)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\sum _{a\in A,1\le a\le n}\frac{1}{n},$

where ${\chi }_A(i)$ is the characteristic function of the set $A\subset \mathbb{\mathbb{N}}$.

Both exist for all sets $A\subset \mathbb{\mathbb{N}}.$ If the two are equal, the asymptotic density $d(A)$ is said to exist and is equal to both.

The asymptotic density is finitely additive when it exists. In particular, for disjoint sets $A$ and $B$, we have

$\underset{\_}{d}(A)+\underset{\_}{d}(B)\le \underset{\_}{d}(A\cup B)\le \underset{\_}{d}(A)+\bar{d}(B)\le \bar{d}(A\cup B)\le \bar{d}(A)+\bar{d}(B).$

Szemerédi's theorem shows that if a set has positive upper asymptotic density, then it contains arbitrarily long arithmetic progressions.

Let $R=\{a/b:a,b\in A\}$ be the set of fractions of $A$. If $A$ has positive asymptotic density, then $R$ is (topologically) dense in the positive reals. If $R$ is not dense in the reals then $A$ has lower asymptotic density less than 1/2 and upper asymptotic density less than 1; and any such lower or upper density is achievable.

Relative density

Sometimes it is natural to look not at the density compared to all natural numbers but to some base set. For example, the asymptotic density of the primes which are 1 mod 3 is 0 but it would be useful for this to be 1/2 in some sense. Relative density simply divides by the number of members of the base set up to $n$ rather than by $n$. It is thus a generalization of asymptotic density, the special case where the base set is $\mathbb{\mathbb{N}}.$ Most densities can be specialized in a natural way to a relative density of some kind, but when used without quantification "relative density" always means relative asymptotic density.

Logarithmic density

Compared to asymptotic density, logarithmic density is less sensitive to certain perturbations and hence may exist when the asymptotic density does not. If the asymptotic density does exist, so does the logarithmic density and the two are equal.

The lower logarithmic density of a set $A\subset \mathbb{\mathbb{N}}$ is defined as

$\underset{\_}{\delta }(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{1}{\log n}\sum _{i=1}^n\frac{{\chi }_A(i)}{i}=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{1}{\log n}\sum _{a\in A,a\le n}\frac{1}{a},$

where ${\chi }_A(i)$ is the characteristic function of the set $A\subset \mathbb{\mathbb{N}}$.

The upper logarithmic density $\bar{\delta }(A)$ is obtained analogously. If both exist then the logarithmic density $\delta (A)$ exists and is equal to both.

Logarithmic density is related to asymptotic density by

$0\le \underset{\_}{d}(A)\le \underset{\_}{\delta }(A)\le \bar{\delta }(A)\le \bar{d}(A)\le 1.$

There exist sequences which have any chosen values as the logarithmic and asymptotic densities, provided they meet these inequalities.

Although the multiples of a set of positive integers may have no asymptotic density, it has logarithmic density equal to its lower asymptotic density. (This is of course positive if the set is nonempty.)

If the fractions $\{a/b:a,b\in A\}$ are not dense in the positive real numbers, $A$ cannot have upper (or lower) logarithmic density greater than or equal to 1/2; for any $0\le r<1/2$ there is such a set with logarithmic density (and hence lower and upper logarithmic density) equal to $r$.

The Dirichlet density, also known as the analytic density or zeta density, is defined as

$\underset{\sigma \to 1^{+}}{\lim }\zeta (\sigma {)}^{-1}\sum _{a\in A}{a}^{-\sigma },$

or equivalently

$\underset{\sigma \to 1^{+}}{\lim }(\sigma -1)\sum _{a\in A}{a}^{-\sigma },$

with upper and lower Dirichlet densities defined as usual by replacing the limit with the limit superior and limit inferior, respectively.

The Dirichlet density is identical to the logarithmic density: one exists if and only if the other does, and their values are equal. It is commonly used in multiplicative number theory where it is often more convenient to calculate.

Generalized densities

Grekos defines a family of densities by

$\overline{d_h}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{1}{h(n)}h\left(\sum _{a\in A,a\le n}1\right),$

and as usual for $\underset{\_}{d_h}(A)$ and $d_h(A),$ where $h$ is an unbounded increasing function on $[0,\mathrm{\infty }).$

Exponential density

This is the special case $h=\log$. This density has the property that the $k$-th powers have exponential density $1/k$, hence the name.

Multiplicative density

The multiplicative density was defined by Davenport & Erdős and is defined as

$\underset{x\to \mathrm{\infty }}{\lim }\left(\prod _{p\le x}(1-\frac{1}{p})\right)\left(\sum _{k\in A,kx\text{-smooth}}\frac{1}{k}\right),$

if this limit exists.

Uniform density

The uniform density (or Banach density) shows the extent of the variability of the sequence.

Define

$\bar{u}(A)=\underset{s}{\lim }\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\sum _{a\in A,n<a\le n+s}\frac{1}{s},$

$\underset{\_}{u}(A)=\underset{s}{\lim }\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\sum _{a\in A,n<a\le n+s}\frac{1}{s}.$

While logarithmic density is less sensitive than asymptotic density, uniform density is more sensitive; the three are related by

$0\le \underset{\_}{u}(A)\le \underset{\_}{d}(A)\le \underset{\_}{\delta }(A)\le \bar{\delta }(A)\le \bar{d}(A)\le \bar{u}(A)\le 1.$

Of course if the uniform density $\underset{\_}{u}(A)=u(A)=\bar{u}(A)$ exists it is equal to the asymptotic and logarithmic densities.

A set with upper uniform density 1 is called thick. A set is syndetic if and only if it has positive lower uniform density.

Schnirelmann density

Schnirelmann introduced a concept of density useful in additive combinatorics. The Schnirelmann density $\sigma$ is defined as

$\sigma (A)=\underset{n}{\inf }\frac{1}{n}\sum _{a\in A,a\le n}1,$

and the upper Schnirelmann density $\bar{\sigma }$ can be defined analogously as

$\bar{\sigma }(A)=\underset{n}{\sup }\frac{1}{n}\sum _{a\in A,a\le n}1,$

though this is rarely used. Note that the two are never equal except for $\sigma (\mathbb{\mathbb{N}})=1=\bar{\sigma }(\mathbb{\mathbb{N}})$: $0\le \sigma (A)<\bar{\sigma }(A)\le 1$ for all $A⊊\mathbb{\mathbb{N}}$. Further, the asymptotic densities are bounds:

$\sigma (A)\le \underset{\_}{d}(A)\le \bar{d}(A)\le \bar{\sigma }(A)$ (at least one of the inequalities being strict).

Mann's theorem states that

$\sigma (A+B)\ge \min (\sigma (A)+\sigma (B),1).$

Here the + on the left denotes Minkowski addition. Lepson shows that this is the best possible result in that equality can be obtained for any choice of $\sigma (A),\sigma (B).$

Niven shows that

$\sigma (\{b_{a_i}\})\ge \sigma (\{a_i\})\sigma (\{b_i\})$.

Divisor density

A subset S of the positive integers has divisor density z if for almost all n it holds that

$\frac{\sum _{d|n,d\in S}1}{\sum _{d|n}1}\sim z$

(where ~ is as n increases without bound).

For any $\alpha \in [0,1]$ and any $\beta \in [0,1]$ there is a set S with divisor density α and logarithmic density β, and this remains true if one or both are replaced with "undefined".

Other densities

• Lacunary density
• Mean density, Abel density, Poisson density, logarithmic block density
• Ψ-density

Properties

It seems reasonable to require that for any density $D,D(A)\le D(B)$ when $A\subseteq B.$ Further, $D(\mathrm{\varnothing })=0$ and $D(\mathbb{\mathbb{N}})=1.$

Grekos suggests four properties which may be desirable:

1. Translation invariance: $D(A)=D(A+\{k\})$ for any $k$, where + is the Minkowski sum.
2. Homogeneity: $D(A)=k\cdot D(kA)$, where $nS$ denotes $\{ns:s\in S\}.$
3. Finiteness: If $A$ is finite, then $D(A)=0.$
4. Finite additivity: If $A$ and $B$ are disjoint then $D(A)+D(B)=D(A\cup B).$

Note that axioms 3 and 4 together imply

3a. If the symmetric difference $(A\setminus B)\cup (B\setminus A)$ is finite, then $D(A)=D(B).$

Note also that sigma additivity, a strengthening of #4, is not possible in this setting. Sigma-additivity, together with finiteness, yields $D(\mathbb{\mathbb{N}})=0.$

Axioms 1 and 2 mean that homothetic transformations have the expected densities. If they are replaced with

1a. $D(A\cap B)=\min (D(A),D(B))$

then the result is a nonprincipal ultrafilter.

Cite this page as

Charles R Greathouse IV, Density. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki.Available at https://oeis.org/wiki/Density