≡

Disclaimer

      

Tabelle 3 - Fehleranalyse der Gauss'schen Näherung

n	π(n)	n/ln(n)	err(n)
...
1.000	168	144	24
2.000	303	263	40
...
11.000	1.335	1182	153
12.000	1.438	1277	161
...
101.000	9.673	8765	908
102.000	9.766	8844	922
...
1.001.000	78.573	72449	6124
1.002.000	78.650	72516	6134
...
5.001.000	348.576	324210	24366
5.002.000	348.641	324271	24370
...
15.485.917	1.000.000	935.397	64.604
32.452.883	2.000.000	1.876.398	123.602
49.979.737	3.000.000	2.819.392	180.608
67.867.999	4.000.000	3.763.528	236.472
86.028.221	5.000.000	4.708.666	291.334
104.395.337	6.000.000	5.654.086	345.914
122.949.839	7.000.000	6.600.523	399.477
141.650.981	8.000.000	7.547.120	452.880
160.481.221	9.000.000	8.493.906	506.094
179.424.697	10.000.000	9.440.788	559.212
198.491.369	11.000.000	10.388.815	611.185
217.645.201	12.000.000	11.336.645	663.355

Aus der Fehlerfunktion \(err(n) = \pi(n) - {n \over \ln(n)}\) lassen sich weitere wichtige Eigenschaften ablesen:

• Der Fehler wächst systematisch mit \(n\), was zeigt, dass die Gauss'sche Näherung strukturell zu klein ist
• Das Verhältnis \({err(n) \over \pi(n)}\) wird jedoch mit steigendem \(n\) kleiner - die relative Genauigkeit verbessert sich
• Legendre versuchte 1808 eine Verbesserung mit \({\pi(n) \sim {n \over {\ln(n) - 1.08366}}}\), was für mittlere Bereiche besser funktionierte, aber für sehr große n wieder schlechter wird
• Gauss erkannte 1849, dass die Integrallogarithmus-Funktion \(Li(n) = \int_2^n {dt \over \ln(t)}\) eine deutlich bessere Approximation liefert als alle bisherigen Ansätze

Diese Verbesserungen führten schließlich zum Primzahlsatz, der besagt: \(\lim_{n \to \infty} {\pi(n) \over {n / \ln(n)}} = 1\).

Der Primzahlsatz wurde 1896 unabhängig von Hadamard und de la Vallée-Poussin bewiesen und stellt einen Höhepunkt der analytischen Zahlentheorie dar. Er bestätigt, dass Gauss' ursprüngliche Intuition asymptotisch exakt war.

Der Primzahlsatz zeigt, dass Primzahlen zwar immer seltener werden, aber nach einem klaren Gesetz: Die Wahrscheinlichkeit, dass eine zufällige Zahl um n prim ist, beträgt etwa \(1 / \ln(n)\). Bei einer Milliarde ist etwa jede 20. Zahl prim, bei einer Billion nur noch jede 28. Zahl.

Anzahl der Primzahlen

Wieviele Primzahlen gibt es? Diese Frage wurde bereits in verschiedenen Varianten beantwortet. Der Erste, der eine Antwort herleiten konnte war Euklid. Angenommen es gäbe nur endlich viele Primzahlen \({p_1, p_2, p_3, ..., p_n}\). Dann kann man eine neue Zahl Z = \(p_1\cdot p_2 \cdot... \cdot p_n + 1\) bilden die durch keine der \(p_i\) teilbar ist. Es ist verlockend zu denken, Z sei automatisch Prim, doch dem ist nicht so. Vielmehr braucht man einen Hauptsatz der Zahlentheorie der ebenfalls seit Euklid bekannt ist, indem es heisst, dass jede Zahl aus Primfaktoren zusammengesetzt ist - so auch Z. Aber die Faktoren von Z sind nicht in unserer Liste \(p_i\) enthalten. Das ist aber ein Widerspruch zur Annahme, das \(p_i\) alle existierenden Primzahlen wären.

Harmonische Reihe

Ein Ausgangspunkt vieler Überlegungen ist die sogenannte harmonische Reihe $$ \sum_{n=1}^{\infty} \frac{1}{n} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots $$ Die harmonische Reihe divergiert, obwohl ihre Glieder gegen Null gehen. Dies lässt sich einfach durch Umsortierung zeigen: $$ 1 + \frac{1}{2} + \left(\frac{1}{3} + \frac{1}{4}\right) + \left(\frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8}\right) + \cdots > 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \cdots $$ Während die harmonische Reihe divergiert, konvergiert bereits \(\sum_{n=1}^{\infty} \frac{1}{n^2}\). Das Basler Problem - die Bestimmung dieser Summe - beschäftigte Mathematiker über 90 Jahre, bis Euler 1735 (im Alter von 28 Jahren) das verblüffende Ergebnis \(\frac{\pi^2}{6}\) fand.

Die interessante Frage ist: Wieviele Glieder kann man aus der harmonischen Reihe entfernen, sodass sie gerade noch divergiert? Ersetzt man die Glieder \(\frac{1}{n}\) durch \(\frac{1}{n^{1+\epsilon}}\) mit beliebig kleinem \(\epsilon > 0\), konvergiert die Reihe bereits. Die kritische Grenze liegt genau bei \(s = 1\) - jede noch so kleine Erhöhung des Exponenten führt zur Konvergenz.

