Mangerel

Youness Lamzouri
email: lamzouri@mathstat.yorku.ca

Alexander P Mangerel
email: sacha.mangerel@mail.utoronto.ca

LARGE ODD ORDER CHARACTER SUMS AND IMPROVEMENTS OF THE P ÓLYA-VINOGRADOV INEQUALITY

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The study of Dirichlet characters and their sums has been a central topic in analytic number theory for a long time. Let q ≥ 2 and χ be a non-principal Dirichlet character modulo q. An important quantity associated to χ is

M (χ) := max t≤q n≤t χ(n) .
The best-known upper bound for M (χ), obtained independently by Pólya and Vinogradov in 1918, reads

(1.1) M (χ) √ q log q.

Though one can establish this inequality using only basic Fourier analysis, improving on it has proved to be a difficult problem, and resisted substantial progress for several decades. Conditionally on the Generalized Riemann Hypothesis (GRH), Montgomery and Vaughan [START_REF] Montgomery | Exponential Sums with Multiplicative Functions[END_REF] showed in 1977 that

(1.2) M (χ) √ q log log q.

This bound is best possible in view of an old result of Paley [START_REF] Paley | A theorem on characters[END_REF] that there exists an infinite family of primitive quadratic characters χ mod q such that (1.3) M (χ) √ q log log q.

Assuming GRH, Granville and Soundararajan [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF] extended Paley's result to characters of a fixed even order 2k ≥ 4. The assumption of GRH was later removed by Goldmakher and Lamzouri [START_REF] Goldmakher | Large even order character sums[END_REF], who obtained this result unconditionally, and subsequently Lamzouri [START_REF] Lamzouri | Large Values of L(1, χ) for kth order characters χ and applications to character sums[END_REF] obtained the optimal implicit constant in (1.3) for even order characters. The situation is quite different for odd order characters. In this case, Granville and Soundararajan [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF] proved the remarkable result that both the Pólya-Vinogradov and the Montgomery-Vaughan bounds can be improved. More specifically, if g ≥ 3 is an odd integer, and χ is a primitive character of order g and conductor q then they showed that (1.4) M (χ) √ q(log Q) 1-δg 2 +o [START_REF] Balog | Soundararajan Multiplicative functions in arithmetic progressions[END_REF] , where δ g := 1 -g π sin(π/g) and

(1.5) Q := q unconditionally, log q on GRH.

By refining their method, Goldmakher [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF] was able to obtain the improved bound (1.6) M (χ) √ q(log Q) 1-δg+o (1) .

As mentioned above, the results of Granville-Soundararajan [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF] and Lamzouri [START_REF] Lamzouri | Large Values of L(1, χ) for kth order characters χ and applications to character sums[END_REF] determine the precise order of magnitude of the maximal values of M (χ) when χ has an even order 1 . The objective of this paper is to answer this question for characters of a fixed odd order g ≥ 3. More precisely, we would like to improve the estimate (1.6) unconditionally, and moreover determine the optimal (log Q) o (1) contributions in the conditional part of (1.6) as well as unconditionally in the corresponding lower bound in (1.7) below. We make progress in both of these directions, as Theorems 1.1 and 1.3 will show.

This work is also motivated by recent results of Bober-Goldmakher [START_REF] Bober | Pólya-Vinogradov and the least quadratic nonresidue[END_REF], Fromm-Goldmakher [START_REF] Fromm | Improving the Burgess bound via Plya-Vinogradov[END_REF] and Mangerel [START_REF] Mangerel | Short character sums and the Pólya-Vinogradov inequality[END_REF], relating improvements of the Pólya-Vinogradov inequality to Vinogradov's conjecture for the least quadratic non-residue, and bounds for short character sums. It is an outstanding problem in analytic number theory to show cancellation in character sums, i.e., estimates of the form n≤x χ(n) = o(x), whenever x > q ε for any ε > 0. In [START_REF] Mangerel | Short character sums and the Pólya-Vinogradov inequality[END_REF], Mangerel shows that such cancellation for an odd character χ of large modulus q and fixed order occurs as long as M (χ) = o( √ q log q), but this only addresses characters of even order. Moreover, in forthcoming work, Granville and Mangerel further strengthen the relationship between improvements to estimates for maximal character sums and cancellation of short sums, but the assumption that χ be an odd character appears necessary here as well. Nevertheless, even small improvements to maximal character sum estimates may have deep consequences towards estimates for short character sums, and our desire in this paper is to sharpen these as much as possible for odd order characters.

Our first main result, Theorem 1.1, yields an improvement of (1.6) for characters χ of odd order g ≥ 3, both conditionally and unconditionally.

Theorem 1.1. Let g ≥ 3 be a fixed odd integer, and let ε > 0 be small. Then, for any primitive Dirichlet character χ of order g and conductor q we have M (χ) ε √ q (log q) 1-δg (log log q) -1 4 +ε .

Moreover, if L(s, ψ) has no Siegel2 zero for any primitive character ψ of conductor at most (log q) 4/11 then

M (χ) √ q (log Q) 1-δg (log log Q) -1 4 (log log log Q) O(1)
where Q is defined as in (1.5).

Remark 1.2. Of course, if GRH is assumed then the second case in Theorem 1.1 holds, with Q = log q. In Section 2.1 we will explain the form of the Siegel zero condition, which is an artefact of our proof.

Assuming GRH, and using results of Granville and Soundararajan (see Theorem 2.4 below), Goldmakher [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF] also showed that the conditional bound in (1.6) is best possible. More precisely, for every ε > 0 and odd integer g ≥ 3, he proved the existence of an infinite family of primitive characters χ mod q of order g such that (1.7) M (χ) ε √ q(log log q) 1-δg-ε , conditionally on the GRH. By modifying the argument of Granville and Soundararajan and using ideas of Paley [START_REF] Paley | A theorem on characters[END_REF], Goldmakher and Lamzouri [START_REF] Goldmakher | Lower bounds on odd order character sums[END_REF] proved this result unconditionally.

Our second main result, Theorem 1.3, gives an unconditional improvement of the abovedescribed lower bound estimates that corresponds with the improved upper bound in Theorem 1.1. Together, Theorems 1.1 and 1.3 show that, conditionally on GRH, the maximal size of M (χ) for a character χ modulo q of odd order g is determined up to a factor (log log log log q) O (1) .

Here and throughout, we write log k x = log(log k-1 x) to denote the kth iterated logarithm, where log 1 x = log x.

Theorem 1.3. Let g ≥ 3 be a fixed odd integer. There are arbitrarily large q and primitive Dirichlet characters χ modulo q of order g such that 1) .

