Siebmethoden | Nico Köslich

Eine endliche Menge natürlicher Zahlen liegt vor uns. Wir streichen alle Zahlen, die durch bestimmte kleine Primzahlen teilbar sind. Wie viele bleiben übrig? Diese einfache Frage führt zur Siebtheorie.

Die Darstellung orientiert sich an Greaves und Ford. Elementare Teilbarkeit wird vorausgesetzt; die wichtigsten Begriffe bauen wir im Folgenden auf.

01 / Ein erstes Experiment

Was durch das Sieb fällt

Für eine reelle Zahl $z>2$ fassen wir alle Primzahlen unterhalb der Siebgrenze zu einem Produkt zusammen:

Definition · Primzahlprodukt

P(z)=\prod_{p<z}p.\qquad P(10)=2\cdot3\cdot5\cdot7=210.

Eine Zahl überlebt genau dann, wenn sie zu $P(z)$ teilerfremd ist. Im Beispiel werden daher alle Vielfachen von 2, 3, 5 und 7 entfernt. Verändere die Grenze oder betrachte die einzelnen Schritte:

Ein Intervall geht durchs SiebZum Ausprobieren

P(10) = 2 · 3 · 5 · 7 = 210

bleibtentferntEinheit

1: bleibt; die Einheit ist keine Primzahl
2: entfernt, erstmals als Vielfaches von 2
3: entfernt, erstmals als Vielfaches von 3
4: entfernt, erstmals als Vielfaches von 2
5: entfernt, erstmals als Vielfaches von 5
6: entfernt, erstmals als Vielfaches von 2
7: entfernt, erstmals als Vielfaches von 7
8: entfernt, erstmals als Vielfaches von 2
9: entfernt, erstmals als Vielfaches von 3
10: entfernt, erstmals als Vielfaches von 2
11: bleibt; kein Primteiler unter der Siebgrenze
12: entfernt, erstmals als Vielfaches von 2
13: bleibt; kein Primteiler unter der Siebgrenze
14: entfernt, erstmals als Vielfaches von 2
15: entfernt, erstmals als Vielfaches von 3
16: entfernt, erstmals als Vielfaches von 2
17: bleibt; kein Primteiler unter der Siebgrenze
18: entfernt, erstmals als Vielfaches von 2
19: bleibt; kein Primteiler unter der Siebgrenze
20: entfernt, erstmals als Vielfaches von 2
21: entfernt, erstmals als Vielfaches von 3
22: entfernt, erstmals als Vielfaches von 2
23: bleibt; kein Primteiler unter der Siebgrenze
24: entfernt, erstmals als Vielfaches von 2
25: entfernt, erstmals als Vielfaches von 5
26: entfernt, erstmals als Vielfaches von 2
27: entfernt, erstmals als Vielfaches von 3
28: entfernt, erstmals als Vielfaches von 2
29: bleibt; kein Primteiler unter der Siebgrenze
30: entfernt, erstmals als Vielfaches von 2
31: bleibt; kein Primteiler unter der Siebgrenze
32: entfernt, erstmals als Vielfaches von 2
33: entfernt, erstmals als Vielfaches von 3
34: entfernt, erstmals als Vielfaches von 2
35: entfernt, erstmals als Vielfaches von 5
36: entfernt, erstmals als Vielfaches von 2
37: bleibt; kein Primteiler unter der Siebgrenze
38: entfernt, erstmals als Vielfaches von 2
39: entfernt, erstmals als Vielfaches von 3
40: entfernt, erstmals als Vielfaches von 2
41: bleibt; kein Primteiler unter der Siebgrenze
42: entfernt, erstmals als Vielfaches von 2
43: bleibt; kein Primteiler unter der Siebgrenze
44: entfernt, erstmals als Vielfaches von 2
45: entfernt, erstmals als Vielfaches von 3
46: entfernt, erstmals als Vielfaches von 2
47: bleibt; kein Primteiler unter der Siebgrenze
48: entfernt, erstmals als Vielfaches von 2
49: entfernt, erstmals als Vielfaches von 7
50: entfernt, erstmals als Vielfaches von 2
51: entfernt, erstmals als Vielfaches von 3
52: entfernt, erstmals als Vielfaches von 2
53: bleibt; kein Primteiler unter der Siebgrenze
54: entfernt, erstmals als Vielfaches von 2
55: entfernt, erstmals als Vielfaches von 5
56: entfernt, erstmals als Vielfaches von 2
57: entfernt, erstmals als Vielfaches von 3
58: entfernt, erstmals als Vielfaches von 2
59: bleibt; kein Primteiler unter der Siebgrenze
60: entfernt, erstmals als Vielfaches von 2
61: bleibt; kein Primteiler unter der Siebgrenze
62: entfernt, erstmals als Vielfaches von 2
63: entfernt, erstmals als Vielfaches von 3
64: entfernt, erstmals als Vielfaches von 2
65: entfernt, erstmals als Vielfaches von 5
66: entfernt, erstmals als Vielfaches von 2
67: bleibt; kein Primteiler unter der Siebgrenze
68: entfernt, erstmals als Vielfaches von 2
69: entfernt, erstmals als Vielfaches von 3
70: entfernt, erstmals als Vielfaches von 2
71: bleibt; kein Primteiler unter der Siebgrenze
72: entfernt, erstmals als Vielfaches von 2
73: bleibt; kein Primteiler unter der Siebgrenze
74: entfernt, erstmals als Vielfaches von 2
75: entfernt, erstmals als Vielfaches von 3
76: entfernt, erstmals als Vielfaches von 2
77: entfernt, erstmals als Vielfaches von 7
78: entfernt, erstmals als Vielfaches von 2
79: bleibt; kein Primteiler unter der Siebgrenze
80: entfernt, erstmals als Vielfaches von 2
81: entfernt, erstmals als Vielfaches von 3
82: entfernt, erstmals als Vielfaches von 2
83: bleibt; kein Primteiler unter der Siebgrenze
84: entfernt, erstmals als Vielfaches von 2
85: entfernt, erstmals als Vielfaches von 5
86: entfernt, erstmals als Vielfaches von 2
87: entfernt, erstmals als Vielfaches von 3
88: entfernt, erstmals als Vielfaches von 2
89: bleibt; kein Primteiler unter der Siebgrenze
90: entfernt, erstmals als Vielfaches von 2
91: entfernt, erstmals als Vielfaches von 7
92: entfernt, erstmals als Vielfaches von 2
93: entfernt, erstmals als Vielfaches von 3
94: entfernt, erstmals als Vielfaches von 2
95: entfernt, erstmals als Vielfaches von 5
96: entfernt, erstmals als Vielfaches von 2
97: bleibt; kein Primteiler unter der Siebgrenze
98: entfernt, erstmals als Vielfaches von 2
99: entfernt, erstmals als Vielfaches von 3
100: entfernt, erstmals als Vielfaches von 2

