ON THE REPRESENTABILITY OF AN EVEN NUMBER AS THE SUM OF TWO PRIME NUMBERS

V. I. LEKONTSEV

(Presented by the scientific seminar of the Faculty of Automation and Telemechanics)

1. Let \(\varphi_2(l,N)\) denote the number of pairs of numbers \(n\) and \(n+l\), simultaneously relatively prime to \(N\), the first of which does not exceed \(N\). Obviously, \(\varphi_2(l,1)=1\). It is easy to prove the following properties of the function:

The function \(\varphi_2\) is multiplicative.

For \(p\) prime,

\[ \varphi_2(l,p^\alpha)= \begin{cases} p^{\alpha-1}(p-2), & \text{if } (l,p)=1,\\ p^{\alpha-1}(p-1), & \text{if } (l,p)=p. \end{cases} \]

Thus,

\[ \varphi_2(l,N)=N \prod_{\substack{p\mid N\\ p\mid l}} \left(1-\frac{1}{p}\right) \prod_{\substack{p\mid N\\ p\nmid l}} \left(1-\frac{2}{p}\right). \]

2. Let \(\varphi_3(l_1,l_2,N)\) denote the number of triples of numbers \(n, n+l_1, n+l_2\), simultaneously relatively prime to \(N\), the first of which does not exceed \(N\). The function \(\varphi_3\) is multiplicative and

\[ \varphi_3(l_1,l_2,p^\alpha)= \begin{cases} p^{\alpha-1}(p-3), & \text{if } (l_1,p)=1,\ (l_2,p)=1,\\ p^{\alpha-1}(p-2), & \text{if one of the } l \text{ is relatively prime to } p,\\ p^{\alpha-1}(p-1), & \text{if } (l_1,p)=p \text{ and } (l_2,p)=p, \end{cases} \]

so that

\[ \varphi_3(l_1,l_2,N)= N \prod_{\substack{p\mid l_1\\ p\mid l_2}} \left(1-\frac{1}{p}\right) \prod_{\substack{p\mid l_1\\ p\nmid l_2}} \left(1-\frac{2}{p}\right) \prod_{\substack{p\nmid l_1\\ p\nmid l_2}} \left(1-\frac{3}{p}\right). \qquad (p,N). \]

3. For the function \(\varphi_m(l_1,\ldots,l_{m-1},N)\), expressing the number of \(m\)-tuples
\(n,\ldots,n+l_{m+1}\), relatively prime to \(N\), the first of which does not exceed \(N\), analogous properties hold.

From item 1 it follows that the number of pairs of numbers \(n\) and \(n'\) \((n'-n=l)\), relatively prime to \(p_1,\ldots,p_k\) and not exceeding \(Q=p_1\cdots p_k\), is equal to

\[ E_2(l,k,Q)= \prod_{p\mid l}(p-1) \prod_{p\nmid l}(p-2) \qquad (p;Q), \tag{1} \]

whence follows an approximate formula for the number of pairs of prime numbers in \([1,n]\), also obtained in the works [1], [2],

\[ \pi_2(l,n)\approx \frac{n}{Q} \prod_{\substack{p\mid l\\ p\mid Q}}(p-1) \prod_{\substack{p\nmid l\\ p\mid Q}}(p-2) \sim c\,\frac{n}{\ln^2 n}, \]

where \(C\) is a certain constant. From (1) one may also suppose that

\[ \frac{\pi_2(l_1,n)}{\pi_2(l_2,n)}\to \frac{E_2(l_1,Q)}{E_2(l_2,Q)} \qquad (n\to\infty). \]

Thus,

\[ \frac{\pi_2(6,n)}{\pi_2(2,n)}\to 2,\qquad \frac{\pi_2(10,n)}{\pi_2(2,n)}\to \frac{4}{3},\qquad \frac{\pi_2(2^i,n)}{\pi_2(2,n)}\to 1. \]

The following table gives an idea of this hypothesis.

Lemma 1. The number of pairs of numbers relatively prime to \(p_1,\ldots,p_k\) and not exceeding \(n+l\) has the lower estimate

