Siebtheorie

Die Siebtheorie bezeichnet eine Reihe von Techniken aus der analytischen Zahlentheorie. Die Grundidee ist, mittels eines mathematischen Siebes eine Grundmenge zu filtern, so dass am Ende eine gewünschte gesiebte Menge übrig bleibt, die nicht durch das Sieb gefallen ist. Dies können zum Beispiel Primzahlen, Primzahlzwillinge oder Fastprimzahlen sein. Der Archetyp eines Siebes ist das Sieb des Eratosthenes zum Ermitteln der Primzahlen. In erster Linie ist man an der Kardinalität der gesiebten Menge interessiert.

Die Siebtheorie hat sich zu einem mächtigen Instrument der analytischen Zahlentheorie entwickelt, die viele bedeutende mathematische Aussagen ermöglicht hat, wie z. B. den Satz von Chen und Yitang Zhangs Resultat über Primzahlabstände. Sie lässt sich aber auch auf andere mathematische Gebiete übertragen.

Siebmethoden haben aber auch Grenzen: so verhindert das sogenannte Paritätsproblem das Finden von nicht-trivialen unteren Schranken für die Primzahlzählfunktion. Klassische Siebmethoden können nicht zwischen Zahlen mit einer geraden und solchen mit einer ungeraden Anzahl von Primfaktoren unterscheiden; diese Eigenschaft nennt man das Paritätsproblem.^[1]

Geschichte

Viggo Brun

Das erste bekannte Sieb ist das antike Sieb des Eratosthenes zum Berechnen der Primzahlen. Das Sieb kann als Anwendung des Prinzips der Inklusion und Exklusion aus der Kombinatorik interpretiert werden und für die Berechnung der Primzahlfunktion benützt werden. Dies führt zu einer ersten Verallgemeinerung des Siebs von Eratosthenes von Adrien-Marie Legendre. Obwohl der Algorithmus sehr intuitiv ist, ist es nicht ganz einfach, das Konzept zu abstrahieren, deshalb entstand die moderne Siebtheorie erst Anfangs des 20. Jahrhunderts.

Der abstrakte Begriff des Siebs entstand mit der 1915 erschienenen Publikation des norwegischen Mathematikers Viggo Brun.^[2] Bruns Arbeit war inspiriert durch die Arbeiten des Franzosen Jean Merlin, dieser verstarb aber im Ersten Weltkrieg und nur zwei seiner Manuskripte haben überlebt.^[3] Als endgültiger Start der modernen Siebtheorie gilt Bruns 1919 veröffentlichte Publikation, in der er bewies, dass die Summe der reziproken Werte der Primzahlzwillinge konvergiert^[4]

${\displaystyle \sum \limits _{p,p+2\;{\text{Primzahl}}}\left({\frac {1}{p}}+{\frac {1}{p+2}}\right)<\infty .}$

Die Konstante ${\displaystyle B_{2}\approx 1.9021\dots }$ zu der diese Summe konvergiert, nennt man Bruns Konstante. Das Brun-Sieb ist ein kombinatorisches Sieb, das auf der Idee eines gewichteten Prinzip der Inklusion und Exklusion basiert. In seiner einfachsten Form bezeichnet man es auch als Bruns reines Sieb.

1934 erschien ein einfaches Sieb von Pál Turán, das Turán-Sieb genannt wird.

1941 erschien das große Sieb von Juri Linnik, der probabilistische Methoden einführte. Linniks Ideen stellten sich als äußerst fruchtbar heraus und sukzessiv wurde das Sieb von vielen Mathematikern weiterentwickelt (darunter Rényi, Roth, Bombieri, Halberstam, Gallagher uvw.). Diese heutige Form befasst sich mit einem viel größeren Kontext als Linniks ursprüngliche Arbeit. Das große Sieb kann von der großen Sieb-Ungleichung abgeleitet werden.^[5]

1947 erschien ein weiteres wichtiges Sieb von Atle Selberg, genannt Selberg-Sieb. Selberg nützte dabei Bruns Ansatz und gab eine einfache Folge von Gewichten an.^[6]

