Refine
Document Type
- diplomthesis (2)
- Book (1)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Institute
- Informatik (2)
- Mathematik (1)
Über die Anzahlfunktion π(x)
(1999)
Bereits Euklid wusste, dass es unendlich viele Primzahlen gibt. Euler zeigte die qualitative Aussage ¼(x) x ! 0 bei x ! 1. Legendre definierte als erster die Anzahlfunktion ¼(x) als die Anzahl aller Primzahlen · x, (x 2 R) und vermutete irrtümlicherweise, dass ¼(x) = x log(x)¡B; wobei lim x!1 B(x) = 1; 083 66 : : : ist. Gauss vermutete, dass die Funktionen ¼(x) und li(x) := lim "!0 ">0 0@ u=1¡" Z u=0 du log(u) + u=x Z u=1+" du log(u)1A asymptotisch Äquivalent sind. Tschebyschew konnte die Legendresche Vermutung widerlegen; außerdem bewies er: Wenn der Grenzwert lim x!1 ¼(x) x log(x) existiert, so muss dieser gleich 1 sein. Dank wegweisender Vorarbeiten von Riemann, gelang es im Jahr 1896 unabhängig voneinander und nahezu zeitgleich Hadamard und De La Vallee Poussin, den Primzahlsatz analytisch zu beweisen. Beide verwendeten entscheidend die Tatsache, dass die Zetafunktion ³ in der Halbebene Re(s) ¸ 1 nicht verschwindet. Die Beweise waren zuerst so lang und kompliziert, dass sie heutzutage nur noch einen historischen Wert besitzen. Es dauerte weitere 84 Jahre bis der Beweis so vereinfacht werden konnte, dass er nur wenige Seiten in Anspruch nimmt. Ein wichtiger Verdienst kommt hierbei der Arbeit von Newman aus dem Jahre 1980 zu. Lange Zeit wurde es für kaum möglich gehalten, einen Beweis des Primzahlsatzes zu finden, der ohne eine gewisse Kenntnis der komplexen Nullstellen der Zetafunktion auskommt. Und doch glückte 1948 ein solcher Beweis durch Selberg und Erdös mit elementaren Mitteln. Erwähnenswert dabei, dass der Beweis noch lange nicht einfach ist. Uns schienen die analytischen Beweise durchsichtiger zu sein. Daher haben wir in dieser Arbeit auf einen elementaren Beweis verzichtet. Der analytischen Weg zum Primzahlsatz von Newman kommt einerseits mit Integration längs endlicher Wege (und der Tatsache ³(s) 6= 0 in ¾ ¸ 1) aus, umgeht also Abschätzungen bei 1; andererseits ist er frei von Sätzen der Fourier-Analysis. Beim Beweis des Primzahlsatzes von Wolke benutzt man anstelle von ³0(s) ³(s) die Funktion ³ 1 k mit großen k. Wegen des Pols bei s=1 bringt dies bei der Integration leichte Komplikationen, hat aber den Vorteil, dass außer der Nullstellen-Freiheit keine nichttriviale Abschätzung für ³ oder ³0 erforderlich ist. Dank der elementaren Äquivalenz zwischen dem Primzahlsatz und der Konvergenz von 1Pn=1 ¹(n) n brauchte Newman nur die Konvergenz von 1Pn=1 ¹(n) n zu zeigen. Dies erreichte er mit Hilfe seines Konvergenzsatzes. Die Legendresche Formel, die auf dem Sieb des Eratosthenes basiert, erlaubt die exakte Berechnung von ¼(x), wenn alle px nicht übersteigenden Primzahlen bekannt sind. Diese prinzipielle Möglichkeit zur Ermittlung von ¼(x) ist in der Praxis natürlich stark limitiert durch die mit x rasch anwachsende Anzahl der rechts in der Legendresche Formel zu berücksichtigenden Summanden. Mit verfeinerten Siebtechniken haben verschiedene Autoren zur Legendresche Formel analoge Formeln ¼(x) ersonnen, bei denen der genannte Nachteil von Legendresche Formel sukzessive reduziert wurde. Zu erwähnen sind hier vor allem Meissel, Lehmer, sowie Lagarias, Miller und Odlyzko. Aus den Graphen von R(x)¡¼(x); li(x)¡¼(x) und x log(x) ¡¼(x) für den betrachteten Bereich x · 1018 konnten wir feststellen, dass R(x); li(x) sowie x log(x) die Anzahlfunktion Pi (x) annähern, wobei R(x) die beste Approximation für Pi(x) von allen drei ist.
In dieser Arbeit definieren wir ein Maß für den Grad der Mehrdeutigkeit (degree of ambiguity da) kontextfreier Grammatiken und Sprachen als die Anzahl der Ableitungsbäume in Abhängigkeit von der Länge n eines Wortes. Wir zeigen, dass es weder Sprachen noch zyklenfreie Grammatiken gibt, deren Mehrdeutigkeitsgrad stärker als 2£(n) wächst (wie z B. £(nn)). Aus [10] ist es außerdem bekannt, dass es keine Grammatiken (und somit keine Sprachen) gibt, deren Mehrdeutigkeit stärker als polynomiell, aber schwächer als exponentiell wächst (wie z. B. £(2pn). Deshalb untersuchen wir in dieser Arbeit hauptsächlich konstant mehrdeutige, polynomiell mehrdeutige und exponentiell mehrdeutige Grammatiken und Sprachen. Für jede feste, ganze Zahl k 2 N hat Maurer [8] die Existenz einer k-deutigen kontextfreien Sprache nachgewiesen. Durch Verwendung einer einfacheren Sprache, nämlich der Sprache Lk := fambm1 1 bm2 2 : : : bmk k jm;m1;m2; : : : ;mk ¸ 1; 9 i mit m = mig, und mit Hilfe von Ogden's Lemma1 erhalten wir einen wesentlich kürzeren Beweis. Ferner zeigen wir die Existenz exponentiell mehrdeutiger Sprachen. Wir zeigen, dass die Sprache L¤ { wobei L = faibicj ji; j ¸ 1g [ faibjciji; j ¸ 1g-exponentiell mehrdeutig ist, indem wir beweisen, dass das Wort (ah+h!bh+h!ch+h!)k mindestens 2k Ableitungen in jeder Grammatik G für L¤ hat, wobei k aus N ist und h die Konstante aus Ogden's Lemma für G ist. Für beliebig kleines c aus R+ entwerfen wir eine Grammatik Gc für L¤, so dass daGc · 2cn gilt. Somit gilt, dass die Sprache L¤ zwar exponentiell mehrdeutig ist, aber es gibt kein festes c aus R+ , so dass L¤ 2cn-deutig ist. Wir geben polynomiell mehrdeutige Grammatiken an und zeigen die Existenz von polynomiell mehrdeutigen Sprachen, indem wir mit Hilfe von Ogden's Lemma beweisen, dass die Anzahl der Ableitungsbäume eines Wortes der Länge n in jeder Grammatik für die Sprache Lk in der Größenordnung von (nk) liegt, wobei k eine Konstante aus N ist, und L := fambm1cbm2c : : : bmpcjp 2 N; m;m1;m2; : : : ;mp 2 N; 9i 2 f1; 2; : : : ; pg mit m = mig gilt. Durch Angabe einer O(nk){deutigen Grammatik zeigen wir schließlich, dass Lk polynomiell vom Grad k mehrdeutig ist. Außerdem entwerfen wir für jedes feste d aus R+ eine Grammatik Gd für L, so dass daGd · dn dn für genügend großes n ist.