(1.8) M (χ) g √ q (log 2 q) 1-δg (log 3 q) -1 4 (log 4 q) O(
To obtain Theorem 1.3, our argument relates M (χ) to the values of certain associated Dirichlet L-functions at 1, and uses zero-density results and ideas from [START_REF] Lamzouri | Large Values of L(1, χ) for kth order characters χ and applications to character sums[END_REF] to construct characters χ for which these values are large. We shall discuss in greater detail the different ingredients in the proofs of Theorems 1.1 and 1.3, as well as the extent to which the above results may be improved, in the next section.

Remark 1.4. As implied by our notation, the implicit constant in Theorem 1.1 is independent of the order g (as is the exponent in the expression (log 3 Q) O (1) ). In contrast, the implicit constant in Theorem 1.3 does depend on g: following the proof of Theorem 1.3 one can deduce that the constant ought to be exp(-c p|g 1/p) (log log g) -c , for some explicitly computable constant c > 0. This factor arises from the use of gth power reciprocity to construct the characters needed to prove Theorem 1.3 (see specifically the proof of Proposition 2.6 below).

Remark 1.5. The O(1) exponent in the (log 3 Q) O (1) factor in Theorem 1.1, and the exponent in the (log 4 q) O(1) factor in Theorem 1.3 arise from the same source; see Remark 2.7 for an indication of this. To be more explicit, we can summarize Theorems 1.1 (in the case where no Siegel zero exists) and 1.3 as follows: there is an absolute constant C > 0 (independent of g) such that we have the upper bound

M (χ) √ q(log Q) 1-δg (log 2 Q) -1/4 (log 3 Q) C ,
for all primitive characters χ to large enough modulus q, and unconditionally the lower bound M (χ) g √ q(log 2 q) 1-δg (log 3 q) -1/4 (log 4 q) -C

holds for an infinite sequence of moduli q and primitive characters χ modulo q.

Recent progress on character sums was made possible by Granville and Soundararajan's discovery of a hidden structure among the characters χ having large M (χ). In particular, they show that M (χ) is large only when χ pretends to be a character of small conductor and opposite parity. To define this notion of pretentiousness, we need some notation. Here and throughout we denote by F the class of completely multiplicative functions f such that |f (n)| ≤ 1 for all n. For f, g ∈ F we define

D(f, g; y) := p≤y 1 -Re(f (p)g(p)) p 1 2
, which turns out to be a pseudo-metric on F (see [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF]). We say that f pretends to be g (up to y) if there is a constant 0 ≤ δ < 1 such that D(f, g; y) 2 ≤ δ log log y.

One of the key ingredients in the proof of (1.4) is the following bound for logarithmic mean values of functions f ∈ F in terms of D(f, 1; x) (see Lemma 4.3 of [11])

(1.9) n≤x f (n) n (log x) exp - 1 2 D(f, 1; x) 2 .
Note that the factor 1/2 inside the exponential on the right hand side of (1.9) is responsible for the weaker exponent δ g /2 in (1.4).

Goldmakher [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF] realized that one can obtain the optimal exponent δ g in (1.6) by replacing (1.9) by a Halász-type inequality for logarithmic mean values of multiplicative functions due to Montgomery and Vaughan [START_REF] Montgomery | Mean values of multiplicative functions[END_REF]. Combining Theorem 2 of [START_REF] Montgomery | Mean values of multiplicative functions[END_REF] with refinements of Tenenbaum (see Chapter III.4 of [START_REF] Tenenbaum | Introduction to analytic and probabilistic number theory[END_REF]) he deduced that

(1.10) n≤x f (n) n (log x) exp -M(f ; x, T ) + 1 T ,
for all f ∈ F and T ≥ 1, where

M(f ; x, T ) := min |t|≤T D(f, n it ; x) 2
(see Theorem 2.4 in [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF], which states this estimate with the weaker 1/ √ T in place of 1/T ; the superior bound stated here follows in the same way from the corresponding improved variant of this result in [START_REF] Tenenbaum | Introduction to analytic and probabilistic number theory[END_REF]).

Motivated by our investigation of character sums, we are interested in characterizing the functions f ∈ F that have a large logarithmic mean, in the sense that

(1.11) n≤x f (n) n (log x) α ,
for some 0 < α ≤ 1. Taking T = 1 in (1.10) shows that this happens only when f pretends to be n it for some |t| ≤ 1. However, observe that

n≤x n it n = x it -2 it it + O(1) min 1 |t| , log x ,
and hence f (n) = n it satisfies (1.11) only when |t| (log x) -α . By refining the ideas of Montgomery and Vaughan [START_REF] Montgomery | Mean values of multiplicative functions[END_REF] and Tenenbaum [START_REF] Tenenbaum | Introduction to analytic and probabilistic number theory[END_REF], we prove the following result, which shows that this is essentially the only case.

Theorem 1.6. Let f ∈ F and x ≥ 2. Then, for any real number T > 0 we have

n≤x f (n) n (log x) exp -M(f ; x, T ) + 1 T ,
where the implicit constant is absolute.

Taking T = c(log x) -α in this result (where c > 0 is a suitably small constant), we deduce that if f ∈ F satisfies (1.11), then f pretends to be n it for some |t| (log x) -α ; of course, this conclusion can only be deduced because of our larger range T > 0.

Theorem 1.6 will be one of the key ingredients in obtaining our superior bounds for M (χ) in Theorem 1.1.

Remark 1.7. To be more precise, in proving Theorem 1.1 we will use the following alternate form of Theorem 1.6: Let f ∈ F and x ≥ y ≥ 2 be real numbers. Then for any real number T > 0 we have (1.12)

n≤x n∈S(y) f (n) n (log y) exp (-M(f ; y, T )) + 1 T ,
where the implicit constant is absolute, and where here and throughout S(y) is the set of y-friable integers (also known as y-smooth integers), i.e., the set of positive integers n whose prime factors are all less than or equal to y. Theorem 1.6 obviously follows from the estimate (1.12) by simply taking y = x. On the other hand, let us assume Theorem 1.6, and for f ∈ F, let f y denote the completely multiplicative function defined on the primes by f y (p) = f (p) if p ≤ y, and f y (p) = 0 otherwise. Then, note that

M(f y ; x, T ) = M(f y ; y, T ) + y<p≤x 1 p = M(f ; y, T ) + log(log x/ log y) + O(1/ log y),
and hence by Theorem 1.6 we obtain n≤x n∈S(y)

f (n) n = n≤x f y (n) n (log y) exp -M(f ; y, T ) + 1 T ,
as desired.

Acknowledgements. We would like to thank the anonymous referee for carefully reading the paper, and for thoughtful remarks and suggestions.

Detailed statement of results

To explain the key ideas in the proofs of Theorems 1.1 and 1.3, we shall first sketch the argument of Granville and Soundararajan [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF]. Their starting point is Pólya's Fourier expansion (see section 9.4 of [START_REF] Montgomery | Multiplicative Number Theory I: Classical Theory[END_REF]) for the character sum n≤t χ(n), which reads

(2.1) n≤t χ(n) = τ (χ) 2πi 1≤|n|≤N χ(n) n 1 -e - nt q + O 1 + q log q N ,
where χ is a primitive character modulo q, e(x) := e 2πix and τ (χ) is the Gauss sum

τ (χ) := q n=1 χ(n)e n q .
Note that |τ (χ)| = √ q whenever χ is primitive.

Thus, in order to estimate M (χ), one needs to understand the size of the exponential sum

(2.2) 1≤|n|≤q χ(n) n e(nθ),
for θ ∈ [0, 1]. Montgomery and Vaughan [START_REF] Montgomery | Exponential Sums with Multiplicative Functions[END_REF] showed that this sum is small if θ belongs to a minor arc, i.e., θ can only be well-approximated by rationals with large denominators (compared to q). This leaves the more difficult case of θ lying in a major arc.

In this case, θ can be well-approximated by some rational b/r with suitably small r (compared to q). Granville and Soundararajan showed that in this case there is some large N (depending on θ, b, r and q) such that we can approximate the sum (2.2) by 1≤|n|≤N χ(n) n e(bn/r) = a mod r e(ab/r)

1≤|n|≤N n≡a mod r χ(n) n = 1 φ(r) ψ mod r a mod r ψ(a)e(ab/r) 1≤|n|≤N χ(n)ψ(n) n .
The bracketed term, a Gauss sum, is well understood; in particular it has norm ≤ √ r * , where r * is the conductor of ψ (see e.g., Theorem 9.7 of [START_REF] Montgomery | Multiplicative Number Theory I: Classical Theory[END_REF]), with equality if ψ is primitive. Thus, what remains to be determined in order to bound M (χ) from above and below, are suitable estimates for the sums

(2.3) 1≤|n|≤N χ(n)ψ(n) n
for each character ψ modulo r. Furthermore, observe that if χ and ψ have the same parity then this sum is exactly 0; hence, we only need to consider the case when χ and ψ have opposite parities.

2.1. Key Results Towards Theorem 1.1. Granville and Soundararajan's breakthrough stems from their discovery of a "repulsion" phenomenon between characters χ of odd order (which are necessarily of even parity), and characters ψ of odd parity and small conductor. A consequence of this phenomenon is that the sum (2.3) is small, allowing them to improve the Pólya-Vinogradov inequality in this case. More specifically, they show that if χ is a primitive character of odd order g ≥ 3 and ψ is an odd primitive character of conductor m ≤ (log y) A then (2.4) D(χ, ψ; y) 2 ≥ (δ g + o(1)) log log y (see Lemma 3.2 of [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF]). Inserting this bound in (1.9) allows them to bound the sum (2.3), from which they deduce the unconditional case of (1.4). The proof of the conditional part of (1.4) (when Q = log q) proceeds along the same lines, but uses an additional ingredient, namely the following approximation for the sum (2.2) (see Proposition 2.3 and Lemma 5.2 of [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF]) conditional on GRH:

(2.5)

n≤q χ(n) n e(nθ) = n≤q n∈S(y) χ(n) n e(nθ) + O y -1/6 (log q) 2 .
In [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF], Goldmakher showed that the bound (2.4) is best possible. Furthermore, in order to obtain the exponent δ g in (1.6), he used the inequality (1.10) to bound the sum (2.3) in terms of M(χψ; y, T ). However, to ensure that this argument works, one needs to show that the lower bound (2.4) still persists if we twist χψ by Archimedean characters n it for |t| ≤ T . By a careful analysis of M(χψ; y, T ), Goldmakher (see Theorem 2.10 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF]) proved that (under the same assumptions as (2.4))

(2.6) M(χψ; y, (log y) 2 ) ≥ (δ g + o(1)) log log y.

Thus, by combining this bound with (1.10) and following closely the argument in [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF], he was able to obtain (1.6).

In order to improve these results and establish Theorem 1.1, the first step is to obtain more precise estimates for the quantity M(χψ; y, T ). We discover that there is a substantial difference between the sizes of M(χψ; y, T 1 ) and M(χψ; y, T 2 ) if T 1 is small and T 2 is large (a result that may be surprising in view of (2.4) and (2.6)). In fact, we prove that there is a large secondary term of size (log 2 y)/k 2 (where k is the order of ψ) that appears in the estimate of M(χψ; y, T ) when T ≤ (log y) -c (for some constant c > 0), but disappears when T ≥ 1 (at least conditionally on GRH). Proposition 2.1. Let g ≥ 3 be a fixed odd integer, α ∈ (0, 1), and ε > 0 be small. Let χ be a primitive character of order g and conductor q. Let ψ be an odd primitive character modulo m, with m ≤ (log y) 4α/7 . Put k * := k/(k, g). Then we have

(2.7) M(χψ; y, (log y) -α ) ≥ δ g + απ 2 (1 -δ g ) 4(gk * ) 2 log 2 y -βε log m + O α (log 2 m) ,
where β = 1 if m is an exceptional modulus and β = 0 otherwise.

Proposition 2.2. Assume GRH. Let g ≥ 3 be a fixed odd integer. Let N be large, and y ≤ (log N )/10. Let ψ be an odd primitive character of conductor m such that exp 2 log 3 y ≤ m ≤ exp √ log y . Then, there exist at least √ N primitive characters χ of order g and conductor q ≤ N , such that for all T ≥ 1 we have

M(χψ; y, T ) ≤ δ g log 2 y + O (log 2 m) .
The secondary term of size (log 2 y)/k 2 in the right hand side of (2.7) is responsible for the additional saving of (log 2 Q) -1/4 (where Q is defined in (1.5)) in Theorem 1.1; clearly, it does not appear in Proposition 2.2, even in the range m (log 2 y) 1 2 -ε in which this secondary term is large. Note that when m is an exceptional modulus (see the precise definition in (6.3) below), there is an additional term that appears when estimating M(χψ; y, (log y) -α ) that has size log L(1, χ m ), where χ m is the exceptional character modulo3 m. In this case, the extra term ε log m on the right hand side of (2.7) is due to Siegel's bound

L(1, χ m ) ε m -ε .
To complete the proof of Theorem 1.1, we shall use our Theorem 1.6 to bound the sum (2.3), where we might choose T = (log y) -α to take advantage of Proposition 2.1. Note that in view of Proposition 2.2, one loses the additional saving of (log 2 Q) -1/4 in Theorems 1.1 if one simply uses (1.10) with T = (log y) 2 , as in [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF]. By using Theorem 1.6 and following the ideas in [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF], we prove the following result, which is a refinement of Theorem 2.9 in [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF].

Theorem 2.3. Let χ be a primitive character modulo q, and let Q be as in (1.5). Of all primitive characters with conductor below (log Q) 4/11 , let ξ modulo m be that character for which M χξ; Q, (log Q) -7/11 is a minimum. Then we have

M (χ) 1-χ(-1)ξ(-1) √ qm φ(m) (log Q) exp -M χξ; Q, (log Q) -7 11 + √ q (log Q) 9 11 +o(1) .
Note that δ g is decreasing as a function of g, so 1 -δ g ≥ 1 -δ 3 ≈ 0.827 > 9/11 for all g ≥ 3. Therefore, when χ is a primitive character of odd order g ≥ 3 and conductor q, we get the better bound M (χ) √ q (log Q)