In den 1970ern erschien das asymptotische Sieb von Bombieri. Bombieri lieferte asymptotische Formeln für die verallgemeinerte Mangoldt-Funktion.^[1]

Mitte der 1990er veröffentlichten John Friedlander und Henryk Iwaniec partitätsempfindliche Siebe, welche das sogenannte Partiätsproblem in manchen Fällen lösen.^[7] Dies bezeichnet die Eigenschaft, dass die Siebtheorie im Allgemeinen nicht zwischen Zahlen mit einer geraden und einer ungeraden Anzahl von Primfaktoren in einer Menge unterscheiden kann. Dies hat zur Folge, dass es äußerst schwierig ist, nicht-triviale untere Schranken für Primzahlmengen zu finden.

2005 veröffentlichten Goldston, Pintz und Yıldırım eine Variante des Selberg-Siebs mit verallgemeinerten, mehrdimensionalen Sieb-Gewichten, das unter dem Namen GPY-Sieb bekannt ist. Mit dieser Methode zeigten sie, dass es unendlich viele Primzahltupel gibt, deren Abstände (die Primzahllücke) beliebig kleiner sind, als der Durchschnittsabstand, der aus dem Primzahlsatz folgt. Aus diesem folgt nämlich, dass der Abstand zwischen zwei benachbarten Primzahlen ${\displaystyle p_{n+1}-p_{n}}$, deren Größe etwa ${\displaystyle x}$ ist, in etwa ${\displaystyle \log x}$ ist. 2013 erweiterte Yitang Zhang diese Sieb-Methode und zeigte, dass es unendlich viele Primzahlpaare mit Differenz kleiner als ${\displaystyle 7\times 10^{7}}$ gibt. Kurz darauf im selben Jahre wurde diese Grenze von James Maynard mit einer weiteren Modifikation des GPY-Siebs durch neue Gewichte auf ${\displaystyle 600}$ gedrückt.^[8]

Siebtheorie

Wir folgen dem Ansatz aus Opera de Cribro von Friedlander und Iwaniec.^[9]

Notation:

Wir bezeichnen mit

