An overestimate of the number of Goldbach pairs

Prerequisites:

Given an even number N \gt 2, we’ll call Goldbach pairs for N the pairs of prime numbers whose sum is N; if the Goldbach’s conjecture were true, the number of these pairs would be at least 1, whatever N. In this article we’ll reason in the opposite direction: we’ll find an overestimate of the number of Goldbach pairs, that is, we’ll establish how many there can be at most. We’ll do this using the sieve theory developed so far, in particular Selberg’s sieve.

The problem of finding an upper estimate of the number of Goldbach pairs may seem trivial. For example, one may observe that prime pairs the sum of which is N must surely be found in the set \{(2, N-2), (3, N-3), (4, N-4), \ldots, (N-4, 4), (N-3, 3), (N-2, 2)\} (while 1 + (N - 1) is not a valid pair, since 1 is not prime); this set contains N - 3 elements, so the Goldbach pairs for N can be at most N - 3.
Actually, it’s not the problem that is trivial, but only the specific solution that we have described. In fact, the excess estimate N - 3, in addition to being very far from the actual number of Goldbach pairs for N, does not provide any useful information, since to obtain it we simply counted all the possible pairs of integers greater than 1 that have N as sum. In this article we’ll see that, using more sophisticated techniques, it’s possible to obtain a lower estimate, therefore a better one, even with a lower asymptotic order. We’ll therefore exclude a significant number of these N - 3 pairs, which are certainly not Goldbach pairs.
We could make a similar argument for the underestimate: in this case too, in fact, there is a trivial estimate, which is 0, because in the worst case there may be no pair. This estimate, in addition to being far from reality, is as trivial as the previous overestimate, because it does not provide any useful information, being based on an obvious principle (the counting of anything is at least 0). Goldbach’s Conjecture instead says that an underestimate is 1: this estimate is also far from the real value, but it’s not trivial, as it asserts something qualitatively very different, namely that at least one pair always exists: from a mathematical point of view, this can be valuable information.

The final result we’ll arrive at is the following:

Overestimate of the number of Goldbach pairs

Let N be an even number greater than 2 and let \mathfrak{R}(N) be the number of times N can be written as a sum of two primes (number of Goldbach pairs). Then:

\mathfrak{R}(N) \ll \prod_{p \mid N} \left(1 + \frac{1}{p}\right) \frac{N}{\log^2 N} \tag{1}

Recall that the \ll notation is equivalent to the big-Oh notation.

It should be clarified that when we talk about “writings of N as a sum”, we mean the number of ordered pairs of prime numbers the sum of which is N. For example, if N = 12, the writings 12 = 5 + 7 and 12 = 7 + 5 are considered different, so they both count in \mathfrak{R}(12). This is not a problem, however, because if we want to know the number of unordered pairs, we can calculate it from the number of ordered pairs.

How can we calculate the number of unordered pairs from the number of ordered pairs?

If N is not of the form p + p, all pairs have distinct addends, so the number of unordered ones is exactly half the number of ordered ones, so it’s \frac{\mathfrak{R}(N)}{2}.
If instead N = p + p, it should be noted that the ordered pair p + p remains identical by changing the order of the addends, so it is not counted twice like the other ordered pairs. Then, to obtain the number of unordered pairs, it’s best to first calculate half the number of the other ordered pairs, that is \frac{\mathfrak{R}(N) - 1}{2}, then add 1 to consider the pair p + p (this time seen as an unordered pair) that had been excluded. In this case the number of unordered pairs is therefore \frac{\mathfrak{R}(N) - 1}{2} + 1, which in turn is equal to \frac{\mathfrak{R}(N) + 1}{2}.

The formula of Theorem C.6 presents two very significant factors:

  • The factor \prod_{p \mid N} \left(1 + \frac{1}{p}\right) grows as the number of prime factors of N increases; this is consistent with the empirical observation that, when comparing the number of Goldbach pairs of even numbers close to each other, those with more prime factors generally have more Goldbach pairs (interested readers can experiment with our Goldbach pairs viewer).
  • The factor \frac{N}{\log^2 N} can be seen as the product \frac{N}{\log N} \cdot \frac{1}{\log N}. Let’s analyze both factors:
    • By the Prime Number Theorem, \frac{N}{\log N} is an estimate of the number of primes less than or equal to N. So this factor approximately counts the number of pairs of the form (p, N - p), with p prime.
    • The factor \frac{1}{\log N}, by the same Theorem, is the approximate probability that a number less than or equal to N is prime; in fact we can rewrite \frac{1}{\log N} as \frac{N / \log N}{N}, where N / \log N is the number of favorable cases (prime numbers less than or equal to N) and N is the number of possible cases (positive integers less than or equal to N).

    If we now assume the probability that N - p is prime to be equal to the probability that a generic positive integer less than or equal to N is prime, that is, \frac{1}{\log N}, then the product \frac{N}{\log N} \cdot \frac{1}{\log N} = \frac{N}{\log^2 N} would be an estimate of the number of pairs of the form (p, N - p) in which N - p is prime, that is, an estimate of the number of Goldbach pairs. Clearly in this reasoning the strong, unproven assumption is that the probability that N - p is prime depends neither on N nor on p.

It’s good to keep in mind, however, that both of these observations are based on the formula of Theorem C.6, which does not claim to compute the number of Goldbach pairs, not even approximately, but only presents an asymptotic overestimation; therefore, in principle, the actual number of Goldbach pairs could have a different behavior. On the other hand, indeed there seems to be a strong similarity between the asymptotic increase of Theorem C.6 and the true value of \mathfrak{R}(N), as far as empirical evidence and our intuition allow us to understand. In this regard, you can also observe the strong similarity of the formula on the right of (1) with that of the Hardy-Littlewood Conjecture A, which according to its creators would estimate \mathfrak{R}(N) in an asymptotically correct way.

Goldbach sieve

In previous articles we have seen that a sieve consists of a function that counts how many elements remain in a set of natural numbers A after eliminating all multiples of prime numbers less than a real number z, where z is a parameter established by the sieve itself. We know that, by choosing appropriately A and z, as in the sieve of Eratosthenes, it is possible to keep only prime numbers in the set.
In the case of Goldbach’s Conjecture, the situation seems to be different, because the starting set A should be a set of pairs and not of numbers. For example, we could define A := \{(1, N-1), (2, N-2), (3, N-3), \ldots, (N-3,3), (N-2,2), (N-1,1)\} and eliminate, using the sieve, all pairs where at least one of the two elements is a multiple of one of the prime numbers considered. Actually, however, it’s not necessary to introduce the pairs explicitely, because for every prime number p the following property holds, which is a consequence of the definition of prime number (Property N.1B):

p \textrm{is a divisor of at least one of the elements of the pair} (a, b) \Leftrightarrow p \mid ab

So we can replace the pairs with the product of their elements, thus obtaining a numerical set to which we can apply the sieve mechanism that we already know, based on the divisibility relation. By the cited property, the sieve applied to the pairs will give the same result (i.e. the same number of remaining elements) as the sieve applied to the products of their elements, as you can see in the following example:

Let N = 12 and suppose we want to count, using a sieve, the number of pairs of natural numbers that are not divisible by 2 or 3, whose sum is N. We’ll start from the set of pairs of all natural numbers that add up to N:

\{(1, 11), (2, 10), (3, 9), (4, 8), (5, 7), (6, 6), (7, 5), (8, 4), (9, 3), (10, 2), (11, 1)\}

Removing all pairs where at least one of the elements is divisible by 2 or 3, the following ones remain:

\{(1, 11), (5, 7), (7, 5), (11, 1)\} \tag{1}

Now let’s replace each pair in the initial set with the product of its elements:

\{11, 20, 27, 32, 35, 36, 35, 32, 27, 20, 11\} \tag{2}

Removing all elements divisible by 2 or 3, the following ones remain:

\{11, 35, 35, 11\}

