# Large sums of high order characters II

Alexander P. Mangerel and Yichen You  Department of Mathematical Sciences,
Durham University, Stockton Road, Durham, DH1 3LE, UK<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract.

Let $\chi$ be a primitive character modulo $q$, and let $\delta>0$. Assuming
that $\chi$ has large order $d$, for any $d$th root of unity $\alpha$ we
obtain non-trivial upper bounds for the number of $n\leq x$ such that
$\chi(n)=\alpha$, provided $x>q^{\delta}$. This improves upon a previous
result of the first author by removing restrictions on $q$ and $d$. As a
corollary, we deduce that if the largest prime factor of $d$ satisfies
$P^{+}(d)\to\infty$ then the level set $\chi(n)=\alpha$ has $o(x)$ such
solutions whenever $x>q^{\delta}$, for any fixed $\delta>0$.

Our proof relies, among other things, on a refinement of a mean-squared
estimate for short sums of the characters $\chi^{\ell}$, averaged over
$1\leq\ell\leq d-1$, due to the first author, which goes beyond Burgess’
theorem as soon as $d$ is sufficiently large. We in fact show the alternative
result that either (a) the partial sum of $\chi$ itself, or (b) the partial
sum of $\chi^{\ell}$, for “almost all” $1\leq\ell\leq d-1$, exhibits
cancellation on the interval $[1,q^{\delta}]$, for any fixed $\delta>0$.

By an analogous method, we also show that the Pólya-Vinogradov inequality may
be improved for either $\chi$ itself or for almost all $\chi^{\ell}$, with
$1\leq\ell\leq d-1$. In particular, our averaged estimates are non-trivial
whenever $\chi$ has sufficiently large _even_ order $d$.

##  1\. Introduction and main results

The objective of this paper is to improve the results of [12] on averages of
short and maximal sums of a Dirichlet character whose (group-theoretic) order
is large. In [12], the first author considered primitive Dirichlet characters
$\chi$ modulo a prime $q$ with order $d$, under the assumption that
$d=d(q)\rightarrow\infty$ as $q\rightarrow\infty$. In that work the first
author investigated how this assumption on $d$ influenced the sizes of the
short sums

$S_{\chi^{\ell}}(x):=\sum_{n\leq x}\chi^{\ell}(n),\quad x>q^{\delta}$

for arbitrary fixed $\delta>0$, and the maximal sums

$M(\chi^{\ell}):=\max_{1\leq t\leq q}\left|\sum_{n\leq
t}\chi^{\ell}(n)\right|$

for $1\leq\ell\leq d-1$. The methods of [12] had the defect that they only
yielded non-trivial results under the assumption that the least prime factor
of $d$ was also assumed to be large.

In this paper, we rectify this shortcoming by presenting (quantitatively
stronger) analogues of the theorems in [12] in which assumptions on the size
of the prime factors of $d$ are removed. Moreover, the results in this paper
apply to general moduli $q$, rather than just to prime $q$.
Our first main theorem is an alternative bound, which states that in the
régime that $d\rightarrow\infty$ with $q$, either $|S_{\chi}(x)|=o(x)$ or else
the mean-square average of the short character sums $S_{\chi^{\ell}}(x)$ with
length $x=q^{\delta}$ exhibits cancellation.

######  Theorem 1.1.

Let $q\geq 3$ and let $\chi$ be a primitive Dirichlet character modulo $q$
with order $d\geq 2$. Then there is an absolute constant $c>0$ such that if
$\tau\in(0,1/2)$,

$\delta:=\max\left\\{\left(\frac{\log\log(ed)}{c\log(ed)}\right)^{1/2},(\log
q)^{-c}\right\\},$

and $x>q^{\delta}$ then at least one of the following is true:

  1. (1)

$\chi$ itself satisfies

$\frac{1}{x}\left|\sum_{n\leq
x}\chi(n)\right|\ll_{\tau}\frac{1}{(\log\log(ed))^{1/6-\tau}};$

  2. (2)

we have the average bound