\[ E_2(l,n)\ge \left[ \left[ \left[ n\frac{p_1-1}{p_1} \right] \frac{p_2-2}{p_2} \right] \cdots \frac{p_k-2}{p_k} \right] \ge \frac{n}{2p_k}. \]

Proof. To prove this inequality it is necessary to show the validity of the following assertion: after crossing out, from the total number \(n\) of numbers, the numbers divisible by \(p_1\), among each \(p_2\) numbers of the sequence obtained as a result of the first “sieving,” not more than one number is divisible by \(p_2\); as a result of the “sieving” of the numbers divisible by \(p_2\), we obtain a sequence in which, for each \(p_3\) numbers, there is not more than one number divisible by \(p_3\), and so on; after \(k-1\) steps we obtain a sequence of numbers in which, for each \(p_k\) numbers beginning with 1, not more than one is divisible by \(p_k\). This can be shown, first, by the fact that among the first \(Q=p_1\cdots p_k\) numbers the number of numbers relatively prime to \(p_1,\ldots,p_k\) is equal to \((p_1-1)(p_2-1)\cdots(p_k-1)\) (Euler). We obtain this same value by the indicated method of counting, that is, by gradual “sieving” from the remaining numbers of those divisible by the next prime number. Indeed, after the first step—the “sieving” of the numbers divisible by \(p_1\)—we obtain the number of numbers relatively prime to \(p_1\), which is equal to

\[ Q_1 := \left[ Q\frac{p_1-1}{p_1} \right] =(p_1-1)p_2\cdots p_k; \]

next, from the remaining numbers, those relatively prime to \(p_2\) are equal to the quantity

\[ Q_2=(p_1-1)(p_2-1)p_3\cdots p_k = \left[ \left[ Q\frac{p_1-1}{p_1} \right] \frac{p_2-1}{p_2} \right], \]

and this is possible only because, out of each \(p_2\) numbers remaining after the first “sieving,” not more than one number is divisible by \(p_2\). At the \(i\)-th step of the “sieving” we obtain the quantity

\[ Q_i=(p_1-1)\cdots(p_i-1)p_{i+1}\cdots p_k \]

—the number of numbers relatively prime to \(p_1,\ldots,p_i\). From the remaining numbers the number of numbers relatively prime to \(p_{i+1}\) is equal to the quantity

\[ (p_1-1)\cdots(p_i-1)(p_{i+1}-1)p_{i+2}\cdots p_k = \left[ Q_i\frac{p_{i+1}-1}{p_{i+1}} \right]. \]

This again is possible only because for each \(p_{i+1}\) of the remaining numbers there is at most one number divisible by \(p_{i+1}\). But since for each \(p_i\) numbers there is at most one number that is a multiple of \(p_i\), we can apply this property for arbitrary \(n\); moreover, the last group of numbers, if it is incomplete, is omitted when the sign \([\,]\) is used, whereby we only strengthen the inequality. We supplement this argument by induction on \(k\). Let us form the sequence obtained after \(i-1\) steps of “sieving,” consisting of \(\nu\) complete groups of numbers, \(p_i\) in each; an incomplete group, if there is one, we discard:

\[ \begin{array}{c} \left|\,\overline{\phantom{1,p_i,p_{i+1},\ldots,a_1,a_2,\ldots,p_i^2,\ldots,a_3,a_4,\ldots,p_i,p_{i+1},\ldots}}\,\right| \left|\,\overline{\phantom{1,p_i,p_{i+1},\ldots,a_1,a_2,\ldots,p_i^2,\ldots,a_3,a_4,\ldots,p_i,p_{i+1},\ldots}}\,\right| \left|\,\overline{\phantom{1,p_i,p_{i+1},\ldots,a_1,a_2,\ldots,p_i^2,\ldots,a_3,a_4,\ldots,p_i,p_{i+1},\ldots}}\,\right| \\ 1,\ p_i,\ p_{i+1},\ldots,\ a_1,\ a_2,\ldots,\ p_i^2,\ldots,\ a_3,\ a_4,\ldots,\ p_i,\ p_{i+1},\ldots \end{array} \]