9
11 +o(1) , unless ξ is odd and M χξ; Q, (log Q) -7 11 is small. Theorem 1.1 can be easily deduced from Theorem 2.3 and Proposition 2.1, both in the case in which GRH is assumed (with Q = log q), as well as unconditionally.

Proof of Theorem 1.1, assuming Proposition 2.1 and Theorem 2.3. Let ξ be the char- (1) , which trivially implies the result in this case since 1 -δ g > 9/11, for all g ≥ 3. Now, suppose that ξ is odd and let k be its order. We also let β = 1 if m is an exceptional modulus, and β = 0 otherwise. Then, combining Theorem 2.3 and Proposition 2.1

acter of conductor m ≤ (log Q) 4/11 that minimizes M χψ; Q, (log Q) -7/11 . If ξ is even, then it follows from Theorem 2.3 that M (χ) √ q(log Q) 9/11+o
(with α = 7/11) we obtain (2.8)

M (χ) √ qm φ(m) (log Q) 1-δg exp - c 1 (1 -δ g ) (gk * ) 2 log 2 Q + βε log m + O (log 2 m) √ q(log Q) 1-δg exp - 1 2 -βε log m - c 1 (1 -δ g ) g 2 m 2 log 2 Q + c 2 log 2 m ,
for some positive constants c 1 , c 2 , since φ(m) m/ log 2 m. One can easily check that the expression inside the exponential is maximal when m log 2 Q, and its maximum equals

- 1 4 - βε 2 log 3 Q + O (log 4 Q) .
Inserting this estimate in (2.8) completes the proof.

Key Results

Towards Theorem 1.3. We next discuss the ideas that go into the proof of Theorem 1.3. To obtain (1.7) under GRH, Goldmakher [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF] used the following result from [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF], which relates M (χ) to the distance between χ and any primitive character ψ with small conductor and parity opposite to that of χ.

Theorem 2.4 (Theorem 2.5 of [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF]). Assume GRH. Let χ mod q and ψ mod m be primitive characters such that χ(-1) = -ψ(-1). Then we have

M (χ) + √ qm φ(m) log 3 q √ qm φ(m) (log 2 q) exp -D(χ, ψ; log q) 2 .
Thus, it only remains to produce characters χ and ψ which satisfy the assumptions of Theorem 2.4, and for which the lower bound (2.4) is attained when y = log q. Using the Eisenstein reciprocity law, Goldmakher (see Proposition 9.3 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF]) proved that for any ε > 0, there exists an odd primitive character ψ modulo m ε 1, and an infinite family of primitive characters χ mod q of order g such that (2.9)

D(χ, ψ; log q) 2 ≤ (δ g + ε) log 3 q.
To remove the assumption of GRH, Goldmakher and Lamzouri [START_REF] Goldmakher | Lower bounds on odd order character sums[END_REF] (see Theorem 1 of [START_REF] Goldmakher | Lower bounds on odd order character sums[END_REF]) used ideas of Paley [START_REF] Paley | A theorem on characters[END_REF] to obtain a weaker version of Theorem 2.4 unconditionally. Namely, they showed that if χ is odd and ψ is even then

M (χ) + √ q √ qm φ(m) log 2 q log 3 q exp -D(χ, ψ; log q) 2 .
Although this bound is enough to obtain (1.7) unconditionally in view of (2.9), it is not sufficient to yield the precise estimate in Theorem 1.3, due to the loss of a factor of log 3 q over Theorem 2.4. Using a completely different method, based on zero density estimates for Dirichlet L-functions, we recover the original bound of Granville and Soundararajan [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF] unconditionally for all characters χ modulo q with q ≤ N , except for a small exceptional set of cardinality N ε . Our argument also gives a simple proof of Theorem 2.4, which exploits the natural properties of the values of Dirichlet L-functions at 1, and avoids the difficult study of exponential sums with multiplicative functions (see Section 6 of [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF]). Note that the statement of Theorem 2.4 trivially holds when m > log q, since D(χ, ψ; log q) 2 log 3 q. We thus only need to consider the case m ≤ log q.

Theorem 2.5. Let ε > 0 and let N be large. Let m ≤ log N be a positive integer and let ψ be a primitive character modulo m. Then, for all but at most N ε primitive characters χ modulo q with q ≤ N and such that χ(-1) = -ψ(-1) we have

(2.10) M (χ) + √ q ε √ qm φ(m) (log 2 q) exp -D(χ, ψ; log q) 2 .
Moreover, if we assume GRH, then (2.10) is valid for all primitive characters χ modulo q with q ≤ N , and the implicit constant in (2.10) is absolute.

To complete the proof of Theorem 1.3, we thus need to refine the estimate (2.9), and this can be achieved using the same ideas as in the proof of Proposition 2.1. However, Goldmakher's proof of (2.9) only produces an infinite sequence of primitive characters χ, and this is not enough to use in Theorem 2.5, due to the possible existence of an exceptional set of characters for which (2.10) does not hold. To overcome this difficulty, we use the results of [START_REF] Lamzouri | Large Values of L(1, χ) for kth order characters χ and applications to character sums[END_REF] to prove the existence of many primitive characters χ of order g and conductor q ≤ N such that when y log N , D(χ, ψ; y) is maximal.

Proposition 2.6. Let g ≥ 3 be a fixed odd integer. Let N be large and y ≤ (log N )/10 be a real number. Let m be a non-exceptional modulus such that m ≤ (log y) 4/7 , and let ψ be an odd primitive character of conductor m. Let k be the order of ψ and put k * = k/(g, k). Then, there exist at least √ N primitive characters χ of order g and conductor q ≤ N such that

(2.11) D(χ, ψ; y) 2 = 1 -(1 -δ g ) π/gk * tan(π/gk * ) log 2 y + O (log 2 m) .
Theorem 1.3 follows easily from Theorem 2.5 and Proposition 2.6.

Proof of Theorem 1.3, assuming Theorem 2.5 and Proposition 2.6. Let N be sufficiently large, and let y = (log N )/10. Let m be a prime number that is also a non-exceptional modulus, such that log 3 N ≤ m ≤ 2 log 3 N . One can make such a choice since it is known that there is at most one exceptional prime modulus between x and 2x for any x ≥ 2 (see Chapter 14 of [START_REF] Davenport | Multiplicative number theory[END_REF] for a reference). Let ψ be a primitive character modulo m of order k = φ(m) = m -1. Note that such a character is necessarily odd. By Proposition 2.6, there are at least √ N /2 primitive characters of order g and conductor

N 1/3 ≤ q ≤ N such that D(χ, ψ; y) 2 = 1 -(1 -δ g ) π/gk * tan(π/gk * ) log 2 y + O(log 2 m) = δ g log 3 q + O (log 5 q) ,
since gk * ≥ k and t/ tan(t) = 1+O(t 2 ). Thus, since D(χ, ψ; log q) 2 = D(χ, ψ; y) 2 +O(1), then it follows from Theorem 2.5 (with ε = 1/4) that there are at least √ N /3 primitive characters of order g and conductor N 1/3 ≤ q ≤ N such that

M (χ) √ qm φ(m) (log 2 q) 1-δg (log 4 q) O(1)
√ q(log 2 q) 1-δg (log 3 q) -1 4 (log 4 q) O(1) .

Remark 2.7. The difference in quality between the GRH conditional upper bound in Theorem 1.1, and the lower bound of Theorem 1.3, is less related to the dependence on twisting by archimedean characters forced upon us by applying Theorem 1.6, and more to do with the amount of precision that can be gotten in Proposition 2.1. Roughly speaking, the lower order terms arise from a careful analysis of the quantity (2.12)

a (mod m) (a,m)=1 w a    p≤z p≡a (mod m) 1 p - 1 φ(m) p≤z p m 1 p    , where {w a }a (mod m) (a,m)=1
is an explicit sequence of real numbers of absolute value ≤ 1 arising from the solution to an optimization problem (see Lemma 6.5 below), m ≤ (log q) 4/11 and log log z log log q (see the proof of Lemma 6.7 below). Since we do not know how to exploit the nature of the sequence {w a }a (mod m)

(a,m)=1
to obtain cancellations in the sum (2.12), we proceed by applying the triangle inequality and a result of Languasco and Zaccagnini (see Lemma 6.6 below) to this quantity to deduce the upper bound O(log 2 m). If we could replace this upper bound by O(1) then the difference of factors of size (log 4 q) O(1) between our upper and lower bound theorems would disappear.

2.3.

Structure of the Paper. In the remaining sections of the paper, our task will be to prove Theorem 1.6 as well as the key results of this section. In Section 3, we give the proof of Theorem 1.6, and we use this in Section 4 to deduce Theorem 2.3. In Section 5 we prove Theorem 2.5, and in Section 6 we prove Proposition 2.6. Finally, by combining the work of Section 6 and some ideas from [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF], we prove Propositions 2.1 and 2.2 in Section 7.

Logarithmic mean values of completely multiplicative functions:

proof of Theorem 1.6

The key ingredient to the proof of Theorem 1.6 is the following generalization of Theorem 2 of [START_REF] Montgomery | Mean values of multiplicative functions[END_REF].

Theorem 3.1. Let f ∈ F and x ≥ 2. Then, for any 0 < T ≤ 1 we have n≤x f (n) n 1 log x 1 1/ log x H T (α) α dα,
where

H T (α) = ∞ k=-∞ max s∈A k,T (α) F (1 + s) s 2 1/2 . and A k,T (α) = {s = σ + it : α ≤ σ ≤ 1, |t -kT | ≤ T /2}.
Montgomery and Vaughan [START_REF] Montgomery | Mean values of multiplicative functions[END_REF] established this result for T = 1, and a straightforward generalization of their proof allows one to obtain Theorem 3.1 for any 0 < T ≤ 1. For the sake of completeness we will include a full sketch of the necessary modifications to obtain this result. The only different treatment occurs when bounding the integrals on the left hand side of (3.1) below. Lemma 3.2. Let 0 < α, T ≤ 1. Then we have

(3.1) ∞ -∞ F (1 + α + it) α + it 2 dt + ∞ -∞ F (1 + α + it) (α + it) 2 2 dt H T (α) 2 α .
Proof. First, we have