$\frac{1}{d}\sum_{1\leq\ell\leq d}\left|\frac{1}{x}\sum_{n\leq
x}\chi^{\ell}(n)\right|^{2}\ll_{\tau}\frac{1}{(\log\log(ed)^{1/6-\tau}}.$

This should be compared with [12, Thm. 2], in which the averaged bound was
only non-trivial under the assumption that $P^{-}(d)\rightarrow\infty$ with
$d$, and the savings only comparable if $P^{-}(d)\gg\log\log d$.
As in [12], a mean-square bound like Theorem 1.1 (together with some
additional inputs) may be used to prove a paucity phenomenon for the level
sets of $\chi$. In this direction, our second main theorem provides a non-
trivial upper bound for the cardinality of the set of solutions $n\leq x$ with
$\chi(n)=\alpha$, for any fixed $d$th order root of unity $\alpha$, whenever
$d\rightarrow\infty$ and $x>q^{\delta}$ for $\delta>0$ fixed but arbitrary.
This strictly generalises [12, Thm. 1], wherein the condition that $d$ be
squarefree had to be assumed.

######  Theorem 1.2.

There are absolute constant $c_{1},c_{2}>0$ such that the following holds.
Let $q\geq 3$ and let $\chi$ be a primitive Dirichlet character modulo $q$
with order $d\geq 2$. For each $z\geq 1$, define

$d_{z}:=\prod_{\begin{subarray}{c}p^{k}||d\\\
p>z\end{subarray}}p^{k},\quad\delta_{z}:=\max\left\\{\left(\frac{\log\log(ed_{z})}{c_{1}\log(ed_{z})}\right)^{1/2},(\log
q)^{-c_{1}}\right\\}.$

Then if $x>q^{\delta_{1}}$,

(1) $\max_{\alpha^{d}=1}\frac{1}{x}|\\{n\leq
x:\chi(n)=\alpha\\}|\leq\inf_{\begin{subarray}{c}1\leq z\leq\log\log(ed)\\\
x>q^{\delta_{z}}\end{subarray}}\left(\frac{1}{z}+O\left(\frac{1}{(\log\log(ed_{z}))^{c_{2}}}\right)\right).$

######  Remark 1.

Let us show that Theorem 1.2 indeed generalises [12, Thm. 1]. If $d$ is
squarefree and $z=\log\log(ed)$ then by the prime number theorem,

$d/d_{z}\leq\prod_{p\leq z}p\leq e^{2z}\asymp(\log d)^{2},$

provided $d$ is sufficiently large. The upper bound from Theorem 1.2 is thus
of quality $O(1/(\log\log(ed))^{c_{2}})$, which is comparable (albeit with a
less explicit $\log\log(ed)$ power) with [12, Thm. 1].

######  Remark 2.

To explain the form of the upper bound given in Theorem 1.2 it is helpful to
consider a case, not covered in [12, Thm. 1], where $d$ is a prime power, say
$d=2^{k}$. In this case, $d_{2}=1$, so that, taking $z\rightarrow 2^{-}$, the
upper bound provided by Theorem 1.2 is precisely

(2) $\max_{\alpha^{2^{k}}=1}\frac{1}{x}|\\{n\leq
x:\chi(n)=\alpha\\}|\leq\frac{1}{2}+o_{k\rightarrow\infty}(1)$

(and indeed this is the worst-possible bound that (1) provides in general). It
can be shown that Theorem 1.1 implies the bound

$\max_{\alpha^{2^{k}}=1}\frac{1}{x}|\\{n\leq
x:\chi(n)=\alpha\\}|\ll\frac{1}{(\log k)^{1/13}}\text{ whenever
}|S_{\chi}(x)|>\frac{x}{(\log k)^{2/13}},$

which is of course much stronger as $k\rightarrow\infty$. In the converse case
that $|S_{\chi}(x)|$ is small, however, the following heuristically plausible
scenario is consistent with (2).
Suppose that $\chi$ has order $2^{k}$, but satisfies $\chi(p)=\pm 1$ for all
$p\leq x$ and

$\sum_{\begin{subarray}{c}p\leq x\\\
\chi(p)=-1\end{subarray}}\frac{1}{p}\rightarrow\infty\text{ as
}k\rightarrow\infty.$

Thus, $\chi$ is a real-valued multiplicative function on $[1,x]$. By a theorem
of Hall and Tenenbaum [7], we obtain

$\left|S_{\chi}(x)\right|\ll x\exp\left(-\frac{1}{4}\sum_{p\leq
x}\frac{1-\chi(p)}{p}\right)=o_{k\rightarrow\infty}(x).$

Since $\chi(n)\in\\{-1,+1\\}$ for all $n\leq x$, this is equivalent to

$\max_{\alpha\in\\{-1,+1\\}}\frac{1}{x}|\\{n\leq
x:\chi(n)=\alpha\\}|=\frac{1}{2}+o_{k\rightarrow\infty}(1),$

which is precisely of the form (2).

We obtain the following straightforward consequence of Theorem 1.2.

######  Corollary 1.3.

Assume the notation and hypotheses of Theorem 1.2, and let

$\delta:=\max\left\\{\left(\frac{\log\log(eP^{+}(d))}{c_{1}\log(eP^{+}(d))}\right)^{1/2},(\log
q)^{-c_{1}}\right\\}.$

Then if $x>q^{\delta}$ we get

$\max_{\alpha^{d}=1}\frac{1}{x}|\\{n\leq
x:\chi(n)=\alpha\\}|\ll\frac{1}{(\log\log(eP^{+}(d)))^{c_{2}}}.$

Corollary 1.3 shows that as long as $P^{+}(d)\rightarrow\infty$ with $d$, the
level sets $|\\{n\leq x:\chi(n)=\alpha\\}|$ are sparse as soon as
$x>q^{\delta}$, for any fixed, but otherwise arbitrary, $\delta>0$. Note that
this property is fairly generic, only excluding orders $d$ that are very
smooth (and hence rare).
In [12] the first author also gave a non-trivial average bound for the maximal
character sums $M(\chi^{\ell})$, $1\leq\ell\leq d-1$. The Pólya-Vinogradov
inequality states that for a non-principal character $\psi$ of modulus $m$ we
have $M(\psi)\ll\sqrt{m}\log m$. It is a long-standing open problem to obtain
unconditional improvements (as $m\rightarrow\infty$) to this bound for general
$\psi$. In [12] (see Theorem 3 there), the bound

$\frac{1}{d}\sum_{1\leq\ell\leq d-1}M(\chi^{\ell})\ll\left(\sqrt{q}\log
q\right)\left(\frac{1}{P^{-}(d)}+\sqrt{\frac{\log\log\log q}{\log\log
q}}\right)$

was obtained by appealing to combinatorial arguments. Clearly, this bound is
non-trivial only when $d$ has no small prime factors and therefore must be
_odd_. Well-known work of Granville and Soundararajan [5] (with refinements in
[2] and [10]) previously showed that $M(\chi)=o(\sqrt{q}\log q)$ whenever
$\chi$ has _odd_ order $d=o(\sqrt{\log\log q})$, so that this result is _only
new_ when

$d\gg\sqrt{\log\log q}\text{ and }P^{-}(d)\rightarrow\infty\text{ as
}d\rightarrow\infty.$

Our next theorem remedies this situation, providing non-trivial bounds as soon
as $d\rightarrow\infty$ (including the case that $d$ is even).

######  Theorem 1.4.

Let $q\geq 3$ and let $\chi$ be a primitive Dirichlet character modulo $q$
with order $d\geq 2$. Then at least one of the following statements is true:

  1. (i)

$\chi$ itself satisfies

$M(\chi)\ll\frac{\sqrt{q}\log q}{(\log\log(ed))^{1/8}}$

  2. (ii)

we have

$\frac{1}{d}\sum_{1\leq\ell\leq d-1}M(\chi^{\ell})\ll\frac{\sqrt{q}\log
q}{(\log\log(ed))^{1/8}}.$

###  1.1. Proof strategy

Let us describe separately the strategy of proof of each of the main theorems
in this paper.

####  1.1.1. On averages of short character sums

The proof of Theorem 1.1 largely follows the line of attack of [12],
introducing refinements of the key lemmas at several junctures.
Ideally, we would like to prove that $|S_{\chi}(x)|=o_{d\rightarrow\infty}(x)$
when $x>q^{\delta}$ for $\delta\in(0,1)$, and the first alternative of Theorem
1.1 is consistent with this goal. We shall mainly discuss the consequences of
assuming that this alternative in fact fails.
As in [12], given small parameters $\delta,\varepsilon\in(0,1)$ we study the
structure of the “large spectrum” set

$\mathcal{C}_{d}(\varepsilon):=\\{1\leq\ell\leq
d-1:|S_{\chi^{\ell}}(x)|\geq\varepsilon x\\},\quad x>q^{\delta}.$

If $|\mathcal{C}_{d}(\varepsilon)|\leq\varepsilon d$ then the $L^{2}$ average
of $|S_{\chi^{\ell}}(x)|$ is $\ll\varepsilon$. Our main objective is to prove
that this upper bound on $|\mathcal{C}_{d}(\varepsilon)|$ indeed holds.
Suppose instead that $|\mathcal{C}_{d}(\varepsilon)|>\varepsilon d$. In this
case we use results from additive combinatorics to derive a structure theorem
for $\mathcal{C}_{d}(\varepsilon)$ (see Proposition 3.1). Precisely, we show
that there is $m=O_{\varepsilon}(1)$ such that the $m$-fold sumset

$m\mathcal{C}_{d}(\varepsilon):=\\{a_{1}+\cdots+a_{m}\pmod{d}:a_{j}\in\mathcal{C}_{d}(\varepsilon)\text{
for all }1\leq j\leq m\\}$

coincides with a large subgroup $H\leq\mathbb{Z}/d\mathbb{Z}$, and that for
each $\ell\in H$ the character $\chi^{\ell}$ “pretends to be” an archimedean
character $n^{it_{\ell}}$, with $\max_{\ell\in H}|t_{\ell}|\log
x=O_{\varepsilon}(1)$. As a consequence, we deduce that

(3) $\sum_{p\leq
x}\frac{1-\text{Re}(\chi(p)^{\ell})}{p}=O_{\varepsilon}(1)\text{ uniformly
over }\ell\in H.$

Unlike in [12] where $P^{-}(d)$ was assumed to be large, here the subgroup $H$
need not be the entirety of $\mathbb{Z}/d\mathbb{Z}$. Nevertheless, the fact
that $|H|\gg_{\varepsilon}d$ is what is crucial in the forthcoming analysis.
As in [12], the argument then splits according to the nature of the prime
level sets111As usual, given $t\in\mathbb{R}$ we write $e(t):=e^{2\pi it}$.

$S_{j}:=\\{p\leq x:\chi(p)=e(j/d)\\},\quad 1\leq j\leq d-1,$

and in particular the associated reciprocal sums

$\sigma_{j}(x):=\sum_{\begin{subarray}{c}p\leq x\\\ p\in
S_{j}\end{subarray}}\frac{1}{p},\quad 1\leq j\leq d-1.$

After showing that

$\Sigma_{\chi}(x):=\sum_{\begin{subarray}{c}p\leq x\\\ \chi(p)\neq
0,1\end{subarray}}\frac{1}{p}=\sum_{1\leq j\leq
d-1}\sigma_{j}(x)\rightarrow\infty\text{ as }d\rightarrow\infty$

(see Proposition 2.5, which is a very slight generalisation of [12, Thm. 1.1]
to composite moduli $q$), we consider two cases. First, if $\max_{1\leq j\leq
d-1}\sigma_{j}(x)$ is rather small compared to $\Sigma_{\chi}(x)$ then we show
that there is $\ell\in H$ such that (3) cannot hold (see Lemma 4.1). This
follows the lines of [12, Lem. 4.4]. Namely, having first observed that

$\sum_{p\leq x}\frac{1-\text{Re}(\chi^{\ell}(p))}{p}\geq 8\sum_{1\leq j\leq
d-1}\|\frac{j\ell}{d}\|^{2}\sigma_{j}(x),$

we use Fourier analysis to obtain a lower bound for the left-hand side sum for
_some_ $\ell\in H$ by showing a variance bound of the shape222Given
$t\in\mathbb{R}$ we write $\|t\|:=\min\\{\\{t\\},1-\\{t\\}\\}$.

$\frac{1}{|H|}\sum_{\ell\in H}\left(\sum_{1\leq j\leq
d-1}\left\|\frac{j\ell}{d}\right\|^{2}\sigma_{j}(x)-\frac{1}{12}\Sigma_{\chi}(x)\right)^{2}=o_{d\rightarrow\infty}(\Sigma_{\chi}(x)^{2}).$

Whereas the argument in [12, Lem. 4.4] made use of the fact that $P^{-}(d)$
was large, we manage to circumvent this assumption by a more careful argument.
In the case that $\sigma_{j_{0}}(x):=\max_{1\leq j\leq
d-1}\sigma_{j}(x)\gg\Sigma_{\chi}(x)$ we provide a quantitatively stronger
variant of [12, Prop. 4.5]. The idea there was to establish an asymptotic of
the shape

(4) $\sum_{n\leq x}\chi^{\ell}(n)=e(j_{0}\ell/d)\sum_{n\leq
x}\chi^{\ell}(n)+o_{d\rightarrow\infty}(x),$

by using the Turán-Kubilius inequality333A similar application of this idea
will be discussed in Section 1.1.3 below to show that most integers $n\leq x$
have $\sim\sigma_{j_{0}}(x)$ prime divisors $p\in S_{j_{0}}$. For each of
these prime divisors, if $n=mp$ then
$\chi^{\ell}(n)=e(j_{0}\ell/d)\chi^{\ell}(m)$, and using Lipschitz estimates
for multiplicative functions the partial sum $S_{\chi^{\ell}}(x)$ for $n\leq
x$ can be well-approximated by the sum $S_{\chi^{\ell}}(x/p)$ for $m\leq x/p$
(as long as $p$ is not too large).
Our refinement of this idea, found in Proposition 4.2 below, generalises this
from single primes $p\in S_{j_{0}}$ to products of $k$ prime factors $p\in
S_{j_{0}}$, where $k=o(\sqrt{\sigma_{j_{0}}(x)})$. The flexibility in the
choice of $k$ is what is ultimately responsible for the improved exponent of
$\log\log d$ in Theorem 1.1, relative to [12, Thm. 2].
Note that (4) is only useful in proving
$|S_{\chi^{\ell}}(x)|=o_{d\rightarrow\infty}(x)$ provided that

$|1-e(j_{0}\ell/d)|\asymp\|j_{0}\ell/d\|\gg 1.$

In [12] the condition $P^{-}(d)\rightarrow\infty$ proved advantageous in
showing that this was the case for _most_ $\ell\in H$. Indeed, since $1\leq
j_{0},\ell<d$, we have $\gamma:=(j_{0},d)\leq d/P^{-}(d)$. Setting
$a=j_{0}/\gamma$ and $d^{\prime}=d/\gamma$, it follows that

$\left\|\frac{j_{0}\ell}{d}\right\|=\left\|\frac{a\ell}{d^{\prime}}\right\|,$

and it can be shown that when $d^{\prime}$ is large, _most_ choices of $\ell$
satisfy $\|j_{0}\ell/d\|\gg_{\varepsilon}1$, essentially because the range
$[\varepsilon d^{\prime},(1-\varepsilon)d^{\prime}]$, say, is large.
This certainly fails if $P^{-}(d)$ is small. For instance, if $d$ is even then
it is plausible that $j_{0}=d/2$, and so $\|j_{0}\ell/d\|=0$ for approximately
half of all $1\leq\ell\leq d-1$. The issue here is that $\gamma=(j_{0},d)$ is
excessively large, i.e., of size $\gg d$, in this case. On the other hand, we
show that $\gamma$ is rather smaller than $d$ whenever $|S_{\chi}(x)|$ is
large, and in this case we may again conclude that
$\|j_{0}\ell/d\|\gg_{\varepsilon}1$ for most $1\leq\ell\leq d-1$. This is
precisely the reason for assuming that $|S_{\chi}(x)|$ is large in the second
alternative in Theorem 1.1.

####  1.1.2. A new bound for level sets of $\chi$

To prove Theorem 1.2 we employ three observations (see Lemmas 5.1 and 5.2
below), two of which are already present in [12]. Firstly, if $b|d$, $\alpha$
is a $d$th order root of unity and $\beta:=\alpha^{b}$ then we have the
trivial inclusion

$\\{n\leq x:\chi(n)=\alpha\\}\subseteq\\{n\leq x:\chi^{b}(n)=\beta\\}.$

This allows us to replace a bound for the level sets of $\chi$ of order $d$ by
those of $\psi:=\chi^{b}$ of some order $d^{\prime}=d/b$ dividing $d$. As
discussed below, this sometimes presents an advantage.
Secondly, the level sets of $\chi$ can be linked to the $L^{2}$ averages of
the powers $\chi^{\ell}$. This follows by orthogonality modulo $d$ from the
formula

$S_{\chi^{\ell}}(x)=\sum_{n\leq
x}\chi^{\ell}(n)=\sum_{\alpha^{d}=1}\alpha^{\ell}|\\{n\leq
x:\chi(n)=\alpha\\}|.$

Therefore, whenever a non-trivial bound is available for the $L^{2}$ average

(5) $\frac{1}{d}\sum_{1\leq\ell\leq d}|S_{\chi^{\ell}}(x)|^{2},$

we obtain correspondingly non-trivial bounds for all level sets $|\\{n\leq
x:\chi(n)=\alpha\\}|$. By Theorem 1.1 this is true as long as $|S_{\chi}(x)|$
is large.
The third key observation concerns the converse case, namely when
$|S_{\chi}(x)|$ is small (and therefore non-trivial bounds for (5) do not
follow from Theorem 1.1). In this case, we may arrive at a bound for the level
sets by interpreting the event $\chi(n)=\alpha=e(a/d)$, $0\leq a\leq d-1$, as
a constraint on the distribution of the complex argument $\theta_{n}\in[0,1)$
of $\chi(n)$ (provided $(n,q)=1$), i.e.,

$\chi(n)=e(\theta_{n})\text{ with
}\theta_{n}\in\left[\frac{a}{d},\frac{a+1}{d}\right).$

Since this interval has measure $1/d$, if $\theta_{n}$ were uniformly
distributed we would expect the number of such $n\leq x$ to have size $\sim
x/d$. Using the Erdős-Turán inequality to control the deviation from this
heuristic, we show that $|\\{n\leq x:\chi(n)=\alpha\\}|$ may be bounded above
by

(6) $\frac{x}{d}+\frac{x}{K+1}+O\left(\sum_{1\leq k\leq
K}\frac{1}{k}|S_{\chi^{k}}(x)|\right)\text{ for any }K\geq 1.$

Knowing that $|S_{\chi}(x)|$ is small, we use the pretentious theory of
multiplicative functions to show (in certain key cases where upper bounds for
(5) are not available) that in fact $|S_{\chi^{k}}(x)|$ is also small whenever
$1\leq k<P^{-}(d)$. This can be understood as being due to

$\chi^{k}(p)\neq 1\text{ whenever }\chi(p)\neq 1\text{ and }1\leq k<P^{-}(d),$

so that $\chi^{k}$ retains much of the oscillation exhibited when $\chi$ has
small partial sums. The upshot of this is that we may then select
$K=P^{-}(d)-1$ in (6). This bound presents no advantage when $P^{-}(d)$ is
quite small, but can be strengthened in the case that the contribution to $d$
from its small prime factors is small. More precisely, applying the first
observation above with

$d^{\prime}=\prod_{\begin{subarray}{c}p^{k}||d\\\
p>z\end{subarray}}p^{k}\text{ for any }1\leq z\leq\log\log(ed)$

allows us (after replacing $d$ and $\chi$ by $d^{\prime}$ and
$\chi^{d/d^{\prime}}$, respectively) to apply (6) with
$K=P^{-}(d^{\prime})-1>z-1$ instead. This improves the bound, as long as
$d^{\prime}$ is sufficiently large.

####  1.1.3. On averages of maximal sums

Our expectation is that the first alternative of Theorem 1.4 always holds, but
here we will mainly focus on the consequences if it fails. As in [12], given a
small parameter $\varepsilon>0$, we investigate the structure of

$\displaystyle\mathcal{L}_{d}(\varepsilon):=\\{1\leq\ell\leq
d-1:|M(\chi^{\ell})|\geq\varepsilon\sqrt{q}\log q\\}.$

If $|\mathcal{L}_{d}(\varepsilon)|\leq\varepsilon d$ then the average size of
$M(\chi^{\ell})$ is $\ll\varepsilon\sqrt{q}\log q$. In other words, for most
$1\leq\ell\leq d-1$, $M(\chi^{\ell})$ admits a sharper upper bound than what
the Pólya-Vinogradov inequality provides. Our goal is to show that
$|\mathcal{L}_{d}(\varepsilon)|$ is indeed of size $O(\varepsilon d)$.

By Proposition 2.1 and Lemma 2.2, bounding $M(\chi^{\ell})$ reduces to the
estimation of a logarithmic sum

$\displaystyle L_{\chi^{\ell}\overline{\gamma}_{\ell}}(N):=\sum\limits_{n\leq
N}\frac{\chi^{\ell}\overline{\gamma}_{\ell}(n)}{n},$

where $\gamma_{\ell}$ is some Dirichlet character of small conductor
determined by $\chi^{\ell}$, and $N=N_{\ell}\in[1,q]$. In turn, this can be
related via standard estimates for logarithmic averages of multiplicative
functions, to the prime sum

$\displaystyle\sum\limits_{p\leq
q}\frac{1-\text{Re}(\chi^{\ell}\overline{\gamma}_{\ell}(p))}{p}.$

In the same vein as the structure theorem for $\mathcal{C}_{d}(\varepsilon)$,
which involved classifying those archimedean characters $n^{it_{\ell}}$ to
which the characters $\chi^{\ell}$, $\ell\in\mathcal{C}_{d}(\varepsilon)$ were
pretentious, we show a _non-archimedean_ analogue of this for
$\mathcal{L}_{d}(\varepsilon)$. Namely, we show that there are
$m,g=O_{\varepsilon}(1)$ such that $m\mathcal{L}_{d}(\varepsilon)$ is a
subgroup $H=\langle g\rangle\leq\mathbb{Z}/d\mathbb{Z}$, where
$|H|=d/g\gg_{\varepsilon}d$. Assuming $\chi^{g}$ “pretends to be” a primitive
Dirichlet character $\xi$ of order $r$, each $g\ell\in H$ the character
$\chi^{g\ell}$ also “pretends to be” $\xi^{\ell}$ (in a manner that is uniform
in $\ell$). As a result, setting $\psi:=\chi^{g}\overline{\xi}$ we show that

$\displaystyle\max_{\ell\in H}\sum\limits_{p\leq
x}\frac{1-\text{Re}(\psi^{\ell}(p))}{p}=O_{\varepsilon}(1).$

which is of the same shape as (3). We have thus reduced matters in this
problem to a situation similar to that of the short character sums problem,
replacing $\chi^{\ell}$ by $\psi^{\ell}$, for $\ell\in H$. By considering the
prime level sets of $\psi$, we can apply analogous arguments to those used in
the proof of Theorem 1.1.
More precisely, let $\omega=e(1/r)$ and

$\tilde{\sigma}_{j_{0}}:=\max\limits_{1\leq
j<r}\sum\limits_{\begin{subarray}{c}p\leq q,\\\
\psi(p)=\omega^{j}\end{subarray}}\frac{1}{p}.$

The case when $\tilde{\sigma}_{j_{0}}$ is small relative to $\Sigma_{\psi}(q)$
is completely analogous to the corresponding case in the proof of Theorem 1.1,
and so we focus here on the case that
$\tilde{\sigma}_{j_{0}}\gg\Sigma_{\psi}(q)$. We seek to obtain an asymptotic
formula of the type in (4), for the logarithmic sums
$L_{\psi^{\ell}}(N_{\ell})$. In fact, we prove that

(7) $\displaystyle
L_{\psi^{\ell}}(N_{\ell})=e(j_{0}\ell/d)L_{\psi^{\ell}}(N_{\ell})+o\left(\frac{\log
N_{\ell}}{\sqrt{\tilde{\sigma}_{j_{0}}}}\right),$

where $|L_{\psi^{\ell}}(N_{\ell})|=\max\limits_{1\leq N\leq
q}|L_{\psi^{\ell}}(N)|$. The idea is to view $\tilde{\sigma}_{j_{0}}$ as the
average value of the completely additive function

$\displaystyle\Omega_{j_{0}}(n)=\sum\limits_{\begin{subarray}{c}p^{k}|n,\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}1,$

and by the Turán-Kubilius inequality we have
$\Omega_{j_{0}}(n)\sim\tilde{\sigma}_{j_{0}}$ for _most_ $n\leq q$. In
particular, we find that

$L_{\psi^{\ell}}(N_{\ell})\sim\frac{1}{\tilde{\sigma}_{j_{0}}(n)}\sum_{n\leq
N_{\ell}}\frac{\psi^{\ell}(n)\Omega_{j_{0}}(n)}{n}\sim\frac{1}{\tilde{\sigma}_{j_{0}}}\sum_{\begin{subarray}{c}p\leq
N_{\ell}\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{\psi^{\ell}(p)}{p}\sum_{m\leq
N_{\ell}/p}\frac{\psi^{\ell}(m)}{m}=\frac{\omega^{\ell
j_{0}}}{\tilde{\sigma}_{j_{0}}}\sum_{\begin{subarray}{c}p\leq N_{\ell}\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{1}{p}L_{\psi^{\ell}}(N_{\ell}/p).$

Using the trivial estimate
$L_{\psi^{\ell}}(N_{\ell}/p)=L_{\psi^{\ell}}(N_{\ell})+O(\log p)$ and Mertens’
theorem, we arrive at (7). (While this gives a quantitatively weaker estimate
than what might be obtained by the more general, yet technical, method of
Proposition 4.2, the argument is shorter and hopefully slightly more
illuminating than that of Proposition 4.2.)

In [12], only the size of $\mathcal{L}_{d}(\varepsilon)$ was studied, using
the ideas of [5] to show that $\mathcal{L}_{d}(\varepsilon)$ is a
$2k$-_sumfree set_ (in the sense of additive combinatorics, see e.g. [1, Thm.
3] and [8, Thm. 2.4]). Bounds for $|\mathcal{L}_{d}(\varepsilon)|$ crucially
depended in this way on the divisors of $d$, and ultimately on whether or not
$P^{-}(d)$ was large. Drawing on the ideas used to prove Theorem 1.1, we
obtain significantly more structural information about
$\mathcal{L}_{d}(\varepsilon)$, which enables us to better estimate its size.
In this way, we refine [12, Thm. 3] in a way that does not rely on $P^{-}(d)$
being large.

### Outline of the paper

The paper is organised as follows. In Section 2 we collect several results
about character sums, and estimates for Cesàro and logarithmic mean values of
multiplicative functions. We also state and prove a slight refinement of an
estimate from [12] establishing a lower bound for the number of primes $p\leq
q^{\delta}$ with $\chi(p)\neq 0,1$.
In Section 3 we establish structure theorems for the respective sets
$\mathcal{C}_{d}(\varepsilon)$ and $\mathcal{L}_{d}(\varepsilon)$ of powers
$1\leq\ell\leq d-1$ for which $|S_{\chi^{\ell}}(x)|\geq\varepsilon x$ and for
which $M(\chi^{\ell})>\varepsilon\sqrt{q}\log q$. In Section 4, the structure
theorem for $\mathcal{C}_{d}(\varepsilon)$ is applied to study the Cesàro
averages of the short sums $S_{\chi^{\ell}}(x)$. The outcome of the analysis
in that section is Theorem 1.1. In Section 5, we use Theorem 1.1 and several
additional ideas to derive Theorem 1.2 and its corollary, Corollary 1.3.
Finally, in Section 6 we use our structure theorem for
$\mathcal{L}_{d}(\varepsilon)$ to establish Theorem 1.4.

### Acknowledgments

We thank Youness Lamzouri and Oleksiy Klurman for useful comments and
encouragement.

##  2\. Auxiliary results

###  2.1. Character sums and mean values of multiplicative functions

In this section we collect various results about mean values of multiplicative
functions in general, and their connection to character sums in particular.
Our first lemma shows that if a character $\psi$ has a large maximal sum
$M(\psi)$ then $M(\psi)$ is asymptotic to a logarithmically-averaged partial
sum determined by $\psi$.

######  Proposition 2.1 (Prop. 2.1 of [3]).

Fix $\Delta\in(2/\pi,1)$ and let $\psi$ be a character modulo $m$. Then

$M(\psi)\gg\sqrt{m}(\log m)^{\Delta}$

if and only if there is a primitive character $\xi\pmod{\ell}$ with

$\xi(-1)=-\psi(-1)\text{ and }\ell\leq(\log m)^{2(1-\Delta)}(\log\log m)^{4}$

such that

$\max_{1\leq N\leq q}\left|\sum_{n\leq
N}\frac{(\psi\overline{\xi})(n)}{n}\right|\gg\frac{\phi(\ell)}{\sqrt{\ell}}(\log
m)^{\Delta}.$

In this case there is a $c_{\psi,\xi}\in[1/2,3]$ such that as
$m\rightarrow\infty$,

$M(\psi)=(c_{\chi,\xi}+o(1))\frac{\sqrt{m\ell}}{\pi\phi(\ell)}\max_{1\leq
N\leq q}\left|\frac{(\psi\overline{\xi})(n)}{n}\right|.$

Our next lemma indicates how the estimation of the logarithmically-averaged
partial sums of a bounded multiplicative function $f$ are quantitatively
controlled by the distribution of the prime values $(f(p))_{p}$.
In the sequel we write $\mathbb{U}:=\\{z\in\mathbb{C}:|z|\leq 1\\}$ to denote
the closed unit disc in the complex plane. For $y\geq 2$ we define the
pretentious distance (at scale $y$) between functions
$f,g:\mathbb{N}\rightarrow\mathbb{U}$ by

$\mathbb{D}(f,g;y):=\left(\sum_{p\leq
y}\frac{1-\text{Re}(f(p)\overline{g}(p))}{p}\right)^{1/2}.$

See [12, Sec.3.1] for a discussion of the properties of the pretentious
distance.

######  Lemma 2.2.

Let $f:\mathbb{N}\rightarrow\mathbb{U}$ be multiplicative and let $x\geq 1$.
Then

$\max_{1\leq y\leq x}\left|\sum_{n\leq y}\frac{f(n)}{n}\right|\ll 1+(\log
x)e^{-\frac{1}{2}\mathbb{D}(f,1;x)^{2}}.$

###### Proof.

Let $y_{0}\in[1,x]$ maximise the left-hand side. Applying [5, Lem. 4.3]], we
obtain

$\max_{1\leq y\leq x}\left|\sum_{n\leq
y}\frac{f(n)}{n}\right|=\left|\sum_{n\leq y_{0}}\frac{f(n)}{n}\right|\ll
1+(\log y_{0})e^{-\frac{1}{2}\mathbb{D}(f,1;y_{0})^{2}}.$

Since $1+\text{Re}(f(p))\geq 0$ for all $p$, by Mertens’ theorem we find

$(\log
y_{0})e^{-\frac{1}{2}\mathbb{D}(f,1;y_{0})^{2}}\asymp\exp\left(\frac{1}{2}\sum_{p\leq
y_{0}}\frac{1+\text{Re}(f(p))}{p}\right)\leq\exp\left(\frac{1}{2}\sum_{p\leq
x}\frac{1+\text{Re}(f(p))}{p}\right)\asymp(\log
x)e^{-\frac{1}{2}\mathbb{D}(f,1;x)^{2}},$

and the claimed bound follows. ∎

Whereas the logarithmically-averaged partial sum up to $x$ of a bounded
multiplicative function $f$ is always controlled by $\mathbb{D}(f,1;x)$, the
same is not true of Cesàro-averaged sums in general. In this case, the
following estimate will be suitable for our applications to short sums of
characters.

######  Lemma 2.3 (Halász-Montgomery-Tenenbaum Inequality).

Let $f:\mathbb{N}\rightarrow\mathbb{U}$ be multiplicative. Let $x\geq 3$,
$T\geq 1$, and set

$M:=\min_{|t|\leq T}\mathbb{D}(f,n^{it};x)^{2}.$

Then we have

(8) $\frac{1}{x}\left|\sum_{n\leq
x}f(n)\right|\ll(M+1)e^{-M}+\frac{1}{T}+\frac{\log\log x}{\log x},$

###### Proof.

This is [14, Cor. III.4.12]. ∎

Finally, the following lemma shows that characters of small modulus cannot be
too close in pretentious distance to the archimedean characters $n\mapsto
n^{it}$.

######  Lemma 2.4.

There is an absolute constant $C_{0}\geq 1$ such that if $C\geq C_{0}$ the
following is true. Let $y\geq 10$ and suppose $1\leq m\leq y^{1/C}$. Let
$\psi$ be a Dirichlet character modulo $m$ and let $|t|\leq y^{2}$. If

$\mathbb{D}(\psi,n^{it};y)^{2}\leq C$

then $\psi$ is principal and $|t|\log y\ll e^{2C}$.

###### Proof.

This is [11, Lem. 3.3], made slightly more precise (the bound claimed here
follows from the proof of that result). ∎

###  2.2. Results about high order characters

We next give a generalisation and sharpening of a result implicitly derived in
[12, Sec. 6] (see in particular the proof of Theorem 2 there), showing that
$\chi(p)\neq 0,1$ often when $\chi$ has large order. In the sequel, we write

$\Sigma_{\chi}(x):=\sum_{\begin{subarray}{c}p\leq x\\\ \chi(p)\neq
0,1\end{subarray}}\frac{1}{p},\quad x\geq 2.$

Given a multiplicative function $f:\mathbb{N}\rightarrow\mathbb{U}$ and $x\geq
1$ we also put

$S_{f}(x):=\sum_{n\leq x}f(n),\quad L_{f}(x):=\sum_{n\leq x}\frac{f(n)}{n}.$

######  Proposition 2.5.

Let $\chi$ be a non-principal character modulo $q$ of order $d\geq 2$. Then
there is a constant $c_{1}>0$ such that if

$\delta:=\max\left\\{\left(\frac{\log\log(ed)}{c_{1}\log d}\right)^{1/2},(\log
q)^{-c_{1}}\right\\}$

then whenever $x>q^{\delta}$ either

$\max\left\\{\frac{|S_{\chi}(x)|}{x},\frac{|L_{\chi}(q)|}{\log
q}\right\\}<\frac{1}{(\log d)^{1/5}},$

or else

$\Sigma_{\chi}(x)\geq c_{1}\log\log d.$

###### Proof.

We follow the arguments in [12, Sec. 5]. Let $c_{1}>0$ be a parameter to be
chosen shortly, define $\delta$ as above and let $x>q^{\delta}$. Assume for
the sake of contradiction that

(9) $\max\left\\{\frac{|S_{\chi}(x)|}{x},\frac{|L_{\chi}(q)|}{\log
q}\right\\}\geq\frac{1}{(\log d)^{1/5}},$

and also that

(10) $\Sigma_{\chi}(x)<c_{1}\log\log d.$

Set $c:=4c_{1}$ and consider first the case in which $d\leq e^{(\log q)^{c}}$.
Since $\chi$ has order $d$, orthogonality of Dirichlet characters implies that

(11) $|\\{n\leq q:\chi(n)=1\\}|=\frac{1}{d}\sum_{0\leq j\leq
d-1}\sum_{\begin{subarray}{c}n\leq q\\\
(n,q)=1\end{subarray}}\chi(n)^{j}=\frac{\phi(q)}{d}.$

Now, let $g:\mathbb{N}\rightarrow[0,1]$ be the completely multiplicative
function defined at primes by

$g(p):=\begin{cases}1&\text{ if }p\leq x\text{ and }\chi(p)=1\\\ 0&\text{
otherwise.}\end{cases}$

Write also

$u:=\mathbb{D}(g,1;q)^{2}=\sum_{x<p\leq
q}\frac{1}{p}+\sum_{\begin{subarray}{c}p\leq x\\\ \chi(p)\neq
1\end{subarray}}\frac{1}{p},$

set $\sigma_{-}(u):=u\rho(u)$ where $\rho$ is the Dickman function (see e.g.
[14, Sec. III.5.3-4] for a definition and relevant properties), and put

$R(g;q):=\prod_{p\leq
q}\left(1-\frac{1}{p}\right)\left(1-\frac{g(p)}{p}\right)^{-1}\asymp e^{-u}.$

By Hildebrand’s theorem [9, Thm. 2] there are absolute constants
$\beta\in(0,1)$ and $A>0$ such that

(12) $\displaystyle|\\{n\leq q:\chi(n)=1\\}|$ $\displaystyle\geq\sum_{n\leq
q}g(n)\geq AqR(g;q)\left(\sigma_{-}(e^{u})+O(e^{-(\log q)^{\beta}})\right).$

Since $\rho(v)\geq v^{-2v}$ for large $v$ we have $\sigma_{-}(e^{u})\gg
e^{-(\log q)^{\beta}}$ as long as $u\leq\tfrac{\beta}{2}\log\log q$. Since
$x>q^{\delta}$ by assumption,

$\displaystyle u\leq\sum_{\begin{subarray}{c}p\leq x\\\ \chi(p)\neq
1\end{subarray}}\frac{1}{p}+\log(1/\delta)+O(1)\leq\Sigma_{\chi}(x)+(c_{1}+o(1))\log\log
q\leq(2c_{1}+o(1))\log\log q$

we obtain $\sigma_{-}(e^{u})\gg e^{-(\log q)^{\beta}}$ with a suitably large
implicit constant as long as $c=4c_{1}<\beta$, and $q$ is large enough.
Combining (11) and (12), we find

$\frac{\phi(q)}{d}\gg qe^{-u}\sigma_{-}(e^{u})\gg q\rho(e^{u})\gg
qe^{-2ue^{u}}.$

We deduce that

$u+\log(2u)=(1+o(1))u\geq\log\log d,$

whence also

$\Sigma_{\chi}(x)+\sum_{p|q}\frac{1}{p}+\log(1/\delta)\geq(1-o(1))\log\log d.$

As $\log(1/\delta)\leq\frac{1}{2}\log\log d$ we deduce that

(13) $\max\\{\Sigma_{\chi}(x),\log(q/\phi(q))\\}\geq(1/4-o(1))\log\log d.$

Now using a theorem of Hall [6], we have

$|S_{\chi}(x)|\leq\sum_{n\leq x}1_{(n,q)=1}\ll
x\prod_{\begin{subarray}{c}p\leq x\\\
p|q\end{subarray}}\left(1-\frac{1}{p}\right)\ll
x\frac{\phi(q)}{q}\exp\left(\sum_{\begin{subarray}{c}p>x\\\
p|q\end{subarray}}\frac{1}{p}\right)\ll x\frac{\phi(q)}{q}.$

Similarly,

$|L_{\chi}(q)|\leq\sum_{\begin{subarray}{c}p|n\Rightarrow p\leq q\\\
(n,q)=1\end{subarray}}\frac{1}{n}\ll(\log
q)\prod_{p|q}\left(1-\frac{1}{p}\right)=\frac{\phi(q)}{q}\log q.$

From (9) we see that

$\sum_{p|q}\frac{1}{p}=\log(q/\phi(q))+O(1)\leq\frac{1}{5}\log\log d+O(1).$

In light of (13), we have

$\Sigma_{\chi}(x)\geq(1/4-o(1))\log\log d,$

whenever $d\leq e^{(\log q)^{c}}$, another contradiction as
$c_{1}<\beta/4<1/4$. Hence $\Sigma_{\chi}(x)>c_{1}\log\log d$ in this case.
Next, assume that $d\geq e^{(\log q)^{c}}$. The argument444While the result
stated there was only stated for prime $q$, the proof employed zero-density
estimates that hold for the family of non-principal characters to more general
moduli $q$, and is therefore applicable to the present circumstances. in the
proof of [12, Prop. 5.1] actually shows in this case that

$\sum_{\begin{subarray}{c}p\leq q\\\ \chi(p)\neq
1\end{subarray}}\frac{1}{p}\geq(c-o(1))\log\log q.$

Since we have

$\sum_{p|q}\frac{1}{p}=\log(q/\phi(q))+O(1)\leq\log\log\log q+O(1)$

and $c_{1}=c/4$ we deduce that when $d\geq e^{(\log q)^{c}}$,

$\Sigma_{\chi}(x)\geq\sum_{\begin{subarray}{c}p\leq q\\\ \chi(p)\neq
0,1\end{subarray}}\frac{1}{p}-\sum_{x<p\leq q}\frac{1}{p}\geq(c-o(1))\log\log
q-\log(1/\delta)\geq(3c_{1}-o(1))\log\log q>c_{1}\log\log d$

using $q\geq\phi(q)\geq d$ in the last bound. The claim now follows.

∎

##  3\. Minimising Archimedean and Dirichlet twists

Let $q\geq 3$ be large and let $\chi$ be a primitive character modulo $q$ with
order $d\geq 2$. We assume that $d$ is larger than any fixed absolute
constant, and for $c_{1}>0$ chosen as in Proposition 2.5 we let

$\delta:=\max\left\\{\left(\frac{\log\log(ed)}{c_{1}\log d}\right)^{1/2},(\log
q)^{-c_{1}}\right\\}.$

Let $\varepsilon>0$ and $x>q^{\delta}$, and define the sets555As we define
$M(\psi):=\max_{1\leq t\leq m}|S_{\psi}(t)|$ for a character $\psi$ of modulus
$m$, the maximal sum $M(\chi_{0})$ of the principal character
$\chi_{0}\pmod{q}$ is well-defined and equal to $q-1$.

$\mathcal{C}_{d}(\varepsilon):=\\{\ell\pmod{d}:|S_{\chi^{\ell}}(x)|\geq\varepsilon
x\\},\quad\mathcal{L}_{d}(\varepsilon):=\\{\ell\pmod{d}:M(\chi^{\ell})\geq\varepsilon\sqrt{q}\log
q\\}.$

We assume here that $\varepsilon$ is smaller than any fixed constant. We will
prove a structural result about each of the sets
$\mathcal{C}_{d}(\varepsilon)$ and $\mathcal{L}_{d}(\varepsilon)$. The first
is an analogue of [12, Prop. 4.1].

######  Proposition 3.1.

Let $\varepsilon>0$ with $\varepsilon\geq(\log q)^{-1/10}$. Assume that
$|\mathcal{C}_{d}(\varepsilon)|\geq\varepsilon d$. Then there are positive
integers $1\leq g\leq\varepsilon^{-1}$ and and $1\leq m\leq\varepsilon^{-2}$
such that

$\mathcal{C}_{d}(\varepsilon)\subseteq\\{\ell g\pmod{d}:1\leq\ell\leq
d/g\\}=m\mathcal{C}_{d}(\varepsilon),$

and furthermore

$\max_{1\leq\ell\leq d/g}\mathbb{D}(\chi^{g\ell},1;x)^{2}\leq
200m^{2}\log(1/\varepsilon).$

###### Proof.

Observe that $\ell\in\mathcal{C}_{d}(\varepsilon)$ if and only if
$-\ell\in\mathcal{C}_{d}(\varepsilon)$, so $\mathcal{C}_{d}(\varepsilon)$ is a
symmetric subset of $\mathbb{Z}/d\mathbb{Z}$. Applying [11, Lem. 5.8], we find
an integer666The proof of [11, Lem. 5.8] actually shows that $m=2^{j+1}$,
where $j$ is the largest integer such that $(3/2)^{j-1}\leq 1/\varepsilon$.
Since $2\log(3/2)\geq\log 2$, it is easy to check that this forces
$m\leq\varepsilon^{-2}$ when $\varepsilon$ is sufficiently small. $1\leq
m\leq\varepsilon^{-2}$ and a divisor $r|d$ with $r\geq\varepsilon d$ such that
$m\mathcal{C}_{d}(\varepsilon)=H$ is a subgroup of $\mathbb{Z}/d\mathbb{Z}$ of
order $|H|=r$. Note that $H$ is generated by $d/r=:g$, so that $1\leq
g\leq\varepsilon^{-1}$ and $H$ can be parameterised as $\\{\ell
g\pmod{d}:1\leq\ell\leq r\\}$. Moreover, since
$0\in\mathcal{C}_{d}(\varepsilon)$ we have
$\mathcal{C}_{d}(\varepsilon)\subseteq m\mathcal{C}_{d}(\varepsilon)$ for all
$m\geq 1$, and hence $\mathcal{C}_{d}(\varepsilon)\subseteq H$ as required.
The proof of Proposition 3.1 now follows the same lines as that of [12, Prop.
4.1]. Taking $T=1/\varepsilon^{2}$ and applying Lemma 2.3, we find that for
each $\ell\in\mathcal{C}_{d}(\varepsilon)$,

$\varepsilon x\leq|S_{\chi^{\ell}}(x)|\ll
x\left(\mathbb{D}(\chi^{\ell},n^{i\tilde{t}_{\ell}};x)^{2}e^{-\mathbb{D}(\chi^{\ell},n^{i\tilde{t}_{\ell}};x)^{2}}+\varepsilon^{2}+\frac{\log\log
x}{\log x}\right)$

for some $|\tilde{t}_{\ell}|\leq 1/\varepsilon^{2}$, from which we deduce that
(when $d$, and thus $q$, is sufficiently large)

$\max_{\ell\in\mathcal{C}_{d}(\varepsilon)}\mathbb{D}(\chi^{\ell},n^{i\tilde{t}_{\ell}};x)\leq\sqrt{2\log(1/\varepsilon)}.$

Now for $\ell_{1},\ell_{2}\in H$ we can choose representations

$\ell_{1}\equiv r_{1}+\cdots+r_{m}\pmod{d},\quad\ell_{2}\equiv
s_{1}+\cdots+s_{m}\pmod{d},\quad r_{i},s_{j}\in\mathcal{C}_{d}(\varepsilon).$

Setting

$t(\ell_{1}):=\tilde{t}_{r_{1}}+\cdots+\tilde{t}_{r_{m}},\quad
t(\ell_{2}):=\tilde{t}_{s_{1}}+\cdots+\tilde{t}_{s_{m}},$

we find by the pretentious triangle inequality that

$\displaystyle\mathbb{D}(\chi^{\ell_{1}},n^{it(\ell_{1})};x)$
$\displaystyle\leq\sum_{1\leq j\leq
m}\mathbb{D}(\chi^{r_{j}},n^{i\tilde{t}_{r_{j}}};x)\leq\sqrt{2m^{2}\log(1/\varepsilon)},$
$\displaystyle\mathbb{D}(\chi^{\ell_{2}},n^{it(\ell_{2})};x)$
$\displaystyle\leq\sum_{1\leq j\leq
m}\mathbb{D}(\chi^{s_{j}},n^{i\tilde{t}_{s_{j}}};x)\leq\sqrt{2m^{2}\log(1/\varepsilon)},$
$\displaystyle\mathbb{D}(\chi^{\ell_{1}+\ell_{2}},n^{i(t(\ell_{1})+t(\ell_{2}))};x)$
$\displaystyle\leq\mathbb{D}(\chi^{\ell_{1}},n^{it(\ell_{1})};x)+\mathbb{D}(\chi^{\ell_{2}},n^{it(\ell_{2})};x)\leq\sqrt{8m^{2}\log(1/\varepsilon)}.$

Define the map $\phi:H\rightarrow\mathbb{R}$ via $\phi(\ell):=t_{\ell}$, where
for each $\ell\in H$, $t_{\ell}\in[-2m/\varepsilon^{2},2m/\varepsilon^{2}]$ is
chosen such that

$\mathbb{D}(\chi^{\ell},n^{it_{\ell}};x)=\min_{|t|\leq
2m/\varepsilon^{2}}\mathbb{D}(\chi^{\ell},n^{it};x).$

Since $|t(\ell_{1})+t(\ell_{2})|\leq|t(\ell_{1})|+|t(\ell_{2})|\leq
2m/\varepsilon^{2}$ we see by the minimality property of $\phi(\ell_{j})$,
$j=1,2$, that

$\displaystyle\mathbb{D}(n^{i\phi(\ell_{j})},n^{it(\ell_{j})};x)$
$\displaystyle\leq\mathbb{D}(\chi^{\ell_{j}},n^{it(\ell_{j})};x)+\mathbb{D}(\chi^{\ell_{j}},n^{i\phi(\ell_{j})};x)\leq
2\mathbb{D}(\chi^{\ell_{j}},n^{it(\ell_{j})};x)\leq\sqrt{8m^{2}\log(1/\varepsilon)},$

and also that

$\displaystyle\mathbb{D}(n^{i\phi(\ell_{1}+\ell_{2})},n^{i(t(\ell_{1})+t(\ell_{2}))};x)$
$\displaystyle\leq\mathbb{D}(\chi^{\ell_{1}+\ell_{2}},n^{i\phi(\ell_{1}+\ell_{2})};x)+\mathbb{D}(\chi^{\ell_{1}+\ell_{2}},n^{i(t(\ell_{1})+t(\ell_{2}))};x)$
$\displaystyle\leq
2\mathbb{D}(\chi^{\ell_{1}+\ell_{2}},n^{i(t(\ell_{1})+t(\ell_{2})};x)\leq\sqrt{32m^{2}\log(1/\varepsilon)}.$

Set $K:=\varepsilon^{-16m^{2}}\geq 1$. It follows from Lemma 2.4 that

$|\phi(\ell_{j})-t(\ell_{j})|\leq\frac{K}{\log
x},\quad|\phi(\ell_{1}+\ell_{2})-t(\ell_{1})-t(\ell_{2})|\leq\frac{K^{4}}{\log
x},$

whence that also

$|\phi(\ell_{1}+\ell_{2})-\phi(\ell_{1})-\phi(\ell_{2})|\leq\frac{2K+K^{4}}{\log
x}\leq\frac{3K^{4}}{\log x}.$

The map $\phi$ is therefore a $\tfrac{3K^{4}}{\log x}$-approximate
homomorphism, in the sense of [13]. Since there are no non-zero homomorphisms
$H\to\mathbb{R}$, by [13, Statement (7.2)] we deduce that

$\max_{\ell\in H}|\phi(\ell)|\leq\frac{3K^{4}}{\log x}.$

By Mertens’ theorem we then deduce (again using the minimality property of
$\phi(\ell)$) that

$\displaystyle\max_{\ell\in H}\mathbb{D}(\chi^{\ell},1;x)^{2}$
$\displaystyle\leq 2\max_{\ell\in
H}\left(\mathbb{D}(\chi^{\ell},n^{i\phi(\ell)};x)^{2}+\mathbb{D}(1,n^{i\phi(\ell)};x)^{2}\right)$
$\displaystyle\leq 2\max_{\ell\in
H}\left(\mathbb{D}(\chi^{\ell},n^{it(\ell)};x)^{2}+\log(1+|\phi(\ell)|\log
x)+O(1)\right)$ $\displaystyle\leq 2\left(8m^{2}\log(1/\varepsilon)+4\log
K+O(1)\right)$ $\displaystyle<150m^{2}\log(1/\varepsilon)+O(1),$

and the claim follows since each $\ell\in H$ can be written in the form
$g\ell^{\prime}$ with $1\leq\ell^{\prime}\leq r$. ∎

We also prove an analogous pretentiousness result about
$\mathcal{L}_{d}(\varepsilon)$; no such result appeared in [12].

######  Proposition 3.2.

Let $\varepsilon>0$ with $\varepsilon\geq(\log q)^{-1/10}$. Assume that
$|\mathcal{L}_{d}(\varepsilon)|\geq\varepsilon d$. Then there are

  * •

positive integers $1\leq m\leq\varepsilon^{-2}$ and $1\leq
g\leq\varepsilon^{-1}$ such that

$\mathcal{L}_{d}(\varepsilon)\subseteq\\{g\ell:1\leq\ell\leq
d/g\\}=m\mathcal{L}_{d}(\varepsilon),$

  * •

a positive integer $1\leq k\leq\varepsilon^{-3m}$ and a primitive Dirichlet
character $\xi\pmod{k}$ of order dividing $d/g$ such that

$\max_{1\leq\ell\leq d/g}\mathbb{D}(\chi^{g\ell},\xi^{\ell};x)^{2}\ll
m^{2}\log(1/\varepsilon).$

###### Proof.

As with $\mathcal{C}_{d}(\varepsilon)$, $\mathcal{L}_{d}(\varepsilon)$ is a
symmetric subset of $\mathbb{Z}/d\mathbb{Z}$. Applying [11, Lem. 5.8] as in
the proof of the previous proposition, we can find an integer $1\leq
m\leq\varepsilon^{-2}$ and a divisor $r|d$ with $r\geq\varepsilon d$ such that
$m\mathcal{L}_{d}(\varepsilon)=H$ is a subgroup of $\mathbb{Z}/d\mathbb{Z}$ of
order $|H|=r$, and $\mathcal{L}_{d}(\varepsilon)\subseteq H$. By Proposition
2.1, for each $\ell\in\mathcal{L}_{d}(\varepsilon)$ there is a primitive
character $\xi_{\ell}$ (mod $k_{\ell}$) such that

(14) $\displaystyle\varepsilon\log
q\leq\frac{1}{\sqrt{q}}M(\chi^{\ell})\ll\frac{\sqrt{k_{\ell}}}{\phi(k_{\ell})}\max\limits_{1\leq
N\leq q}|L_{\chi^{\ell}\overline{\xi_{\ell}}}(N)|.$

Applying the trivial bound $|L_{\chi^{\ell}\overline{\xi}_{\ell}}(N)|\leq\log
N$ in (14), we see that

$\varepsilon\ll\frac{\sqrt{k_{\ell}}}{\phi(k_{\ell})}\max_{1\leq N\leq
q}\frac{\log N}{\log q}\ll\frac{\sqrt{k_{\ell}}}{\phi(k_{\ell})},$

so that since $\phi(b)\gg b/\log\log(3b)$ for any $b\geq 1$ we obtain the
bound

(15)
$\max_{\ell\in\mathcal{L}_{d}(\varepsilon)}k_{\ell}\ll(\varepsilon^{-1}\log\log(1/\varepsilon))^{2}.$

Using instead Lemma 2.2 in (14), we deduce that

$\varepsilon\log q\ll 1+(\log
q)e^{-\tfrac{1}{2}\mathbb{D}(\chi^{\ell}\overline{\xi}_{\ell},1;q)^{2}},$

from which we find that

$\displaystyle\mathbb{D}(\chi^{\ell}\overline{\xi_{\ell}},1;q)^{2}=\mathbb{D}(\chi^{\ell},\xi_{\ell};q)^{2}\ll\log(1/\varepsilon).$

Let $\ell^{\prime}\in H$. As $H=m\mathcal{C}_{d}(\varepsilon)$ there is a
representation

$\displaystyle\ell^{\prime}\equiv
r_{1}+\cdots+r_{m}\pmod{d},\;\;r_{i}\in\mathcal{L}_{d}(\varepsilon).$

By the pretentious triangle inequality, we find that

$\displaystyle\mathbb{D}(\chi^{\ell^{\prime}},\prod\limits_{i=1}^{m}\xi_{r_{i}};q)\leq\sum\limits_{1\leq
i\leq m}\mathbb{D}(\chi^{r_{i}},\xi_{r_{i}};q)\ll
m\sqrt{\log(1/\varepsilon)}.$

Using (15), the modulus of $\prod_{1\leq i\leq m}\xi_{r_{i}}$ is

$[k_{r_{1}},\ldots,k_{r_{m}}]\leq k_{r_{1}}\cdots
k_{r_{m}}\leq(\varepsilon^{-1}\log\log(1/\varepsilon))^{2m}\leq\varepsilon^{-3m},$

provided $\varepsilon$ is sufficiently small. This modulus is a divisor of

$K(\varepsilon):=[1,2,\ldots,\lfloor(\varepsilon^{-1}\log\log(1/\varepsilon))^{2}\rfloor],$

which, by the prime number theorem, satisfies

$\log K(\varepsilon)\leq 2(\varepsilon^{-1}\log\log(1/\varepsilon))^{2},$

again provided $\varepsilon$ is sufficiently small.
In the sequel, write $\psi_{0}$ to denote the principal character modulo
$K(\varepsilon)$. For each $\ell^{\prime}\in H$, there is a primitive
character $\xi_{\ell^{\prime}}$ with conductor $\leq\varepsilon^{-3m}$ such
that

$\displaystyle\mathbb{D}(\chi^{\ell^{\prime}},\xi_{\ell^{\prime}};q)^{2}\ll
m^{2}\log(1/\varepsilon)+\sum_{\begin{subarray}{c}p|k_{\ell^{\prime}}\end{subarray}}\frac{1}{p}\ll
m^{2}\log(1/\varepsilon)+\log\log\log k_{\ell^{\prime}}\ll
m^{2}\log(1/\varepsilon),$

and therefore also

(16)
$\mathbb{D}(\chi^{\ell^{\prime}},\xi_{\ell^{\prime}}\psi_{0};q)^{2}\leq\mathbb{D}(\chi^{\ell^{\prime}},\xi_{\ell^{\prime}};q)^{2}+\sum_{p|K(\varepsilon)}\frac{1}{p}\ll
m^{2}\log(1/\varepsilon)+\log\log\log K(\varepsilon)\ll
m^{2}\log(1/\varepsilon).$

Let $g=d/r$. Then $H$ can be parametrised as $\\{jg\pmod{d}:1\leq j\leq r\\}$.
Let $\mathcal{S}$ denote the group of characters modulo $[k_{\ell}:\ell\in
H]$, generated by the set

$\displaystyle\\{\xi_{1}\psi_{0},\ldots,\xi_{r}\psi_{0}\\}.$

Define a map $\phi:H\to\mathcal{S}$ by $\phi(i)=\xi_{i}\psi_{0}$, and $1\leq
i,j\leq r$. By (16) and the triangle inequality,

$\displaystyle\mathbb{D}(\chi^{(i+j)g},\phi(i)\phi(j);q)\leq\mathbb{D}(\chi^{ig},\phi(i);q)+\mathbb{D}(\chi^{jg},\phi(j);q)\ll
m\sqrt{\log(1/\varepsilon)},$

so that

$\displaystyle\mathbb{D}(\phi(i+j),\phi(i)\phi(j);q)\leq\mathbb{D}(\chi^{(i+j)g},\phi(i)\phi(j);q)+\mathbb{D}(\chi^{(i+j)g},\phi(i+j);q)\ll
m\sqrt{\log(1/\varepsilon)}.$

Take $k:=\max\\{k_{i},k_{j},k_{i+j}\\}$. By Lemma 2.4 we see that either

$\varepsilon^{-9m}K(\varepsilon)\geq k^{3}K(\varepsilon)>q^{1/C},$

or else that

$\phi(i+j)\overline{\phi(i)}\overline{\phi(j)}=\xi_{i+j}\overline{\xi}_{i}\overline{\xi}_{j}\psi_{0}$

is principal, with modulus $m_{i,j}$ dividing
$[K(\varepsilon),k_{i},k_{j},k_{i+j}]=K(\varepsilon)$. Since
$m^{2}\log(1/\varepsilon)=o(\log\log q)$ the former is not possible. Thus,
writing $\chi_{0}^{(m_{i,j})}$ to denote the principal character modulo
$m_{i,j}$, we have

$\phi(i+j)=\xi_{i+j}\psi_{0}=\xi_{i}\xi_{j}\chi_{0}^{(m_{i,j})}\psi_{0}=(\xi_{i}\psi_{0})(\xi_{j}\psi_{0})=\phi(i)\phi(j).$

It follows that $\phi$ is a homomorphism, and therefore

$\xi_{j}\psi_{0}=\phi(j)=\phi(1)^{j}=\xi_{1}^{j}\psi_{0}\text{ for all }1\leq
j\leq r.$

Since $\xi_{j}$ is primitive for all $1\leq j\leq r$, it follows that
$\xi_{r}$ is the trivial character, and thus $\xi_{1}^{r}$ is principal, i.e.,
$\xi_{1}$ has order dividing $r$.
We deduce that, uniformly over $1\leq j\leq r$,

$\displaystyle\mathbb{D}(\chi^{jg},(\xi_{1})^{j};q)^{2}\leq\mathbb{D}(\chi^{jg},\phi(j);q)^{2}+\sum_{p|K(\varepsilon)}\frac{1}{p}\ll
m^{2}\log(1/\varepsilon).$

We write $\xi=\xi_{1}$ and $k=k_{1}$, and the claim follows. ∎

##  4\. Averaged Cesàro sums: Proof of Theorem 1.1

Write $\zeta=e(1/d)$, which is a primitive $d$th root of unity. As in [12] we
decompose

$\Sigma_{\chi}(x)=\sum_{\begin{subarray}{c}p\leq x\\\ \chi(p)\neq
0,1\end{subarray}}\frac{1}{p}=\sum_{1\leq j\leq d-1}\sigma_{j}(x),$

where given $y\geq 2$ and $1\leq j\leq d-1$ we set

$\sigma_{j}(y):=\sum_{\begin{subarray}{c}p\leq y\\\
\chi(p)=\zeta^{j}\end{subarray}}\frac{1}{p}.$

We consider below how the size of the fibred sums $\sigma_{j}$ influence the
magnitudes of the partial sums $S_{\chi^{\ell}}(x)$, for $1\leq\ell\leq d-1$.
For the remainder of this section, fix $\eta\in(0,1)$ to be a small parameter,
to be chosen later.

###  4.1. Small $\sigma_{j}$ case

In the case where all $\sigma_{j}$ are “small” (in a sense to be made
precise), we will prove the following analogue of [12, Lem. 4.4].

######  Proposition 4.1.

Let $\eta$ be sufficiently small, and suppose
$\sigma_{j}(x)\leq\tfrac{\eta}{g}\Sigma_{\chi}(x)$ for all $1\leq j\leq d-1$.
Then there are elements $1\leq\ell\leq d/g$ such that

$\mathbb{D}(\chi^{g\ell},1;x)^{2}\geq\frac{1}{2}\Sigma_{\chi}(x).$

###### Proof.

Set $r:=d/g$ and let $1\leq\ell\leq r$. As in [12], we use the lower bound

(17) $\mathbb{D}(\chi^{g\ell},1;x)^{2}=\sum_{1\leq j\leq d-1}(1-\cos(2\pi
jg\ell/d))\sum_{\begin{subarray}{c}p\leq x\\\
\chi(p)=\zeta^{j}\end{subarray}}\frac{1}{p}\geq 8\sum_{1\leq j\leq
d-1}\left\|\frac{j\ell}{r}\right\|^{2}\sigma_{j}(x).$

In the sequel we write $\sigma_{j}=\sigma_{j}(x)$ for convenience. We then
consider the (restricted) variance777In contrast to [12], here we restrict
ourselves to an average over powers $g\ell$, and thus our sums over $\ell$ and
$j$ have different ranges.

$\Delta:=\frac{1}{r}\sum_{1\leq\ell\leq r}\left(\sum_{1\leq j\leq
d-1}\left\|\frac{j\ell}{r}\right\|^{2}\sigma_{j}-\frac{1}{12}\Sigma_{\chi}(x)\right)^{2}=\frac{1}{r}\sum_{1\leq\ell\leq
r}\left(\sum_{1\leq j\leq
d-1}\left(\left\|\frac{j\ell}{r}\right\|^{2}-\frac{1}{12}\right)\sigma_{j}\right)^{2}$

Expanding the square and using the Fourier expansion

$\|t\|^{2}=\frac{1}{12}+\frac{1}{2\pi^{2}}\sum_{v\neq
0}\frac{(-1)^{v}}{v^{2}}e(vt),$

for the $1$-periodic map $t\mapsto\|t\|^{2}$, we obtain

$\displaystyle\Delta$ $\displaystyle=\sum_{1\leq j_{1},j_{2}\leq
d-1}\sigma_{j_{1}}\sigma_{j_{2}}\frac{1}{r}\sum_{1\leq\ell\leq
r}\left(\left\|\frac{\ell
j_{1}}{r}\right\|^{2}-\frac{1}{12}\right)\left(\left\|\frac{\ell
j_{2}}{r}\right\|^{2}-\frac{1}{12}\right)$
$\displaystyle=\frac{1}{4\pi^{4}}\sum_{1\leq j_{1},j_{2}\leq
d-1}\sigma_{j_{1}}\sigma_{j_{2}}\sum_{v_{1},v_{2}\neq
0}\frac{(-1)^{v_{1}+v_{2}}}{(v_{1}v_{2})^{2}}\frac{1}{r}\sum_{1\leq\ell\leq
r}e\left(\frac{\ell}{r}(j_{1}v_{1}-j_{2}v_{2})\right)$
$\displaystyle=\frac{1}{4\pi^{4}}\sum_{1\leq j_{1},j_{2}\leq
d-1}\sigma_{j_{1}}\sigma_{j_{2}}\sum_{\begin{subarray}{c}v_{1},v_{2}\neq 0\\\
j_{1}v_{1}\equiv
j_{2}v_{2}\pmod{r}\end{subarray}}\frac{(-1)^{v_{1}+v_{2}}}{(v_{1}v_{2})^{2}}$
$\displaystyle=\frac{1}{4\pi^{4}}\sum_{e_{1},e_{2}|r}\sum_{\begin{subarray}{c}1\leq
j_{1}<d\\\ (j_{1},r)=e_{1}\end{subarray}}\sum_{\begin{subarray}{c}1\leq
j_{2}<d\\\
(j_{2},r)=e_{2}\end{subarray}}\sigma_{j_{1}}\sigma_{j_{2}}\sum_{\begin{subarray}{c}v_{1},v_{2}\neq
0\\\ j_{1}v_{1}\equiv
j_{2}v_{2}\pmod{r}\end{subarray}}\frac{(-1)^{v_{1}+v_{2}}}{(v_{1}v_{2})^{2}},$

where we have split the sum according to the GCDs of $j_{1}$ and $j_{2}$ with
$r$. Note that $(j_{1}v_{1},r)=(j_{2}v_{2},r)$ whenever $j_{1}v_{1}\equiv
j_{2}v_{2}\pmod{r}$. Letting $\lambda=(j_{i}v_{i},r)$ denote this common
divisor of $r$, we of course have $e_{1},e_{2}|\lambda$. In this case, writing
$\lambda=e_{i}f_{i}$ and $j_{i}=J_{i}e_{i}$ for $i=1,2$, and noting that
$(J_{i},r/e_{i})=1$, we find

$\lambda=(e_{i}\cdot J_{i}v_{i},e_{i}\cdot
r/e_{i})=e_{i}(J_{i}v_{i},r/e_{i})=e_{i}(v_{i},r/e_{i}),$

so that $f_{i}=(v_{i},r/e_{i})$; in particular, $f_{i}|v_{i}$ for $i=1,2$.
Setting $u_{i}:=v_{i}/f_{i}$, it follows that

$\displaystyle\Delta$
$\displaystyle=\frac{1}{4\pi^{4}}\sum_{\begin{subarray}{c}\lambda|r\end{subarray}}\sum_{\begin{subarray}{c}e_{i}f_{i}=\lambda\\\
i=1,2\end{subarray}}\frac{1}{(f_{1}f_{2})^{2}}\sum_{\begin{subarray}{c}1\leq
J_{1}<d/e_{1}\\\
(J_{1},r/e_{1})=1\end{subarray}}\sum_{\begin{subarray}{c}1\leq
J_{2}<d/e_{2}\\\
(J_{2},r/e_{2})=1\end{subarray}}\sigma_{J_{1}e_{1}}\sigma_{J_{2}e_{2}}\sum_{\begin{subarray}{c}u_{1},u_{2}\neq
0\\\ J_{1}u_{1}\equiv J_{2}u_{2}\pmod{r/\lambda}\\\
(u_{1},r/\lambda)=(u_{2},r/\lambda)=1\end{subarray}}\frac{(-1)^{f_{1}u_{1}+f_{2}u_{2}}}{(u_{1}u_{2})^{2}}.$

If we truncate both of the $u_{1},u_{2}$ series to terms with $|u_{j}|\leq
Mr/\lambda$ for some $M\geq 1$ then we obtain

(18)
$\Delta=\frac{1}{4\pi^{4}}\sum_{\begin{subarray}{c}\lambda|r\end{subarray}}\sum_{\begin{subarray}{c}e_{i}f_{i}=\lambda\\\
i=1,2\end{subarray}}\frac{1}{(f_{1}f_{2})^{2}}\sum_{\begin{subarray}{c}1\leq
J_{1}<d/e_{1}\\\
(J_{1},r/e_{1})=1\end{subarray}}\sum_{\begin{subarray}{c}1\leq
J_{2}<d/e_{2}\\\
(J_{2},r/e_{2})=1\end{subarray}}\sigma_{J_{1}e_{1}}\sigma_{J_{2}e_{2}}\sum_{\begin{subarray}{c}1\leq|u_{1}|,|u_{2}|\leq
Mr/\lambda\\\ J_{1}u_{1}\equiv J_{2}u_{2}\pmod{r/\lambda}\\\
(u_{1},r/\lambda)=(u_{2},r/\lambda)=1\end{subarray}}\frac{(-1)^{f_{1}u_{1}+f_{2}u_{2}}}{(u_{1}u_{2})^{2}}+O\left(\mathcal{E}_{M}\right),$

where we have set

$\mathcal{E}_{M}=\frac{1}{Mr}\sum_{\begin{subarray}{c}\lambda|r\end{subarray}}\lambda\sum_{\begin{subarray}{c}e_{i}f_{i}=\lambda\\\
i=1,2\end{subarray}}\frac{1}{(f_{1}f_{2})^{2}}\sum_{\begin{subarray}{c}1\leq
J_{1}<d/e_{1}\\\
(J_{1},r/e_{1})=1\end{subarray}}\sum_{\begin{subarray}{c}1\leq
J_{2}<d/e_{2}\\\
(J_{2},r/e_{2})=1\end{subarray}}\sigma_{J_{1}e_{1}}\sigma_{J_{2}e_{2}}.$

Rearranging, we obtain

$\displaystyle\mathcal{E}_{M}$
$\displaystyle=\frac{1}{Mr}\sum_{\begin{subarray}{c}e_{1},e_{2}|r\end{subarray}}\left(\sum_{\begin{subarray}{c}1\leq
j_{1}<d\\\
(j_{1},r)=e_{1}\end{subarray}}\sigma_{j_{1}}\right)\left(\sum_{\begin{subarray}{c}1\leq
j_{2}<d\\\
(j_{2},r)=e_{2}\end{subarray}}\sigma_{j_{2}}\right)\sum_{\begin{subarray}{c}\lambda|r\\\
[e_{1},e_{2}]|\lambda\end{subarray}}\frac{\lambda}{(\lambda^{2}/e_{1}e_{2})^{2}}$
$\displaystyle=\frac{1}{Mr}\sum_{\begin{subarray}{c}e_{1},e_{2}|r\end{subarray}}\left(\sum_{\begin{subarray}{c}1\leq
j_{1}<d\\\
(j_{1},r)=e_{1}\end{subarray}}\sigma_{j_{1}}\right)\left(\sum_{\begin{subarray}{c}1\leq
j_{2}<d\\\
(j_{2},r)=e_{2}\end{subarray}}\sigma_{j_{2}}\right)\sum_{\begin{subarray}{c}a|r/[e_{1},e_{2}]\end{subarray}}\frac{(e_{1}e_{2})^{2}}{a^{3}[e_{1},e_{2}]^{3}}.$

We observe that for each pair $e_{1},e_{2}|r$ we have

$\frac{(e_{1}e_{2})^{2}}{r[e_{1},e_{2}]^{3}}\sum_{a|r/[e_{1},e_{2}]}\frac{1}{a^{3}}\ll\frac{(e_{1},e_{2})^{3}}{re_{1}e_{2}}\leq
1,$

since $(e_{1},e_{2})\leq\min\\{e_{1},e_{2}\\}\leq r$. It follows therefore
that

$\mathcal{E}_{M}\ll\frac{1}{M}\sum_{\begin{subarray}{c}e_{1},e_{2}|r\end{subarray}}\left(\sum_{\begin{subarray}{c}1\leq
j_{1}<d\\\
(j_{1},r)=e_{1}\end{subarray}}\sigma_{j_{1}}\right)\left(\sum_{\begin{subarray}{c}1\leq
j_{2}<d\\\
(j_{2},r)=e_{2}\end{subarray}}\sigma_{j_{2}}\right)=\frac{1}{M}\Sigma_{\chi}(x)^{2}.$

In the main term in (18), momentarily fix $1\leq|u_{1}|,|u_{2}|\leq
Mr/\lambda$ with $(u_{1},r/\lambda)=(u_{2},r/\lambda)=1$, assume $e_{2}\geq
e_{1}$ and let $1\leq J_{1}<d/e_{1}$ with $(J_{1},r/e_{1})=1$. If

$J_{2}u_{2}\equiv J_{1}u_{1}\pmod{r/\lambda},\text{ i.e., }J_{2}\equiv
J_{1}u_{2}^{-1}u_{1}\pmod{r/\lambda}$

then among the $d/e_{2}$ possible choices of $J_{2}$ there are
$O(\frac{d/e_{2}}{r/\lambda}+1)$ choices satisfying this congruence. For each
of these $J_{2}$ we have $\sigma_{J_{2}e_{2}}\leq(r\eta/d)\Sigma_{\chi}(x)$ by
assumption. Thus, applying the preceding arguments to all $u_{1},u_{2}$,
$e_{2}\geq e_{1}$ (the other case being identical up to relabelling) and
$J_{1}$ as above the main term in (18) is bounded above by

$\displaystyle\ll\frac{r\eta}{d}\Sigma_{\chi}(x)\sum_{\begin{subarray}{c}\lambda|r\end{subarray}}\sum_{\begin{subarray}{c}e_{1}f_{1}=\lambda\\\
e_{2}f_{2}=\lambda\\\ e_{2}\geq
e_{1}\end{subarray}}\frac{1}{(f_{1}f_{2})^{2}}\sum_{\begin{subarray}{c}1\leq
j_{1}<d\\\
(j_{1},r)=e_{1}\end{subarray}}\sigma_{j_{1}}\sum_{\begin{subarray}{c}1\leq|u_{1}|,|u_{2}|\leq
Mr/\lambda\\\
(u_{1}u_{2},r/\lambda)=1\end{subarray}}\frac{1}{(u_{1}u_{2})^{2}}\cdot\left(\frac{\lambda
d}{re_{2}}+1\right)$ (19)
$\displaystyle\ll\frac{r\eta}{d}\Sigma_{\chi}(x)(\mathcal{R}_{1}+\mathcal{R}_{2}),$

where, using $\lambda=e_{1}f_{1}=e_{2}f_{2}$ and the fact that the series in
$u_{1},u_{2}$ are both convergent, we have set

$\displaystyle\mathcal{R}_{1}$
$\displaystyle:=\frac{d}{r}\sum_{e_{1}|r}\left(\sum_{\begin{subarray}{c}1\leq
j_{1}<d\\\
(j_{1},r)=e_{1}\end{subarray}}\sigma_{j_{1}}\right)\sum_{f_{1}|r/e_{1}}\frac{1}{f_{1}^{2}}\sum_{\begin{subarray}{c}f_{2}|e_{1}f_{1}\\\
f_{2}\leq f_{1}\end{subarray}}\frac{1}{f_{2}},$ $\displaystyle\mathcal{R}_{2}$
$\displaystyle:=\sum_{e_{1}|r}\left(\sum_{\begin{subarray}{c}1\leq j_{1}<d\\\
(j_{1},r)=e_{1}\end{subarray}}\sigma_{j_{1}}\right)\sum_{\begin{subarray}{c}e_{2}|r\\\
e_{2}\geq e_{1}\end{subarray}}\sum_{\begin{subarray}{c}\lambda|r\\\
[e_{1},e_{2}]|\lambda\end{subarray}}\frac{(e_{1}e_{2})^{2}}{\lambda^{4}}.$

To estimate $\mathcal{R}_{1}$ we observe that $1_{f_{2}\leq
f_{1}}\leq(f_{1}/f_{2})^{1/2}$ in the inner sum, whence

$\sum_{f_{1}|r/e_{1}}\frac{1}{f_{1}^{2}}\sum_{\begin{subarray}{c}f_{2}|e_{1}f_{1}\\\
f_{2}\leq
f_{1}\end{subarray}}\frac{1}{f_{2}}\leq\sum_{f_{1}|r/e_{1}}\frac{1}{f_{1}^{3/2}}\sum_{\begin{subarray}{c}f_{2}|e_{1}f_{1}\end{subarray}}\frac{1}{f_{2}^{3/2}}\ll
1.$

It follows therefore that

$\mathcal{R}_{1}\ll\frac{d}{r}\sum_{e_{1}|r}\left(\sum_{\begin{subarray}{c}1\leq
j_{1}<d\\\
(j_{1},r)=e_{1}\end{subarray}}\sigma_{j_{1}}\right)=\frac{d}{r}\Sigma_{\chi}(x).$

To bound $\mathcal{R}_{2}$, note that for each $e_{1}|r$,

$\sum_{\begin{subarray}{c}e_{2}|r\\\ e_{2}\geq
e_{1}\end{subarray}}\sum_{\begin{subarray}{c}\lambda|r\\\
[e_{1},e_{2}]|\lambda\end{subarray}}\frac{(e_{1}e_{2})^{2}}{\lambda^{4}}=\sum_{\begin{subarray}{c}e_{2}|r\\\
e_{2}\geq
e_{1}\end{subarray}}\frac{(e_{1}e_{2})^{2}}{[e_{1},e_{2}]^{4}}\sum_{\begin{subarray}{c}a|r/[e_{1},e_{2}]\end{subarray}}\frac{1}{a^{4}}\ll\frac{1}{e_{1}^{2}}\sum_{e_{2}|r}\frac{(e_{1},e_{2})^{4}}{e_{2}^{2}}.$

We now observe that

$\displaystyle\frac{1}{e_{1}^{2}}\sum_{e_{2}|r}\frac{(e_{1},e_{2})^{4}}{e_{2}^{2}}$
$\displaystyle=\frac{1}{e_{1}^{2}}\prod_{\begin{subarray}{c}p^{k}||r\\\
p^{\nu}||e_{1}\\\ 0\leq\nu\leq k\end{subarray}}\left(\sum_{0\leq
j\leq\nu}p^{2j}+p^{4\nu}\sum_{\nu<j\leq k}\frac{1}{p^{2j}}\right)$
$\displaystyle\ll\frac{1}{e_{1}^{2}}\prod_{\begin{subarray}{c}p^{\nu}||e_{1}\\\
\nu\geq
1\end{subarray}}\left(p^{2\nu}\left(1-\frac{1}{p^{2}}\right)^{-1}+p^{2\nu-2}\left(1-\frac{1}{p^{2}}\right)^{-1}\right)=\prod_{p|e_{1}}\left(1+\frac{2}{p^{2}-1}\right)\ll
1.$

Applying this bound for each $e_{1}|r$, we find that

$\mathcal{R}_{2}\ll\sum_{e_{1}|r}\sum_{\begin{subarray}{c}1\leq j_{1}<d\\\
(j_{1},r)=e_{1}\end{subarray}}\sigma_{j_{1}}=\Sigma_{\chi}(x).$

Substituting our bounds for $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ into
(4.1), we obtain the upper bound

$\frac{r\eta}{d}\Sigma_{\chi}(x)(\mathcal{R}_{1}+\mathcal{R}_{2})\ll\frac{r\eta}{d}\Sigma_{\chi}(x)^{2}\left(\frac{d}{r}+1\right)\ll\eta\Sigma_{\chi}(x)^{2}.$

Gathering all of the bounds together and selecting $M=\eta^{-1}$, we obtain

$\Delta\ll\left(\eta+\frac{1}{M}\right)\Sigma_{\chi}(x)^{2}\ll\eta\Sigma_{\chi}(x)^{2}.$

Thus, by Chebyshev’s inequality we see that, with $O(\eta^{1/2}\log(1/\eta)r)$
exceptions $1\leq\ell\leq r$, whenever
$\sigma_{j}(x)\leq(r\eta/d)\Sigma_{\chi}(x)$ for all $1\leq j\leq d-1$,

$\mathbb{D}(\chi^{g\ell},1;x)^{2}\geq 8\sum_{1\leq j\leq
d-1}\|\frac{j\ell}{r}\|^{2}\sigma_{j}\geq\left(\frac{2}{3}+O\left(\frac{1}{\sqrt{\log(1/\eta)}}\right)\right)\Sigma_{\chi}(x).$

In particular, provided $\eta$ is small enough, we deduce that
$\mathbb{D}(\chi^{g\ell},1;x)^{2}\geq\tfrac{1}{2}\Sigma_{\chi}(x)$ for _some_
$1\leq\ell\leq r$. ∎

###  4.2. Large $\sigma_{j}$ case

Suppose next that there is a $1\leq j_{0}\leq d-1$ for which
$\sigma_{j_{0}}(x)$ is “large”, in contrast to the previous subsection. Our
objective is to give a strengthening of [12, Prop. 4.5], in this case.

######  Proposition 4.2.

There exists an absolute constant $c>0$ such that the following holds. Suppose
there is $1\leq j_{0}\leq d-1$ such that
$\sigma_{j_{0}}(x)>\tfrac{\eta}{g}\Sigma_{\chi}(x)$, and that moreover

$m^{2}\log(1/\varepsilon)<c\Sigma_{\chi}(x).$

Then for any parameters $z\geq 10$ and $k\in\mathbb{N}$ satisfying

$10\leq z\leq\exp\left(\tfrac{\log x}{3k}\right),\quad 1\leq
k\leq\sqrt{\sigma_{j_{0}}(z)},$

for any $0<\rho<1-2/\pi$ and any $1\leq\ell\leq r$,

$\displaystyle\left(\left\|\frac{j_{0}\ell}{r}\right\|+O\left(\frac{m^{2}\log(1/\varepsilon)}{\sigma_{j_{0}}(z)}\right)\right)^{k}\left|\frac{1}{x}\sum_{n\leq
x}\chi^{g\ell}(n)\right|\ll
k!\left((8\sigma_{j_{0}}(z))^{-k/2}+\left(\frac{\log z}{\log
x}\right)^{\rho}\sigma_{j_{0}}(z)^{-1}+x^{-1/6}\right).$

###### Proof.

Define

$\mathcal{T}_{k,z}:=\\{p_{1}\cdots p_{k}:\,p_{i}\leq z\text{ and
}\chi(p_{i})=\zeta^{j_{0}}\text{ for all }1\leq i\leq k\\}.$

For each $t\in\mathcal{T}_{k,z}$ and $n\in\mathbb{N}$ define888Note that when
$t=p$ is prime this reduces to the “mean $0$” function
$f_{p}(n)=1_{p|n}-\frac{1}{p}$.

$f_{t}(n):=\sum_{ab=t}\frac{\mu(b)}{b}1_{a|n}.$

Let $1\leq\ell\leq r$. Select $y_{g\ell,0}$ to be a maximiser for
$\max_{|y|\leq 2\log x}|F_{g\ell}(1+iy)|$, where for $s\in\mathbb{C}$ with
$\text{Re}(s)>0$ we write

$F_{g\ell}(s):=\prod_{p\leq
x}\left(1-\frac{\chi^{g\ell}(p)}{p^{s}}\right)^{-1}.$

We then define

$y_{g\ell}:=\begin{cases}0&\text{ if }|y_{g\ell,0}|>\tfrac{1}{2}\log x,\\\
y_{g\ell,0}&\text{ otherwise.}\end{cases}$

Now, by Proposition 3.1, whenever $1\leq\ell\leq r$ we have

$\mathbb{D}(\chi^{g\ell},1;x)^{2}\leq 200m^{2}\log(1/\varepsilon).$

Since, when $y_{g\ell}\neq 0$,

$\exp\left(-\mathbb{D}(\chi^{g\ell},n^{iy_{g\ell}};x)^{2}\right)\asymp\frac{|F_{g\ell}(1+iy_{g\ell})|}{\log
x}=\max_{|y|\leq 2\log x}\frac{|F_{g\ell}(1+iy)|}{\log
x}\asymp\exp\left(-\min_{|y|\leq 2\log
x}\mathbb{D}(\chi^{g\ell},n^{iy};x)^{2}\right),$

it follows that

$\mathbb{D}(\chi^{g\ell},n^{iy_{g\ell}};x)^{2}=\min_{|y|\leq 2\log
x}\mathbb{D}(\chi^{g\ell},n^{iy};x)^{2}+O(1).$

Using this minimal property when $y_{g\ell}\neq 0$, we deduce that when
$\varepsilon$ is sufficiently small,

$\mathbb{D}(1,n^{iy_{g\ell}};x)^{2}\leq
2(\mathbb{D}(\chi^{g\ell},1;x)+\mathbb{D}(\chi^{g\ell},n^{iy_{g\ell}};x))\leq
4\mathbb{D}(\chi^{g\ell},1;x)^{2}+O(1)\leq 1000m^{2}\log(1/\varepsilon),$

a bound which also trivially holds when $y_{g\ell}=0$. From this and Lemma 2.4
we deduce that there is $C\geq 1$ such that

(20) $|y_{g\ell}|\ll\varepsilon^{-Cm^{2}}/\log x.$

Next, define $h_{\ell}(n):=\chi^{g\ell}(n)n^{-iy_{g\ell}}$, and consider the
sum

$M_{h_{\ell}}(x;t):=\frac{1}{x}\sum_{n\leq x}h_{\ell}(n)f_{t}(n),\quad
t\in\mathcal{T}_{k,z}.$

We will estimate the sum $\sum_{t\in\mathcal{T}_{k,z}}M_{h_{\ell}}(x;t)$ in
two ways.
First, we relate this sum to the mean value of $h_{\ell}$. To begin with,
observe that since $h_{\ell}$ is completely multiplicative,

$M_{h_{\ell}}(x;t)=\frac{1}{x}\sum_{n\leq
x}h_{\ell}(n)\sum_{ac=t}\frac{\mu(c)}{c}1_{a|n}=\sum_{ac=t}\frac{\mu(c)h_{\ell}(a)}{ac}\cdot\frac{a}{x}\sum_{m\leq
x/a}h_{\ell}(m)=\frac{1}{t}\sum_{ac=t}\mu(c)h_{\ell}(a)\cdot\frac{a}{x}\sum_{m\leq
x/a}h_{\ell}(m).$

For each $a|t$ the Lipschitz bound [4, Thm. 4] yields

$\frac{a}{x}\sum_{m\leq x/a}h_{\ell}(m)=\frac{1}{x}\sum_{m\leq
x}h_{\ell}(m)+O\left(\left(\frac{\log(3a)}{\log
x}\right)^{1-2/\pi}\log\left(\frac{\log x}{\log(3a)}\right)^{2}\right).$

It follows that

$\displaystyle
M_{h_{\ell}}(x;t)=\left(\frac{1}{t}\sum_{ac=t}\mu(c)h_{\ell}(a)\right)\frac{1}{x}\sum_{n\leq
x}h_{\ell}(n)+O(\delta_{t}(x)),$

where $\delta_{t}$ is defined via

$\delta_{t}(x):=\frac{1}{t}\sum_{ac=t}\mu^{2}(c)\left(\frac{\log(3a)}{\log
x}\right)^{1-2/\pi}\log\left(\frac{\log x}{\log(3a)}\right)^{2}.$

Now let

$\displaystyle A_{k,z}$
$\displaystyle:=\sum_{t\in\mathcal{T}_{k,z}}\frac{1}{t}\sum_{ac=t}\mu(c)h_{\ell}(a)=\sum_{ac\in\mathcal{T}_{k,z}}\frac{\mu(c)}{c}\frac{\chi^{g\ell}(a)}{a^{1+iy_{g\ell}}}.$

Then we have

(21) $\displaystyle A_{k,z}\frac{1}{x}\sum_{n\leq x}h_{\ell}(n)$
$\displaystyle=\sum_{t\in\mathcal{T}_{k,z}}M_{h_{\ell}}(x;t)+O\left(\sum_{t\in\mathcal{T}_{k,z}}\delta_{t}(x)\right).$

We next obtain an asymptotic estimate for $A_{k,z}$. Since
$ac\in\mathcal{T}_{k,z}$ if and only if there is $0\leq\nu\leq k$ such that
$a\in\mathcal{T}_{\nu,z}$ and $c\in\mathcal{T}_{k-\nu,z}$, taking into account
the number of representations of this shape we deduce that

$\displaystyle A_{k,z}$ $\displaystyle=\sum_{0\leq\nu\leq
k}\left(\sum_{c\in\mathcal{T}_{k-\nu,z}}\frac{\mu(c)}{c}\right)\left(\sum_{a\in\mathcal{T}_{\nu,z}}\frac{\chi^{g\ell}(a)}{a^{1+iy_{g\ell}}}\right)$
$\displaystyle=\sum_{0\leq\nu\leq
k}\frac{1}{(k-\nu)!\nu!}\left(\sum_{\begin{subarray}{c}p_{1},\ldots,p_{k-\nu}\leq
z\\\ \chi(p_{i})=\zeta^{j_{0}}\\\ p_{i}\text{
distinct}\end{subarray}}\frac{(-1)^{k-\nu}}{p_{1}\cdots
p_{k-\nu}}\right)\left(\sum_{\begin{subarray}{c}p\leq z\\\
\chi(p)=\zeta^{j_{0}}\end{subarray}}\frac{\chi^{\ell}(p)p^{-iy_{g\ell}}}{p}\right)^{\nu}$
(22) $\displaystyle=\frac{1}{k!}\sum_{0\leq\nu\leq
k}\binom{k}{\nu}\zeta^{j_{0}g\ell\nu}(-1)^{k-\nu}\left(\sum_{\begin{subarray}{c}p_{1},\ldots,p_{k-\nu}\leq
z\\\ \chi(p_{i})=\zeta^{j_{0}}\\\ p_{i}\text{
distinct}\end{subarray}}\frac{1}{p_{1}\cdots
p_{k-\nu}}\right)\left(\sum_{\begin{subarray}{c}p\leq z\\\
\chi(p)=\zeta^{j_{0}}\end{subarray}}\frac{p^{-iy_{g\ell}}}{p}\right)^{\nu}.$

Dispensing with the distinctness condition in the first bracketed expression
in (22), we get

$\displaystyle\sum_{\begin{subarray}{c}p_{1},\ldots,p_{k-\nu}\leq z\\\
\chi(p_{i})=\zeta^{j_{0}}\\\ p_{i}\text{
distinct}\end{subarray}}\frac{1}{p_{1}\cdots p_{k-\nu}}$
$\displaystyle=\sum_{\begin{subarray}{c}p_{1},\ldots,p_{k-\nu}\leq z\\\
\chi(p_{i})=\zeta^{j_{0}}\end{subarray}}\frac{1}{p_{1}\cdots
p_{k-\nu}}+O\left(\sum_{1\leq i<j\leq
k-\nu}\sum_{\begin{subarray}{c}p_{1},\ldots,p_{k-\nu}\leq z\\\ p_{i}=p_{j}\\\
\chi(p_{\ell})=\zeta^{j_{0}}\end{subarray}}\frac{1}{p_{1}\cdots
p_{k-\nu}}\right)$
$\displaystyle=\sigma_{j_{0}}(z)^{k-\nu}\left(1+O\left(k^{2}\sigma_{j_{0}}(z)^{-2}\right)\right),$

for each $0\leq\nu\leq k-2$. Setting

$\Theta_{j_{0},\ell}(z):=\frac{1}{\sigma_{j_{0}}(z)}\sum_{\begin{subarray}{c}p\leq
z\\\ \chi(p)=\zeta^{j_{0}}\end{subarray}}\frac{p^{-iy_{g\ell}}}{p},$

we may rewrite our expression for $A_{k,z}$ in (22) as

$\displaystyle A_{k,z}$
$\displaystyle=\left(1+O(k^{2}\sigma_{j_{0}}(z)^{-2})\right)\frac{\sigma_{j_{0}}(z)^{k}}{k!}\sum_{0\leq\nu\leq
k}\binom{k}{\nu}\left(\zeta^{j_{0}g\ell}\Theta_{j_{0},\ell}(z)\right)^{\nu}(-1)^{k-\nu}$
$\displaystyle=\left(1+O(k^{2}\sigma_{j_{0}}(z)^{-2})\right)\frac{\sigma_{j_{0}}(z)^{k}}{k!}\left(\zeta^{j_{0}g\ell}\Theta_{j_{0},\ell}(z)-1\right)^{k}.$

Next, we estimate $\Theta_{j_{0},\ell}(z)$. Set
$z_{0}:=\min\\{z,e^{1/|y_{g\ell}|}\\}$. By Mertens’ theorem and (20), we find

$\displaystyle\sum_{\begin{subarray}{c}p\leq z\\\
\chi(p)=\zeta^{j_{0}}\end{subarray}}\frac{|1-p^{-iy_{g_{\ell}}}|}{p}\ll\sum_{p\leq
e^{1/|y_{g\ell}|}}\frac{|y_{g\ell}|\log p}{p}+\sum_{z_{0}<p\leq
z}\frac{1}{p}\ll 1+\log\left(|y_{g\ell}|\log z\right)\ll
m^{2}\log(1/\varepsilon).$

We deduce therefore that

(23)
$\displaystyle\Theta_{j_{0},\ell}(z)=1+O\left(\frac{m^{2}\log(1/\varepsilon)}{\sigma_{j_{0}}(z)}\right),$

so that we may finally conclude that

$\displaystyle A_{k,z}$
$\displaystyle=\left(1+O(k^{2}\sigma_{j_{0}}(z)^{-2})\right)\frac{\sigma_{j_{0}}(z)^{k}}{k!}\left(\zeta^{j_{0}g\ell}-1+O\left(\frac{m^{2}\log(1/\varepsilon)}{\sigma_{j_{0}}(z)}\right)\right)^{k}.$

We now obtain an upper bound for the right-hand side in (21), beginning with
the average value of $M_{h_{\ell}}(x;t)$. By the Cauchy-Schwarz inequality,

(24) $\displaystyle\left|\sum_{t\in\mathcal{T}_{k,z}}M_{h_{\ell}}(x;t)\right|$
$\displaystyle=\left|\frac{1}{x}\sum_{n\leq
x}h_{\ell}(n)\left(\sum_{t\in\mathcal{T}_{k,z}}f_{t}(n)\right)\right|\leq\left(\frac{1}{x}\sum_{n\leq
x}\left|\sum_{t\in\mathcal{T}_{k,z}}f_{t}(n)\right|^{2}\right)^{1/2}=\left(\sum_{t_{1},t_{2}\in\mathcal{T}_{k,z}}\frac{1}{x}\sum_{n\leq
x}f_{t_{1}}(n)f_{t_{2}}(n)\right)^{1/2}.$

Next, fixing $t_{1},t_{2}\in\mathcal{T}_{k,z}$ for the moment we observe that

$\displaystyle\sum_{n\leq x}f_{t_{1}}(n)f_{t_{2}}(n)$
$\displaystyle=\sum_{a_{1}c_{1}=t_{1}}\sum_{a_{2}c_{2}=t_{2}}\frac{\mu(c_{1})\mu(c_{2})}{c_{1}c_{2}}\sum_{\begin{subarray}{c}n\leq
x\\\
[a_{1},a_{2}]|n\end{subarray}}1=\sum_{a_{1}c_{1}=t_{1}}\sum_{a_{2}c_{2}=t_{2}}\frac{\mu(c_{1})\mu(c_{2})}{c_{1}c_{2}}\left(\frac{x}{[a_{1},a_{2}]}+O(1)\right)$
$\displaystyle=\frac{x}{t_{1}t_{2}}\sum_{a_{1}c_{1}=t_{1}}\sum_{a_{2}c_{2}=t_{2}}\mu(c_{1})\mu(c_{2})(a_{1},a_{2})+O(d(t_{1})d(t_{2})),$

where $d(t)$ is the divisor function. For each pair of divisors
$a_{1}c_{1}=t_{1}$, notice that999Given $n\in\mathbb{N}$ and a prime $p$ we
write $\nu_{p}(n)$ to be the maximal power $\nu\geq 0$ such that $p^{\nu}|n$.

(25)
$\sum_{a_{2}c_{2}=t_{2}}\mu(c_{2})(a_{1},a_{2})=\prod_{p^{\nu}||t_{2}}\left(p^{\min\\{\nu,\nu_{p}(a_{1})\\}}-p^{\min\\{\nu-1,\nu_{p}(a_{1})\\}}\right),$

which is non-zero precisely when

$\nu_{p}(a_{1})\geq\nu\text{ for all }p^{\nu}||t_{2},\text{ i.e.,
}t_{2}|a_{1}.$

In this case, the left-hand side of (25) is precisely
$\phi(t_{2})1_{t_{2}|a_{1}}$. Since $a_{1}|t_{1}$ we get $t_{2}|t_{1}$. Making
the change of variables $a_{1}=t_{2}A_{1}$, we find

$\displaystyle\sum_{n\leq x}f_{t_{1}}(n)f_{t_{2}}(n)$
$\displaystyle=\frac{x\phi(t_{2})}{t_{1}t_{2}}1_{t_{2}|t_{1}}\sum_{\begin{subarray}{c}A_{1}c_{1}=t_{1}/t_{2}\end{subarray}}\mu(c_{1})+O(d(t_{1})d(t_{2}))$
$\displaystyle=\frac{x\phi(t_{2})}{t_{1}t_{2}}1_{t_{2}=t_{1}}+O(d(t_{1})d(t_{2}))=\frac{x\phi(t)}{t^{2}}1_{t_{1}=t_{2}=t}+O(d(t_{1})d(t_{2})).$

Substituting this back into (24), using $d(t)\leq 2^{k}$ for all
$t\in\mathcal{T}_{k,z}$ and $|\mathcal{T}_{k,z}|\leq\pi(z)^{k}$, we obtain

$\displaystyle\left|\sum_{t\in\mathcal{T}_{k,z}}M_{h_{\ell}}(x;t)\right|$
$\displaystyle\ll\left(\sum_{t\in\mathcal{T}_{k,z}}\frac{\phi(t)}{t^{2}}\right)^{1/2}+\left(\frac{1}{x}\sum_{t_{1},t_{2}\in\mathcal{T}_{k,z}}d(t_{1})d(t_{2})\right)^{1/2}$
$\displaystyle\ll\sigma_{j_{0}}(z)^{k/2}+\frac{(2\pi(z))^{k}}{\sqrt{x}}.$

Finally, we estimate the contribution to (21) from $\delta_{t}(x)$. Applying
the trivial bound $a\leq t$ in the sum defining $\delta_{t}(x)$, we get

$\displaystyle\delta_{t}(x)\leq\frac{d(t)}{t}\left(\frac{\log t}{\log
x}\right)^{1-2/\pi}\log\left(\frac{\log x}{\log
t}\right)^{2}\ll\frac{d(t)}{t}\left(\frac{\log t}{\log x}\right)^{\rho},$

for any $0<\rho<1-2/\pi$. Using the simple inequality

$(a_{1}+\cdots+a_{m})^{\rho}\leq a_{1}^{\rho}+\cdots+a_{m}^{\rho},\quad
a_{j}\in(0,\infty),$

together with Mertens’ theorem and partial summation, we deduce that

$\displaystyle\sum_{t\in\mathcal{T}_{k,z}}\delta_{t}(x)$
$\displaystyle\leq\frac{1}{(\log
x)^{\rho}}\sum_{t\in\mathcal{T}_{k,z}}\frac{d(t)}{t}\left(\sum_{p^{\nu}||t}\log
p^{\nu}\right)^{\rho}$ $\displaystyle\leq\frac{1}{(\log
x)^{\rho}}\sum_{\begin{subarray}{c}p\leq z\\\ \nu\geq
1\end{subarray}}\frac{(\nu+1)(\log
p^{\nu})^{\rho}}{p^{\nu}}\sum_{\begin{subarray}{c}t^{\prime}\in\mathcal{T}_{k-\nu,z}\\\
p\nmid t^{\prime}\end{subarray}}\frac{d(t^{\prime})}{t^{\prime}}$
$\displaystyle\ll\left(\frac{\log z}{\log
x}\right)^{\rho}(2\sigma_{j_{0}}(z))^{k-1}.$

Consequently, when $km\leq\eta\sqrt{\sigma_{j_{0}}(z)}$ for $\eta>0$ small
enough, we find that

$\displaystyle\frac{1}{x}\left|\sum_{n\leq x}h_{\ell}(n)\right|$
$\displaystyle\ll\frac{\sigma_{j_{0}}(z)^{k}}{|A_{k,z}|}\left(\sigma_{j_{0}}(z)^{-k/2}+2^{k}\left(\frac{\log
z}{\log
x}\right)^{\rho}\sigma_{j_{0}}(z)^{-1}+\frac{(2\pi(z))^{k}}{\sqrt{x}}\right).$

Recall that $h_{\ell}(n)=\chi^{g\ell}(n)n^{-iy_{g\ell}}$. Recalling the bound
(20) and applying [4, Lem. 7.1], we obtain

$\displaystyle\left|\frac{1}{x}\sum_{n\leq x}\chi^{g\ell}(n)\right|$
$\displaystyle=(1+|y_{g\ell}|)\left|\frac{1}{x}\sum_{n\leq
x}h_{\ell}(n)\right|+O\left(\frac{\exp\left(\mathbb{D}(\chi^{g\ell},n^{iy_{g\ell}};x)\sqrt{(2+o(1))\log\log
x}\right)}{\log x}\right)$ $\displaystyle\ll\left|\frac{1}{x}\sum_{n\leq
x}h_{\ell}(n)\right|+\frac{1}{\sqrt{\log x}}$ (26)
$\displaystyle\ll\frac{\sigma_{j_{0}}(z)^{k}}{|A_{k,z}|}\left(\sigma_{j_{0}}(z)^{-k/2}+2^{k}\left(\frac{\log
z}{\log
x}\right)^{\rho}\sigma_{j_{0}}(z)^{-1}+\frac{(2\pi(z))^{k}}{\sqrt{x}}\right).$

whenever $m^{2}\log(1/\varepsilon)<c\log\log x$ for $c>0$ small enough. In
light of the lower bound

$|1-\zeta^{j_{0}g\ell}|=2|\sin(\pi j_{0}g\ell/d)|\geq
4\|j_{0}g\ell/d\|=4\|j_{0}\ell/r\|,$

we obtain that

$|A_{k,z}|\gg\frac{4^{k}\sigma_{j_{0}}(z)^{k}}{k!}\left(\left\|\frac{j_{0}\ell}{r}\right\|+O\left(\frac{m^{2}\log(1/\varepsilon)}{\sigma_{j_{0}}(z)}\right)\right)^{k}.$

Finally, as $z^{k}\leq x^{1/3}$, the last error term in (26) is $O(x^{-1/6})$.
The claim now follows upon rearranging. ∎

The bound in Proposition 4.2 is only efficient provided we can obtain a lower
bound for $\|j_{0}\ell/r\|$ for many $\ell$. The purpose of the next result is
to bound the number of $\ell$ for which $\|j_{0}\ell/r\|$ is small.

######  Proposition 4.3.

With the above notation, there is an absolute constant $C>0$ such that if

$\theta_{0}:=C\left(\frac{m^{2}\eta^{-1}\log(1/\varepsilon)}{\log\log
d}\right)^{1/2}.$

then at least one of the following is true:

  1. (i)

$|S_{\chi}(x)|\leq\varepsilon x$, and

  2. (ii)

$(j_{0},r)\leq\theta_{0}r$.

Moreover, in the second case we find that for any $\theta\in[\theta_{0},1/2]$,

$|\\{1\leq\ell\leq r:\|j_{0}\ell/r\|\leq\theta\\}|\ll\theta r.$

###### Proof.

Assume (i) fails, so that $|S_{\chi}(x)|\geq\varepsilon x$, i.e.,
$1\in\mathcal{C}_{d}(\varepsilon)$. By Proposition 3.1, $g\ell\equiv
1\pmod{d}$ for some $g|d$, whence $g=1$, and

$\mathbb{D}(\chi,1;x)^{2}\leq 200m^{2}\log(1/\varepsilon).$

Combining this with (17) and $\ell=1$, we find that

(27) $200m^{2}\log(1/\varepsilon)\geq 8\sum_{1\leq j\leq
d-1}\left\|\frac{j}{d}\right\|^{2}\sigma_{j}\geq
8\left\|\frac{j_{0}}{d}\right\|^{2}\sigma_{j_{0}}\geq
8\eta\left\|\frac{j_{0}}{d}\right\|^{2}\Sigma_{\chi}(x).$

Let $\gamma:=(j_{0},d)$ and put $\tilde{j}_{0}:=j_{0}/\gamma$, $D:=d/\gamma$.
Since

$\|j_{0}/d\|=\|\tilde{j}_{0}/D\|\geq 1/D=\gamma/d,$

it follows from Proposition 2.5 that there is a constant $C>0$ such that

$\gamma\leq
d\left(\frac{25m^{2}\eta^{-1}\log(1/\varepsilon)}{\Sigma_{\chi}(x)}\right)^{1/2}\leq
Cd\left(\frac{m^{2}\eta^{-1}\log(1/\varepsilon)}{\log\log
d}\right)^{1/2}=\theta_{0}d.$

Since $r=d$, $(j_{0},r)/r=(j_{0},d)/d$ and (ii) follows.
Next, write $R:=r/(r,j_{0})$ and $J_{0}:=j_{0}/(r,j_{0})$. Dividing
$\ell=mR+L$ with $0\leq m\leq r/R-1$ and $1\leq L\leq R$, observe that

$\|j_{0}\ell/r\|=\|J_{0}\ell/R\|=\|J_{0}L/R\|.$

Let $\theta\in[\theta_{0},1/2]$. As $(J_{0},R)=1$, taking $V:=R/2$ and
applying the Erdős-Turán inequality [14, I.6.15], we obtain

$\displaystyle\left|\left|\left\\{1\leq L\leq
R:\,\left\|\frac{J_{0}L}{R}\right\|\leq\theta\right\\}\right|-2\theta
R\right|$ $\displaystyle\ll R\left(\frac{1}{V}+\sum_{1\leq\nu\leq
V}\frac{1}{\nu}\left|\frac{1}{R}\sum_{\begin{subarray}{c}1\leq L\leq
R\end{subarray}}e\left(\frac{\nu J_{0}L}{R}\right)\right|\right)$
$\displaystyle=R\left(\frac{1}{V}+\sum_{\begin{subarray}{c}1\leq\nu\leq V\\\
R|J_{0}\nu\end{subarray}}\frac{1}{\nu}\right)\ll 1.$

It follows that

$|\\{1\leq\ell\leq
r:\|j_{0}\ell/r\|\leq\theta\\}|=\frac{r}{R}\cdot\left(2\theta
R+O(1)\right)=r\left(2\theta+O(1/R)\right).$

As $R=r/(j_{0},r)>\theta^{-1}$, we obtain

$|\\{1\leq\ell\leq r:\|j_{0}\ell/r\|\leq\theta\\}|\ll\theta r,$

as claimed. ∎

###### Proof of Theorem 1.1.

Since the bound in the theorem is otherwise trivial, we may assume that $d$ is
larger than any fixed constant. Hence, we may assume that $x$ is also larger
than any fixed constant, given the constraint $x>q^{\delta}$.
Let $\tau\in(0,1/2)$ and let $\varepsilon:=\Sigma_{\chi}(x)^{-1/(6+\tau)}$ and
suppose throughout that $|S_{\chi}(x)|\geq\varepsilon x$. Assume for the sake
of contradiction that $|\mathcal{C}_{d}(\varepsilon)|\geq\varepsilon d$.
By Proposition 3.1 we find integers $1\leq m\leq\varepsilon^{-2}$ and $1\leq
g\leq\varepsilon^{-1}$ such that

$\max_{1\leq\ell\leq d/g}\mathbb{D}(\chi^{g\ell},1;x)^{2}\ll
m^{2}\log(1/\varepsilon).$

Fix $\eta=\theta=\varepsilon^{\tau/30}$, so that since

$\theta_{0}\ll\left(\frac{\varepsilon^{-4-\tau/30}\log(1/\varepsilon)}{\varepsilon^{-(6+\tau)}}\right)^{1/2}\ll\varepsilon^{1/2},$

we have $\theta\in[\theta_{0},1/2]$, when $\varepsilon$ is sufficiently small.
Let $1\leq j_{0}\leq d-1$ be an index satisfying

$\sigma_{j_{0}}(x)=\max_{1\leq j\leq d-1}\sigma_{j}(x).$

If $\sigma_{j_{0}}(x)\leq\tfrac{\eta}{g}\Sigma_{\chi}(x)$ then by Proposition
4.1 we can find $1\leq\ell\leq d/g$ such that

$\mathbb{D}(\chi^{g\ell},1;x)^{2}\geq\tfrac{1}{2}\Sigma_{\chi}(x).$

Comparing these bounds using Proposition 2.5 and $m\leq\varepsilon^{-2}$, we
find

$\varepsilon^{-6-\tau}=\Sigma_{\chi}(x)\ll
m^{2}\log(1/\varepsilon)\leq\varepsilon^{-4}\log(1/\varepsilon),$

which is a101010We emphasise that this part of the argument is independent of
the assumption $|S_{\chi}(x)|\geq\varepsilon x$. contradiction.
Next, suppose $\sigma_{j_{0}}(x)>\tfrac{\eta}{g}\Sigma_{\chi}(x)$. Since
$1\in\mathcal{C}_{d}(\varepsilon)$ we deduce that $g=1$, and $d=r$. Let $M\geq
2$ be a parameter to be chosen later, and set $z:=x^{1/M}$. We have the crude
lower bound

$\sigma_{j_{0}}(z)\geq\sigma_{j_{0}}(x)-\sum_{x^{1/M}<p\leq
x}\frac{1}{p}\geq\eta\Sigma_{\chi}(x)-\log M-O(1).$

Assume henceforth that $M$ is chosen so that $\log
M\leq\frac{\eta}{3}\Sigma_{\chi}(x)$. Thus, when $d$ is large enough we have

$\sigma_{j_{0}}(z)\geq\frac{\eta}{2}\Sigma_{\chi}(x).$

We first establish the existence of $\ell$ with $\|j_{0}\ell/d\|>\theta$.
Assume for the sake of contradiction that

$\max_{\tilde{\ell}\in\mathcal{C}_{d}(\varepsilon)}\|j_{0}\tilde{\ell}/d\|\leq\theta/m.$

Since $\mathbb{Z}/\ell\mathbb{Z}=m\mathcal{C}_{d}(\varepsilon)$, if

$\ell\equiv a_{1}+\cdots+a_{m}\pmod{d},\quad
a_{i}\in\mathcal{C}_{d}(\varepsilon)$

then the triangle inequality implies that for every $1\leq\ell\leq d$,

$\left\|\frac{j_{0}\ell}{d}\right\|\leq\sum_{1\leq i\leq
m}\left\|\frac{j_{0}a_{i}}{d}\right\|\leq m\cdot\frac{\theta}{m}\leq\theta.$

On the other hand, since $|S_{\chi}(x)|\geq\varepsilon x$, Proposition 4.3
shows that

$|\\{1\leq\ell\leq d:\|j_{0}\ell/d\|\leq\theta\\}|\ll\theta d,$

which is a contradiction. In particular, there must exist
$\ell\in\mathcal{C}_{d}(\varepsilon)$ for which $\|j_{0}\ell/d\|>\theta/m$.
Note that by our parameter choices, we have

$\frac{m^{2}\log(1/\varepsilon)}{\sigma_{j_{0}}(z)}<\frac{2m^{2}\eta^{-1}\log(1/\varepsilon)}{\Sigma_{\chi}(x)}\ll\varepsilon^{6+\tau-4-\tau/2}=\varepsilon^{2+\tau/2}\leq\varepsilon^{\tau/4}\frac{\theta}{m}<\varepsilon^{\tau/4}\left\|\frac{j_{0}\ell}{d}\right\|.$

Taking $\rho=1/4$ and applying Proposition 4.2 we thus find that if

$1\leq k\leq\min\left\\{\frac{M}{3},\sqrt{\eta\Sigma_{\chi}(x)}\right\\}$

then for any $1\leq\ell\leq r$ for which $r\nmid j_{0}\ell$ we have

(28) $\displaystyle\frac{1}{x}|S_{\chi^{\ell}}(x)|\ll
k!\left\|\frac{j_{0}\ell}{r}\right\|^{-k}\left(\left(\frac{1}{\eta\Sigma_{\chi}(x)}\right)^{k/2}+\frac{1}{\eta
M^{1/4}\Sigma_{\chi}(x)}+x^{-1/6}\right).$

By Proposition 3.1, $\mathcal{C}_{d}(\varepsilon)\subseteq
m\mathcal{C}_{d}(\varepsilon)=\mathbb{Z}/d\mathbb{Z}$. We deduce using $k!\leq
k^{k}$ that

$\varepsilon\leq\frac{1}{x}|S_{\chi^{g\ell}}(x)|\ll\left(\left(\frac{(km)^{2}}{\eta\theta^{2}\Sigma_{\chi}(x)}\right)^{k/2}+\frac{(2km/\theta)^{k}}{\eta
M^{1/4}\Sigma_{\chi}(x)}\right).$

As $m\leq\varepsilon^{-2}$, we get that

(29)
$\varepsilon\ll\left(\left(\frac{k^{2}\varepsilon^{-4}}{\eta\theta^{2}\Sigma_{\chi}(x)}\right)^{k/2}+\frac{(2k/(\varepsilon^{2}\theta))^{k}}{\eta
M^{1/4}\Sigma_{\chi}(x)}\right).$

Set now $\eta=\theta=\varepsilon^{\tau/30}$, choose $M$ so that $\log
M=\frac{\eta}{3}\Sigma_{\chi}(x)$ and select

$k:=\left\lfloor\frac{10}{\tau}\sqrt{\varepsilon^{4+\tau/2}\Sigma_{\chi}(x)}\right\rfloor.$

We then find that if $d$ is sufficiently large relative to $\tau$ then

$\displaystyle\left(\frac{k^{2}\varepsilon^{-4}}{\eta\theta^{2}\Sigma_{\chi}(x)}\right)^{k/2}$
$\displaystyle\leq\left(100\tau^{-2}\varepsilon^{2\tau/5}\right)^{\frac{5}{\tau}}\ll_{\tau}\varepsilon^{2},$

on the one hand, and also

$\displaystyle\frac{(2k/(\varepsilon^{2}\theta))^{k}\varepsilon^{-1}}{\eta
M^{1/4}\Sigma_{\chi}(x)}$
$\displaystyle\ll\frac{1}{\varepsilon^{31/30}\Sigma_{\chi}(x)}\exp\left(-\frac{\varepsilon^{31/30}}{12}\Sigma_{\chi}(x)+10\frac{\varepsilon^{5/2}}{\tau}\Sigma_{\chi}(x)^{1/2}\log\Sigma_{\chi}(x)\right)$
$\displaystyle\ll\Sigma_{\chi}(x)^{-2/3}e^{-\frac{\varepsilon^{2}}{24}\Sigma_{\chi}(x)}\ll\Sigma_{\chi}(x)^{-100}$
$\displaystyle\ll\varepsilon^{600},$

on the other. It follows that (29) yields a contradiction.
We conclude, therefore, that $|\mathcal{C}_{d}(\varepsilon)|\leq\varepsilon
d$, and therefore

$\frac{1}{d}\sum_{1\leq\ell\leq
d}|S_{\chi^{\ell}}(x)|^{2}\leq\varepsilon^{2}+\frac{|\mathcal{C}_{d}(\varepsilon)|}{d}\leq\varepsilon.$

As $\varepsilon=\Sigma_{\chi}(x)^{-1/(6+\tau)}\ll(\log\log
d)^{-\tfrac{1}{6}+\tau}$ by Proposition 2.5, the proof of the theorem follows.
∎

##  5\. Proof of Theorem 1.2

In this section, we present the proof of Theorem 1.2. For convenience, we
introduce the notation

$M_{d,\chi}(x):=\max_{\alpha^{d}=1}|\\{n\leq x:\chi(n)=\alpha\\}|.$

We begin by establishing a couple of lemmas.

######  Lemma 5.1.

We have

$M_{d,\chi}(x)\leq\min_{r|d}M_{r,\chi^{d/r}}(x).$

###### Proof.

It clearly suffices to prove that $M_{d,\chi}(x)\leq M_{r,\chi^{d/r}}(x)$ for
each $r|d$. Thus, fix $r|d$ and let $\psi:=\chi^{d/r}$. Let $\alpha$ be a
$d$th order root of unity for which

$M_{d,\chi}(x)=|\\{n\leq x:\chi(n)=\alpha\\}|,$

and let $\beta:=\alpha^{d/r}$. Then $\psi(n)=\beta$ whenever $\chi(n)=\alpha$.
Since $\beta$ is a root of unity of order $r$, we obtain

$M_{d,\chi}(x)\leq|\\{n\leq x:\psi(n)=\beta\\}|\leq M_{r,\psi}(x),$

as claimed. ∎

######  Lemma 5.2.

Let $\chi$ be a character modulo $q$ of order $d$, and let $K\geq 1$. Then

$M_{d,\chi}(x)\leq\min\left\\{\left(\frac{1}{d}\sum_{1\leq\ell\leq
d}|S_{\chi^{\ell}}(x)|^{2}\right)^{\tfrac{1}{2}},\,\frac{x}{d}+\frac{x}{K+1}+\frac{2}{3}\sum_{1\leq
k\leq K}\frac{|S_{\chi^{k}}(x)|}{k}\right\\}.$

###### Proof.

We prove each of the above bounds in sequence. The proof of the first, which
is already invoked in [12, Sec. 3.2], is as follows. Given any $d$th root of
unity $\alpha$ we have

$\displaystyle|\\{n\leq x:\chi(n)=\alpha\\}|=|\\{n,m\leq
x:\chi(n)=\chi(m)=\alpha\\}|^{1/2}$ $\displaystyle\leq|\\{n,m\leq
x:\chi(n)=\chi(m)\\}|^{1/2}$ (30)
$\displaystyle=\left(\frac{1}{d}\sum_{\ell=0}^{d-1}|S_{\chi^{\ell}}(x)|^{2}\right)^{1/2}.$

Maximising over $\alpha$, the first alternative bound for $M_{d,\chi}(x)$
holds.
For the second bound, set $N:=|\\{n\leq x:(n,q)=1\\}$ and for each $(n,q)=1$
write $\chi(n)=e(\theta_{n})$ for some $\theta_{n}\in[0,1]$. Specifying that
$\chi(n)=\alpha=e(a/d)$ is equivalent to

$\theta_{n}\in\left[\frac{a}{d},\frac{a+1}{d}\right).$

By the Erdős-Turán inequality (in the form given in [14, I.6.15]), for any
$K\geq 1$ we have

$\displaystyle|\\{n\leq x:\chi(n)=\alpha\\}|$
$\displaystyle\leq\frac{N}{d}+\sup_{I\subseteq[0,1)}\left|\,|\\{n\leq
x:\,(n,q)=1,\,\theta_{n}\in I\\}|-|I|N\,\right|$ $\displaystyle\leq
N\left(\frac{1}{d}+\frac{1}{K+1}+\frac{2}{3}\sum_{1\leq k\leq
K}\frac{1}{k}\left|\frac{1}{N}\sum_{\begin{subarray}{c}1\leq n\leq x\\\
(n,q)=1\end{subarray}}e(k\theta_{n})\right|\right)$ (31) $\displaystyle\leq
x\left(\frac{1}{d}+\frac{1}{K+1}+\frac{2}{3}\sum_{1\leq k\leq
K}\frac{1}{k}\left|\frac{1}{x}\sum_{n\leq x}\chi(n)^{k}\right|\right).$

This implies the claim. ∎

###### Proof of Theorem 1.2.

Let $c_{1}>0$ be a sufficiently small constant to be determined later. Given
$1\leq z\leq\log\log d$, write

$\delta_{z}:=\max\left\\{\left(\frac{\log\log(ed_{z})}{c_{1}\log(ed_{z})}\right)^{1/2},(\log
q)^{-c_{1}}\right\\},\quad d_{z}:=\prod_{\begin{subarray}{c}p^{k}||d\\\
p>z\end{subarray}}\text{ and }r_{z}:=d/d_{z}.$

By Lemma 5.1 we have

$M_{d,\chi}(x)\leq\min_{r|d}M_{r,\chi^{d/r}}(x)\leq\min_{\begin{subarray}{c}1\leq
z\leq\log\log d\\\ x>q^{\delta_{z}}\end{subarray}}M_{d_{z},\chi^{r_{z}}}(x).$

For ease of notation, we write $\tilde{d}:=d_{z_{0}}$ and
$\tilde{\chi}:=\chi^{r_{z_{0}}}$, where $1\leq z_{0}\leq\log\log d$ minimises
this latter upper bound, subject to the condition that $x>q^{\delta_{z_{0}}}$.
In the remainder of the proof, we show that

(32) $M_{\tilde{d},\tilde{\chi}}(x)\leq
x\left(\frac{1}{P^{-}(\tilde{d})}+O\left(\frac{1}{(\log\log\tilde{d})^{c}}\right)\right),$

and since $P^{-}(\tilde{d})>z_{0}$ this provides the required upper bound.
Similarly to the proof of Theorem 1.1, let
$\varepsilon:=\Sigma_{\chi}(x)^{-1/7}$
Case 1: Assume first that $\phi(q)/q<\frac{1}{(\log d)^{1/10}}$. Picking
$K:=\lfloor(\log d)^{1/10}\rfloor$ in (5), together with the uniform upper
bound

$\left|S_{\tilde{\chi}^{k}}(x)\right|\leq\sum_{\begin{subarray}{c}n\leq x\\\
(n,q)=1\end{subarray}}1\ll\frac{\phi(q)}{q}x\leq\frac{x}{(\log d)^{1/5}}$

(using [6] as before), we deduce that

$M_{\tilde{d},\tilde{\chi}}(x)\leq
x\left(\frac{1}{\tilde{d}}+\varepsilon+O\left(\frac{x}{(\log
d)^{1/5}}\sum_{1\leq k\leq(\log
d)^{1/10}}\frac{1}{k}\right)\right)\ll\frac{x\log\log
d}{(\log\tilde{d})^{1/5}},$

which is more than enough suffices for the bound we seek. In the remaining
cases we shall assume that $\phi(q)/q>\frac{1}{(\log d)^{1/10}}$, and in
particular by Proposition 2.5, $\Sigma_{\chi}(x)>c\log\log d$ for some
absolute constant $c>0$. We assume this lower bound henceforth.

Case 2: Assume next that
$|\mathcal{C}_{\tilde{d}}(\varepsilon)|\leq\varepsilon\tilde{d}$. By (5), we
have

$\displaystyle M_{\tilde{d},\tilde{\chi}}(x)$
$\displaystyle\leq\left(\frac{1}{\tilde{d}}\sum_{\ell\notin\mathcal{C}_{\tilde{d}}(\varepsilon)}|S_{\tilde{\chi}^{\ell}}(x)|^{2}+\frac{1}{\tilde{d}}\sum_{\ell\in\mathcal{C}_{\tilde{d}}(\varepsilon)}|S_{\tilde{\chi}^{\ell}}(x)|^{2}\right)^{1/2}$
$\displaystyle\leq\left(\varepsilon^{2}x^{2}+x^{2}\frac{|\mathcal{C}_{\tilde{d}}(\varepsilon)|}{\tilde{d}}\right)^{1/2}\leq
2\sqrt{\varepsilon}x\ll\frac{x}{(\log\log\tilde{d})^{1/14}},$

which is more than sufficient.

Case 3: Assume $|\mathcal{C}_{\tilde{d}}(\varepsilon)|>\varepsilon\tilde{d}$
and $\varepsilon^{-7}=\Sigma_{\tilde{\chi}}(x)\geq c\log\log\tilde{d}$. We
consider several subcases below.

Case 3.(i): Assume that $g>1$ in Proposition 3.1. Since $g|\tilde{d}$, we have
$g\geq P^{-}(\tilde{d})$, and as
$\mathcal{C}_{\tilde{d}}(\varepsilon)\subseteq\\{g\ell:1\leq\ell<\tilde{d}/g\\}$
we have that $|S_{\tilde{\chi}^{k}}(x)|\leq\varepsilon x$ for all $1\leq k<g$.
Applying (5) with $K=g-1$ and recalling that $g\leq\varepsilon^{-1}$, we get

$M_{\tilde{d},\tilde{\chi}}(x)\leq
x\left(\frac{1}{\tilde{d}}+\frac{1}{g}+O\left(\varepsilon\log
g\right)\right)\leq
x\left(\frac{1}{P^{-}(\tilde{d})}+O\left(\frac{\log\log\log\tilde{d}}{(\log\log\tilde{d})^{1/7}}\right)\right),$

which implies the bound (32) in this case. We will assume for the remaining
subcases that $g=1$.

Case 3.(ii) If $|S_{\tilde{\chi}}(x)|>\varepsilon x$ then as
$x>q^{\delta_{z_{0}}}$, Theorem 1.1 immediately implies that

$\frac{1}{\tilde{d}}\sum_{\ell=0}^{\tilde{d}-1}|S_{\tilde{\chi}^{\ell}}(x)|^{2}\ll\frac{x}{(\log\log\tilde{d})^{1/7}},$

and the claimed bound (with $c=1/14$) follows from (5).

Case 3. (iii) If $|S_{\tilde{\chi}}(x)|\leq\varepsilon x$ and (recalling
$g=1$) $\max_{1\leq
j\leq\tilde{d}-1}\sigma_{j}(x)\leq\eta\Sigma_{\tilde{\chi}}(x)$ then we obtain
a contradiction to
$|\mathcal{C}_{\tilde{d}}(\varepsilon)|>\varepsilon\tilde{d}$ as in the proof
of Theorem 1.1 (as this part of the argument did not require
$|S_{\tilde{\chi}}(x)|>\varepsilon x$). We deduce that
$|\mathcal{C}_{\tilde{d}}(\varepsilon)|\leq\varepsilon\tilde{d}$, and the
claim follows from Case 2 above.

Case 3.(iv) Assume that $|S_{\tilde{\chi}}(x)|\leq\varepsilon x$,
$\sigma_{j_{0}}(x)=\max_{1\leq
j\leq\tilde{d}-1}\sigma_{j}(x)>\eta\Sigma_{\tilde{\chi}}(x)$ and (as
$r=\tilde{d}/g=\tilde{d}$) $(j_{0},\tilde{d})\leq\theta\tilde{d}$, noting that
here $\theta>\varepsilon^{1/2}$. From this, we deduce by Proposition 4.3 that
there exists an $\ell$ such that $\|j_{0}\ell/\tilde{d}\|>\theta/m$. Following
the proof of Theorem 1.1, this was enough to deduce a contradiction to the
assumption $|\mathcal{C}_{\tilde{d}}(\varepsilon)|>\varepsilon\tilde{d}$, and
so the claim of the current proposition follows once again from Case 2.

Case 3. (v) Finally, we assume the following data:

  * •

$g=1$, so $r=\tilde{d}$

  * •

$|S_{\tilde{\chi}}(x)|\leq\varepsilon x$,

  * •

$\sigma_{j_{0}}(x)>\eta\Sigma_{\tilde{\chi}}(x)$

  * •

$\Sigma_{\tilde{\chi}}(x)>c\log\log\tilde{d}$

  * •

$(j_{0},\tilde{d})>\theta\tilde{d}$.

Set $R:=\tilde{d}/(j_{0},\tilde{d})<\theta^{-1}$, and note that for each
$1\leq k\leq R-1$ we have

$\left\|\frac{j_{0}k}{\tilde{d}}\right\|=\left\|\frac{k(j_{0}/(j_{0},\tilde{d}))}{R}\right\|\geq\frac{1}{R},$

since $j/(j_{0},\tilde{d})$ is coprime to $R$. It follows from equation (17)
that for every $1\leq k\leq R-1$,

$\mathbb{D}(\tilde{\chi}^{k},1;x)^{2}\geq 8\sum_{1\leq
j\leq\tilde{d}-1}\left\|\frac{jk}{\tilde{d}}\right\|^{2}\sigma_{j}(x)\geq
8\left\|\frac{j_{0}k}{\tilde{d}}\right\|^{2}\sigma_{j_{0}}(x)>\frac{8\eta}{R^{2}}\Sigma_{\tilde{\chi}}(x)\geq
8\eta\theta^{2}\Sigma_{\tilde{\chi}}(x).$

Now, either (a) $k\notin\mathcal{C}_{\tilde{d}}(\varepsilon)$, or else (b)
$k\in m\mathcal{C}_{\tilde{d}}(\varepsilon)$. In case (a) we immediately have
$|S_{\tilde{\chi}^{k}}(x)|\leq\varepsilon x$. Thus, assume that (b) holds.
From the proof of Proposition 3.1, if $t_{k}$ is a minimiser for
$\mathbb{D}(\tilde{\chi}^{k},n^{it};x)$ from
$[-2m/\varepsilon^{2},2m/\varepsilon^{2}]$ then $|t_{k}|\log x\leq
3\varepsilon^{-64m^{2}}$, and therefore

$\mathbb{D}(1,n^{it_{k}};x)^{2}=\log(1+|t_{k}|\log x)+O(1)\leq
64m^{2}\log(1/\varepsilon)+O(1)\leq
64\varepsilon^{-4}\log(1/\varepsilon)+O(1).$

Now, by the pretentious triangle inequality we have

$\displaystyle\mathbb{D}(\tilde{\chi}^{k},n^{it_{k}};x)$
$\displaystyle\geq\mathbb{D}(\tilde{\chi}^{k},1;x)-\mathbb{D}(1,n^{it_{k}};x).$

Given the bound $\eta,\theta>\varepsilon^{1/8}$, we have

$\mathbb{D}(\tilde{\chi}^{k},1;x)>\left(8\eta\theta^{2}\right)^{1/2}\Sigma_{\tilde{\chi}}(x)^{1/2}>2\sqrt{2}\varepsilon^{3/16-7/2}\geq
2\sqrt{2}\varepsilon^{-3}>20\varepsilon^{-2}\log(1/\varepsilon)\geq
2\mathbb{D}(1,n^{it_{k}};x).$

whenever $\tilde{d}$ is sufficiently large. Hence we have

$\mathbb{D}(\tilde{\chi}^{k},n^{it_{k}};x)^{2}\geq\frac{1}{4}\mathbb{D}(\tilde{\chi}^{k},1;x)^{2}>2\eta\theta^{2}\Sigma_{\tilde{\chi}}(x)>2c\varepsilon^{-6}.$

Applying Halász’ theorem (with $T=m/\varepsilon^{2}$), we obtain, for each
$1\leq k<R$,

$|S_{\tilde{\chi}^{k}}(x)|\ll
x\left(\varepsilon^{2}+\mathbb{D}(\tilde{\chi}^{k},n^{it_{k}};x)^{2}e^{-\mathbb{D}(\tilde{\chi}^{k},n^{it_{k}};x)^{2}}\right)\ll
x\left(\varepsilon^{2}+\varepsilon^{-6}\exp\left(-c\varepsilon^{-6}\right)\right)\ll\varepsilon^{2}x.$

It follows that in either of cases (a) and (b),
$|S_{\chi^{k}}(x)|\ll\varepsilon x$ for all $1\leq k\leq R-1$.
Applying this in (5) with $K=R\leq\theta^{-1}$, we get

$M_{\tilde{d},\tilde{\chi}}(x)\leq
x\left(\frac{1}{\tilde{d}}+\frac{1}{R}+O\left(\varepsilon^{2}\log
R\right)\right)\leq
x\left(\frac{1}{R}+O\left(\varepsilon\log(1/\varepsilon)\right)\right).$

Since $j_{0}<\tilde{d}$, we have
$(j_{0},\tilde{d})\leq\tilde{d}/P^{-}(\tilde{d})$, and therefore as
$\varepsilon\gg(\log\log\tilde{d})^{-1/6}$, we obtain

$M_{\tilde{d},\tilde{\chi}}(x)\leq
x\left(\frac{1}{P^{-}(\tilde{d})}+O\left(\frac{\log\log\log\tilde{d}}{(\log\log\tilde{d})^{1/7}}\right)\right).$

Conclusion: Summarising all of the above cases, we obtain, for some
$c\in(0,1/14]$,

$M_{\tilde{d},\tilde{\chi}}(x)\leq
x\left(\frac{1}{P^{-}(\tilde{d})}+O\left(\frac{1}{(\log\log\tilde{d})^{c}}\right)\right),$

as claimed. ∎

###### Proof of Corollary 1.3.

If $z\in(P^{+}(d)-1,P^{+}(d))$ then $d_{z}\geq P^{+}(d)$. Taking $z\rightarrow
P^{+}(d)$ from below, and letting $\delta=\delta_{P^{+}(d)-1/(\log q)}$, we
find that when $x>q^{\delta}$,

$\max_{\alpha^{d}=1}\frac{1}{x}|\\{n\leq
x:\chi(n)=\alpha\\}|\leq\left(\frac{1}{P^{+}(d)}+O\left(\frac{1}{(\log\log
d_{z})^{c_{2}}}\right)\right)\ll\frac{1}{(\log\log P^{+}(d))^{c_{2}}},$

as claimed. ∎

##  6\. Averaged Maximal Character Sums: Proof of Theorem 1.4

Our strategy towards proving Theorem 1.4 will be similar to the proof of
Theorem 1.1. Given $\varepsilon>0$, recall that

$\mathcal{L}_{d}(\varepsilon):=\\{1\leq\ell\leq
d:M(\chi^{\ell})>\varepsilon\sqrt{q}\log q\\}.$

Assuming that $|\mathcal{L}_{d}(\varepsilon)|\geq\varepsilon d$, Proposition
3.2 shows that there are positive integers $m\leq\varepsilon^{-2}$,
$g\leq\varepsilon^{-1}$ and $k\leq e^{-3m}$, and a Dirichlet character
$\xi\pmod{k}$ of order dividing $r=d/g$ such that

$\mathcal{L}_{d}(\varepsilon)\subseteq\\{g\ell:1\leq\ell\leq
r\\}=m\mathcal{L}_{d}(\varepsilon),$

and furthermore

$\max_{1\leq\ell\leq r}\mathbb{D}(\chi^{g\ell},\xi^{\ell};x)^{2}\ll
m^{2}\log(1/\varepsilon).$

Set $\psi:=\chi^{g}\overline{\xi}$, so that $\psi^{r}$ is principal. Write
$\omega=e(1/r)$ and put

$\displaystyle\Sigma_{\psi}(q)=\sum\limits_{1\leq j\leq
r-1}\tilde{\sigma}_{j}(q),\text{ where
}\tilde{\sigma}_{j}(q)=\sum\limits_{\begin{subarray}{c}p\leq q,\\\
\psi(p)=\omega^{j}\end{subarray}}\frac{1}{p}.$

We will study the influence of the sizes of the prime sums
$\tilde{\sigma}_{j}(q)$ on the maximal sums $M(\chi^{\ell})$. Throughout this
section, fix $\eta\in(0,1)$ to be a small parameter.

###  6.1. Small $\tilde{\sigma}_{j}$ case

We assume first of all that
$\tilde{\sigma}_{j}(q)\leq\tfrac{\eta}{g}\Sigma_{\psi}(q)$ for all $1\leq
j\leq r$.

######  Proposition 6.1.

Let $\eta>0$ be sufficiently small, and suppose
$\tilde{\sigma}_{j}(q)\leq\frac{\eta}{g}\Sigma_{\psi}(q)$ for all $1\leq j\leq
r-1$. Then there are elements $1\leq\ell\leq r$ such that

$\displaystyle\mathbb{D}(\chi^{g\ell},\xi^{\ell};q)^{2}\geq\frac{1}{2}\Sigma_{\psi}(q).$

###### Proof.

Since $\psi=\chi^{g}\overline{\xi}$ has order dividing $r$ and

$\mathbb{D}(\chi^{g\ell},\xi^{\ell};q)=\mathbb{D}(\psi^{\ell},1;q)$

for each $1\leq\ell\leq r$, the result follows upon applying Proposition 4.1
to $\psi$ in place of $\chi^{g}$ (as
$\Sigma_{\chi}(x)\geq\Sigma_{\chi^{g}}(x)$ there). ∎

###  6.2. Large $\tilde{\sigma}_{j}$ case

Next, we assume that $\tilde{\sigma}_{j}(q)>\tfrac{\eta}{g}\Sigma_{\psi}(q)$
for some $j=j_{0}$.

######  Proposition 6.2.

Suppose there is $1\leq j_{0}\leq r-1$ such that
$\tilde{\sigma}_{j_{0}}(q)>\frac{\eta}{g}\Sigma_{\psi}(q)$. For each
$1\leq\ell\leq r$ let $1\leq N_{\ell}\leq q$ satisfy

$|L_{\psi^{\ell}}(N_{\ell})|=\max_{1\leq N\leq q}|L_{\psi^{\ell}}(N)|.$

Then for any $1\leq\ell\leq r$,

$\displaystyle\frac{|L_{\psi^{\ell}}(N_{\ell})|}{\log
q}\ll\min\Bigg{\\{}1,\Big{\|}\frac{j_{0}g\ell}{d}\Big{\|}^{-1}\frac{\log
N_{\ell}}{(\log q)\sqrt{\tilde{\sigma}_{j_{0}}(N_{\ell})}}\Bigg{\\}}.$

###### Proof.

For $g\ell\in\mathcal{L}_{d}(\varepsilon)$, by the trivial bound

$\displaystyle\varepsilon\log q\ll|L_{\psi^{\ell}}(N_{\ell})|\leq\log
N_{\ell},$

we have $N_{\ell}\gg q^{\varepsilon}$. We introduce the completely additive
function

$\displaystyle\Omega_{j_{0}}(n)=\sum\limits_{\begin{subarray}{c}p^{k}|n,\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}1.$

By the complete multiplicativity of $\psi$, we have

$\displaystyle\frac{L_{\psi^{\ell}}(N_{\ell})}{\log q}$
$\displaystyle=\frac{1}{\log q}\sum\limits_{n\leq
N_{\ell}}\frac{\psi^{\ell}(n)}{n}\cdot\frac{\Omega_{j_{0}}(n)+\tilde{\sigma}_{j_{0}}(N_{\ell})-\Omega_{j_{0}}(n)}{\tilde{\sigma}_{j_{0}}(N_{\ell})}$
(33) $\displaystyle=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})\log
q}\sum\limits_{\begin{subarray}{c}mp^{k}\leq N_{\ell},\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{\psi^{\ell}(p)^{k}}{p^{k}}\frac{\psi^{\ell}(m)}{m}+O\Bigg{(}\frac{1}{\log
q}\sum\limits_{n\leq
N_{\ell}}\frac{|\Omega_{j_{0}}(n)/\tilde{\sigma}_{j_{0}}(N_{\ell})-1|}{n}\Bigg{)}.$

We first estimate the error term above. By the Cauchy-Schwarz inequality,

(34) $\displaystyle\sum\limits_{n\leq
N_{\ell}}\frac{|\Omega_{j_{0}}(n)/\tilde{\sigma}_{j_{0}}(N_{\ell})-1|}{n}\leq\Bigg{(}\sum\limits_{n\leq
N_{\ell}}\frac{|\Omega_{j_{0}}(n)/\tilde{\sigma}_{j_{0}}(N_{\ell})-1|^{2}}{n}\Bigg{)}^{1/2}\sqrt{\log
N_{\ell}}.$

We will show that

(35) $\displaystyle\sum\limits_{n\leq
N_{\ell}}\frac{|\Omega_{j_{0}}(n)/\tilde{\sigma}_{j_{0}}(N_{\ell})-1|^{2}}{n}=O\left(\frac{\log
N_{\ell}}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\right).$

After expanding the square on the left-hand side, to prove (35) it suffices to
show that for $j=0,1,2$,

$\displaystyle\sum\limits_{n\leq
N_{\ell}}\frac{(\Omega_{j_{0}}(n)/\tilde{\sigma}_{j_{0}}(N_{\ell}))^{j}}{n}=\log
N_{\ell}+O\left(\frac{\log
N_{\ell}}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\right).$

This bound clearly holds when $j=0$. When $j=1$, we have

$\displaystyle\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\sum\limits_{n\leq
N_{\ell}}\frac{\Omega_{j_{0}}(n)}{n}$
$\displaystyle=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\sum\limits_{n\leq
N_{\ell}}\sum\limits_{\begin{subarray}{c}mp^{k}=n,\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{1}{mp^{k}}=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\sum\limits_{\begin{subarray}{c}p^{k}\leq
N_{\ell},\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{1}{p^{k}}\sum\limits_{m\leq
N_{\ell}/p^{k}}\frac{1}{m}$
$\displaystyle=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\sum\limits_{\begin{subarray}{c}p^{k}\leq
N_{\ell},\\\ \psi(p)=\omega^{j_{0}}\end{subarray}}\frac{1}{p^{k}}(\log
N_{\ell}-k\log p+O(1)).$

Using Mertens’ theorem, we find that

$\displaystyle\sum\limits_{\begin{subarray}{c}p^{k}\leq N_{\ell},\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{k\log p}{p^{k}}$
$\displaystyle\leq\log N_{\ell}+\sum\limits_{2\leq k\leq\log
N_{\ell}}k\sum\limits_{2\leq n\leq N_{\ell}^{1/k}}\frac{1}{n^{k-1/2}}$
$\displaystyle\ll\log N_{\ell}+\sum\limits_{2\leq k\leq\log
N_{\ell}}\frac{k}{k-3/2}\ll\log N_{\ell}.$

We also note that

$\sum_{\begin{subarray}{c}p^{k}\leq N_{\ell}\\\ k\geq 2\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{\log
N_{\ell}}{p^{k}}+\sum_{\begin{subarray}{c}p^{k}\leq N_{\ell}\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{1}{p^{k}}\ll\log N_{\ell}.$

Hence, we obtain

$\displaystyle\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\sum\limits_{n\leq
N_{\ell}}\frac{\Omega_{j_{0}}(n)}{n}=\log N_{\ell}+O\left(\frac{\log
N_{\ell}}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\right).$

Finally, when $j=2$,

$\displaystyle\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})^{2}}\sum\limits_{n\leq
N_{\ell}}\frac{\Omega_{j_{0}}(n)^{2}}{n}$
$\displaystyle=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})^{2}}\sum\limits_{n\leq
N_{\ell}}\Bigg{(}\sum\limits_{\begin{subarray}{c}p_{1}^{k_{1}}|n,\\\
\psi(p_{1})=\omega^{j_{0}}\end{subarray}}\frac{1}{n}\Bigg{)}\Bigg{(}\sum\limits_{\begin{subarray}{c}p_{2}^{k_{2}}|n,\\\
\psi(p_{2})=\omega^{j_{0}}\end{subarray}}\frac{1}{n}\Bigg{)}$
$\displaystyle=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})^{2}}\sum\limits_{\begin{subarray}{c}p_{1}^{k_{1}},p_{2}^{k_{2}}\leq
N_{\ell},\\\
\psi(p_{1})=\psi(p_{2})=\omega^{j_{0}}\end{subarray}}\sum\limits_{\begin{subarray}{c}n\leq
N_{\ell},\\\ p_{1}^{k_{1}},p_{2}^{k_{2}}|n\end{subarray}}\frac{1}{n}$
$\displaystyle=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})^{2}}\sum\limits_{\begin{subarray}{c}[p_{1}^{k_{1}},p_{2}^{k_{2}}]\leq
N_{\ell},\\\
\psi(p_{1})=\psi(p_{2})=\omega^{j_{0}}\end{subarray}}\frac{1}{[p_{1}^{k_{1}},p_{2}^{k_{2}}]}\left(\log(N_{\ell}/[p_{1}^{k_{1}},p_{2}^{k_{2}}])+O(1)\right).$

