Siebtheorie

Gegenstand und Grundidee

Die Siebtheorie ist ein Teilgebiet der analytischen Zahlentheorie. Sie entwickelt Verfahren, mit denen eine Grundmenge mathematisch „gesiebt“ wird: Man entfernt alle Elemente, die durch bestimmte Primzahlen teilbar sind. Übrig bleibt eine gesiebte Menge, die beispielsweise Primzahlen, Primzahlzwillinge oder Fastprimzahlen enthalten kann. Meist interessiert man sich vor allem für die Kardinalität, also die Anzahl der Elemente, der gesiebten Menge.

Als Grundmenge betrachtet man häufig A={a | a≤x}⊆ℕ. Eine vorgegebene Primzahlmenge heißt Siebbereich und wird mit 𝒫={2,3,5,…,p_k} bezeichnet. Für jede Primzahl p entfernt man die Vielfachen E_p={pn | n∈ℕ}. Die gesiebte Menge ist A_sift=A\⋃_{p∈𝒫}E_p={a∈A | (a,p_1⋯p_k)=1}.

Mit P(z)=P(z,𝒫)=∏_{p∈𝒫, p<z}p werden die Primzahlen des Siebbereichs bis zur Grenze z zusammengefasst. Die Siebfunktion S(A,𝒫,z):=#A_sift zählt die Elemente von A, die durch keine Primzahl p<z aus 𝒫 teilbar sind. Da diese Anzahl meist nicht direkt berechnet werden kann, besteht das Siebproblem darin, obere und untere Schranken für S(A,𝒫,z) zu bestimmen.

Inklusion, Möbiusfunktion und Kongruenzsummen

Die Berechnung der gesiebten Menge beruht auf dem Prinzip von Inklusion und Exklusion. Zunächst zieht man die durch 2 oder 3 teilbaren Zahlen ab, addiert die durch 6 teilbaren Zahlen wieder hinzu, zieht die durch 5 teilbaren Zahlen ab und korrigiert anschließend mit den Schnittmengen. Für die ersten Primzahlen ergibt sich beispielsweise |A_sift|=|A|-|E_2|-|E_3|+|E_6|-|E_5|+|E_10|+|E_15|-|E_30|+⋯.

Die Vorzeichen werden durch die Möbiusfunktion μ beschrieben: |A_sift|=∑{d|P}μ(d)|E_d|, wobei P=∏{p∈𝒫}p und E_1=A.

Für eine allgemeinere Darstellung ersetzt man die Indikatorfunktion einer Menge A durch eine endliche Folge nicht-negativer reeller Zahlen 𝒜=(a_n). Üblicherweise gilt a_n=1 für n∈A und a_n=0 sonst. So können später auch allgemeinere, etwa komplex-wertige Folgen untersucht werden.

Die Kongruenz-Teilfolge zu d besteht aus den a_n mit n≡0 (mod d): 𝒜_d={a_n | n≤x, n≡0 (mod d)}. Ihre Summe heißt Kongruenzsumme: A_d(x)=∑_{n≤x, n≡0 (mod d)}a_n. In der Regel betrachtet man A_d(x) nur für quadratfreie d.

Die Möbiusfunktion erfüllt ∑{d|(n,P(z))}μ(d)=1, falls (n,P(z))=1, und 0, falls (n,P(z))>1. Daraus folgt Legendres Identität: S(𝒜,𝒫,z)=∑{d|P(z)}μ(d)A_d(x). Die Kongruenzsumme A_d(x) erfasst dabei die Masse aller Vielfachen von d. Für z=7 und 𝒫=ℙ lautet die Entwicklung S(𝒜,ℙ,7)=A_1(x)-A_2(x)-A_3(x)-A_5(x)+A_6(x)+A_10(x)+A_15(x)-A_30(x).

Dichte, Restterm und Ausgangsform einer Siebmethode

Um Legendres Identität praktisch auszuwerten, nähert man die Kongruenzsummen durch A_d(x)=g(d)X+r_d(x) an. Dabei ist X eine Approximation der Gesamtmasse A(x)=A_1(x)=∑_{n≤x}a_n. Die Funktion g(d) heißt Dichtefunktion und kann als Wahrscheinlichkeit interpretiert werden. Vorausgesetzt wird, dass g multiplikativ ist sowie g(1)=1 und 0≤g(d)<1 für d>0. Der Term r_d(x) ist ein Restterm, der möglichst klein sein soll.

Damit erhält man S(𝒜,𝒫,z)=X∑{d|P(z)}μ(d)g(d)+∑{d|P(z)}μ(d)r_d(x). Kurz schreibt man S(𝒜,𝒫,z)=XG(x,z)+R, wobei G(x,z)=∑{d|P(z)}μ(d)g(d), X≈A_1(x), R=∑{d|P(z)}μ(d)r_d(x).

Für jede multiplikative Funktion g mit g(1)=1 gilt außerdem ∑{d|n}μ(d)g(d)=∏{p|n, p∈ℙ}(1-g(p)). Diese Identität verwandelt eine Summe über Teiler in ein Produkt über die Primteiler und ist ein wichtiges Rechenwerkzeug der Siebtheorie.

Klassische Siebe und Anwendungen