∞ -∞ F (1 + α + it) α + it 2 dt = ∞ k=-∞ kT +T /2 kT -T /2 F (1 + α + it) α + it 2 dt ≤ ∞ k=-∞ max |t-kT |≤T /2 F (1 + α + it) α + it 2 kT +T /2 kT -T /2 F (1 + α + it) F (1 + α + it 2 dt.
To bound the integral on the right hand side of this inequality, we appeal to a result of Montgomery (see Lemma 6.1 of [START_REF] Tenenbaum | Introduction to analytic and probabilistic number theory[END_REF]) which states that if n≥1 a n n -s and n≥1 b n n -s are two Dirichlet series which are absolutely convergent for Re(s) > 1 and satisfy |a n | ≤ b n for all n ≥ 1, then we have

(3.2) u -u ∞ n=1 a n n σ+it 2 dt ≤ 3 u -u ∞ n=1 b n n σ+it 2 dt,
for any real numbers u ≥ 0 and σ > 1. This implies that

kT +T /2 kT -T /2 F (1 + α + it) F (1 + α + it) 2 dt = T /2 -T /2 ∞ n=1 Λ(n)f (n) n 1+α+ikT +it 2 dt T /2 -T /2 ζ (1 + α + it) ζ(1 + α + it) 2 dt T /2 -T /2 1 |α + it| 2 dt ≤ ∞ -∞ 1 α 2 + t 2 dt 1 α .
Hence, we deduce that

∞ -∞ F (1 + α + it) α + it 2 dt H T (α) 2 α .
To complete the proof, note that

∞ -∞ F (1 + α + it) (α + it) 2 2 dt ≤ ∞ k=-∞ max |t-kT |≤T /2 F (1 + α + it) α + it 2 kT +T /2 kT -T /2 1 |α + it| 2 dt H T (α) 2 α . Proof of Theorem 3.1. Let S(x) = n≤x f (n) n .
From the Euler product, |F (2)| > 0, so H T (α) 1. Thus, it is enough to prove the statement for x ≥ x 0 , where x 0 is a suitably large constant. Moreover, observe that Montgomery and Vaughan proved that for x ∈ B we have (see equations ( 7) and ( 8) of [START_REF] Montgomery | Mean values of multiplicative functions[END_REF])

|S(x)| log x x e |S(u)| u du+ 1 log x n≤x f (n) n (log n) log x n + 1 log x n≤x f (n) n log 2 x n .
Integrating the first integral by parts, we get , by the Cauchy-Schwarz inequality. Using Parseval's Theorem, Montgomery and Vaughan proved that (see equation ( 14) of [START_REF] Montgomery | Mean values of multiplicative functions[END_REF])

u e |S(t)| 2 (log t) 2 t dt ∞ -∞ F (1 + β + it) β + it 2 dt + ∞ -∞ F (1 + β + it) (β + it) 2 2 dt,
where β = 2/ log u. Appealing to Lemma 3.2 and making the change of variable α = 1/ log u in the integral of the right hand side of (3.3) we deduce that

(3.4) x e |S(u)| u du H T 2 log x + 1 1/ log x H T (2α) α dα.
Since H T (α) is decreasing as a function of α, we have

(3.5) H T 2 log x 2/ log x 1/ log x H T (α) α dα ≤ 1 1/ log x H T (α) α dα.
Combining (3.4) and (3.5) we get

x e |S(u)| u du 1 1/ log x H T (α) α dα.
Furthermore, Montgomery and Vaughan proved that (see pages 207-208 of [START_REF] Montgomery | Mean values of multiplicative functions[END_REF])

n≤x f (n) n (log n) log x n 1 β ∞ -∞ F (1 + β + it) β + it 2 dt 1/2 and n≤x f (n) n log 2 x n 1 β ∞ -∞ F (1 + β + it) (β + it) 2 2 dt 1/2
, where β = 2/ log x. Combining these bounds with Lemma 3.2 and equation (3.5) completes the proof.

In order to derive Theorem 1.6 from Theorem 3.1, we need to bound H T (α), and hence to bound |F (1 + s)| for Re(s) ≥ α. Tenenbaum (see Section III.4 of [START_REF] Tenenbaum | Introduction to analytic and probabilistic number theory[END_REF]) proved that for all y, T ≥ 2, and 1/ log y ≤ α ≤ 1, we have

(3.6) max |t|≤T |F (1 + α + it)| (log y) exp -M(f ; y, T ) .
However, this bound does not hold for all T > 0 and 1/ log y ≤ α ≤ 1. Indeed, taking f to be the Möbius function µ, α = 1/2, y large and T = 1/ log y shows that

max |t|≤T |F (1 + α + it)| ≥ |ζ(3/2)| -1 , while M(f ; y, T ) = min |t|≤1/ log y p≤y 1 + Re(p -it ) p = 2 p≤y 1 p + O(1) = 2 log log y + O(1),
and hence the right side of (3.6) is 1/(log y). Nevertheless, using Tenenbaum's ideas, we show that (3.6) is valid whenever T ≥ α. Lemma 3.3. Let y ≥ 2 and f ∈ F such that f (p) = 0 for p > y. Let F (s) be its corresponding Dirichlet series. Then, for all real numbers 0 < α ≤ 1 and T ≥ α we have

max |t|≤T F (1 + α + it)| (log y) exp -M(f ; y, T ) .
Proof. Note that

(3.7) M(f ; y, T ) = log 2 y -max |t|≤T Re p≤y f (p) p 1+it + O(1).
We first remark that the result is trivial if α ≤ 1/ log y, since in this case we have Appealing to (3.7) completes the proof.

log |F (1 + α + it)| = Re p≤y f (p) p 1+α+it + O(1) = Re
We finish this section by proving Theorem 1.6 in the equivalent form stated in Remark 1.7.

Proof of Theorem 1.6. First, observe that the result is trivial if T ≤ 1/ log x, since we have in this case

n≤x n∈S(y) f (n) n n≤x 1 n log x 1 T .
Moreover, if T > 1 then the result follows from (1.10) above. Thus, we may assume that 1/ log x < T ≤ 1.

Let g be the completely multiplicative function such that g(p) = f (p) for p ≤ y and g(p) = 0 otherwise, and let G be its corresponding Dirichlet series. Then, it follows from Theorem 3.1 that

(3.8) n≤x n∈S(y) f (n) n = n≤x g(n) n 1 log x 1 1/ log x H T (α) α dα,
where

H T (α) = ∞ k=-∞ max s∈A k,T (α) G(1 + s) s 2 1/2 .
First, observe that if |t -kT | ≤ T /2 and k = 0 then |t| |k|T . Moreover, uniformly for all t ∈ R, we have (3.9)

|G(1 + σ + it)| ≤ ζ(1 + σ) 1 σ .
We will first bound H T (α) when α > T . Using (3.9) we obtain in this case (3.10)

α 2 • H T (α) 2 ∞ k=-∞ max |t-kT |≤T /2 1 α 2 + t 2 |k|>α/T 1 k 2 T 2 + |k|≤α/T 1 α 2 1 αT .
Now, suppose that 0 < α ≤ T . To bound H T (α) in this case, we first use (3.9) for |k| ≥ 1. This gives

H T (α) 2 1 α 2 |k|≥1 1 k 2 T 2 + 1 α 2 max s∈A 0,T (α) |G(1 + s)| 2 1 (αT ) 2 + 1 α 2 max s∈A 0,T (α) |G(1 + s)| 2 .
Furthermore, by (3.9) and Lemma 3.3 we have max s∈A 0,T (α)

|G(1 + s)| max |t|≤T σ≥T |G(1 + σ + it)| + max |t|≤T α≤σ≤T |G(1 + σ + it)| 1 T + (log y) exp -M(g; y, T ) .
Since M(g; y, T ) = M(f ; y, T ) we deduce that for 0 < α ≤ T we have

(3.11) H T (α) 2 1 (αT ) 2 + (log y) 2
α 2 exp (-2M(f ; y, T )) .

Using (3.10) when T < α ≤ 1 and (3.11) when 1/ log x ≤ α ≤ T we get

1 1/ log x H T (α) α dα 1 T + log y • exp (-M(f ; y, T )) T 1/ log x 1 α 2 dα + 1 T 1/2 1 T 1 α 5/2 dα log x T + (log x)(log y) exp (-M(f ; y, T )) .
Inserting this bound in (3.8) yields the result.

Proof of Theorem 2.3

To prove Theorem 2.3, the general strategy we use is that of [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF] (with the refinements from [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF]), and it will be clear where we shall make use of Theorem 1.6. We will consider the conditional (on GRH) and unconditional results simultaneously, setting y := log 12 q if we are assuming GRH, and setting y := q otherwise. We recall here that y = Q in the unconditional case, and y = Q 12 on GRH, so that in all cases we have log y log Q. When χ is primitive and α ∈ R, we have this being trivial unconditionally, and on GRH is precisely the content of (2.5). Inserting this estimate in Pólya's Fourier expansion (2.1) gives

M (χ) √ q    max α∈[0,1] 1≤|n|≤q n∈S(y) χ(n) n 1 -e(nα) + 1    .
Therefore, to prove Theorem 2.3 it suffices to show that for all α ∈ [0, 1] we have (4.1)

1≤|n|≤q n∈S(y) χ(n) n e (nα) 1-χ(-1)ξ(-1) √ m φ(m) (log Q)e -M(χξ;Q,(log Q) -7/11 ) +(log Q) 9 11 +o(1)
.

Let α ∈ [0, 1] and R := (log Q) 5 . By Dirichlet's theorem on Diophantine approximation, there exists a rational approximation |α -b/r| ≤ 1/rR, with 1 ≤ r ≤ R and (b, r) = 1.

Let M := (log Q) 4/11 . We shall distinguish between two cases. If r ≤ M , we say that α lies on a major arc, and if M < r ≤ R we say that α lies on a minor arc. In the latter case, we shall use Corollary 2.2 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF], which is a consequence of the work of Montgomery and Vaughan [START_REF] Montgomery | Exponential Sums with Multiplicative Functions[END_REF]. Indeed, this shows that

1≤|n|≤q n∈S(y) χ(n) n e (nα) (log M ) 5/2 √ M log y + log R + log 2 y (log Q) 9 11 +o (1)
.

