Zeef van Brun

In de getaltheorie, een deelgebied van de wiskunde, is de zeef van Brun (ook wel pure zeef van Brun genoemd) een techniek voor het schatten van de grootte van "gezeefde verzamelingen" van positieve gehele getallen, die voldoen aan een verzameling van condities die worden uitgedrukt door congruenties. De zeef van Brun werd in 1915 ontwikkeld door de Noorse wiskundige Viggo Brun.

Beschrijving

In termen van de zeeftheorie is de zeef van Brun van het combinatorische type: dat wil zeggen dat de zeef van Brun wordt afgeleid door een zorgvuldig gebruik van het principe van inclusie en exclusie.

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 voorstellen die deelbaar zijn door p en breidt dit uit om A_d de doorsnede van de A_p voor p die deelt op d, wanneer d een product is van de verschillende priemgetallen van P. Laat A₁ verder A zelf voorstellen. Laat z een positief reëel getal zijn en laat P(z) de priemgetallen in P ≤ z voorstellen. Het doel van de zeef van Brun is het schatten van onderstaande formule:

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

Wij nemen aan dat |A_d| kan worden geschat door

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

waar w een multiplicatieve functie is en X   =   |A|. Laat

$W(z)=\prod _{p\in P(z)}\left(1-{\frac {w(p)}{p}}\right).$