Zum Inhalt springen

Asymptotische Dichte

aus Wikipedia, der freien Enzyklopädie

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

Asymptotische Dichte

Sei <math>A \subseteq \N</math> und definiere die Zählfunktion

<math>a(n):=|\{a\leq n:a\in A\}|</math>

für ein <math>n\in \mathbb{N}</math>, wobei <math>|\cdot|</math> die Mächtigkeit bezeichnet.

Falls der Grenzwert

<math>d(A):=\lim_{n \rightarrow \infty} \frac{a(n)}{n}</math>

existiert, so nennt man ihn die asymptotische Dichte von <math>A</math>. Es gilt <math>0 \leq d(A) \leq 1</math>.

Erläuterungen

Bei der asymptotischen Dichte handelt es sich um einen Spezialfall einer allgemeinen Dichte von der Form

<math>D(A)=\lim\limits_{n\to \infty}\sum\limits_{a\leq n, a\in A}\lambda_{a}/\sum\limits_{x\leq n}\lambda_{x}.</math>

Die asymptotische Dichte erhält man bei der Wahl <math>\lambda_x=1</math> für alle <math>x\geq 1</math>.

Eine weitere übliche Dichtefunktion ist die logarithmische Dichte <math>\delta(A)</math>, welche man durch die Wahl <math>\lambda_x=1/x</math> für alle <math>x\geq 1</math> erhält. Für den natürlichen Logarithmus gilt

<math>\sum\limits_{k=1}^n\frac{1}{k}\approx\log(n)+\gamma</math>

wobei <math>\gamma</math> die Euler-Mascheroni-Konstante bezeichnet. Somit definiert man die logarithmische Dichte als

<math>\delta(A)=\lim\limits_{n\to \infty}\frac{1}{\log(n)}\sum\limits_{a\leq n, a\in A}\frac{1}{a},</math>

falls sie existiert.

Obere und untere asymptotische Dichte

Die obere asymptotische Dichte <math>\overline{d}(A)</math> von <math>A</math> ist durch

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

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

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

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

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

und daher kann durch ihn <math>d(A)</math> definiert werden.

Beispiele

  • Wenn <math>d(A)</math> für die Menge <math>A</math> existiert, dann gilt für die bezüglich <math>\N</math> komplementäre Menge <math>\overline{A}</math>: <math>d(\overline{A}) = 1 - d(A)</math>
  • <math>d(\N) = 1</math>
  • Für eine beliebige endliche Menge <math>E</math> natürlicher Zahlen gilt: <math>d(E) = 0</math>
  • Für die Menge <math>A=\{n^2; n\in\mathbb{N}\}</math> aller Quadratzahlen gilt: <math>d(A) = 0</math>
  • Für die Menge <math>A=\{2n; n\in\mathbb{N}\}</math> aller geraden Zahlen gilt: <math>d(A) = 1/2</math>
  • Allgemeiner gilt für jede arithmetische Folge <math>A=\{an+b; n\in\mathbb{N}\}</math> mit positivem <math>a</math>: <math>d(A) = 1/a</math>
  • Für die Menge <math>P</math> aller Primzahlen erhält man aufgrund des Primzahlsatzes: <math>d(P) = 0</math>
  • Die Menge aller quadratfreien natürlichen Zahlen hat die Dichte <math>6/\pi^2=1/\zeta(2)</math> mit der Riemannschen Zetafunktion <math>\zeta</math>.
  • Die Dichte abundanter Zahlen liegt zwischen 0,2474 und 0,2480.
  • Die Menge <math>A=\bigcup\limits_{n=0}^\infty \left\{2^{2n},\dotsc,2^{2n+1}-1\right\}</math> 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:
<math>\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 13</math>

<math>\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 23</math>

Quellen

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf}}%7C%7C}}}}{{#if:Probabilistic number theory|{{#if:{{#invoke:WLink|isValidLinktext|1=Probabilistic number theory|lines=0}}||}}}}{{#if: psu.edu| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=psu.edu}}}}{{#if: citeseerx.ist.psu.edu| citeseerx.ist.psu.edu{{#if: |,|{{#if: 2016-02-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format||noerror=1}}
            |{{#invoke:DateTime|format||T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=|class=Zitationswartung}} }}{{#if: |,|{{#if: 2016-02-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2016-02-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:citeseerx.ist.psu.edu|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:2715274||(?)}}}}}}{{#if: 2016-02-07|;}}}}{{#if: 2016-02-07| {{#if:citeseerx.ist.psu.edu{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2016-02-07 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2016-02-07|class=Zitationswartung}} }} {{#invoke:DateTime|format|2016-02-07|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:psu.educiteseerx.ist.psu.edu{{#if: 2016-02-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if:PDF | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2016-02-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf
      | {{#if:{{#invoke:URLutil|isWebURL|http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf
       | {{#if:{{#invoke:URLutil|isWebURL|http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf
      | {{#if:{{#invoke:URLutil|isWebURL|http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf
       | {{#if:{{#invoke:URLutil|isWebURL|http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.4755&rep=rep1&type=pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}

  • {{#invoke:Vorlage:Literatur|f}}
Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Asymptotische_Dichte&oldid=2715274“