Gamma-Funktion

Die Gamma-Funktion ist eine Verallgemeinerung der Fakultät auf reelle und komplexe Zahlen. Während \(n!\) nur für natürliche Zahlen definiert ist, ermöglicht \(\Gamma(s)\) Berechnungen wie \(1.5!\) oder \((2+3i)!\). $$ \Gamma(s) = \int_0^\infty {t^{s-1} e^{-t}}dt, \quad \text{mit } Re(s) > 0 $$ $$ \Gamma(s+1) = \int_0^\infty {t^{(s+1)-1} e^{-t}}dt = \int_0^{\infty}t^s e^{-t} dt $$ $$ = -e^{-t}t^s|_0^{\infty} - \int_0^{\infty}{{dt^s \over dt}e^{-t}}dt $$ $$ = \int_0^{\infty} st^{s-1}e^{-t}dt = s\cdot\int_0^{\infty} t^{s-1}e^{-t}dt = s \cdot \Gamma(s) $$ also $$ \Gamma(s+1) = s \cdot \Gamma(s) $$ Substituiere und setze in ursprüngliche Form ein: $$ e^{-t} = \lim\limits_{n \to \infty}\left(1+\frac{-t}{n}\right)^n $$ $$ \Gamma(s) = \int_0^{\infty}t^{s-1}e^{-t}dt $$ $$ = \int_0^{\infty}t^{s-1}\lim\limits_{n \to \infty}\left(1+\frac{-t}{n}\right)^n dt $$ $$ = \lim\limits_{n \to \infty} \int_0^n t^{s-1}\left(1-\frac{t}{n}\right)^n dt $$ Nun kann man partiell integrieren: $$ \int_0^n t^{s-1}\left( 1 - \frac{t}{n}\right)^n dt = \frac{1}{s} t^s\left(1-\frac{t}{n}\right)^n\bigg|_0^n - \int_0^n \frac{1}{s}t^s n\left(1- \frac{t}{n}\right)^{n-1}\left(-\frac{1}{n}\right)dt $$ $$ = \frac{n}{s \cdot n} \int_0^n t^s\left(1- \frac{t}{n} \right)^{n-1}dt $$ $$ = \frac{n}{s \cdot n} \cdot \frac{(n-1)}{n(s+1)} \int_0^n t^{s+1}\left(1-\frac{t}{n}\right)^{n-2}dt $$ $$ = \frac{n}{s \cdot n} \cdot \frac{(n-1)}{n(s+1)} \cdot \frac{(n-2)}{n(s+2)} \int_0^n t^{s+2}\left(1-\frac{t}{n}\right)^{n-3}dt $$ $$ = \frac{n}{s \cdot n} \cdot \frac{(n-1)}{n(s+1)} \cdot \frac{(n-2)}{n(s+2)} \cdots \frac{1}{n(s+n-1)} \int_0^n t^{s+n-1}dt $$ $$ = \frac{n}{s \cdot n} \cdot \frac{(n-1)}{n(s+1)} \cdot \frac{(n-2)}{n(s+2)} \cdots \frac{1}{n(s+n-1)} \frac{t^{s+n}}{(s+n)} \bigg|_0^n $$ $$ = \frac{n!}{n^n} n^{s+n} \prod_{i=0}^n (s+i)^{-1} $$ $$ = \frac{n! n^s}{\prod_{i=0}^n(s+i)} $$ Also $$ \Gamma(s) = \lim\limits_{n \to \infty} ( {n^s \over s} \prod_{i=1}^n {i \over {(s+i)}}) $$

Wenn man in dieser Weise fortfährt, kann man zeigen, dass die Gamma-Funktion eng mit der Riemann-Zeta-Funktion verknüpft ist: $$ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \frac{1}{\Gamma(s)} \int_0^{\infty} \frac{t^{s-1}}{e^t - 1} dt $$ Bereits 1737 entdeckte Euler die fundamentale Beziehung zwischen der Zeta-Funktion und den Primzahlen, die als Euler-Produktformel bekannt wurde:

$$ \prod_{\text{$p$ prim}} {1 \over {1 - {1 \over {p^s}}}} = {\sum_{n\ge1} {1 \over n^s}} = \zeta(s) $$ Und das ist nun wirklich erstaunlich: Das unendliche Produkt aus lauter Primzahl-Inversen ergibt dasselbe wie die Summe aus lauter Inversen natürlicher Zahlen.

Die Riemann-Hypothese und moderne Primzahlforschung

Die Euler'sche Produktformel verbindet die Riemann-Zeta-Funktion direkt mit den Primzahlen und zeigt deren fundamentale Rolle in der Zahlentheorie. Die berühmte Riemann-Hypothese besagt, dass alle nichttrivialen Nullstellen von ζ(s) den Realteil 1/2 haben - ein Beweis würde präzise Aussagen über die Verteilung der Primzahlen ermöglichen.

Heute stehen wir an einem Wendepunkt: Während die klassische Primzahltheorie durch Quantencomputer bedroht wird, eröffnen sich neue Forschungsfelder in der Post-Quantum-Kryptographie. Die jahrtausendealten Primzahlen bleiben ein zentrales Element sowohl der reinen Mathematik als auch der angewandten Informatik.

---

Griechisches Alphabet