Exakt · S(𝒜, 10)22Zahlen bleiben übrig

Dichtemodell · N V(z)≈ 22,9Näherung aus lokalen Dichten

Was jede Primzahl neu entfernt

p = 2−50 neu entfernt50 übrig
p = 3−17 neu entfernt33 übrig
p = 5−7 neu entfernt26 übrig
p = 7−4 neu entfernt22 übrig

Eine Zahl wird nur beim ersten passenden Primteiler entfernt. So zählt jedes Vielfache genau einmal.

Gesiebt heißt: ohne kleine Primteiler. Die 1 bleibt im Sieb, ist aber keine Primzahl. Bei größeren Intervallen können auch zusammengesetzte Zahlen übrig bleiben. Das Produkt V(z) ist ein Dichtemodell; die tatsächliche Anzahl wird hier exakt gezählt.

Die übrig gebliebenen Zahlen sind nicht automatisch Primzahlen: Die 1 überlebt immer; bei größeren Grundmengen können auch zusammengesetzte Zahlen ohne kleine Primteiler übrig bleiben. Außerdem werden die kleinen Primzahlen selbst ausgesiebt.

02 / Das algebraische Werkzeug

Die Möbiusfunktion

Um das Streichen in eine Formel zu übersetzen, brauchen wir eine Funktion, die zwischen gerader und ungerader Anzahl verschiedener Primfaktoren unterscheidet.