• ${\displaystyle \mathbb {P} }$ die Menge der Primzahlen.
• ${\displaystyle {\mathcal {A}}=(a_{n})}$ die Indikatorfunktion einer Menge ${\displaystyle A}$.
• ${\displaystyle A_{d}(x)}$ die Kardinalität einer Kongruenzmenge (in der Literatur wird diese auch mit ${\displaystyle |A_{d}(x)|}$ notiert).
• ${\displaystyle (a,b)}$ den größten gemeinsamen Teiler ${\displaystyle (a,b):=\operatorname {ggT} (a,b)}$.
• ${\displaystyle \lfloor x\rfloor }$ die Abrundungsfunktion.
• ${\displaystyle \{x\}}$ den Nachkommateil, das heißt ${\displaystyle \{x\}:=x-\lfloor x\rfloor }$.
• ${\displaystyle |A|}$ und ${\displaystyle \#A}$ die Kardinalität von ${\displaystyle A}$.

Grundidee

Sei ${\displaystyle A:=\{a\mid a\leq x\}\subseteq \mathbb {N} }$ eine beliebige abzählbare Grundmenge bis zur Zahl ${\displaystyle x}$. Die Restriktion bis ${\displaystyle x}$ muss nicht sein, ist aber üblich. Angenommen, wir möchten nun alle Primzahlen in ${\displaystyle A}$ finden, die sich nicht in einer vorgegebenen Primzahlmenge ${\displaystyle {\mathcal {P}}:=\{2,3,5,\dots ,p_{k}\}\subset \mathbb {P} }$ befinden.

Wenden wir das Sieb des Eratosthenes an, dann entfernen wir von ${\displaystyle A}$ in einem ersten Schritt alle Vielfachheiten von ${\displaystyle 2}$ und danach sukzessiv für jedes ${\displaystyle p\in {\mathcal {P}}}$ alle anderen Mengen der Form

${\displaystyle E_{p}=\{pn:n\in \mathbb {N} \}.}$

Die resultierende Menge ist die gesiebte Menge (englisch sieved set)

${\displaystyle A_{\operatorname {sift} }:=A\setminus \bigcup _{p\in {\mathcal {P}}}E_{p}=A\setminus \left(E_{2}\cup E_{3}\cup E_{5}\cup \cdots \cup E_{p_{k}}\right)}$

bestehend aus den zu ${\displaystyle {\mathcal {P}}}$ teilerfremden Zahlen

${\displaystyle A_{\operatorname {sift} }=\{a\in A|(a,p_{1}\cdots p_{k})=1\}.}$

Aus Notationsgründen definieren wir für ${\displaystyle {\mathcal {P}}}$ folgende Funktion

${\displaystyle P(z):=P(z,{\mathcal {P}})=\prod \limits _{p\in {\mathcal {P}},p<z}p.}$

Das Inklusion-Exklusion-Prinzip

Sei nun ${\displaystyle {\mathcal {P}}}$ eine Primzahlmenge der Form ${\displaystyle {\mathcal {P}}=\{2,3,5,7,11,13,\dots \}}$.

Möchte man die Kardinalität von ${\displaystyle A_{\operatorname {sift} }}$ berechnen, so zieht man von ${\displaystyle |A|}$ in einem ersten Schritt die Kardinalität von ${\displaystyle E_{2}}$ und ${\displaystyle E_{3}}$ ab. Da man jetzt aber die Zahlen, welche durch ${\displaystyle 2}$ und ${\displaystyle 3}$ teilbar sind, doppelt abgezogen hat, muss man die Kardinalität von ${\displaystyle E_{6}}$ wieder dazuzählen. Nun zieht man die Kardinalität von ${\displaystyle E_{5}}$ ab und zählt die von ${\displaystyle E_{10}}$ und ${\displaystyle E_{15}}$ dazu. Zusätzlich muss man nun noch die Menge ${\displaystyle E_{30}}$ abziehen, also die Menge der Zahlen die durch ${\displaystyle 2,3}$ und ${\displaystyle 5}$ teilbar sind. Wiederholt man diese Schritte nun für alle Primzahlen ${\displaystyle {\mathcal {P}}}$, so führt das zum Prinzip von Inklusion und Exklusion

${\displaystyle |A_{\operatorname {sift} }|=|A|-|E_{2}|-|E_{3}|+|E_{6}|-|E_{5}|+|E_{10}|+|E_{15}|-|E_{30}|+\cdots }$.

Der Vorzeichenwechsel kann durch die Möbiusfunktion modelliert werden

${\displaystyle |A_{\operatorname {sift} }|=\sum \limits _{d\mid P}\mu (d)|E_{d}|}$.

wobei hier ${\displaystyle P:=\prod \limits _{p\in {\mathcal {P}}}p}$ das Produkt aller Primzahlen in ${\displaystyle {\mathcal {P}}}$ ist und ${\displaystyle E_{1}:=A}$.

Das Siebproblem

Die Menge ${\displaystyle A}$ nennt man Siebmenge (englisch sifting set) und die Menge ${\displaystyle {\mathcal {P}}}$ Siebbereich (englisch sifting range). Die Kardinalität der Menge ${\displaystyle A_{\operatorname {sift} }}$ bezeichnet man als Siebfunktion (englisch sifting function):

${\displaystyle S(A,{\mathcal {P}},z):=\#A_{\operatorname {sift} }.}$

Die Siebfunktion zählt somit alle Elemente in der Menge ${\displaystyle A}$, die nicht durch ein Element der Menge ${\displaystyle \{p\in {\mathcal {P}}:p<z\}}$ teilbar sind.

Häufig kann man ${\displaystyle S(A,{\mathcal {P}},z)}$ nicht explizit berechnen, deshalb versucht man eine obere und untere Schranken zu finden. Das Abschätzen der Siebfunktion nennt man Siebproblem.

Beispiel

Sei ${\displaystyle A=[1,x]\cap \mathbb {N} }$, betrachte alle Primzahlen ${\displaystyle {\mathcal {P}}:=\mathbb {P} }$ und sei ${\displaystyle 1<z<x,}$, dann zählt ${\displaystyle S(A,{\mathcal {P}},z)}$ alle Elemente in ${\displaystyle A_{\operatorname {sift} }=(z,x]\cap \mathbb {N} }$, welche nicht durch eine der Primzahlen bis ${\displaystyle z}$ teilbar sind.

Zählen durch eine abstrakte Folge

Da wir im Wesentlichen an der Evaluation einer Summe der Form

${\displaystyle S(A,{\mathcal {P}},z)=\sum \limits _{s\in A_{\operatorname {sift} }}1}$

interessiert sind, ist es natürlich, den Zählfaktor ${\displaystyle 1}$ als abstrakte Folge zu betrachten. Im Allgemeinen wählt man dafür eine endliche Folge von nicht-negativen reellen Zahlen ${\displaystyle {\mathcal {A}}:=(a_{n})}$. Dieser Abstraktionsschritt hat den Vorteil, dass man später auch ziemlich allgemeine Folgen wählen kann (zum Beispiel komplex-wertige wie im großen Sieb), um das Problem in andere Räume zu übertragen. Dadurch kann man analytisch interessantere Funktionen als die Indikatorfunktion analysieren.

Wir wählen für ${\displaystyle {\mathcal {A}}}$ die charakteristische Funktion von ${\displaystyle A}$, das heißt

${\displaystyle a_{n}:={\begin{cases}1&n\in A,\\0&{\text{sonst}}.\end{cases}}}$

Die Folge ist so sortiert, dass sich die Zahl ${\displaystyle 1_{A}(n)}$ an der Position ${\displaystyle n}$ befindet. Die charakteristische Funktion von ${\displaystyle A_{\operatorname {sift} }}$ ist eine Teilfolge ${\displaystyle (b_{n})}$ von ${\displaystyle {\mathcal {A}}}$.

Kongruenz-Teilfolgen

Zusätzlich definieren wir Teilfolgen von ${\displaystyle {\mathcal {A}}}$ bestehend aus den ${\displaystyle a_{n}}$ mit ${\displaystyle n\equiv 0\ (\mathrm {mod} \ d)}$, das heißt

${\displaystyle {\mathcal {A}}_{d}=\{a_{n}\mid n\leq x,n\equiv 0\ (\operatorname {mod} d)\}}$

und führen deren Summen ein, welche wir Kongruenzsumme nennen

${\displaystyle A_{d}(x):=\sum \limits _{n\leq x,\;n\equiv 0\ (\operatorname {mod} d)}a_{n}.}$

In der Regel betrachtet man nur ${\displaystyle A_{d}(x)}$ für quadratfreie Zahlen ${\displaystyle d}$.^[9]

Identitäten für die Siebfunktion

Die Siebfunktion ist

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{n\leq x,\ (n,P(z))=1}a_{n}}$

und die Restriktion durch die Teilerfremdheit lässt sich mit Hilfe der Möbiusfunktion ausdrücken, denn es gilt

${\displaystyle \sum \limits _{d\mid (n,P(z))}\mu (d)={\begin{cases}1&{\text{wenn }}(n,P(z))=1,\\0&{\text{wenn }}(n,P(z))>1.\end{cases}}}$

Somit erhalten wir für die Siebfunktion

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{n}a_{n}\sum \limits _{d\mid (n,P(z))}\mu (d)=\sum \limits _{d\mid P(z)}\mu (d)\sum \limits _{n\equiv 0{\pmod {d}}}a_{n}}$

