The asymptotic density is a number-theoretic limit that indicates the proportion of a subset of natural numbers in the set of natural numbers.
Simple definition
One calls the limit value
lim
n
→
∞
a
(
n
)
n
{\ displaystyle \ lim _ {n \ rightarrow \ infty} {\ frac {a (n)} {n}}}
the asymptotic density of a subset . It is the counting function of . This indicates how many elements from are not larger than . It applies .
d
(
A.
)
{\ displaystyle d (A)}
A.
⊆
N
{\ displaystyle A \ subseteq \ mathbb {N}}
a
(
n
)
{\ displaystyle a (n)}
A.
{\ displaystyle A}
A.
{\ displaystyle A}
n
{\ displaystyle n}
0
≤
d
(
A.
)
≤
1
{\ displaystyle 0 \ leq d (A) \ leq 1}
Upper and lower asymptotic density
For any one be and .
n
∈
N
{\ displaystyle n \ in \ mathbb {N}}
A.
(
n
)
=
{
1
,
2
,
...
,
n
}
∩
A.
{\ displaystyle A (n) = \ {1,2, \ dotsc, n \} \ cap A}
a
(
n
)
=
|
A.
(
n
)
|
{\ displaystyle a (n) = | A (n) |}
The upper asymptotic density of is then through
d
¯
(
A.
)
{\ displaystyle {\ overline {d}} (A)}
A.
{\ displaystyle A}
d
¯
(
A.
)
:
=
lim sup
n
→
∞
a
(
n
)
n
{\ displaystyle {\ overline {d}} (A) \ colon = \ limsup _ {n \ rightarrow \ infty} {\ frac {a (n)} {n}}}
defined, where lim sup is the limes superior . Likewise, it 's through
d
_
(
A.
)
{\ displaystyle {\ underline {d}} (A)}
d
_
(
A.
)
:
=
lim inf
n
→
∞
a
(
n
)
n
{\ displaystyle {\ underline {d}} (A) \ colon = \ liminf _ {n \ rightarrow \ infty} {\ frac {a (n)} {n}}}
defined lower asymptotic density of . has an asymptotic density only if holds. In this case the limit exists
A.
{\ displaystyle A}
A.
{\ displaystyle A}
d
(
A.
)
{\ displaystyle d (A)}
d
_
(
A.
)
=
d
¯
(
A.
)
{\ displaystyle {\ underline {d}} (A) = {\ overline {d}} (A)}
lim
n
→
∞
a
(
n
)
n
=
d
_
(
A.
)
=
d
¯
(
A.
)
=
:
d
(
A.
)
{\ displaystyle \ lim _ {n \ rightarrow \ infty} {\ frac {a (n)} {n}} = {\ underline {d}} (A) = {\ overline {d}} (A) = \ colon d (A)}
and therefore can be defined by him .
d
(
A.
)
{\ displaystyle d (A)}
Examples
If exists for the set , then for the complementary set :
d
(
A.
)
{\ displaystyle d (A)}
A.
{\ displaystyle A}
N
{\ displaystyle \ mathbb {N}}
A.
¯
{\ displaystyle {\ overline {A}}}
d
(
A.
¯
)
=
1
-
d
(
A.
)
{\ displaystyle d ({\ overline {A}}) = 1-d (A)}
d
(
N
)
=
1
{\ displaystyle d (\ mathbb {N}) = 1}
For any finite set of natural numbers we have:
E.
{\ displaystyle E}
d
(
E.
)
=
0
{\ displaystyle d (E) = 0}
The following applies to the set of all square numbers :
A.
=
{
n
2
;
n
∈
N
}
{\ displaystyle A = \ {n ^ {2}; n \ in \ mathbb {N} \}}
d
(
A.
)
=
0
{\ displaystyle d (A) = 0}
The following applies to the set of all even numbers:
A.
=
{
2
n
;
n
∈
N
}
{\ displaystyle A = \ {2n; n \ in \ mathbb {N} \}}
d
(
A.
)
=
1
/
2
{\ displaystyle d (A) = 1/2}
More generally applies to every arithmetic sequence with a positive :
A.
=
{
a
n
+
b
;
n
∈
N
}
{\ displaystyle A = \ {an + b; n \ in \ mathbb {N} \}}
a
{\ displaystyle a}
d
(
A.
)
=
1
/
a
{\ displaystyle d (A) = 1 / a}
For the set of all prime numbers one obtains due to the prime number theorem :
P
{\ displaystyle P}
d
(
P
)
=
0
{\ displaystyle d (P) = 0}
The set of all square-free natural numbers has the density with the Riemann zeta function .
6th
/
π
2
=
1
/
ζ
(
2
)
{\ displaystyle 6 / \ pi ^ {2} = 1 / \ zeta (2)}
ζ
{\ displaystyle \ zeta}
The density of abundant numbers is between 0.2474 and 0.2480.
The set of all numbers whose binary representation has an odd number of digits is an example of a set with no asymptotic density. In this case, the following applies to the lower and upper asymptotic density:
A.
=
⋃
n
=
0
∞
{
2
2
n
,
...
,
2
2
n
+
1
-
1
}
{\ displaystyle A = \ bigcup \ limits _ {n = 0} ^ {\ infty} \ left \ {2 ^ {2n}, \ dotsc, 2 ^ {2n + 1} -1 \ right \}}
d
_
(
A.
)
=
lim
m
→
∞
1
+
2
2
+
⋯
+
2
2
m
2
2
m
+
2
-
1
=
lim
m
→
∞
2
2
m
+
2
-
1
3
(
2
2
m
+
2
-
1
)
=
1
3
{\ displaystyle {\ underline {d}} (A) = \ lim _ {m \ rightarrow \ infty} {\ frac {1 + 2 ^ {2} + \ dotsb + 2 ^ {2m}} {2 ^ {2m +2} -1}} = \ lim _ {m \ rightarrow \ infty} {\ frac {2 ^ {2m + 2} -1} {3 (2 ^ {2m + 2} -1)}} = {\ frac {1} {3}}}
d
¯
(
A.
)
=
lim
m
→
∞
1
+
2
2
+
⋯
+
2
2
m
2
2
m
+
1
-
1
=
lim
m
→
∞
2
2
m
+
2
-
1
3
(
2
2
m
+
1
-
1
)
=
2
3
{\ displaystyle {\ overline {d}} (A) = \ lim _ {m \ rightarrow \ infty} {\ frac {1 + 2 ^ {2} + \ dotsb + 2 ^ {2m}} {2 ^ {2m +1} -1}} = \ lim _ {m \ rightarrow \ infty} {\ frac {2 ^ {2m + 2} -1} {3 (2 ^ {2m + 1} -1)}} = {\ frac {2} {3}}}
swell
Melvyn B. Nathanson: Elementary methods in number theory (= Graduate Texts in Mathematics . Volume 195 ). Springer, New York 2000, ISBN 0-387-98912-9 (English, zbmath.org ).
Hans-Heinrich Ostmann: Additive number theory (= results of mathematics and its border areas . Volume 7 ). Part One: General Investigations . Springer-Verlag, Berlin / Göttingen / Heidelberg 1956, ISBN 978-3-662-11030-0 ( books.google.de - reading sample).
Jörn Steuding: Probabilistic number theory. (PDF) In: psu.edu. citeseerx.ist.psu.edu, accessed February 7, 2016 .
Gérald Tenenbaum: Introduction to analytic and probabilistic number theory (= Cambridge studies in advanced mathematics . Volume 46 ). Cambridge university press, Cambridge 1995, ISBN 0-521-41261-7 (French, zbmath.org ).
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">