Definition · Möbiusfunktion

\mu(n)=\begin{cases}1,&n=1,\\(-1)^r,&n=p_1\cdots p_r\text{ quadratfrei},\\0,&p^2\mid n\text{ für eine Primzahl }p.\end{cases}

In der zweiten Zeile sind die $p_i$ paarweise verschiedene Primzahlen. Eine Zahl heißt quadratfrei, wenn kein Primzahlquadrat sie teilt.

\mu(1)

\mu(7)

−1

\mu(30)

−1

\mu(6)

\mu(12)

Für teilerfremde $a,b$ ist die Funktion multiplikativ:

\operatorname{ggT}(a,b)=1\quad\Longrightarrow\quad\mu(ab)=\mu(a)\mu(b).

Ein Indikator für Teilerfremdheit

Der entscheidende Zusammenhang lautet:

Identität · Übrig bleiben oder verschwinden

\sum_{d\mid\operatorname{ggT}(a,P(z))}\mu(d)=\begin{cases}1,&\operatorname{ggT}(a,P(z))=1,\\0,&\operatorname{ggT}(a,P(z))>1.\end{cases}

Warum die Summe nur 0 oder 1 ergibt

Setze $m=\operatorname{ggT}(a,P(z))$ . Für $m=1$ enthält die Summe nur $\mu(1)=1$ . Für $m>1$ ergibt die Multiplikativität

\sum_{d\mid m}\mu(d)=\prod_{p\mid m}(1-1)=0.

Jeder Primteiler liefert also einen Faktor null. Genau das macht die Summe zu einem Indikator für das Überleben im Sieb.

03 / Exaktes Zählen

Legendres Identität

Sei $\mathscr A\subset\mathbb N$ eine endliche Menge. Für einen positiven ganzzahligen Teiler $d$ sammeln wir die durch ihn teilbaren Elemente:

Definition · Teilbarkeitsmenge und Siebfunktion

\mathscr A_d=\{a\in\mathscr A:d\mid a\}.

Für quadratfreies $d>1$ gilt $\mathscr A_d=\bigcap_{p\mid d}\mathscr A_p$ ; außerdem ist $\mathscr A_1=\mathscr A$ . Die Zahl der überlebenden Elemente ist

S(\mathscr A,z)=\bigl|\{a\in\mathscr A:\operatorname{ggT}(a,P(z))=1\}\bigr|.

Wir summieren den Möbiusindikator über die Grundmenge und vertauschen die beiden endlichen Summen:

Satz · Legendres Identität

\begin{aligned}S(\mathscr A,z)&=\sum_{a\in\mathscr A}\;\sum_{d\mid\operatorname{ggT}(a,P(z))}\mu(d)\\&=\sum_{d\mid P(z)}\mu(d)\,|\mathscr A_d|.\end{aligned}

Das ist das Inklusions-Exklusions-Prinzip in arithmetischer Form: Einfach entfernte Mengen werden abgezogen, doppelte Überschneidungen wieder hinzugefügt und so weiter.

Beispiel: Nur durch 2 und 3 sieben

Für $\mathscr A=\{1,\ldots,N\}$ und $z=5$ ist $P(5)=6$ . Es folgt exakt:

\begin{aligned}S(\mathscr A,5)&=N-\left\lfloor\frac N2\right\rfloor-\left\lfloor\frac N3\right\rfloor+\left\lfloor\frac N6\right\rfloor\\&=\frac N3+O(1).\end{aligned}