wobei die letzte Summe eine Kongruenzsumme ist.

Legendres Identität

Wir haben somit folgende Identität für die Siebfunktion hergeleitet

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{d\mid P(z)}\mu (d)A_{d}(x),}$

die auch Legendres Identität genannt wird. Die Kongruenzsumme ist die Masse aller Vielfachheiten von ${\displaystyle d}$.

Beispiel

Sei ${\displaystyle z=7}$ und ${\displaystyle {\mathcal {P}}=\mathbb {P} }$. Die Möbiusfunktion ist für alle Primzahlen negativ, somit gilt

${\displaystyle {\begin{aligned}S({\mathcal {A}},\mathbb {P} ,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).\end{aligned}}}$

Approximation der Kongruenzsumme

Wir nehmen an, wir können die Kongruenzsumme aufteilen

${\displaystyle A_{d}(x)=g(d)X+r_{d}(x)}$

wobei ${\displaystyle X}$ eine Approximation der gesamten Masse ist

${\displaystyle X\approx A(x)=A_{1}(x)=\sum \limits _{n\leq x}a_{n}.}$

Die Funktion ${\displaystyle g(d)}$ kann als Wahrscheinlichkeit interpretiert werden und wird deshalb Dichtefunktion genannt. Wir setzen voraus, dass ${\displaystyle g(d)}$ eine multiplikative Funktion ist und folgendes gilt

