In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, the fundamental lemma of sieve theory is any of several results that systematize the process of applying
sieve methods to particular problems.
Halberstam &
Richert
[
]
write:
Diamond &
Halberstam[
]
attribute the terminology ''Fundamental Lemma'' to
Jonas Kubilius.
Common notation
We use these notations:
*
is a set of
positive integers, and
is its subset of integers divisible by
*
and
are functions of
and of
that estimate the number of elements of
that are divisible by
, according to the formula
:
:Thus
represents an approximate density of members divisible by ''
'', and
represents an error or remainder term.
*
is a set of primes, and
is the product of those primes
*
is the number of elements of
not divisible by any prime in
that is
*
is a constant, called the sifting density,
that appears in the assumptions below. It is a
weighted average
The weighted arithmetic mean is similar to an ordinary arithmetic mean (the most common type of average), except that instead of each of the data points contributing equally to the final average, some data points contribute more than others. The ...
of the number of
residue class
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...
es sieved out by each prime.
Fundamental lemma of the combinatorial sieve
This formulation is from Tenenbaum.
[
] Other formulations are in
Halberstam &
Richert,
in Greaves,
[
]
and in
Friedlander &
Iwaniec.
We make the assumptions:
*
is a
multiplicative function
In number theory, a multiplicative function is an arithmetic function ''f''(''n'') of a positive integer ''n'' with the property that ''f''(1) = 1 and
f(ab) = f(a)f(b) whenever ''a'' and ''b'' are coprime.
An arithmetic function ''f''(''n'') i ...
.
* The sifting density
satisfies, for some constant
and any real numbers
and
with
:
:
There is a parameter
that is at our disposal. We have uniformly in
, ''
'', ''
'', and
that
:
In applications we pick ''
'' to get the best error term. In the sieve it is related to the number of levels of the
inclusion–exclusion principle
In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
: , A \cu ...
.
Fundamental lemma of the Selberg sieve
This formulation is from
Halberstam &
Richert.
Another formulation is in Diamond &
Halberstam.
We make the assumptions:
*
is a
multiplicative function
In number theory, a multiplicative function is an arithmetic function ''f''(''n'') of a positive integer ''n'' with the property that ''f''(1) = 1 and
f(ab) = f(a)f(b) whenever ''a'' and ''b'' are coprime.
An arithmetic function ''f''(''n'') i ...
.
* The sifting density
satisfies, for some constant
and any real numbers
and
with
:
* ''
'' for some small fixed ''
'' and all ''
''.
* ''
'' for all squarefree ''
'' whose prime factors are in ''
''.
The fundamental lemma has almost the same form as for the combinatorial sieve. Write ''
''. The conclusion is:
:
Note that ''
'' is no longer an independent parameter at our disposal, but is controlled by the choice of ''
''.
Note that the error term here is weaker than for the fundamental lemma of the combinatorial sieve. Halberstam & Richert remark:
"Thus it is not true to say, as has been asserted from time to time in the literature, that Selberg's sieve is always better than Brun's."
Notes
{{Reflist
Sieve theory
Theorems in analytic number theory