Die Vielfachen von 6 wurden zweimal entfernt und müssen einmal zurückkehren. Ohne diese Korrektur wäre der Hauptterm nur $N/6$ . Die Schreibweise $O(1)$ bezeichnet hier einen Fehler, der unabhängig von $N$ beschränkt bleibt.

Beispiel: Die ersten 10 000 Zahlen

Wählen wir $\mathscr A=\{1,\ldots,10000\}$ und $z=10$ , dann gilt

|\mathscr A_d|=\left\lfloor\frac{10000}{d}\right\rfloor,\qquad S(\mathscr A,10)=2285.

Die 16 Teiler von 210 liefern die vollständige Legendre-Summe. Allein $|\mathscr A_2|=5000$ zeigt: Beim ersten Schritt verschwindet genau die Hälfte der Grundmenge.

04 / Vom Zählen zum Abschätzen

Hauptterm, Dichte und Rest

In anspruchsvolleren Beispielen kennen wir die Teilbarkeitsmengen nicht exakt. Stattdessen zerlegen wir ihre Größen in einen erwarteten Anteil und einen Restterm:

Das kleine Siebproblem

|\mathscr A_d|=X\frac{\rho(d)}d+r_{\mathscr A}(d)=Xg(d)+r_d.

Dabei ist $X$ ein Haupttermparameter, $g(d)=\rho(d)/d$ die lokale Dichte und $r_d=|\mathscr A_d|-Xg(d)$ der Rest.

Die genaue Gesamtmasse bezeichnen wir mit $M=|\mathscr A|$ . Häufig ist $X=M$ , aber nicht immer: Bei Primzahleingaben ist etwa $X=\operatorname{Li}(x)$ ein natürlicher Näherungswert.

Wir nehmen $g(1)=1$ und $0\leq g(p)<1$ für die betrachteten Primzahlen an und setzen auf quadratfreien Zahlen multiplikativ fort:

g(d)=\prod_{p\mid d}g(p),\qquad V(z)=\prod_{p<z}(1-g(p)).

Das Produkt $V(z)$ beschreibt den Anteil, der bei unabhängigen lokalen Teilbarkeitsbedingungen übrig bliebe.

Zurück zu den ersten 10 000 Zahlen

Hier sind $X=10000$ , $\rho(d)=1$ und $g(d)=1/d$ . Wegen der Abrundung ist $|r_d|<1$ . Also:

V(10)=\frac12\cdot\frac23\cdot\frac45\cdot\frac67=\frac8{35}.

XV(10)\approx2285{,}714,\qquad S(\mathscr A,10)=2285.

Die Produktdichte liefert einen Hauptterm; die ganzzahlige Zählung liefert den exakten Wert.

Wie weit sind die Reste kontrollierbar?

Ein Parameter $D$ beschreibt, bis zu welchen Teilern wir die Restterme hinreichend gut beherrschen. Diese Reichweite heißt Level des Siebs. Später wählen wir Gewichte, die nur Teiler $d\leq D$ verwenden.

Im Intervallbeispiel könnte man etwa $D=\sqrt X=100$ betrachten. Die exakte Legendre-Summe darf man deshalb jedoch nicht einfach bei 100 abschneiden: Auch der Teiler 210 gehört zu ihr.

05 / Eine arithmetische Anwendung

Polynome an Primzahlstellen

Sei $f\in\mathbb Z[T]$ ein Polynom. Wir betrachten die Familie der Werte $f(p)$ für Primzahlen $p\leq x$ . Jeder Primzahleingang wird einzeln gezählt; gleiche Funktionswerte behalten ihre Vielfachheit. Die Schreibweise $|\mathscr A_d|$ zählt nun die Eingaben mit $d\mid f(p)$ .

Wir zerlegen diese Eingaben nach Restklassen:

|\mathscr A_d|=\sum_{\substack{l\bmod d\\f(l)\equiv0\pmod d}}\pi(x;d,l),

