Multiplicative functions in short arithmetic progressions
Oleksiy Klurman Alexander P. Mangerel Joni Teräväinen

Multiplicative functions in short arithmetic progressions]Multiplicative functions in short arithmetic progressions

School of Mathematics,
University of Bristol, Woodland Road, Bristol,  UK
lklurman@gmail.com



Department of Mathematical Sciences, Durham University, Upper Mountjoy Campus, Stockton Road, Durham, UK
smangerel@gmail.com




Department of Mathematics and Statistics, University of Turku, Turku, Finland
joni.p.teravainen@gmail.com






We study for bounded multiplicative functions f sums of the form

    ∑_n≤ x
    n≡ a qf(n),

establishing that their variance over residue classes a  q is small as soon as q=o(x), for almost all moduli q, with a nearly power-saving exceptional set of q. This improves and generalizes  previous results of Hooley on Barban–Davenport–Halberstam-type theorems for such f, and moreover our exceptional set is essentially optimal unless one is able to make progress on certain well-known conjectures. We are nevertheless able to prove stronger bounds for the number of the exceptional moduli q in the cases where q is restricted to be either smooth or prime, and conditionally on GRH we show that our variance estimate is valid for every q.

These results are special cases of a ”hybrid result” that we establish that works for sums of f over almost all short intervals and arithmetic progressions simultaneously, thus generalizing the Matomäki–Radziwiłł theorem on multiplicative functions in short intervals.

We also consider the maximal deviation of f over all residue classes a q in the square root range q≤ x^1/2-ε, and show that it is small for ”smooth-supported” f, again apart from a nearly power-saving set of exceptional q, thus providing a smaller exceptional set than what follows from Bombieri–Vinogradov-type theorems. 

As an application of our methods, we consider Linnik-type problems for products of exactly three primes, and in particular prove a ternary approximation to a conjecture of Erdős on representing every element of the multiplicative group ℤ_p^× as the product of two primes less than p.


[
    Joni Teräväinen
    December 30, 2023
=====================





To the memory of Christopher Hooley










§ MAIN THEOREMS



Let U{z∈ℂ:  |z|≤ 1} denote the unit disc of the complex plane, and let f NU be a 1-bounded multiplicative function. In this paper we study sums of the form

    ∑_n≤ x
    n≡ aqf(n)

with (a,q)=1 and with the modulus 1 ≤ q ≤ x being very large as a function of x. We call such arithmetic progressions short, since the number of terms is ∼ x/q, which is assumed to grow slowly with x. 

Our main results concern the deviation of multiplicative functions fℕ→𝕌 in residue classes in the square-root range q≤ x^1/2-ε, as well as their variance in residue classes in the full range q=o(x). Here by deviation we mean

    max_a∈ℤ_q^×|∑_n≤ x
    n≡ a qf(n)-χ_1(a)/ϕ(q)∑_n≤ xf(n)χ̅_̅1̅(n)|,

where ℤ_q^× is the set of invertible residue classes q, and by variance we mean 

    _a q|∑_n≤ x
    n≡ a qf(n)-χ_1(a)/ϕ(q)∑_n≤ xf(n)χ̅_̅1̅(n)|^2,

where ∑_a(q)^* denotes a sum over reduced residue classes q. 
The character χ_1 q here is chosen[If there is more than one minimizing character, we may choose any of these.] such that the map χ↦inf_|t| ≤log xD_q(f,χ(n) n^it;x) is minimized, where, given f,gNU we define

    𝔻_q(f,g;x)(∑_p≤ x
    p∤ q1-Re(f(p)g(p))/p)^1/2

to be the pretentious distance function of Granville and Soundararajan (see, e.g., <cit.>). As a consequence of a well-known theorem of Halász, it can be shown that any other character χ≠χ_1 q has small correlation sums ∑_n ≤ x f(n)χ̅(n), and so informally we may think of χ_1 as a character that “correlates the most” with f among all the characters q.


Comparing the sum (<ref>) to the main term χ_1(a)/φ(q)·∑_n≤ xf(n)χ_1(n) is natural, since if, in fact, f “correlates" significantly with some Dirichlet character χ, then we expect

    ∑_n≤ x
    n≡ a qf(n)≈χ(a)/ϕ(q)∑_n≤ xf(n)χ̅(n).


In this paper, we develop a systematic approach to estimating weighted character sums ∑_n≤ xf(n)χ̅(̅n̅)̅n^it for the wide range of parameters t,q=O(x), and deduce numerous estimates for (<ref>) and (<ref>). 




 §.§ Results for prime moduli


For many problems on well-distribution in arithmetic progressions one can obtain stronger results for prime moduli than for general moduli (see, for example, <cit.>, <cit.>); the same is true in our setting.   

Our first main result concerns the variance (<ref>) in the range where x/q tends to infinity very slowly. It is motivated by the groundbreaking work of Matomäki and Radziwiłł <cit.>, which produces a comparable result for multiplicative functions in short intervals. 

All the constants in this paper implied by the ≪ notation will be absolute unless otherwise indicated.

 Let 1≤ Q≤ x/10 and (log(x/Q))^-1/200≤ε≤ 1. Then there exists a set [1,x^ε^200]∩ℤ⊂𝒬_x,ε⊂ [1,x]∩ℤ with |[1,Q] ∖𝒬_x,ε|≪ (log x)^ε^-200 such that the following holds.

Let p∈𝒬_x,ε∩ [1,Q] be a prime. Let fNU be a multiplicative function. Let χ_1 be a character p minimizing the distance inf_|t|≤log x𝔻_p(f,χ(n)n^it;x). Then  we have

    _a p|∑_n ≤ x 
     n ≡ a p f(n) - χ_1(a)/ϕ(p)∑_n ≤ x f(n)χ̅_̅1̅(n)|^2 ≪εx^2/p.

Moreover, assuming GRH, (<ref>) holds for all p∈ [1,Q].





Applying Halász's theorem (Lemma <ref>), we see that in Corollary <ref> (as well as in our other results to follow) the main term (χ_1(a)/ϕ(q))·∑_n≤ xf(n)χ_1(n) can be deleted from the variance, unless 

    inf_|t|≤log x𝔻_q(f,χ_1(n)n^it; x)^2≤ 2log1/ε.
 
In particular, if GRH holds, then by the pretentious triangle inequality we see that (<ref>) can only hold if χ_1 is induced by χ', where χ' is the primitive character of conductor ≤ Q that minimizes inf_|t|≤log x𝔻(f,χ(n)n^it;x) (without assuming GRH, the situation is somewhat more complicated; cf. Subsection <ref>). 


We refer to Section <ref> for a discussion of the strength of this theorem as well as that of our other theorems. 





 §.§ Smooth-supported functions in the square root range



We are also able to obtain a result on the deviation (<ref>) of multiplicative functions in all arithmetic progressions n≡ a q in the “middle range” q≤ x^1/2-o(1). This supports the well-known analogy between results for all moduli in the middle range q≤ x^1/2-o(1) and almost all moduli in the large range x^1-ε≤ q≤ x^1-o(1) (an example of this analogy is provided by the theorems of Bombieri–Vinogradov and Barban–Davenport–Halberstam).

Transferring results from the almost all case to the case of all arithmetic progressions requires a bilinear structure in our sums. In our case, we introduce this bilinear structure by considering multiplicative functions f supported on smooth (otherwise known as friable) numbers.

 Let η>0 be fixed. Let x≥ 10, (log x)^-1/200≤ε≤ 1, and Q≤ x^1/2-100η. There is a set [1,x^ε^200]∩ℤ⊂𝒬_x,ε⊂ [1,x]∩ℤ with |[1,Q]∖𝒬_x,ε|≪ Qx^-ε^200 such that the following holds.

Let q∈𝒬_x,ε∩ [1,Q]. Let f NU be a multiplicative function supported on x^η-smooth numbers. Let χ_1 be a character q minimizing the distance inf_|t|≤log x𝔻_q(f,χ(n)n^it;x). Then we have

    max_a∈ℤ_q^×|∑_n≤ x
    n≡ a qf(n)-χ_1(a)/ϕ(q)∑_n≤ xf(n)χ_1(n)|≪εx/q.

Furthermore, if Q^' is any subset of [1,Q] whose elements are pairwise coprime, then we have the bound |Q^'∖𝒬_x,ε|≪ (log x)^ε^-200. Moreover, assuming GRH, (<ref>) holds for all q∈ [1,Q].






 §.§ Results for smooth moduli


In addition to primality of moduli, we can also leverage their smoothness (see <cit.>, <cit.> for some other level of distribution estimates leveraging the smoothness of moduli). For moduli q that are q^ε'-smooth, we may prove a variant of Corollary <ref> without any exceptional moduli at all, but with the disadvantage that the upper bound for the variance is weaker (and possibly trivial) when q has abnormally many small prime divisors. To this end, we make the following definition.

 We say that an integer q≥ 1 is y-typical if

    |{p≤ z:  p| q}|≤1/100π(z)  for all   z≥ y.



Theorem <ref> below analogizes Corollary <ref> for smooth moduli that are, in addition, (x/Q)^^2-typical numbers.
A simple argument (see Lemma <ref>) shows that all q≤ x are such numbers if Q=o(x/(log x)^1/ε^2), and otherwise the number of q≤ Q that are not (x/Q)^ε^2-typical is bounded by ≪ Qexp(-10^-4(x/Q)^ε^2).



Let 1≤ Q≤ x/10, (log(x/Q))^-1/200≤ε≤ 1, and ε'=exp(-ε^-3). Let q≤ Q be q^ε'-smooth and (x/Q)^ε^2-typical. Let fℕ→𝕌 be a multiplicative function. Let χ_1 q be a character minimizing the distance inf_|t|≤log x𝔻_q(f,χ(n)n^it;x). Then we have 

    _a q|∑_n≤ x
    n≡ a qf(n)-χ_1(a)/φ(q)∑_n≤ xf(n)χ̅_̅1̅(n)|^2≪εϕ(q) (x/q)^2.



We note that the need to restrict to typical moduli arises naturally in our proof and is present also in other works (formulated in slightly different terms), see e.g. <cit.>, <cit.>.  See also Subsection <ref> for a discussion of the necessity of this assumption.   






 §.§ General moduli


We may now state a result for general moduli q that are not required to be prime or smooth. In this case we obtain the desired bound for the variance (<ref>) for all typical moduli outside a nearly power-saving exceptional set. 

 
Let 1≤ Q≤ x/10 and (log(x/Q))^-1/200≤ε≤ 1. Then there exists a set [1,x^ε^200]∩ℤ⊂𝒬_x,ε⊂ [1,x]∩ℤ with |[1,Q]∖𝒬_x,ε|≪ Qx^-ε^200 such that the following holds.

Let q∈𝒬_x,ε∩ [1,Q] be (x/Q)^ε^2-typical. Let fNU be a multiplicative function. Let χ_1 be a character q minimizing the distance inf_|t|≤log x𝔻_q(f,χ(n)n^it;x). Then we have

    _a q|∑_n ≤ x 
     n ≡ a q f(n) - χ_1(a)/ϕ(q)∑_n ≤ x f(n)χ̅_̅1̅(n)|^2 ≪εϕ(q)(x/q)^2.

Moreover, assuming GRH, (<ref>) holds for all (x/Q)^ε^2-typical q∈ [1,Q].





 §.§ Hybrid results


As already mentioned, our results are motivated by the following theorem from <cit.>.

A[Matomäki–Radziwiłł] Let 10≤ h≤ X, and let fℕ→ [-1,1] be multiplicative. Then we have

    ∫_X^2X|∑_x< n≤ x+hf(n)-h/X∑_X≤ n≤ 2Xf(n)|^2 dx ≪((loglog h/log h)^2+(log X)^-1/50)Xh^2.



This was generalized to functions fℕ→𝕌 that are not n^it-pretentious for any |t|≤ X by Matomäki–Radziwiłł–Tao <cit.>. Our next theorem is a hybrid result that allows us to ”interpolate” between Theorem <ref> (in the complex-valued case) and our Theorem <ref> on multiplicative functions in short arithmetic progressions, thus generalizing both results. This theorem applies to sums of the form

    ∑_x< n≤ x+h
    n≡ a qf(n)

over short intervals and arithmetic progressions, with averaging over x∈ [X,2X] and a∈ℤ_q^×, as soon as h/q→∞.




Let X ≥ h ≥ 10 and 1 ≤ Q ≤ h/10. Let (log(h/Q))^-1/200≤ε≤ 1. Then there is a set [1,X^ε^200]∩ℤ⊂Q_X,⊂ [1,X]∩ℤ satisfying |[1,Q] Q_X,| ≪ QX^-^200 such that the following holds.

Let q ∈Q_X,∩ [1,Q] be (h/Q)^ε^2-typical. Let fℕ→𝕌 be multiplicative.  Let χ_1 be a character q minimizing the distance inf_|t| ≤ XD_q(f,χ(n) n^it;X), and for each χ let t_χ∈ [-X,X] be a point that minimizes[If there are several such t_χ, pick any one of them.] D_q(f,χ(n) n^it;X). Then  we have

    ∫_X^2X_a q   |∑_x < n ≤ x + h 
     n ≡ a q f(n) - χ_1(a)/ϕ(q)(∫_x^x+h v^it_χ_1 dv) 1/3X∑_n ≤ 3X f(n)χ̅_1(n) n^-it_χ_1|^2 dx
       ≪ϕ(q)X(h/q)^2.

Moreover, assuming GRH, (<ref>) holds for all (h/Q)^ε^2-typical q∈ [1,Q].


We remark that for h≤ε X, by Taylor approximation we have

    ∫_x^x+hv^it_χ_1  dv=hx^it_χ_1+O(ε h).


Taking Q=1, ε=(log h)^-1/200, and letting h tend to infinity slowly with X, we recover Theorem <ref>  (though with a smaller power of logarithm saving) in a form that applies to any 1-bounded f, whether n^it-pretentious or not (cf. <cit.>). Taking in turn Q=o(h) and h=X, we arrive at a slightly weaker  form of our variance result, Theorem <ref>, where we now need to average over x∈ [X,2X]. 




In the case of real-valued multiplicative functions fN [-1,1], we have a simpler formulation of the result as follows.

Let the notation be as in Theorem <ref>, and assume additionally that f is real-valued. Then for all q∈𝒬_X,ε∩ [1,Q] that are (h/Q)^ε^2-typical we have

    ∫_X^2X_a q|∑_x < n ≤ x+h 
     n ≡ a qf(n) - 
    χ_1(a)/ϕ(q)h/3X∑_n≤ 3X f(n)χ̅_̅1̅(n)|^2  dx ≪εϕ(q)X(h/q)^2.

Moreover, the second sum inside the absolute values can be deleted unless χ_1 q is real. 


We can also specialize Corollary <ref> to f=μ and to the smaller range q≤ x^ε^200 to obtain a clean statement, which has recently been used in <cit.> to obtain applications to ergodic theory. 


Let A≥ 1 be fixed. Let X≥ h≥ 10q≥ 10,  (log(h/q))^-1/200≤ε≤ 1,  q≤ X^ε^200, and let q be (h/q)^ε^2-typical. Then we have

    ∫_X^2X_a q|∑_x < n ≤ x+h 
     n ≡ a qμ(n)|^2  dx≪εφ(q)X(h/q)^2,

except possibly if q is a multiple of a single number q_0≥ (log X)^A depending only on A and X.


The exclusion of the multiples of a single modulus is necessary if Siegel zeros exist, as they bias the distribution of μ in residue classes. 






§ APPLICATIONS


A celebrated theorem of Linnik states that the least prime p≡ a q is ≪ q^L for some absolute constant L and uniformly for a∈ℤ_q^× and q≥ 1. The record value to date is L=5, due to Xylouris <cit.>. For q^δ-smooth moduli (with δ=δ(ε)), a better bound of ≪ q^12/5+ε is available, this being a result of Chang <cit.>. Under GRH, we would have L=2+o(1) in place of L=5, and assuming a conjecture of Cramér-type, L=1+o(1) would be the optimal exponent.
 

We apply the techniques used to prove our main results to make progress on the analogue of Linnik's theorem for E_3 numbers, that is, numbers that are the product of exactly 3 primes. We seek bounds on the quantity 

    ℒ_3(q)max_a∈ℤ_q^×min{n∈ℕ:  n≡ a q:   n∈ E_3}.

One can show that under GRH one has ℒ_3(q)≪ q^2+o(1). The E_3 numbers, just like the primes, are subject to the parity problem, and hence one cannot use sieve methods to tackle the problem of bounding ℒ_3(q) (in contrast, for products of at most two primes ≤ x, it is known that one can find them in every reduced residue class modulo q for q≤ x^1/2+δ for some δ>0 by a result of Heath-Brown <cit.> proved using sieve methods). In relation to this problem, Ramaré and Walker <cit.> obtained the bound ℒ_3(q) ≪ q^16 by constructing products of primes p_1p_2p_3 with each p_j ≤ q^16/3.

We show unconditionally that ℒ_3(q)≪ q^2+o(1) for all smooth moduli and for all but a few prime moduli; moreover, the products p_1p_2p_3 constructed satisfy p_j < q for j = 1,2,3.


Let ε>0, and let ε'>0 be small enough in terms of ε.
 
    
  * For any integer q≥ 1  that is q^ε'-smooth, for any a∈ℤ_q^×, there exists some q-smooth n∈ E_3 such that n≪ q^2+ε and n≡ a q. Consequently, ℒ_3(q)≪ q^2+ε.
    
    
  * Let Q≥ 2. Then for all but ≪_ε 1 primes q∈ [Q^1/2, Q], for any a∈ℤ_q^×, there exists some q-smooth n∈ E_3 such that n≪ q^2+ε and n≡ a q. Consequently, ℒ_3(q)≪ q^2+ε.






This will be proved in Section <ref>. Since all the E_3 numbers we detect are q-smooth, our results are connected to the question of representing every element of the multiplicative group ℤ_q^× by using only a bounded number of small primes. This problem was introduced by Erdős, Odlyzko and Sárközy in <cit.>. In <cit.> it is mentioned that Erdős conjectured that every residue class in ℤ_q^×, with q a large prime, has a representative of the form p_1p_2 with p_1,p_2≤ q primes. As is noted in <cit.>, this remains open, even under GRH. The weaker “Schnirelmann-type” question of representing every residue class in ℤ_q^× as the product of at most k primes in [1,q] was studied by Walker <cit.>, who showed[Both in <cit.> and <cit.> a stronger result was shown, namely that one can restrict to primes in [1,q^1-η] for explicitly given values of η>0. An inspection of the proof of our Corollary <ref> shows that there also we could restrict to primes bounded by q^1-η, with η>0 small enough.] that k=6 suffices for all large primes q, and moreover that k=48 suffices if we consider products of exactly k primes. Shparlinski <cit.> then improved on the former by showing that at most 5 primes suffice for every large integer q. See also the very recent works <cit.>, <cit.> for further results on this problem. From Theorem <ref> we deduce the following.

 There exists an absolute constant C>0 such that the following holds. For all Q≥ 2 and all primes q∈ [Q^1/2,Q], apart from ≤ C exceptions, every element of the multiplicative group ℤ_q^× can be represented as the product of exactly three primes from [1,q].




Finally, we consider an analogue of Linnik's theorem concerning values of the Möbius function. Since the theorems above give ℒ_3(q)≪ q^2+o(1) for smooth q and all but a few primes q (and since the E_3 numbers we detect are typically squarefree), for such q the least number n with μ(n)=-1 and n≡ a q also satisfies n≪ q^2+o(1). Going further, we are able to obtain lower bounds of the correct order of magnitude for the number of n ≤ x with μ(n) = -1 in any residue class a q as soon as x ≥ q^2+, as opposed to just showing their existence.

 Let ε>0 and Q≥ 2. Then, for all but ≪_ε 1 primes q∈ [Q^1/2, Q], we have

    min_a∈ℤ_q^× |{n≤ x:    n≡ a  q,   μ(n)=-1}| ≫_εx/q

for all x≥ q^2+ε. The same holds when the condition μ(n) = -1 is replaced by μ(n) = +1.


 
We lastly remark that unconditionally proving the estimate ℒ_3(q)≪ q^2+o(1) for every q seems challenging, due to connections between this problem and Vinogradov's conjecture (see Subsection <ref>).




§ OPTIMALITY OF THEOREMS AND PREVIOUS WORK




 §.§ Previous results


The study of the deviations (<ref>) and (<ref>) of f in arithmetic progressions can roughly speaking be divided into three different regimes: the small moduli q≤ x^ε, the middle moduli x^ε≤ q≤ x^1-ε, and the large moduli x^1-ε≤ q=o(x), for > 0 small.



  §.§.§ Small moduli


In the regime of small moduli, Linnik's theorem, in its quantitative form <cit.>, gives the expected asymptotic formula for the average of μ (or Λ) over a q, valid for all a∈ℤ_q^× and q≤ x^ε, apart possibly from multiples q of a single number q_0 (a Siegel modulus). A far-reaching generalization of this to arbitrary 1-bounded multiplicative functions f was achieved by Balog, Granville and Soundararajan <cit.>. See also the work <cit.> of Granville, Harper and Soundararajan for related results. One consequence of our Theorem <ref> (noting that the set 𝒬_X,ε there contains [1,X^ε^200]∩ℤ) is a short interval version of the result of <cit.>, albeit with an average over a.



  §.§.§ Middle moduli


The middle regime q=x^θ with ε≤θ≤ 1-ε (and typically with θ near 1/2) is arguably the most well-studied one. Results related to this range include the celebrated Bombieri–Vinogradov theorem, which for f=μ (or f=Λ) can be interpreted as providing cancellation in the deviation (<ref>) for almost all q≤ x^1/2-ε and all a∈ℤ_q^×.  A complete generalization of the Bombieri–Vinogradov theorem to arbitrary 1-bounded multiplicative functions was recently achieved by Granville and Shao <cit.>. 


The work of Granville and Shao in particular implies the following result applicable to almost all moduli: if fNU is multiplicative, then for all but ≤ Q/(log x)^1-1/√(2)-2ε choices of q∈ [Q,2Q]⊂ [1,x^1/2-ε], we have

    max_a∈ℤ_q^×|∑_n≤ x
    n≡ a qf(n)-χ_1(a)/ϕ(q)∑_n≤ xf(n)χ̅_̅1̅(n)|=o(x/q).

In <cit.>, Granville and Shao obtained a saving of an arbitrary power of log x, assuming that f is supported on x^η-smooth numbers and that f satisfies the Siegel–Walfisz condition. 


Our Theorem <ref> improves on (<ref>) in the aspect of the exceptional set, as our result implies that if f is supported on x^η-smooth numbers, then the size of the exceptional set of q≤ x^1/2-ε in (<ref>) can be reduced to an almost power-saving bound, or even to a power of logarithm in the case of prime moduli. In this aspect, our result may also be compared with a recent result of Baker <cit.>, who showed that the estimate (<ref>) holds for f=Λ (with χ_1≡ 1) for all but a power of logarithm number of primes q≤ x^9/40-ε. 

Though the theorems in this paper are not related to such developments, we note in passing that in the literature there are several results, valid in the middle range q≤ x^θ, that go beyond θ=1/2 for general multiplicative functions,  provided that one removes the maximum over the residue classes a q. See the works of Green <cit.>, Granville–Shao <cit.>, Drappeau–Granville–Shao <cit.>, and Fouvry–Radziwiłł <cit.>, among others. 






  §.§.§ Large moduli


In the range x^1-ε≤ q=o(x), one aims for estimates valid for almost all q and for almost all a∈ℤ_q^×; results of this shape arise from upper bounds for the variance (<ref>). The most classical theorem of this type is the Barban–Davenport–Halberstam theorem <cit.>, which states that

    ∑_q≤ x/(log x)^B∑_a∈ℤ_q^×|∑_n≤ x
    n≡ a  qμ(n)|^2≪_A x^2/(log x)^A,

with B=B(A) explicit (and there is an analogue in which μ is replaced with Λ). 

The Barban–Davenport–Halberstam theorem was extensively studied by Hooley in a seminal series of publications titled “On the Barban–Davenport–Halberstam theorem”, spanning 19 papers. In this series, he significantly improved and generalized the Barban–Davenport–Halberstam bound, and among other things produced an asymptotic formula for the left-hand side of (<ref>), and also with μ replaced by any bounded sequence satisfying a Siegel–Walfisz type assumption. Of this series of papers, the ones related to the aims of the present paper are <cit.>, <cit.>, <cit.>, <cit.>, <cit.>. 
In particular, from <cit.> (where Hooley considers the variance summed over all moduli q≤ Q) one extracts the following result (see also the work of Vaughan <cit.> for a related result, proved using the circle method).

B[Hooley] Let ε>0 and A≥ 1 be fixed. Let 1≤ Q≤ x, and let fℕ→𝕌 be an arbitrary function satisfying the Siegel–Walfisz condition. Denote H x/Q. Then, for all 1≤ q≤ Q apart from ≪ Q((log H)/H+(log x)^-A) exceptions we have

    _a q|∑_n≤ x
    n≡ a qf(n)-χ_0(a)/ϕ(q)∑_n≤ xf(n)χ_0(n)|^2≤εφ(q)(x/q)^2,

where, for each q ≤ Q, the character χ_0 is principal modulo q.



By our Theorem <ref>, and the fact that the number of moduli q≤ Q that are not H^ε^2-typical is ≪ Qexp(-(1/1000+o(1))H^ε^2) (see Lemma <ref>), the size of the exceptional set here for multiplicative f reduces to ≪ Qexp(-c_0H^ε^2), for c_0 > 0 constant. We can at the same time remove the Siegel–Walfisz assumption on f. If we restrict ourselves to H^ε^2-typical moduli only, then  Theorem <ref> bounds the exceptional set by ≪ Qx^-ε^200. This essentially power-saving bound was not, according to our knowledge, previously available even for f=μ. 


We now discuss some of the key features of our results when it comes to the strength and optimality.




 §.§ The description and size of the exceptional set


The set ([1,x]∩ℤ)∖𝒬_x,ε of exceptional moduli present in our main theorems turns out to be completely independent of the function f that we consider, a feature that does not arise from applying the Barban–Davenport–Halberstam theorem or Hooley's Theorem <ref>. We have the following explicit[Here, given a Dirichlet character χ we denote by cond(χ) the conductor of χ.] description of 𝒬_x,ε in terms of zeros of L-functions q: 

    𝒬_x,ε{q≤ x: ∏_χ q
    (χ)>x^ε^200 L(s,χ)≠ 0  for  (s)≥ 1-ε^-100(loglog x)/log x,   |(s)|≤ 3x};

see Proposition <ref> and Lemma <ref> for this. Hence, assuming GRH (or even a weaker version of it), 𝒬_x,ε = [1,x]∩ℤ. From the description of 𝒬_x,ε above and zero density estimates, it is not difficult to see that we have a structural description of the exceptional moduli as the set of multiples of a subset ℰ_x⊂ [x^ε^200,x] of integers of size O((log x)^ε^-200). This explains why the bound for the number of exceptional prime moduli in Corollary <ref> is so strong, compared to the case of general moduli.





 §.§ Connection to Vinogradov's conjecture and character sums


 For any fixed ε>0, the number of exceptional moduli in Theorem <ref> is of the form Qx^-^200, saving a power of x that tends to 0 as ε→ 0. We show here that this is essentially the best possible, in the sense that replacing Qx^-^200 by Qx^-η_0 for η_0 > 0 fixed would lead to the proof of some form of Vinogradov's conjecture[Vinogradov's conjecture on the least quadratic nonresidue states that for every η>0 and for any prime q>q_η there is a quadratic nonresidue q in the interval [1,q^η].] (which is known under GRH but not unconditionally).