which are precisely the products of the elements of the pairs of the set (1); in particular, their cardinality is also the same.

However, there is one aspect that requires further explanation. While the pairs, considered as ordered, are all distinct, when we move on to the products we obtain repeated elements, as you can see in the set (2) of the example, which should more correctly be written as \{11, 20, 27, 32, 35, 36\}. However, in order not to change the nature of the problem, we want to maintain a one-to-one correspondence between products and pairs; to do this, we consider the set of products as an ordered collection of elements that admits duplicate elements, unlike “normal” sets that are unordered and do not admit duplicates. In mathematics, an ordered collection of elements, possibly duplicated, is called a family. The same notations as sets are applied to families (curly brackets, the membership symbol, etc.) and sieve theory applies to both sets and families. In the definition of sieve we could therefore replace the term “set” with “family” and no theorem of sieve theory would change; however, for greater correctness, we’ll always specify when we are dealing with a family rather than a set.
So, our sieve function will be the following:

Goldbach sieve

Let them be:

  • N an even number greater than 2
  • z \gt 1 a real number
  • A the family, of N elements, \set{n(N - n) | 1 \leq n \leq N}

We’ll call Goldbach sieve, with parameters N and z, the sieve function S(A, \mathbb{P}, z).

For now, we don’t set the z parameter, because at the end of the article we’ll understand what is the most appropriate value to assign to it; the important thing is to keep in mind that it’s a real number that we can set at will, as long as it’s greater than 1.

Since it’s convenient for calculations that the family A has N elements, usually among the possible values of n it’s admitted that n = N, even if this choice generates the element N(N - N) = 0 which will certainly be eliminated from the sieve, because any prime number is a divisor of 0.

Goldbach sieve is related to the number of Goldbach pairs as follows:

Relationship between Goldbach sieve and the number of Goldbach pairs

Let N be an even number greater than 2 and z \gt 1 be a real number. Let S(A, \mathbb{P}, z) be the Goldbach sieve with parameters N and z. Then:

\mathfrak{R}(N) \leq 2z + S(A, \mathbb{P}, z) \tag{3}

Let G := \{(p, q) \mid p + q = N\} be the set of Goldbach pairs for N (as always we denote with p and q some prime numbers). We can partition this set into three subsets:

  • G_1 := \{(p, q) \mid p + q = N, p \leq z\}
  • G_2 := \{(p, q) \mid p + q = N, z \lt p \lt N - z\}
  • G_3 := \{(p, q) \mid p + q = N, p \geq N - z\}

Surely |G_1| \leq z, because the elements of G_1 are at most as many as the prime numbers p \leq z, which in turn they are at most z (they would be z if all the integers between 1 and z were prime, which is not true, but as an overestimation it’s fine; to be more precise we could say that |G_1| \leq \pi(z), but that would not improve the final statement significantly).
Similarly, we can say that |G_3| \leq z, because the elements of G_3 are at most as many as the prime numbers p between N - z and N - 1, which in turn are at most z (they would be z if all the integers between N - z and N - 1 were prime).

As for G_2, from the condition z \lt p \lt N - z we can immediately obtain that p \gt z, but we can also obtain that q = N - p \gt N - (N - z) = z, that is, q \gt z. Since both p and q are greater than z and are prime, they are certainly not divisible by any prime less than z; the same can therefore be said of their product pq. Recall that the sieve function S(A, \mathbb{P}, z) counts the elements of the family A that are not divisible by any prime less than z: one of these elements will therefore be pq. Since this is true for every p and q that fall within the definition of the set G_2, we can conclude that all elements of G_2 fall within the sieve count, so |G_2| \leq S(A, \mathbb{P}, z).

In conclusion, we’ll have that:

\mathfrak{R}(N) = |G| = |G_1| + |G_2| + |G_3| \leq z + S(A, \mathbb{P}, z) + z = 2z + S(A, \mathbb{P}, z)

In the following we’ll use (3) to find a bound of \mathfrak{R}(N). To bound the sieve function S(A, \mathbb{P}, z) we’ll use the Selberg’s sieve in its most general form.

The f function of Selberg’s sieve applied to Goldbach pairs

We know that, in the most specific form of Selberg’s sieve, the f function used is f(d) = \frac{1}{d}. As we saw in the previous article, this f function contains the meaning of the entire sieve, because it must be chosen so that |A| f(d) approximates as closely as possible the number of multiples of d present in the set A. If A = \set{1, \ldots, N}, the function f(d) = \frac{1}{d} is fine, because in that case |A| f(d) = \frac{|A|}{d} = \frac{N}{d} is a good estimate of the number of multiples of d in the set A. If instead we set A equal to the family of Definition C.3, the function \frac{1}{d} is no longer fine, as you can see from the following example.

Let N = 20 and d = 3. Let’s calculate the family A:

\begin{aligned} A &= \set{n(N - n) | 1 \leq n \leq N} \\ &= \left\{\begin{aligned}1 \cdot 19, 2 \cdot 18, 3 \cdot 17, 4 \cdot 16, 5 \cdot 15, 6 \cdot 14, 7 \cdot 13, 8 \cdot 12, 9 \cdot 11, 10 \cdot 10 \\ 11 \cdot 9, 12 \cdot 8, 13 \cdot 7, 14 \cdot 6, 15 \cdot 5, 16 \cdot 4, 17 \cdot 3, 18 \cdot 2, 19 \cdot 1, 20 \cdot 0 \end{aligned}\right\} \\ &= \left\{\begin{aligned}19, 36, 51, 64, 75, 84, 91, 96, 99, 100 \\ 99, 96, 91, 84, 75, 64, 51, 36, 19, 0 \end{aligned}\right\} \end{aligned}

The multiples of 3 are the following: 36, 51, 75, 84, 96, 99, 99, 96, 84, 75, 51, 36, and 0, for a total of 12. It may seem strange to see duplicates, but we have to remember that we are dealing with a family, not a set. To clarify the meaning of these numbers, it’s useful to reconstruct the pairs of factors associated with each one; by doing so, we can say that the numbers to eliminate are those corresponding to the pairs: (2, 18), (3, 17), (5, 15), (6, 14), (8, 12), (9, 11), (11, 9), (12, 8), (14, 6), (15, 5), (17, 3), (18, 2), (20, 0). We can partition these pairs into two subsets:

  • those in which the first element is a multiple of 3, and not the second: (3, 17), (6, 14), (9, 11), (12, 8), (15, 5), (18, 2), for a total of 6;
  • those in which the second element is a multiple of 3, and not the first: (17, 3), (14, 6), (11, 9), (8, 12), (5, 15), (2, 18) and (20, 0), for a total of 7;

There are no pairs in which both elements are multiples of 3. In fact, if this were the case, their sum would also be a multiple of 3, but this sum is N = 20, which is not a multiple of 3, so the hypothetical situation in which both elements of the pair are multiples of 3 cannot occur.

Now, if we try to compute |A| f(d) with f(d) = \frac{1}{d}, we get |A| f(d) = \frac{|A|}{d} = \frac{20}{3} \approx 6, while the correct result would be 13. This happens because the fraction \frac{20}{3} approximates the number of multiples of d in a range of 20 consecutive integers; this is equivalent to counting in how many pairs only the first element (which is between 1 and 20) is a multiple of 3, or equivalently only the second (which is between 0 and 19), but not any of the two. A function that gives us the correct result in this case is \frac{2}{d}, because |A| \frac{2}{d} = \frac{2|A|}{d} = \frac{40}{3} \approx 13.

There are other cases, however, where the \frac{1}{d} function is fine, as the following example shows:

Let N = 20 and d = 5. In the family A, which is the same as the previous example, the multiples of 5 are 75, 100, 75 and 0, for a total of 4. They correspond to the pairs (5, 15), (10, 10), (15, 5) and (20, 0), which are the only pairs where both elements are multiples of 5. This case is the opposite of the previous one, in the sense that there are no pairs where only one of the two elements is a multiple of 5; if this were the case, in fact, their sum would not be a multiple of 5, but the sum is 20 which is a multiple of 5, therefore the hypothesized case cannot occur.
For d = 5 the function \frac{1}{d} returns the correct result, because |A| \frac{1}{d} = \frac{|A|}{d} = \frac{20}{5} = 4, which is exactly the number of pairs we wanted. In fact, the fraction \frac{20}{5} represents the number of multiples of 5 in a set of 20 consecutive integers, which can be for example the set of the first elements of the pairs. This time, however, unlike the previous example, if the first element is a multiple of 5, the second is also a multiple of 5; so the pairs where one of the two elements is a multiple of 5 are the same as those where only the first element is a multiple of 5, the cardinality of which is given by the formula \frac{20}{5}.

The two previous examples are summarized in the following figure:

Illustration of the Goldbach sieve
Figure 1: Illustration of the Goldbach sieve

In general, if d is a prime number, the following two cases can occur:

  • If d \nmid N, the number of elements of A that are multiples of d, which is equal to the number of corresponding pairs where one of the two elements is a multiple of d, is approximately \frac{2|A|}{d}, then f(d) = \frac{2}{d};
  • If d \mid N, the same count of multiples (or corresponding pairs), is approximately \frac{|A|}{d}, then f(d) = \frac{1}{d}.

More compactly, using as usual the letter p to indicate a prime number:

f(p) := \begin{cases} \frac{1}{p} & \textrm{if} p \mid N \\ \frac{2}{p} & \textrm{otherwise} \end{cases} \tag{4}

To obtain the value of this new function f on composite numbers and on 1, it’s enough to remember, from the statement of the Selberg’s sieve, that f must be completely multiplicative, and as such it’s enough to define it on prime numbers, because all the other values of the function for integers greater than 1 are obtained by applying Property N.26, furthermore f(1) = 1 again by definition of completely multiplicative function.

How does the f function behave in the sieve, when counting in the set A the multiples of a number that is not square-free?

It can be observed that, if d is not square-free, if we apply the f function that we have defined in the sieve, we’ll obtain an incorrect result.
For example, if N = 20 and d = 9, the elements of the family A that are multiples of 9 are 36, 99, 99 and 36, for a total of 4 (the corresponding pairs are (2, 18), (9, 11), (11, 9) and (18, 2)), while applying the formula |A| f(d) we get more than double: |A| f(d) = 20 f(9) = 20 f(3) f(3) = 20 \cdot \frac{2}{3} \cdot \frac{2}{3} = \frac{80}{9} \geq 8.

But this is not a problem, because actually it’s not the value of the function that is wrong, but the initial question. In fact, all the argument behind Selberg’s sieve, developed in previous articles, considers only numbers d which are square-free; in fact, as you can see in many formulas of the proof, d is always a divisor of P(z), which is square-free, both in the estimate term of the sieve and in the error term.
The only part of the Theorem where it’s necessary for f to be defined on all integers is the final one, which occurs after having already found the following overestimation (formula (7) of the article Selberg’s sieve: generalization and conclusion of the proof):

S(A, \mathbb{P}, z) \leq \frac{|A|}{V(z)} + \sum_{\substack{d \lt z^2 \\ d \mid P(z)}} 3^{\omega(d)} |r(d)|

to obtain which, during the proof, it was sufficient to apply f to square-free numbers (for further information, see the last detail of the cited article).

The need for f to be defined on all integers (and to be completely multiplicative) therefore arises a posteriori with respect to the sieve, when, in order to simplify the previous inequality, it’s shown that (formula (8) of the cited article):

V(z) \geq \sum_{1 \leq n \lt z} \frac{1}{n}

where, as we know, \frac{1}{n} is generalized as f(n) in the most general form of the Theorem (so it’s necessary that f is defined at least on all positive integers less than z). The preceding overestimation, however, is a purely numerical step that has nothing to do with the sieve mechanism, so it does not matter if f(n), for not square-free numbers, assumes values that, if they were used in the sieve, would be wrong. What matters, in this “numerical” phase of the proof of the Theorem, is only that the function is completely multiplicative, not the particular values it assumes.

Application of Selberg’s sieve

In order to overestimate the Goldbach’s sieve function S(A, \mathbb{P}, z) which appears in (3), we’ll apply the Selberg’s sieve (Theorem C.5), remembering that in our case |A| = N:

S(A, \mathbb{P}, z) \leq \frac{N}{\sum_{1 \leq n \lt z} f(n)} + \sum_{\substack{d \lt z^2 \\ d \mid P(z)}} 3^{\omega(d)} |r(d)| \tag{5}

Let’s see what happens when we consider the function defined by (4) as the function f.

As for the first term of (5), the following Lemma can be applied:

Asymptotic upper bound of Selberg’s sieve estimate applied to Goldbach pairs

Let f be the function given by (4). Then:

\frac{1}{\sum_{1 \leq n \lt z} f(n)} \ll \prod_{p \mid N} \left(1 + \frac{1}{p}\right) \frac{1}{\log^2 z}

Consider a positive integer n \lt z. We can factor n by distinguishing between the prime factors that divide N, which we’ll call p_1, \ldots, p_k, and those that do not divide it, which we’ll call q_1, \ldots, q_r:

n = p_1^{a_1} \ldots p_k^{a_k} q_1^{b_1} \ldots q_r^{b_r}

with a_1, \ldots, a_k, b_1, \ldots, b_r \gt 0.

Let’s calculate f(n), remembering that it’s completely multiplicative:

\begin{aligned} f(n) &= \\ f(p_1^{a_1} \ldots p_k^{a_k} q_1^{b_1} \ldots q_r^{b_r}) &= \\ f(p_1)^{a_1} \cdot \ldots \cdot f(p_k)^{a_k} \cdot f(q_1)^{b_1} \cdot \ldots \cdot f(b_r)^{b_r} &= \\\frac{1}{p_1^{a_1}} \cdot \ldots \cdot \frac{1}{p_k^{a_k}} \cdot \frac{2^{b_1}}{q_1^{b_1}} \cdot \ldots \cdot \frac{2^{b_r}}{q_r^{b_r}} & = \\\frac{2^{b_1 + \ldots + b_r}}{p_1^{a_1} \ldots p_k^ {a_k} q_1^{b_1} \ldots q_r^{b_r}} & = \\\frac{2^{b_1 + \ldots + b_r}}{n} \end{aligned} \tag{a}

Now let’s consider the number of divisors of n coprime to N and let’s indicate with d(n, N) their cardinality:

d(n, N) := |\set{d \mid n \textrm{such that }\mathrm{GCD}(d, N) = 1}|

We can calculate exactly what these divisors are; in fact, if d is a divisor of n coprime with N, in its factorization only q_1, \ldots, q_r can appear as prime factors, each with an exponent not greater than the one it has in the factorization of n. So d must be of the type:

d = q_1^{c_1} \ldots q_r^{c_r}

with 0 \leq c_1 \leq b_1, \ldots, 0 \leq c_r \leq b_r (if the exponent is zero, the prime number is absent in the factorization of d).
Considering all possible combinations of exponents, we’ll have (1 + b_1)\cdot\ldots\cdot(1 + b_r) possibilities for d, so

d(n, N) = (1 + b_1)\cdot\ldots\cdot(1 + b_r)

We can observe that, if b_1 = \ldots = b_r = 1, that is, if n is square-free, this number is equal to \underbrace{2 \cdot \ldots \cdot 2}_{r \textrm{times}} = 2^r = 2^{b_1 + \ldots + b_r}, so it would coincide with the numerator of f(n) given by (a). In general, without making additional assumptions about b_1, \ldots, b_r, we can say that:

d(n, N) = (1 + b_1)\cdot\ldots\cdot(1 + b_r) \leq 2^{b_1} \cdot \ldots \cdot 2^{b_r} = 2^{b_1 + \ldots + b_r} \tag{b}