wobei $\pi(x;d,l)$ die Primzahlen bis $x$ in der Restklasse $l$ modulo $d$ zählt. Für teilerfremde Restklassen schreiben wir

\pi(x;d,l)=\frac{\operatorname{Li}(x)}{\varphi(d)}+E(x;d,l),\qquad\operatorname{ggT}(l,d)=1.

Hier ist $\varphi(d)$ die Eulersche Phi-Funktion und $\operatorname{Li}(x)=\int_2^x dt/\log t$ das logarithmische Integral. Die Anzahl der zulässigen Nullstellen ist

\psi_f(d)=\#\{l\bmod d:\operatorname{ggT}(l,d)=1,\ f(l)\equiv0\pmod d\}.

Damit erhalten wir erneut die Form eines kleinen Siebproblems:

Lokale Dichte für Polynomwerte

|\mathscr A_d|=\operatorname{Li}(x)\frac{\rho(d)}d+r_d,\qquad\rho(d)=\frac{d\,\psi_f(d)}{\varphi(d)}.

Der chinesische Restsatz zeigt die Multiplikativität von $\psi_f$ und damit von $\rho$ .

Für die Anwendung unter der Annahme $g(q)<1$ benötigen wir außerdem $\psi_f(q)<q-1$ für jede verwendete Siebprimzahl $q$ . Diese Bedingung gilt nicht für jedes Polynom; lokale Ausnahmen müssen gesondert behandelt werden.

Was im Restterm steckt

Für nicht teilerfremde Restklassen kann eine Primzahleingabe nur dann beitragen, wenn sie selbst ein Primteiler von $d$ ist. Daher gilt

|r_d|\leq\sum_{\substack{l\bmod d\\(l,d)=1\\f(l)\equiv0\pmod d}}|E(x;d,l)|+\omega(d).

Hier zählt $\omega(d)$ die verschiedenen Primteiler von $d$ ; für $d>1$ gilt $\omega(d)\leq\log d/\log2$ und $\omega(1)=0$ .

Das Muster der Primzahlzwillinge

Mit $f(T)=T+2$ fragen wir nach Primzahlen $p$ , für die auch $p+2$ prim ist. Für jede ungerade Primzahl $q$ ist die einzige Nullstelle $l\equiv-2\pmod q$ teilerfremd zu $q$ . Deshalb gilt

\rho(q)=\frac q{q-1}\quad(q>2),\qquad\rho(2)=0.

Die Ausnahme $p=2$ liegt im Restterm. Durch das Sieben lassen sich Kandidaten ohne kleine Primteiler zählen und abschätzen. Die Existenz unendlich vieler Primzahlzwillinge folgt daraus nicht. Einen verwandten Blick auf lokale Primzahlbedingungen bietet die Bateman–Horn-Vermutung.

Verteilung im Mittel: Bombieri–Vinogradov

Für die Kontrolle der Fehler in arithmetischen Progressionen ist folgendes Resultat zentral. Für jedes $A>0$ gibt es ein $B>0$ , sodass für hinreichend großes $x$ gilt:

Satz · Bombieri–Vinogradov

\sum_{d\leq x^{1/2}/(\log x)^B}\;\max_{\substack{l\bmod d\\(l,d)=1}}|E(x;d,l)|\ll_A\frac{x}{(\log x)^A}.

Das Zeichen $\ll_A$ erlaubt einen konstanten Faktor, der von $A$ abhängt.

Kontrolliert wird die Summe der Fehler über viele Moduln, bis nahe an die Quadratwurzel von $x$ . Beim Übergang zu allgemeinen Polynomen muss zusätzlich die Anzahl ihrer zulässigen Nullstellen berücksichtigt werden. Eine ausführliche Fassung steht in Fords Vorlesungsnotizen, Theorem 3.4.

06 / Eine zweite Perspektive

Die Dichte der Überlebenden