We now handle the more difficult case of α lying on a major arc. First, it follows from Lemma 4.1 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF] (which is a refinement of Lemma 6.2 of [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF]) that for N := min{q, |rα -b| -1 }, we have (4.2)

1≤|n|≤q n∈S(y) χ(n) n e(nα) = 1≤|n|≤N n∈S(y) χ(n) n e nb r + O (log R) 3/2 √ R (log y) 2 + log R + log 2 y = 1≤|n|≤N n∈S(y) χ(n) n e nb r + O (log 2 Q) .
We first assume that b = 0. In this case we can use an identity of Granville and Soundararajan (see Proposition 2.3 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF]) which asserts that (4.3)

1≤|n|≤N n∈S(y) χ(n) n e nb r = 1 -χ(-1)ψ(-1) d|r d∈S(y) χ(d) d • 1 φ(r/d) ψ mod r/d τ (ψ)ψ(b)    n≤N/d n∈S(y) χ(n)ψ(n) n    .
To bound the inner sum above, we appeal to Theorem 1.6 (in the form stated in Remark 1.7) with T = (log Q)

χ(n)ψ(n) n (log Q) • exp -M(χψ; Q, (log Q) -7/11 ) + (log Q) 7/11 .
We now order the primitive characters ψ (mod ) for ≤ M (including the trivial character ψ which equals 1 for all integers) as {ψ k } k , where

M(χψ k ; Q, (log Q) -7/11 ) ≤ M(χψ k+1 ; Q, (log Q) -7/11
), for all k ≥ 1. Note that ψ 1 = ξ, in the notation of Theorem 2.3. Furthermore, by a slight variation of Lemma 3.1 of [START_REF] Balog | Soundararajan Multiplicative functions in arithmetic progressions[END_REF] we have

M χψ k ; Q, (log Q) -7/11 ≥ 1 - 1 √ k log 2 Q + O log 2 Q . Therefore, if ψ (mod ) is induced by ψ k , then (4.5)
M χψ; Q, (log Q) -7/11 ≥ M χψ k ; Q, (log Q) -7/11 + O   p| 1 p   ≥ 1 - 1 √ k + o(1) log 2 Q,
since p| 1/p log 2 log 3 Q. Inserting this bound in (4.4), we deduce that the contribution of all characters ψ that are induced by some ψ k with k ≥ 3 to (4.3) is

(log Q) 7/11 d|r 1 dφ(r/d) ψ mod r/d |τ (ψ)| (log Q) 7/11 d|r √ r d 3/2 (log Q) 9/11 , since 1/ √ 3 < 7/11, |τ (ψ)| ≤ r/d, and r ≤ (log Q) 4/11
. Moreover, observe that there is at most one character ψ (mod r/d) such that ψ is induced by ψ 2 . Using (4.5), we deduce that the contribution of these characters to (4.3) is 1) .

(log Q) 1/ √ 2+o(1) d|r 1 d • r/d φ(r/d) (log Q) 1/ √ 2+o(1) log r (log Q) 1/ √ 2+o (
Thus, it now remains to estimate the contribution of the characters ψ mod r/d that are induced by ξ, recalling that ξ has conductor m. If m r, there are no such characters ψ and the theorem follows in this case. If m | r and ψ mod r/d is induced by ξ, then we must have d | (r/m). Furthermore, by Lemma 4.1 of [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF] we have

τ (ψ) = µ r dm ξ r dm τ (ξ).
Therefore, the contribution of these characters to (4.3) is (4.6)

1 -χ(-1)ξ(-1) ξ(b)τ (ξ) d|(r/m) d∈S(y) χ(d) d • 1 φ(r/d) µ r dm ξ r dm n≤N/d (n,r/d)=1 n∈S(y) χ(n)ξ(n) n .
Furthermore, it follows from Lemma 4.4 of [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF] that

n≤N/d (n,r/d)=1 n∈S(y) χ(n)ξ(n) n = n≤N (n,r/d)=1 n∈S(y) χ(n)ξ(n) n + O(log d) = p| r d 1 - χ(p)ξ(p) p n≤N n∈S(y) χ(n)ξ(n) n + O (log 2 Q) 2 .
Thus, in view of Theorem 1.6, we deduce that (4.6) is (4.7)

1 -χ(-1)ξ(-1) √ m (log Q)e -M(χξ;Q,(log Q) -7/11 ) + (log Q) 7/11 × d|(r/m) (r/(dm),m)=1 1 dφ(r/d) µ 2 r dm p| r dm 1 + 1 p .
Finally, by a change of variables a = r/(md), we obtain

d|(r/m) (r/(dm),m)=1 1 dφ(r/d) µ 2 r dm p| r dm 1 + 1 p = m rφ(m) a|(r/m) (a,m)=1 a φ(a) µ 2 (a) p|a 1 + 1 p ≤ 1 φ(m) • 1 r/m p|(r/m) 1 + p + 1 p -1 ≤ 4 φ(m) ,
since 2p/(p -1) ≤ p for all primes p ≥ 3. Combining this bound with (4.7), it follows that the contribution of the characters ψ that are induced by ξ to (4.3) is

1 -χ(-1)ξ(-1) √ m φ(m) (log Q)e -M(χξ;Q,(log Q) -7/11 ) + (log Q) 7/11 .
It thus remains to consider when b = 0, and hence r = 1. First, if ξ is identically 1 (so m = 1), then a trivial application of Theorem 1.6 shows that in this case

1≤|n|≤N n∈S(y) χ(n) n 1 -χ(-1) √ m φ(m) (log Q)e -M(χ;Q,(log Q) -7/11 ) + (log Q) 7/11 .
On the other hand, if ξ is not the trivial character, then it follows from (4.5) that 1) , which completes the proof of (4.1), and hence Theorem 2.3 as well.

M(χ; Q, (log Q) -7/11 ) ≥ 1 - 1 √ 2 + o(1)
χ(n) n (log Q) 1/ √ 2+o (

5.

A lower bound for M (χ): Proof of Theorem 2.5

The main ingredient in the proof of Theorem 2.4 (which corresponds to Theorem 2.5 of [START_REF] Granville | Large character sums: pretentiuous characters and the Pólya-Vinogradov theorem[END_REF]) is the approximation (2.5), which is valid under the assumption of GRH. To avoid this assumption and prove Theorem 2.5, we shall instead relate M (χ) to the values of certain Dirichlet L-functions at s = 1, and then use the classical zero-density estimates to approximate these L-functions by short Euler products, for "almost all" primitive characters χ. Proposition 5.1. Let q be large and m ≤ q/(log q) 2 . Let χ mod q and ψ mod m be primitive characters such that ψ(-1) = -χ(-1). Then we have

M (χ) + √ q √ qm φ(m)
• L 1, χψ .

Proposition 5.2. Fix 0 < ε < 1 and let A = 100/ε. Let N be large and m ≤ log N . Then for all but at most N ε primitive characters χ modulo q ≤ N we have

(5.1) L(1, χψ) = 1 + O 1 log N p≤log A N 1 - χ(p)ψ(p) p -1
.

for all primitive characters ψ modulo m. Moreover, if we assume GRH, then (5.1) is valid with A = 10, for all primitive characters χ modulo q ≤ N and ψ modulo m.

Proof of Theorem 2.5, assuming Propositions 5.1 and 5.2. Combining Propositions 5.1 and 5.2 we deduce that for all but at most N ε primitive characters χ modulo q with N ε/3 ≤ q ≤ N we have

(5.2) M (χ) + √ q √ qm φ(m) p≤log A N 1 - χ(p)ψ(p) p -1
with A = 100/ε. The first part of the theorem follows, upon noting that

p≤log A N 1 - χ(p)ψ(p) p -1 ε (log 2 q) • exp -D(χ, ψ; log q) 2 .
The second part follows along the same lines, since if we assume GRH then (5.2) holds with A = 10 for all primitive characters χ with conductor q ≤ N .

We have thus reduced our work to proving Propositions 5.1 and 5.2.

5.1. Proof of Proposition 5.1. To prove this result, we first need the following lemma.

Lemma 5.3. Let q be large and m ≤ q/(log q) 2 . Let χ be a character modulo q and ψ be a character modulo m such that χψ is non-principal. Then

L(1, χψ) = n≤q χ(n)ψ(n) n + O(1).
Proof. Note that χψ is a non-principal character of conductor at most qm ≤ (q/ log q) 2 . Therefore, using partial summation and the Pólya-Vinogradov inequality we obtain

q<n≤N χ(n)ψ(n) n = q<n≤N 1 n(n + 1) q<k≤n χψ(k) + O(1) 1,
and the claim follows.

Proof of Proposition 5.1. Taking N = q in (2.1) gives

M (χ) + log q √ q • max θ 1≤|n|≤q χ(n) n (1 -e (nθ)) .
Moreover, we observe that

b mod m ψ(b) 1≤|n|≤q χ(n) n 1 -e nb m = - 1≤|n|≤q χ(n) n b mod m ψ(b)e nb m = -τ (ψ) 1≤|n|≤q χ(n)ψ(n) n ,
which follows from the identity

b mod m ψ(b)e nb m = ψ(n)τ (ψ).
Since χ and ψ are primitive and m ≤ q/(log q) 2 then χψ is non-principal. Therefore, by Lemma 5.3 together with the fact that χψ(-1) = -1 we deduce that

1≤|n|≤q χ(n)ψ(n) n = 2 1≤n≤q χ(n)ψ(n) n = 2L(1, χψ) + O(1).
The result follows upon noting that

b mod m ψ(b) 1≤|n|≤q χ(n) n 1 -e nb m ≤ φ(m) • max θ 1≤|n|≤q χ(n) n (1 -e (nθ)) ,
and that |τ (ψ)| = √ m by the primitivity of ψ.

5.2. Proof of Proposition 5.2. In order to prove Proposition 5.2, we need some preliminary results.

Lemma 5.4. Let q be large and χ be a non-principal character modulo q. Let 2 ≤ T ≤ q 2 and X ≥ 2. Let 1 2 ≤ σ 0 < 1 and suppose that the rectangle {s : σ 0 < Re(s) ≤ 1, |Im(s)| ≤ T + 3} does not contain any zeros of L(s, χ). Then we have

log L(1, χ) = - p≤X log 1 - χ(p) p + O log X T + log q (1 -σ 0 )T + log q log T (1 -σ 0 ) 2 X (σ 0 -1)/2 .
Proof. Let α = 1/ log X. Then it follows from Perron's formula that

(5.3) 1 2πi α+iT α-iT log L(1 + s, χ) X s s ds = n≤X Λ(n) n log n χ(n) + O ∞ n=1 Λ(n) n 1+α log n min 1, 1 T log |X/n| = n≤X Λ(n) n log n χ(n) + O log X T + 1 X ,
by a standard estimation of the error term. Moreover, we observe that n≤X

Λ(n) n log n χ(n) = - p≤X log 1 - χ(p) p + O   ∞ k=2 p k >X 1 kp k   = - p≤X log 1 - χ(p) p + O X -1 2 .
We now move the contour in (5.3) to the line Re(s) = σ 1 -1, where

σ 1 = (1 + σ 0 )/2.
We encounter a simple pole at s = 0 that leaves a residue of log L(1, χ). Furthermore, it follows from Lemma 8.1 of [START_REF] Granville | Large character sums[END_REF] that for σ ≥ σ 1 and |t| ≤ T we have log L(σ + it, χ) log q σ -σ 0 log q 1 -σ 0 .

Therefore, we deduce that

1 2πi α+iT α-iT log L(1 + s, χ) X s s ds = log L(1, χ) + E,
where

E = 1 2πi σ 1 -1-iT α-iT + σ 1 -1+iT σ 1 -1-iT + α+iT σ 1 -1+iT log L(1 + s, χ) X s s ds log q (1 -σ 0 )T + log q log T (1 -σ 0 ) 2 X (σ 0 -1)/2 .
Since σ 0 ≥ 1/2, combining the above estimates completes the proof.

Lemma 5.5. Let ξ mod q and ψ mod m be primitive characters. Then, there is a unique primitive character χ such that χψ is induced by ξ if m | q, and no such character exists if m q.

Proof. Suppose that χψ is induced by ξ, where χ is a primitive character of conductor . Then we must have q = [ , m], and hence there is no such character χ if m q. Now, suppose that m | q, and let m = p a 1 1 • • • p a k k be its prime factorization. We construct χ in this case as follows. Since q = [ , m], then we have q = q 0

• p b 1 1 • • • p b k k
where (q 0 , m) = 1 and b j ≥ a j for all 1 ≤ j ≤ k, and = q 0

• p c 1 1 • • • p c k k where c j = b j if b j > a j and 0 ≤ c j ≤ a j if b j = a j . Now, since ξ is primitive then ξ = ξ • ξ 1 • • • ξ k
where ξ is a primitive character modulo q 0 and ξ j is a primitive character modulo p

b j j for 1 ≤ j ≤ k. Similarly, we have ψ = ψ 1 • • • ψ k and χ = χ • χ 1 • • • χ k
where χ is a primitive character modulo q 0 and ψ j , χ j are primitive characters modulo p a j j and p c j j respectively. Moreover, since ξ induces χψ then we must have χ = ξ, and ξ j induces χ j ψ j for all 1 ≤ j ≤ k. But this implies that χ j (n) = ξ j (n)ψ j (n) for all n such that p j n, and hence we deduce that there is only one choice for χ j since it is primitive. Since this holds for all 1 ≤ j ≤ k, the character χ is unique.

Proof of Proposition 5.2. By Bombieri's classical zero-density estimate (see Theorem 20 of [START_REF] Bombieri | Le grand crible dans la théorie analytique des nombres[END_REF]), we know that there are at most N 6(1-σ) (log N ) B primitive characters ξ with conductor q ≤ N log N and such that L(s, ξ) has a zero in the rectangle {s :

σ ≤ Re(s) ≤ 1, |Im(s)| ≤ N }, where B is an absolute constant. Let ξ 1 , • • • , ξ L be these characters with σ = 1-ε/20.
Then, it follows from the above argument that L N ε/2 . Recall that if ξ is a primitive character that induces ξ, then L(s, ξ) and L(s, ξ) have the same zeros in the half-plane Re(s) > 0. For a primitive character ψ modulo m, let E ψ denote the set of primitive characters χ modulo q with q ≤ N and such that χψ is induced by one of the characters ξ j for 1 ≤ j ≤ L. Let E m be the union over all primitive characters ψ modulo m of the sets E ψ . Then, it follows from Lemma 5.5 that