Beim Sieb von Eratosthenes-Legendre sei A={n∈ℕ | 0<n≤x}, a_n=1_A(n), 𝒫=ℙ und X=x. Dann gilt A_d(x)=⌊x/d⌋, g(d)=1/d, r_d(x)={−{x/d}}, |r_d(x)|≤1. Damit ist G(x,z)=∑{d|P(z), d≤x} μ(d)/d und R(x,z)=−∑{d|P(z), d≤x}μ(d){x/d}.

Wählt man z=√x, erhält man genau die Primzahlen im Intervall (√x,x]. Daher gilt S(𝒜,𝒫,z)=π(x)−π(z)+1. Außerdem ist G(x,z)=∏_{p≤z}(1−1/p)=(2e^{−γ}+𝒪(1))/log z, wobei der Satz von Mertens mit Restterm verwendet wird. Für den Restterm gilt |R|≤2^{π(√x)}. Wählt man stattdessen z=log(x), so erhält man die Schranke π(x)≤x(2e^{−γ}+𝒪(1))/log z+z+𝒪(x^{log 2}) und daraus π(x)≤𝒪(x/log log x), was schlechter als der Primzahlsatz ist.

Bruns reines Sieb ersetzt die Möbiusfunktion auf einem kleineren Träger durch Gewichte λ_d. Für eine Menge 𝒟={d:ω(d)<k}, wobei ω(d) die verschiedenen Primfaktoren zählt, gilt λ_d=μ(d), falls d∈𝒟, und λ_d=0 sonst. Ist D die Anzahl der Elemente von 𝒟, heißt die Folge ein Sieb mit Niveau D. Allgemein heißen die λ_d Sieb-Gewichte. Folgen λ_d^- und λ_d^+ mit ∑{d|n}λ_d^-≤∑{d|n}μ(d)≤∑_{d|n}λ_d^+ liefern ein unteres und oberes Schrankensieb: S^{Λ^-}(𝒜,𝒫,z)≤S(𝒜,𝒫,z)≤S^{Λ^+}(𝒜,𝒫,z).

Für Primzahlzwillinge betrachtet man A={m(m+2)≤x}. Dabei ist g(p)=2/p für ungerade Primzahlen und g(2)=1/2; außerdem gilt |r_d(x)|≤2^{ν(d)}. Bruns Sieb liefert #{p≤x: p∈ℙ, p+2∈ℙ}≤S(𝒜,z)≪x((log log x)/(log x))^2. Daraus folgt Bruns Theorem über die Primzahlzwillinge.

Entwicklung, GPY-Sieb und Grenzen

Das antike Sieb des Eratosthenes ist der historische Ausgangspunkt. Es lässt sich als Anwendung des Inklusions-Exklusions-Prinzips verstehen. Legendres Verallgemeinerung führte zur Primzahlfunktion. Die moderne Siebtheorie begann Anfang des 20. Jahrhunderts: Viggo Brun veröffentlichte 1915 eine grundlegende Arbeit und bewies 1919, dass ∑_{p,p+2 prim} (1/p+1/(p+2))<∞. Der Grenzwert heißt Bruns Konstante B_2≈1,9021…. 1934 folgte das Turán-Sieb, 1941 Linniks großes Sieb mit probabilistischen Methoden und 1947 das Selberg-Sieb. In den 1970er-Jahren entwickelte Bombieri das asymptotische Sieb. Mitte der 1990er veröffentlichten Friedlander und Iwaniec paritätsempfindliche Siebe.

2005 entwickelten Goldston, Pintz und Yıldırım das GPY-Sieb, eine Variante des Selberg-Siebs mit verallgemeinerten mehrdimensionalen Sieb-Gewichten. Für ℋ={h_1,…,h_k} mit h_i∈ℤ_+∪{0} und R∈ℝ wird D(n)={d≤R: d|(n+h_1)(n+h_2)⋯(n+h_k)} definiert. Die GPY-Gewichte lauten Λ_R(n;ℋ,ℓ)=∑_{d∈D(n)}λ(d), λ(d)=1/(k+ℓ)! · μ(d)(log(R/d))^{k+ℓ}, 0≤ℓ≤k. Mit dieser Methode wurde gezeigt, dass es unendlich viele Primzahltupel mit Primzahllücken gibt, die beliebig kleiner als der aus dem Primzahlsatz folgende Durchschnittsabstand sind. Für benachbarte Primzahlen der Größe etwa x ist dieser Durchschnittsabstand ungefähr log x.

2013 zeigte Yitang Zhang, dass es unendlich viele Primzahlpaare mit Differenz kleiner als 7×10^7 gibt. James Maynard senkte diese Grenze im selben Jahr durch eine weitere Modifikation des GPY-Siebs auf 600.

Eine grundlegende Grenze klassischer Siebmethoden ist das Paritätsproblem: Sie können im Allgemeinen nicht zwischen Zahlen mit einer geraden und einer ungeraden Anzahl von Primfaktoren unterscheiden. Deshalb sind nicht-triviale untere Schranken für die Primzahlzählfunktion besonders schwierig. Paritätsempfindliche Siebe von Friedlander und Iwaniec lösen dieses Problem in manchen Fällen.