Using Mertens’ theorem, we deduce that

$\displaystyle\sum_{\begin{subarray}{c}[p_{1}^{k_{1}},p_{2}^{k_{2}}]\leq
N_{\ell}\\\
\psi(p_{1})=\psi(p_{2})=\omega^{j_{0}}\end{subarray}}\frac{1}{[p_{1}^{k_{1}},p_{2}^{k_{2}}]}=\sum_{\begin{subarray}{c}[p_{1},p_{2}]\leq
N_{\ell}\\\
\psi(p_{1})=\psi(p_{2})=\omega^{j_{0}}\end{subarray}}\frac{1}{[p_{1},p_{2}]}+O(\tilde{\sigma}_{j_{0}}(N_{\ell}))=\sum_{\begin{subarray}{c}p_{1},p_{2}\leq
N_{\ell}\\\
\psi(p_{1})=\psi(p_{2})=\omega^{j_{0}}\end{subarray}}\frac{1}{[p_{1},p_{2}]}+O(\tilde{\sigma}_{j_{0}}(N_{\ell})),$
$\displaystyle\sum_{\begin{subarray}{c}[p_{1}^{k_{1}},p_{2}^{k_{2}}]\leq
N_{\ell}\\\
\psi(p_{1})=\psi(p_{2})=\omega^{j_{0}}\end{subarray}}\frac{\log[p_{1}^{k_{1}},p_{2}^{k_{2}}]}{[p_{1}^{k_{1}},p_{2}^{k_{2}}]}\ll\left(\sum_{\begin{subarray}{c}p_{1}^{k_{1}}\leq
N_{\ell}\\\
\psi(p_{1})=\omega^{j_{0}}\end{subarray}}\frac{1}{p_{1}^{k_{1}}}\right)\left(\sum_{p_{2}^{k_{2}}\leq
N_{\ell}}\frac{\log
p_{2}^{k_{2}}}{p_{2}^{k_{2}}}\right)\ll\tilde{\sigma}_{j_{0}}(N_{\ell})\log
N_{\ell}.$