|E m | ≤ ψ mod m ψ primitive |E ψ | ≤ Lφ(m) N ε .
Let X = (log N ) A where A = 100/ε. If χ is a primitive character with conductor q ≤ N and such that χ / ∈ E m then it follows from Lemma 5.4 with T = X that for all primitive characters ψ modulo m we have

log L(1, χψ) = - p≤X log 1 - χ(p)ψ(p) p + O 1 log N ,
which implies (5.1). Finally, if we assume GRH, then this estimate is valid for all primitive characters χ modulo q ≤ N and ψ modulo m with X = (log N ) 10 by Lemma 5.4.

6.

Estimates for the distance D(χ, ψ; y): Proof of Proposition 2.6

For g ≥ 3, we let µ g denote the set of g-th roots of unity. Then, we observe that

D(χ, ψ; y) 2 = log log y - p≤y Re(χ(p)ψ(p)) p + O(1)
≥ log log y -

mod k max z∈µg∪{0} Re z • e - k p≤y ψ(p)=e ( k ) 1 p + O(1). (6.1)
We shall prove a lower bound for D(χ, ψ; y) 2 , which is a refined version of (2.4), by proving an asymptotic formula for the sum on the right hand side of (6.1). Proposition 6.1. Let g ≥ 3 be a fixed odd integer, and ε > 0 be small. Let ψ be an odd primitive character of conductor m and order k, and y be such that m ≤ (log y) 4/7 . Put k * = k/(g, k). Then (6.2)

mod k max z∈µg∪{0} Re z • e - k p≤y ψ(p)=e ( k ) 1 p = (1 -δ g ) π/gk * tan(π/gk * ) log 2 y + θε log m + O (log 2 m) ,
where θ = 0 if m in a non-exceptional modulus, and |θ| ≤ 1 if m is exceptional.

Combining this result with (6.1), we deduce the following corollary.

Corollary 6.2. Let g ≥ 3 be a fixed odd integer, and ε > 0 be small. Let ψ be an odd primitive character of conductor m and order k, and y be such that m ≤ (log y) 4/7 . Put k * = k/(g, k). Then, for any primitive character χ (mod q) of order g we have

D(χ, ψ; y) 2 ≥ 1 -(1 -δ g ) π/gk * tan(π/gk * ) log 2 y -βε log m + O (log 2 m) ,
where β = 0 if m is a non-exceptional modulus, and β = 1 if m is exceptional.

Corollary 6.2 shows that Proposition 2.6 is best possible, and will be the main ingredient in the proof of Proposition 2.1.

We say that m ≥ 1 is an exceptional modulus if there exists a Dirichlet character χ m and a complex number s such that L(s, χ m ) = 0 and

(6.3) Re(s) ≥ 1 - c log(m(Im(s) + 2))
for some sufficiently small constant c > 0. One expects that there are no such moduli, but what is known unconditionally is that if m is exceptional, then there is only one exceptional character χ m modulo m, which is quadratic, and for which L(s, χ m ) has a unique zero in the region (6.3) which is real and simple (this zero is called a Siegel zero).

6.1. Proof of Proposition 2.6 assuming Proposition 6.1. Let ψ be any odd character modulo m, with even order k. In choosing characters χ of order g and conductor q ≤ N that maximize the distance D(χ, ψ; y) with y ≤ (log N )/10, we will need to be able to choose the values of χ at the "small" primes p ≤ y. Using Eisenstein's reciprocity law and the Chinese Remainder Theorem, Goldmakher [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF] proved the existence of such characters. Lemma 6.3 (Proposition 9.3 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF]). Let g ≥ 3 be fixed, and y be large. Let {z p } p be a sequence of complex numbers such that z p ∈ µ g ∪ {0} for each prime p. There exists a positive integer q such that g p≤y p g p ≤ q ≤ 2g p≤y p g p, and a primitive Dirichlet character χ of order g and conductor q such that χ(p) = z p for all p ≤ y with p g. However, in order to prove Proposition 2.6 we need to find "many" such characters. This is needed in the proof of Theorem 1.3, since we must avoid those in the exceptional set of Theorem 2.5, which has size at most N ε . To this end we prove Lemma 6.4. Let N be large. Let g ≥ 3 be fixed. Let 2 ≤ y ≤ (log N )/10, and put z = (z p ) p≤y ∈ (µ g ∪ {0}) π(y) . There are

N 3/4 g 2π(y)+2 log 2 N
primitive Dirichlet characters χ of order g and conductor q ≤ N such that χ(p) = z p for each p ≤ y such that p g.

The special case z = 1 = (1, 1, . . . , 1) was proved by the first author in Lemma 2.3 of [START_REF] Lamzouri | Large Values of L(1, χ) for kth order characters χ and applications to character sums[END_REF], but the proof there does not appear to generalize to all z ∈ (µ g ∪ {0}) π(y) . However, we will show that one can combine the special case z = 1 with Lemma 6.3 in order to obtain the general case in Lemma 6.4.

Proof of Lemma 6.4. Let S z,g (N ) be the set of all characters χ of order g and conductor q ≤ N such that χ(p) = z p for all p ≤ y with p g. By Lemma 6.3, there exists and a primitive Dirichlet character ξ of order g and conductor such that ξ(p) = z p for all p ≤ y with p g. Moreover, one has log = p≤y log p + O g (1) = y(1 + o(1)), by the prime number theorem, and hence ≤ N 1/8 by our assumption on y.

On the other hand, Lemma 2.3 of [START_REF] Lamzouri | Large Values of L(1, χ) for kth order characters χ and applications to character sums[END_REF] implies that there are

N 3/4 g 2π(y)+2 log 2 N
primitive Dirichlet characters ψ n of order g and conductor n, such that n = q 1 q 2 where N 3/8 < q 1 < q 2 < 2N 3/8 are primes with p 1 ≡ p 2 ≡ 1 mod g, and such that ψ n (p) = 1 for all primes p ≤ y. Now, for any such n we have ( , n) = 1 since ≤ N 1/8 , and hence ψ n ξ is a primitive character of order g and conductor n ≤ N . Finally observe that ψ n ξ(p) = z p for each p ≤ y such that p g. Thus we deduce that ψ n ξ ∈ S z,g (N ) for every character ψ n , completing the proof.