Indeed, assume that Vinogradov's conjecture is false. Then there exists η>0 and infinitely many x≥ 10 such that for some prime x^η-o(1)≤ q_0≤ x^η we have nq_0 = 1 for all n with the largest prime factor P^+(n) ≤ q_0^η. 

Defining the multiplicative function f_η(n) 1_P^+(n)≤ q_0^η, by the classical asymptotic formula for smooth numbers (and the fact that q_0 is prime), we have

    ∑_n≤ x f_η(n)nq_0   =∑_n≤ x f_η(n)χ_0(n) = (ρ(η^-2)+o(1)) x,

with χ_0 the principal character modulo q_0 and ρ(·) the Dickman function (see Section <ref> for its definition). It follows that, regardless of the choice of χ_1 q_0,

    1/ϕ(q_0)∑_χq_0
    χ≠χ_1|∑_n≤ xf_η(n)χ(n)|^2≫_ηφ(q_0)x^2/q_0^2.

However, by Parseval's identity (i.e., just expanding the square and using orthogonality), (<ref>) equals to the left-hand side of (<ref>) (with f=f_η), and thus q_0∉𝒬_x,ε if ε is small in terms of η. 

Note that if Q=x/log x and r=q_0p with p∈ [log x,Q/q_0] a prime, then the same argument as above (with χ_0(n) and nq_0 replaced by χ_0(n)1_(n,r)=1 and nq_01_(n,r)=1 in (<ref>)) shows that also r∉𝒬_x,ε, meaning that there are ≫ Qx^-η+o(1) exceptional q≤ Q (again with ε small enough in terms of η). Taking η<η_0, this shows that the number of exceptional moduli for (<ref>) is in fact not bounded by ≪ Qx^-η_0. Thus, one cannot generally improve on the exceptional set in Theorem <ref> without settling Vinogradov's conjecture at the same time.

One could also adapt the argument above to show more strongly that improving  the exceptional set for (<ref>) implies cancellation in smooth-supported character sums. Using arguments from <cit.>, it should further be possible to say that this implies bounds for zeros of L-functions near 1 (which is out of reach of current knowledge).

Similar conclusions apply to the size of the exceptional set in our other main theorems.




 §.§ The restriction to typical moduli


We now discuss the importance of working with typical moduli in Theorems <ref> and <ref>. In our proofs, as in the work <cit.>, it is important for us to be able to discard those n≤ x, n≡ a q from the sum (<ref>) that have no prime factors from certain long intervals [P_i,Q_i] (with Q_i≤ h/Q). However, if q is divisible by all (or most) primes in [P_i,Q_i], then the contribution of such integers is not negligible. This would then prevent us from factorizing our character sums in a desirable way, which is crucial to our method.  

While Theorem <ref> may remain valid for all moduli q≤ Q (under GRH, say), there seem to be serious obstacles to proving this. Indeed, Granville and Soundararajan <cit.> proved a very general uncertainty principle for arithmetic sequences, which roughly speaking says that “multiplicatively interesting” sequences cannot be perfectly distributed in all arithmetic progressions. For example, if f(n)=1_(n,r)=1 with r having very many small prime factors in the sense that ∑_p| r, p≤log x(log p)/p≫loglog x, then for large constant C>0 there exists y∈ (x/4,x) and a progression a q with (a,q)=1 and q≤ x/(log x)^C and P^-(q)≫loglog x such that the mean value of f over n≤ y, n≡ a q does not obey the anticipated asymptotic formula. Note that this is not due to “trivial” reasons such as f having sparse support, as it is possible for f, constructed in this fashion, to have f(n) =1 for a positive proportion of n≤ x, e.g., if r=∏_(log x)^1-η≤ p≤log xp.

Similarly, if for example f is the indicator of sums of two squares, then the results of <cit.> imply that f is poorly distributed in some residue classes a q with q≤ x/(log x)^C. 









 §.§ Remarks on improvements


We finally list a few small improvements to our main theorems that could be obtained with only slight modifications to the proofs.




    
  * In Theorem <ref>, we obtain an upper bound for (<ref>) of the form (log(h/Q))^-cϕ(q)(x/q)^2  for small c>0 by choosing ε=(log(h/Q))^-1/500, say. Thus our savings are comparable to those in <cit.>. Due to our reliance on typical factorizations, one cannot hope for larger savings than ((loglog(h/Q))/log(h/Q))^2 in general. However, if one specializes to the case f=μ in our main theorems, one can easily adapt the proof to yield savings of the form ≪ (log(h/Q))^-2+o(1) by applying the Siegel–Walfisz theorem in place of Hálasz-type estimates. We leave the details to the interested reader.
    
    
  * As in the work of Granville and Shao <cit.> on the Bombieri–Vinogradov theorem for multiplicative functions, we could obtain stronger bounds for (<ref>) if we subtracted the contribution of more than one character from the sum of f over an arithmetic progression. Moreover, it follows directly from our proof that if we subtracted the contribution of ≪ (log x)^C(ε) characters, where C(ε)>0 is large, then there would be no exceptional q at all in the theorem. We leave these modifications to the interested reader.
    
  











§ PROOF IDEAS


We shall briefly outline some of the ideas that go into the proofs of our main results. 



  §.§.§ Proof ideas for the variance results

We start by discussing the proof of the hybrid result, Theorem <ref>; the proof of our result on multiplicative functions in short progressions, Theorem <ref>, is similar but slightly easier in some aspects.

As in the groundbreaking work of Matomäki–Radziwiłł <cit.>, we begin by applying a suitable version of Parseval's identity to transfer the problem to estimating an L^2-average of partial sums of f twisted by characters from a family. Of course, since we are working with both intervals and arithmetic progressions, the right family of characters to employ are the twisted characters {χ(n)n^it}_χ q 
 |t|≤ X/h. In this way, we reduce our task to obtaining cancellation in 

    ∑_χ q∫_t∈ T_χ|∑_X≤ n≤ 2Xf(n)χ(n)n^-it|^2  dt,

with T_χ=[-X/h,X/h] if χ≠χ_1 and T_χ_1=[-X/h,X/h]∖ [t_χ_1-ε^-10,t_χ_1+ε^-10], with χ_1 and t_χ_1 as in the theorem (so (χ,t)↦𝔻_q(f,χ(n)n^it;X) for χ q and |t|≤ X is minimized at (χ_1,t_χ_1)); the contribution from the deleted segment in T_χ_1 accounts for our main term.

We make crucial use of the Ramaré identity, thus obtaining a factorization[Due to the restriction to reduced residue classes a q in our theorems, we have desirable factorizations for typical integers only if q is not divisible by an atypically large number of small primes, e.g. by almost all of the primes up to (h/Q)^0.01. This is what results in the need in our main theorems to restrict to typical moduli. This issue of course does not arise in the short interval setting of <cit.>.]  

    ∑_X≤ n ≤ 2X f(n)χ(n)n^-it≈∑_P_j≤ p≤ Q_jf(p)χ(p)p^-it∑_X/p≤ m≤ 2X/pf(m)a_m,P_j,Q_jχ(m)m^-it,

with parameters P_j,Q_j, 1 ≤ j ≤ J, at our disposal, and the approximation being accurate in an L^2-sense (after splitting the p variable into short intervals). Here a_m,P_j,Q_j1/1+ω_[P_j,Q_j](m) is a well-behaved sequence, behaving essentially like the constant 1 for the purposes of our argument. After having obtained this bilinear structure, we split the “spectrum” {χ q}× [-X/h,X/h] into parts depending on which (if any) of the sums ∑_P_j≤ p≤ Q_jf(p)χ(p)p^-it with j≤ J exhibits cancellation. The contributions from different parts of the spectrum are bounded differently by establishing various mean and large value estimates for twisted character sums (see Section <ref>), in analogy with <cit.> for Dirichlet polynomials.

The outcome of all of this is that we can reduce to the case where the longest of our twisted character sums, ∑_P_J≤ p≤ Q_Jf(p)χ(p)p^-it, has (essentially) no cancellation at all. It is this large spectrum case where we significantly deviate from <cit.>; in that work, the large spectrum is not the most difficult case to deal with, thanks to the Vinogradov–Korobov zero-free region for the Riemann zeta-function. In our setting, in turn, we encounter L-functions L(s,χ) with χ having very large conductor, and for these L-functions the known zero-free regions are very poor (the best region being the Landau–Page zero-free region σ>1-c_0/log(q(|t|+1)), valid apart from possible Siegel zeros). At this point, we restrict the set of moduli in question to those q ≤ Q for which the functions L(s,χ) for every χ q (of large conductor) enjoy a suitable zero-free region (see Proposition <ref> and Lemma <ref> for the definition of the region involved). Our bounds for the number of moduli omitted in this fashion come from log-free zero-density estimates for L-functions (Lemma <ref>); in the case of pairwise coprime moduli, as in Corollary <ref>, the bound is much better thanks to there being no effect from a single bad character inducing many others.

Having restricted to such moduli we establish a bound essentially of the form

    sup_χ qsup_|t|≤ X
    χ=χ_1⟹ |t-t_χ_1|≥ε^-10|∑_X≤ n ≤ 2X f(n)χ(n)n^-it|≪εϕ(q)/qX

for the sup norm of the twisted character sums involved, and also prove that the large spectrum set under consideration is extremely small[One could use moment estimates (e.g. Lemma <ref>) to show that the large values set is ≪ (log X)^O_ε(1) in size; however, in our case that would be a fatal loss, since the saving we get in (<ref>) is at best 1/log X and is therefore not enough to compensate this. In <cit.>, a Halász–Montgomery-type estimate for prime-supported Dirichlet polynomials is established to deal with the large spectrum; our Proposition <ref> essentially establishes a hybrid version of this, but in a very different regime.], that is, 

    sup_P∈ [X^ε,X]|{(χ,t)∈{χ q}×T:   |∑_P≤ p≤ 2Pf(p)χ(p)p^-it|≥ε P/log P}|≪ε^-2,

with 𝒯⊂ [-X,X] well-spaced. These two bounds are our two key Propositions <ref> and <ref> in the proof of the hybrid theorem. We need full uniformity in |t|, q≤ X, which makes the proofs somewhat involved: in particular, our proofs rely on some lemmas from the works of Koukoulopoulos <cit.> and  Granville–Harper–Soundararajan <cit.> (as well as a result of Chang <cit.> for Theorem <ref> on smooth moduli).




  §.§.§ Proof ideas for the case of all moduli in the square-root range

The starting point of the proof of Theorem <ref> is the simple Lemma <ref> that allows us to conveniently decompose any x^η-smooth number into a product n=dm with an appropriate choice of d,m∈ [x^1/2-η,x^1/2+η].
However, the decoupling of the d and m variables here is somewhat delicate and requires some smooth number estimates.  After decoupling the variables (and extracting a further small prime factor), we have introduced a trilinear structure with two variables of almost equal length, which (by Cauchy–Schwarz) means that we can employ the techniques from previous sections to bound the mean squares of the product of three character sums involved. 



  §.§.§ Proof ideas for the Linnik-type results

For the proof of our Linnik-type results, Theorems <ref>(i)–(ii), we use similar ideas as for Theorem <ref>, with a couple of additions. Since we only need a positive lower bound for the number of n≡ a  q that are E_3 numbers,  we can require that these n have prime factors from any intervals that we choose. Thanks to this flexibility in the sizes of the prime factors, we can get good bounds for the trilinear sums that arise. A key maneuver here is to count suitable n with the logarithmic weight 1/n, so that we will be able to utilize a modification of the ”Rodosskii bound” from the works of Soundararajan <cit.> and Harper <cit.>, which establishes cancellation in logarithmically averaged character sums over primes assuming only a very narrow zero-free region. For smooth moduli, we have a suitable zero-free region by a result of Chang <cit.>, whereas for prime q we apply the log-free zero-density estimate to obtain a suitable region apart from a few bad moduli.









§ STRUCTURE OF THE PAPER
 We will present the proofs of Theorems <ref> and <ref>  in Subsections <ref> and <ref>, respectively. The necessary lemmas for proving these results are presented in Sections <ref> and <ref>. Section <ref> in turn contains two propositions that are key ingredients in the proofs of the main theorems.  In Section <ref> we prove Theorem <ref> on smooth moduli. Our result on smooth-supported functions in the square-root range is proved in Section <ref>. Section <ref> in turn contains the proofs of the applications to Linnik-type theorems. We remark that Sections <ref>, <ref> and <ref> can be read independently of each other, but they all depend on the work in Section <ref>.






§ NOTATION


We use the usual Vinogradov and Landau asymptotic notation ≪, ≫, ≍, O(·), o(·), with the implied constants being absolute unless otherwise stated. If we write ≪_ε, ≫_ε or O_ε(·), this signifies that the implied constant depends on the parameter ε. 

We write 1_S(n) for the indicator function of a set S. The functions Λ, ϕ and τ_k are the usual von Mangoldt, Euler phi and k-fold divisor functions, and π(x) is the prime-counting function. By P^+(n) and P^-(n) we mean the largest and smallest prime factors of n, respectively. We say that n is y-smooth if P^+(n)≤ y. We write e(x)=e^2π i x for the complex exponential. The symbol ρ (0,∞)→ [0,1] denotes the Dickman function, the unique solution to the delay differential equation ρ(u-1)=-uρ'(u) for u>1, with the initial data ρ(u)=1 for 0<u≤ 1; see <cit.> for further properties of this function.

The symbol p is reserved for primes, whereas j, k,m,n,q are positive integers.

Below we list for the reader's convenience the notation we introduce in later sections.




§ NOMENCLATURE


 

_a q     A sum over the invertible residue classes q


_χq     A sum over the primitive characters q


χ_0     The principal character


χ^∗     The primitive character inducing the character χ


(χ)     The conductor of the character χ


ℤ_q^×     The set of invertible residue classes q


Ω_[P,Q](n), ω_[P,Q](n)     The number of prime factors of n from an interval [P,Q], with and without multiplicities, respectively


Δ(q,Z)     Equation (<ref>)


Ψ_q(X,Y)     Equation (<ref>)


 𝔻_q(f,g;x)     Equation (<ref>) 
 

 𝔻(f,g;y,x)     Equation (<ref>) 
 
 
 F(χ)     Equation (<ref>)

 

L_y(s,f)     Equation (<ref>)


M_q(T)     Equation (<ref>)


N(σ,T,χ)     Equation (<ref>)


𝒬_x,ε,M     Equation (<ref>)


V_t     Equation (<ref>)

 










§ MEAN AND LARGE VALUES ESTIMATES




We begin this section with several standard L^2-bounds for sums twisted both by Dirichlet and Archimedean characters.


In what follows, we will seek to make all of our estimates as sharp as possible as a function of q, in particular obtaining factors of ϕ(q)/q in our estimates wherever possible. While this increases the lengths of some proofs (particularly in Section <ref>), it is critical in order for us to state our main variance estimates with no loss.



 
Let q,M,N≥ 1, and let (a_n)_n be complex numbers. Then

    ∑_χq|∑_M < n ≤ M+N a_nχ(n)|^2 ≪(ϕ(q)+ϕ(q)/qN) ∑_M < n ≤ M+N
     (n,q) = 1 |a_n|^2.



This is <cit.>. 


 
Let T,N, q ≥ 1. Then

    ∑_χ q∫_0^T |∑_n ≤ N a_nχ(n)n^it|^2 dt ≪(ϕ(q)T+ϕ(q)/qN) ∑_n≤ N
     (n,q) = 1 |a_n|^2.




This is a slight sharpening of <cit.> (more precisely, see (6.14) there).


For the proof of Lemma <ref> below, we will also need a discrete version of the large sieve estimate, in which we sum over well-spaced sets. We say that a set 𝒯⊂ℝ is well-spaced if t,u∈𝒯, t≠ u implies |t-u|≥ 1. We give two such results below, one of which is sensitive to sparse families of characters.



Let T,N,q≥ 1, and let T⊂ [-T,T] be a well-spaced set. Then 

    ∑_χ q∑_t ∈T|∑_n ≤ N a_nχ(n)n^it|^2 ≪(ϕ(q)T + ϕ(q)/qN)log(3N)∑_n ≤ N
     (n,q) = 1 |a_n|^2.



This result, which is a slight sharpening of <cit.> (taking δ = 1 there), is proved in a standard way by combining Gallagher's Sobolev-type lemma <cit.> with Lemma <ref>; we leave the details to the reader.



 
Let T, q ≥ 1 and let E⊂{χ q}× [-T,T] be such that if t ≠ u and (χ,t), (χ,u)∈E then |t-u|≥ 1.
Then

    ∑_(χ,t)∈E|∑_n ≤ N a_nχ(n)n^it|^2 ≪(ϕ(q)/qN + |E|(qT)^1/2log(2qT))∑_n ≤ N
     (n,q) = 1|a_n|^2.





This is a slight sharpening (paying attention to coprimality with q) of <cit.> (see especially (8.16), taking δ = 1 and _0 = 0), and is proven in much the same way. We leave the details to the interested reader.


When it comes to estimating the size of the large values set of a short twisted character sum supported on the primes, the following hybrid version of <cit.> will be important.



Let P,T≥ 2. Let T⊂ [-T,T] be well-spaced. Let 

    P_χ(s) ∑_P < p ≤ 2P a_pχ(p)p^-s,
 