Auf einer endlichen Grundmenge mit $M=|\mathscr A|>0$ wählen wir jedes Element mit Wahrscheinlichkeit $1/M$ . Teilbarkeit durch eine Primzahl ist dann ein Ereignis. Die Siebfunktion wird zu

S(\mathscr A,z)=M\,\mathbb P\!\left(\bigcap_{p<z}\mathscr A_p^{\,c}\right).

Bei einer Familie mit Vielfachheiten wählen wir entsprechend gleichverteilt aus ihren Eingaben. Wären die Teilbarkeitsereignisse unabhängig und hätten exakt die Wahrscheinlichkeiten $g(p)$ , wäre die Überlebenswahrscheinlichkeit gerade $V(z)$ . In der tatsächlichen Siebsituation messen die Restterme die Abweichungen vom lokalen Modell.

Satz · Legendres Sieb mit Restterm

S(\mathscr A,z)=XV(z)+O\!\left(\sum_{d\mid P(z)}|r_d|\right).

Beweis durch Einsetzen in Legendres Identität

\begin{aligned}S(\mathscr A,z)&=\sum_{d\mid P(z)}\mu(d)(Xg(d)+r_d)\\&=X\prod_{p<z}(1-g(p))+\sum_{d\mid P(z)}\mu(d)r_d.\end{aligned}

Im Hauptterm nutzen wir die Multiplikativität auf quadratfreien Zahlen. Für die Restsumme liefert die Dreiecksungleichung wegen $|\mu(d)|\leq1$ genau die behauptete Schranke; die implizite Konstante kann hier als 1 gewählt werden.

Die Formel ist exakt bis auf einen ausdrücklich kontrollierten Fehler. Doch $P(z)$ hat viele Teiler: Bei $k$ Siebprimzahlen sind es $2^k$ . Selbst kleine Einzelreste können sich zu einem großen Gesamtfehler summieren.

07 / Mit begrenzter Information arbeiten

Obere und untere Siebgewichte

Die exakte Möbiussumme verwendet alle Teiler von $P(z)$ . Wenn wir nur bis zum Level $D$ genügend Information haben, ersetzen wir sie durch obere und untere Abschätzungen.

Definition · Gewichte vom Level D

Für jeden Teiler $t\mid P(z)$ fordern wir

\sum_{d\mid t}\lambda_D^-(d)\leq\mathbf1_{t=1}\leq\sum_{d\mid t}\lambda_D^+(d),

und die Gewichte verschwinden außerhalb der kontrollierten Reichweite:

\lambda_D^\pm(d)=0\qquad(d>D).

Setzen wir $t=\operatorname{ggT}(a,P(z))$ und summieren über die Grundmenge, erhalten wir:

\sum_{d\mid P(z)}\lambda_D^-(d)|\mathscr A_d|\leq S(\mathscr A,z)\leq\sum_{d\mid P(z)}\lambda_D^+(d)|\mathscr A_d|.

Nach Einsetzen von $|\mathscr A_d|=Xg(d)+r_d$ zerfällt jede Schranke in einen gewichteten Hauptterm und einen Fehler. Für die obere Schranke etwa gilt

S(\mathscr A,z)\leq X\sum_{d\mid P(z)}\lambda_D^+(d)g(d)+\sum_{\substack{d\mid P(z)\\d\leq D}}|\lambda_D^+(d)r_d|.

Die Kunst liegt darin, Gewichte zu konstruieren, die einen guten Hauptterm liefern und den Fehler klein halten. Die Wahl $\lambda^\pm(d)=\mu(d)$ auf den Teilern von $P(z)$ ergibt die exakte Identität; das geforderte Level ist dafür jedoch erst bei $D\geq P(z)$ automatisch ausreichend.

Der rote Faden

Lokale Teilbarkeit, globale Information.

Die Möbiusfunktion macht aus dem Streichen eine exakte Summe. Lokale Dichten liefern einen Hauptterm. Restterme und Siebgewichte entscheiden, wie präzise wir die Anzahl der Überlebenden tatsächlich abschätzen können.