In fact, for every b_i \in \set{b_1, \ldots, b_r}, if b_i = 1 then 1 + b_i = 2 = 2 ^{b_1}, while if b_i \gt 1, it’s easy to see that the exponential function generates larger values than the other (for 1 + b_i = 3, 4, 5, \ldots, while 2^{b_i} = 4, 8, 16, \ldots, respectively); this can be proved for example by induction.
So from (a) and (b) we can conclude that:

f(n) \geq \frac{d(n, N)}{n} \tag{c}

Now consider the product \prod_{p \mid N}\left(1 - \frac{1}{p} \right)^{-1}. By Property A.26 we have that:

\prod_{p \mid N}\left(1 - \frac{1}{p} \right)^{-1} = \sum_{a \in A} \frac{1}{a} \tag{d}

where

A := \set{a \geq 1 | \textrm{in the factorization of $a$ there are only prime factors of $N$}}

From (c) and (d) we’ll have:

\begin{aligned} \sum_{1 \leq n \lt z} f(n) \prod_{p \mid N}\left(1 - \frac{1}{p} \right)^{-1} & \geq \\\sum_{1 \leq n \lt z} \frac{d(n, N)}{n} \sum_{a \in A} \frac{1}{a} &= \\\sum_{1 \leq n \lt z} d(n, N) \sum_{a \in A} \frac{1}{na} \end{aligned} \tag{e}

Let s := na.

The innermost summation contains all fractions of the type \frac{1}{s} with 1 \leq s \lt z, because, given such a s, we can set n := s and a := 1 (these choices are legitimate because by hypothesis n = s satisfies the condition 1 \leq n \lt z of the first summation, while, as required by the second summation, a = 1 \in A, because 1 has no prime factors). A fraction of the type \frac{1}{s} can however appear more than once, because there can be various choices of n and a the product of which is s. In particular, we can choose n among the divisors of s and then check whether a = \frac{s}{n} \in A: the fraction \frac{1}{s} will appear every time the check is successful, and each time it will be multiplied by the same term d(n, N) of the external sum. We can then exchange the sums this way:

\textrm{(e)} \geq \sum_{s \lt z} \frac{1}{s} \sum_{\substack{n \mid s \\\frac{s}{n} \in A}} d(n, N) \tag{f}

where the \geq is because the internal sum of (e) also contains fractions having s \geq z that we have not considered, while (f) includes only fractions of the type \frac{1}{s}, with 1 \leq s \lt z, which however also appear in (e). Therefore, if we expanded the double sums, the terms of (f) would be a subset of the terms of (e).

Let N := 20 and z := 11. The prime factors of N are 2 and 5, so the set A contains all positive integers in the factorization of which only 2 and 5 appear, that is:

A = \set{1, 2, 4, 5, 8, 10, 16, 25, \ldots}

In this case (e) can be expanded as follows:

\begin{aligned} \sum_{1 \leq n \lt 11} d(n, 20) \sum_{a \in A} \frac {1}{na} = & d(1, 20) \cdot \left(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{5} + \frac {1}{8} + \frac{1}{10} + \frac{1}{16} + \frac{1}{25} + \ldots \right) + \\ & d(2, 20) \cdot \left(\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{10} + \frac{1}{16} + \frac{1}{20} + \frac{1}{32} + \frac{1}{50} + \ldots \right) + \\ & d(3, 20) \cdot \left(\frac{1}{3} + \frac{1}{6} + \frac{1}{12} + \frac{1}{15} + \frac{1}{24} + \frac{1}{30} + \frac{1}{48} + \frac{1}{75} + \ldots \right) + \\ & d(4, 20) \cdot \left(\frac{1}{4} + \frac {1}{8} + \frac{1}{16} + \frac{1}{20} + \frac{1}{32} + \frac{1}{40} + \frac{1}{64} + \frac{1}{100} + \ldots \right) + \\ & d(5, 20) \cdot \left(\frac{1}{5} + \frac{1}{10} + \frac{1}{20} + \frac{1}{25} + \frac{1}{40} + \frac{1}{50} + \frac{1}{80} + \frac{1}{125} + \ldots \right) + \\ & d(6, 20) \cdot \left(\frac{1}{6} + \frac{1}{12} + \frac{1}{24} + \frac {1}{30} + \frac{1}{48} + \frac{1}{60} + \frac{1}{96} + \frac{1}{150} + \ldots \right) + \\ & d(7, 20) \cdot \left(\frac{1}{7} + \frac{1}{14} + \frac{1}{28} + \frac{1} {35} + \frac{1}{56} + \frac{1}{70} + \frac{1}{112} + \frac{1}{175} + \ldots \right) + \\ & d (8, 20) \cdot \left(\frac{1}{8} + \frac{1}{16} + \frac{1}{32} + \frac{1}{40} + \frac{1}{64} + \frac{1}{80} + \frac{1}{128} + \frac{1}{200} + \ldots \right) + \\ & d(9, 20) \cdot \left(\frac{1}{9} + \frac{1}{18} + \frac{1}{36} + \frac{1}{45} + \frac{1}{72} + \frac{1}{90} + \frac{1}{144} + \frac{1}{225} + \ldots \right) + \\ & d(10, 20) \cdot \left(\frac{1}{10} + \frac{1}{20} + \frac{1}{40} + \frac{1}{50} + \frac{1}{80} + \frac{1}{100} + \frac{1}{160} + \frac{1}{250} + \ldots \right)\end{aligned}

We can observe that in the summations all the fractions of the type \frac{1}{s} with 1 \leq s \lt 11 appear, plus many others that we’ll not consider, which are the reason for the \geq in (f). The number 1 = \frac{1}{1} appears only once because it has itself as only divisor. Also the fractions \frac{1}{3}, \frac{1}{7} and \frac{1}{9} appear only once because, even if their denominators have more than one divisor, in all three cases only the divisor 1 belongs to A, while the others (3, 9 and 7) don’t. Even for the fraction \frac{1}{6}, only some of the divisors of the denominator belong to A: 6 has divisors 1, 2, 3 and 6 but only the first two belong to A, so the fraction appears twice. Finally, in the other fractions (\frac{1}{2}, \frac{1}{4}, \frac{1}{8} and \frac{1}{10}) all divisors of the denominator belong to A, so, in these cases, the number of occurrences is equal to the number of divisors. For example, all three divisors of 4 (1, 2 and 4) belong to A, so the fraction \frac{1}{4} appears three times.

Now let’s highlight the fractions of the type \frac{1}{s} with 1 \leq s \lt 11:

\begin{aligned} 1 & \cdot d(1, 20) + \\\frac{1}{2} & \cdot \left(d(1, 20) + d(2, 20) \right) + \\\frac{1}{3} & \cdot \left(d(3, 20) \right) + \\\frac{1}{4} & \cdot \left(d(1, 20) + d(2, 20) + d(4, 20) \right) + \\\frac{1}{5} & \cdot \left(d(1, 20) + d(5, 20) \right) + \\\frac{1}{6} & \cdot \left(d(3, 20) + d(6, 20) \right) + \\\frac{1}{7} & \cdot \left(d(7, 20) \right) + \\\frac{1}{8} & \cdot \left(d(1, 20) + d(2, 20) + d(4, 20) + d(8, 20) \right) + \\\frac{1}{9} & \cdot \left(d(1, 20) \right) + \frac{1}{10} & \cdot \left(d(1, 20) + d(2, 20) + d(5, 20) + d(10, 20) \right) \end{aligned} \tag{g}

We can observe that each fraction \frac{1}{s} is multiplied by a sum of elements of the type d(n, 20); as we observed before, the number of elements of the sum (which corresponds to the number of occurrences of the fraction \frac{1}{s} in the previous expression) is equal to the number of divisors of s that belong to A. To see these divisors, however, we must write the n obtained as a fraction that has s as its numerator:

\begin{aligned} 1 & \cdot d\left(\frac{1}{\colorbox{aqua}{1}}, 20\right) + \\\frac{1}{2} & \cdot \left(d\left(\frac{2}{\colorbox{aqua}{2}}, 20\right) + d\left(\frac{2}{\colorbox{aqua}{1}}, 20\right) \right) + \\\frac{1}{3} & \cdot \left(d\left(\frac{3}{\colorbox{aqua}{1}}, 20\right) \right) + \\\frac{1}{4} & \cdot \left(d\left(\frac{4}{\colorbox{aqua}{4}}, 20\right) + d\left(\frac{4}{\colorbox{aqua}{2}}, 20\right) + d\left(\frac{4}{\colorbox{aqua}{1}}, 20\right) \right) + \\\frac{1}{5} & \cdot \left(d\left(\frac{5}{\colorbox{aqua}{5}}, 20\right) + d \left(\frac{5}{\colorbox{aqua}{1}}, 20\right) \right) + \\\frac{1}{6} & \cdot \left(d\left(\frac{6}{\colorbox{aqua}{2}}, 20\right) + d\left(\frac{6}{\colorbox{aqua}{1}}, 20\right) \right) + \\\frac {1}{7} & \cdot \left(d\left(\frac{7}{\colorbox{aqua}{1}}, 20\right) \right) + \\\frac{1}{8} & \cdot \left(d \left(\frac{8}{\colorbox{aqua}{8}}, 20\right) + d\left(\frac{8}{\colorbox{aqua}{4}}, 20\right) + d \left(\frac{8}{\colorbox{aqua}{2}}, 20\right) + d\left(\frac{8}{\colorbox{aqua}{1}}, 20\right) \right) + \\\frac{1}{9} & \cdot \left(d\left(\frac{9}{\colorbox{aqua}{9}}, 20\right) \right) + \\\frac {1}{10} & \cdot \left(d\left(\frac{10}{\colorbox{aqua}{10}}, 20\right) + d\left(\frac{10}{\colorbox{aqua}{5}}, 20\right) + d\left(\frac{10}{\colorbox{aqua}{2}}, 20\right) + d\left(\frac{10}{\colorbox{aqua}{1}}, 20\right) \right) \end{aligned} \tag{h}

The highlighted denominators, line by line, are the divisors of s that belong to A. Since the fractions are equal to n and since they have numerator s, their denominators are \frac{s}{n}, because n = \frac{s}{\colorbox{aqua}{s/n}}. So we can compactly express (h) as follows:

\sum_{s \lt 11} \frac{1}{s} \sum_{\substack{n \mid s \\\colorbox{aqua}{$\frac{s}{n}$} \in A}} d(n, 20)

which is in agreement with the second member of (f).

Now let’s simplify the summation \sum_{\substack{n \mid s \\\frac{s}{n} \in A}} d(n, N).

In the following we’ll use the function d which returns the number of divisors of a natural number; we’ll also use the notation d(s, N) to indicate the number of divisors of s coprime to N.

We can factor s by distinguishing between the prime factors that divide N, which we’ll call p_1, \ldots, p_k, and those that do not, which we’ll call q_1, \ldots, q_r (we are using the same symbols as at the beginning of the proof, but the two parts of the proof are to be understood as separate, so these p_1, \ldots, p_k, q_1, \ldots, q_r are not the same as before). Furthermore, we’ll call a the product of the factors that divide N and b the product of the others:

s = \underbrace{p_1^{a_1} \ldots p_k^{a_k}}_{a} \cdot \underbrace{q_1^{b_1} \ldots q_r^{b_r}}_{b} \tag{i}

with a_1, \ldots, a_k, b_1, \ldots, b_r \gt 0.

Now let’s prove that:

  1. d(a) \cdot d(b) = d(s)
  2. d(s, N) = d(b)
  3. If n \mid s and \frac{s}{n} \in A, then d(n, N) = d(s, N)
  4. The number of positive integers n such that n \mid s and \frac{s}{n} \in A is d(a)

Proof:

  1. If n \mid s, then we can write n as:

    n = \underbrace{p_1^{a_1^{\prime}} \ldots p_k^{a_k^{\prime}}}_{a^{\prime}} \cdot \underbrace{q_1^{b_1^{\prime}} \ldots q_r^{b_r^{\prime}}}_{b^{\prime}} \tag{j}

    with 0 \leq a_1^{\prime} \leq a_1, \ldots, 0 \leq a_k^{\prime} \leq a_k, 0 \leq b_1^{\prime} \leq b_1, \ldots, 0 \leq b_r^{\prime} \leq b_r.

    In particular, a^{\prime} \mid a and b^{\prime} \mid b, so to each divisor of s we can associate a pair (a^{\prime}, b^{\prime}) where a^{\prime} \mid a and b^{\prime} \mid b. But the converse is also true: if a^{\prime} \mid a, then a^{\prime} is of the type p_1^{a_1^{\prime}} \ldots p_k^{a_k^{\prime}} with 0 \leq a_1^{\prime} \leq a_1, \ldots, 0 \leq a_k^{\prime} \leq a_k and if b^{\prime} \mid b, then b^{\prime} is of the type q_1^{b_1^{\prime}} \ldots q_k^{b_k^{\prime}} with 0 \leq b_1^{\prime} \leq b_1, \ldots, 0 \leq b_k^{\prime} \leq b_k; hence their product, given by (j), is a divisor of s. In summary, there is a one-to-one correspondence between the divisors of s, the cardinality of which is d(s), and the pairs (a^{\prime}, b^{\prime}) with a^{\prime} \mid a and b^{\prime} \mid b, the cardinality of which is d(a) \cdot d(b). Hence d(a) \cdot d(b) = d(s).

  2. Starting from (i), we can observe that the divisors of s coprime to N are the divisors of b. In fact, if a divisor is coprime to N it can have as prime factors only q_1, \ldots, q_r, therefore it divides b; vice versa, a divisor of b is also a divisor of s, and it’s coprime to N because it only has prime factors that do not divide N. Therefore, passing to cardinalities, d(s, N) = d(b).

  3. From (i) and (j) we’ll have:

    \frac{s}{n} = p_1^{a_1 - a_1^{\prime}} \ldots p_k^{a_k - a_k^{\prime}} \cdot q_1^{b_1 - b_1^{\prime}} \ldots q_r^{b_r - b_r^{\prime}}

    but by hypothesis \frac{s}{n} \in A, so it must have only prime factors of N, therefore the factors q_1, \ldots, q_r must have zero exponent. So:

    \begin{aligned} n \mid s, \frac{s}{n} \in A & \Rightarrow \\ b_1 = b_1^{\prime}, \ldots, b_r = b_r^{\prime} & \Rightarrow \\ q_1^{b_1^{\prime}} \ldots q_r^{b_r^{\prime}} = q_1 ^{b_1} \ldots q_r^{b_r} & \Rightarrow \\ b^{\prime} = b & \Rightarrow \\ d(b^{\prime}) = d(b) \end{aligned} \tag{k}

    Starting from (i) we have shown that d(s, N) = d(b); similarly, starting from (j), we can show that d(n, N) = d(b^{\prime}). Then, by (k), d(n, N) = d(s, N).

    Let’s consider the last line of (g):

    \frac{1}{10} \cdot \left(d(\colorbox{aqua}{1}, 20) + d(\colorbox{aqua}{2}, 20) + d(\colorbox{aqua}{5}, 20) + d(\colorbox{aqua}{10}, 20) \right)

    The highlighted numbers are the ns of the hypothesis, that are the divisors of s = 10 such that \frac{s}{n} \in A. This third point is telling us that, for all these numbers, the number of divisors coprime to N = 20 is equal to the number of divisors of s = 10 coprime to N = 20.
    In fact, the only divisor of 10 that is coprime to 20 is 1, and the same can be said for 1, 2, 5, and 10: the only divisor coprime to 20 for each of them is 1, because they are all divisors of 20.

    Now let’s analyze this other line:

    \frac{1}{6} \cdot \left(d(\colorbox{aqua}{3}, 20) + d(\colorbox{aqua}{6}, 20) \right)

    In this case the divisors of s = 6 coprime to 20 are 1 and 3, for a total of 2, so d(s, 20) = d(6, 20) = 2. We can observe that also for the two highlighted ns we have that d(n, 20) = d(s, 20): for n = 6 this is obvious because n = s, but the formula is also valid for the other n which is 3; in fact, both divisors of 3 are coprime to 20.

  4. From (j) and (k) we’ll have that:

    \begin{aligned} n \mid s, \frac{s}{n} \in A & \Rightarrow \\ b^{\prime} = b & \Rightarrow \\ n = \underbrace{p_1^{a_1^{\prime}} \ldots p_k^{a_k^{\prime}}}_{a^{\prime}} \cdot \underbrace{q _1^{b_1} \ldots q_r^{b_r}}_{b} \end{aligned}

    But b is fixed, because it depends only on s which was fixed initially, so the number of possible ns is equal to the number of possible a^{\prime}s. The latter, by the definition of n, are the possible divisors of a; therefore, by transitivity, we can conclude that the number of possible ns is d(a).

    This fourth point tells us how many addends there are inside the parentheses in each line of (g), because each addend is associated with a different value of n. For example, let’s analyze this line again:

    \frac{1}{10} \cdot \left(d(1, 20) + d(2, 20) + d(5, 20) + d(10, 20) \right)

    We can note that there are 4 terms in brackets: according to what we have proved, the divisors of a should also be 4, where a is that part of the factorization of s = 10 which includes only the prime factors of N = 20. In this case a = 10 because all the prime factors of s are also prime factors of N, and indeed 10 has 4 divisors.

    Now let’s analyze this other line:

    \frac{1}{6} \cdot \left(d(3, 20) + d(6, 20) \right)

    In this case s = 6. To obtain the value of a, we can factor 6 as in (i), separating the factors that divide N = 20 from those that do not:

    6 = \underbrace{2}_{a} \cdot \underbrace{3}_{b}

    So a = 2, which has 2 divisors. This is in agreement with the fourth point, because in the line we actually found 2 terms inside the brackets.