Suppose that among each \(p_i\) numbers of this sequence one is divisible by \(p_i\), among each \(p_{i+1}\) one is divisible by \(p_{i+1}\), and so on. We “sieve out” the numbers that are multiples of \(p_i\), after which \(\nu p_i-\nu\) numbers remain in the sequence. Initially, among the \(\nu p_i\) numbers, the number of multiples of \(p_{i+1}\) was

\[ \left[\frac{\nu p_i}{p_{i+1}}\right], \]

but in sieving out the numbers that are multiples of \(p_i\), the numbers

\[ p_i p_{i+1},\qquad p_i p_{i+1}^{2},\qquad p_i p_{i+1}p_{i+2},\ldots,\le n, \]

also dropped out; the number of such numbers is not less than the number \(f\) of terms of a geometric progression with first term \(p_{i+1}\) and ratio \(p_k\). Then, out of the share of \(\nu p_i-\nu\) numbers, the number of multiples of \(p_{i+1}\) remaining will be no more than

\[ \left[\frac{\nu p_i}{p_{i+1}}\right]-f . \]

It is now not difficult to show that for each \(p_{i+1}\) of the remaining numbers there is at most one number divisible by \(p_{i+1}\). Thus our assertion that at the \(i\)-th step of “sieving” the share of each \(p_i\) numbers contains at most one number that is a multiple of \(p_i\) is proved.

The lemma follows from this assertion when one takes into account the fact that, for \((l,p)=1\), from \(p_i\) numbers two numbers, \(n'\) and \(n'+r\), are “sieved out,” where

\[ r \equiv l \pmod p,\qquad r<p . \]

This method of the sieve differs somewhat from those previously used, for example in [1], [2] and others, in that, unlike the “sieving” of numbers that are multiples of successive primes out of the total number \(n\), here the “sieving” takes place at each step from the remaining numbers. But upon closer examination one obtains the same picture: the “sieving” of numbers that are multiples of primes.

Theorem 1. For \(n\ge 6\), between \(n\) and \(2n\) there exists at least one pair of twin primes \(p'\), \(p''\) \((p''-p'=2)\).

Proof. There is a \(\kappa\) such that \(p_\kappa\le n<p_{\kappa+1}\). By Lemma 1, the number of pairs of numbers relatively prime to \(p_1,\ldots,p_\kappa\) in \([1,2n]\) is not less than

\[ \frac{n}{p_\kappa}>1. \]

But among the first numbers there is no required pair: \((p_\kappa\le n<p_{\kappa+1})\). Therefore a pair of numbers (possibly more than one), relatively prime to \(p_1,\ldots,p_\kappa\), lies between \(n\) and \(2n\). But they are less than \(p_{\kappa+1}^2\), and therefore both numbers of the pair will be prime.

Theorem 2. An even number is representable as the difference of two primes, and the number of such representations is infinite.

Proof. Whatever the even number \(l\) may be, there exist such \(p_\kappa\) and \(n\) (for fixed \(l\) there will be infinitely many such \(p_\kappa\) and \(n\)) that the inequalities

\[ n+l<p_{\kappa+1}^{2},\qquad n>4p_\kappa \]

are satisfied.

For \(n \ge 4p_\kappa\) we have \(E_2(l,\kappa,n) > 2\) (greater than 1 is not enough for us, since such a pair may be the numbers 1 and \(1+l\)); consequently, between \(p_\kappa\) and \(n\) there exists the first number of at least one pair of primes \(p'\) and \(p''\) such that \(p''-p'=l\).

Lemma 2. The numbers relatively prime to \(p_1,\ldots,p_\kappa\) are arranged symmetrically with respect to the number \(p_2\cdots p_\kappa\) in the interval \([1,p_1\cdots p_\kappa]\), and this symmetry is repeated in the subsequent intervals of the same length.

Theorem 3. An even number is representable as the sum of two prime numbers, and the number of such representations is not less than

\[ \left[\left[N\frac{p_2-2}{p_2}\right]\cdots\frac{p_\kappa-2}{p_\kappa}\right]. \]