Inserting these bounds in the previous estimates, we deduce that

$\displaystyle\frac{1}{(\tilde{\sigma}_{j_{0}}(N_{\ell}))^{2}}\sum\limits_{n\leq
N_{\ell}}\frac{(\Omega_{j_{0}}(n))^{2}}{n}$ $\displaystyle=\frac{\log
N_{\ell}}{(\tilde{\sigma}_{j_{0}}(N_{\ell}))^{2}}\sum\limits_{\begin{subarray}{c}p_{1},p_{2}\leq
N_{\ell},\\\
\psi(p_{1}),\psi(p_{2})=\omega^{j_{0}}\end{subarray}}\frac{1}{[p_{1},p_{2}]}+O\left(\frac{\log
N_{\ell}}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\right)$ $\displaystyle=\frac{\log
N_{\ell}}{(\tilde{\sigma}_{j_{0}}(N_{\ell}))^{2}}\sum\limits_{\begin{subarray}{c}p_{1}\\\
p_{2}\leq N_{\ell},p_{1}\neq p_{2}\\\
\psi(p_{1}),\psi(p_{2})=\omega^{j_{0}}\end{subarray}}\frac{1}{p_{1}p_{2}}+O\left(\frac{\log
N_{\ell}}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\right)$ $\displaystyle=\log
N_{\ell}+O\left(\frac{\log
N_{\ell}}{\tilde{\sigma}_{j_{0}}(N_{\ell})}\right),$