${\displaystyle g(1)=1\quad {\text{und}}\quad 0\leq g(d)<1,\quad d>0.}$

Die Funktion ${\displaystyle r_{d}(x)}$ bezeichnet einen Restterm, den man möglichst klein halten möchte.

Die Siebfunktion lässt sich nun als

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=X\sum \limits _{d\mid P(z)}\mu (d)g(d)+\sum \limits _{d\mid P(z)}\mu (d)r_{d}(x)}$

schreiben, was oft abgekürzt wird mit

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=XG(x,z)+R.}$

Identität für die Möbiusfunktion und eine multiplikative Funktion

Sei ${\displaystyle g}$ eine multiplikative Funktion mit ${\displaystyle g(1)=1}$, dann gilt für alle ${\displaystyle n\in \mathbb {N} }$

${\displaystyle \sum \limits _{d\mid n}\mu (d)g(d)=\prod \limits _{\begin{array}{c}p|n;\;p\in \mathbb {P} \end{array}}(1-g(p))}$

Zusammengefasst

Die Ausgangslage einer Siebmethode lässt sich grob wie folgt zusammenfassen:^[9]

Wir beginnen mit einer nicht-negativen Folge ${\displaystyle {\mathcal {A}}=(a_{n})}$ und einer Primzahlmenge ${\displaystyle {\mathcal {P}}\subseteq \mathbb {P} }$ sowie

${\displaystyle P(z)=\prod \limits _{p\in {\mathcal {P}},p<z}p.}$

Dann definiert man die Siebfunktion

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=XG(x,z)+R,}$

wobei

${\displaystyle G(x,z)=\sum \limits _{d\mid P(z)}\mu (d)g(d),\quad X\approx A_{1}(x),\quad R:=\sum \limits _{d\mid P(z)}\mu (d)r_{d}(x).}$

Beispiele

Das Sieb von Eratosthenes-Legendre

Wir betrachten das Sieb von Eratosthenes. Sei ${\displaystyle A=\{n\mid n\in \mathbb {N} ,0<n\leq x\}}$, ${\displaystyle a_{n}=1_{A}(n)}$, ${\displaystyle {\mathcal {P}}=\mathbb {P} }$ und ${\displaystyle X=x}$ sowie^[10]

${\displaystyle A(x)=\sum \limits _{n\in \mathbb {N} }a_{n}=\sum \limits _{n:0<n\leq x}1,\quad A_{d}(x)=\left\lfloor {\frac {x}{d}}\right]}$

sowie

${\displaystyle g(d)={\frac {1}{d}},\quad r_{d}=-\left\{{\frac {x}{d}}\right\},\quad |r_{d}(x)|\leq 1.}$

Die Siebfunktion ist somit

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=xG(x,z)+R}$

mit