Proof. By Lemma 2, the number of solutions of the equation \(P_1+P_2=2N\) in prime numbers is equal to the number of pairs of numbers \(n\) and \(n+p_1\cdots p_\kappa-2N\) that are simultaneously relatively prime to \(p_1,\ldots,p_\kappa\), where \(p_\kappa \le \sqrt{2N-1}<p_{\kappa+1}\). Indeed, if \(n\) and \(n+p_1\cdots p_\kappa-2N\) are relatively prime to \(p_1,\ldots,p_\kappa\), then \(n\) and \(2N-n\) are also relatively prime to \(p_1,\ldots,p_\kappa\) and, consequently, \((n<p_{\kappa+1}^2,\ 2N-n<p_{\kappa+1}^2)\) will be prime. By Lemma 1 the number of such pairs of numbers is estimated by the indicated expression.

From item 2 it follows that the number of triples of numbers \(n, n+l_1, n+l_2\), simultaneously relatively prime to \(p_1,\ldots,p_\kappa\) and not exceeding \(p_1\cdots p_\kappa+l\), is equal to

\[ E_3(l_1,l_2,\kappa,Q)= \prod_{\substack{p\nmid l_1\\ p\nmid l_2}}(p-1) \prod_{\substack{p\mid l_1\\ p>l_2}}(p-2) \prod_{\substack{p>l_1\\ p>l_2}}(p-3) \qquad (p\mid Q), \]

and, consequently, we have an approximate formula for the number of triples of prime numbers of the indicated kind in \([1,n]\)

\[ \pi_3(l_1,l_2,n)\simeq \frac{n}{Q} \prod_{\substack{p\nmid l_1\\ p\nmid l_2}}(p-1) \prod_{\substack{p\mid l_1\\ p>l_2}}(p-2) \prod_{\substack{p>l_1\\ p>l_2}}(p-3) \simeq c\frac{n}{\ln^3 n}, \]

where \(c\) is some constant and \(p_\kappa \le n < p_{\kappa+1}^2\). From item 3 it follows that the number of quadruples of numbers, for example, of the form \(n, n+2, n+6, n+8\), simultaneously relatively prime to \(p_1,\ldots,p_\kappa\), and not exceeding \(p_1\cdots p_\kappa\), is equal to \((p_1-1)(p_2-2)(p_3-4)\cdots(p_\kappa-4)\); therefore one may take the number of quadruples of prime numbers of the indicated kind from \([1,n]\) approximately to be the quantity

\[ \frac{n}{p_1\cdots p_\kappa}(p_4-4)\cdots(p_\kappa-4)\simeq c\frac{n}{\ln^4 n}, \qquad n<p_{\kappa+1}^2. \]

Supplement to the proof of Lemma 1

We apply the sieve principle to the sequence \(A_1\) of natural numbers not exceeding \(x\),

\[ A_1\quad 1,2,3,4,\ldots,n^{(1)}, \qquad n^{(1)}\le x. \]

At the first step the numbers divisible by \(p_1\) are sifted out, that is, the numbers equal to the first terms of the sequence \(A_1\), multiplied by \(p_1\), and not exceeding \(x\). At the same time, a \(\frac{1}{p_1}\) part of the numbers divisible by \(p_2,\ldots,p_\kappa\) is also sifted out. As a result we obtain the sequence

\[ A_2\quad 1,3,5,7,9,\ldots,n^{(2)}, \qquad n^{(2)}\le x, \]

containing at least \(Q_1=\left[x\dfrac{p_1-1}{p_1}\right]\) terms of the form \(2k+1\leq x\). At the second step the terms of the sequence \(A_2\) that are multiples of \(p_2\), not exceeding \(x\) and equal to its first terms multiplied by \(p_2\), will be sifted out. For each \(p_i\) \((i=2,3,\ldots)\) of the terms of the sequence \(A_2\) there is no more than one term divisible by \(p_i\). Indeed, the terms divisible by \(p_i\) are obtained successively from the first terms of \(A_2\) by multiplying them by \(p_i\), so that if \(n\) is the total number of terms of \(A_2\), and \(n^*\) is the number of its terms divisible by \(p_i\), then from the inequalities

\[ [x]-1\leq 2n^*+1\leq [x],\qquad n\geq \frac{[x]-2}{2} \]