Based on the four points proved, we can conclude that:

\begin{aligned} \sum_{\substack{n \mid s \\\frac{s}{n} \in A}} d(n, N) &= \textrm{[by point 3]} \\\sum_{\substack{n \mid s \\\frac{s}{n} \in A}} d(s, N) & = \textrm{since [$s$ and $N$ are constants]} \\ d(s, N) \cdot \left|\left\{n \textrm{ such that }n \mid s, \frac{s}{n} \in A\right\}\right| &= \textrm{[by point 4]} \\ d(s, N) \cdot d(a) &= \textrm{[by point 2]} \\ d(b) \cdot d(a) &= \textrm{[by point 1]} \\ d(s) \end{aligned}

Resuming (e) and (f), we’ll have:

\sum_{1 \leq n \lt z} f(n) \prod_{p \mid N}\left(1 - \frac{1}{p} \right)^{-1} \geq \sum_{s \lt z} \frac{d(s)}{s}

The summation \sum_{s \lt z} \frac{d(s)}{s} has a known asymptotic order; in particular, by Proposition N.31, \sum_{s \lt z} \frac{d(s)}{s} \gg \log^2 z. So:

\sum_{1 \leq n \lt z} f(n) \prod_{p \mid N}\left(1 - \frac{1}{p} \right)^{-1} \gg \log^2 z

from which:

\sum_{1 \leq n \lt z} f(n) \gg \prod_{p \mid N}\left(1 - \frac{1}{p} \right) \log^2 z

Applying Property A.27, we’ll have:

\frac{1}{\sum_{1 \leq n \lt z} f(n)} \ll \prod_{p \mid N}\left(1 - \frac{1}{p} \right)^{-1} \frac{1}{\log^2 z} \tag{l}

The term of the producer can be rewritten as follows:

\begin{aligned} \left(1 - \frac{1}{p} \right)^{-1} &= \\ \left(\frac{p - 1}{p} \right)^{-1} &= \\ \frac{p}{p - 1} &= \\ \frac{p (p + 1)}{(p - 1)(p + 1)} &= \\ \frac{p}{p^2 - 1} \cdot (p + 1) &= \\\frac{p^2}{p^2 - 1} \cdot \frac{p + 1}{p} &= \\ \left(\frac{p^2 - 1}{p^2}\right)^{-1} \cdot \frac{p + 1} {p} &= \\ \left(1 - \frac{1}{p^2}\right)^{-1} \cdot \frac{p + 1}{p} \end{aligned}

Substituting into (l), we’ll have:

\frac{1}{\sum_{1 \leq n \lt z} f(n)} \ll \left(\prod_{p \mid N} \left(1 - \frac{1}{p^2}\right)^{-1} \right) \cdot \left(\prod_{p \mid N} \frac{p + 1}{p} \right) \cdot \frac{1}{\log^2 z} \tag{m}

Now, in analogy with formula (d), using the same logic of the proof of Property A.26, it can be shown that:

\prod_{p \mid N} \left(1 - \frac{1}{p^2}\right)^{-1} = \sum_{q \in Q} \frac{1}{q} \tag{n}

where:

Q := \Set{q \geq 1 | \begin{gathered} \textrm{in the factorization of $q$ there are} \\ \textrm{only prime factors of $N$, with even exponent} \end{gathered}}

But the numbers that in their factorization have only prime factors with even exponents are squares numbers, so:

Q = \Set{q \geq 1 | \begin{gathered} \textrm{$q$ is a square and in its factorization} \\ \textrm{there are only prime factors of $N$} \end{gathered}}

In particular, this set Q is a subset of the set of all square numbers, so surely the series \sum_{q \in Q} \frac{1}{q} is less than or equal to the series of reciprocals of all squares, that is \sum_{n \geq 1} \frac{1}{n^2}. So, starting from (n), we’ll have:

\prod_{p \mid N} \left(1 - \frac{1}{p^2}\right)^{-1} \leq \sum_{n \geq 1} \frac{1}{n^2} \tag{o}

But this last series, as it can be proved, is convergent, because the exponent of n is strictly greater than 1. It therefore has a finite sum L \in \mathbb{R}. So, by (o), the production is also limited by the same L:

\prod_{p \mid N} \left(1 - \frac{1}{p^2}\right)^{-1} \leq L

This makes the production asymptotically irrelevant; it can therefore be eliminated from (m), obtaining:

\frac{1}{\sum_{1 \leq n \lt z} f(n)} \ll \prod_{p \mid N} \frac{p + 1}{p} \cdot \frac{1}{\log^2 z}

So we have completed the proof.

As for the error term, to perform an asymptotic increase we need to calculate the order of magnitude of r(d). It’s given by the following Lemma:

Asymptotic order of the Selberg’s sieve error applied to Goldbach pairs

Let them be (the hypotheses indicated with (*) are additional or modified with respect to Selberg’s sieve statement):

  • (*) N a positive even number
  • (*) A the family, of N elements, \{n(N - n)\\mid\n \leq N\}
  • z \gt 1 a real number
  • P(z) the product of all prime numbers less than z
  • A_d the set of multiples of a natural number d which belong to A
  • (*) f the completely multiplicative function defined by (4)
  • r(d) := |A_d| - |A| f(d)
  • \omega(d) the number of distinct prime factors of d

Then, for every natural number d that divides P(z):

r(d) = O(2^{\omega(d)})

Since d \mid P(z), the factorization of d is a product of distinct primes, which we can partition into those that divide N and those that do not. So we can set d := q_1 \ldots q_k p_1 \ldots p_r, where q_1, \ldots, q_k are divisors of N; p_1, \ldots, p_r do not divide N; k, r \geq 0.