${\displaystyle G(x,z)=\sum \limits _{d\mid P(z);\;d\leq x}{\frac {\mu (d)}{d}},\qquad R(x,z)=-\sum \limits _{d\mid P(z);\;d\leq x}\mu (d)\left\{{\frac {x}{d}}\right\}.}$

Wählt man ${\displaystyle z:={\sqrt {x}}}$, so erhält man gerade alle Primzahlen im Interval ${\displaystyle ({\sqrt {x}},x]}$ und somit

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\pi (x)-\pi (z)+1.}$

Für ${\displaystyle G}$ gilt

${\displaystyle G(x,z)=\prod \limits _{p\leq z}\left(1-{\frac {1}{p}}\right)={\frac {2e^{-\gamma }+{\mathcal {O}}(1)}{\log z}},}$

wobei wir in der letzten Gleichung den Satz von Mertens mit Restterm verwendet haben. Für den Restterm nützen wir die Abschätzung

${\displaystyle \left|R\right|\leq \sum \limits _{d\mid P(z)}1=2^{\pi ({\sqrt {x}})}.}$

Wir kriegen folgende Abschätzung

${\displaystyle {\frac {x}{\log z}}\left(2e^{-\gamma }+{\mathcal {O}}(1)\right)+{\mathcal {O}}(2^{\pi ({\sqrt {x}})})\geq \pi (x)-\pi (z)+1\geq \pi (x)-z.}$

Wir können den Restterm verbessern, wenn wir ${\displaystyle z:=\log(x)}$ wählen, denn dann gilt

${\displaystyle 2^{\pi (\log x)}\leq 2^{\log x}=x^{\log {2}}}$

und wir erhalten

${\displaystyle \pi (x)\leq {\frac {x}{\log z}}\left(2e^{-\gamma }+{\mathcal {O}}(1)\right)+z+{\mathcal {O}}(x^{\log {2}}).}$

Daraus folgern wir

${\displaystyle \pi (x)\leq {\mathcal {O}}\left({\frac {x}{\log \log x}}\right),}$

was aber ein schlechteres Resultat als der Primzahlsatz ist.

Bruns reines Sieb

Bruns Idee beruht auf der Beobachtung, dass das Sieb von Eratosthenes-Legendre betrachtet als das Prinzip der Inklusion und Exklusion jeweils für jede Partialsumme abwechselnd über- und unterzählt. Seine Idee war es deshalb, die Partialsummen zu gewichten, indem er die Möbiusfunktion ${\displaystyle \mu (d)}$ durch eine passende Folge ${\displaystyle \Lambda =(\lambda _{d})}$ auf einem kleineren Träger ersetzt

${\displaystyle \lambda _{d}={\begin{cases}\mu (d)&{\text{falls }}d\in {\mathcal {D}}\\0&{\text{sonst}}\end{cases}},}$

Hierzu wählte er die Menge ${\displaystyle {\mathcal {D}}=\{d:\omega (d)<k\}}$, wobei ${\displaystyle \omega (d)}$ die Prim-Omega-Funktion bezeichnet, welche die distinkten Primfaktoren zählt.

Sei ${\displaystyle D}$ die Anzahl Elemente in ${\displaystyle {\mathcal {D}}}$, dann sagt man ${\displaystyle \Lambda =(\lambda _{d})}$ ist ein Sieb mit Niveau ${\displaystyle D}$ (englisch sieve of level D).

Sieb-Gewichte

Die ${\displaystyle (\lambda _{d})}$ nennt man Sieb-Gewichte (oder siebende Gewichte) und die neue Siebfunktion wird mit ${\displaystyle S^{\Lambda }({\mathcal {A}},{\mathcal {P}},z)}$ notiert. Allgemein ist diese nun nicht mehr gleich groß wie die ursprüngliche Siebfunktion.

Wählt man zwei verschiedene Folgen ${\displaystyle \Lambda ^{+}=(\lambda _{d}^{+})}$ und ${\displaystyle \Lambda ^{-}=(\lambda _{d}^{-})}$ mit der Eigenschaft