We finish this subsection by proving Proposition 2.6.

Proof of Proposition 2.6, assuming Proposition 6.1. Let m be a non-exceptional modulus, and ψ be an odd primitive character modulo m with order k. For each 0 ≤ ≤ k -1, suppose that the maximum of Re zek for z ∈ (µ g ∪ {0}) π(y) is attained when z = z . Then, it follows from Lemma 6.4 that there are at least √ N primitive characters χ of order g and conductor q ≤ N such that

p≤y Re χ(p)ψ(p) p = mod k Re z • e - k p≤y ψ(p)=e ( k ) 1 p + O g (1)
.

The desired result then follows from (6.1) and Proposition 6.1.

6.2. Proof of Proposition 6.1. We first record the following lemma, which is a special case of Lemma 8.3 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF].

Lemma 6.5. Let g, k and k * be as in Proposition 6.1. Then

1 k mod k max z∈µg∪{0} Re z • e - k = (1 -δ g ) π/gk * tan(π/gk * ) .
Proof. This is Lemma 8.4 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF] (see also Lemma 7.2 below) with θ = 0.

In view of this lemma, our next task is to estimate the inner sum in the left hand side of (6.2). Since ψ is periodic modulo m we have In what follows we shall need estimates of Mertens type for sums of reciprocals of primes from specific arithmetic progressions a modulo m that are uniform in a range of the modulus m. Results of this type were established by Languasco and Zaccagnini [START_REF] Languasco | A note on Mertens' formula for arithmetic progressions[END_REF].

χ =χ 0 mod m χ(a) • log K(1, χ) L(1, χ) - 1 φ(m) (γ + log(φ(m)/m)) ,
where, for each non-principal character χ modulo q, K(s, χ) :

= ∞ n=1 k χ (n) n s
is an absolutely convergent Dirichlet series for Re(s) > 0, and k χ (n) is a completely multiplicative function defined as

(6.5) k χ (p) := p 1 -1 - χ(p) p 1 - 1 p -χ(p)
.

In order to study the asymptotic behaviour of the sum in (6.4), it will be crucial to have an upper bound for the average of |C m (a)|. Lemma 6.7. Fix ε > 0, and let m ≥ 3. Then, we have

a mod m (a,m)=1 |C m (a)| ≤ O(log 2 m), if m is a non-exceptional modulus, ε log m + O(log 2 m), if m is exceptional. Proof. First, since φ(m) m/ log 2 m then C m (a) = 1 φ(m) χ =χ 0 mod m χ(a) • log K(1, χ) L(1, χ) + O log 3 m φ(m) .
Let χ be a non-principal character modulo m. Then, it follows from the definition of k χ (p) and Taylor expansion that

|k χ (p)| 1 p .
Using this estimate, we get

log K(1, χ) = - p≤x log 1 - k χ (p) p + O p>x |k χ (p)| p = - p≤x log 1 - k χ (p) p + O 1 x .
Furthermore, it follows from (6.5) that

-log 1 - k χ (p) p + log 1 - χ(p) p = χ(p) log 1 - 1 p .
If χ is a non-exceptional character, then L(σ + it, χ) does not vanish when

σ ≥ 1 - c log(m(|t| + 2))
, We first consider the case when m is a non-exceptional modulus. Using the above estimates together with the orthogonality of characters we conclude that (6.7)

for
C m (a) = 1 φ(m) χ =χ 0 mod m χ(a) p≤X χ(p) log 1 - 1 p + O log 3 m φ(m) = p≤X p≡a mod m log 1 - 1 p - 1 φ(m) p≤X p m log 1 - 1 p + O log 3 m φ(m) .
Thus, we deduce in this case that

a mod m (a,m)=1 |C m (a)| ≤ - a mod m (a,m)=1 p≤X p≡a mod m log 1 - 1 p - p≤X log 1 - 1 p + O(log 3 m) log 2 m.
Now, suppose that m is an exceptional modulus, and let χ m be the exceptional character modulo m. The approximation (6.6) is valid for all non-principal characters χ = χ m modulo m. Furthermore, for χ = χ m we have Siegel's bound (see Theorem 11.4 in [START_REF] Montgomery | Multiplicative Number Theory I: Classical Theory[END_REF])

log L(1, χ m ) ≥ -ε log m + O ε (1),
and hence, instead of (6.6) we use that log

L(1, χ m ) + p≤X log 1 - χ m (p) p ≤ ε log m + O(log 2 m).
Thus, similarly to (6.7) we obtain in this case that

|C m (a)| ≤ - p≤X p≡a mod m log 1 - 1 p + ε log m φ(m) + O log 2 m φ(m) .
Summing over all reduced residue classes a modulo m gives the desired bound. Proposition 6.1 now follows readily.

Proof of Proposition 6.1. First, note that for each fixed modulo k, there are exactly φ(m)/k residue classes a modulo m such that (a, m) = 1 and ψ(a) = e k . This follows from the simple fact that the number of such residue classes equals the size of the kernel of ψ, and by basic group theory this is | (Z/mZ) * |/|Im(ψ)| = φ(m)/k. Thus, we deduce from (6.4) and Lemma 6.6 that

p≤y ψ(p)=e ( k ) 1 p = a mod m ψ(a)=e ( k )    log 2 y φ(m) -C m (a) + p≤y p≡a(m) log 1 - 1 p + 1 p + O 1 (log y) 4/7    = log 2 y k - a mod m ψ(a)=e ( k ) C m (a) + p≤y ψ(p)=e ( k ) log 1 - 1 p + 1 p + O φ(m) k(log y) 4/7 .
Summing over modulo k, and using Lemma 6.5, we get

mod k max z∈µg∪{0} Re z • e - k p≤y ψ(p)=e ( k ) 1 p = (1 -δ g ) π/gk * tan(π/gk * ) log 2 y + θ a mod m (a,m)=1 |C m (a)| + O (1) ,
for some complex number |θ| ≤ 1. Appealing to Lemma 6.7 completes the proof.

7.

Estimates for M(χψ; y, T ): Proofs of Propositions 2.1 and 2.2

Let χ be a primitive character modulo q of odd order g ≥ 3, and ψ be an odd primitive character of conductor m and order k. We shall prove the following result, from which we deduce Proposition 2.1.

Proposition 7.1. Let χ and ψ be as above, and α ∈ (0, 1). Let y ≥ exp(m

D(χ, ψ; x) 2 ≥ 1 -(1 -δ g ) π/gk * tan(π/gk * ) log 2 x -βε log m + O (log 2 m) ≥ δ g + π 2 (1 -δ g ) 4(gk * ) 2 log 2 x -βε log m + O (log 2 m) ,
since gk * ≥ 6, and u/ tan(u) ≤ 1 -u 2 /4 for 0 ≤ u ≤ π/6. Recall that M(χψ; y, (log y) -α ) = min |t|≤(log y) -α D(χψ, n it ; y) 2 . We shall consider the cases |t| ≤ (log y) -1 , and (log y) -1 < |t| ≤ (log y) -α separately. In the first case, we use p -it = 1 + O(|t| log p) to obtain Hence, the desired lower bound for D(χψ, n it ; y) 2 follows in this case from (7.1). Now, we suppose that (log y) -1 < |t| ≤ (log y) -α = 1/ log z. Then similarly to (7.2) one has

D(χψ, n it ; y) 2 = D(χ, ψ; z) 2 + z<p≤y 1 -Re(χ(p)ψ(p)p -it ) p + O(1).
In this case, the desired lower bound for D(χψ, n it ; y) 2 follows upon combining (7.1) with Proposition 7.1. This completes the proof of Proposition 2.1.

7.1. Proof of Proposition 7.1. To establish this result, we will follow the arguments in Section 8 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF]. First, we need the following lemmas.

Lemma 7.2 (Lemma 8.3 of [START_REF] Goldmakher | Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality[END_REF]). Let g ≥ 3 be odd, k ≥ 2 be even, and θ ∈ R. Put k * = k/(g, k). Then we have

1 k mod k max z∈µg∪{0} Re z • e θ - k = sin(π/g) k * tan(π/gk * ) F gk * (-gk * θ) ,
where F n (u) := cos(2π{u}/n) + tan(π/n) sin(2π{u}/n), and {u} is the fractional part of u.

For each 0 ≤ r ≤ R -1, we define , since φ(m)R (log y) 3 , and z = exp ((log y) α ) . Recall that for n ≥ 3, F n (u) = cos(2π{u}/n) + tan(π/n) sin(2π{u}/n) is bounded, periodic with period 1, and continuous on R (since lim u→1 -F n (u) = F n (0)). Moreover, F n is continuously differentiable on the interval (0, 1), and F n (u) = O(1/n) uniformly in u ∈ R \ Z. It follows from these facts, together with the mean value theorem, that |F n (a) -F n (b)| = O(|a -b|/n) for all a, b ∈ R such that |a -b| < 1, where the constant in the O is absolute. This shows that for all u ∈ [log x r , log x r+1 ) we have Throughout this subsection, we assume GRH. Let T ≥ 1, g ≥ 3 be fixed and odd, and let N be such that y ≤ (log N )/10. Let ψ be an odd primitive character of conductor m with 2 log 3 y ≤ log m ≤ √ log y. We note that for any f ∈ M we have M(f ψ; y, T ) ≤ D(f ψ, n i ; y) 2 .

F
Thus, the remainder of this subsection is devoted to showing that there are √ N primitive characters χ of order g and conductor q ≤ N such that (7.8) D(χψ, n i ; y) 2 = δ g log 2 y + O(log 2 m).

Proposition 2.2 then follows immediately from this.

To prove (7.8) we follow the proof of Proposition 7.1 in such a way that we achieve equality in all steps. Since the arguments here are similar to those in that proof, we omit some of the details. Let z := exp ((log m) 2 ) and y ≥ z. Let δ > 0 be a small parameter to be chosen and put R := log(y/z)/ log(1 + δ) as before. Set x 0 = z and x r := (1 + δ) r x 0 . Then, as log 2 m, it suffices to find at least √ N primitive characters χ of order g and conductor q ≤ N such that (7.9) z<p≤y Re(χ(p)ψ(p)p -i ) p = (1 -δ g ) log(log y/ log z) + O(1).