where |a_p| ≤ 1 for all P < p ≤ 2P. Then for any α∈ [0,1] we have 

    |{(χ,t) ∈{χ'  q}×T: |P_χ(it)| ≥ P^1-α}|≪ (qT)^2α(P^2α+exp(100log(qT)/log Ploglog (qT))).




Without loss of generality, we may assume that P and T are larger than any given constant. Let N be the number of pairs (χ,t) in question and V P^1-α; then

    N≤  V^-2k∑_χ q∑_t ∈T |P_χ(it)|^2k

for any k≥ 1. We pick k=⌈log(qT)/log P⌉. Expanding out, we see that

    P_χ(s)^k = ∑_P^k < n ≤ (2P)^k b(n) χ(n)n^-s,  where   b(n)=∑_p_1⋯ p_k = n
     p_j∈ [P,2P]  ∀ j a_p_1⋯ a_p_k.

By the discrete large sieve (Lemma <ref>), we have

    ∑_χ q∑_t ∈T |P_χ(it)|^2k   ≪ (ϕ(q)T+(2P)^k)log(3· (2P)^k) ∑_P^k≤ n ≤ (2P)^k |b(n)|^2.


We can then compute the mean square over n as 

    ∑_P^k ≤  n ≤ (2P)^k |b(n)|^2 ≤∑_p_1 ⋯ p_k = q_1 ⋯ q_k
     P≤ p_j,q_j ≤ 2P 1≤ k!(∑_P < p ≤ 2P 1)^k  ≤ k!(2P/log P)^k.

This gives the bound

    ∑_χ q∑_t ∈T|P_χ(it)|^2k   ≪ k!(ϕ(q)T+(2P)^k)log((2P)^k+1)(2P/log P)^k 
       ≤ (k+1)!log(2P)(1+ϕ(q)T/(2P)^k)(4P^2/log P)^k.

Multiplying this by V^-2k and recalling the choices of V and k, this becomes

    ≪ (qT)^2αP^2α(8k/log P)^k-1.

If log P≥ 8k then this bound is ≪ (qT)^2α P^2α; otherwise, we obtain the bound ≪ (qT)^2α(e^20k)^k (for P large enough). Together, these two bounds imply the claim.


The proofs of the next two lemmas are almost identical to the proofs of the corresponding results in <cit.>, with the following small modifications. Firstly, one applies Lemma <ref>, rather than  the mean value theorem for Dirichlet polynomials. Secondly, the corresponding Dirichlet polynomials are considered on the zero line rather than the one line. Finally, the coefficients are supported on the integers (n,q)=1 which accounts for the extra factor ϕ(q)/q. We give the proof of one of them to illustrate the changes needed.



Let q,T≥ 1, 2 ≤ Y_1 ≤ Y_2 and ℓ⌈log Y_2/log Y_1⌉. For a_m, c_p 1-bounded complex numbers, define

    Q(χ,s) ∑_Y_1≤ p≤ 2Y_1 c_pχ(p)p^-s  and   A(χ,s) ∑_X/Y_2≤ m≤ 2X/Y_2 a_mχ(m)m^-s.
 
Then

    ∑_χ q∫_-T^T |Q(χ,it)^ℓA(χ,it)|^2 dt ≪ϕ(q)/qXY_12^ℓ(ϕ(q)T + ϕ(q)/qXY_1 2^ℓ)(ℓ+1)!^2.


Moreover, we have the same bound for

    ∑_χ q |Q(χ,0)^ℓA(χ,0)|^2

when we put T=1 on the right-hand side.



This is analogous to <cit.>. The Dirichlet polynomial Q(χ,s)^ℓA(χ,s) has its coefficients supported on the interval

    [Y_1^ℓ· X/Y_2,(2Y_1)^ℓ· 2X/Y_2]⊂ [X,2^ℓ+1Y_1X].

We now apply Lemma <ref> to arrive at

    ∑_χ q∫_-T^T |Q(χ,it)^ℓA(χ,it)|^2 dt≪(ϕ(q)T+ϕ(q)/q2^ℓY_1 X)∑_X≤ n≤ 2^ℓ+1Y_1X
    (n,q)=1(∑_n=mp_1⋯ p_ℓ
    Y_1≤ p_1,…, p_ℓ≤ 2Y_1,
     X/Y_2≤ m≤ 2X/Y_21)^2.


We note that, for each n in the outer sum, we have 

    ∑_n=mp_1… p_ℓ
    Y_1≤ p_1… p_ℓ≤ 2Y_1,
     X/Y_2≤ m≤ 2X/Y_21≤ℓ!·∑_n=mr
     p| r⟹ Y_1≤ p≤ 2Y_11ℓ!g(n)

where g(n) is a multiplicative function defined by g(p^k)=k+1 for Y_1≤ p≤ 2Y_1 and g(p^k)=1 otherwise. Consequently,

    ∑_χ q∫_-T^T |Q(χ,it)^ℓA(χ,it)|^2 dt≪(ϕ(q)T+ϕ(q)/q2^ℓY_1X)(ℓ!)^2∑_X≤ n≤ 2^ℓ+1Y_1X
     (n,q)=1g(n)^2.

Shiu's bound <cit.> in dyadic ranges yields

    ∑_Y≤ n≤ 2Y
     (n,q)=1g(n)^2≪ Yϕ(q)/q∏_p≤ Y
    p∤ q(1+|g(p)|^2-1/p)≪ Yϕ(q)/q.


We now split the right-hand side of (<ref>) into dyadic ranges, apply (<ref>) to each of them and sum the results up to finish the proof of the first claim. The second claim is proven in the same way, but using Lemma <ref> in place of Lemma <ref>.



Let X≥ H ≥ 1, Q ≥ P ≥ 1. Let a_m,b_m,c_p be 1-bounded sequences with a_mp = b_mc_p whenever p ∤ m and P ≤ p ≤ Q. Let Ξ be a collection of Dirichlet characters modulo q≥ 1. Let 
    Q_v,H(χ,s) ∑_P≤ p≤ Q
    e^v/H≤ p ≤ e^(v+1)/H c_pχ(p)p^-s,

and 

    R_v,H(χ,s)∑_Xe^-v/H≤ m≤ 2Xe^-v/H b_mχ(m)m^-s·1/1+ω_[P,Q](m),

for each χ∈Ξ and v≥ 0. Let T⊂ [-T,T] be measurable, and I{j ∈Z : ⌊ H log P⌋≤ j≤ H log Q}. Then

    ∑_χ∈Ξ∫_T|∑_n ≤ X a_nχ(n)n^-it|^2 dt ≪ H log(Q/P) ∑_j ∈I∑_χ∈Ξ∫_T|Q_j,H(χ,it)R_j,H(χ,it)|^2 dt 
       + ϕ(q)/qX(ϕ(q)T+ϕ(q)/qX)(1/H+1/P) + ϕ(q)/qX(∑_n ≤ X
     (n,q) = 1 |a_n|^2 1_(n,P) = 1),

where P∏_P ≤ p ≤ Q p.

Moreover, the same bound holds for 

    ∑_χ∈Ξ|∑_n ≤ X a_nχ(n)|^2

with T=1 and the integration removed on the right-hand side.



The proof is almost identical to the proof of <cit.>, the only slight difference being that after splitting the sum involving a_n into short sums, one estimates the error terms by applying Lemma <ref> (or Lemma <ref> in the case of (<ref>)) instead of the mean value theorem for Dirichlet polynomials.




§ LEMMAS ON MULTIPLICATIVE FUNCTIONS






 §.§ Preliminaries


Throughout this section, given t ∈R we set

    V_t exp(log(3+|t|)^2/3loglog(3+|t|)^1/3).

For y ≥ 2, Re(s) > 1, and a multiplicative fℕ→𝕌, we define 

    L_y(s,f) ∏_p > y∑_k ≥ 0f(p^k)/p^ks.

Also recall the definition of the 𝔻_q distance from (<ref>), and let 𝔻𝔻_1.

We begin with two estimates for L_y(s,f) from the work of Koukoulopoulos <cit.>.


Let x,y≥ 2, t∈ℝ, and let fℕ→𝕌 be multiplicative. Then

    log|L_y(1+1/log x+it,f)|=(∑_y<p≤ xf(p)p^-it/p)+O(1).




This is <cit.>.



Let ε>0. Let q≥ 1 and s=σ+it with σ>1 and t∈ℝ. Let y≥ qV_t, and let χ q be a character. Then, if |t|≥ε/log y or if χ is complex, we have |L_y(s,χ)|≍_ε 1.



This is <cit.>.



In this section and the next, we need estimates for the count of zeros of  L(s,χ), namely

    N(σ,T,χ)∑_ρ:  L(ρ,χ)=0
    (ρ)≥σ
    |(ρ)|≤ T1,

where multiple zeros are counted according to their multiplicities. 

 For Q,T≥ 1, 1/2≤σ≤ 1 and ε>0, we have 

    ∑_q≤ Q  _χ q N(σ,T,χ)≪_ε (Q^2T)^(12/5+ε)(1-σ).




This is well known (see `Zeros Result 1 (iv)' in <cit.>). For 1/2≤σ≤ 4/5, say, the lemma follows from the work of Huxley <cit.>, whereas in the complementary region we can apply Jutila's log-free zero-density estimate <cit.> (with 12/5+ε replaced with the better exponent 2+ε).





 §.§ General estimates for partial sums of multiplicative functions

In this subsection we collect various estimates for partial sums of 1-bounded multiplicative functions.
 
Let x ≥ 10 and 1 ≤ q,T ≤ 10x. Let fNU be a multiplicative function. Then

    1/x∑_n ≤ x
     (n,q) = 1 f(n)≪ϕ(q)/q((M_q(T)+1)e^-M_q(T) + 1/√(T) + (log x)^-1/4),

where 

    M_q(T) = M_q(f;x,T)inf_|t|≤ T𝔻_q(f,n^it;x)^2.
 




We may assume that T≤√(log x), since otherwise we can use  M_q(T)≤ M_q(√(log x)) and the fact that y↦ (y+1)e^-y is decreasing to reduce to the case T=√(log x). But then the claim follows[In <cit.>, it is assumed that q≤√(x), but the same proof works for q≤ 10x.] from <cit.>. 





We also need a version of Halász's inequality that is sharp for sums that are restricted to rough numbers (i.e., integers having only large prime factors). This will be employed in the proof of Lemma <ref>.


 
Let 2 ≤ y ≤ x, and let fNU be multiplicative. Then

    1/x∑_n ≤ x
    P^-(n)>y f(n) ≪(1+M(f;(y,x],log x/log y))e^-M(f;(y,x],log x/log y)/log y + 1/log x,

where M(f;(y,x],T) is defined for T≥ 0 by 

    M(f;(y,x],T) inf_|t| ≤ TD(f,n^it;y,x)^2

with 

    D(f,g;y,x) (∑_y < p ≤ x1-(f(p)g(p))/p)^1/2.




Without loss of generality, we may assume that f(p^k)=0 for all primes p≤ y and all k≥ 1. We may also assume that y≤ x^1/2, since otherwise the estimate follows trivially from the prime number theorem.

A consequence of <cit.> (see in particular formula (7.3) there) implies that

    ∑_n ≤ x f(n) ≪ (1+M)e^-Mx/log y + x/log x,

where M is defined implicitly via

    sup_|t| ≤log x/log y|F(1+1/log x + it)/1+1/log x + it| = e^-Mlog x/log y,

where F(s) ∏_p∑_k ≥ 0 f(p^k)/p^ks for Re(s) > 1. On the other hand, as f(p^k) = 0 for all p ≤ y, by Lemma <ref> for any t ∈R we have

    |F(1+1/log x+it)|log y/log x≍exp(-∑_y < p ≤ x1-Re(f(p)p^-it)/p) = e^-D(f,n^it;y,x)^2,

so that

    e^-M≪sup_|t| ≤log x/log ye^-D(f,n^it;y,x)^2/|1+1/log x+it|≪ e^-M(f;(y,x],log x/log y).

In particular, M(f;(y,x],log x/log y) ≤ M + O(1). 

Since t ↦ (1+t)e^-t is decreasing, it now follows from (<ref>) that

    ∑_n ≤ x f(n) ≪(1+M(f;(y,x],log x/log y))e^-M(f;(y,x],log x/log y)x/log y + x/log x,

as claimed.


In the proof of Theorem <ref>, we will also need the following three lemmas.


 
 Let α∈R. Then for any x ≥ 3 and any multiplicative fNU,

    1/x∑_n ≤ x f(n)n^iα = x^iα/1+iα1/x∑_n ≤ x f(n) + O(log(2+|α|)/log xexp(D(f,1;x) √((2+o(1)) loglog x))).



From <cit.>, we have the claimed estimate with the error term

    O(log(2+|α|)/log xexp(∑_p≤ x|1-f(p)|/p)).
 
Hence, the claim follows from 

    ∑_p ≤ x|1-f(p)|/p≤(∑_p≤ x1/p)^1/2(∑_p ≤ x|1-f(p)|^2/p)^1/2≤(loglog x +O(1))^1/2(2∑_p ≤ x1-Re(f(p))/p)^1/2.





 
Let X,Z ≥ 10, with 1 ≤ Z ≤ (log X)^1/20. Let 1 ≤ h ≤ X, and let 1 ≤ q ≤ h/10. Let gNU be multiplicative, and let t_0 be a minimizer of t ↦D(g,n^it;X) on |t| ≤ X. Then for every x∈ [X,2X] we have 

    1/2π h∫_t_0-Z^t_0+Z(∑_n ≤ 3X 
     (n,q) = 1 g(n)n^-it) (x+h)^it-x^it/it  dt= (1/3hX∑_n ≤ 3X 
     (n,q) = 1 g(n)n^-it_0) ∫_x^x+h v^it_0 dv + O(ϕ(q)/qZ^1/2).



We note that (x+h)^it-x^it/it = ∫_x^x+h v^-1+itdv for each t ∈ [t_0-Z,t_0+Z]. Inserting this into the left-hand side of the statement, swapping the orders of integration and making the change of variables u    t-t_0, we obtain

    1/2π h∫_x^x+h v^-1+it_0(∫_-Z^Z v^iu∑_n ≤ 3X 
     (n,q) = 1 g(n)n^-it_0-iu  du )  dv.


Let Mmin_|u| ≤1/2log XD_q(g,n^i(t_0+u);X)^2. By Lemma <ref>, if  M≥ (1/4)loglog X, then

    sup_|u| ≤ Z|∑_n ≤ 3X 
     (n,q) = 1 g(n)n^-it_0-iu| ≪φ(q)/q (X(1+M)e^-M+X/(log X)^1/4) ≪ X(log X)^-1/4+o(1),

in which case the expression (<ref>) can be bounded by

    ≪h/hx· Z X(log X)^-1/4+o(1)≪ (log X)^-1/5

for X sufficiently large, given that Z≤ (log X)^1/20. The claim follows in this case, so we may assume in the sequel that M < (1/4)loglog X. 

Put g_t_0(n)   g(n)n^-it_0. Since |u| ≤ Z, Lemma <ref> yields

    ∑_n ≤ 3X 
     (n,q) = 1 g_t_0(n)n^-iu   = (3X)^-iu/1-iu∑_n ≤ 3X 
     (n,q) = 1 g_t_0(n) + O(X (log(2Z))/log X e^√((2+o(1))Mloglog X)) 
       =(3X)^-iu/1-iu∑_n ≤ 3X 
     (n,q) = 1 g_t_0(n) + O(X/(log X)^0.29-o(1)),

as √(1/2)-1 < -0.29. Furthermore, 0.29-1/20 > 1/5, so upon inserting this estimate into (<ref>) that expression becomes

    (∑_n ≤ 3X 
     (n,q) = 1 g(n)n^-it_0)∫_x^x+h v^-1+it_0I(v;3X)/hdv + O(1/(log X)^1/5),

where for y ≥ 1 we have defined

    I(v;y) 1/2π∫_-Z^Z v^iuy^-iu/1-iu du.


Using a standard, truncated version of Perron's formula (e.g., <cit.>), if y ≠ v then

    I(v;y) 
       = v/y(1/2π i∫_Re(s) = 1(y/v)^s/sds + O(y/v/Z|log(y/v)|)) 
       = v/y 1_y > v  + O(1/Z|log(y/v)|).

As [x,x+h] is disjoint from [3X-3X√(Z), 3X + 3X√(Z)], we have Z|log(3X/v)| ≫ Z^1/2 for all v ∈ [x,x+h] and (<ref>) becomes

    (3hX)^-1(∑_n ≤ 3X 
     (n,q) = 1 g_t_0(n)) ∫_x^x+h v^it_0 dv +O(ϕ(q)/qhZ∫_x^x+hdv/|log(3X/v)|+1/(log X)^1/5) 
       = (3hX)^-1(∑_n ≤ 3X 
     (n,q) = 1 g_t_0(n))∫_x^x+h v^it_0 dv + O(ϕ(q)/qZ^1/2+1/(log X)^1/5).

Since (log X)^-1/5≪φ(q)/(qZ^1/2), this completes the proof.






 §.§ Bounds on prime sums of twisted Dirichlet characters

The following lower bound on the pretentious distance D between Dirichlet and Archimedean characters will enable us to show that f can only correlate significantly with at most one Dirichlet character χq, which must then be χ_1 (see Proposition <ref>).

Let x ≥ 10, 1 ≤ q ≤ x, and let χ be any non-principal Dirichlet character modulo q induced by a primitive character χ^∗ modulo q^∗. Then

    inf_|t| ≤ 10xD_q(χ,n^it;x)^2 ≥1/4log(log x/log(2q^∗)) + O(1).




 For the purpose of proving Theorem <ref>, our estimates only require uniformity in the t-aspect for |t| ≤log x, and in that regime Lemma <ref> is easier to prove. However, in order to prove Theorem <ref>, we will need full uniformity in the much larger range |t| ≪ x. The same remark applies to Lemma <ref> and several lemmas in Section <ref>.





We may assume that x is larger than any fixed absolute constant, since otherwise the bound is trivial upon choosing the term O(1) appropriately. 
Let t_0 be a minimizer for the map t↦D(χ,n^it;x) on [-10x,10x]. We split the proof of the lemma into two cases. 

Case 1. If |t_0|≤log x, then the claim follows directly from <cit.>.




Case 2. Next assume that  |t_0|>log x. Let us write χ(n)=χ^*(n)1_(n,r)=1, where χ^*q^* induces χ and (r,q^*)=1.  Let y    q^∗V_10x; then we have V_10x≤ y≤max{ (q^∗)^2,V_10x^2}. 

We now observe that, since q^*<y, we have

    D_q(χ,n^it_0;x)^2    ≥Re(∑_y < p ≤ x1-χ^*(p)p^-it_0/p)-O(∑_p| q
    p≥ y1/p)
       = log(log x/log y) - log|L_y(1+1/log x + it_0,χ^*)| + O(1),

where for the last line we used Lemma <ref> and the crude estimate ∑_p| q1≪log x=o(y).

Recalling log x ≤ |t_0| ≤ 10x and our choice of y, Lemma <ref> gives |L_y(1+1/log x+it_0,χ^∗)| ≍ 1. It follows that

    D_q(χ,n^it_0;x)^2    ≥log(log x/log y) + O(1)≥1/4log(log x/log(2q^∗))  + O(1),

where for the last inequality we used y≤max{(q^*)^2,V_10x^2}.






The following pointwise bound for twisted character sums over primes will be needed in the proof of Proposition <ref>.


Let x≥ 10, X=x^(log x)^1/25, and 1≤ q≤ x. Let h be a fixed smooth function supported on [1/2,4]. Then, for ε∈ (0,1) and for any character χ q with (χ)≤ x^ε, uniformly in the range |t|≤ X we have

    |∑_nΛ(n)χ(n)n^-ith(n/x)| ≪_hε(log^3 1/ε)x +x/(log x)^0.3+x/t^2+1.

Moreover, the x/t^2+1 term can be deleted for all but possibly one non-principal χ q, and this χ (if it exists) must be real and satisfy L(β,χ)=0 for some real β>1-c_0/(log q) for some absolute constant c_0>0.




By looking at the proof of Lemma <ref>, it is clear that (<ref>) works also for the sharp weight h(u)=1_u∈ (0,1] if x/(t^2+1) is replaced with x/(|t|+1) there. The 1/(t^2+1) decay is helpful when we apply Lemma <ref> in the proof of Proposition <ref> to ensure that when (<ref>) is summed over a well-spaced set of t the resulting bound will not be too large.


 Without loss of generality, we may assume that x is larger than any given constant,  that ε≥ (log x)^-0.4, and that ε is smaller than any fixed constant. If χ is induced by χ^∗q^∗, we have

    ∑_nΛ(n)χ(n)n^-ith(n/x)=∑_nΛ(n)χ^∗(n)n^-ith(n/x)+O_h((log x)^2),

and as the error term is small, may assume that χ is primitive and q=q^∗.

We split into cases depending on the sizes of q and t. 

Case 1. Suppose first that q=1. Then χ is identically 1, and in that case by Mellin inversion we have

    ∑_nΛ(n)n^-ith(n/x)=-1/2π i∫_2-i∞^2+i∞ζ'/ζ(s+it)h(s)x^s  ds.

Since h is smooth, its Mellin transform h̃ satisfies |h(s)|≪_h 1/(1+|s|^10) for (s)∈ [-100,100]. Hence, shifting the line of integration to (s)=b:=1-(log x)^1/10, we obtain

    ∑_nΛ(n)n^-ith(n/x)=-1/2π i∫_b-ilog x^b+ilog xζ'/ζ(s+it)h(s)x^s  ds+h(1-it)x+O_h(x/log x),

and this is ≪ x/(t^2+1)+O_h(x/log x) by using the Vinogradov–Korobov bound |ζ'/ζ(s+it)|≪log x in the region of the integrand. We may thus assume that q^∗≥ 2.

Case 2. Suppose then that  2≤ q^∗≤ (log x)^10,|t|≤ (log x)^10. Then (<ref>) follows straightforwardly from partial summation and the Siegel–Walfisz theorem (with a better bound of ≪_h x(log x)^-100).

Case 3. Next, suppose q^∗>(log x)^10, |t|≤ (log x)^10. We apply the explicit formula (proven similarly to <cit.>) 

    ∑_nΛ(n)χ^∗(n)n^-ith(n/x)=-∑_ρ=β+iγ:
    L(ρ,χ^∗)=0
    |γ-it|≤ T
    0≤β≤ 1x^ρ-ith(ρ-it)+O_h(x/T(log^3(qx(|t|+2)))),

where we choose T=(log x)^100 to make the error term small.

 Let D=log(x^ε(|t|+2)). Note that by the Landau–Page theorem <cit.> we have the zero-free region L(s,χ^∗)≠ 0 for (s)≥ 1-c_0/(log D) for some constant c_0>0, apart from possibly one zero ρ=β, which has to be real and simple; additionally, such an exceptional zero can only exist for at most one character χ^∗ of conductor ≤ x^ε, which has to be real and non-principal. Applying the bound h(s)≪ 1/(1+|s|^10) for (s)∈ [-100,100], the contribution of ρ=β to the right of (<ref>) is certainly 

    ≪_h x/t^2+1,

which is admissible. Moreover, the contribution of (ρ)≤ 9/10 to (<ref>) is trivially ≪ x^91/100.

By splitting the sum in (<ref>) into pieces (s)∈ (1-(k+1)c_0/(log D),1-kc_0/log D], (s)∈ [T,2T], the sum becomes

    ≪_h x/t^2+1+x^91/100+∑_1≤ k≤ (log D)/(5c_0) ∑_T=2^j
    j≥ 0x^1-kc_0/log DN(1-kc_0/log D,2T,χ^∗)/T^10+1.


The log-free zero density estimate (see Lemma <ref>) allows us to bound this by

    ≪_h x/t^2+1+x^91/100+∑_1≤ k≤ (log D)/(5c_0) ∑_T=2^j
    j≥ 0x^1-kc_0/log D(q^∗)^6kc_0/(log D)/T^5+1≪ x^-c_0/2log D.

by the geometric sum formula and the fact that q^∗≤ x^1/1000. Noting that x^-c_0/(2log D)≪ε^100 for |t|≤ (log x)^10≤ q^∗≤ x^ε, this case has now been handled.

Case 4. We are left with the case |t|>(log x)^10, q^∗≥ 2. Since q^∗ = cond(χ) ≤ x^ by assumption, we may assume that 2≤ q^∗≤ x^1/50000 by selecting  smaller if necessary. Since |t| is large, we no longer need the smoothing factor h(n/x), and in fact by partial summation (and the fact that h' is bounded) we see that (<ref>) in the regime under consideration follows once we prove

    |∑_n≤ x'Λ(n)χ(n)n^-it|≪εlog^3(1/ε)x'+x'/(log x)^0.3

for any x' ∈ [x/2,4x]. In what follows, for notational convenience we denote x' by x. 

Put y = (q^∗)^4V_X^100, so that for q^∗≤ x^1/50000 we have y ≤ x^1/10000. We define 

    μ_y(m)    μ(m)1_P^-(m) > y, 
    log_y m       (log m)1_P^-(m) > y,

and as in <cit.> we make use of the convolution identity

    Λ(n)1_P^-(n)>y=μ_y∗log_y(n),   n>y.

By the prime number theorem, we then see that for any t ∈R we have

    ∑_n ≤ xΛ(n)χ(n)n^-it   = ∑_y^2 < n ≤ xΛ(n)χ(n)n^-it + O(y^2)
       = ∑_y^2 < md ≤ xμ_y(m)χ(m)m^-itlog_y(d)χ(d)d^-it + O(y^2+x^1/3).


Let M,D∈ [y,x] be parameters that satisfy MD = x, with D ≤ x^1/2. Using the hyperbola method, we have

    ∑_y^2<n≤ xΛ(n)χ(n)n^-it=T_1+T_2 + O(y^2+x^1/3),
    
    T_1    ∑_m ≤ Mμ_y(m)χ(m)m^-it∑_y^2/m < d ≤ x/mlog_y(d) χ(d)d^-it
    
    T_2    ∑_d ≤ Dlog_y(d)χ(d)d^-it∑_y^2/d < m ≤ x/d
    m>Mμ_y(m)χ(m)m^-it.


We first deal with T_2. By Halász's theorem for rough numbers (Lemma <ref>), for each d ≤ D the inner sum is

    ≪x/d((N+1)e^-N/log y + loglog M/log M) + y^2/d,

where we have defined

    N inf_|u| ≤log x∑_y<p ≤ M1-Re(μ_y(p)χ(p)p^-i(t+u))/p.

As D ≤ x^1/2, M≥ x^1/2 and μ_y(p)=-1_p>y, it follows (as in the proof of Lemma <ref>) that

    N    ≥inf_|u| ≤log x∑_y < p ≤ x1+Re(χ(p)p^-i(t+u))/p +O(1)
       ≥loglog x/log y+ inf_|u| ≤log xlog|L_y(1+1/log x + i(t+u),χ)| + O(1).


Now since y > q^∗V_2X, Lemma <ref> tells us that

    |L_y(1+1/log x + iw,χ)| ≍ 1

for χ complex and |w|≤ 2X, or for χ real and 1≤ |w|≤ 2X. Note that since |t|≥ (log x)^10 in (<ref>) by assumption, we have |t+u|≥ 1 there, and thus (<ref>) holds in any case for w=t+u, |u|≤log x.

The above implies that N ≥log((log x)/(log y)) - O(1). Hence, by partial summation and the estimate ∑_d≤ u1_P^-(d)>y≪ u/(log y) coming from Selberg's sieve, we have 

    T_2    ≪xloglog x/log y/log x∑_d ≤ D
     P^-(d) > ylog d/d + (ylog x)^2
       ≪xloglog x/log y/log x(log D/log y + ∫_y^D (∑_d ≤ u 
     P^-(d) > y 1) log( u/e)du/u^2) +(ylog x)^2
       ≪ x(log D)^2loglog x/log y/(log x)(log y) + (ylog x)^2,

for all non-principal characters χ modulo q (recalling that y≤ x^1/10000).

We next estimate T_1. By partial summation, the inner sum in T_1, for each m ≤ M, is

    |∑_y^2/m < d ≤ x/m
     P^-(d) > y (log d)χ(d) d^-it|≪ (log x)max_y≤ u_1≤ u_2≤ x/m|∑_u_1≤ d≤ u_2
    P^-(d)>yχ(d)d^-it|  R(m).


Recalling that y=(q^∗)^4V_X^100, we apply <cit.> to the R(m) terms, obtaining

    R(m) ≪log x/log y((x/m)^1-1/(30log y) + (x/m)^1-1/(100log V_t)),

and since y≥ V_t^100, the second term can be ignored.


Summing over m≤ M, and using Selberg's sieve to bound the number of integers with P^-(m)>y, we conclude that T_1 is bounded by

    ∑_m ≤ M
     P^-(m) > y |R(m)|   ≪ xlog x/log yx^-1/(30log y)∑_m≤ M
    P^-(m)>ym^-1+1/(30log y)
       ≪ x(log x/log y)^2(x/M)^-1/(30log y).


Putting this all together and recalling |t| ≤ X, we find that

    T_1    ≪ x(log x/log y)^2(x/M)^-1/(30log y),
    
    T_2    ≪ x(log (x/M))^2loglog x/log y/(log x)(log y).

We select M=x/y^1000log(log x/log y)∈ [x^1/2,x] (so in particular y≤ x/M=D≤ x^1/2, as required). Then log(x/M) = 1000 log y log(log x/log y) and thus, as q^∗≤ x^1/10, we have

    T_1 + T_2 ≪ x(log y/log x)^30+x log y/log xlog^3(log x/log y)≪ x log y/log xlog^3(log x/log y).

If q^∗≤ V_X then log y ≪ (log x)^0.694 for large enough x, and hence the bound reduces to ≪ x/(log x)^0.3. On the other hand, if V_X < q^∗≤ x^ then the above bound becomes ≪ x log q^∗/log xlog^3(log x/log q^∗)≪εlog^3(1/ε)x. This proves (<ref>), and thus completes the proof of the lemma.








§ KEY PROPOSITIONS




The goal of this section is to prove two key propositions, namely Propositions <ref> and <ref>. For the proofs of both of these propositions, we will need good bounds on the number of Dirichlet characters whose L-functions have a bad zero-free region.


The log-free zero density estimate is easily employed to yield the following.

 Let x≥ 10, ε∈ ((log x)^-1/20,1), and 1/(loglog x)≤ M≤^20log x/(20loglog x), and define the set

    𝒬_x,ε,M{q≤ x: ∏_χ q
    (χ)>x^ε^20 L(s,χ)≠ 0  for  (s)≥ 1-M(loglog x)/log x,   |(s)|≤ 3x}.

Then for 1≤  Q≤ x we have |[1,Q]∖𝒬_x,ε,M|≪ Qx^-ε^20/2. Moreover, there exists a set ℬ_x,ε,M⊂ [x^ε^20,x] of size ≪ (log x)^10M such that every integer in [1,x]∖𝒬_x,ε,M is a multiple of some element of ℬ_x,ε,M.



If Q≤ x^ε^20, then trivially [1,Q]∩ℤ⊆𝒬_x,ε,M, so there is nothing to be proved. We may thus assume that Q>x^ε^20.

Let

    ℬ_x,M{q≤ x:  ∃ ≥ 1-Mloglog x/log x,   |t|≤ 3x    with ∏_χ q
    χ  primitiveL( + it,χ) = 0}.

By Lemma <ref>, we have 

    |ℬ_x,M| ≤∑_q ≤ x  _χq N(1-Mloglog xlog x, 3x, χ) ≪ (x^3)^(12/5+0.1)Mloglog xlog x≪(log x)^10M.


Since L(s,χ) and L(s,χ') have the same zeros in the region Re(s) > 0 if χ and χ' are induced by the same character, we see that every q ≤ x with q∉𝒬_x,ε,M is a multiple of some element of ℬ_x,ε,M := ℬ_x,M∩[x^ε^20,x], and each such element has ≤ Qx^-ε^20+1 multiples up to Q. Thus

    |[1,Q]∖𝒬_x,ε,M|≪ (log x)^10MQx^-ε^20≪ Qx^-ε^20/2,

since M≤^20(log x)/(20loglog x), ε>(log x)^-1/20, and Q > x^ε^20.


The next lemma will be a crucial ingredient in the proof of Propositions <ref> and <ref>.


Let x≥ 10 and (log x)^-1/50≤ε≤ 1. For a character χ q, let  

    u_χ=1,  χ principal or χ real and (χ)≤ x^ε^20
    0,  otherwise.   v_χ=1,  χ  principal
    
    0,  otherwise.
Let  q∈𝒬_x,ε,ε^-6.

    
  * Uniformly for x^ε^5.5≤ P≤ x, we have

    sup_χ qsup_ε^-10u_χ≤ |t|≤ 2.1x|∑_n≤ PΛ(n)χ(n)n^-it|≪ε^10P.




  * We have 
    
    inf_χ qinf_v_χ√(log x)≤ |t|≤ 2.1x𝔻_q(χ(n)n^it,1;x)^2≥ 5.5log1/ε+O(1).





 We may assume that x is large enough and that ε>0 is small enough. 

Suppose first that (χ)>x^ε^20. In that case we shall show the stronger bound

    sup_|t|≤ 2.1x|∑_n≤ PΛ(n)χ(n)n^-it|≪P/(log P)^100.


By Perron's formula, we have

    ∑_n≤ PΛ(n)χ(n)n^-it=-1/2π i∫_1+1/log x-iT^1+1/log x+iTL'/L(s+it,χ)P^s/s  ds+O(P/(log P)^100)

where T (log x)^1000. Recall that by the definition of 𝒬_x,ε,ε^-6 the function L(s,χ) has the zero-free region (s) ≥ 1-σ_0 1-ε^-6(loglog x)/(log x), |(s)|≤ 3x. Shift the line of integration in (<ref>) to (s)= 1-σ_0/2. By <cit.>, we have 
    |L'/L(s,χ)|≪ (log x)^2
 whenever 9/10≤(s)≤ 2, |(s)|≤ 10x, and the distance from s to the nearest zero of L(·, χ) is ≥1/log x.  Hence, we obtain for (<ref>) the bound

    ≪ P^1-σ_02(log x)^2(loglog x)≪ P^1-ε^-1/2loglog P4log P≪P/(log P)^100.


Suppose then that (χ)≤ x^ε^20. Then, since (χ)≤ P^ε^14, by Lemma <ref> and Remark <ref> we have

    |∑_n≤ PΛ(n)χ(n)n^-it|≪ε^14log^3(1/ε)P+P/(log P)^0.3+P/1+|t|,

where the last term can be deleted if χ is complex. Since (log P)^-0.3≤ε^10 and by assumption |t|≥ε^-10 if χ is real and (χ)≤ x^ε^20, we obtain the desired bound. 

Proof of (ii). Suppose first that χ is principal. Let y=V_10x in the notation of (<ref>) (in particular, log y ≥√(log x)). Note that ∑_p| q,  p≥ y1/p≪ 1. Then by Mertens's theorem and Lemma <ref>, we have

    𝔻_q(χ(n)n^it,1;x)^2   =𝔻_q(n^it,1;x)^2≥loglog x/log y+(∑_y<p≤ x1/p^1+it)+O(1)
       =loglog x/log y+log|L_y(1+1/log x+it,1)|+O(1).

Lemma <ref> tells us that |L_y(1+1/log x+it,1)|≍ 1 for 1log y≤ |t|≤ 10 x, so we obtain

    inf_1√(log x)≤ |t|≤ 10x𝔻_q(n^it,1;x)^2≥(1/3-o(1))loglog x,

which suffices. 

If χ is non-principal (so that v_χ = 0) and (χ)≤ x^ε^20, then Lemma <ref> gives the desired bound

    𝔻_q(χ(n)n^it,1;x)^2≥11/40log(log x/log x^ε^20)+O(1)=5.5log1/ε+O(1).

We are then left with the case where (χ)> x^ε^20.

Since ∑_p| q, p>x^ε^5.51/p≪ 1, we have

    𝔻_q(χ(n) n^it,1;x)^2 ≥( ∑_x^ε^5.5≤  p ≤ x1-χ(p)p^it/p)+ O(1).

By Mertens's theorem, this is

    ≥ 5.5log1/ +S+ O(1),

where by partial summation

    S:=∑_x^ε^5≤ p≤ xχ(p)p^-it/p= 1/xlog x∑_x^ε^5≤ p≤ xχ(p)(log p)p^-it+∫_x^ε^5^x (log y+1)∑_x^ε^5≤ p≤ yχ(p)(log p)p^-it/y^2log^2 ydy.

From part (i) we now see that S=O(1), completing the proof.


 Let x≥ 10 and (log x)^-1/50≤ε≤ 1. Let fℕ→𝕌 be a multiplicative function. Let (χ_1,t_χ_1) be a point minimizing the map (χ,t)↦𝔻_q(f,χ(n)n^it;x) among χ q and |t|≤ x. 

Let 10 ≤ P,Q ≤ x with log Qlog P≤ε^-1/6, and let g: N [0,1] be any multiplicative function with the property that g(p) = 1 for all p ∉ [P,Q]. 

Then, with the notation of Lemma <ref>, for all q∈𝒬_x,ε,ε^-6 we have

    sup_χ q
    χ≠χ_1sup_|t| ≤ x/2sup_y∈ [x^0.1,x]|1/y∑_n≤ y f(n)g(n)χ̅(n)n^-it|≪εϕ(q)/q.

In addition, for all 1 ≤ Z ≤ x and 1≤ q≤ x we have 

    sup_|t| ≤ x 
     |t-t_χ_1| ≥ Zsup_y∈ [x^0.1,x]|1/y∑_n≤ y f(n)g(n)χ̅_̅1̅(n)n^-it| ≪ϕ(q)/q((log x)^-1/15 +1/√(Z)).



 
    For the proofs of Theorem <ref> and <ref>, we need a version of this proposition where the supremum over t is over the smaller range [-1/2log x,1/2log x], and (χ_1,t_χ_1) is taken be a minimizing point of (χ,t)↦𝔻_q(f,χ(n)n^it;x) with |t|≤log x. The same proof applies to this case, and we can obtain a similar variant of Corollary <ref> as well.
    
    
    
    The same arguments as in Subsection <ref> show that we cannot prove (<ref>) for all q≤ x without settling Vinogradov's conjecture at the same time. However, in the smaller range of q≤ x^ε^20  there are no exceptional moduli in Proposition <ref>; cf. <cit.> for a related result in this range.
     



We begin with the first claim. We may assume in what follows that x is larger than any fixed constant and that  is smaller than any fixed constant. 

Suppose for the sake of contradiction that there is a character χ≠χ_1 q and a real number t ∈ [-x/2,x/2] for which 

    |∑_n≤ y f(n)g(n)χ(n)n^-it| ≥ϕ(q)/qy

for some y∈ [x^0.1,x]. Owing to > (log x)^-1/50 and the fact that ∑_y≤ p≤ x1/p≪ 1, Lemma <ref> implies that there is some v ∈ [-1/2log x,1/2log x] for which

    D_q(fg,χ(n) n^i(t+v);x)^2 ≤ 1.001 log1/ + O(1).

Since fg(p) = f(p) for all p ∉ [P,Q] we have that

    max_α∈R|D_q(fg,χ(n)n^iα;x)^2 - D_q(f,χ(n)n^iα;x)^2| 
       = max_α∈R|∑_P ≤ p ≤ Q 
     p ∤ q(1-g(p))Re(f(p)χ̅(p)p^-iα)/p| ≤∑_P ≤ p ≤ Q1-g(p)/p≤log(log Q/log P) + O(1),

and thus as log Q ≤ε^-1/6log P we obtain

    D_q(f,χ(n)n^i(t+v);x)^2 ≤ 1.17 log(1/ε) + O(1).

According to the definition of χ_1, we also have D_q(f,χ_1(n) n^it_χ_1;x)^2 ≤ 1.17log(1/) + O(1) with t_χ_1∈ [-x,x]. As such, the pretentious triangle inequality implies that

    𝔻_q(χ_1(n) n^it_χ_1,χ(n) n^i(t+v);x)^2   ≤(D_q(f,χ(n) n^i(t+v);x) + D_q(f,χ_1(n) n^it_χ_1;x) )^2
       ≤ 5.48log1/ε+O(1).

But since χ_1χ is nonprincipal, this contradicts Lemma <ref>(ii). 


We proceed to the second claim of the proposition. We may assume that Z≥ 2. Suppose |t-t_χ_1| ≥ Z and |t| ≤ x. Let |u| ≤ Z/2, so that Z/2 ≤ |t+u-t_χ_1| ≤ 2x. By the definition of t_χ_1 and the triangle inequality, 

    2D_q(f,χ_1(n) n^i(t+u);x)    ≥D_q(f,χ_1(n) n^i(t+u);x) + D_q(f,χ_1(n) n^it_χ_1;x)
       ≥𝔻_q(1,n^i(t+u-t_χ_1);x).



From (<ref>), we see that

    inf_1 ≤ |α|≤ 2x D_q(n^iα,1;x)^2≥(1/3-o(1) )loglog x+O(1).

Therefore, we conclude that 

    D_q(f,χ_1(n) n^i(t+u);x)^2≥(1/12-o(1))loglog x.

Using (<ref>) and ε≥ (log x)^-1/50, we deduce that for x sufficiently large,

    D_q(fg,χ_1(n) n^i(t+u);x)^2≥(1/12-o(1))loglog x - log(log Q/log P) ≥1/15loglog x.

Applying the Halász-type bound of Lemma <ref> with T = Z/2, this yields

    |∑_n≤ y f(n)g(n)χ̅_̅1̅(n)n^-it| ≪ϕ(q)/q((log x)^-1/15+1/√(Z))y,

for every |t| ≤ x satisfying |t-t_χ_1| ≥ Z, as claimed.


We will also require a variant of Proposition <ref> for sums weighted by the factor 1/(1+ω_[P,Q](m)) that arises in the statement of Lemma <ref>.


 Let x≥ R≥ 10, ε∈ ((log x)^-1/50,1) and (log x)^-0.1<α<β<1, with β/α≤ε^-1/6.  Set P=x^α, Q=x^β and for fℕ→𝕌 multiplicative consider the twisted character sum

    R(χ,s)∑_R≤ m≤ 2Rf(m)χ(m)m^-s/1+ω_[P,Q](m).

Let (χ_1,t_χ_1) be a point minimizing the map (χ,t)↦𝔻_q(f,χ(n)n^it;x) for χ q and |t|≤ x. Then, with the notation of Lemma <ref>, for q∈Q_x,ε,ε^-6 we have

    sup_χ q
    χ≠χ_1sup_|t|≤ x/2sup_R∈ [x^1/2,x]1/R|R(χ,it)|≪εϕ(q)/q.

Furthermore, for 1≤ Z≤ (log x)^1/10 we have

    sup_|t| ≤ x 
     |t-t_χ_1| ≥ Zsup_R∈ [x^1/2,x]1/R|R(χ_1,it)|≪1/√(Z)ϕ(q)/q.





The case q=1 of the corollary is a variant of <cit.>. 



 We may assume that x is larger than any fixed constant, and ε is smaller than any fixed constant, since otherwise both results are immediate from the trivial bound |R(χ,it)| ≤ |{R ≤ m ≤ 2R : (m,q) = 1}.
 
The proof of both (<ref>) and (<ref>) rely on the following simple observation: for any m ≥ 1 we have

    1/1+ω_[P,Q](m) = ∫_0^1 r^ω_[P,Q](m) dr.

For each r ∈ (0,1] the map g_r(m) := r^ω_[P,Q](m) is a multiplicative function satisfying 0 ≤ g_r ≤ 1, and such that g_r(p) = 1 for every prime p ∉ [P,Q]. 

Given χq and t ∈R, we therefore have

    1/R|R(χ,it)| = ∫_0^1 (1/R∑_R ≤ m ≤ 2R f(m)g_r(m)χ̅(m)m^-it) dr.

With regards to (<ref>) there is thus some r_0 ∈ (0,1] such that if g = g_r_0 then

    sup_χ q
    χ≠χ_1sup_|t|≤ x/2sup_R∈ [x^1/2,x]1/R|R(χ,it)| 
       ≤∫_0^1 (sup_χ q
    χ≠χ_1sup_|t|≤ x/2sup_R∈ [x^1/2,x]|1/R∑_R ≤ m ≤ 2R f(m)g_r(m)χ̅(m)m^-it|) dr 
       ≤sup_χ q
    χ≠χ_1sup_|t|≤ x/2sup_R∈ [x^1/2,x]|1/R∑_R ≤ m ≤ 2R f(m)g(m)χ̅(m)m^-it|,

and similarly towards (<ref>) there is some r_1 ∈ (0,1] such that if g = g_r_1 then

    sup_|t| ≤ x 
     |t-t_χ_1| ≥ Zsup_R∈ [x^1/2,x]1/R|R(χ_1,it)| ≤sup_|t| ≤ x 
     |t-t_χ_1| ≥ Zsup_R∈ [x^1/2,x]|1/R∑_R ≤ m ≤ 2R f(m)g(m)χ̅_1(m)m^-it|.

The corollary is proved upon applying (<ref>) and (<ref>) of Proposition <ref>, respectively, to each of the last two estimates.




  Let x≥ 10,   (log x)^-1/30<ε≤δ≤  1/2, and η=max{(log x)^-1/30,ε^4}. Let (a_p)_p be 1-bounded complex numbers, let T⊂ [-x,x] be a well-spaced set, and let S{(χ,t) : χq,  t ∈T}. Define 

    N_q,Ssup_x^η≤ P≤ x|{(χ,t) ∈S : |log P/δ P∑_P≤ p≤ (1+δ)Pa_pχ̅(p)p^-it|≥ε}|.

Then, with the notation of Lemma <ref>, for q∈𝒬_x,ε,ε^-6 we have N_q,S≪ε^-2δ^-1. The implied constant is absolute.



For the proof of Theorem <ref> will only require the special, simpler case T={0}.




We may assume without loss of generality that ε>0 is smaller than any fixed constant. Let P ∈ [x^η,x] yield the set of largest cardinality that is counted by N_q,S, and let B_q,S denote the set of pairs (χ,t) yielding the large values counted by N_q,𝒮 at scale P. We have, for some unimodular c_χ,t,

    δ P/log PN_q,S   ≤∑_(χ, t) ∈B_q,S|∑_P ≤ p ≤ (1+δ)P a_pχ̅(p)p^-it| = ∑_(χ,t)∈B_q,S c_χ,t∑_P ≤ p ≤ (1+δ)P a_pχ̅(p)p^-it
       = ∑_P ≤ p ≤ (1+δ)P a_p∑_(χ,t)∈B_q,S c_χ,tχ̅(p)p^-it.

Applying the Cauchy–Schwarz and Brun–Titchmarsh inequalities, this is 

    ≪(δ P/log P)^1/2(∑_P ≤ p ≤ (1+δ)P|∑_(χ,t)∈B_q,S c_χ,tχ̅(p)p^-it|^2)^1/2
       ≪(δ P/log P)^1/2(∑_P ≤ n ≤ (1+δ)PΛ(n)/log P|∑_(χ,t)∈B_q,S c_χ,tχ̅(n)n^-it|^2)^1/2.


Let h be a smooth function supported on [1/2,2] with h(u)=1 for u∈ [1,3/2], and 0≤ h(u)≤ 1 for all u. We insert the weight h(n/P) into the n sum in (<ref>) and expand out the square, obtaining the upper bound

    ≪(δ P/(log P)^2)^1/2(∑_(χ_1,t_1)∈B_q,S∑_(χ_2,t_2)∈B_q,S|∑_nΛ(n)χ_1χ̅_̅2̅(n)n^-i(t_1-t_2)h(n/P)|)^1/2
       = (δ P/(log P)^2)^1/2(S_1+S_2)^1/2,

where we let S_1 be the sum over the pairs with (χ_1χ_2)≤ x^ε^20 and S_2 be the sum over the pairs with (χ_1χ_2)> x^ε^20.

We first treat S_1. If (χ_1χ_2)≤ x^ε^20, then (χ_1χ_2)≤ P^(η^-1/20ε)^20≤ P^ε^10, so by Lemma <ref> (and the fact that x≤ P^η^-1≤ P^(log P)^1/25) for some non-principal real character ξ_1 q we have

    |∑_nΛ(n)χ_1χ̅_̅2̅(n)n^-i(t_1-t_2)h(n/P)|≪ε^10log^3(1/ε)P+P/(log P)^0.3+ P1_χ_1χ_2∈{χ_0, ξ_1}/|t_1-t_2|^2+1,

with χ_0 q the principal character. 

Since |ℬ_q,S|=N_q,S and (log P)^-0.3≤ε^5, summing (<ref>) over (χ_1,t_1),(χ_2,t_2) ∈B_q,S shows that the contribution of the characters with small conductor obeys the bound

    S_1   ≪ε^5N_q,S^2 P+∑_(χ_1,t_1) ∈B_q,S∑_χ_2 q∑_t_2∈𝒯P/|t_1-t_2|^2+11_χ_1χ_2∈{χ_0,ξ_1}
       ≪ε^5N_q,S^2P+N_q,SP∑_k∈ℤ1/k^2+1
       ≪ (ε^5N_q,S^2+N_q,S)P,

where in the second-to-last step we used the fact that T is well-spaced.


We then consider the contribution of S_2. By Lemma <ref>(i) and partial summation (and the fact that P≥ x^η≥ x^ε^4), for q∈𝒬_x,ε,ε^-6, we have

    sup_χ q
    (χ)>x^ε^20sup_|t| ≤ x|∑_nΛ(n)χ(n)n^-ith(n/P)| ≪ε^10P.

On the other hand, for χ principal we use Lemma <ref> with q=1 and ε=1/log P to estimate 

    |∑_nΛ(n)χ(n)n^-ith(n/P)| ≤|∑_nΛ(n)n^-ith(n/P)|+O((log P)^2) ≪P/(log P)^0.3+ P/|t|^2+1

for |t|≤ x.

Applying (<ref>) or (<ref>)  with χ = χ_1χ̅_2 and t = t_1-t_2 for each  (χ_1,t_1),(χ_2,t_2) ∈B_q,S counted by S_2, and handling the contributions from these as in (<ref>), we find 

    S_2≪ (ε^10 N_q,S^2+N_q,S)P.

Combining the bounds on S_1 and S_2 with (<ref>) and (<ref>), we see that

    εδ P/log PN_q,S≪δ^1/2P/log P(ε^5 N_q,S+N_q,S^1/2),

and since ε≤δ and ε>0 is small enough, we deduce from this that N_q,S≪ε^-2δ^-1, which was to be shown.


 If in Proposition <ref> or <ref> we restrict to a set Q^'⊂ [1,x] of pairwise coprime moduli q, then by Lemma <ref> the sizes of the corresponding sets of exceptional q≤ x are ≪ (log x)^10ε^-6. Moreover, under GRH there are no exceptional moduli.





§ VARIANCE IN PROGRESSIONS AND SHORT INTERVALS







 §.§ Typical number of prime factors

Before proceeding to the proofs of our main theorems, we elaborate on some observations about typical moduli (in the sense of Definition <ref>) that were made in the introduction.

Let ω_[P,Q](n)  |{p| n:   p∈ [P,Q]}| denote the number of prime factors of n belonging to the interval [P,Q]. Given y≥ 1, define

    Δ(q,y)max_z≥ yω_[z,2z](q)/z/log z,

which gives the maximal relative density of prime divisors of q on a dyadic subinterval of [y,∞). Clearly, if q is y-typical in the sense of Definition <ref>, then Δ(q,y)≤ 1/50+o(1) by the prime number theorem. Note also that 0≤Δ(q,y)≪ 1 always.


Let Q≥ 1, y≥ 1. Then the number of q≤ Q that are not y-typical is ≪ Qexp(-10^-4y). Moreover, if y≥ 1000(log Q) and Q is large enough, then all q≤ Q are y-typical. 



We may assume that y is large enough. Note that by dyadic summation, if

    Δ(q,y)≤1/500,

then q is y-typical. The second claim of the lemma follows directly from this and the estimate ω(q)≤ (1+o(1))(log q)/(loglog q).

We are left with the first claim. Observe that for any fixed c>0,
by the union bound we have

    |{q≤ Q:  Δ(q,y)>c}|   ≤∑_2^j≥ y|{q≤ Q:  ω_[2^j-1,2^j](n)≥c· 2^j/5log(2^j)}|
       ≤∑_2^j≥ y∑_𝒫⊂ℙ∩ [2^j-1,2^j]
    |𝒫|≥ c· 2^j/(5log(2^j))|{q≤ Q: ∏_p∈𝒫p| q}|
       ≪∑_2^j≥ y2^2^j/(log(2^j))· Qe^-c· 2^j-1/5
       ≪ Qe^-cy/20.


Applying this with c=1/500, we obtain the claim.




From Lemma <ref>, we deduce the claims made before Theorem <ref> that all q≤ x are (x/Q)^ε^2-typical if Q=o(x/(log x)^1/ε^2) and otherwise the number of q≤ x that are not  (x/Q)^ε^2-typical is ≪exp(-10^-4(x/Q)^ε^2).




 §.§ Parseval-type bounds
 

We reduce the proofs of Corollary <ref> and Theorems <ref> and <ref> to L^2 bounds for (twisted) character sums. 

 Let 1≤ Q≤ x/10 and (log(x/Q))^-1/200≤ε≤ 1, and let fℕ→𝕌 be multiplicative. Let χ_1 be a character q minimizing the distance inf_|t|≤log x𝔻_q(f,χ(n)n^it;x). Then, with the notation of Lemma <ref>, for q∈𝒬_x,ε^6,ε^-80∩ [1,Q] we have

    ∑_χ q
    χ≠χ_1|∑_n ≤ x f(n)χ(n)|^2 ≪ε^1-3Δ(q,(x/Q)^)(ϕ(q)/qx)^2.


Moreover, assuming GRH, (<ref>) holds for all q ∈ [1,Q].


Regarding Corollary <ref>, we in fact prove the following generalisation.

 Let 𝒬'⊂ [1,Q] be any set of pairwise coprime numbers. Corollary <ref> continues to hold if the moduli p, rather than being prime, are taken to be (x/Q)^ε^2-typical elements of 𝒬', and if the right-hand side of (<ref>) is replaced with εϕ(p)(x/p)^2.


 We apply Proposition <ref> with ε^1.1 in place of ε. We have Δ(q,(x/Q)^ε^1.1)≤ 1/50+o(1) by the assumption that q is (x/Q)^ε^2-typical. Therefore, (ε^1.1)^1-3Δ(q,(x/Q)^ε^1.1)≪ε^1.1· (1-3/50+o(1))≪ε.  

By orthogonality of Dirichlet characters, we have the Parseval-type identity

    1/φ(q)∑_χ q
    χ∉Ξ|∑_n ≤ x f(n)χ(n)|^2=_a (q)|∑_n≤ x
    n≡ a(q)f(n)-∑_χ∈Ξχ(a)/ϕ(q)∑_n≤ xf(n)χ(n)|^2

for any Ξ⊂{χ q}. Each of the claimed results follows from this, as the corresponding bounds for exceptional moduli in each theorem may be deduced from Lemma <ref> (see also Remark <ref>): for any 1 ≤ Q ≤ x we have |[1,Q]∖𝒬_x,(ε^1.1)^6,(ε^1.1)^-80|≪ Qx^-ε^200, while if Q' ⊂ [1,x] is a set of pairwise coprime numbers then |𝒬'∖𝒬_x,(ε^1.1)^6,(ε^1.1)^-80|≪ (log x)^ε^-100.

Finally, assuming GRH, each of the claims holds without exception. 


Similarly, we will deduce Theorem <ref>  from the following proposition.

 Let 1≤ Q≤ h/10 and (log(h/Q))^-1/200≤ε≤ 1, and let fℕ→𝕌 be multiplicative. Let χ_1 be a character q minimizing the distance inf_|t| ≤ XD_q(f,χ(n) n^it;X), and let t_χ_1∈ [-X,X] be a point that minimizes D_q(f,χ_1(n) n^it;X). Let Z_χ_1 =ε^-10 and Z_χ=0 for χ≠χ_1. Then, with the notation of Lemma <ref>, for all q∈𝒬_X,ε^6,ε^-80∩ [1,Q] and for T=(X/h) (h/Q)^0.01ε, we have

    ∑_χq∫_|t-t_χ| ≥ Z_χ
     |t| ≤ T|∑_n≤ 3Xf(n)χ(n)n^-it|^2  dt≪ε^1-3Δ(q,(h/Q)^ε)(ϕ(q)/qX)^2.

Moreover, assuming either the GRH or that Q ≤ X^^150, the exceptional set of q vanishes.




 We use Proposition <ref> with ε^1.1 in place of ε. 









By Lemma <ref>, for x∈ [X,2X] the second term inside the square in (<ref>) is 

    χ_1(a)/ϕ(q)·1/2π∫_t_χ_1-ε^-11^t_χ_1 + ε^-11(∑_n ≤ 3X f(n)χ_1(n)n^-it) (x+h)^it-x^it/itdt+O(ε^11/2h/q).

Let us call the main term here ℳ(X;x,q,a). 



By the Cauchy–Schwarz inequality, this implies that (<ref>) is

    ≪_aq∫_X^2X|∑_x < n ≤ x+h
     n ≡ a q f(n) -ℳ(X;x,q,a)|^2 dx + ε X ϕ(q)(h/q)^2.


We will now show that the following Parseval-type bound holds: for 1 ≤ q≤ h ≤ X, we have

    _aq∫_X^2X|∑_x < n ≤ x+h
     n ≡ a q f(n) -ℳ(X;x,q,a)|^2 dx ≪max_T ≥ X/hh/Tϕ(q)∑_χq∫_|t-t_χ| ≥ Z_χ
     |t| ≤ T |F(χ,it)|^2 dt,

where F(χ,s)∑_n≤ 3Xf(n)χ(n)n^-s and Z_χ=ε^-11 if χ=χ_1 and Z_χ=0 otherwise. 

Once we have this, the case where the maximum in (<ref>) is attained with T≥ X/h· (h/Q)^0.01ε^1.1 can be bounded using Lemma <ref> as

    ≪ h(1+X/qT)ϕ(q)/qX ≤(1/h/Q + X/Th) ϕ(q)/q^2 Xh^2 ≪ϕ(q)/q^2Xh^2,

since (log h/Q)^-1/200≤ε^1.1 certainly implies (h/Q)^-0.01ε^1.1≪ε. This contribution is small enough for Theorem <ref>. If instead T∈ [X/h,X/h· (h/Q)^0.01ε^1.1],  we have h/Tϕ(q)≪h^2/ϕ(q)X, so the bound of Proposition <ref> (with ε^1.1 in place of ε) suffices.  

The proof of (<ref>) follows closely that of <cit.> (here we choose to work on the 0-line rather than on the 1-line for convenience, though). Let us write I_χ   (t_χ-Z_χ,t_χ + Z_χ], where Z_χ is as above. Recall that I_χ=∅ if χ≠χ_1. We note first of all that[Here the integral is interpreted as zero if I_χ is empty.] 

    ∑_x < n ≤ x+h
     n ≡ a q f(n) - M(X;x,q,a) 
       = ∑_χqχ(a)/ϕ(q)(∑_x < n ≤ x+h f(n)χ̅(n) - 1/2π∫_I_χ F(χ,it) (x+h)^it-x^it/it dt),

so that by orthogonality of Dirichlet characters we find

    _a q|∑_x < n ≤ x+h
     n ≡ a q f(n) - M(X;x,q,a)|^2 
       = 1/ϕ(q)∑_χq|∑_x < n ≤ x+h f(n)χ̅(n) - 1/2π i∫_I_χF(χ,it) (x+h)^it-x^it/tdt|^2.


Now, by Perron's formula (taking the line of integration Re(s) = c  0^+ since P_fχ̅ is finitely supported), whenever x,x+h are not integers, for each χ we have

    ∑_x < n ≤ x+h f(n)χ̅(n) = 1/2π i∫_-∞^∞ F(χ,it) (x+h)^it-x^it/t dt,

so that, if ℒ is the expression on the left-hand side of (<ref>), we have

    L = 1/ϕ(q)∑_χq∫_X^2X|1/2π i∫_RI_χ F(χ,it) (x+h)^it-x^it/t dt|^2 dx.




Repeating the trick at the bottom of page 22 of <cit.>, we can find some point u ∈ [-3h/X, 3h/X] for which

    L≪1/ϕ(q)∑_χq∫_X^2X|∫_RI_χ F(χ,it) x^it(1+u)^it-1/t dt|^2 dx.

The rest of the proof of (<ref>) then follows that of <cit.> almost verbatim (adding a smooth weight to the x integral, expanding the square and swapping the order of integration).






 §.§ Proof of hybrid theorem


We may of course assume in what follows that h/Q is larger than any given absolute constant and that ε>0 is smaller than any given positive constant.

We have shown that to prove Theorem <ref> it is enough to prove Proposition <ref>, i.e., that

    ∑_χq∫_|t-t_χ| ≥ Z_χ
    |t| ≤ T|F(χ,it)|^2 dt≪ε^1-3Δ(q,(h/Q)^ε)(ϕ(q)/qX)^2

for T= (X/h)(h/Q)^0.01ε, where

    F(χ,s)∑_n≤ 3Xf(n)χ(n)n^-s.


As in <cit.>, we restrict the support of F(χ,s) to integers with typical factorization. Define a “well-factorable” set 𝒮 as follows. For 1≤ Q≤ h/10, ε∈ ((logh/Q)^-1/200,1) and 2≤ j≤ J-1, set 

    P_1    = Q_1^ε,    Q_1 =  h/Q,
    
    
    P_j    = exp(j^4j(log Q_1)^j-1log P_1),    Q_j = exp(j^4j+2 (log Q_1)^j),
    
    P_J   =X^ε^2,   Q_J=X^ε,

with J ≥ 2 being chosen minimally subject to the constraint J^4J+2(log Q_1)^J > (log X)^1/2. (If J=2, only use the definitions of P_1,Q_1, P_J,Q_J.)  

Then let 

    𝒮{n≤ x: ω_[P_i,Q_i](n)≥ 1  ∀ 1 ≤ i≤ J}.

One sees that for 2≤ j≤ J the inequalities

    loglog Q_j/log P_j-1-1≤η/4j^2,  η/j^2log P_j≥ 8log Q_j-1+16log j

hold for fixed η∈ (0,1) and large enough h/Q (the j=2 case follows from the assumption log(h/Q)>ε^-100, and for the j=J case it is helpful to note that J≪loglog X and P_J-1≫exp((loglog X)^10) if J≥ 3), and thus the P_j, Q_j satisfy all the same requirements as in <cit.>. A simple sieve upper bound shows that 

    |[1,3X]∖𝒮|≪∑_j≤ JXlog P_j/log Q_j≪ Xlog P_1/log Q_1∑_j≥ 11/j^2≪ε X.


We next define

    H_1=H_J=H⌊ε^-1⌋,   H_j  j^2P_1^0.1   for    2≤ j≤ J-1;
       I_j  [⌊ H_jlog P_j⌋, H_jlog Q_j];
       Q_v,H_j(χ,s)∑_e^v/H_j≤ p<e^(v+1)/H_jf(p)χ(p)p^-s   for v ∈I_j;
       R_v,H_j(χ,s)∑_m≤ 3Xe^-v/H_jf(m)χ(m)m^-s/1+ω_[P_j,Q_j](m) for v ∈I_j.


We split the set

    E{(χ,t)∈{χ q}× [-X,X]:   |t-t_χ|≥ Z_χ,   |t|≤ T}

as E=⋃_j≤ J-1X_j∪U with

    X_1   ={(χ,t)∈E:   |Q_v,H_1(χ,it)|≤ e^(1-α_1)v/H_1  ∀ v∈I_1},
    X_j   ={(χ,t)∈E:   |Q_v,H_j(χ,it)|≤ e^(1-α_j)v/H_j  ∀ v∈I_j}∖⋃_i≤ j-1X_i,      2≤ j≤ J-1,
    U   =E∖⋃_i≤ J-1X_i,

where we take

    α_j=1/4-η(1+1/2j),  η=0.01.


We may of course write, for some (possibly empty) sets T_j,χ⊂ [-T,T],

    X_j=⋃_χ q{χ}×T_j,χ.


By Lemma <ref>, for each 1 ≤ j ≤ J-1 we have

    ∑_χ q∫_T_j,χ|∑_n ≤ 3Xf(n)χ(n)n^-it|^2 dt
       ≪ H_j logQ_j/P_j∑_v ∈I_j∑_χ q∫_T_j,χ |Q_v,H_j(χ,it)|^2|R_v,H_j(χ,it)|^2 dt
          + (ϕ(q)/qX)^2(1/H_j + 1/P_j+∏_P_j≤ p≤ Q_j
    p∤ q(1-1/p)),

the integrals here being interpreted as zero if T_j,χ = ∅. By our choices of P_j and H_j, the error terms involving 1/H_j or 1/P_j are ≪ε (ϕ(q)/q · X)^2 when summed over j≤ J-1, since log(h/Q)≥ε^-100 by assumption. After summing over j≤ J-1, the error terms involving ∏_P_j≤ p≤ Q_j
p∤ q(1-1/p) contribute

    ≪(ϕ(q)/qX)^2 ∑_j≤ J-1log P_j/log Q_j∏_p| q
    P_j≤ p≤ Q_j(1+1/p)≪(ϕ(q)/qX)^2∑_j≤ J-1ε/j^2∏_p| q
    P_j≤ p≤ Q_j(1+1/p).


In terms of the Δ(·) function defined in (<ref>), for j≤ J-1 we have

    ∏_p| q
    P_j≤ p≤ Q_j(1+1/p)   ≪exp(∑_p| q
    P_j≤ p≤ Q_j1/p)≪exp(∑_2^k∈ [P_j/2,Q_j]Δ(q,P_1)/log (2^k))
       ≪(log Q_j/log P_j)^1/log 2Δ(q,P_1)≪(j^2ε^-1)^1/log 2Δ(q,P_1).

Hence, on multiplying by ε/j^2 and summing over j≤ J-1, for Δ(q,P_1)≤ 1/3, we get a contribution of ≪ε^1-3Δ(q,P_1), which is the desired savings (the j sum converges since 2(1/3log 2-1)<-1). For Δ(q,P_1)>1/3, in turn, we simply use the triangle inequality to note that the trivial bound ≪ (ϕ(q)/q· X)^2 for (<ref>) coming from Lemma <ref> (after forgetting the condition |t-t_χ| ≥ Z_χ) is good enough.


Making use of the assumption defining X_j, we have

    H_j logQ_j/P_j∑_v ∈I_j∑_χ q∫_T_j,χ |Q_v,H_j(χ,it)|^2|R_v,H_j(χ,it)|^2 dt 
       ≪ H_j logQ_j/P_j∑_v ∈I_j e^(2-2α_j) v/H_j∑_χ q∫_T_j,χ |R_v,H_j(χ,it)|^2 dt =: E_j

It thus remains to bound E_j for 1 ≤ j ≤ J-1, as well as the contributions from the pairs (χ,t)∈U.


Case of X_1. For the pairs in X_1, we crudely extend the t-integral to [-T,T] and apply Lemma <ref> to arrive at

    E_1    ≪  H_1logQ_1/P_1∑_v ∈ℐ_1 e^(2-2α_1) v/H_1(ϕ(q)/qXe^-v/H_1 + ϕ(q)T)·ϕ(q)/qXe^-v/H_1
       ≪(ϕ(q)/qX)^2H_1log Q_1 ·∑_v ∈I_1 e^-2α_1 v/H_1
       ≪(ϕ(q)/qX)^2H_1log Q_1·1/P_1^2α_1·1/1-e^-2α_1/H_1
       ≪(ϕ(q)/qX)^2P_1^-0.1H_1^2,

where on the second line we used Xe^-v/H≥ X/Q_1≥ q T by the assumptions T=(X/h)· P_1^0.01 and Q_1 ≤ h/(QP_1^0.01). We see that the contribution of E_1 is small enough, since H_1≪ε^-1 and P_1^-0.1 = (h/Q)^-0.1ε≪ε^10.
 


Case of X_j. Let 2≤ j≤ J-1.  We partition 

    X_j = ⋃_r ∈I_j-1X_j,r
 
where X_j,r is the set of (χ,t) ∈X_j such that r is the minimal index in I_j-1 with |Q_r,H_j-1(χ,it)| > e^(1-α_j-1)r/H_j-1. Letting r_0 ∈I_j-1 and v_0 ∈I_j denote the choices of r and v, respectively, with maximal contribution, we obtain

    E_j    ≪ H_j (log Q_j) |I_j||I_j-1|
         ·∑_χ q e^(2-2α_j) v_0/H_j∫_-T^T(|Q_r_0,H_j-1(χ,it)|/e^(1-α_j-1)r_0/H_j-1)^2ℓ_j,r_0|R_v_0,H_j(χ,it)|^2 dt,

where ℓ_j,r_0⌈v_0/H_j/r_0/H_j-1⌉ > 1.

Using |I_j-1| ≤ |I_j|≪ H_j log Q_j, this becomes

    E_j    ≪(H_j log Q_j)^3 e^(2-2α_j)v_0/H_j -(2- 2α_j-1)ℓ_j,r_0r_0/H_j-1∑_χ q∫_-T^T|Q_r_0,H_j-1(χ,it)^ℓ_j,r_0 R_v_0,H_j(χ,it)|^2 dt.

We apply Lemma <ref> to obtain

    ∑_χ q∫_-T^T|Q_r_0,H_j-1(χ,it)^ℓ_j,r_0 R_v_0,H_j(χ,it)|^2 dt ≪(ϕ(q)/qXe^r_0/H_j-12^ℓ_j,r_0)^2((ℓ_j,r_0+1)!)^2.

We have ℓ_j,r_0≥v_0/H_j/r_0/H_j-1, whence using 2^ℓ(ℓ+1)!≪ℓ^ℓ we get

    E_j ≪ (H_jlog Q_j)^3 (ϕ(q)/qXe^r_0/H_j-1)^2e^2(α_j-1-α_j)v_0/H_j + 2ℓ_j,r_0logℓ_j,r_0.

Since ℓ_j,r_0≤v_0/H_j/r_0/H_j-1+1 and r_0/H_j-1≥log P_j-1-1, v_0/H_j≤log Q_j, we have

    ℓ_j,r_0logℓ_j,r_0≤v_0/H_jloglog Q_j/log P_j-1 - 1 + loglog Q_j + 1.

Thus, (<ref>) is

    ≪(ϕ(q)/qXe^r_0/H_j-1)^2H_j^3(log Q_j)^5exp((2loglog Q_j/log P_j-1-1+2(α_j-1-α_j))v_0/H_j).


By (<ref>) and the choice of the α_j, we have the inequalities

    loglog Q_j-1/log P_j-1≤η/4j^2,  α_j-1-α_j≤ -η/2j^2,  log Q_j≤ Q_j-1^1/24,

so we get

    E_j   ≪(ϕ(q)/qX)^2H_j^3 (log Q_j)^5 Q_j-1^2P_j^-η/2j^2
       ≪(ϕ(q)/qX)^2j^6P_1^0.3Q_j-1^2+5/24P_j^-η/2j^2
       ≪(ϕ(q)/qX)^2j^6 Q_j-1^3P_j^-η/2j^2.


Again by (<ref>), we have the inequality

    η/j^2log P_j≥ 8log Q_j-1+16log j,

so

    E_j≪(ϕ(q)/qX)^21/j^2Q_j-1≪(ϕ(q)/qX)^21/j^2P_1.

Summing over j gives

    ∑_2 ≤ j ≤ J-1 E_j ≪(ϕ(q)/qX)^2P_1^-1,

and this is acceptable. It remains to deal with U.
 


Case of U. Let us write 

    U=⋃_χ q{χ}×T_χ.


By Lemma <ref> and the definitions of P_J, Q_J and H  H_J, we have

    ∑_χ q∫_T_χ |F(χ,it)|^2 dt    ≪ HlogQ_J/P_J∑_v ∈I_J∑_χq∫_T_χ |Q_v,H(χ,it)|^2|R_v,H(χ,it)|^2 dt
       +(ϕ(q)/q X)^2(1/H+1/P_J+ε∏_P_J≤ p≤ Q_J
    p| q(1+1/p)).

 Since H=⌊ε^-1⌋ and ∏_P_J≤ p≤ Q_J
p| q(1+1/p)≪ε^-3Δ(q,P_1) (similarly to the X_j case), the terms on the second line of (<ref>) contribute ≪ε^1-3Δ(q,P_1)(ϕ(q)/qX)^2. Thus we have 
 
    ∑_χq∫_T_χ |F(χ,it)|^2 dt    ≪ (HlogQ_J/P_J)^2  ∑_χq∫_T_χ |Q_v_0,H(χ,it)|^2 |R_v_0,H(χ,it)|^2dt
       + ε^1-3Δ(q,P_1)(ϕ(q)/qX)^2
       ≪ H^2ε^2(log X)^2∑_χq∫_T_χ |Q_v_0,H(χ,it)|^2 |R_v_0,H(χ,it)|^2 dt
       + ε^1-3Δ(q,P_1)(ϕ(q)/qX)^2

for some v_0∈ [Hε^2 log X-1,Hεlog X], with H=⌊ε^-1⌋. 

We discretize the integral, so that the term on the right of (<ref>) is bounded by

    ≪ H^2ε^2(log X)^2∑_χ q∑_t∈T_χ'|Q_v_0,H(χ,it)|^2|R_v_0,H(χ,it)|^2

for some (possibly empty) well-spaced set 𝒯_χ'⊂𝒯_χ⊂ [-T,T]. 

Let us define the discrete version of U as

    U'=⋃_χ q{χ}×T_χ'.

We consider separately the subsets

    U_S:   ={(χ,t)∈U': |Q_v_0,H(χ,it)|≤ε^2 e^v_0/H/v_0},
    U_L:   ={(χ,t)∈U': |Q_v_0,H(χ,it)|> ε^2 e^v_0/H/v_0};

note that by the Brun–Titchmarsh inequality the trivial upper bound is |Q_v_0,H(χ,it)|≪ e^v_0/H/v_0.

We start with the 𝒰_S case. Observe that if (χ,t) ∈U_S then |Q_v',H_J-1(χ,it)| > e^(1-α_J-1)v'/H_J-1 for some v' ∈I_J-1. Applying our large values estimate, Lemma <ref>, together with the fact that qT≪ X^1+o(1), this leads to

    |U_S|≪ (qT)^2α_J-1(Q_J-1^2α_J-1+(log X)^200ε^-2)≪ X^0.49,

since α_J-1≤ 1/4-η and η=0.01. Hence, by the Halász–Montgomery inequality for twisted character sums (Lemma <ref>), we have

    ∑_(χ,t) ∈U_S |Q_v_0,H(χ,it)|^2 |R_v_0,H(χ,it)|^2≪ε^4e^2v_0/H/v_0^2∑_(χ,t) ∈𝒰_S|R_v_0,H(χ,it)|^2
       ≪ε^4e^2v_0/H/v_0^2(ϕ(q)/qXe^-v_0/H+(qT)^1/2(log(2qT))|𝒰_S|)ϕ(q)/qXe^-v_0/H
       ≪ε^4e^2v_0/H/v_0^2(ϕ(q)/qXe^-v_0/H)^2≪ H^-2· (log X)^-2(ϕ(q)/qX)^2,

since ϕ(q)/qXe^-v_0/H≫ X^0.999 and v_0≫ Hε^2log X. This bound is admissible after multiplying by H^2ε^2(log X)^2.

Now we turn to the U_L case. We recall that our modulus satisfies q∈𝒬_x,ε^6,ε^-80, 
and note that ε^7>(log X)^-1/13.

By Proposition <ref> (with →ε^2 and δ = e^1/H-1 ≍ 1/H and ε>0 small enough), for q∈𝒬_x,ε^6,ε^-80, we have |U_L|≪ε^-4H≪ε^-5. In addition, by Corollary <ref> (with ε replaced by ε' := ε^6, α and β replaced, respectively, by ε^2 and ε so that β/α = ε^-1 = (ε')^-1/6), for q∈𝒬_x,ε^6,ε^-80⊆𝒬_x,ε',(ε')^-6 we have the pointwise bound 

    sup_χ q
    χ≠χ_1sup_|t|≤ X|R_v_0(χ,it)|/(Xe^-v_0/H)≪ε'ϕ(q)/q = ε^6 ϕ(q)/q.

Hence we can bound the contribution of the pairs (χ,t) with χ≠χ_1 by

    ∑_(χ,t)∈U_L
    χ≠χ_1|Q_v_0,H(χ,it)|^2|R_v_0,H(χ,it)|^2   ≪ |U_L|e^2v_0/H/v_0^2sup_χ q
    χ≠χ_1sup_|t|≤ X|R_v_0,H(χ,it)|^2
       ≪ε^-5+12/ε^4H^2(log X)^2(ϕ(q)/qX)^2,

and this multiplied by the factor H^2ε^2(log X)^2 yields a more than sufficient bound for (<ref>).

The contribution of χ=χ_1, in turn, is bounded using Corollary <ref> in the form that

    sup_Z≤ |t-t_χ_1|≤ x|R_v_0,H(χ_1,it)|/Xe^-v_0/H≪1/√(Z)ϕ(q)/q

for Z = ε^-10≤ (log X)^1/20 and for q as before. This yields

    ∑_(χ_1,t)∈U_L|Q_v_0,H(χ_1,it)|^2|R_v_0,H(χ_1,it)|^2   ≪ |U_L|e^2v_0/H/v_0^2sup_Z ≤ |t-t_χ_1|≤ X|R_v_0,H(χ_1,it)|^2
       ≪ε^-5+10/ε^4 H^2(log X)^2(ϕ(q)/qX)^2.

This multiplied by H^2ε^2(log X)^2 produces a good enough bound, finishing the proof of Proposition <ref>, and hence that of Theorem <ref>.

 
Our task is to simplify the main term in Theorem <ref> in the case of a real-valued multiplicative fℕ→ [-1,1]. We work with the same set of moduli q∈𝒬_x,ε^6,ε^-80 as in Proposition <ref>. By the triangle inequality and Theorem <ref>, it suffices to show that

    ∫_X^2X|1/3X∑_n ≤ 3X f(n)χ̅_̅1̅(n) - (1/h∫_x^x+h v^it_χ dv) 1/3X∑_n ≤ 3X f(n)χ̅_̅1̅(n)n^-it_χ_1|^2  dx ≪ε X(ϕ(q)/q)^2.


Set Y := 3X. By the triangle inequality for pretentious distance, we have

    2𝔻_q(f,χ_1(n)n^it_χ_1;Y)≥𝔻_q(f^2,χ_1^2(n)n^2it_χ_1;Y)≥𝔻_q(1,χ_1^2(n)n^2it_χ_1;Y)-𝔻_q(f^2,1;Y).

We then split into several cases.

Case 1. Suppose first that 𝔻_q(f^2,1;Y)^2> 2log(1/ε). Applying the Cauchy–Schwarz inequality, for  
t∈{0,t_χ_1} we obtain

    |∑_n≤ Yf(n)χ_1(n)n^-it|≪(φ(q)/qY)^1/2(∑_n≤ Y 
     (n,q) = 1f(n)^2)^1/2.

By an elementary upper bound <cit.> for mean values of multiplicative functions taking values in [0,1], we have

    ∑_n≤ Y 
     (n,q) = 1f(n)^2≪ϕ(q)/qY∏_p≤ Y 
     p ∤ q(1+f(p)^2-1/p)≪ϕ(q)/q Yexp(-𝔻_q(f^2,1;Y)^2)≪ε^2ϕ(q)/qY.

Hence (<ref>) holds. 

Case 2. Suppose then that 𝔻_q(f^2,1;Y)^2≤ 2log(1/ε) and that either χ_1 is complex or |t_χ_1|≥ 2log x. Then by Lemma <ref>(ii) (with ε^6 in place of ε) from (<ref>) (with t in place of t_χ_1) we obtain

    inf_|t-t_χ_1|≤log x𝔻_q(f,χ_1(n)n^it;Y)^2≥(√(5.5· 6)-√(2)/2)^2log1/ε>4log1/ε.

By Lemma <ref> and the minimal property of t_χ_1,  
we then obtain

    max_t∈{0,t_χ_1}|∑_n≤ Yf(n)χ_1(n)n^-it|≪ε^3φ(q)/qY,

which implies (<ref>).



Case 3. Finally, suppose that 𝔻_q(f^2,1;Y)≤ 2log(1/ε) and that χ_1 is real and |t_χ_1|≤ 2log x. We may assume that 

    𝔻_q(f,χ_1(n)n^it_χ_1;Y)^2≤ 2log1/ε,

since otherwise (<ref>) holds by the minimal property of t_χ_1 and then we can conclude as before. But then by (<ref>), 

    𝔻_q(1,χ_1^2(n)n^2it_χ_1;Y)-𝔻_q(f^2,1;Y)≤(8log1/ε)^1/2,

so by the assumption on 𝔻_q(f^2,1;Y) and the fact that χ_1 is real we deduce

    𝔻_q(1,n^2it_χ_1;Y)^2≤(2^1/2+8^1/2)^2log1/ε = 18log1/ε.

By (<ref>) (and the fact that ε≥ (log X)^-1/200) this is a contradiction unless |t_χ_1|≤ε.

For |t_χ_1|≤ε, in turn, we have

    1/h(∫_x^x+h v^it_χ_1 dv) 1/Y∑_n ≤ Y f(n)χ_1(n) n^-it_χ_1= x^it_χ_1/Y∑_n ≤ Y f(n)χ_1(n)n^-it_χ_1 + O(εϕ(q)/q).

by estimating the integrand trivially. Moreover, the expression on the right is by (<ref>) and Lemma <ref> equal to

    1/Y∑_n ≤ Y f(n)χ_1(n)+ O(εϕ(q)/q)


This proves (<ref>) also in this case, and now all the cases have been dealt with.




Corollary <ref> follows quickly from Corollary <ref>. 

 We apply Corollary <ref> with f=μ. Note that the set 𝒬_X,ε in Corollary <ref> contains all positive integers ≤ X^ε^200. Now, let c_0 be a small enough absolute constant, and let m≤ X^ε^200 be a modulus for which L(s,χ^*) for some real character χ^* m has a real zero >1-c_0/log(X^ε^200) (if it exists). By the Landau–Page theorem and Siegel's theorem, all such m are multiples of a single number q_0≫ (log X)^A (if no such m exists, set q_0=1).

It then suffices to show that for q not divisible by q_0 we have

    |∑_n≤ 3Xμ(n)χ(n)|≪ε^1/2φ(q)/qX

for all characters χ q. We may assume that χ is non-principal, as otherwise the claim follows from the prime number theorem (with e.g. de la Vallée-Poussin error term). By Lemma <ref>, we have (<ref>) provided that

    inf_|t|≤log x𝔻_q(μ,χ(n)n^it;3X)^2≥log(1/ε),

say. By Mertens's theorem, for |t|≤log x we can lower bound

    𝔻_q(μ,χ(n)n^it;3X)^2≥∑_X^ε^10≤ p≤ X1+Re(χ(p)p^it)/p= 10log1/ε+Re(∑_X^ε^10≤ p≤ Xχ(p)p^it/p)+O(1).


 
By Lemma <ref> and Remark <ref>, for any q^1/ε^100≤ y≤ X and q not divisible by q_0 we have

    |∑_n≤ yΛ(n)χ(n)n^it|≪ε^100(log^31/ε)y+y/(log y)^0.3.

Using (<ref>) and partial summation, we conclude that the left-hand side of (<ref>) is ≥ 9log(1/ε), say. We thus obtain (<ref>), and hence (<ref>).





 §.§ The case of arithmetic progressions


In this subsection we prove Theorem <ref> and Theorem <ref>. As shown in Section <ref>, it suffices to prove Proposition <ref>. 

 We may plainly assume that x is larger than any fixed constant and that ε>0 is smaller than any fixed positive constant. 

The proof follows the same lines as that of Proposition <ref>, and we merely highlight the main differences. For x ≥ 10, 1 ≤ Q ≤ x/100 and (log(x/Q))^-1/200≤ε≤ 1 we set

    P_1    = Q_1^ε,    Q_1 =  x/Q
    
    P_j    = exp(j^4j(log Q_1)^j-1log P_1),    Q_j = exp(j^4j+2(log Q_1)^j),    2 ≤ j ≤ J-1 
    
    P_J    = x^ε^2,    Q_J = x^ε,

where J ≥ 2 is the smallest integer with J^4J+2(log Q_1)^J > (log x)^1/2. (If J = 2 then only define P_1,Q_1,P_J,Q_J as above.)


In analogy to the definitions made in the proof of Proposition <ref>, we also define

    F(χ)∑_n≤ 3xf(n)χ(n),
       H_1 = H_J = H ε^-1,    H_j    j^2P^0.1 for  2 ≤ j ≤ J-1, 
       I_j  [⌊ H_jlog P_j⌋, H_jlog Q_j]  for  2 ≤ j ≤ J-1, 
       Q_v,H_j(χ)∑_e^v/H_j≤ p<e^(v+1)/H_jf(p)χ(p),
       R_v,H_j(χ)∑_m≤ 3xe^-v/H_jf(m)χ(m)/1+ω_[P_j,Q_j](m) for  v ∈I_j,  1 ≤ j ≤ J.


Finally, for q≥ 1 and 2≤ j≤ J-1, let us write

    X_1:   ={χ≠χ_1 q:   |Q_v,H_1(χ)| ≤ e^(1-α_1) v/H_1  ∀  v∈I_1},
    X_j:   ={χ≠χ_1 q:   |Q_v,H_j(χ)| ≤ e^(1-α_j) v/H_j  ∀  v∈I_j}∖⋃_i≤ j-1X_i,     2≤ j≤ J-1
    U:   ={χ≠χ_1 q}∖⋃_i≤ J-1X_i,

where, as before, we put

    α_j = 1/4 - η(1+1/2j),  η=0.01

for each 1 ≤ j ≤ J-1. Similarly to the proof of Proposition <ref>, the proof of Proposition <ref> (and hence of Theorem <ref>) splits into the cases χ∈𝒳_1,…, 𝒳_J-1, 𝒰, depending on which character sum is small or large. 

The introduction of the typical factorizations corresponding to the set 𝒮 is handled, as above, using Lemma <ref> (more precisely, (<ref>) there), which gives

    ∑_χ∈𝒳_j|F(χ)|^2≪ H_jlogQ_j/P_j∑_v∈ I_j∑_χ∈X_j|Q_v,H_j(χ)R_v,H_j(χ)|^2 +(ϕ(q)/q x)^2(1/H_j+1/P_j+∏_P_j≤ p≤ Q_j
    p∤ q(1-1/p)).

When summed over 1 ≤ j ≤ J-1, the error terms are small, analogously to the proof of Theorem <ref>.

Letting E_j denote the main term on the right of (<ref>), we apply the same arguments, but with Lemma <ref> in place of Lemma <ref> for j = 1, and for 2 ≤ j ≤ J-1 we use the second statement of Lemma <ref>, rather than the first. In this way we obtain

    E_1    ≪(ϕ(q)/qx)^2 H_1^2P_1^-0.1≪ε(ϕ(q)/qx)^2 
    ∑_2 ≤ j ≤ J-1 E_j    ≪(ϕ(q)/qx)^2 ∑_2 ≤ j ≤ J-11/j^2Q_j-1≪(ϕ(q)/qx)^2 P_1^-1,

which is sufficient. 


In the case of U, we apply Lemma <ref> once again with the choices P_J and Q_J. As above, we find a v_0 ∈I_J such that

    ∑_χ∈U |F(χ)|^2 ≪ (Hlog Q_J)^2 ∑_χ∈U |Q_v_0,H(χ)|^2|R_v_0,H(χ)|^2 + ε^1-3Δ(q,P_1)(ϕ(q)/qx)^2,

estimating the error term as for the sets X_j, but invoking the specific choices of H_J, P_J and Q_J. 

As in the proof of Proposition <ref>, we split U further into the subsets

    U_S    {χ≠χ_1 : |Q_v_0,H(χ)| ≤ε^2e^v_0/H/v_0}∩U
    U_L    {χ≠χ_1 : |Q_v_0,H(χ)| > ε^2e^v_0/H/v_0}∩U.

We combine Lemma <ref> (with T = {0} this time) with Lemma <ref> (wherein E consists of points (χ,0)), and argue as in the proof of Proposition <ref> to obtain that

    ∑_χ∈U_S |Q_v_0,H(χ)|^2|R_v_0,H(χ)|^2 ≪ (H log x)^-2(ϕ(q)/qx)^2,

which, when multiplied by (Hlog Q_J)^2 ≪ε^2 (Hlog x)^2 yields an acceptable bound. 

We treat the U_L case in essentially the same way as in the proof of Proposition <ref>, and in fact the claim is simpler, as it suffices to combine Proposition <ref> (with the same parameter choices as in the previous proof) with Corollary <ref> (taking Remark <ref> into account).
 





§ THE CASE OF SMOOTH MODULI




In this section, we prove Theorem <ref> on the variance of multiplicative functions in arithmetic progressions to all smooth moduli. A key additional ingredient compared to the proof of Corollary <ref> is the following estimate for short sums of Dirichlet characters with smooth conductor.


Let q,N≥ 1 with P^+(q)≤ N^0.001 and N≥ q^C/(loglog q) where C>0 is a large absolute constant. Then, uniformly for any non-principal character χ q and any M≥ 1,

    |∑_M≤ n≤ M+Nχ(n)|≪ Nexp(-1/4√(log N)).




We may assume that q, and thus N, is larger than any fixed constant, since the claim is immediate otherwise. We note moreover that for N≥ q, the estimate (<ref>) follows directly from the Pólya–Vinogradov inequality, and thus we can assume that N<q.

The result (<ref>) holds for primitive χ q (in a wider range than stated above and with exp(-√(log N)) in place of exp(-1/4√(log N))) by a result of Chang <cit.>. Indeed, Chang's estimate holds in the regime log N>(log q)^1-c+C'log(2log q/log q')log q'/log qlog q/loglog q for some c,C'>0 and with q'=∏_p| qp, so as ulog2/u≤ 1 for u≤ 1 the range in Chang's result contains the range N>q^2C'/loglog q. 

Let now χ q be a non-principal character induced by a primitive character χ'q' with q'| q, so that χ(n) = χ'(n)1_(n,q) = 1. By Möbius inversion,

    ∑_M≤ n≤ M+Nχ(n)   =∑_d| qμ(d)χ'(d)∑_M/d≤ m≤ (M+N)/dχ'(m).

Note that in our range √(N)≥ q^0.5C/(loglog q) and √(N)τ(q)≪ N^0.9, thus taking C=10C' and using Chang's strengthening of (<ref>) for the primitive character χ'q', we arrive at

    ∑_M≤ n≤ M+Nχ(n)   ≪∑_d| q
    d≤√(N)|∑_M/d≤ m≤ (M+N)/dχ'(m) |+∑_d| q
    d>√(N)(N/d+1)
       ≪  Nexp(-1/2√(log N))∑_d| q1/d+√(N)τ(q)
       ≪ Nexp(-(1/2+o(1))√(log N)),

and the result follows for large enough N.




Lemma <ref> below, which uses Lemma <ref> as an input, allows us to improve on Proposition <ref> for smooth moduli. It provides good upper bounds for the frequency of large character sums q over primes without any exceptional smooth q.


 Let q≥ P≥ 1 be integers with  P^+(q)≤ P^1/10000. Suppose also that P > q^1/(loglog q)^0.9. Then for 1≥δ≥exp(-(log P)^0.49) and V≥exp(-(log P)^0.49) and for any complex numbers |a_p|≤ 1, we have 

    |{χ q:  |∑_P≤ p≤ (1+δ)Pa_pχ(p)|≥ Vδ P/log P}|≪ (CV^-1)^6log (qP)/log P,

with the implied constant and C>1 being absolute.



 We begin by noting that, under our assumptions, Lemma <ref> implies 

    ∑_n∈ Iχ(n)≪δ Pexp(-1/10√(log P))

whenever χ q is non-principal and I is an interval of length |I| ∈ [P^0.2,P].

Let R be the quantity on the left-hand side of (<ref>). For any k∈ℕ we have by Chebyshev's inequality

    R   ≪(log P/δ P)^2kV^-2k∑_χq|∑_P≤ p≤ (1+δ)Pa_pχ(p)|^2k
       = (log P/δ P)^2kV^-2k∑_P≤ p_1,…, p_2k≤ (1+δ)Pa_p_1⋯ a_p_ka_p_k+1⋯a_p_2k∑_χqχ(p_1⋯ p_k)χ̅(p_k+1⋯ p_2k)
       ≤(log P/δ P)^2kV^-2kφ(q)∑_P≤ p_1,…, p_2k≤ (1+δ)P
    (p_1⋯ p_2k,q)=11_p_1⋯ p_k≡ p_k+1⋯ p_2kq.

We pick k=⌊3log (qP)/log P⌋, so that 3≤ k≪ (loglog q)^0.9. 

Let ν(n) be the sieve majorant coming from the linear sieve with sifting level D=P^ρ and sifting parameter z=P^ρ^2, where ρ>0 is a small enough absolute constant (say ρ=1/100). The sieve weight takes the form

    ν(n)=∑_d| n
    d≤ P^ρλ_d

for some λ_d∈ [-1,1]. Then R is bounded by

    R   ≪(log P/δ P)^2kV^-2kφ(q)∑_P≤ n_1,…,n_2k≤ (1+δ) P
    (n_1⋯ n_2k,q)=1ν(n_1)⋯ν(n_2k)1_n_1⋯ n_k≡ n_k+1⋯ n_2k q
       =(log P/δ P)^2kV^-2k∑_χq|∑_P≤ n≤ (1+δ)Pν(n)χ(n)|^2k.


The contribution of the principal character to the χ sum is

    ≤(∑_P≤ n≤ (1+δ)Pν(n))^2k≪(2ρ^-2δ P/log P)^2k

by the linear sieve, and this contribution is admissible by setting C=2ρ^-2 in the lemma.
Consider next when χ is non-principal. Exchanging the order of summation and applying (<ref>), we have the upper bound

    ∑_P≤ n≤ (1+δ)Pν(n)χ(n)   =∑_d≤ P^ρλ_d χ(d) ∑_P/d≤ m≤ (1+δ)P/dχ(m) ≪ P(log P)exp(-1/10√(log P))
       ≪ Pexp(-1/15√(log P)).

Hence the contribution of the non-principal characters to the χ sum in (<ref>) is bounded by

    ≪ P^2exp(-2/15√(log P))∑_χq|∑_P≤ n≤ (1+δ)Pν(n)χ(n)|^2(k-1),

and expanding out the moment again, this is

    ≪  P^2exp(-√(log P)/15) ϕ(q)∑_P≤ n_1,…,n_2(k-1)≤ (1+δ) P
    (n_1⋯ n_2(k-1),q)=1ν(n_1)⋯ν(n_2(k-1))1_n_1⋯ n_k-1≡ n_k⋯ n_2(k-1) q
       ≪ P^2exp(-√(log P)/15)ϕ(q) ∑_P≤ n_1,…,n_2(k-1)≤ (1+δ) P
    (n_1⋯ n_2(k-1),q)=1τ(n_1)⋯τ(n_2(k-1))1_n_1⋯ n_k-1≡ n_k⋯ n_2(k-1) q.


Merging variables, this becomes

    ≪ P^2exp(-√(log P)/15)ϕ(q) ∑_m_1,m_2≤ (2P)^k-1
    m_1≡ m_2 q
    (m_1m_2,q)=1τ_2(k-1)(m_1)τ_2(k-1)(m_2)
       = P^2exp(-√(log P)/15)ϕ(q)∑_m_1≤ (2P)^k-1
    (m_1,q)=1τ_2(k-1)(m_1)∑_m_2≤ (2P)^k-1
    m_2≡ m_1 qτ_2(k-1)(m_2).


Shiu's bound <cit.> shows that the inner sum is ≪(2P)^k-1/φ(q)(log (2P)^k)^2(k-1)-1, as q≤ (2P)^0.9(k-1) by our choice of k. Thus the whole expression above is

    ≪ P^2kexp(-1/20√(log P)),

since (klog P)^2k≪exp((log P)^0.01). When we multiply this contribution by (log P/(δ P))^2kV^-2k and recall the assumptions δ, V≥exp(-(log P)^0.49) and the fact that k≪loglog P, we see that

    R   ≪ (CV^-1)^2k+(δ^-1V^-1)^2kexp(-1/30√(log P))
       ≪ (CV^-1)^2k+1,

which, recalling our choice of k, is what was to be shown.


Our next lemma improves on Proposition <ref> for smooth moduli (apart from the t-aspect).

 Let x≥ 10, κ>0 and 2≤ P<Q≤ x. Then for all q≤ x satisfying P^+(q)≤ q^κ^100 and for any multiplicative function fℕ→𝕌, if χ_1 q is defined as in Theorem <ref> then 

    sup_χ q
    χ≠χ_1sup_y∈ [x^κ,x]|1/y∑_n≤ y 
     (n,[P,Q]) = 1f(n)χ̅(n)|≪κ(log Q/log P)ϕ(q)/q.





We may assume in what follows that κ>0 is small enough (adjusting the implied constant  if necessary). We may also assume q^κ^100≥ 2, so κ≫ (log q)^-0.01. 

Note that n ↦ 1_(n,[P,Q]) = 1 is multiplicative, and that for any g_1,g_2NU and any y≥ 2 we have

    D_q(g_1 1_(·,[P,Q]) = 1, g_2;y)^2 ≥D_q(g_1,g_2;y)^2 - ∑_P ≤ p ≤ Q1/p = D_q(g_1,g_2;y)^2 - log(log Q/log P) + O(1).

Hence, following the beginning of the proof of Proposition <ref> almost verbatim, we obtain the result once we prove that

    sup_|t|≤ (log q)^0.02𝔻_q(ξ,n^it;x^κ)^2≥ 5.5log1/κ + log fracqϕ(q) + O(1)

for all non-principal characters ξ q.

From Lemma <ref>, it follows that

    𝔻(ξ,n^it;x^κ)^2≥loglog x^κ-log |L(σ+it,ξ)|-O(1),

where σ=1+1/(log x^κ), so it suffices to show that

    sup_|t|≤ (log q)^0.02|L(σ+it,ξ)|≪κ^6.5ϕ(q)/qlog q

for all q≤ x satisfying P^+(q)≤ q^κ^100. By partial summation and the Pólya–Vinogradov theorem,

    L(σ+it,ξ)=∑_n≤ q(|t|+1)ξ(n)/n^σ+it+O(1).


Let q'=q^10000κ^100. Then 

    |L(σ+it,ξ)|≪ϕ(q)/qlog q'+  |∑_q'≤ n≤ q(|t|+1)ξ(n)/n^σ+it|+1.

The first term on the right-hand side is acceptable. For the second term, we apply partial summation to write it  as

    ∑_q'≤ n≤ q(|t|+1)ξ(n)/n^σ+it=S(q',q(|t|+1))/(q(|t|+1))^σ+it + (σ+it)∫_q'^q(|t|+1)S(q',u)u^-1-σ-it  du,

where

    S(M,N)∑_M≤ n≤ Nξ(n).


We are now in a position to apply Lemma <ref> (which is applicable, as P^+(q)≤ q^κ^100≤ (q')^0.0001). The triangle inequality and Lemma <ref> imply that whenever q' < u ≤ 2q'  we have

    |S(q',u)| ≤ |S(q'/2,q')| + |S(q'/2,u)| ≪ u exp(-1/4√(log (q'/2))) ≪ u exp(-1/10√(log u)),

a bound that continues to hold for all u ≥ 2q' directly from Lemma <ref>. 
Thus, we may bound the right-hand side of (<ref>) by  

    ≪ 1+(1+|t|)∫_q'^∞1/uexp(1/10√(log u))  du≪ 1≪κ^10ϕ(q)/qlog q,

 since ϕ(q)/q≫ 1/loglog q and κ≥ (log q)^-0.01. This concludes the proof. 


From the previous lemma, we derive the following variant of Corollary <ref> for smooth moduli q, again without exceptions.
 Let x≥ R≥ 10, κ∈ ((log x)^-1/100,1), and 10≤ P≤ Q/2≤ x. Let the twisted character sum R(χ,s), multiplicative function fℕ→𝕌 and character χ_1 q be defined as in Corollary <ref>. Then for 2≤ q≤ x satisfying P^+(q)≤ q^κ^100 we have

    sup_χ q
    χ≠χ_1sup_R∈ [x^1/2,x]1/R|R(χ,0)|≪κ(log x/log P)^2ϕ(q)/q.



 
Applying the hyperbola method, 
we see that

    |R(χ,0)|   ≪|∑_m_1≤ Rx^-κ
    p| m_1⟹ p∈ [P,Q]f(m_1)χ(m_1)/1+ω_[P,Q](m_1)∑_R/m_1≤ m_2 ≤ 2R/m_1 
     (m_2,[P,Q]) = 1f(m_2)χ(m_2)|
       +∑_m_2≤ 2x^κ
    (m_2,[P,Q])=1
    (m_2,q)=1∑_Rx^-κ<m_1≤ 2R/m_2
    p| m_1⟹ p∈ [P,Q]1.

Since R/m_1≥ x^κ holds in the first sum on the right, we can apply Lemma <ref> to bound this sum by

    ≪κlog Q/log Pϕ(q)/q(∑_m_1≤ x
    p| m_1⟹ p∈ [P,Q]R/m_1)
       ≪κlog Q/log Pϕ(q)/q R∏_P≤ p≤ Q(1-1/p)^-1
       ≪κϕ(q)/q(log Q/log P)^2R.

The second sum on the right of (<ref>), in turn, is bounded using Selberg's sieve by

    ≤∑_m_2≤ 2x^κ
    (m_2,[P,Q])=1
    (m_2,q)=1∑_m_1≤ 2R/m_2
     P^-(m_1) > P 1 ≪∑_m_2≤ 2x^κ
    (m_2,q)=1R/m_2log P≪κlog x/log Pϕ(q)/qR,

using the fact that p|q ⇒ p ≤ q^κ^100 < 2x^κ in the final step.


  Inspecting the proof of Theorem <ref>, the result of that theorem holds for any modulus q≤ x satisfying, for H=⌊ε^-1⌋, the bounds  

    sup_P∈ [x^ε^2,x^ε]|{χ q:  |∑_P≤ p≤ Pe^1/Hf(p)χ(p)|≥ε^2/10 ·P/Hlog P}|≪ K(ε),
 
and for P = x^ε^2 and Q = x^ε,

    sup_χ q
    χ≠χ_1|1/Rsup_R∈ [x^1/2,x]∑_R≤ m≤ 2Rf(m)χ(m)/1+ω_[P,Q](m)|≪ε/K(ε)^1/2φ(q)/q

for some function K(ε)≥ 1. Indeed, it is only the U_L case of the proof of Theorem <ref> where we need to assume something about the modulus q, and the assumptions that we need there are precisely a large values estimate of the form (<ref>) together with a pointwise bound of the type (<ref>).

We then establish (<ref>) and (<ref>). Let P^+(q)≤ q^ε' with ε'=exp(-ε^-3). Lemma <ref> (where we take V=ε^2/10 and δ=e^1/H-1) readily provides (<ref>) with K(ε)=ε^-100ε^-2 (assuming as we may that ε>0 is smaller than any fixed constant).

Corollary <ref> in turn gives (<ref>) (with the same K(ε)=ε^-100ε^-2 as above) when we take κ=ε^5K(ε)^-1/2 there, which we can do since P^+(q)≤ q^ε'≤ q^κ^100. This completes the proof.






§ ALL MODULI IN THE SQUARE-ROOT RANGE







 §.§ Preliminary lemmas


For the proof of Theorem <ref>, we need a few estimates concerning smooth and rough numbers to bound the error terms arising from exhibiting good factorizations for smooth numbers in Lemmas <ref> and <ref>.



 
Let c ∈ (0,1). Let 1 ≤ Y ≤ X and 1≤ q ≤ X^1-c, and let X^-c/2≤δ≤ 1. Then for any reduced residue class a modulo q,

    ∑_(1-δ)X < m ≤ X
     P^-(m) > Y 
     m ≡ a q 1 ≪ c^-1δ X/ϕ(q)log Y.



This follows immediately from Selberg's sieve.


Given 1 ≤ q,Y ≤ X, define the counting function of Y-smooth numbers up to X that are coprime to q as

    Ψ_q(X,Y)  |{n ≤ X : P^+(n) ≤ Y, (n,q) = 1}|.

We have the following estimate for Ψ_q(X,Y) in short intervals. 

 
Let 10 ≤ Y ≤ X and set u log X/log Y. Assume that Y ≥exp((log X)^0.99) and exp(-(log X)^0.01) ≤δ≤ 1. Finally, let 1 ≤ q ≤ e^√(Y). Then

    Ψ_q((1+δ) X,Y) -Ψ_q(X,Y) ≪ρ(u)ϕ(q)/qδ X.




By the sieve of Eratosthenes, we have 

    Ψ_q((1+δ) X,Y) -Ψ_q(X,Y)=∑_d| q
    P^+(d)≤ Yμ(d)∑_X/d≤ m≤ (1+δ)X/d
    P^+(m)≤ Y1

Let S_1 and S_2 be parts of the sum with d≤exp(10(log X)^1/2) and d>exp(10(log X)^1/2), respectively. For estimating S_2, we crudely remove the smoothness condition from the m and d sums, and estimate the remaining sum using 1/d≤exp(-5(log X)^1/2)/√(d) to obtain

    S_2   ≪∑_d| q
    d>exp(10(log X)^1/2)δ X/d≪δ Xexp(-5(log X)^1/2)∏_p| q(1-1/√(p))^-1
       ≪δ Xexp(-5(log X)^1/2)exp(3√(ω(q)))

and using ω(q)=o(log q) this is certainly ≪δ X ρ(u)ϕ(q)/qexp(-1/2(log X)^1/2) by u≤ (log X)^0.01 and the well-known estimate ρ(u)=u^-(1+o(1))u.

For the S_1 sum, we instead apply <cit.> (noting that its hypothesis δ X/d≥ XY^-5/12 is satisfied) so that we obtain

    S_1   =∑_d| q
    d≤exp(10(log X)^1/2)
    P^+(d)≤ Y(μ(d)δ X/dρ(u-log d/log Y)(1+O(log(u+1)/log Y))) 
       =∑_d| q
    P^+(d)≤ Y(μ(d)δ X/dρ(u)(1+O(log(u+1)/log Y))) 
       + O(δ Xexp(3√(ω(q))-5(log X)^1/2) + δ X∑_d| q
    d≤exp(10(log X)^1/2)
    P^+(d)≤ Y|ρ(u)-ρ(u-log d/log Y)|/d),

where we used the same bound as in the S_2 case to extend the d sum to all d| q, P^+(d)≤ Y. 

As with S_2, the first error term in (<ref>) is ≪δ X ρ(u)ϕ(q)/qexp(-1/2(log X)^1/2).
To treat the second, we apply the mean value theorem and the identity uρ'(u) = -ρ(u-1), for d≤exp(10(log X)^1/2) to obtain 

    |ρ(u-log d/log Y) - ρ(u)|≤log d/log Ymax_u-10(log X)^1/2/log Y ≤ v ≤ uρ(v-1)/v≪ρ(u-2)(log X)^1/2/log Y,

and therefore the expression for S_1 simplifies to

    S_1=δρ(u)X(∏_p| q
    p≤ Y(1-1/p) +O(∑_d| q1/d(log(u+1)/log Y+ρ(u-2)/ρ(u)(log X)^-0.3))).


 Now the result follows by recalling that u≤ (log X)^0.01 and noting that the product over p| q is ≍ϕ(q)/q as Y≥log^2 q and that ρ(u-2)≪ u^3ρ(u) by <cit.>.
 


Let 1 ≤ Y ≤ X_1 < X_2 ≤ e^√(Y) and 1≤ q≤ X_2, with Y ≥exp((log X_1)^0.99). Then

    ∑_X_1 < n ≤ X_2
     P^+(n) ≤ Y
    (n,q)=11/n≪ϕ(q)/qρ(u_1) log2X_2/X_1,

where u_1  (log X_1)/log Y. 



Decompose the interval (X_1,X_2] dyadically. Making use of Lemma <ref>, we find

    ∑_X_1 < n ≤ 2X_2
     P^+(n) ≤ Y
    (n,q)=11/n≪∑_X_1 < 2^j ≤ 4X_2 2^-j∑_2^j-1<n≤ 2^j
     P^+(n) ≤ Y
    (n,q)=1 1 ≪ϕ(q)/qρ(u_1) ∑_X_1 < 2^j ≤ 4X_2 1 ≪ϕ(q)/qρ(u_1) log2X_2/X_1,

as claimed.






 §.§ Decoupling of variables


The proof of Theorem <ref> is based on obtaining bilinear structure in the sum, coming from the fact that the summation may be restricted to smooth numbers. Certainly any x^η-smooth number n∈ [x^1-η,x] can be written as n=dm with d,m∈ [x^1/2-η,x^1/2+η], but a typical smooth number has a lot of representations of the above form, and therefore it appears nontrivial to decouple the d and m variables just from this. The following simple lemma however provides a more specific factorization that does allow the decoupling of our variables. 


Let x≥ 4, and let n∈ [x^1/2,x] be an integer. Then n can be written uniquely as dm with d∈ [x^1/2/P^-(m),x^1/2) and P^+(d)≤ P^-(m). 



Let n=p_1p_2⋯ p_k, where p_1≤ p_2≤⋯≤ p_k are primes. Let r≥ 1 be the smallest index for which p_1⋯ p_r≥ x^1/2. Then d=p_1⋯ p_r-1, m=p_r⋯ p_k works. We still need to show that this is the only possible choice of d and m.


Let d and m be as in the lemma. Since dm=p_1⋯ p_k and P^+(d)≤ P^-(m), there exists r≥ 1 such that d=p_1⋯ p_r-1, m=p_r⋯ p_k, and by the condition on the size of d we must have p_1⋯ p_r-1<x^1/2, p_1⋯ p_r-1≥ x^1/2/p_r. There is exactly one suitable r, namely the smallest r with p_1⋯ p_r≥ x^1/2.


We need to be able to control the size of the P^-(m) variable, since if it is very small then so is P^+(d), leading to character sums over very sparse sets. The next lemma says that for typical n≤ x the corresponding P^-(m) is reasonably large, even if n is restricted to an arithmetic progression.

In what follows, set

    θ_jη(1-ε^2)^j  for all   j≥ 0,

and let 

    J⌈ε^-2loglog (1/ε)⌉

so that for small ε>0 we have

    θ_J ≍_η1/log1/ε  and  ρ(1/(3θ_J))≪ (3θ_J)^1/(6θ_J)≪ε^100.

We have J≤ 2ε^-2loglog (1/ε) as long as ε>0 is small enough in terms of η.



Let x≥ 10, η∈ (0,1/10) and (log x)^-1/100≤ε≤ 1. Let θ_j be given by (<ref>) and J given by (<ref>), and define

    𝒮_J⋃_0≤ j≤ J{n≤ x:   n=dm,   d∈ (x^1/2-θ_j+1,x^1/2),  P^+(d)≤ x^θ_j+1,   P^-(m)∈ (x^θ_j+1,x^θ_j]}.
 
Let q≤ x^1/2-100η. Then for (a,q)=1 we have

    ∑_n≤ x
    n≡ a q
    P^+(n)≤ x^η(1-1_𝒮_J(n))≪_ηεx/q.




We may assume that ε is smaller than any fixed function of η. In what follows, let n≤ x, P^+(n)≤ x^η and n≡ a  q with (a,q)=1.

Owing to Lemma <ref>, we may write any n as above uniquely in the form n=dm with P^+(d)≤ P^-(m) and d∈ [x^1/2/P^-(m),x^1/2). Let us further denote by 𝒯_j the set of n as above for which P^-(m)∈ (x^θ_j+1,x^θ_j], so that every n belongs to a unique set 𝒯_j with j≥ 0. We claim that n∈S_J unless one of the following holds:

(i) n has a divisor d≥ x^1/2-η with P^+(d)≤ x^θ_J+1 and P^-(n/d)≥ P^+(d);

(ii) For some 0 ≤ j ≤ J there exist two (not necessarily distinct) primes p_1,p_2>x^θ_j+1 with p_1p_2| n and 1≤ p_1/p_2≤ x^ε^2;

(iii) For some 0≤ j≤ J, we can write n=md with d∈ [x^1/2-θ_j,x^1/2-θ_j+1], P^+(d)≤ x^θ_j,  P^-(m)∈ (x^θ_j+1,x^θ_j].

Indeed, if n≤ x, P^+(n)≤ x^η and none of (i), (ii), (iii) holds, then letting j be the index for which n∈𝒯_j, we have j≤ J (by negation of (i)) and in the factorization n=dm of n we have the conditions P^-(m)∈ (x^θ_j+1,x^θ_j], P^+(d)≤ x^θ_j+1 (by negation of (ii) and the fact that θ_j-θ_j+1≤ε^2), and d∈ (x^1/2-θ_j+1,x^1/2] (by negation of (iii)), so that n∈𝒮_J.

Applying Lemma <ref>, the contribution of (i) is 

    ≪∑_x^1/2-η≤ d≤ x^1/2
    P^+(d)≤ x^θ_J+1
    (d,q)=1∑_m≤ x/d
    P^-(m)≥ P^+(d)
    m≡ ad^-1 q1   ≪η^-1∑_x^1/2-η≤ d≤ x^1/2
    P^+(d)≤ x^θ_J+1
    (d,q)=1x/d/ϕ(q)(log P^+(d))
       ≪_η∑_k≥log(1/θ_J+1)-1e^-k∑_x^1/2-η≤ d≤ x^1/2
    P^+(d)∈ [x^e^-k-1, x^e^-k]
    (d,q)=11/dlog x·x/ϕ(q).

Set u_0(log x)^0.01. The contribution of the terms with e^k≤ u_0 can be bounded using Lemma <ref>, and ρ(u)≪ u^-u (see <cit.>), yielding a contribution of

    ≪∑_k≥log(1/θ_J+1)-1e^-kρ(e^k/3)x/q≪∑_k≥log(1/θ_J+1)-1e^-(k-log 3)e^-k/3≪ε^100x/q,

since θ_J+1≫_η 1/log(1/ε). The remaining terms with e^k>u_0 can be estimated trivially using Corollary <ref>, giving 

    ≪η^-1∑_k≥ 0.01loglog x e^-kρ(u_0/3)x/q≪_ηεx/q.



Denoting M=θ_J+1ε^-2 and applying the prime number theorem, the contribution of (ii) in turn is bounded by

    ∑_M≤ k≤ε^-2∑_p_1,p_2∈ [x^(k-1)ε^2,x^(k+1)ε^2]∑_n≤ x
    n≡ a  q
    p_1p_2| n1   ≪x/q∑_M≤ k≤ε^-2(∑_p∈ [x^(k-1)ε^2,x^(k+1)ε^2]1/p)^2
       ≪x/q∑_M≤ k≤ε^-2(log(k+1/k-1)+(log x)^-100)^2
       ≪x/q∑_M≤ k≤ε^-2(1/k^2+(log x)^-100)
       ≪x/qM,

and by the definition of M and the fact that θ_J+1≪_η 1/log(1/ε), this is ≪_ηεx/q. 

Lastly, by Lemma <ref> and Corollary <ref>, for any fixed 0≤ j≤ J, the contribution of (iii) is

    ∑_x^1/2-θ_j≤ r≤ x^1/2-θ_j+1
    P^+(r)≤ x^θ_j
    (r,q)=1∑_s≤ x/r
    P^-(s)∈ [x^θ_j+1,x^θ_j]
    s≡ ar^-1 q1 
    ≤∑_x^1/2-θ_j≤ r≤ x^1/2-θ_j+1
    P^+(r)≤ x^θ_j
    (r,q)=1∑_p∈ [x^θ_j+1,x^θ_j]
    p∤ q∑_s'≤ x/(pr)
    P^-(s')≥ x^θ_j+1
    s'≡ a(pr)^-1 q1
       ≪η^-1∑_x^1/2-θ_j≤ r≤ x^1/2-θ_j+1
    P^+(r)≤ x^θ_j
    (r,q)=1∑_p∈ [x^θ_j+1,x^θ_j]x/(pr)/ϕ(q)θ_j+1(log x)
       ≪_η∑_x^1/2-θ_j≤ r≤ x^1/2-θ_j+1
    P^+(r)≤ x^θ_j
    (r,q)=1x/ϕ(q)rθ_j+1(log x)(logθ_j/θ_j+1+(log x)^-100)
       ≪_ηθ_j-θ_j+1/θ_j+1logθ_j/θ_j+1ρ(1/(3θ_j))x/q+x/q(log x)^99.

Here the second term is certainly small enough. Using ρ(u)≪ u^-2, log(1+v)≪ v and formulas (<ref>) and (<ref>), the first term summed over 0≤ j≤ J is crudely bounded by

    ≪_η∑_0≤ j≤ J(θ_j-θ_j+1)^2x/q≪_ηJε^4 x/q≪_ηε^1.9x/q.

Therefore we have proved the assertion of the lemma.


We further wish to split the d and m variables into short intervals to dispose of the cross-condition dm≤ x on their product. This is achieved in the following lemma.


Let x≥ 10, η∈ (0,1/10) and (log x)^-1/100≤≤ 1. Let H⌊ε^-1.1⌋. For each 0 ≤ j ≤  J (with J given by (<ref>)) let θ_j be given by (<ref>), and write 

    I_j :   = {u∈ℤ:   H θ_j+1log x  ≤ u ≤ H θ_j log x-1},
    K_j :   = {v∈ℤ:   (1/2-θ_j+1)Hlog x ≤ v ≤1/2H log x-1}.

Define the set

    S'_J⋃_0≤ j≤ J⋃_u∈I_j,v∈𝒦_j   {n=pdm',   p∈ (e^u/H,e^(u+1)/H],   d∈ (e^v/H,e^(v+1)/H],   m'≤ xe^-(u+v+2)/H,
       P^+(d)≤ x^θ_j+1,   P^-(m')> x^θ_j}.

Let q≤ x^1/2-100η. Then for (a,q)=1 we have

    ∑_n≤ x
    n≡ a q
    P^+(n)≤ x^η(1-1_𝒮_J'(n))≪_ηεx/q.
    



By Lemma <ref>, it suffices to prove the claim with 1_S_J(n)-1_S_J'(n) in place of 1-1_S_J'(n). We have S_J'⊂S_J, since for n∈S_J we have a unique way to write it, for some 0≤ j≤ J, as n=dm with P^+(d)≤ x^θ_j+1, P^-(m)∈ (x^θ_j+1,x^θ_j], and we may further write m=pm', so that p∈ (x^θ_j+1,x^θ_j] and P^-(m')>p.

Now, if we define u_j^(1),u_j^(2) as the endpoints of the discrete interval I_j, and similarly v_j^(1), v_j^(2) as the endpoints of K_j, we see that n∈S_J belongs for unique 0≤ j≤ J, u∈I_j, v∈K_j to the set in the definition of S_J', unless one of the following holds for the factorization n=pdm' of n:

(i) We have p∈ [e^(u_j^(i)-1)/H,e^(u_j^(i)+1)/H] or d∈ [e^(v_j^(i)-1)/H,e^(v_j^(i)+1)/H] for some i∈{1,2} and 0≤ j≤ J;

(ii) We have p∈ [e^u/H,e^(u+1)/H], d∈ [e^v/H,e^(v+1)/H], m'∈ [xe^-(u+v+2)/H,xe^-(u+v)/H] for some u∈I_j, v∈K_j and 0≤ j≤ J.

(iii) We have P^-(m')∈ (x^θ_j+1,x^θ_j].

Condition (iii) clearly leads to condition (ii) in the proof of Lemma <ref> holding, so its contribution is ≪_ηε x/q.

We are left with the contributions of (i) and (ii). They are bounded similarly, so we only consider (ii).

For given j,u,v, Lemmas <ref> and <ref> tell us that the contribution of (ii) is

    ∑_e^u/H≤ p≤ e^(u+1)/H
    p∤ q∑_e^v/H≤ d≤ e^(v+1)/H
    P^+(d)≤ x^θ_j+1
    (d,q)=1∑_xe^-(u+v+2)/H≤ m'≤ xe^-(u+v)/H
    P^-(m')≥ x^θ_j+1
    m'≡ a(pd)^-1 q1
       ≪η^-1/H∑_e^u/H< p≤ e^(u+1)/H∑_e^v/H< d≤ e^(v+1)/H
    P^+(d)≤ x^θ_j+1
    (d,q)=1xe^-(u+v)/H/ϕ(q)θ_j+1log x
       ≪_η1/H^2θ_j+1ρ(1/(3θ_j+1))x/uqlog x,

where the second 1/H factor arose from summation over d and the 1/u factor arose from the summation over p. Summing this over u∈I_j, v∈K_j and 0≤ j≤ J and recalling that |I_j|≪ (θ_j-θ_j+1)H(log x), |K_j|≪θ_j+1Hlog x and ρ(y)≪ y^-2 yields a bound of

    ≪_η∑_0≤ j≤ J(θ_j-θ_j+1)θ_j+1(Hlog x)^2·1/H^21/Hlog^2 x·x/q≪_ηε^2 J/H·x/q≪_ηεx/q

by the definitions of H and J.


Now that we have decoupled the variables, we may introduce Dirichlet characters and obtain a trilinear sum. For u∈I_j,v∈K_j and H=⌊ε^-1.1⌋, write

    P_u(χ)   =∑_e^u/H< p≤ e^(u+1)/Hf(p)χ(p)
    
    D_v(χ)   =∑_e^v/H< d≤ e^(v+1)/H
    P^+(d) ≤ x^θ_j+1 f(d)χ(d),
    
    M_u,v(χ)   =∑_m≤ x/e^(u+v+2)/H
    P^-(m)  >x^θ_j f(m)χ(m).

Then we have the following.

 
Let x≥ 10, η∈ (0,1/10), ε∈ ((log x)^-1/200,1), q≤ x^1/2-100η, and let fℕ→𝕌 be a multiplicative function supported on x^η-smooth numbers. Letting χ_1 be as in Theorem <ref>, and recall the definitions in (<ref>). Then for (a,q)=1 we have

    |∑_n ≤ x
     n ≡ a q f(n) - χ_1(a)/ϕ(q)∑_n ≤ x f(n)χ_1(n)|
       ≤1/ϕ(q)∑_χ≠χ_1 q∑_0 ≤ j ≤ J∑_u ∈I_j∑_v ∈K_j |P_u(χ̅)||D_v(χ̅)||M_u,v(χ̅)|+O_η(ε x/q).




Applying Lemma <ref> to both f and fχ_1 and observing that the union of sets in the definition of S_J' is disjoint, we see that the left-hand side in the statement is

    |∑_0 ≤ j ≤ J∑_u ∈I_j
     v ∈K_j∑_e^u/H < p ≤ e^(u+1)/H∑_e^v/H < d ≤ e^(v+1)/H
     P^+(d) ≤ x^θ_j+1∑_m ≤ xe^-(u+v+2)/H
     P^-(m)> x^θ_j f(p)f(d)f(m)ξ_q(mdp)|
       + O_η(ε x/q),

where 

    ξ_q(n)1_n ≡ a q - χ_1(a)/ϕ(q)χ_1(n).

Making use of the orthogonality of characters and then applying the triangle inequality, the main term here is (omitting the summation ranges for brevity)

    |∑_0 ≤ j ≤  J∑_u ∈I_j
     v ∈K_j∑_χ≠χ_1 qχ(a)/ϕ(q)(∑_p f(p)χ(p)) (∑_d
     P^+(d) ≤ x^θ_j+1 f(d)χ(d)) (∑_m
     P^-(m) > x^θ_j f(m)χ(m))| 
       ≤1/ϕ(q)∑_0 ≤ j ≤ J∑_u ∈I_j∑_v ∈K_j∑_χ≠χ_1 q |P_u(χ̅)||D_v(χ̅)||M_u,v(χ̅)|,

and the claim follows.





 §.§ The main proof


Let η > 0. Suppose henceforth that the multiplicative function fNU is supported on x^η-smooth integers. Our task is to prove Theorem <ref>, i.e., to obtain cancellation in the deviation

    max_a ∈Z_q^×|∑_n ≤ x
     n ≡ a q f(n) - χ_1(a)/ϕ(q)∑_n ≤ x f(n)χ_1(n)|.

In what follows, let (log x)^-1/200≤≤ 1, let θ_j and J be given by (<ref>) and (<ref>), and recall the notation of (<ref>) and (<ref>). 

According to Lemma <ref>, we can restrict ourselves to bounding the product of character sums present in that lemma. Taking the maximum over (u,v)∈ℐ_j×𝒦_j there, it suffices to prove that

    ∑_0 ≤ j≤ J(θ_j-θ_j+1)θ_j+1 H^2(log x)^2/ϕ(q)∑_χ≠χ_1 q|P_u_j(χ)||D_v_j(χ)||M_u_j,v_j(χ)|≪_ηεx/q,

where for each 0≤ j≤ J the numbers u_j∈I_j, v_j∈K_j are chosen so that they give maximal contribution.

In analogy with the proofs of Theorems <ref> and <ref>, for each j≤ J we define[We only need to split the χ spectrum into two sets here, as opposed to many sets in the proof of Theorem <ref>. This is owing to the fact that P_u_j(χ) already has length ≫ q^ε, and thus our large values estimates for it are effective. The reason we are allowed to take P_u_j(χ) so long here (unlike in our previous proofs) is that we are assuming q≤ x^1/2-100η. If we only assumed that q=o(x^1/2), we would have to perform an iterative decomposition as in the preceding sections.] the sets X^(j) and U^(j) by

    X^(j)   {χ≠χ_1 q: |P_u_j(χ)| ≤ε^3e^u_j/H/u_j}
    U^(j)   {χ≠χ_1 q}X^(j).



  §.§.§ Case of X^(j)
 For a given 0 ≤ j ≤ J, consider the contribution from X^(j). Applying Cauchy–Schwarz, we have

    1/ϕ(q)∑_χ∈X^(j)  |P_u_j(χ)||D_v_j(χ)||M_u_j,v_j(χ)| 
       ≤(1/ϕ(q)∑_χ∈X^(j)  |M_u_j,v_j(χ)|^2)^1/2(1/ϕ(q)∑_χ∈X^(j)  |P_u_j(χ)|^2|D_v_j(χ)|^2)^1/2.


We begin by bounding the first bracketed sum. We do not use Lemma <ref> directly for this, since that would lose one factor of log x that comes from the sparsity of the m variable in the definition of M_u_j,v_j(χ). Instead, we expand the square and apply orthogonality, which shows that the first bracketed sum is bounded by

    (∑_m_1 ≤ xe^-(u_j+v_j)/H
     P^-(m_1) ≥ x^θ_j ∑_m_2≤ xe^-(u_j+v_j)/H
     P^-(m_2)≥ x^θ_j
    m_2≡ m_1 q1)^1/2.

Taking the maximum over m_1, summing over m_2 conditioned to m_2 ≡ m_1 q, and applying Lemma <ref> (recalling that xe^-(u_j+v_j)/H/q≫ x^η), this is

    ≪η^-1/θ_jϕ(q)^1/2log xxe^-(u_j+v_j)/H.


To treat the remaining bracketed expression, we use the pointwise bound from the definition of X^(j), and then use Lemma <ref> to bound D_v_j(χ), giving

    (1/ϕ(q)∑_χ∈X^(j) |P_u_j(χ)|^2|D_v_j(χ)|^2 )^1/2≪(ε^6/ϕ(q) e^2u_j/H/u_j^2∑_χ∈X^(j) |D_v_j(χ)|^2)^1/2
       ≪(ε^6/ϕ(q)e^2u_j/H/u_j^2 (ϕ(q)+ ϕ(q)/qe^v_j/H) (Ψ_q(e^(v_j+1)/H,x^θ_j+1) - Ψ_q(e^v_j/H,x^θ_j+1)))^1/2.


By Lemma <ref>,

    Ψ_q(e^(v_j+1)/H,x^θ_j+1) - Ψ_q(e^v_j/H,x^θ_j+1) ≪ρ(1/(3θ_j+1))ϕ(q)/qe^v_j/H/H.

Inserting this into (<ref>), and using e^v_j/H/q ≥ 1 for any v_j ∈K_j, results in the bound

    ≪ε^3(ϕ(q)/q^2ρ(1/(3θ_j+1))H^-1)^1/2e^(u_j+v_j)/H/u_j.

Combining this with the contribution from M_u_j,v_j(χ) yields the upper bound

    1/ϕ(q)∑_χ∈X^(j) |P_u_j(χ)||D_v_j(χ)||M_u_j,v_j(χ)| 
       ≪_ηε^3H^-1/2ρ(1/(3θ_j+1))^1/2/θ_j+1x/u_j(log x)q.

Recalling H= ⌊^-1.1⌋, ρ(u)≪ u^-2 and θ_j-θ_j+1≪ε^2, when inserted into (<ref>) this expression yields

    ≪_ηε^3(θ_j-θ_j+1)θ_j+1 H^2(log x)^2· H^-1/2ρ(1/(3θ_j+1))^1/2x/Hθ_j+1(log x)^2 q≪_η^4.1x/q.

Finally summing this over 0≤ j≤ J, the bound we obtain is

    ≪_η Jε^4.1x/q≪_ηε^2x/q,

which is good enough.




  §.§.§ Case of U^(j)
 
It remains to consider the contributions from U^(j). We restrict to q ∈Q_x,ε^9.5,ε^-100 with the notation of Lemma <ref>. As in the proof of Theorem <ref>, that set satisfies the desired size bound |[1,Q]∖𝒬_x,ε^9.5, ε^-100|≪ Qx^-ε^200 (since 9.5· 20<200), and for any set 𝒬'⊂ [1,x] of coprime integers the set 𝒬_x,ε^9.5, ε^-100 intersects it in ≪ (log x)^ε^-200 points (and under GRH we have 𝒬_x,ε^9.5,ε^-100=[1,x]∩ℤ). We also recall that in Theorem <ref> the character χ_1 q is such that inf_|t|≤log x𝔻_q(f,χ_j(n)n^it;x) is minimal.

By Proposition <ref> (with δ e^1/H-1≍1/H), for q as above we have |𝒰^(j)|≪ε^-6H≪ε^-7.1, since  P_u(χ) has length ≫ x^θ_J and θ_J≫_η 1/(log1/ε). 

Furthermore, applying Proposition <ref> (and Remark <ref>) to f(n)1_P^+(n)≤ x^θ_j (and recalling q ∈Q_x,ε^9.5,ε^-100), we see that[Note that the saving of ε^9.5 is much better than the trivial saving (which we do not need to exploit here) that comes from the fact that d is supported on x^θ_j-smooth numbers. The trivial saving would only be better if θ_j is roughly of size 1/log(1/ε) or smaller, but as we shall see the contribution of these large values of the index j is small in any case by trivial estimation.] 

    |D_v_j(χ)|=|∑_e^v_j/H≤ d≤ e^(v_j+1)/Hf(d)χ(d)1_P^+(d)≤ x^θ_j+1|≪ε^9.5ϕ(q)/qe^v_j/H

for all χ∈𝒰^(j), except possibly for the χ=χ^(j) that minimizes the pretentious distance inf_|t|≤log x𝔻_q(f,χ(n)1_P^+(n)≤ x^θ_j+1n^it;x). We argue that χ^(j) must be the character χ_1 of Theorem <ref>, in which case χ^(j)∉𝒰^(j) and we can ignore this character.

By applying Lemma <ref>, we see that either

    inf_|t|≤log x𝔻_q^2(f,χ^(j)(n)1_P^+(n)≤ x^θ_j+1n^it;x)≤ 1.01log1/ε^9.5+O(1)

or else (<ref>) holds without any exceptional characters. We may assume we are in the former case, and then by  θ_j+1≥θ_J+1≫_η 1/(log(1/ε)) and trivial estimation we obtain

    inf_|t|≤log x𝔻_q^2(f,χ^(j)(n)n^it;x)≤ 1.1log1/ε^9.5+O_η(1).

But we have the same for χ_1 in place of χ^(j) by the minimality of χ_1. Thus, assuming that χ^(j)≠χ_1 and applying the pretentious triangle inequality as in the proof of Proposition <ref> (using also that ε > (log x)^-1/200), we obtain a contradiction. This means that we may assume from now on that (<ref>) holds for all χ∈𝒰^(j) and 0≤ j≤ J.

Now we take the maximum over χ∈U^(j) in the sum that we are considering and apply the Brun–Titchmarsh inequality to P_u_j(χ) and Lemma <ref>  to M_u_j,v_j(χ) to bound 

    1/ϕ(q)∑_χ∈U^(j)  |P_u_j(χ)||D_v_j(χ)||M_u_j,v_j(χ)| 
       ≪ e^u_j/H/(u_j/H) · |U^(j)|max_χ∈U^(j) |D_v_j(χ̅)|· |M_u_j,v_j(χ̅)| 
       ≪ e^u_j/H/(u_j/H)·ε^-7.1·ε^9.5e^v_j/H/q· xe^-(u_j+v_j)/Hη^-1/Hθ_j+1log x
       ≪_ηε^2.4x/qθ_j+1^2H(log x)^2,

and this multiplied by (θ_j-θ_j+1)H^2(log x)^2 and summed over 0≤ j≤ J (recalling that θ_J≫_η1/log (1/ε)) produces the bound

    ≪_ηε^2.4(log1/ε)^2H ∑_0≤ j≤ J(θ_j-θ_j+1)x/q≪_ηε^1.2x/q.

This completes the proof of Theorem <ref>.






§ A LINNIK-TYPE RESULT




In this section, we prove our Linnik-type theorems stated in Section <ref>. As in the proof of Theorem <ref>, we employ the Matomäki–Radziwiłł method in arithmetic progressions. 

Our main propositions in this section concern products of exactly three primes of the form

    E_3^*{n=p_1p_2p_3:   P_j^1-ε≤ p_j≤ P_j,   j∈{1,2,3}},   P_1=q^1000ε,  P_2=P_3=q.


  For every small enough ε>0 there exists η(ε)>0 such that the following holds. 

Let q≥ 2 with P^+(q)≤ q^η(ε). There exists a real character ξ q such that for all a coprime to q we have

    ∑_n∈ E_3^*
    n≡ a  q1/n   =1+O(ε)/ϕ(q)∑_P_1^1-ε≤ p_1≤ P_1∑_P_2^1-ε≤ p_2≤ P_2∑_P_3^1-ε≤ p_3≤ P_31/p_1p_2p_3
       +ξ(a)/φ(q)∑_P_1^1-ε≤ p_1≤ P_1∑_P_2^1-ε≤ p_2≤ P_2∑_P_3^1-ε≤ p_3≤ P_3ξ(p_1p_2p_3)/p_1p_2p_3

with E_3^*, P_1, P_2, P_3 as in (<ref>). 


  For every small enough ε>0 there exists M(ε)≥ 1 such that the following holds. 

Let q≥ 2. Suppose that the product ∏_χ qL(s,χ) has the zero-free region (s)≥ 1-M(ε)/log q, |(s)|≤ (log q)^3. Then for all a coprime to q we have

    ∑_n∈ E_3^*
    n≡ a  q1/n   =1+O(ε)/ϕ(q)∑_P_1^1-ε≤ p_1≤ P_1∑_P_2^1-ε≤ p_2≤ P_2∑_P_3^1-ε≤ p_3≤ P_31/p_1p_2p_3

with E_3^*, P_1, P_2, P_3 as in (<ref>).


We shall deduce Theorem <ref>(i)–(ii)  from these two propositions at the end of the section. 



 §.§ Auxiliary lemmas

In order to prove these propositions, we shall need a result of Chang <cit.>, giving an improved zero-free region for L(s,χ) when the conductor of χ is smooth.



Suppose q≥ 2 and P^+(q)≤ q^κ with C/(loglog(10q))<κ<0.001 for large enough C>0. Then the product ∏_χ qL(s,χ) obeys the zero-free region

    (s)≥ 1-cκ^-1/log q,   |(s)|≤ q

for some constant c>0, apart from possibly a single zero β. If β exists, then it is real and simple and corresponds to a unique real character q.



This follows from work of Chang <cit.> (improving on work of Iwaniec <cit.>). Indeed, that theorem shows that, apart from possibly one real, simple zero corresponding to a real, non-principal character, there are constants c,c' > 0 such that L(s,χ) has the zero-free region 

    (s)>1-cmin{1/log P^+(q),loglog d'/(log d')log(2log d/log d'),1/(log (dT))^1-c'},   |(s)|≤ T,

where d is the conductor of χ
and d'=∏_p| d p. We take T=q and note that the middle term in the minimum is ≫loglog d/log d≥loglog q/log q, and this produces the zero-free region of the lemma.



We will also need the following mean value estimate for sums over small sets of characters.
 Let q≥ 1 be an integer, and let Ξ be a set of characters q. Then for k∈{2,3}, η>0, 2≤ R<√(N), and for any complex numbers a_p, we have the estimate

    ∑_χ∈Ξ|∑_p≤ Na_pχ(p)|^2≪_k,η(N/log R+N^1-1/kq^(k+1)/4k^2+η|Ξ|R^2/k)∑_p≤ N|a_p|^2.






This is a result of Puchta <cit.>.


In the proof of Theorem <ref>(i)–(ii), we will need pointwise estimates for logarithmically weighted character sums assuming only a narrow zero-free region. By a simple Perron's formula argument, we can obtain cancellation in 

    ∑_P≤ p≤ P^1+κχ(p)/p

for χ≠χ_0 q, κ>0 fixed, and P∈ [ q^ε,q] if we assume a zero-free region of the form (s)>1-3loglog q/log P, |(s)|≤ q for L(s,χ); the need for this zero-free region comes from pointwise estimation of |L'/L(s,χ)|≪log^2(q(|t|+2)) which costs us two logarithms (in the region where we are ≫1/log(q(|t|+1)) away from any zeros). However, we must argue differently, since we are only willing to assume a zero-free region of the form (s)>1-M(ε)/log P, |(s)|≤ q (which we know for smooth moduli apart from Siegel zeros). To do so, we exploit the logarithmic weight 1/p  in the sum over P≤ p≤ P^1+κ, which allows us to insert a carefully chosen smoothing. A variant of such an argument is known as a Rodosskii bound in the literature. 
 

 Let q≥ 2, ε>0, κ>0, and let χ q be a non-principal character. Suppose that L(s,χ)≠ 0 for (s)>1-κ^-2/log q, |(s)|≤ (log q)^3. Then, provided that P≥ q^κ≫_κ 1, we have

    sup_|t|≤ (log q)^3/2|∑_P≤ p≤ P^1+εχ(p)/p^1+it|≤ C_0 κ

with C_0>0 an absolute constant.




This is a slight modification of results proved by Soundararajan <cit.> and by Harper <cit.>; in those bounds there is the nonnegative function (1-(χ(p)p^-it))/p in place of χ(p)/p^1+it in (<ref>), and consequently only lower bounds of the correct order of magnitude are needed in those results. We will choose a more elaborate smoothing to obtain asymptotics (up to O(κ)) for (<ref>). Also note that our range of |t| is smaller than in the works mentioned above, but correspondingly the zero-free region is assumed to a lower height.  


We may assume without loss of generality that κ< ε/10<1/10, since otherwise the trivial Mertens bound for (<ref>) is good enough. By splitting the interval [P,P^1+ε] into ≪ε/κ intervals of the form [y,y^1+κ] (and possibly one additional interval), it suffices to show that

    sup_|t|≤ (log q)^3/2|∑_y≤ p≤ y^1+κχ(p)log p/p^1+it|≪κ^2 log y

uniformly for y∈ [P,P^2].

We introduce the continuous, nonnegative weight function

    g(u)=κ^-2u,   u∈ [0,κ^2]
    
    1,   u∈ [κ^2, κ-κ^2]
    κ^-2(κ-u),    u∈ [κ-κ^2,κ],
    
    0,   u∉[0,κ];

in other words, g is a trapezoid function. We further define the weight function

    W(p)=W_y,κ(p)=g(logp/y/log y)log y.

Since W(p)=log y for p∈ [y^1+κ^2,y^1+κ-κ^2], and 0≤ W(p)≤log y everywhere, by estimating the contribution of p∈ [y,y^1+κ^2]∪ [y^1+κ-κ^2,y^1+κ] trivially, it suffices to show that

    sup_|t|≤ (log q)^3/2|∑_pχ(p)W(p)log p/p^1+it|≪κ^2 log^2 y.


Let χ^* be the primitive character that induces χ. Since the contribution of p| q to the sum in (<ref>) is negligible, and since we can replace log p with the von Mangoldt function, from Perron's formula we see that 

    ∑_pχ(p)W(p)log p/p^1+it=-1/2π i∫_-i∞^i∞L'/L(1+it+s,χ^*)W(s)  ds+O(κ^2log y),

where

    W(s)∫_0^∞W(x)x^s-1  dx=κ^-2y^(1+κ)s-y^(1+κ-κ^2)s-y^(1+κ^2)s+y^s/s^2

is the Mellin transform of W.

Shifting the contours to the left, and noting that W(s) is entire and |W(s)|≪κ^-2/|s|^2 for (s)≤ 0, we reach

    ∑_pχ(p)W(p)log p/p^1+it=-∑_ρW(ρ-1-it)+O(κ^2log y),

where the sum is taken over all nontrivial zeros of L(s,χ^*). Since |t|≤(log q)^3/2, we can truncate the ρ sum to end up with 

    ∑_pχ(p)W(p)log p/p^1+it=-∑_|(ρ)|≤ (log q)^3W(ρ-1-it)+O(κ^2log y).


Let Aκ^-2. Thanks to our assumption on zero-free regions, we clearly have

    |W(ρ-1-it)|≪κ^-2y^-A/log q/|ρ-1-it|^2,

and consequently

    |∑_pχ(p)W(p)log p/p^1+it|≪κ^-2 y^-A/log q∑_|(ρ)|≤ (log q)^31/|1+it-ρ|^2+κ^2 log y.


We now note that for any zero ρ=β+iγ, with |γ|≤ (log q)^3 we must have β≤ 1-A/log q, and so

    1/|1+it-ρ|^2≪1/|1+1/log q+it-ρ|^2≪log q/A(1/1+1/log q+it-ρ).

Thus we can estimate 

    |∑_pχ(p)W(p)log p/p^1+it|≪κ^-2y^-A/log q·log q/A∑_ρ(1/1+1/log q+it-ρ)+κ^2 log y.


Recall that y≥ P≥ q^1/√(A). We can use the Hadamard factorization theorem in the form given in <cit.> on the right-hand side of the above formula, and estimate |L'/L(1+1/log q + it,χ)|≪log q, to see that

    |∑_pχ(p)W(p)log p/p^1+it|≪κ^-2 e^-√(A)A(log y)^2+κ^2log y≪κ^2 log^2 y

by our choice of A. This finishes the proof of the lemma. 





 §.§ Proof of Propositions <ref> and <ref>

 We may assume that ε>0 is small enough and that q is large enough in terms of ε, since we must have q^ε'≥ 2, and we are free to choose the dependence of ε' on ε. We shall show that if q is such that we have the zero-free region L(s,χ)≠ 0 for (s)≥ 1-ε^-100/log q, |(s)|≤ (log q)^3 for all χ q apart from possibly one real character ξ, then (<ref>) holds[If this bad ξ does not exist, let ξ be any non-principal real character in what follows.]. This zero-free region is in particular satisfied for those q that satisfy P^+(q)≤ q^η(ε) with small enough η(ε)>0.

By the orthogonality of characters, we have

    ∑_n∈ E_3^*
    n≡ a  q1/n=∑_χ∈{χ_0,ξ} qχ(a)/ϕ(q)P_1(χ)P_2(χ)P_3(χ)+∑_χ q
    χ≠χ_0,ξχ(a)/ϕ(q)P_1(χ)P_2(χ)P_3(χ),

where we have defined

    P_j(χ)∑_P_j^1-ε≤ p≤ P_jχ(p)/p,    j∈{1,2,3}.

In the above expression, in the term corresponding to χ_0 we can replace χ_0 by 1 at the cost of O((log q)/q^ε).

We employ the Matomäki–Radziwiłł method as in our other proofs. Let

    𝒳:   ={χ q:  χ∉{χ_0,ξ},   |P_1(χ)|≤ P_1^-0.01},
    𝒰_S:   ={χ q:  χ∉{χ_0,ξ}}∖𝒳.
   
Unlike in the earlier sections, there is no 𝒰_L case to analyze, owing to the fact that for χ∈𝒰_S we already have some cancellation in |P_1(χ)| by Lemma <ref> and our assumption on q.

The case of X is handled similarly to our other proofs. Indeed, by Cauchy–Schwarz, we have

    ∑_χ∈X|P_1(χ)||P_2(χ)||P_3(χ)|≪ P_1^-0.01(∑_χ∈X|P_2(χ)|^2)^1/2(∑_χ∈X|P_3(χ)|^2)^1/2.

By the mean value theorem for character sums (Lemma <ref>) and the fact that P_1=q^1000ε, P_2=P_3=q, this is

    ≪ q^-10εϕ(q)(∑_P_2^1-ε≤ p_2≤ P_21/p_2^2)^1/2(∑_P_3^1-ε≤ p_3≤ P_31/p_3^2)^1/2≪ q^-ε,

say, since ϕ(q)/(P_2P_3)^1/2(1-ε)≪ q^ε. 

The remaining case to consider is that of U_S. Note that, combining the assumed zero-free region for L(s,χ), χ≠ξ q with Lemma <ref>, we see that |P_1(χ)|≪ε^2 for all χ∈𝒰_S.

We first estimate |U_S|. For each χ∈U_S we decompose P_1(χ̅) into dyadic segments [y,2y] with y = 2^j ∈ [P_1^1-ε/2,P_1] and use partial summation to obtain

    |P_1(χ̅)| ≪ (εlog P_1) max_y ∈ [P_1^1-ε/2, P_1] 
     y = 2^j1/y|∑_y ≤ p ≤ 2yχ(p)|.

From Lemma <ref>, which bounds the number of large values taken by a prime-supported character sum, we have the size bound

    |U_S|    ≤ |{χ q:   |P_1(χ)|>P_1^-0.01}| 
       ≤|{χq :   max_y ∈ [P_1^1-ε, P_1] 
     y = 2^j1/y|∑_y ≤ p ≤ 2yχ(p)| ≥ P_1^-0.01(log P_1)^-1}| 
       ≪∑_P_1^1-ε/2 ≤ y ≤ P_1 
     y = 2^j |{χq :    |∑_y ≤ p ≤ 2yχ(p)| ≥ y^1-0.02}| ≪ q^0.05,

recalling that P_1 = q^1000ε, and q is sufficiently large in terms of ε.

Introducing the dyadic sums 

    P_j,v(χ)∑_e^v≤ p≤ e^v+1
    P_j^1-ε≤ p≤ P_jχ(p)/p,    v∈ I_j  [(1-ε)log P_j,log P_j],

the upper bound on |P_1(χ)| above and Cauchy–Schwarz give

    ∑_χ∈U_S|P_1(χ)||P_2(χ)||P_3(χ)|   ≪ε^2∑_v_1,v_2∈ I_2∑_χ∈U_S|P_2,v_1(χ)||P_3,v_2(χ)|
       ≪ε^2 (εlog q)^2 (∑_χ∈U_S|P_2,v'_1(χ)|^2)^1/2(∑_χ∈U_S|P_3,v'_2(χ)|^2)^1/2

for some v'_1,v'_2∈ I_2 (since as P_2 = P_3 we have I_2 = I_3). It remains to be shown that for any v ∈ I_j,

    ∑_χ∈U_S|P_j,v(χ)|^2≪1/log^2 q

for j∈{2,3}, since then we get a bound of ≪ε^4 for the sum over χ∈U_S, and this (multiplied by the 1/ϕ(q) factor) can be included in the error term in (<ref>).

For this purpose, we apply Lemma <ref>, which is a sharp inequality of Halász–Montgomery-type for character sums over primes[For this estimate to work, it is crucial that the character sums P_j,v(χ) are long enough in terms of q; in particular, we need them to have length ≫ q^1/3+ε.]. We take N=e^v+1, |Ξ|=|𝒰_S|≪ q^0.05, k=3, R=N^0.0001, a_p=1/p1_p∈ [e^v, e^v+1]∩ [P_j^1-ε,P_j] in that lemma. Since the term N^2/3q^1/9|Ξ|R^2/3 appearing in Lemma <ref> is smaller than the other term N/log R for our choice of parameters, we get a bound of ≪ e^v/v·1/ve^v≪1/log^2 q, as desired. This completes the analysis of the U_S case, so  Proposition <ref> follows.


 The proof of Proposition <ref> is similar to that of Proposition <ref>, except that there are no exceptional characters arising. The proof of (<ref>) goes through for any q for which L(s,χ)≠ 0 whenever (s)>1-ε^-100/log q, |(s)|≤ (log q)^3 and χ≠ξ q. Moreover, since under the assumption of Proposition <ref> the exceptional character ξ does not exist (that is, the above holds for all χ q), we can delete the term involving ξ from (<ref>), giving (<ref>). This gives Proposition <ref>.




 §.§ Deductions of Linnik-type theorems


Corollary <ref> is a direct consequence of Theorem <ref>(i) (by fixing ε>0 in its statement). Hence, it suffices to prove Theorem <ref>(i)–(ii).


 It suffices to show that for all but ≪_ε1 primes q∈ [Q^1/2,Q] the right-hand side of (<ref>) is >0; indeed, then the smallest q-smooth E_3 number in the progression a q is ≤ q^2+1000ε (and since ε>0 is arbitrarily small, this is good enough). 

In view of Proposition <ref>, it suffices to show that for all but ≪_ε 1 primes q ∈ [Q^1/2,Q], ∏_χ qL(s,χ) obeys the zero-free region (s)≥ 1-M(ε)/log q, |(s)|≤ (log q)^3 required by that proposition.

Since q is a prime, all the characters modulo q apart from the principal one are primitive. Moreover, the zeros of the L-function corresponding to the principal character are the same as the zeros of the Riemann zeta function, so we have the Vinogradov–Korobov zero-free region for this L-function. It therefore suffices to consider the L-functions corresponding to primitive characters. By the log-free zero density estimate (Lemma <ref>), we immediately see that ∏_χ q^* L(s,χ) has the required zero-free region  for all but
≪exp(100M(ε)) prime
moduli q∈ [Q^1/2,Q], so we have the claimed result. 




 Fixing δ>0, we will show that if P^+(q)≤ q^ε' with ε' very small in terms of δ, then the least product of exactly three primes in every reduced residue class a q is ≪ q^2+δ.

Let ε>0 be very small in terms of δ. By Lemma <ref>, we have the zero-free region required by Proposition <ref> whenever P^+(q)≤ q^η(ε) with η(ε)>0 small enough, apart from possibly a single zero β, which is real and simple and corresponds to a single real character q.


If this exceptional zero β does not exist, then from Proposition <ref> we obtain a positive lower bound for the left-hand side of (<ref>). Therefore, we can assume that β exists. This is a  real zero of an L-function q, and we write the zero as β=1-c/log q with c>0. By a result of Heath-Brown <cit.> on Linnik's theorem and Siegel zeros, if c≤ c_0(δ) for a suitably small function c_0(δ), then the least prime in any arithmetic progression a q with (a,q)=1 is ≪ q^2+δ/2, and thus also the least n≡ a q with exactly three prime factors obeys the same bound (indeed, if p_1,p_2≪log^2 q are chosen to be primes not dividing q and p≪ q^2+δ/2 is a prime ≡ a(p_1p_2)^-1 q, then p_1p_2p≪ q^2+δ and p_1p_2p≡ a  q). Thus we have proved the theorem if β≥ 1-c_0(δ)/log q, so henceforth we will assume we are in the opposite case.

According to Proposition <ref>, it suffices to show that 

    |∑_P_3^1-ε≤ p≤ P_3ξ(p)/p|≤ (1-√(ε))∑_P_3^1-ε≤ p≤ P_31/p,

since then the left-hand side of (<ref>) is >0 for ε>0 small enough.  

Following the exact same argument as in the proof of Lemma <ref>, and introducing the same weight function W=W_y,κ with y∈ [P_3^1-ε,P_3] and κ=ε^10 (and using (<ref>)), it is enough to show that 

    |∑_ρW(ρ-1)|≤ (1-10√(ε))(log^2 y)∑_y^1-κ≤ p≤ y1/p,

where the sum is over the nontrivial zeros ρ of L(s,ξ). Just as in the proof of Lemma <ref>, the contribution of all the zeros ρ≠β is ≪ε(log^2 y) ∑_y^1-κ≤ p≤ y1/p as long as P^+(q)≤ q^η_1(ε) with η_1(ε) small enough. It suffices to show, then, that

    |W(β-1)|≤  (1-11√(ε))(log^2 y)∑_y^1-κ≤ p≤ y1/p.


We recall that β≤ 1-c_0(δ)/2log y, and denote 
    F(u)W(-u/log y)=κ^-2e^-au-e^-bu-e^-cu+e^-u/u^2log^2 y,
 
where a=1+κ, b=1+κ-κ^2, c=1+κ^2 and the value at u=0 is interpreted as the limit as u→ 0. We compute using L'Hôpital's rule that W(0)=F(0)=κ(1-κ)log^2 y, and differentiation shows that F is decreasing, so W is increasing. Moreover, F' is increasing and F'(u)=(κ/2· (-2+κ+κ^2)+O(κ u))log^2 y for |u|≤ 1. Thus, by the mean value theorem applied to F we have

    W(β-1)≤W(-c_0(δ)/2log y)=F(c_0(δ)/2)≤ F(0)+c_0(δ)/2F'(c_0(δ)/2)≤κ(1-κ-c_0(δ)/4)log^2 y,

since δ>0 is small. We further have 1-κ-c_0(δ)/4≤ 1-100√(ε) if ε>0 (and hence κ) is small enough in terms of δ, so that (<ref>) holds by Mertens' bound. This completes the proof. 



 The proof of Proposition <ref> follows along similar lines as those above, so we merely sketch it, indicating the required modifications. We outline the lower bound for n with μ(n) = -1; the corresponding estimate for μ(n) = +1 is proved in the analogous way. 

When considering numbers n with μ(n)=-1, we restrict to those n that belong to the set

    S{n∈ℕ:  Ω_[P_j,Q_j](n)=1,   j∈{1,2}}

with P_1=x^ε/10, Q_1=x^ε/5, P_2=x^1/2-ε, Q_2=x^1/2-ε/2;
this introduces essentially the same factorization patterns for our n as in the case of products of exactly three primes. By writing 1_μ(n)=-1=1/2(μ^2(n)-μ(n)), it suffices to bound

    ∑_n≤ x
    n≡ a qμ^2(n)1_S(n)≫εx/q,    |∑_n≤ x
    n≡ a qμ(n)1_S(n)|≪ε^2 x/q.


We concentrate on the latter bound (the former is similar but easier). Write n=p_1p_2m with p_j∈ [P_j,Q_j] for j = 1,2, m≤x/p_1p_2. As in the previous sections, we can easily get rid of the cross condition on the variables by splitting into short intervals, so applying orthogonality of characters it suffices to show that

    1/φ(q)∑_χ q
    χ≠χ_0|Q_v_1,H(χ)Q_v_2,H(χ)R_v_1+v_2,H(χ)|≪ε^2 x/H^3(log Q_1)(log Q_2)q,

uniformly for v_i∈ I_i,
where we have defined

    Q_v,H(χ)∑_e^v/H≤ p<e^(v+1)/Hχ(p),   R_v,H(χ)∑_m≤ x/e^v/Hμ(m)χ(m)1_𝒯(m),
       I_i=[Hlog P_i,Hlog Q_i],   H=⌊ε^-3⌋,

and T is the set of numbers coprime to all the primes in [P_j,Q_j] for j∈{1,2}. We consider the cases 

    X:   ={χ q:   |Q_v_1,H(χ)|≤ e^0.99v_1/H}∖{χ_0}
    U_S:   ={χ q:   |Q_v_1,H(χ)|≤ε^20e^v_1/H/v_1}∖ (X∪{χ_0})
    U_L:   ={χ q}∖ (𝒳∪𝒰_S∪{χ_0}).


The case of X is easy and is handled just as in the proof of Proposition <ref>. The case of U_S is also handled similarly as in that proposition, except that we also need a Halász–Montgomery estimate for ∑_χ∈U_S|R_v_1+v_2,H(χ)|^2. This bound takes the same form as Lemma <ref>, but is proved simply by applying duality and the Burgess bound (since R_v_1+v_2,H(χ) is a sum over the integers rather than over the primes). 

Finally, the U_L set is small in the sense that |U_L|≪ε^-43 by Proposition <ref> whenever we have the zero-free region

    ∏_χ qL(s,χ)≠ 0    for   (s)>1-M(ε)/log q,  |(s)|≤ 3q
 
with M(ε) large enough. It thus suffices to prove that 
    sup_χ≠χ_0 q|R_v_1+v_2,H(χ)|≪ε^60ϕ(q)/qxe^-(v_1+v_2)/H,
 
and by Lemma <ref> this reduces to the bound 

    sup_χ q
    χ≠χ_0inf_|t|≤ (log q)^3/2∑_p≤ x
    p∤ q1+(χ(p)p^-it)/p≥ 61log1/ε+O(1).

At first, a direct application of Lemma <ref> reduces to proving (<ref>) with χ(p)p^-it1_𝒮(p) in place of χ(p)p^-it, but since log Q_j/log P_j≪ 1 by our choices, the contribution of those p with 1_𝒮(p)≠ 1 is negligible in (<ref>).

Restricting the sum in (<ref>) to p∈ [x^κ,x] with κ=ε^61, we indeed obtain (<ref>) from Lemma <ref> upon splitting [x^κ,x] into segments 
    [x^κ_j,x^κ_j+1], 
      where κ_j = κ(1+ε)^j  and  0 ≤ j ≤⌈log(1/κ)/log(1/ε)⌉≪ 1,
 
 as long as we have the zero-free region (<ref>). This zero-free region is indeed available by Lemma <ref> for all but ≪_ε1 primes q∈ [Q^1/2,Q], as in the proof of Theorem <ref>(ii).




§ ACKNOWLEDGMENTS
 We are grateful to Kannan Soundararajan for inspiring discussions and remarks, and in particular for his insistence that there should be a way to improve our main result. This indeed led to a stronger version of our main theorem. We also thank Claus Bauer, Andrew Granville, Kaisa Matomäki and Maksym Radziwiłł for useful comments and discussions.  

We thank the anonymous referees for their very helpful and valuable comments that improved the exposition of this paper and led to strengthened formulations of some of the results. 

The third author was supported by a Titchmarsh Fellowship of the University of Oxford, 
Academy of Finland grant no. 340098, and funding from European Union's Horizon
Europe research and innovation programme under Marie Skłodowska-Curie grant agreement No
101058904.

This project was initiated while the authors were visiting CRM in Montreal in spring 2018, and they would like to thank CRM for excellent working conditions during their visit there. 



plain

