Selberg’s sieve: study of the error term

Prerequisites:

• Selberg’s sieve: statement and beginning of the proof
• Selberg’s sieve: study of the parameters λ

We have seen that, thanks to the Selberg’s sieve, we can calculate an estimate of the sieve function S(A, \mathbb{P}, z), where, as usual, A is a finite set of natural numbers, \mathbb{P} is the set of prime numbers and z \gt 1 is a real number. This estimate is of the type:

where:

and P(z) is the product of the prime numbers smaller than z.

In the previous article we calculated the \lambda_d parameters that make the T estimate as low as possible. Now all that remains is to replace these values of \lambda_d in the function R which represents the error term of our estimate: this will be the aim of this article. We will proceed in subsequent steps.

Step 1: increasing the parameters \lambda_d

The expression of the \lambda_d parameters that we found in the last article is quite complicated, so we’ll avoid putting it in the expression of R and we’ll adopt a simpler approach. The fundamental issue is that it’s not necessary to calculate the error exactly, but it is sufficient to overestimate it, or rather, in order to treat excess and defect errors in the same way, it is sufficient to overestimate its absolute value, i.e. establish how much |R| can be at most. Consequently, even for the \lambda_d parameters, their exact value is not so important; rather it’s important to know how much |\lambda_d| can be at most. In particular, we can prove the following property:

Substituting into (2), we obtain a fairly simple expression of the upper bound for |R|:

The next step is to simplify this relationship.

Step 2: Group by least common multiple

An important aspect can be observed regarding formula (2′): if d_1 and d_2 are divisors of P(z), their least common multiple must also be a divisor of P(z).

So the possible values of \mathrm{lcm}(d_1, d_2), in (2′), are the divisors of P(z), but it’s possible that several (d_1, d_2) pairs have the same least common multiple, so there will be repeated values of r(\mathrm{lcm}(d_1, d_2)). We can therefore think of grouping equal values of r(\mathrm{lcm}(d_1, d_2)), multiplying each by the number of times it appears in the summation, i.e. by the number of pairs (d_1, d_2) having the least common multiple indicated in the subscript:

It therefore remains to calculate, for each d, the cardinality of the set \{d_1, d_2 \mid P(z) \textrm{\ such that\ } \mathrm{lcm}(d_1, d_2) = d\}, i.e. how many pairs of divisors of P(z) have d as least common multiple.
First we can observe that the condition d_1, d_2 \mid P(z) is superfluous: in fact it can be obtained from the condition \mathrm{lcm}(d_1, d_2) = d, remembering that d in turn a divisor of P(z); therefore we can simply count how many pairs of integers have least common multiple d without any particular constraints, and the condition d_1, d_2 \mid P(z) will be automatically satisfied. In other words, the following equality holds:

The counting of the number of pairs is given by Proposition N.29, of which for convenience we report the statement (following the previous link you can also find the proof and an example):

Applying Proposition N.29 to our case, we’ll have that:

So, combining formulas (4), (5) and (6), we’ll obtain:

Finally, by combining this last formula with (2′), we’ll obtain the overestimate we were looking for:

As you can see, this function depends only on z, which is one of the parameters set initially, so the result will be a number.

Step 3: Limit d to make the error small

As we saw in the previous example, formula (8) tends to generate very large error estimates. This is not surprising, as the summation is extended to all divisors of P(z), which grow exponentially with respect to P(z). Furthermore, the number of prime factors of each divisor (\omega(d)) appears as an exponent of 3, potentially generating very large values; so not only does the summation have many terms, but each term is also potentially very large.
Making the terms of the summation smaller is difficult, because it would mean thinking in a completely different way than what has been done so far, but it’s possible to reduce the number of terms by changing only some details. To do this, however, we need to take a step back. It’s possible to prove that the overestimation

continues to be valid if T and R are expressed by the following formulas, to be used instead of (1) and (2):

Compared to the previous formulas, we have imposed an additional condition on d_1 and d_2, establishing that they must be less than z. But how is it possible to make a change of this magnitude without distorting the reasoning?
The reason is that we have full freedom in choosing the \lambda_d parameters. In fact, remember that (Selberg’s sieve: statement and beginning of the proof) they can be any real numbers, except \lambda_1 which must be equal to 1. So we can choose them arbitrarily, and nothing prevents us from putting:

This way, equations (1) and (2) would be equivalent to (1′) and (2′) respectively; in fact in all terms with d_1 \gt z or with d_2 \gt z we would have that \lambda_{d_1} \lambda_{d_2} = 0, therefore such terms would be equal to zero.

This modification can be introduced from the beginning and, apart from a single exception, does not modify the logical and algebraic steps of the previous articles: it only adds one more condition in each formula (depending on the case, d \lt z, d_1 \lt z, d_2 \lt z or d^{\prime} \lt z). For example, formulas (10) and (12) of the article Selberg’s sieve: study of the parameters λ would respectively become:

In this article, however, the meaning of the symbol d is a little different: it is the least common multiple of d_1 and d_2, which in turn are both less than z. In this regard, being d_1, d_2 \lt z \Rightarrow d_1 d_2 \lt z^2, and \mathrm{lcm}(d_1, d_2) \leq d_1 d_2, the following property holds:

which however is not valid in the other sense, as it can be easily checked (if for example z = 10, \mathrm{lcm}(50, 50) = 50 \lt 100 but 50 is not less than 10). So, being d = \mathrm{lcm}(d_1, d_2), we can say that:

In fact, the summation on the right will have at least the same terms as the one on the left, because the lowest common multiples smaller than z^2 are at least those obtainable starting from two numbers smaller than z. The \leq on the right is therefore less stringent than the one on the left (and consequently the increase is less precise); however, the formula on the right is still preferred because the other one is less explicit, given that d_1 and d_2 don’t appear as variables in the summation; only d appears, which is derived from them.

Our final estimate of the error will therefore be the following:

This restriction on d greatly lowers the overestimate of R; in fact, as z increases, the divisors of P(z) less than z^2 become an increasingly smaller fraction of the total, hence the condition tends to exclude most of the possible terms, making the increase much closer to the real value. To understand the extent of this effect, it’s useful to compare the graphs of the overestimates (8) and (8′). We’ll do this by taking the example of the article Selberg’s sieve: statement and beginning of the proof, where we have used the parameters of the sieve of Eratosthenes, i.e. N \gt 1, A = \{1, 2, \ldots, N\} and z = \sqrt {N + 1}:

As you can see, the two increases have very different orders of magnitude. The graphs are also qualitatively different, because the one of the error function without the limitation on d shows some jumps, which occur when, from one value of N to another, a new prime number is added in the product P(z): this doubles the number of ds considered in the summation (because the number of divisors of a product of k+1 prime numbers is double that of a product of k prime numbers), so the final value is suddently much larger than the previous one.