Zeef van Legendre

In de getaltheorie, een deelgebied van de wiskunde, is de zeef van Legendre (vernoemd naar Adrien-Marie Legendre) de eenvoudigste methode uit de moderne zeeftheorie. Het past het concept van de zeef van Eratosthenes toe om de boven- of ondergrenzen van het aantal priemgetallen binnen een gegeven verzameling van gehele getallen te vinden. Omdat het een eenvoudige uitbreiding van idee achter de zeef van Eratosthenes is, wordt het soms ook wel de zeef van Eratosthenes-Legendre genoemd.

Identiteit van Legendre

Het centrale idee van de methode komt tot uitdrukking in de volgende identiteit die soms de identiteit van Legendre wordt genoemd:

$S(A,P)=\sum _{a\in A}\sum _{d\mid a;\,d\mid P}\mu (d)=\sum _{d\mid P}\mu (d)|A_{d}|,$

waar A een verzameling van gehele getallen is, P het product van de verschillende priemgetallen, $\mu$ de Möbiusfunctie, en $A_{d}$ de verzameling van gehele getallen in A is, die deelbaar is door d, en S(A, P) wordt gedefinieerd als:

$S(A,P)=|\{n:n\in A,(n,P)=1\}|$

dat wil zeggen dat S(A, P) het aantal getallen in A is zonder gemeenschappelijke factoren met P.

Note that in the most typical case, A is all integers less than or equal to some real number X, P is the product of all primes less than or equal to some integer z < X, and then the Legendre identity becomes:

Merk op dat in het meest typische geval A gelijk is aan het aantal gehele getallen kleiner dan of gelijk aan enig reëel getal X, P het product is van alle priemgetallen kleiner dan of gelijk aan enig geheel getal z < X. De identiteit van Legendre wordt dan

${\begin{aligned}S(A,P)&=\sum _{d\mid P}\mu (d)\left\lfloor {\frac {X}{d}}\right\rfloor \\&=[X]-\sum _{p_{1}<z}\left\lfloor {\frac {X}{p_{1}}}\right\rfloor +\sum _{p_{1}<p_{2}<z}\left\lfloor {\frac {X}{p_{1}p_{2}}}\right\rfloor -\sum _{p_{1}<p_{2}<p_{3}<z}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots \end{aligned}}$

(waar $\lfloor X\rfloor$ de vloerfunctie aangeeft). In dit voorbeeld is het feit dat de identiteit van Legendre wordt afgeleid van de zeef van Eratosthenes duidelijk: de eerste term is het aantal gehele getallen kleiner dan X, de tweede term verwijdert de veelvouden van alle priemgetallen, de derde term telt er weer de veelvouden van twee priemgetallen bij (deze waren ten onrechte "tweemaal weggestreept), en zo verder totdat alle

$2^{\pi (z)}$

combinaties van priemgetallen zijn afgelopen. ($\pi (z)$ staat hier voor het aantal priemgetallen kleiner dan z)

Wanneer S(A, P) voor dit speciale geval is uitgerekend kan het resultaat worden gebruikt om $\pi (X)$ te begrenzen door gebruik te maken van de uitdrukking

$S(A,P)\geq \pi (X)-\pi (z)+1,\,$

wat onmiddellijk volgt uit de definitie van S(A, P).

Beperkingen

Helaas heeft de zeef van Legendre een probleem met fractionele delen van termen die in een grote fout accumuleren. waardoor de zeef in de meeste gevallen slechts zeer zwakke grenzen geeft. Daarom wordt de zeef van Legendre in de praktijk bijna nooit gebruikt. Zij is vervangen door andere technieken zoals de zeef van Brun en zeef van Selberg. Aangezien deze krachtigere zeven echter uitbreidingen zijn van de basisideeën van de zeef van Legendre, is het nuttig om eerst te begrijpen hoe de zeef van Legendre werkt.

Bronvermelding

• Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Legendre sieve op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.