{'fraction_non_alphanumeric': 0.06971818810511757, 'fraction_numerical': 0.03081777316735823, 'mean_word_length': 3.5608121427163413, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A variant of the Bombieri-Vinogradov theorem with explicit constants and applications

We give an effective version with explicit constants of a mean value theorem of Vaughan related to the values of \psi(y, \chi), the twisted summatory function associated to the von Mangoldt function \Lambda and a Dirichlet character \chi. As a consequence of this result we prove an effective variant of the Bombieri-Vinogradov theorem with explicit constants. This effective variant has the potential to provide explicit results in many problems. We give examples of such results in several number theoretical problems related to shifted primes.


INTRODUCTION
For integers a and q ≥ 1, let ψ(x; q, a) = n≤x n≡a mod q Λ(n), where Λ(n) is the von Mangoldt function. If q = 1, ψ(x; 1, a) = ψ(x) := n≤x Λ(n). The prime number theorem in arithmetic progressions is the assertion that , as x → ∞, where φ(q) is the Euler function. The Bombieri-Vinogradov theorem is an estimate for the error terms in the prime number theorem for arithmetic progressions averaged over all moduli q up to almost x 1/2 . The version given in 1965 by Bombieri [1] states that if A is a given positive number and Q ≤ x 1/2 (log x) −B where B = 3A + 23, then q≤Q max 2≤y≤x max a (a,q)=1 ψ(y, q, a) − y φ(q) Over the years the value of B has been improved. For instance, Dress, Iwaniec, and Tenenbaum [5] proved B = A + 5/2 is valid. The implied constant in the Bombieri-Vinogradov theorem is not effective. This is ultimately due to the need to allow for the possible existence of exceptional characters associated to those q in the sum having small prime factors.
The Bombieri-Vinogradov theorem has been used to prove a number of interesting results. One such result is the following estimate on the number of primes whose shifts have large prime factors. For the statement, we introduce the notation P (n) for the greatest prime divisor of an integer n = 0, ±1. Also, throughout the paper p always denotes a prime number. Theorem 1.1. There is a θ 0 > 1/2 such that for all non-zero a ∈ Z and all θ ≤ θ 0 there are positive constants X 0 (a, θ) and δ(θ) for which p≤x P (p+a)>x θ 1 > δ(θ) x log x whenever x ≥ X 0 (a, θ). This was first proved by Goldfeld [8] with θ 0 = 0.583 . . .. The best version to date was proved by Baker and Harman [2], who obtained θ 0 = 0.677. The proofs of Goldfeld and of Baker and Harman give no way of calculating X 0 (a, θ) as they rely on the Bombieri-Vinogradov theorem and other ineffective results. In [10], Harman showed how to use an effective variant of the Bombieri-Vinogradov theorem (in which the moduli q are restricted to the primes) to prove Theorem 1.1 with θ 0 = 0.6105 . . . and effectively computable δ(θ) and X 0 (a, θ). While Harman asserted that calculating X 0 (a, θ) is feasible, he did not provide an explicit value for X 0 (a, θ) for any values of a and θ.
Inspired by Harman's work, in this paper we provide an effective variant of the Bombieri-Vinogradov theorem with explicit constants where q varies over integers. We then apply our variant to several number theoretical problems involving shifted primes to obtain new effective results. One of our results (Corollary 2.7 (ii)) provides numerical values for the constants δ(θ) and X 0 (a, θ) in Harman's theorem (see [10,Theorem 2]) for a = −1 and θ = 0.6.
We now describe our effective variant in detail.
In 1977, following the ideas of I. M. Vinogradov, Vaughan [21] described a method for estimating sums of the form where f (n) is either an exponential function of the form e 2πiαn or a Dirichlet character χ(n) modulo q. He then applied this method to give an elementary proof of the Bombieri-Vinogradov theorem [22]. The main step in Vaughan's proof is a mean value theorem for ψ(y, χ) = n≤y Λ(n)χ(n), the twisted summatory function associated to the von Mangoldt function Λ and a Dirichlet character χ.
Our first theorem provides a version of Vaughan's mean value inequality with explicit constants. Q is any positive real number, and * χ (q) denotes a sum over all primitive characters χ (mod q). Mean value theorems of this type have many applications (see [19] and [20] for some examples). One of the most important consequences of (1.1) is a straightforward proof of the Bombieri-Vinogradov theorem (see [4,Chapter 28] or [22]). In addition to Theorem 1.2, the proof uses the Siegel-Walfisz theorem, which states that Here A > 0 is a fixed real number, c is an absolute positive constant, and δ(χ) is 1 or 0 according to whether the Dirichlet character χ is principal or non-principal. The implied constant in the Bombieri-Vinogradov theorem is ineffective because the implied constant in the Siegel-Walfisz theorem is ineffective. In the proof of the Bombieri-Vinogradov theorem, one uses the Siegel-Walfisz theorem to deal with moduli q ≤ Q having small prime divisors and uses Theorem 1.2 to deal with the sum over the remaining q ≤ Q. The following theorem is simply what one gets for the sum over these remaining q; we refer to this theorem as an effective variant of the Bombieri-Vinogradov theorem. (1.2) Here e = exp(1) and Effective variants of the Bombieri-Vinogradov theorem have been known for a while. However, as far as we know, prior to our work there has not been a version with explicit numerical constants. Timofeev [18,Theorem 2] proved an effective variant (without constants explicitly given) when the modulus q varies over integers with ℓ(q) > exp ((log x) 1/4 ). Our effective variant is stronger and produces upper bounds in the form x/(log x) A for ℓ(q) > exp (( 9 2 + A) log log x). Another effective variant without explicit constants is given by Lenstra and Pomerance [11,Lemma 11.2] in their work on Gaussian periods and a polynomial time primality testing algorithm.
Next we state the version of Theorem 1.3 that we will employ in the applications. As usual, let π(x) = p≤x 1 and π(x; q, a) = p≤x p≡a mod q 1.
Harman [10,Theorem 3] gives a version of Corollary 1.4 for prime moduli p ≤ Q without explicit constants. In many applications one needs the version given in Corollary 1.4. Indeed, for Theorem 2.1 below we have to work with composite modulus q. Remark 1.5. The right-hand side of the inequality (1.1) in Theorem 1.2 has the form where c 0 and α are positive real numbers. Our goal was to generate an explicit expression for f (x, Q) which is not far from optimal and at the same time can be neatly written. Following the methods of this paper, there are several ways that one can replace f (x, Q) with a more optimal function. As an example, the coefficients of f (x, Q) in (1.1) have been rounded up to be integers. The proof of Theorem 1.2 can be modified to establish this inequality with slightly smaller non-integral coefficients. As a more significant example, an application of an improved version of the Polya-Vinogradov inequality (see [16,Theorem 1]) in (6.9) and (6.12) will reduce the values of the coefficients of f (x, Q). Our method also permits further reduction of the exponent α. From [5] we know that where µ is the Möbius function. Employing an explicit version of this inequality (whenever one becomes available) instead of (6.14), will result in α = 5/2. We note that by the main result of [5] the upper bound x in (1.4) is optimal. Thus it will not be possible to improve α beyond 5/2 by sharpening the inequality (1.4). Similar comments are applicable to the inequalities in Theorem 1.3 and Corollary 1.4.
Here we describe the structure of this paper. Section 2 presents several applications of our variant of the Bombieri-Vinogradov theorem (Corollary 1.4) in problems related to shifted primes. In Section 3 we collect some known number theoretic inequalities with explicit constants that will be used in our proofs. Sections 4 and 5 are devoted to proofs of the results stated in Section 2. Section 6 is dedicated to a detailed proof of our main mean value theorem (Theorem 1.2). The proofs of Theorem 1.3 and Corollary 1.4 are given in Sections 7 and 8, respectively.
Notation. The symbols p, p 1 , p 2 , ℓ, ℓ 1 , and ℓ 2 always denote primes. The symbols n and q always denote integers. The least prime divisor of q is denoted ℓ(q). The number of distinct prime divisors of n is denoted ω(n). The Möbius function and the von Mangoldt function are defined, respectively, by and Λ(n) = log p if n = p k for some prime p and integer k ≥ 1, 0 otherwise. The prime counting function and the standard Chebyshev functions are where a, q are integers with q ≥ 1. The twisted summatory function associated to the von Mangoldt function Λ and a Dirichlet character χ is defined by The greatest prime divisor of an integer n = 0, ±1 is denoted P (n). The least prime congruent to a modulo p is denoted L(p, a). The multiplicative order of a nonzero integer b modulo p is denoted e b (p). The constants c 0 and A 0 are defined in Theorem 1.2. The constants c 1 and E 0 are defined in Theorem 1.3. The constant c 2 is defined in Corollary 1.4.

Acknowledgements.
We thank Adam Felix, Andrew Granville, Glyn Harman, Kumar Murty, Carl Pomerance, Olivier Ramaré, and Igor Shparlinski for their correspondence and their comments on an earlier draft of this paper. We also thank the referee for many helpful comments and suggestions.

SUMMARY OF APPLICATIONS
In this section we describe some applications of Corollary 1.4. Moreover, we calculate explicitly the constants involved. As far as we know, this has not been done before.
The following two theorems are explicit Turán-type inequalities for ω(p − 1), the number of prime divisors of p − 1.
for all x ≥ C(b). If a = log log C(b), some of the possible values for a and b are given in the following As a consequence of Theorem 2.2, we get an explicit version of a theorem of Erdös [7] on the normal order of ω(p − 1).
where some of the possible values for a and b are given in the table in Theorem 2.2.
The proofs of the above theorems follow the general strategy outlined in [3, Section 3.3]. However, modifications are required since Corollary 1.4 (our effective variant of the Bombieri-Vinogradov theorem) produces non-trivial results only for moduli bigger than a power of log x. A key idea is the application of the Brun-Titchmarsh inequality (Lemma 3.1(f)) when Corollary 1.4 is not useful. Generating the table in Theorem 2.2 requires some care in choosing values for the parameters U and V that arise in the proof of the theorem. See Section 4 for details.
Our second application is an effective version of a theorem of Goldfeld [8, Theorem 1]. Let p 1 and p 2 denote primes.

Theorem 2.4.
There is an effective positive constant C 0 (ǫ) depending only on ǫ > 0 such that By an argument similar to the proof of the lower bound in Theorem 2.4, we can establish the following.
. Then there is an effectively computable constant C 0 (θ, ǫ) such that For the proofs of the previous two theorems, a key idea is that we apply the Brun-Titchmarsh inequality (Lemma 3.1(f)) for the small moduli where our effective variant of the Bombieri-Vinogradov theorem (Corollary 1.4) gives only trivial estimates. Harman used this idea in [10].
Theorem 2.5 has applications to problems related to the least prime in an arithmetic progression, the greatest prime divisor of a shifted prime, and the order of an integer modulo a prime. Let L(p, a) be the least prime congruent to a modulo p, let P (n) be the greatest prime divisor of the integer n, and let e b (p) be the multiplicative order of the positive integer b modulo p. Corollary 2.6. Let n ≥ 1 be an integer, 1 2 ≤ θ < 1 − 1 2 exp − 1 4 = 0.6105 . . ., and δ(θ) = 1 2 + 2 log(2 − 2θ). Let C 0 (θ, ǫ) be the constant given in Theorem 2.5.
Then for every Then .
The ineffective version of part (i) is due to Motohashi [14]. Part (ii) is essentially Harman's effective estimate on the density of shifted primes with large prime divisors, which we discussed in the introduction. The ineffective version of part (iii) is due to Goldfeld [8].
In the next corollary we give numerical values for all the constants in Corollary 2.6 when θ = 0.6 and n = 100. For part (i) we chose ǫ = 4, and for parts (ii) and (iii) we chose ǫ = 2.
Corollary 2.7 gives numerical values for the constants in Corollary 2.6 for specific values of the parameters. The constants C 1 (θ, ǫ), C 2 (θ, ǫ, n), C 3 (θ, ǫ), and C 4 (θ, ǫ, n) are clearly easy to calculate for fixed values of the parameters. Calculating C 0 (θ, ǫ) can be done by carefully following the proofs of Theorem 2.4 and Theorem 2.5 and incorporating the modification described in Remark 5.2. For the calculation to be practical, some care must be taken in choosing values for the parameters U and V arising in these proofs. For part (i), where we chose θ = 0.6, n = 100, and ǫ = 4, we set U = (log x) 7 and V = x 1/2 /(log x) 7 . For parts (ii) and (iii), where we chose θ = 0.6, n = 100, and ǫ = 2, we set U = (log x) 6.75 and V = x 1/2 /(log x) 6.75 . Remarks 2.8. (i) Results similar those in this section can be obtained for ω(p + a), p 1 + a, L(p, a), P (p + a), and e b (p), for any fixed a, b ∈ Z \ {0}. For simplicity in our presentation we described the results for a = −1 and b = 2.
(ii) An adaptation of Theorem 2.1 to the case of ω(p + 2) will give an explicit estimate for the number of twin primes p ≤ x, however sieve methods may provide superior explicit results.
(iii) An effective version of the full Bombieri-Vinogradov theorem would imply the inequality of Theorem 2.1 with the right-hand side (9 + ǫ) log log x. The extra factor log log log x in our current theorem is a consequence of the fact that our variant is non-trivial only for Q 1 bigger than a power of log x. Since we deal with moduli ≤ Q 1 with the Brun-Titchmarsh inequality, the extra factor log log log x results. This illustrates a limitation of the method.
(iv) The constants appearing in the inequality of Theorem 2.4 are closely related to the exponent α of log x in Corollary 1.4. More precisely our proof establishes 2α + ǫ (resp. 4α + ǫ) for the coefficient of x log log x/ log x in the upper bound (resp. lower bound) given in Theorem 2.4. So an improvement of the exponent α will improve the constants in Theorem 2.4. An improvement of the exponent α will in fact improve the constants in all the theorems and corollaries in this section.

EXPLICIT INEQUALITIES
In the next lemma we will collect several known explicit inequalities (mostly from [17] and [6]) used in the proofs. Note that γ = 0.57721 . . . is Euler's constant and ϑ(x) = p≤x log p. , Proof. (a) This is a consequence of the inequality (see [6,Theorem 2]). The lower inequality holds for x > 1.
(b) We can deduce this from the inequality By applying (3.11) to (I) and then employing (3.1) in the resulting expression we see that and M is defined in Lemma 3.1(a). We observe that the dominant term in (4.3) is Next we note that To estimate (III) observe that if p ≤ x and V T +1 ≥ x, then p − 1 can have at most ⌊T ⌋ distinct prime factors larger than V . Thus Therefore, by (4.1), (4.2), (4.4), and (4.5), we have Next we write ℓ≤x π(x; ℓ, 1) in the right-hand side of the above inequality as three sums over ℓ ≤ U , U < ℓ ≤ V , and ℓ > V respectively. We apply (3.11) in the first sum and treat the third sum as we treated (III). Then after some rearrangement we arrive at To generate the table in Theorem 2.2, we set B = 7 and, for each value of b, computed to a few decimal places the smallest a for which the right-hand side of (4.6) is majorized by the right-hand side of (4.7) for all x ≥ exp(exp(a)).
for all x ≥ C(b). This statement is stronger than both Theorem 2.1 and 2.2. However it is not practical to explicitly compute a value of C(b) for small b.

PROOFS OF THEOREM 2.4, THEOREM 2.5, AND COROLLARY 2.6
We will need the following lemma in the proof of Theorem 2.4 and Theorem 2.5 below.
Proof. We first apply the Brun-Titchmarsh inequality (3.11) to the sum on the left of inequality (5.1) and then split the resulting sum into two to get
Proof of Theorem 2.4. We start by observing that Next we decompose the first sum on the right as We will first bound this quantity from below. By (3.6) we have Observe that E 2 = k≥2 p≤x 1/k (log p)π(x; p k , 1).
Using Lemma 3.1(f) and the trivial bound π(x; q, 1) ≤ x/q, we find We next apply (3.12), (3.13), and the fact that − 0.02303 . . . , in (5.10) to obtain an upper bound for E 2 . Applications of the resulting upper bound for E 2 , the upper bound (5.9) for E 1 , and the lower bound (3.6) for ϑ(x) in (5.8) yield Next we consider the second sum on the right of (5.7), i.e.
Let U = (log x) 6.5 and V = x 1/2 /(log x) 6.5 . Write We need to find upper bounds on the three sums on the right.
By the Brun-Titchmarsh inequality (3.11), we have Observe that (5.13) together with (3.2) imply that p≤U (log p)π(x, p, 1) < 13 x log log x log x provided x ≥ C 1 , where C 1 is an explicitly computable constant. For the sum with V < p ≤ x 1/2 , we use Lemma 5.1 with θ = 1 2 to get for V ≥ 563. So by employing the inequality log(1 + y) ≤ y − y 2 2 + y 3 3 , valid for y > −1, we can find an explicit constant C 2 such that For the sum over U < p ≤ V in (5.12), we will use our effective variant of the Bombieri-Vinogradov theorem. Applying (1.3) yields

By (3.2) we have
for V > U ≥ 2974. Let ǫ > 0 be given. Then by (5.14), (5.15), the upper bound for π(x) given in (3.10), and the triangle inequality we can obtain U <p≤V is explicitly computable. Now that we have the lower bound (5.11) and the upper bounds on the three sums on the right of (5.12), we can put everything together to conclude can be determined explicitly. The upper bound in the theorem is proved by a similar argument. Let U = (log x) 6.5 and V = x 1/2 /(log x) 6.5 . By (5.8) and (3.6) we have We estimate the first sum in the last line using (1.3). To estimate the second sum, we combine the lower bound (3.9) on π(x) with the observation that (3.2) implies for V > U ≥ 2974. Let ǫ > 0 be given. By combining (5.14), (5.16), (5.17), (5.18), (3.9), and (1.3) we find that Proof of Theorem 2.5. Write where U = (log x) 6.5 and V = x 1/2 /(log x) 6.5 . Then imitate the proof of the lower bound in Theorem 2.4.
The result follows by applying Theorem 2.5 and then dividing by log x.
(iii) Since e 2 (p) | p − 1, we have By Theorem 2.5 there is an effective constant C 0 (θ, ǫ) such that for all x ≥ C 0 (θ, ǫ). Next we observe that In the first sum on the right of (5.20) we apply the Brun-Titchmarsh inequality (3.11) and (3.2) to deduce Now we deal with the second sum on the right of (5.20). Let

PROOF OF THEOREM 1.2
Fix arbitrary real numbers Q > 0 and x ≥ 4. In this section, we shall establish (1.1), which is the key inequality used in the proof of Theorem 1.3. We closely follow Vaughan's proof as described in [4,Chapter 28], and in each step will make the constants explicit.
The main tool in the proof of (1.1) is the large sieve inequality Here the a m 's are arbitrary complex numbers. Note that (6.1) is given in [12, p. 561, last line].
We will use the following consequence of (6.1). Lemma 6.1. Suppose that a m 0 , · · · , a M and b n 0 , · · · , b N are complex numbers. Then Proof. Since the product mn will be a positive integer not exceeding M N , we may assume that y is of the form y = k + 1 2 , where k ∈ {1, . . . , M N }. By contour integration one can show that if α ≥ 0, β > 0, and T > 0, then where O * means that the implied constants are less than or equal to 1. By setting α = log(mn), β = log y, and summing against a m b n χ(mn), we find Therefore the modulus of the left-hand side of (6.3) is and so the left-hand side of (6.1) is Applying first Cauchy's inequality and then (6.1), the sum under the integral in (6.4) is seen to be Thus, by applying Cauchy's inequality in the second sum in (6.4), the right-hand side of (6.4) is The integral in the above inequality is 2 log(eT log(2M N )). So, since Q 2 ≤ (M ′ + Q 2 ) 1 2 (N ′ + Q 2 ) 1 2 , to complete the proof it will be enough to show that for some choice of T . A bit of calculus reveals that the left-hand side of (6.5) is minimized by choosing T = (M N ) 3/2 / log(4/3). With this choice of T the left-hand side is decreasing in M N , and so (since M N ≥ 1) its maximum value is seen to be c 3 .
We are almost at the heart of the proof of (1.1), but first we reduce to the case 2 ≤ Q ≤ x 1/2 . If Q < 1 the sum on the left-hand side of (1.1) is empty and there is nothing to prove. If 1 ≤ Q < 2 then only the q = 1 term appears and we have which is better than (1.1). Note the last inequality is the Chebyshev estimate (see [17,Theorem 12]) where A 0 = max(ψ(x)/x) = ψ(113)/113. In the case Q > x 1/2 , (1.1) follows from (6.1) with M = m 0 = n 0 = 1, N = ⌊x⌋, a m = 1, b n = Λ(n), and the estimate From now on we assume 2 ≤ Q ≤ x 1/2 . We will need the following decomposition of Λ(n) due to Vaughan (see [21] or [4, p. 139]). Let U and V be arbitrary real numbers ≥ 1. We have Λ(n) = λ 1 (n) + λ 2 (n) + λ 3 (n) + λ 4 (n), Assume y ≤ x, q ≤ Q, and χ is a character mod q. We use the above decomposition to write We take U and V to be functions of x and Q to be specified later. We will treat each S i separately. It immediately follows that by the Chebyshev estimate (6.6). Then Next we write We have In the last expression we dropped the condition d ≤ y/w because the sum over h is empty when d > y/w. Now we see that If q = 1 then the only character χ mod q is the trivial character, and so w≤h≤y/d 1 = y(log y) d≤V 1 d < y(log y)(log eV ) < x(log xV ) 2 .
If q > 1 and χ is a primitive character mod q, the Polya-Vinogradov inequality a≤n≤b χ(n) < q These two estimates for |S 2 | imply Consider the last expression. Since the innermost sum is empty when t > U V , we are free to introduce the condition t ≤ U V on the sum over t. Hence Now we split the summation over small and large t by writing t≤U r≤y/t χ(r) .
Note the similarity to the inequality (6.8) which we obtained for S 2 . Indeed, by proceeding as we did with S 2 , we obtain We deal now with S ′′ 3 by breaking the sum for U < t ≤ U V into sums over dyadic sub-intervals. We have r≤y/t md=t m≤U d≤V Λ(m)µ(d)χ(tr).
Since M < t and y ≤ x, we have r ≤ x/M in the sum over r. Then where we have put a t = md=t m≤U d≤V Λ(m)µ(d) and b r = 1.
where T ′ and R ′ are the number of terms in the sums over t and r, respectively. Clearly, T ′ ≤ M , R ′ ≤ x/M , and log(2 min(U V, 2M )x/M ) ≤ log(4x). By (6.11), |a t | ≤ log t. Putting these facts together we see that Using that (6.13) Next we treat S 4 . We have We employ the same technique we used with S ′′ 3 . Writing S 4 as a dyadic sum we have By the triangle inequality Then applying (6.1) gives q≤Q q φ(q) * Since a primitive character χ * (mod q * ) induces characters to moduli which are multiples of q * and since ψ ′ (y, χ * ) = 0 whenever χ is principal, we have q≤Q ℓ(q)>Q 1 1 φ(q) .
It then follows by the triangle inequality that the left hand side of (1.3) is The first term is estimated by (1.2). So to establish (1.3) we just note that, for x ≥ 4, 2x 1 2 q≤Q ℓ(q)>Q 1

+ φ(q)
is less than the expression on the right of (1.2) without c 1 present.