Consider the set A_d. By hypothesis, it’s the set of the multiples of d in the family A, that is, the set of all integers n \leq N such that d \mid n(N - n). In the form of a congruence, the last relation can be written as n(N - n) \equiv 0\ \textrm{ (mod }d\textrm{)}. Since d = q_1 \ldots q_k p_1 \ldots p_r, this congruence is equivalent to the system of congruences:

\begin{cases} n(N - n) \equiv 0 \textrm{ (mod }q_1\textrm{)} \\ n(N - n) \equiv 0 \textrm{ (mod }\ldots\textrm{)} \\ n(N - n) \equiv 0\ \textrm{(mod }q_k\textrm{)} \\ n(N - n) \equiv 0 \textrm{ (mod }p_1\textrm{)} \\ n(N - n) \equiv 0 \textrm{ (mod }\ldots\textrm{)} \\ n(N - n) \equiv 0\ \textrm{(mod }p_r\textrm{)}\end{cases} \tag{a}

As for the first k congruences, for each q_i \in \{q_1, \ldots, q_k\}, since q_i is prime, we have that n(N - n) \equiv 0 \textrm{ (mod }q_i\textrm{)} if and only if n \equiv 0 \textrm{ (mod }q_1\textrm{)} or (N - n) \equiv 0 \textrm{ (mod }q_i\textrm{)}. We can observe however that these two congruences are equivalent. In fact, since q_i \mid N, the second congruence is equivalent to - n \equiv 0 \textrm{ (mod }q_i\textrm{)} which in turn is equivalent to n \equiv 0 \textrm{ (mod }q_i\textrm{)}, which corresponds to the first congruence. So we can conclude that:

n(N - n) \equiv 0 \textrm{ (mod }q_i\textrm{)} \Leftrightarrow n \equiv 0 \textrm{ (mod }q_i\textrm{)}

As for the last r congruences, for each p_j \in \{p_1, \ldots, p_r\}, since it’s prime, we have that n(N - n) \equiv 0 \textrm{ (mod }p_j\textrm{)} if and only if n \equiv 0 \textrm{ (mod }p_j\textrm{)} or (N - n) \equiv 0 \textrm{ (mod }p_j\textrm{)}; this time the two congruences obtained are not equivalent, because from the second one we can obtain n - N \equiv 0 \textrm{ (mod }p_j\textrm{)} which in turn is equivalent to n \equiv N \textrm{ (mod }p_j\textrm{)}, which is not equivalent to the first congruence because by hypothesis N \not \equiv 0 \textrm{ (mod }p_j\textrm{)}. So in this case we have two distinct solutions modulo p_j:

n(N - n) \equiv 0 \textrm{ (mod }p_j\textrm{)} \Leftrightarrow n \equiv 0 \textrm{ (mod }p_j\textrm{)} \textrm{or} n \equiv N \textrm{ (mod }p_j\textrm{)}

Substituting into (a), we’ll have:

\begin{cases} n \equiv 0 \textrm{ (mod }q_1\textrm{)} \\ n \equiv 0 \textrm{ (mod }\ldots\textrm{)} \\ n \equiv 0\ \textrm{(mod }q_k\textrm{)} \\ n \equiv 0 \textrm{ or } N \textrm{ (mod }p_1\textrm{)} \\ n \equiv 0 \textrm{ or } N \textrm{ (mod }\ldots\textrm{)} \\ n \equiv 0 \textrm{ or } N\ \textrm{(mod }p_r\textrm{)}\end{cases}

Depending on whether we choose 0 or N in each of the last r congruences, we’ll obtain a system of congruences of the type:

\begin{cases} n \equiv 0 \textrm{ (mod }q_1\textrm{)} \\ n \equiv 0 \textrm{ (mod }\ldots\textrm{)} \\ n \equiv 0\ \textrm{(mod }q_k\textrm{)} \\ n \equiv a_1 \textrm{ (mod }p_1\textrm{)} \\ n \equiv \ldots \textrm{ (mod }\ldots\textrm{)} \\ n \equiv a_r\ \textrm{(mod }p_r\textrm{)}\end{cases} \tag{b}

where a_1, \ldots, a_r \in \{0, N\}. The solutions of system (a) therefore will be given by the union of the solutions of each system (b), as a_1, \ldots, a_r \in \{0, N\} vary. Since there are two possible choices for each a_i \in \set{a_1, \ldots, a_r}, the systems of type (b) are in total 2^r. Each of them, by the Chinese remainder theorem, identifies a unique solution modulo d (being d = q_1 \ldots q_k p_1 \ldots p_r). We can therefore conclude that the system (a) admits 2^r solutions modulo d, which we can indicate, using the equivalence class notation, as [\alpha_1], \ldots, [\alpha_{2^r}], with 0 \leq \alpha_1, \ldots, \alpha_{2^r} \lt d. In other words, we can say that d \mid n(N - n) for all integers n that, when divided by d, have a remainder belonging to the set \set{\alpha_1, \ldots, \alpha_{2^r}}. So we can calculate |A_d| as follows:

\begin{aligned} |A_d| & = \\ |\set{a \in A \textrm{\ such that\ } d \mid a}| &= \\ |\set{n \lt N \textrm{\ such that\ } d \mid n(N-n)}| &= \\ |\set{n \lt N \textrm{\ such that\ } n \equiv \alpha_1 \textrm{or} \ldots \textrm{or} \alpha_{2^r} \textrm{ (mod } d\textrm{)}}| &= \\ \left| \bigcup_{i=1}^{2^r} \set{n \leq N \textrm{\ such that\ } n \equiv \alpha_i \textrm{ (mod }d\textrm{)}} \right| &= \\ \sum_{i = 1}^{2^r} |\set{n \leq N \textrm{\ such that\ } n \equiv \alpha_i \textrm{ (mod }d\textrm{)}}| \end{aligned} \tag{c}

where in the last step we observed that the sets in the union are all disjoint, because the \alpha_is represent distinct remainder classes.
The set \set{n \leq N \textrm{\ such that\ } n \equiv \alpha_i \textrm{ (mod }d\textrm{)}} contains all the integers between 1 and N that are congruent to \alpha_i modulo d. To calculate its cardinality, we can divide N by d, obtaining N = \left\lfloor \frac{N}{d} \right\rfloor d + h, where we have indicated with \left\lfloor \frac{N}{d} \right\rfloor the integer part of the division and with h the remainder. We can say that certainly, whatever \alpha_i is, only one of the integers between 1 and d will be congruent to it modulo d; the same can be said for the integers between d + 1 and 2d, between 2d + 1 and 3d, etc., up to the integers between \left(\left\lfloor \frac{N}{d} \right\rfloor - 1\right) d + 1 and \left\lfloor \frac{N}{d} \right\rfloor d. So there are exactly \left\lfloor \frac{N}{d} \right\rfloor integers congruent to \alpha_i between 1 and \left\lfloor \frac{N}{d} \right\rfloor d. But N = \left\lfloor \frac{N}{d} \right\rfloor d + h, so we still have to analyze the integers between \left\lfloor \frac{N}{d} \right\rfloor d + 1 and \left\lfloor \frac{N}{d} \right\rfloor d + h. We cannot say exactly how many of these integers are congruent to \alpha_i, but we can say that there can be at most only one, because, by the same principle as before, there is exactly one between \left\lfloor \frac{N}{d} \right\rfloor d + 1 and \left\lfloor \frac{N}{d} \right\rfloor d + d \gt \left\lfloor \frac{N}{d} \right\rfloor d + h. So the maximum number of integers between 1 and N that are congruent to \alpha_i modulo d is \left\lfloor \frac{N}{d} \right\rfloor + 1. Hence:

\begin{aligned} (c) & \leq \\\sum_{i = 1}^{2^r} \left(\left\lfloor \frac{N}{d} \right\rfloor + 1 \right) & \leq \\\sum_{i = 1}^{2^r} \left(\frac{N}{d} + 2 \right) &= \\\sum_{i = 1}^{2^r} \left(\frac{N}{d} + O(1) \right) &= \\ N \frac{2^r} {d} + 2^r O(1) &= \\ N \frac{2^r}{d} + O(2^r) \end{aligned} \tag{d}