${\displaystyle \sum \limits _{d|n}\lambda _{d}^{-}\leq \sum \limits _{d|n}\mu (d)\leq \sum \limits _{d|n}\lambda _{d}^{+},\quad \forall n\in \mathbb {N} }$

dann erhält man ein unteres und oberes Schrankensieb

${\displaystyle S^{\Lambda ^{-}}({\mathcal {A}},{\mathcal {P}},z)\leq S({\mathcal {A}},{\mathcal {P}},z)\leq S^{\Lambda ^{+}}({\mathcal {A}},{\mathcal {P}},z).}$

Häufig notiert man diese Schranken auch nur mit ${\displaystyle S^{-}}$ und ${\displaystyle S^{+}}$. Diese Ungleichung ist die einfachste Form der Methode von Brun und sie trägt daher den Namen Bruns reines Sieb.^[11]

Anwendung: Primzahlzwillinge

Sei ${\displaystyle A=\{m(m+2)\leq x\}}$, ${\displaystyle a_{n}=1_{A}(n)}$, ${\displaystyle {\mathcal {P}}=\mathbb {P} }$, ${\displaystyle {\mathcal {A}}_{p}=\{a_{m}:p|m(m+2)\}}$ und ${\displaystyle X=x}$. Weiter sei

${\displaystyle \lambda _{d}={\begin{cases}\mu (d)&{\text{falls }}\omega (d)<k\\0&{\text{sonst}}\end{cases}},}$

dann ist für ${\displaystyle p\in \mathbb {P} }$

${\displaystyle g(p)={\begin{cases}2/p&p{\text{ ungerade}}\\1/2&p=2.\end{cases}}}$

Für den Restterm gilt

${\displaystyle |r_{d}(x)|\leq 2^{\nu (d)}.}$

Es lässt sich mit Hilfe von Bruns Sieb folgende Ungleichung für die Primzahlzwillinge herleiten:

${\displaystyle \#\{p\leq x:p\in \mathbb {P} ,(p+2)\in \mathbb {P} \}\leq S({\mathcal {A}},z)\ll x\left({\frac {\log \log {x}}{\log {x}}}\right)^{2}}$

woraus Bruns Theorem über die Primzahlzwillinge folgt.^[11]

Das Sieb von Goldston-Pintz-Yıldırım

→ Hauptartikel: Goldston-Pintz-Yıldırım-Sieb

Sei

${\displaystyle {\mathcal {H}}=\{h_{1},\dots ,h_{k}\}}$ mit ${\displaystyle h_{i}\in \mathbb {Z} _{+}\cup \{0\}}$ und ${\displaystyle n,\ell \in \mathbb {N} ,R\in \mathbb {R} }$.

und

${\displaystyle D(n)=\{d\leq R:d\mid (n+h_{1})(n+h_{2})\cdots (n+h_{k})\}.}$

Das GPY-Sieb hat verallgemeinerte Selberg-Gewichte von der Form

${\displaystyle \Lambda _{R}(n;{\mathcal {H}},\ell ):=\sum \limits _{d\in D(n)}\lambda (d),\qquad \lambda (d):={\frac {1}{(k+\ell )!}}\mu (d)\left(\log \left({\frac {R}{d}}\right)\right)^{k+\ell },\quad 0\leq \ell \leq k}$.^[12]

Literatur

Allgemeine Siebtheorie

• John Friedlander und Henryk Iwaniec: Opera de Cribro. In: American Mathematical Society (Hrsg.): American Mathematical Society Colloquium Publications. Band 57, 2010, ISBN 978-0-8218-4970-5 (englisch). 
• Alina Carmen Cojocaru und M. Ram Murty: An Introduction to Sieve Methods and Their Applications. Hrsg.: Cambridge University Press. 2005, doi:10.1017/CBO9780511615993 (englisch). 
• George Greaves: Sieves in Number Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete 43, Springer 2001
• Heini Halberstam und Hans-Egon Richert: Sieve Methods. Hrsg.: Academic Press. 1974 (englisch). , Nachdruck Dover, ISBN 978-0-486-47939-2
• Andrew M. Odlyzko: Sieve Methods. Hrsg.: California Institute of Technology. 1971, doi:10.7907/28FN-8P32 (caltech.edu – Senior Thesis (Diplomarbeit)). 

Literatur über das große Sieb

• Emmanuel Kowalski: The Large Sieve and its Applications: Arithmetic Geometry, Random Walks and Discrete Groups. In: Cambridge University Press (Hrsg.): Cambridge Tracts in Mathematics. 2008, doi:10.1017/CBO9780511542947 (englisch). 

Geschichte der Siebtheorie

• Yōichi Motohashi: An Overview of the Sieve Method and its History. Hrsg.: arXiv. 2005, doi:10.48550/ARXIV.MATH/0505521, arxiv:math/0505521 (englisch). 
• Alina Carmen Cojocaru und M. Ram Murty: An Introduction to Sieve Methods and Their Applications. Hrsg.: Cambridge University Press. 2005, doi:10.1017/CBO9780511615993 (englisch). 

Einzelnachweise

1. Kevin Ford: On Bombieri's asymptotic sieve. Hrsg.: arXiv. 2004, doi:10.48550/ARXIV.MATH/0401215, arxiv:math/0401215. 
2. Viggo Brun: Über das Goldbachsche Gesetz und die Anzahl der Primzahlpaare. In: Archiv for Math. Naturvidenskab. Band 34, 1915. 
3. Alina Carmen Cojocaru und M. Ram Murty: An Introduction to Sieve Methods and Their Applications. Hrsg.: Cambridge University Press. 2005, doi:10.1017/CBO9780511615993 (englisch). 
4. Viggo Brun: La série 1/5+1/7+1/11+1/13+1/17+1/19+1/29+1/31+1/41+1/43+1/59+1/61+..., où les dénominateurs sont nombres premiers jumeaux est convergente ou finie. In: Bulletin des Sciences Mathématiques. Band 43, 1919, S. 100–104, 124–128 (französisch, bnf.fr). 
5. John Friedlander und Henryk Iwaniec: Opera de Cribro. In: American Mathematical Society (Hrsg.): American Mathematical Society Colloquium Publications. Band 57, 2010, ISBN 978-0-8218-4970-5, S. 151. 
6. Atle Selberg: On an elementary method in the theory of primes. In: Norsk. Vid. Selsk. Forh. Band 19, Nr. 18, 1947, S. 64–67. 
7. John Friedlander und Henryk Iwaniec: Using a parity-sensitive sieve to count prime values of a polynomial. In: PNAS. Band 94, Nr. 4, 1997, S. 1054–1058, doi:10.1073/pnas.94.4.1054, PMID 11038598, PMC 19742 (freier Volltext).  (Zusammenfassung der Resultate)
8. James Maynard: Small gaps between primes. In: Annals of Mathematics. Band 181, Nr. 1, 2015, S. 383–413, doi:10.4007/annals.2015.181.1.7, arxiv:1311.4600 [abs]. 
9. John Friedlander und Henryk Iwaniec: Opera de Cribro. In: American Mathematical Society (Hrsg.): American Mathematical Society Colloquium Publications. Band 57, 2010, ISBN 978-0-8218-4970-5. 
10. John Friedlander und Henryk Iwaniec: Opera de Cribro. In: American Mathematical Society (Hrsg.): American Mathematical Society Colloquium Publications. Band 57, 2010, ISBN 978-0-8218-4970-5, S. 5;31–33. 
11. John Friedlander und Henryk Iwaniec: Opera de Cribro. In: American Mathematical Society (Hrsg.): American Mathematical Society Colloquium Publications. Band 57, 2010, ISBN 978-0-8218-4970-5, S. 6;55–56. 
12. Daniel A. Goldston, János Pintz und Cem Y. Yildirim: Primes in Tuples I. In: Annals of Mathematics. Band 170, Nr. 2, 2009, S. 827–829, doi:10.4007/annals.2009.170.819.