Natural density

Natural density

In number theory, asymptotic density (or natural density or arithmetic density) is one of the possibilities to measure how large a subset of the set of natural numbers is.

Intuitively, we think that there are "more" positive integers than perfect squares, since every perfect square is already positive, and many other positive integers exist besides. However, the set of positive integers is not in fact "bigger" than the set of perfect squares: both sets are infinite and countable and can therefore be put in one-to-one correspondence. Clearly, we need a better way to formalize our intuitive notion.

If we pick randomly an integer from the set [1,n], then the probability that it belongs to A is the ratio of the number of elements of A in [1,n] to the total number of elements in [1,n]. If this probability tends to some limit as n tends to infinity, then we call this limit the asymptotic density of A. We see that this notion can be understood as a kind of probability of choosing a number from the set A. Indeed, the asymptotic density (as well as some other types of densities) is studied in probabilistic number theory.

Asymptotic density contrasts, for example, with the Schnirelmann density. A drawback of this approach is that the asymptotic density is not defined for all subsets of \mathbb{N}.

Contents

Definition

A subset A of positive integers has natural density (or asymptotic density) α, where

0 ≤ α ≤ 1,

if the proportion of elements of A among all natural numbers from 1 to n is asymptotic to α as n tends to infinity.

More explicitly, if one defines for any natural number n the counting function a(n) as the number of elements of A less than or equal to n, then the natural density of A being α exactly means that

a(n)/n → α as n → +∞.

Upper and lower asymptotic density

Let A be a subset of the set of natural numbers \mathbb{N}=\{1,2,\ldots\}. For any n \in \mathbb{N} put A(n)=\{1,2,\ldots,n\} \cap A. and a(n) = | A(n) | .

Define the upper asymptotic density \overline{d}(A) of A by

 \overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{a(n)}{n}

where lim sup is the limit superior. \overline{d}(A) is also known simply as the upper density of A.

Similarly, we define \underline{d}(A), the lower asymptotic density of A, by

 \underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{ a(n) }{n}

One may say A has asymptotic density d(A) if \underline{d}(A)=\overline{d}(A), in which case we put d(A)=\overline{d}(A).

This definition can be restated in the following way:

 d(A)=\lim_{n \rightarrow \infty} \frac{a(n)}{n}

if the limit exists.

A somewhat weaker notion of density is upper Banach density; given a set A \subseteq \mathbb{N}, define d * (A) as

 d^*(A) = \limsup_{N-M \rightarrow \infty} \frac{| A \bigcap \{M, M+1, ... , N\}|}{N-M+1}

If one were to write a subset of \mathbb{N} as an increasing sequence

 A=\{a_1<a_2<\ldots<a_n<\ldots; n\in\mathbb{N}\}

then

\underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{n}{a_n},
\overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{n}{a_n}

and d(A) = \lim_{n \rightarrow \infty} \frac{n}{a_n} if the limit exists.

Examples

  • If d(A) exists for some set A, then for the complement set we have d(Ac) = 1 - d(A).
  • Obviously, d(N) = 1.
  • For any finite set F of positive integers, d(F) = 0.
  • If A=\{n^2; n\in\mathbb{N}\} is the set of all squares, then d(A) = 0.
  • If A=\{2n; n\in\mathbb{N}\} is the set of all even numbers, then d(A) = 1/2. Similarly, for any arithmetical progression A=\{an+b; n\in\mathbb{N}\} we get d(A) = 1/a.
  • For the set P of all primes we get from the prime number theorem d(P) = 0.
  • The set of all square-free integers has density \tfrac{6}{\pi^2}
  • The density of the set of abundant numbers is known to be between 0.2474 and 0.2480.
  • The set A=\bigcup\limits_{n=0}^\infty \{2^{2n},\ldots,2^{2n+1}-1\} of numbers whose binary expansion contains an odd number of digits is an example of a set which does not have an asymptotic density, since the upper density of this set is
\overline d(A)=\lim_{m \rightarrow \infty} \frac{1+2^2+\cdots +2^{2m}}{2^{2m+1}-1}
= \lim_{m \rightarrow \infty} \frac{2^{2m+2}-1}{3(2^{2m+1}-1)}
= \frac 23\, ,
whereas its lower density is
\underline d(A)=\lim_{m \rightarrow \infty} \frac{1+2^2+\cdots +2^{2m}}{2^{2m+2}-1}
= \lim_{m \rightarrow \infty} \frac{2^{2m+2}-1}{3(2^{2m+2}-1)}
= \frac 13\, .
A_x:=\{n\in\mathbb{N}\,:\, \alpha_n<x \}\, .
Then, by definition, d(Ax) = x for all x.

References


This article incorporates material from Asymptotic density on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Density (disambiguation) — Density and dense usually refer to a measure of how much of some entity is within a fixed amount of space. Types of density include: In physics, density of mass: Density, mass per volume Area density or surface density, mass over a (two… …   Wikipedia

  • Natural killer cell — Latin lymphocytus K Code TH H2.00.04.1.02006 Natural killer cells (or NK cells) are a type of cytotoxic lymphocyte that constitute a major component of the innate immune system. NK cells play a major role in the rejection of …   Wikipedia

  • Natural Bridge, New York —   CDP   Church in Natural Bridge, NY …   Wikipedia

  • Natural Bridge, Alabama —   Town   …   Wikipedia

  • Density gradient — is a spatial variation in density over an area. The term is used in the natural sciences to describe varying density of matter, but can apply to any quantity whose density can be measured. [1] [2] Contents 1 Aerodynamics 2 …   Wikipedia

  • Natural Steps, Arkansas — Natural Steps   Census designated place   …   Wikipedia

  • Natural gas processing — plants, or fractionators, are used to purify the raw natural gas extracted from underground gas fields and brought up to the surface by gas wells. The processed natural gas, used as fuel by residential, commercial and industrial consumers, is… …   Wikipedia

  • Natural-gas condensate — is a low density mixture of hydrocarbon liquids that are present as gaseous components in the raw natural gas produced from many natural gas fields. It condenses out of the raw gas if the temperature is reduced to below the hydrocarbon dew point… …   Wikipedia

  • Natural gas condensate — is a low density mixture of hydrocarbon liquids that are present as gaseous components in the raw natural gas produced from many natural gas fields. It condenses out of the raw gas if the temperature is reduced to below the hydrocarbon dew point… …   Wikipedia

  • Natural organic matter — (NOM) is broken down organic matter that comes from plants and animals in the environment. [ Natural Organic Matter, GreenFacts, 22 Apr, 2007 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”