where in the last step we applied the Corollary 1 of Property A.8 (note that 2^r must be treated as a non-constant function, since r depends on N).
But \frac{2^r}{d} is exactly the value of f(d), in fact:

\begin{aligned} f(d) &= \\ f(q_1 \ldots q_k p_1 \ldots p_r) &= \\ f(q_1) \cdot \ldots \cdot f(q_k) \cdot f(p_1) \cdot \ldots \cdot f(p_r) &= \\\frac{1}{q_1} \cdot \ldots \cdot \frac{1}{q_k} \cdot \frac{2}{p_1} \cdot \ldots \cdot \frac{2}{p_r} & = \\\frac{2^r}{q_1 \ldots q_k p_1 \ldots p_r} & = \\ \frac{2^r}{d} \tag{e} \end{aligned}

In fact, as we have already observed, the f used in the Goldbach sieve has been defined precisely in such a way as to estimate with the greatest possible precision the cardinalities of the sets A_d.

From formulas (c), (d) and (e) we can conclude that:

|A_d| \leq N f(d) + O(2^r)

Using this inequality we can calculate r(d), concluding the proof:

\begin{aligned} r(d) &= \\ |A_d| - |A| f(d) &= \\ |A_d| - N f(d) & \leq \\ N f(d) + O(2^r) - N f(d) & =\\ O(2^r) &= \\ O(2^{\omega(d)}) \end{aligned}

where in the last step we observed that r \leq r + k = \omega(d).

Applying this last Lemma and Property A.6, we’ll have that:

\sum_{\substack{d \lt z^2 \\ d \mid P(z)}} 3^{\omega(d)} |r(d)| \ll \sum_{\substack{d \lt z^2 \\ d \mid P(z)}} 3^{\omega(d)} 2^{\omega(d)} = \sum_{\substack{d \lt z^2 \\ d \mid P(z)}} 6^{\omega(d)} \leq \sum_{d \lt z^2} 6^{\omega(d)} \tag{6}

Applying the properties of logarithms, we can rewrite the expression 6^{\omega(d)} changing the base from 6 to 2, as follows:

6^{\omega(d)} = \left(2^{\log_2 6}\right)^{\omega(d)} = 2^{\left(\log_2 6\right) \omega(d)} = \left(2^{\omega(d)}\right)^{\log_2 6} \tag{7}

Now we have to remember that \omega(d) is the number of distinct prime factors of d, so the factorization of d will be of the type p_1^{i_1} \cdot \ldots \cdot p_{\omega(d)}^{i_{\omega(d)}}, with p_1, \ldots, p_{\omega(d)} distinct and i_1, \ldots, i_{\omega(d)} \gt 0. Then, since all prime numbers are greater than or equal to 2:

2^{\omega(d)} = \underbrace{2 \cdot \ldots \cdot 2}_{\omega(d) \textrm{times}} \leq p_1 \cdot \ldots \cdot p_{\omega(d)} \leq p_1^{i_1} \cdot \ldots \cdot p_{\omega(d)}^{i_{\omega(d)}} = d

So, for every d \lt z^2:

(7) \leq d^{\log_2 6} \lt z^{2 \log_2 6} \tag{8}

From formulas (6), (7) and (8) we can conclude that:

\sum_{\substack{d \lt z^2 \\ d \mid P(z)}} 3^{\omega(d)} |r(d)| \ll \sum_{d \lt z^2} z^{2 \log_2 6} \lt z^2 z^{2 \log_2 6} = z^{2 + 2 \log_2 6}

where the inequality is because the sum \sum_{d \lt z^2} z^{2 \log_2 6} repeats the same term z^{2 \log_2 6} as many times as there are positive integers less than z^2, so exactly z^2 - 1 times, that is, less than z^2 times.
Substituting in (5) and applying Lemma C.1 we obtain:

S(A, \mathbb{P}, z) \ll \prod_{p \mid N} \left(1 + \frac{1}{p}\right) \frac{N}{\log^2 z} + z^{2 + 2 \log_2 6}

Now let’s substitute into (3):

\mathfrak{R}(N) \ll 2z + \prod_{p \mid N} \left(1 + \frac{1}{p}\right) \frac{N}{\log^2 z} + z^{2 + 2 \log_2 6} \tag{9}

Now that remains to do is to find a value of z that makes the first and third terms of an asymptotic order lower than the second; this way the first and third terms of (9) can be neglected in the asymptotic bound, obtaining (1).

For simplicity of calculation, we’ll look for the value of z among the powers of N with rational exponent, so we set z := N^{\frac{a}{b}}, with \frac{a}{b} \in \mathbb{Q}. Substituting into (9), we’ll have:

\mathfrak{R}(N) \ll 2 N^{\frac{a}{b}} + \prod_{p \mid N} \left(1 + \frac{1}{p}\right) \frac{N}{\left(\frac{a}{b}\right)^2 \log^2 N} + N^{\frac {a}{b} \left(2 + 2 \log_2 6\right)} \tag{9'}

Our strategy will now be to choose \frac{a}{b} such that, for some real number \alpha \lt 1, both of the following conditions hold:

\begin{cases} 2 N^{\frac{a}{b}} \ll N^{\alpha} \\ N^{\frac{a}{b} \left(2 + 2 \log_2 6\right)} \ll N^{\alpha} \end{cases} \tag{10}

With a few calculations you can verify that two possible values are \frac{a}{b} := \frac{1}{8} and \alpha := 0.9.

How can we find the values \frac{a}{b} := \frac{1}{8} and \alpha := 0.9?

Starting from the second relation, we can observe that 2 + 2 \log_2 6 = 7.169\ldots, so for example multiplying this number by \frac{1}{8} we obtain a number less than 1; in particular \frac{1}{8} \left(2 + 2 \log_2 6\right) \lt 0.9. So we can set \frac{a}{b} := \frac{1}{8} and \alpha := 0.9, obtaining that \frac{a}{b} \left(2 + 2 \log_2 6\right) \lt \alpha and therefore N^{\frac{a}{b} \left(2 + 2 \log_2 6\right)} \ll N^{\alpha}.
Finally, the values found for \frac{a}{b} and \alpha also satisfy the first relation; in fact, since \frac{a}{b} \lt \alpha, we have that N^{\frac{a}{b}} \ll N^{\alpha} and therefore, by Corollary 2 of Property A.8, 2 N^{\frac{a}{b}} \ll N^{\alpha}.

Substituting the values found in (9′), remembering that they satisfy (10), we’ll have that:

\mathfrak{R}(N) \ll N^{0,9} + \prod_{p \mid N} \left(1 + \frac{1}{p}\right) \frac{N}{\left(\frac{1}{8}\right)^2 \log^2 N} + N^{0,9} \tag{11}

But, as it’s known from analysis, since 0.9 \lt 1, we have N^{0.9} \ll \frac{N}{\left(\frac{1}{8}\right)^2 \log^2 N}, and in turn \frac{N}{\left(\frac{1}{8}\right)^2 \log^2 N} \ll \prod_{p \mid N} \left(1 + \frac{1}{p}\right) \frac{N}{\left(\frac{1}{8}\right)^2 \log^2 N}, because the factor \prod_{p \mid N} \left(1 + \frac{1}{p}\right) is greater than 1 for every N. So the dominant term in (11) is the central one, and we can conclude that:

\mathfrak{R}(N) \ll \prod_{p \mid N} \left(1 + \frac{1}{p}\right) \frac{N}{\left(\frac{1}{8}\right)^2 \log^2 N}

Finally, by the Corollary of Property A.8A, the constant \left(\frac{1}{8}\right)^2 does not modify the asymptotic order, hence we obtain (1); the proof is thus concluded.

Leave a Reply

Your email address will not be published. Required fields are marked *