Zeef van Selberg

In de getaltheorie, een deelgebied van de wiskunde, is de zeef van Selberg een techniek voor het schatten van de grootte van "gezeefde verzamelingen" van positieve gehele getalllen die voldoen aan een aantal voorwaarden die worden uitgedrukt in congruenties. De zeef van Selberg werd in de jaren veertig van de twintigste eeuw ontwikkeld door de Noorse wiskundige Atle Selberg.

Beschrijving

In termen van de zeeftheorie is de zeef van Selberg van het combinatorische type: dat wil zeggen dat de zeef van Selberg wordt afgeleid door een zorgvuldig gebruik van het principe van inclusie en exclusie. Selberg verving de waarden van de Möbiusfunctie die hierin voorkomen door een systeem van gewichten, die vervolgens worden geoptimaliseerd om op een gegeven probleem te fitten. Het resultaat geeft een bovengrens voor de grootte van de gezeefde verzameling.

Laat A een verzameling van positieve gehele getallen ≤ x zijn en laat P een verzameling van priemgetallen zijn. Laat A_p voor elke p in P de verzameling van elementen van A aanduiden die deelbaar zijn door p en breidt dit uit door A_d de doorsnede te laten zijn van de A_p voor p die delen op d, wanneer d een product van de verschillende priemgetallen van P is. Laat A₁ verder A zelf aanduiden. Laat z een positief reëel getal aanduiden en laat P(z) het product van de priemgetallen in P aanduiden die ≤ Z zijn. Het doel van de zeef is het schatten van de onderstaande formule

$S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .$

Wij nemen aan dat |A_d| kan worden geschat door

$\left\vert A_{d}\right\vert ={\frac {1}{f(d)}}X+R_{d}.$

waar f een multiplicatieve functie is en X   =   |A|. Laat de functie g worden verkregen uit f door Möbius-inversie, dat wil zeggen dat

$g(n)=\sum _{d\mid n}\mu (d)f(n/d)$

$f(n)=\sum _{d\mid n}g(d)$

waar μ de Möbiusfunctie is.

Neem

$V(z)=\sum _{\begin{smallmatrix}d<z\\d\mid P(z)\end{smallmatrix}}{\frac {\mu ^{2}(d)}{g(d)}}.$

dan geldt vervolgens

$S(A,P,z)\leq {\frac {X}{V(z)}}+O\left({\sum _{\begin{smallmatrix}d_{1},d_{2}<z\\d_{1},d_{2}\mid P(z)\end{smallmatrix}}\left\vert R_{[d_{1},d_{2}]}\right\vert }\right).$

Het is vaak nuttig om V(z) te schatten door de grens

$V(z)\geq \sum _{d\leq z}{\frac {1}{f(d)}}.\,$