Legendre Sieve - Legendre's Identity

Legendre's Identity

The central idea of the method is expressed by the following identity, sometimes called the Legendre identity:

where A is a set of integers, P is a product of distinct primes, is the Möbius function, and is the set of integers in A divisible by d, and S(A, P) is defined to be:

i.e. S(A, P) is the count of numbers in A with no factors common with 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:

$\begin{align} S(A,P) & = \sum_{d|P}\mu(d)\left\lfloor\frac{X}{d}\right\rfloor \\ & = - \sum_{p_1 < z} \left\lfloor\frac{X}{p_1}\right\rfloor + \sum_{p_1 < p_2 < z} \left\lfloor\frac{X}{p_1p_2}\right\rfloor - \sum_{p_1 < p_2 < p_3 < z} \left\lfloor\frac{X}{p_1p_2p_3}\right\rfloor + \cdots \end{align}$

(where denotes the floor function). In this example the fact that the Legendre identity is derived from the Sieve of Eratosthenes is clear: the first term is the number of integers below X, the second term removes the multiples of all primes, the third term adds back the multiples of two primes (which were miscounted by being "crossed out twice"), and so on until all (where denotes the number of primes below z) combinations of primes have been covered.

Once S(A, P) has been calculated for this special case, it can be used to bound using the expression

which follows immediately from the definition of S(A, P).

Read more about this topic: Legendre Sieve

Famous quotes containing the word identity:

“Let it be an alliance of two large, formidable natures, mutually beheld, mutually feared, before yet they recognize the deep identity which beneath these disparities unites them.”
—Ralph Waldo Emerson (1803–1882)