Natural density - Citizendia

In number theory, asymptotic density or natural density is one of the possibilities to measure how large is a subset of the set of natural numbers $\mathbb{N}$ . Number theory is the branch of Pure mathematics concerned with the properties of Numbers in general and Integers in particular as well as the wider classes In Mathematics, the term small set may refer to Small set (category theory Small set (combinatorics See In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an

Intuitively, we feel that there are "more" odd numbers than perfect squares; however, the set of odd numbers 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. In Mathematics, the parity of an object states whether it is even or odd In Mathematics, a square number, sometimes also called a Perfect square, is an Integer that can be written as the square of some other Infinity (symbolically represented with ∞) comes from the Latin infinitas or "unboundedness In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property Clearly, we need a better way to formalize our intuitive notion.

If we pick randomly a number from the set $\{1,2,\ldots,n\}$ , then the probability that it belongs to A is the ratio of the number of elements in the set $A\cap\{1,2,\ldots,n\}$ and 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 the probabilistic number theory. Probabilistic number theory is a subfield of Number theory, which uses explicitly Probability to answer questions of number theory

Asymptotic density contrasts, for example, with the Schnirelmann density. In Mathematics, the Schnirelmann density of a Sequence of numbers is a way to measure how "dense" the sequence is A drawback of this approach is that the asymptotic density is not defined for all subsets of $\mathbb{N}$ . Asymptotic density is also called arithmetic density.

1 Definition
- 1.1 Upper and lower asymptotic density
2 Examples
3 References

Definition

A sequence

a₁, a₂, . . . , a_n, . . . . .

with the a_j positive integers and

a_j < a_j+1 for all j,

has natural density (or asymptotic density) α, where

0 ≤ α ≤ 1,

if the proportion of natural numbers included as some a_j is asymptotic to α. In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an In pure and Applied mathematics, particularly the Analysis of algorithms, real analysis and engineering asymptotic analysis is a method of describing

More formally, if we define the counting function A(x) as the number of a_j's with

a_j < x

then we require that

A(x) ~ αx as x → +∞. The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function

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.$

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

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

$\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}$

We 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 \subset \mathbb{N}$ , define $d * (A)$ as

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

If we 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

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) = ¹/₂. 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. In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1

The set of all square free integers has density 6/(pi^2).

The set $A=\bigcup\limits_{n=0}^\infty \{3^{2n},\ldots,3^{2n+1}-1\}$ is an example of a set which does not have asymptotic density, since the upper density of this set is $\overline d(A)=\frac 23$ and the lower density is $\underline d(A)=\frac 13$ .

References

M. Kolibiar, A. Legéň, T. Šalát and Š. Znám (1992). Algebra a príbuzné disciplíny. Alfa, Bratislava (in Slovak). ISBN 80-05-00721-3.

H. H. Ostmann (1956). Additive Zahlentheorie I (in German). Berlin-Göttingen-Heidelberg: Springer-Verlag.

Steuding, Jörn. Probabilistic number theory. Retrieved on 2005-10-06. Year 2005 ( MMV) was a Common year starting on Saturday (link displays full calendar of the Gregorian calendar. Events 105 BC - Battle of Arausio: The Cimbri inflict the heaviest defeat on the Roman army of Gnaeus Mallius Maximus

G. Tenenbaum (1995). Introduction to analytic and probabilistic number theory. Cambridge: Cambridge Univ. Press.

This article incorporates material from Asymptotic density on PlanetMath, which is licensed under the GFDL. PlanetMath is a free, collaborative online Mathematics Encyclopedia.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Definition

Upper and lower asymptotic density

Examples

References