as required.
Combining (35) with (34) and combining the result into (6.2), we find that

$\displaystyle\frac{L_{\psi^{\ell}}(N_{\ell})}{\log q}$
$\displaystyle=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})\log
q}\sum\limits_{\begin{subarray}{c}p^{k}\leq N_{\ell},\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{\psi^{\ell}(p)^{k}}{p^{k}}\sum\limits_{m\leq
N_{\ell}/p^{k}}\frac{\psi^{\ell}(m)}{m}+O\Bigg{(}\frac{\log N_{\ell}}{(\log
q)\sqrt{\tilde{\sigma}_{j_{0}}(N_{\ell})}}\Bigg{)}$
$\displaystyle=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})\log
q}\sum\limits_{\begin{subarray}{c}p^{k}\leq N_{\ell},\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{\omega^{j_{0}k\ell}}{p^{k}}L_{\psi^{\ell}}(N_{\ell}/p^{k})+O\Bigg{(}\frac{\log
N_{\ell}}{(\log q)\sqrt{\tilde{\sigma}_{j_{0}}(N_{\ell})}}\Bigg{)}.$

Since whenever $p^{k}\leq N_{\ell}$ we have

$\displaystyle
L_{\psi^{\ell}}(N_{\ell}/p^{k})=L_{\psi^{\ell}}(N_{\ell})+O\left(\sum_{N_{\ell}/p^{k}<m\leq
N_{\ell}}\frac{1}{m}\right)=L_{\psi^{\ell}}(N_{\ell})+O(k\log p),$

we obtain using Mertens’ theorem again that

$\displaystyle\frac{L_{\psi^{\ell}}(N_{\ell})}{\log q}$
$\displaystyle=\frac{1}{\tilde{\sigma}_{j_{0}}(N_{\ell})\log
q}\sum\limits_{\begin{subarray}{c}p^{k}\leq N_{\ell},\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{\omega^{j_{0}k\ell}}{p^{k}}\Big{(}L_{\psi^{\ell}}(N_{\ell})+O(k\log
p)\Big{)}+O\Bigg{(}\frac{\log N_{\ell}}{(\log
q)\sqrt{\tilde{\sigma}_{j_{0}}(N_{\ell})}}\Bigg{)}$
$\displaystyle=\frac{\omega^{j_{0}\ell}L_{\psi^{\ell}}(N_{\ell})}{\tilde{\sigma}_{j_{0}}(N_{\ell})\log
q}\left(\sum\limits_{\begin{subarray}{c}p\leq N_{\ell},\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{1}{p}\right)+O\left(\frac{\log
N_{\ell}}{(\log q)\sqrt{\tilde{\sigma}_{j_{0}}(N_{\ell})}}\right)$
$\displaystyle=\omega^{j_{0}\ell}\frac{L_{\psi^{\ell}}(N_{\ell})}{\log
q}+O\left(\frac{\log N_{\ell}}{(\log
q)\sqrt{\tilde{\sigma}_{j_{0}}(N_{\ell})}}\right).$

Rearranging this expression and using the bound
$|1-\omega^{j_{0}\ell}|\gg\|j_{0}\ell/r\|$, we deduce that

$\frac{|L_{\psi^{\ell}}(N_{\ell})|}{\log
q}\ll\left\|\frac{j_{0}\ell}{r}\right\|^{-1}\frac{\log N_{\ell}}{(\log
q)\sqrt{\tilde{\sigma}_{j_{0}}(N_{\ell})}},$

as claimed. ∎

In analogy to Proposition 4.3, the number of $\ell$ for which
$\Big{\|}\frac{j_{0}g\ell}{d}\Big{\|}$ can also be estimated effectively.

######  Proposition 6.3.

With the above notation there is an absolute constant $C>0$ such that if

$\theta_{0}:=C\left(\frac{(mg)^{2}\eta^{-1}\log(1/\varepsilon)}{\log\log
r}\right)^{1/2}.$

then at least one of the following is true:

  1. (i)

$|M(\chi)|\leq\varepsilon\sqrt{q}\log q$, and

  2. (ii)

$(j_{0},r)\leq\theta_{0}r$.

Moreover, in the second case we find that for any $\theta\in[\theta_{0},1/2]$,

$\displaystyle|\\{1\leq\ell\leq r:\|j_{0}\ell/r\|\leq\theta\\}|\ll\theta r.$

###### Proof.

Assume (i) fails, so $|M(\chi)|\geq\varepsilon\sqrt{q}\log q$, i.e.,
$1\in\mathcal{L}_{d}(\varepsilon)$. By Proposition 3.2,
$H\cong\mathbb{Z}/d\mathbb{Z}$ implies $g=1$, and

$\displaystyle\mathbb{D}(\psi,1;q)^{2}\ll m^{2}\log(1/\varepsilon)$

where $\psi=\chi\overline{\xi}$. Arguing as in (27), we have

$\displaystyle
m^{2}\log(1/\varepsilon)\gg\eta\Big{\|}\frac{j_{0}}{d}\Big{\|}^{2}\Sigma_{\psi}(q).$

Following the same argument as in the proof of Proposition 4.3, now gives the
claim. ∎

###### Proof of Theorem 1.3.

Let $\varepsilon>0$ be a parameter to be chosen shortly, and suppose
throughout that $|M(\chi)|\geq\varepsilon\sqrt{q}\log q$. Assume for the sake
of contradiction that $\mathcal{L}_{d}(\varepsilon)\geq\varepsilon d$.
By Proposition 3.2, there are integers $1\leq m\leq\varepsilon^{-2}$ and
$1\leq g\leq\varepsilon^{-1}$ and a primitive Dirichlet character
$\xi\pmod{k}$ with $1\leq k\leq\varepsilon^{-3m}$ such that if
$\psi:=\chi^{g}\overline{\xi}$ then

$\displaystyle\max_{1\leq\ell\leq d/g}\mathbb{D}(\psi^{\ell},1;q)^{2}\ll
m^{2}\log(1/\varepsilon).$

We now set $\varepsilon=\Sigma_{\psi}(q)^{-1/8}$. Fix also $\eta\in(0,1)$
small such that $\eta>\varepsilon^{1/6}$, and let $1\leq j_{0}\leq d-1$ be an
index satisfying

$\displaystyle\tilde{\sigma}_{j_{0}}(q)=\max_{1\leq j\leq
d-1}\tilde{\sigma}_{j}(q).$

Set $r:=d/g$ as previously. If
$\sigma_{j_{0}}(q)\leq\frac{\eta}{g}\Sigma_{\psi}(q)$, then by Proposition 5.1
there is $1\leq\ell\leq r$ such that

$\displaystyle\mathbb{D}(\psi^{\ell},1;q)^{2}\geq\frac{1}{2}\Sigma_{\psi}(q).$

Using Proposition 2.5 and $m\leq\varepsilon^{-2}$, we have

$\displaystyle\log\log r\ll\Sigma_{\psi}(q)\ll
m^{2}\log(1/\varepsilon)\leq\varepsilon^{-4}\log(1/\varepsilon).$

Since $\varepsilon=\Sigma_{\psi}(q)^{-1/8}$ we obtain a contradiction as soon
as $d$ is large enough.
Next, suppose $\sigma_{j_{0}}(q)>\frac{\eta}{g}\Sigma_{\psi}(q)$. Let
$\theta\in[\theta_{0},1/2]$ be a parameter that satisfies
$\theta>\varepsilon^{1/6}$. Since $|M(\chi)|\geq\varepsilon\sqrt{q}\log q$, by
Proposition 5.3, we have

$\displaystyle|\\{1\leq\ell\leq d:\|j_{0}\ell/d\|\leq\theta\\}|\leq\theta d.$

By the same argument as in the proof of Theorem 1.2, there must exist
$g\ell\in\mathcal{L}_{d}(\varepsilon)$ such that $\|j_{0}g\ell/d\|>\theta/m$.
Moreover, as noted previously we have $N_{\ell}\gg q^{\varepsilon}$, so by
Mertens’ theorem

$\displaystyle\sigma_{j_{0}}(N_{\ell})=\sigma_{j_{0}}(q)-\sum\limits_{\begin{subarray}{c}N_{\ell}<p\leq
q,\\\
\psi(p)=\omega^{j_{0}}\end{subarray}}\frac{1}{p}\geq\frac{\eta}{g}\Sigma_{\psi}(q)-\log(1/\varepsilon)+O(1)\geq\frac{\eta}{2g}\Sigma_{\psi}(q).$

Thus, as $\theta,\eta>\varepsilon^{1/6},m\leq\varepsilon^{-2}$ and
$g\leq\varepsilon^{-1}$,

$\displaystyle\varepsilon\leq\frac{1}{\log
q}|L_{\psi^{\ell}}(N_{\ell})|\ll\Bigg{(}\frac{m^{2}g}{\theta^{2}\eta\Sigma_{\psi}(q)}\Bigg{)}^{1/2}\ll\frac{1}{\sqrt{\varepsilon^{11/2}\Sigma_{\psi}(q)}}$

Given that $\Sigma_{\psi}(q)=\varepsilon^{-8}$ we again obtain a
contradiction. Therefore, we conclude that
$|\mathcal{L}_{d}(\varepsilon)|\leq\varepsilon d$. Applying Proposition 2.5
together with the lower bound $r\geq\varepsilon d$, we have

$\varepsilon\ll(\log\log r)^{-1/8}\ll(\log\log d)^{-1/8},$

and therefore

$\displaystyle\frac{1}{d}\sum\limits_{1\leq\ell\leq
d}|M(\chi^{\ell})|\ll\Big{(}\varepsilon+\frac{|\mathcal{L}_{d}(\varepsilon)|}{d}\Big{)}\left(\sqrt{q}\log
q\right)\ll\frac{\sqrt{q}\log q}{(\log\log d)^{1/8}}$

as desired. ∎

## References

  * [1] B. Bajnok.  On the maximum size of a (k, l)-sum-free subset of an abelian group.  International Journal of Number Theory, 5(06):953–971, 2009.
  * [2] L. Goldmakher.  Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality.  Algebra Number Theory, 6(1):123–163, 2012.
  * [3] A. Granville and A.P. Mangerel.  Three conjectures about character sums.  Math. Zeit., 305:49:34 pp., 2023.
  * [4] A. Granville and K. Soundararajan.  Decay of mean values of multiplicative functions.  Can. J. Math., 55(6):1191–1230, 2003.
  * [5] A. Granville and K. Soundararajan.  Large character sums: pretentious characters and the Pólya-Vinogradov inequality.  J. Amer. Math. Soc., 20(2):357–384, 2007.
  * [6] R.R. Hall.  Halving an estimate obtained from Selberg’s upper bound sieve.  Acta Arith., 25:347–351, 1974.
  * [7] R.R. Hall and G. Tenenbaum.  Effective mean value estimates for complex multiplicative functions.  Math. Proc. Camb. Philos. Soc., 110:337–351, 1991.
  * [8] Y. o. Hamidoune and A. Plagne.  A new critical pair theorem applied to sum-free sets in abelian groups.  Commentarii Mathematici Helvetici, 79:183–207, 2004.
  * [9] A. Hildebrand.  Quantitative mean value theorems for nonnegative multiplicative functions II.  Acta Arith., 48:209–260, 1987.
  * [10] Y. Lamzouri and A.P. Mangerel.  Large odd order character sums and improvements to the Pólya-Vinogradov inequality.  Trans. Amer. Math. Soc., 375:3759–3793, 2022.
  * [11] A.P. Mangerel.  Gap problems for integer-valued multiplicative functions.  arXiv:2311.11636 [math.NT].
  * [12] A.P. Mangerel.  Large sums of high order characters.  J. Lond. Math. Soc., 109(1), 2024.
  * [13] I.Z. Ruzsa.  On the concentration of additive functions.  Acta Math. Acad. Sci. Hung., 36:215–232, 1980.
  * [14] G. Tenenbaum.  Introduction to Analytic and Probabilistic Number Theory.  Graduate Studies in Mathematics vol. 163, AMS Publications, Providence, RI, 2015.