Let θ r := -log xr 2π , for each 0 ≤ r ≤ R -1. As in the proof of Proposition 7.1, when x r < p ≤ x r+1 we approximate p i by x i r , for each 0 ≤ r ≤ R -1. Let k be the order of ψ, and for each r let {z r, } ∈ (µ g ∪ {0}) k be chosen so as to maximize the sum By Lemma 6.4 there are at least √ N primitive characters χ of order g and conductor q ≤ N such that χ(p) = z r, whenever x r < p ≤ x r+1 , ψ(p) = e ( /k) and p g. For such characters, it follows that To estimate the inner sum, we use the following asymptotic formula, which is valid under the assumption of GRH: (1 + δ) -2r/5 δ + z -2/5 δ -1 .

1 1 /

 1 log x H T (α)α -1 dα is strictly increasing as a function of x, and |S(x) log x| is strictly increasing for x ∈ [n, n + 1), for all n ≥ 1. Hence it is enough to prove the result for x ∈ B where B = {x ≥ x 0 : |S(y) log y| < |S(x) log x| for all y < x}.

p

  p≤y f (p) p 1+it + O(1), which follows from the fact that |p α -1| α log p. Now, suppose that α ≥ 1/ log y and put A = exp(1/α). Then we have log |F (1+α+it)| = Re p≤y f (p) p 1+α+it +O(1) = Re p≤A f (p) p 1+α+it +O(1) = Re p≤A f (p) p 1+it +O(1), since p>A p -1-α 1 by the prime number theorem. Furthermore, for any |β| ≤ α/2 we have p≤A f (p) p 1+i(t+β) = p≤A f (p) p 1+it + O(1), |t| ≤ T -α/2 be a real number. Then, we have iα/2 -p -iα/2 i log p = α Re p≤A f (p) p 1+it + O α + p>A 1 p log p .Since p>A (p log p) -1 α by the prime number theorem, we deduce that Re p≤A

  ) + O(1),

Lemma 6 . 6 (

 66 Theorem 2 and Corollary 3 of [13]). Let x ≥ 3. Then, uniformly in m ≤ log x and reduced residue classes a modulo m, we have log 2 x -C m (a) + O (log log x) 16/5 (log x) 3/5 , where C m (a) is the Mertens constant of the residue class a modulo m, defined by C m (a) := 1 φ(m)

  some positive constant c. Therefore, taking T = m 2 , σ 0 = 1 -c/(4 log m) and X = exp((log m) 3 ) in Lemma 5.

1 -

 1 Recall that M(χψ; y, T ) = min |t|≤T D(χψ, n it ; y) 2 , and for 2 ≤ z < y D(χψ, n it ; y) 2 = D(χψ, n it ; z) 2 + z<p≤y Re(χ(p)ψ(p)p -it ) p .

(7. 2 )

 2 D(χψ, n it ; y) 2 = D(χ, ψ; y) 2 + O |t| p≤y log p p = D(χ, ψ; y) 2 + O(1).

1 = 1 + 1 S 1 F

 1111 Note that m ≤ (log x r ) 4/7 for each 0 ≤ r ≤ R. Thus, by the Siegel-Walfisz theorem (seeCorollary 11.19 in [17]), there is a positive constant b such thatxr <p≤x r+1 p≡a mod m log p = x r+1 -x r φ(m) + O x r exp -b log x r , for all 0 ≤ r ≤ R -1. Moreover, for x r < p ≤ x r+1 = (1 + δ)x r , we have 1 p = log p x r log x r 1 + p log p -x r log x r x r log x r -O(δ) log p x r log x r .Thus, combining these two statements, we getxr <p≤x r+1 p≡a mod m 1 p = 1 + O(δ) x r log x r xr <p≤x r+1 p≡a mod m log p = 1+O(δ) δ φ(m) log x r +O exp -b log z ,and upon summing over a modulo m such that ψ(a) = e k , of which there are φ(m)/k (as remarked in Section 3), we see thatS r ≤ 1 + O(δ) δ k log x r mod k max z∈µg∪{0} Re ze θ rk + O φ(m) exp -b log z ≤ 1 + O(δ) δ sin(π/g) k * tan(π/gk * ) F gk * (-gk * θ r ) log x r + O φ(m) exp -b log z by Lemma 7.2. Summing over 0 ≤ r ≤ R -1 this yields (7.7) 0≤r≤R-r ≤ 1+O(δ) δ sin(π/g) k * tan(π/gk * ) 0≤r≤R-gk * tgk * 2π log x r log x r +O exp -(log y) α 4

  Re z r, • e θ rk a mod m ψ(a)=e( /k) xr <p≤x r+1 p≡a mod m 1 p .

z<p≤y

  Re(χ(p)ψ(p)p-i ) p = 0≤r≤R-1 xr<p≤x r+1 Re(χ(p)ψ(p)x -i r ) p + O (δ) = 0≤r≤R-1 mod k Re z r, • e θ rk Re z r, • θ rk a mod m ψ(a)=e( /k)xr <p≤x r+1 p≡a mod m 1 p .

. 1 S

 1 xr <p≤x r+1 p≡a mod m log p = x r+1 -x r φ(m) + O x 1/2 r log 2 x r . log x r (1 + O (δ)) + O x -2/5r Using this estimate and proceeding exactly as in the proof of Proposition 7.1, we obtain that0≤r≤R-r = (1 + O (δ)) sin(π/g) k * tan(π/gk * ) log y log z F gk * gk * 2π u u du + O (E) ,whereE δ + z -2/50≤r≤R-1

  -7/11 . This implies that • exp -M(χψ; y, (log Q) -7/11 ) + (log Q) 7/11 .

	n≤N/d n∈S(y) (log y) Moreover, in the conditional case y = Q 12 , and thus we have χ(n)ψ(n) n
	M(χψ; y, (log Q) -7/11 ) ≥ M(χψ; Q, (log Q) -7/11 ) + O(1).
	Therefore, we get
	(4.4)
	n≤N/d
	n∈S(y)

  log 2 Q,

	and hence by Theorem 1.6 we get
	1≤|n|≤N
	n∈S(y)

  7/(4α) ) be a real number, and put z = exp ((log y) α ). Let t be a real number such that |t| ≤ (log y) -α .

	Then we have
	z<p≤y	1 -Re(χ(p)ψ(p)p -it ) p	≥ δ g log	log y log z	+ O(1).
	Proof of Proposition 2.1, assuming Proposition 7.1. Since m ≤ (log z) 4/7 , then it fol-
	lows from Corollary 6.2 that for all x ≥ z we have
	(7.1)

  gk * tgk We now estimate the integral in the main term above. One can easily check that for n ≥ 3, F n is an even function. Making the change of variable v := gk * |t| 2π u, and setting A := gk * |t| 2π log z and B := gk * |t| 2π log y, we get

	Combining these two facts, we obtain
			δ log x r	F gk *		tgk * 2π	log x r = 1 + O(δ)	log x r+1 log xr	F gk *	tgk * 2π	log x r	du u
			= 1 + O(δ)	log x r+1 log xr	F gk *	tgk * 2π	u	du u	+ O δ|t|	log x r+1 log xr	du u	.
	Summing over 0 ≤ r ≤ R -1, we get
		δ	0≤r≤R-1	F gk * tgk * 2π log x r log x r	= 1 + O(δ)	log y log z	F gk *	tgk * 2π	u	du u	+ O (δ) ,
	since	log y log x R dt/t		δ.
	log y log z	F gk *		tgk * 2π	u	du u	=	B A	F gk * (v)	dv v	≤	gk * π	tan	π gk * log	log y log z	+ O(1),
	by Lemma 7.3. Combining the above estimates with (7.6) and (7.7) we obtain
	S ≤ 1 + O(δ)	g π	sin	π g	log	log y log z
	Furthermore, we note that
											log x r+1 log xr	du u	= 1 + O(δ)	δ log x r	.

* 2π u = F gk * tgk * 2π log x r + O δ|t| . + O(1) ≤ (1 -δ g ) log log y log z + O(δ log 2 y).

Choosing δ = (log 2 y) -1 completes the proof of Proposition 7.1.

7.2. Estimating M(χψ; y, T ) for large twists T : Proof of Proposition 2.2. In this subsection, we prove Proposition 2.2.

Mathematics Subject Classification. Primary 11L40. The first author is partially supported by a Discovery Grant from the Natural Sciences and Engineering Research Council of Canada.1

By a Siegel zero, we mean a real zero β of the L-function L(s, ξ) of a real character ξ (mod m) such that β > 1 -c/ log(2m), c > 0 being a fixed small constant independent of m.

We will apply Proposition 2.1 towards proving Theorem 1.1 with α = 7/11. Thus, it is enough to assume there are no exceptional characters with modulus m ≤ (log q)

4/11 in order to avoid this issue.

In particular, for any 0 < A < B we have

and the constants in the O(1) error terms are absolute.

Proof. We first prove (7.3). Since F n is bounded and 1-periodic, we have

The second estimate (7.4) follows from observing that for u ∈ [0, 1) and n ≥ 3 we have

Finally, to prove (7.5) we consider the three cases 1 ≤ A < B, A < 1 < B, and A < B ≤ 1. The first case follows from (7.3), and the third follows from (7.4) upon using the inequality tan(π/n) ≥ π/n. Finally, in the second case we have

which implies the result since tan(π/n) ≥ π/n and -log A > 0.

Proof of Proposition 7.1. Let x 0 = z, and δ > 0 be a small parameter to be chosen. For each positive integer r ≤ R := log(y/z)/ log(1 + δ) , set x r := (1 + δ) r z. We consider the sum

Write θ r := -t log xr 2π , and note that if p ∈ (x r , x r+1 ] then

Here, note that if we transform the integral as we did in the proof of Proposition 7.1, i.e., with v := gk * u 2π then the bounds of integration, A := gk * log z 2π and B := gk * log y 2π are both larger than 1. Thus, applying Lemma 7.3, we get

Inserting this into our estimate for r S r , we get

Choosing δ = (log 2 y) -1 as before, and noting that z ≥ (log 2 y) 4 yields (7.9) for y sufficiently large. This completes the proof of (7.8), and thus of Proposition 2.2.