\[ (2n^*+1)p_i\leq [x],\qquad n^*\leq \frac{[x]-p_i}{2p_i} \]

we conclude that \(n^*\leq \dfrac{n}{p_i}\).

As a result of sifting the numbers of the sequence \(A_2\) divisible by \(p_2=3\), we obtain the sequence

\[ A_3\quad 1,5,7,\ldots,25,\ldots,n^{(3)},\qquad n^{(3)}\leq x, \]

containing at least \(Q_2=\left[Q_1\dfrac{p_2-1}{p_2}\right]\) terms, which have the form \(mp_1p_2+b\), where \((b,p_1\cdot p_2)=1,\ b<p_1\cdot p_2\), that is, \(b=1,5\). We shall sift out the numbers divisible by \(p_3\), equal to the first terms of \(A_3\) multiplied by \(p_3\), and not exceeding \(x\). In exactly the same way one can show that for each \(p_i\) \((i\geq 3)\) of the numbers of the sequence \(A_3\) there is no more than one number divisible by \(p_i\).

Suppose that, as a result of sifting the numbers divisible by \(p_1,\ldots,p_{i-1}\), we obtain the sequence

\[ A_i\quad 1,p_i,p_{i+1},\ldots,p_i^2,\ldots,p_i,p_{i+1},\ldots,n^{(i)},\qquad n^{(i)}\leq x, \]

in which for each \(p_j\) \((j\geq i)\) of the numbers there is no more than one number divisible by \(p_j\). We shall show that, as a result of sifting the numbers divisible by \(p_i\), we obtain a sequence \(A_{i+1}\), in which for each \(p_j\) \((j\geq i+1)\) of the numbers there is no more than one number divisible by \(p_j\). The numbers of the sequence \(A_i\) subject to sifting, that is, those divisible by \(p_i\), are formed from its first terms not exceeding \(\left[\dfrac{x}{p_i}\right]\), by multiplying them by \(p_i\). When the numbers divisible by \(p_i\) are sifted from the sequence \(A_i\), containing \(\nu\) groups of \(p_i\) numbers in each, there will also be sifted numbers divisible by \(p_{i+1},p_{i+2},\ldots\). The \(\nu\) sifted numbers are formed from the \(\nu\) first numbers of the sequence \(A_i\); therefore among the \(\nu\) sifted numbers divisible by \(p_{i+1}\) there will be either

\[ \left[\frac{\nu}{p_{i+1}}\right], \quad \text{or} \quad \left[\frac{\nu}{p_{i+1}}\right]+1, \]

and equal to

\[ \left[\frac{\nu}{p_{i+1}}\right] \]

there will be when \(p_{i+1}\nmid \nu\), and equal to

\[ \left[\frac{\nu}{p_{i+1}}\right]+1 \]

when \(\nu=c\cdot p_{i+1}+r,\ 1\leq r\leq p_{i+1}-1\), and among the \(r\) numbers there will be one number divisible by \(p_{i+1}\).

In both cases:

\[ \left[\frac{\nu p_i}{p_{i+1}}\right] - \left[\frac{\nu}{p_{i+1}}\right] < \frac{\nu p_i-\nu}{p_{i+1}} \qquad \text{when } p_{i+1}\nmid \nu, \]

\[ \left[\frac{\nu p_i}{p_{i+1}}\right] - \left[\frac{\nu}{p_{i+1}}\right] -1 < \frac{\nu p_i-\nu}{p_{i+1}} \qquad \text{when } \nu=c p_{i+1}+r. \]

Hence we conclude that for every \(p_{i+1}\) numbers of the sequence \(A_{i+1}\) there is at most one number divisible by \(p_{i+1}\). In the same way one can show that among any \(p_j\) \((j \geq i+1)\) numbers of \(A_{i+1}\), at most one is divisible by \(p_j\).

References

1. A. O. Gelfond, Yu. V. Linnik. Elementary Methods in Analytic Number Theory. Moscow, 1962.

2. A. I. Vinogradov. Application of \(\zeta(s)\) to the Sieve of Eratosthenes. Mat. Sb. 41, 1957.