Asymptotische Dichte

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die asymptotische Dichte ist ein zahlentheoretischer Grenzwert, der den Anteil einer Untermenge natürlicher Zahlen an der Menge natürlicher Zahlen angibt.

Einfache Definition[Bearbeiten]

Man nennt den Grenzwert

\lim_{n \rightarrow \infty} \frac{a(n)}{n}

die asymptotische Dichte d(A) einer Untermenge A \subseteq \N. Dabei ist a(n) die Zählfunktion von A. Diese gibt an, wie viele Elemente aus A nicht größer als n sind. Es gilt 0 \leq d(A) \leq 1.

Obere und untere asymptotische Dichte[Bearbeiten]

Für ein beliebiges n \in \mathbb{N} sei A(n)=\{1,2,\ldots,n\} \cap A und a(n)=|A(n)|.

Die obere asymptotische Dichte \overline{d}(A) von A ist dann durch

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

definiert, wobei lim sup der Limes superior ist. Ebenso ist \underline{d}(A) die durch

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

definierte untere asymptotische Dichte von A. A hat nur dann eine asymptotische Dichte d(A), wenn \underline{d}(A)=\overline{d}(A) gilt. In diesem Fall existiert der Grenzwert

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

und daher kann durch ihn d(A) definiert werden.

Beispiele[Bearbeiten]

  • Wenn d(A) für die Menge A existiert, dann gilt für die bezüglich \N komplementäre Menge \overline{A}: d(\overline{A}) = 1 - d(A)
  • d(\N) = 1
  • Für eine beliebige endliche Menge E natürlicher Zahlen gilt: d(E) = 0
  • Für die Menge A=\{n^2; n\in\mathbb{N}\} aller Quadratzahlen gilt: d(A) = 0
  • Für die Menge A=\{2n; n\in\mathbb{N}\} aller geraden Zahlen gilt: d(A) = 1/2
  • Allgemeiner gilt für jede arithmetische Folge A=\{an+b; n\in\mathbb{N}\} mit positivem a: d(A) = 1/a
  • Für die Menge P aller Primzahlen erhält man aufgrund des Primzahlsatzes: d(P) = 0
  • Die Menge aller quadratfreien natürlichen Zahlen hat die Dichte 6/\pi^2=1/\zeta(2) mit der Riemannschen Zetafunktion \zeta.
  • Die Dichte abundanter Zahlen liegt zwischen 0.2474 und 0.2480.
  • Die Menge A=\bigcup\limits_{n=0}^\infty \{2^{2n},\ldots,2^{2n+1}-1\} aller Zahlen, deren Binärdarstellung eine ungerade Anzahl an Stellen hat, ist ein Beispiel für eine Menge ohne asymptotische Dichte. Für die untere und obere asymptotische Dichte gilt in diesem Fall:
\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
\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

Quellen[Bearbeiten]