# Large Sums of High Order Characters

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

Let $\chi$ be a primitive character modulo a prime $q$, and let $\delta>0$. It
has previously been observed that if $\chi$ has large order $d\geq
d_{0}(\delta)$ then $\chi(n)\neq 1$ for some $n\leq q^{\delta}$, in analogy
with Vinogradov’s conjecture on quadratic non-residues. We give a new and
simple proof of this fact. We show, furthermore, that if $d$ is squarefree
then for any $d$th root of unity $\alpha$ the number of $n\leq x$ such that
$\chi(n)=\alpha$ is $o_{d\rightarrow\infty}(x)$ whenever $x>q^{\delta}$.
Consequently, when $\chi$ has sufficiently large order the values
$\\{\chi(n)\\}_{n\leq q^{\delta}}$ cannot cluster near $1$ for any $\delta>0$.

Our proof relies on a non-trivial second moment estimate for short sums of the
characters $\chi^{\ell}$ on average over $1\leq\ell\leq d-1$, provided that
$d$ has no small prime factors, which may be of independent interest. In
particular, given any $\delta>0$ we show that for all but $o(d)$ powers
$1\leq\ell\leq d-1$, the partial sums of $\chi^{\ell}$ exhibit cancellation in
intervals $n\leq q^{\delta}$ as long as $d\geq d_{0}(\delta)$, going beyond
Burgess’ theorem. Our argument blends together results from pretentious number
theory and additive combinatorics.

Finally, we show that, _uniformly_ over prime $3\leq d\leq q-1$, the Pólya-
Vinogradov inequality may be improved for $\chi^{\ell}$ on average over
$1\leq\ell\leq d-1$, extending work of Granville and Soundararajan.

##  1\. Introduction and Main Results

###  1.1. Background

Understanding the value distribution of Dirichlet characters is a central
theme in analytic number theory. An old and famous conjecture of I.M.
Vinogradov predicts that the least quadratic non-residue $n_{p}$ modulo a
prime $p$ satisfies $n_{p}\ll_{\delta}p^{\delta}$ as $p\rightarrow\infty$ for
any $\delta>0$, which is a statement about negative values of the Legendre
symbol $\left(\tfrac{\cdot}{p}\right)$. More generally, one can ask whether
any primitive character $\chi\pmod{q}$ satisfies the property that the least
integer $n_{\chi}$ for which $\chi(n)\neq 0,1$ satisfies
$n_{\chi}\ll_{\delta}q^{\delta}$ as $q\rightarrow\infty$ for any $\delta>0$.
These problems may be recast in terms of cancellation in short character sums.
For the Legendre symbol modulo $p$ it is a folklore conjecture going beyond
Vinogradov’s that

$\left|\sum_{n\leq
x}\left(\frac{n}{p}\right)\right|=o_{p\rightarrow\infty}(x)\text{ whenever
$x>p^{\delta}$ for any $\delta>0$,}$

and more generally for any primitive Dirichlet character $\chi\pmod{q}$ we
expect that

(1) $\left|\sum_{n\leq x}\chi(n)\right|=o_{q\rightarrow\infty}(x)\text{
whenever $x>q^{\delta}$ for any $\delta>0$.}$

Currently, the best general result towards (1), due to Burgess [3], allows for
such cancellation (at least for $q$ cube-free) whenever $\delta>1/4$, improved
to $\delta\geq 1/4$ for prime $q$ by Hildebrand [16].
Both of the above conjectures are well-known to hold (in a much stronger form)
under the assumption of the Generalized Riemann Hypothesis (GRH), but should
even hold assuming far less. Indeed, Granville and Soundararajan [14, Cor.
1.2] showed that (1) holds as long as $L(s,\chi)$ has sufficiently few zeros
in certain small rectangles near the line $\text{Re}(s)=1$, a condition that
is easily implied for _typical_ characters $\chi$ by classical zero density
estimates.
As has been elaborated upon in various works (see e.g., [2], [6], [20] and
[10]), there is also a relationship between such questions about short
character sums and corresponding estimates for _maximal_ character sums, in
particular regarding improvements to the Pólya-Vinogradov inequality, which
asserts that any non-principal character modulo $q$ satisfies

(2) $M(\chi):=\max_{1\leq t\leq q}\left|\sum_{n\leq
t}\chi(n)\right|\ll\sqrt{q}\log q.$

Montgomery and Vaughan [21] showed that, assuming GRH, the factor $\log q$ in
(2) may be improved to $\log\log q$. This is sharp (up to the implicit
constant) for quadratic characters according to a construction due to Paley
[24]. A general, _unconditional_ improvement to the Pólya-Vinogradov
inequality has, however, resisted proof for over a century.
Characters of various fixed orders $d\geq 2$ have been considered in this
connection in a number of works. In [13] and [8], it was shown that, similarly
to Paley’s collection of quadratic characters, collections of characters of
any _fixed even_ order may be constructed for which the Montgomery-Vaughan
estimate is sharp; in contrast, in [13] it was shown that for _fixed odd_
order characters the factor $\log\log q$ may be sharpened (under GRH) to
$(\log\log q)^{1-\delta(d)+o(1)}$, for some $\delta(d)>0$ explicit (see [7]
and [19] for more precise results). On the other hand, unconditional
improvements to (2) for even order characters seem to provide a logjam to
generally improving upon the Pólya-Vinogradov inequality, and thereby also on
improvements to the range in which cancellation may be proved for short sums
as well.

###  1.2. Motivating Questions

A major obstacle in obtaining improvements in the estimation of short and
maximal character sums boils down to the heuristic possibility, currently
difficult to rule out, that a character $\chi$ may take the value $\chi(p)=1$
for a large initial segment of the primes $p\leq q^{\delta}$, which thus also
forces $\chi(n)=1$ significantly often. Thus, even barring actually obtaining
improved bounds in short and maximal sums of $\chi(n)$, it seems relevant to
try to _quantify the frequency with which a character takes the value $1$_ at
integers $n$ up to some small threshold $x$. Note that this question is more
refined than simply trying to bound $n_{\chi}$.
In this paper, we consider such questions for characters $\chi$ of _large_
order (in a sense to be made precise shortly). This is motivated, for example,
by the elementary results in Section 2 below, regarding the variation in
values of $\chi(n)$ for small $n$. Such characters have been considered in
work of, among others, K. K. Norton in relation to small upper bounds for
$n_{\chi}$ (see [22] and especially [23], which contains a substantial survey
on the topic), and Granville and Soundararajan [11] in regards to upper bounds
for $|L(1,\chi)|$. To our knowledge, however, questions surrounding especially
the _paucity_ of solutions to $\chi(n)=1$ and _distribution_ of values
$\chi(n)\neq 1$ for small $n$ have not appeared previously in the literature,
in particular when the order of the character is allowed to grow as a function
of its modulus.

######  Question 1.

If $\chi$ is a primitive character modulo $q$ with order $d=d(q)$ growing with
$q$, and $\delta\in(0,1)$ is fixed, how few solutions $n\leq q^{\delta}$ are
there to $\chi(n)=1$, or more generally to $\chi(n)=\alpha$ when
$\alpha^{d}=1$?

The rationale for this question is the following: if, say, $\chi$ is primitive
modulo a prime $q$ of order $d$ then $\\{\chi(n)\\}_{n<q}$ equidistributes
among the $d$th order roots of unity (by orthogonality of Dirichlet
characters). If $d$ is large then one expects that the level sets

$\\{n\leq x:\chi(n)=\alpha\\},\quad\alpha^{d}=1,$

should become sparse in some range of values of $x$ that are rather smaller
than $q$. Naturally, we would like to understand how quickly this can occur
(i.e. how small can $x$ be for this to happen).
Similarly, we might expect that if $\chi(n)$ can oscillate in value for rather
small values of $n$ then non-trivial bounds for the short and maximal sums of
$\chi$ might be possible as a result. This leads to two further questions.

######  Question 2.

If $\chi$ is a character as in the previous question, can it be shown that for
any fixed $\delta\in(0,1)$,

$\Big{|}\sum_{n\leq x}\chi(n)\Big{|}=o_{d\rightarrow\infty}(x)\text{ for all
}x>q^{\delta}?$

######  Question 3.

For a character $\chi$ as in the previous two questions, can it be shown that
$M(\chi)=o_{d\rightarrow\infty}(\sqrt{q}\log q)$?

###  1.3. Main Results

Our first main result addresses Question 1, provided $q$ is prime and $d$ is
squarefree. See Remarks 2 and 3 below regarding the necessity of these
conditions.
(Unless indicated otherwise, all implicit constants in this paper are
absolute.)

######  Theorem 1.

Let $q$ be a large prime, let $d\geq 2$ be squarefree with $d|(q-1)$ and let
$\chi$ be a primitive character modulo $q$ of order $d$. Then there is an
absolute constant $c_{1}>0$ such that if

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

and $x>q^{\delta}$ then for any111Here and below, we write $\mu_{d}$ to denote
the set of $d$th order roots of unity. $\alpha\in\mu_{d}$,

$|\\{n\leq x:\chi(n)=\alpha\\}|\ll\frac{x}{(\log\log d)^{1/25}}$

Our second main theorem is a mean-square estimate for short sums of order $d$
characters, showing that for _typical_ $1\leq\ell\leq d-1$ the partial sums of
$\chi^{\ell}$ over intervals $[1,q^{\delta}]$ exhibit cancellation for any
fixed $\delta>0$, as long as $d$ has no small prime factors. This shows that
Question 2 has a positive answer for _almost all_ powers $\chi^{\ell}$ of
$\chi$.

######  Theorem 2.

Let $q$ be a large prime, let $d\geq 2$ with $d|(q-1)$ and let $\chi$ be a
primitive character modulo $q$ of order $d$. Define222Here and elsewhere, for
$d\in\mathbb{N}$ we write $P^{-}(d)$ to denote the smallest prime factor of
$d$, and $P^{+}(d)$ to denote the largest prime factor of $d$.

$G=G(d):=\min\\{P^{-}(d),\log\log(ed)\\}.$

Then there is an absolute constant $c_{2}>0$ such that if

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

and $x>q^{\delta}$ then

$\frac{1}{d}\sum_{1\leq\ell\leq d-1}\left|\sum_{n\leq
x}\chi^{\ell}(n)\right|^{2}\ll x^{2}\frac{(\log G)^{2}}{G^{1/11}}.$

Our third main theorem333Though we could have deduced a similar result as a
corollary to Theorem 2, we present in Section 5 a separate argument that gives
the stronger result given here. gives an upper bound for the average size of
$M(\chi^{\ell})$ with $1\leq\ell\leq d-1$ that improves on the Pólya-
Vinogradov inequality for _any_ $d|(q-1)$ having no small prime factors. This
addresses Question 3, again for _almost all_ powers $\chi^{\ell}$ of $\chi$.

######  Theorem 3.

Let $q$ be a large prime, let $d\geq 2$ with $d|(q-1)$ and let $\chi$ be a
primitive character modulo $q$ of order $d$. Then

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

Combined with a (slight extension of a) result of Granville and Soundararajan
[13, Thm. 2], this gives the following bound, which is uniform over all
_prime_ $d$.

######  Corollary 4.

Let $q$ be a large prime. Then, uniformly over all primitive characters $\chi$
modulo $q$ of prime order $d\geq 3$ with $d|(q-1)$,

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

###  1.4. More precise results

With the exception of Theorem 3 on maximal character sums, our main theorems
may be presented in a slightly broader context extending beyond Dirichlet
characters to a larger collection of completely multiplicative functions
taking non-zero values in roots of unity of large order. Considerations of
such a general nature arose also in [11]; see e.g. the discussion surrounding
[11, (1.2)] for the definition of the collection of functions considered
there. For concreteness, we introduce the following definition.

######  Definition 1.

Let $d\in\mathbb{N}$ and $x_{0}\geq 1$. We say that a completely
multiplicative function $f:\mathbb{N}\rightarrow\mu_{d}\cup\\{0\\}$ _weakly
equidistributes beyond (a scale) $x_{0}$_ if444The constant $100$ here could
be replaced by any fixed constant. for any $x\geq x_{0}$,

$\max_{\alpha\in\mu_{d}}|\\{n\leq
x:f(n)=\alpha\\}|\leq\frac{100x}{d}\prod_{\begin{subarray}{c}p\leq x\\\
f(p)=0\end{subarray}}\left(1-\frac{1}{p}\right).$

We define $\mathcal{M}(x_{0};d)$ to be the collection of all such completely
multiplicative functions. For $f\in\mathcal{M}(x_{0};d)$ and $x\geq x_{0}$ we
write

$c_{f}(x):=\prod_{\begin{subarray}{c}p\leq x\\\
f(p)=0\end{subarray}}\left(1-\frac{1}{p}\right),$

and we call $x_{0}$ the _threshold_ of $f$. We define
$\mathcal{M}_{1}(x_{0};d)$ to be the subcollection of those
$f\in\mathcal{M}(x_{0};d)$ for which

(3) $\sum_{\begin{subarray}{c}p:f(p)=0\end{subarray}}\frac{1}{p}\leq 100,$

so that $c_{f}(x)\gg 1$ uniformly in $x$ whenever
$f\in\mathcal{M}_{1}(x_{0};d)$.

Primitive characters modulo primes furnish motivating examples for these
definitions. Indeed, by (2) we have

$\sum_{n\leq x}\chi^{\ell}(n)\ll\sqrt{q}\log q=o(x/d)$

with $x>q^{3/2+\varepsilon}$ _uniformly_ over $1\leq\ell\leq d-1$ and
$d|(q-1)$, and thus by the Weyl criterion we have

$\max_{\alpha\in\mu_{d}}|\\{n\leq x:\chi(n)=\alpha\\}|=(1+o(1))\frac{x}{d}$

whenever $x\geq q^{3/2+\varepsilon}$. This shows that, provided $\theta>3/2$
and $q$ is a large prime we have $\chi\in\mathcal{M}_{1}(q^{\theta};d)$, for
any $d|(q-1)$.
Our first general theorem shows that if $f\in\mathcal{M}_{1}(x_{0};d)$ then
for any fixed $\delta>0$ there are many primes $p\leq x$ for which $f(p)\neq
0,1$ as long as $x>x_{0}^{\delta}$ and $d$ is large enough as a function of
$\delta$. That is, a weakly equidistributed function $f$ cannot be _too_
$1$-pretentious beyond small powers of its threshold (see Section 3.1 for the
appropriate notion of pretentiousness). This result makes no assumptions on
the arithmetic nature of $d$.

######  Theorem 1.1.

Let $x_{0}\geq 3$ be large and let $\eta,\delta\in(0,1)$. Then there are
absolute constants $c_{3}\in(0,1)$ and $C_{1},C_{2},C_{3}>0$ such that the
following is true:

  1. (a)

if $f\in\mathcal{M}_{1}(x_{0};d)$ with555Here and elsewhere,
$\rho:[0,\infty)\rightarrow\mathbb{R}$ denotes the Dickman-de Bruijn function,
i.e. the unique solution to the delay differential equation
$u\rho^{\prime}(u)+\rho(u-1)=0,\quad u>1,$ with initial condition $\rho(u)=1$
for all $u\in[0,1]$. See [26, Sec. III.5.3-III.5.4] for an account of some of
its useful properties.

(4) $C_{1}\rho(\tfrac{C_{2}}{\eta\delta})^{-1}\leq
d\leq\tfrac{C_{3}}{\eta\delta}e^{(\log x_{0})^{c_{3}}}$

then for any $x>x_{0}^{\delta}$,

$\sum_{\begin{subarray}{c}p\leq x\\\ f(p)\neq
0,1\end{subarray}}\frac{1}{p}\geq\log(1/\eta).$

  2. (b)

if $f$ is, in addition, a primitive Dirichlet character modulo a large prime
$q$, $d|(q-1)$ and $\eta\delta\geq(\log q)^{-c}$ for some $0<c<c_{3}$, then
the upper bound constraint in (4) may be removed.

The second general theorem that we prove is a mean-square estimate for short
sums of powers of elements of $\mathcal{M}(x_{0};d)$, showing that for
_typical_ $1\leq\ell\leq d-1$ the short sums of $f^{\ell}$ exhibit
cancellation as long as $f(p)\neq 0,1$ sufficiently often and $d$ has no small
prime factors.

######  Theorem 1.2.

Let $d\geq 2$ and $x_{0}\geq 3$. Let $f\in\mathcal{M}(x_{0};d)$, let $1\leq
x\leq x_{0}$ and set

$\Sigma:=\min\Big{\\{}P^{-}(d),2+\sum_{\begin{subarray}{c}p\leq x\\\ f(p)\neq
0,1\end{subarray}}p^{-1}\Big{\\}}.$

Then

$\frac{1}{d}\sum_{0\leq\ell\leq d-1}\left|\sum_{n\leq
x}f^{\ell}(n)\right|^{2}\ll x^{2}\frac{(\log\Sigma)^{2}}{\Sigma^{1/11}}.$

Combining Theorems 1.1 and 1.2, we will deduce the following corollary in
Section 3, from which Theorem 1 follows.

######  Corollary 1.3.

Let $x_{0}\geq 3$ be large. Let $\eta,\delta\in(0,1)$ and let $d\geq 2$ be
squarefree. Then there are absolute constants $c_{4}\in(0,1)$ and
$C_{4},C_{5}>0$ such that if $\eta\delta>(\log x_{0})^{-c_{4}}$ then the
following holds:
If $\chi$ is a primitive character modulo a prime $q$ with order $d|(q-1)$ and

$d\geq C_{4}\rho(\tfrac{C_{5}}{\eta\delta})^{-1}$

then for any $x>x_{0}^{\delta}$ and $\alpha\in\mu_{d}$,

$|\\{n\leq x:\chi(n)=\alpha\\}|\ll\frac{x}{(\log(1/\eta))^{1/25}}.$

###  1.5. Remarks on the results

######  Remark 1.

Underlying the results above is the commonly-exploited strategy that while
information about _individual_ characters is usually difficult to ascertain,
it is often possible to make progress on average over a _family_ of
characters. When $d$ is a large prime, for instance, the set of powers
$\\{\chi^{\ell}\\}_{1\leq\ell\leq d-1}$ forms a collection of exact degree $d$
characters that, though thin, is large enough that the average behaviour can
be studied. Fortunately, since these are all generated by the same character
$\chi$, as in Theorem 1 we may elucidate some properties of $\chi$ from the
collection of its powers.

######  Remark 2.

The condition that $q$ is prime in our main theorems is mainly a convenience
that ensures that both (3) and the assumption that
$\chi\in\mathcal{M}_{1}(x_{0};d)$ for an appropriate scale $x_{0}$ both hold
in Theorems 1.1 and 1.2. Condition (3) is only used in the proof of Theorem
1.1, and could be removed at the expense of replacing the quantity
$\rho(\tfrac{C_{2}}{\eta\delta})$ appearing in the lower bound for $d$ there,
by $\rho(\tfrac{q}{\phi(q)}\frac{C_{2}}{\eta\delta})$ in the case of a
character, or for general $f\in\mathcal{M}_{1}(x_{0};d)$, by
$\rho(c_{f}(x_{0})\tfrac{C_{2}}{\eta\delta})$. In particular, we can freely
replace the primality of $q$ in the statement of Corollary 1.3 by the
condition that $\sum_{p|q}p^{-1}\leq 100$ (or any other absolute bound, if
desired). Note in this connection that the trivial bound

$\Big{|}\sum_{n\leq x}\chi(n)\Big{|}\leq|\\{n\leq x:(n,q)=1\\}|\ll
x\prod_{p|q}\left(1-\frac{1}{p}\right),$

valid for any $x>q^{\delta}$ and $\delta>0$ fixed, shows that if
$\sum_{p|q}p^{-1}$ is unbounded, in contrast, then we can trivially answer
Question 2 in the affirmative.

######  Remark 3.

The arithmetic condition that $d$ is squarefree in Theorem 1 and Corollary 1.3
is used in order to conclude, simply from a lower bound condition on $d$, that
the group of $d$th order roots of unity does not have too many “small”
subgroups (see the proof of Proposition 3.3 below, which invokes the additive
combinatorial result Corollary 3.5). Indeed, the product of prime factors
$p|d$ that are “small” (in some precise sense) cannot be too large when $d$ is
squarefree. Morally, this prevents the situation in which $\chi$ takes many of
its values among roots of unity of small order from occurring, which might
cause significant repetition of values of $\chi(n)$. More precisely, what we
actually require about $d$ in the proof is that

$\prod_{\begin{subarray}{c}p^{k}||d\\\ p>z\end{subarray}}p^{k},\text{ with
}z\asymp\log(1/\eta),$

is large enough in terms of $\eta,\delta$.

######  Remark 4.

Note that Theorem 3 is only non-trivial when $d$ has no small prime factors,
and is thus odd. While in [13],[7] and [19] it is shown that odd order
characters all have small maximal sums, the corresponding savings of $(\log
q)^{\tfrac{d}{\pi}\sin(\pi/d)-1}$ over (2) there is only non-trivial provided
that $d\ll(\log\log q)^{1/2}$ (besides the fact that, as presented, the
estimates in [13, Thms. 1-2] are not uniform in $d$). The aforementioned
results therefore do not trivialize Theorem 3 in general, given that no
assumptions on the relative sizes of $d$ and $q$ are made here. In any case,
in Section 5 we will combine Theorem 3 with a slight extension of the work of
[13] in order to obtain Corollary 4.
It is worth noting that Theorem 3 is also related to, though not implied by,
[11, Thm. 3], where, for slowly-growing $d$ an upper bound for the _geometric
mean_ of the related quantities

$|L(1,\chi^{\ell})|,\quad 1\leq\ell\leq d,\,(\ell,d)=1$

is obtained that goes beyond the Pólya-Vinogradov bound. The estimate there
does not, however, extend uniformly to the full range of $d$ considered here.

######  Remark 5.

We have made no attempt to optimize any of the exponents in Theorems 1 or 2,
and we do not believe our results to be best possible.

###  1.6. Plan of the paper

The paper is structured as follows.
In Section 2 we give context for our main theorems by providing elementary
proofs of two results, Propositions 2.1 and 2.3, that show how the large order
condition helps in finding small $n$ with $\chi(n)$ (at times significantly)
different from 1 in value.
In Section 3 we deduce Corollary 1.3 and Theorem 1 from Theorems 1.1 and 1.2,
then proceed to prove the latter using ideas from pretentious number theory
and additive combinatorics.
In Section 4 we derive Theorem 1.1 by combining a result of Hildebrand, valid
for a wide collection of multiplicative functions, together with zero-density
estimates in the case of characters. We then deduce Theorem 2 by combining
this with the work of Section 3.
Finally, in Section 5 we prove Theorem 3 and Corollary 4 by combining
(slightly extended) work of Granville and Soundararajan with some
combinatorial observations.
Sections 2 and 5 may be read independently of the remaining sections.

### Acknowledgments

Parts of this work were completed during visits by the author to the
University of Bristol, to the Institut Élie Cartan de Lorraine and to King’s
College London. We would like to warmly thank Bristol, IECL and KCL for their
hospitality and excellent working conditions.
We are most grateful to Andrew Granville, Oleksiy Klurman, Youness Lamzouri
and Aled Walker for helpful discussions, references and encouragement.

##  2\. Elementary Arguments Towards Small $n$ with $\chi(n)\neq 1$

###  2.1. Estimates for $n_{\chi}$

To substantiate our claims that large order characters are somewhat easier to
study than their fixed order counterparts, in this subsection we give an
elementary argument that shows that when $d$ is sufficiently large and $\chi$
is a primitive character of order $d$ modulo a prime $q$ one can find
solutions to $\chi(n)\neq 1$ with $n\leq q^{\delta}$ and $\delta$ much smaller
than $1/4$. This coincides with666Strictly speaking, Norton states his results
as $n_{\chi}\ll q^{\frac{1}{4\alpha_{w}}+\varepsilon}$ for prime $q$, where
$\alpha=\alpha_{w}$ is the unique solution to $\rho(\alpha)=1/w$, under the
condition $d\geq w$. Aside from the factor $1/4$ that arises from his use of
Burgess’ theorem, it is easy to see that the parameter choices in Proposition
2.1 correspond with his. work of Norton (see e.g., [22, Thm. 6.4] or [23, Thm.
1.20]), but we give a different proof that is also short.

######  Proposition 2.1.

Let $\delta>0$ and let $q\geq q_{0}(\delta)$ be prime. If $\chi$ is a
primitive character modulo $q$ of order $d>\rho(1/\delta)^{-1}$ then there is
$1\leq n\leq q^{\delta}$ with $\chi(n)\neq 1$. In particular, $n_{\chi}\ll
q^{\frac{\log\log(Cd\log d)}{\log d}}$ for some $C>0$ absolute.

To prove this we use the following simple combinatorial lemma.

######  Lemma 2.2.

Let $\delta>0$ and let $q\geq q_{0}(\delta)$. Then there is a constant
$c=c(\delta)\in(0,1)$ for which the following holds. If $0\leq d_{1}\leq
d_{2}\leq cq$ are such that $n^{d_{2}}\equiv n^{d_{1}}\pmod{q}$ for all $1\leq
n\leq q^{\delta}$ then $d_{1}=d_{2}$. In fact, we may take any
$0<c<\rho(1/\delta)$.

###### Proof.

Assume the contrary, so that $d:=d_{2}-d_{1}>0$. By assumption, we have
$t^{d}\equiv 1\pmod{q}$ for all $1\leq t\leq q^{\delta}$, and in particular
for all primes $p\in[1,q^{\delta}]$ this congruence holds. But then we
additionally have $(t_{1}t_{2})^{d}\equiv 1\pmod{q}$ whenever $t_{j}^{d}\equiv
1\pmod{q}$ for $j=1,2$, and thus all $q^{\delta}$-friable integers $1\leq
t\leq q-1$ also satisfy this congruence. But for large enough $q$ there are
$(\rho(1/\delta)+o(1))q$ such integers up to $q$ [26, Thm. III.5.8]. Thus, if
$0<c<\rho(1/\delta)$ and $q$ is large enough then we find that there are
$>cq\geq d$ solutions to the polynomial equation $X^{d}\equiv 1\pmod{q}$,
which is a contradiction since $d\neq 0$. ∎

###### Proof of Proposition 2.1.

Write $\chi=\chi_{q}^{\ell\tfrac{q-1}{d}}$, where $\chi_{q}$ generates the
character group modulo $q$ and $(\ell,d)=1$. Setting
$\chi_{1}:=\chi_{q}^{(q-1)/d}$, note that $\chi_{1}$ takes values in roots of
unity of order $d$, and so if we can show that $\chi_{1}(n)\neq 1$ for some
$n\leq q^{\delta}$ then the same is true for $\chi=\chi_{1}^{\ell}$.
Note that $1\leq\frac{q-1}{d}\leq cq$ for some $0<c<\rho(1/\delta)$. Now
assume for the sake of contradiction that $\chi_{1}(n)=1$ for all $1\leq n\leq
q^{\delta}$. Since $\chi_{q}$ is injective on $\mathbb{Z}/q\mathbb{Z}$ it
follows that $n^{\tfrac{q-1}{d}}\equiv 1\pmod{q}$ for all $1\leq n\leq
q^{\delta}$. By the previous lemma we deduce that $(q-1)/d=0$, which is a
contradiction. This establishes the first claim.
If $\delta$ is small enough then, using

(5) $\rho(u)\gg\left(\frac{e}{2u\log u}\right)^{u}$

with $u=1/\delta$ (see [9, Sec. 3.9]), we deduce that if

$\delta\log d>\log\log d+\log\log\log d+O(1)$

then $d>\rho(1/\delta)^{-1}$ and we may apply the first claim. The choice
$\delta:=\frac{\log\log(Cd\log d)}{\log d}$ with $C>0$ absolute and
sufficiently large, furnishes the second claim. ∎

###  2.2. Small $n$ with $\chi(n)$ bounded away from $1$

It is reasonable to expect that, for $n$ only slightly larger than $n_{\chi}$
we might have $\chi(n)\neq 1$ but still only with $\chi(n)$ _very close to_
$1$. That is, $\chi(n)=e(j/d)$ where777Given $t\in\mathbb{R}$ we write
$e(t):=e^{2\pi it}$ and $\|t\|:=\min_{n\in\mathbb{Z}}|t-n|$. $\|j/d\|$ is
quite small. By an elementary argument, however, we can also show that this is
not necessarily always the case. In the sequel, for $z\in S^{1}$ we write
$\text{arg}(z)$ to denote the element of $(-1/2,1/2]$ for which
$z=e(\text{arg}(z))$.

######  Proposition 2.3.

Let $q$ be a large prime, let $d\geq 2$ and let $\chi$ be a primitive
character modulo $q$ of order $d$. Let $\delta\in(0,1/2)$ with

$1/\delta=o\Big{(}\frac{\log\log q}{\log\log\log q}\Big{)}$

as $q\rightarrow\infty$, and suppose that $d>\rho(1/\delta)^{-1}$. Then for
any $c>1$,

$\exists\,n\leq q^{\delta}\text{ with
}|\text{arg}(\chi(n))|\geq\max\Big{\\{}\tfrac{1}{d},\rho(1/\delta)^{c}\Big{\\}}.$

######  Remark 6.

For $c>1$ fixed set $M:=\rho(1/\delta)^{-c}$. If $M>d$ then the above result
gives no further information than what is provided by Proposition 2.1, since
if $\chi(n)\neq 0,1$ then $|\text{arg}(\chi(n))|\geq 1/d$. The proposition is
interesting, however, when $d$ is significantly larger than $M$.

The proof depends on the following results. The first is due to Friedlander
[5, Thm. 1(B), Thm. 6(B)].

######  Theorem (Friedlander).

There is a continuous function $\sigma$ defined on
$\\{(u,v)\in(1,\infty)^{2}:v>u\\}$ such that the following holds. For any
fixed $\alpha>1$ there is $u_{0}=u_{0}(\alpha)>2$ such that if $u\geq u_{0}$
and $X$ is large enough then

$|\\{n\leq X:P^{-}(n)>X^{1/(\alpha u)},\,P^{+}(n)\leq
X^{1/u}\\}|=\left(\sigma(u,\alpha
u)+O\left(\frac{1}{\log(X^{1/(u\alpha)})}\right)\right)\frac{X}{\log(X^{1/(u\alpha)})}.$

Moreover, under these conditions there is a $c_{0}=c_{0}(\alpha)\geq 1$ such
that $\sigma$ satisfies

(6) $\sigma(u,\alpha u)\geq\rho(1/u)c_{0}^{-u}.$

######  Corollary 2.4.

Let $q$ and $\delta$ be as in the statement of Proposition 2.3. Then there is
an absolute constant $c_{0}\geq 1$ such that

$|\\{n=mk<q:\,m\leq q^{\delta/10}\text{ and }p|k\Rightarrow
q^{\delta/10}<p\leq q^{\delta}\\}|\gg\rho(1/\delta)c_{0}^{-1/\delta}q.$

###### Proof.

Call $\mathcal{S}_{\delta}$ the set of $n=mk$ as above. Note that if
$n\in\mathcal{S}_{\delta}$ then its representation $n=mk$ is uniquely
determined. Now, for each $m\leq q^{\delta/10}$ define $u_{m}$ to be the
unique solution to $(q/m)^{1/u_{m}}=q^{\delta}$; explicitly,
$u_{m}=\delta^{-1}\Big{(}1-\frac{\log m}{\log q}\Big{)}$ for each such $m$. As

$\sigma(u_{m},10u_{m})\geq\rho(1/u_{m})c_{0}^{-1/u_{m}}\gg\frac{1}{\log(q^{1/(10u_{m})})}$

with $c_{0}=c_{0}(10)$ and a large implicit constant by (6), (5) and our
hypothesis on $\delta$, taking $\alpha=10$ in Friedlander’s theorem yields

$|\mathcal{S}_{\delta}|\geq\sum_{m\leq
q^{\delta/10}}\sum_{\begin{subarray}{c}k<q/m\\\ q^{\delta/10}<P^{-}(k)\leq
P^{+}(k)\leq q^{\delta}\end{subarray}}1\gg\frac{q}{\delta\log q}\sum_{m\leq
q^{\delta/10}}\frac{\sigma(u_{m},10u_{m})}{m}\geq\frac{q}{\delta\log
q}\sum_{m\leq q^{\delta/10}}\frac{\rho(u_{m})c_{0}^{-u_{m}}}{m}.$

Since $u_{m}\leq\delta^{-1}$ uniformly over $m\leq q^{\delta/10}$, $c_{0}\geq
1$ and $\rho$ is decreasing, we obtain

$|\mathcal{S}_{\delta}|\gg\frac{q\rho(1/\delta)c_{0}^{-1/\delta}}{\delta\log
q}\sum_{m\leq q^{\delta/10}}\frac{1}{m}\gg q\rho(1/\delta)c_{0}^{-1/\delta},$

as claimed. ∎

######  Lemma 2.5.

Let $I\subseteq[0,1]$ be an open interval with length $|I|$. If $\chi$ is a
primitive character modulo prime $q$ of order $d$ then for any $K\geq 1$,

$|\\{n<q:\text{arg}(\chi(n))\in
I\\}|=q\left(|I|+O\left(\frac{1}{K}+\frac{\log(1+\left\lfloor
K/d\right\rfloor)}{d}\right)\right).$

###### Proof.

We apply the Erdős-Turán inequality [26, Thm. I.6.15]. Given $K\geq 1$,

$|\,|\\{n<q:\text{arg}(\chi(n))\in I\\}|-q|I|\,|\ll\frac{q}{K}+\sum_{1\leq
k\leq K}\frac{1}{k}\left|\sum_{n\leq q}\chi(n)^{k}\right|.$

If $d|k$ then $\chi(n)^{k}$ is principal and the inner sum is $q-1$.
Otherwise, if $d\nmid k$ then $\chi^{k}$ is non-principal and the sum is zero
by orthogonality. This yields the upper bound

$\ll\frac{q}{K}+q\sum_{1\leq k\leq K}\frac{1_{d|k}}{k}\ll
q\left(\frac{1}{K}+\frac{\log(1+\left\lfloor K/d\right\rfloor)}{d}\right),$

and implies the claim. ∎

###### Proof of Proposition 2.3.

If $M>d$ then the result follows from Proposition 2.1. Thus, in the sequel we
need only consider $M\leq d$. Suppose for the sake of contradiction that
$|\text{arg}(\chi(n))|\leq\frac{1}{M}$ for all $n\leq q^{\delta}$. It follows
that whenever $n=mk<q$, where $m\leq q^{\delta/10}$ and $p|k\Rightarrow
q^{\delta/10}<p\leq q^{\delta}$ then we have

$|\text{arg}(\chi(mk))|\leq|\text{arg}(\chi(m))|+\sum_{p|k}|\text{arg}(\chi(p))|\leq\frac{1}{M}+\frac{10}{\delta}\max_{\begin{subarray}{c}p|k\\\
p\leq q^{\delta}\end{subarray}}|\text{arg}(\chi(q))|\leq\frac{11}{M\delta}.$

Since $M\leq d$, applying Lemma 2.5 with $K=\left\lfloor M\right\rfloor-1<d$
gives

$|\mathcal{S}_{\delta}|=|\\{n=mk<q:m\leq q^{\delta/10},\,p|k\Rightarrow
q^{\delta/10}<p\leq
q\\}|\leq|\\{n<q:|\text{arg}(\chi(n))|\leq\tfrac{11}{M\delta}\\}|\ll\frac{q}{M\delta}.$

On the other hand, Corollary 2.4 directly implies that

$|\mathcal{S}_{\delta}|\gg q\rho(1/\delta)c_{0}^{-1/\delta}.$

It follows that if $\delta$ is sufficiently small, and $C>0$ is chosen large
enough then upon picking
$M:=\min\\{d,C(\delta\rho(1/\delta))^{-1}c_{0}^{1/\delta}\\}$ we obtain a
contradiction. Thus, we must have some $n\leq q^{\delta}$ with
$|\text{arg}(\chi(n))|>1/M$. Since for any $c>1$ and small enough $\delta$ we
immediately have $\rho(1/\delta)^{c}\ll\delta\rho(1/\delta)c_{0}^{-1/\delta}$,
the claimed bound follows. ∎

##  3\. Short Sums of Powers on Average

###  3.1. A Pretentious Primer

The arguments used towards the proof of our main theorems are grounded in
notions of pretentious number theory, as developed by Granville and
Soundararajan. Here, we give a brief overview of those ideas from that subject
that will be relevant in this paper.
Let $\mathbb{U}:=\\{z\in\mathbb{C}:|z|\leq 1\\}$. Given arithmetic functions
$f,g:\mathbb{N}\rightarrow\mathbb{U}$ and $x\geq 2$ we define the pretentious
distance

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

Note that $\mathbb{D}(f,g;x)=\mathbb{D}(f\overline{g},1;x)$, and by Mertens’
theorem, $0\leq\mathbb{D}(f,g;x)^{2}\leq 2\log\log x$. This distance function
also satisfies a triangle inequality: given $f,g,h$ arithmetic functions
taking values in $\mathbb{U}$, we have

(7) $\mathbb{D}(f,h;x)\leq\mathbb{D}(f,g;x)+\mathbb{D}(g,h;x),$

which implies the useful inequality (see [13, Lem. 3.1])

(8)
$\mathbb{D}(f_{1}f_{2},g_{1}g_{2};x)=\mathbb{D}(f_{1}\overline{g}_{1},f_{2}\overline{g}_{2};x)\leq\mathbb{D}(f_{1}\overline{g}_{1},1;x)+\mathbb{D}(f_{2}\overline{g}_{2},1;x)=\mathbb{D}(f_{1},g_{1};x)+\mathbb{D}(f_{2},g_{2};x).$

If $f$ and $g$ are multiplicative functions for which
$\mathbb{D}(f,g;x)^{2}=o(\log\log x)$ then $f(p)\overline{g}(p)\approx 1$ in a
suitable average sense, and we think of $f$ and $g$ as approximating one
another. We say in this situation that $f$ is _$g$ -pretentious_ (or
symmetrically, $g$ is _$f$ -pretentious_).
Our key interest in $\mathbb{D}$ lies in the fact that it can be used to
express upper bounds for Césaro averages of bounded multiplicative functions.
In this direction, the Halász-Montgomery-Tenenbaum inequality [26, Cor.
III.4.12], a quantitative refinement of fundamental work of Halász, states
that for a multiplicative function $f:\mathbb{N}\rightarrow\mathbb{U}$ and
parameters $x\geq 3$ and $T\geq 1$,

(9) $\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},$

where $M:=\min_{|t|\leq T}\mathbb{D}(f,n^{it};x)^{2}$. Thus, if $f$ is not
$n^{it}$-pretentious for all $|t|\leq T$, and $T$ is large enough, then the
partial sums of $f$ are small. This result will be used several times in the
sequel.

###  3.2. Deduction of Corollary 1.3 and Theorem 1

Given a multiplicative function $f:\mathbb{N}\rightarrow S^{1}\cup\\{0\\}$ and
$\alpha\in S^{1}$ define the level set

$\mathcal{A}_{\alpha}(x;f):=\\{n\leq x:f(n)=\alpha\\}.$

######  Corollary 3.1.

Assume the hypotheses and notation of Theorem 1.2. Let
$\\{\alpha_{j}\\}_{1\leq j\leq d}$ be an ordering of $\mu_{d}$ so that
$\max_{\alpha\in\mu_{d}}|\mathcal{A}_{\alpha}(x;f)|=|A_{\alpha_{1}}(x;f)|$ and
for each $j\geq 2$,

$|\mathcal{A}_{\alpha_{j}}(x;f)|=\max_{\begin{subarray}{c}\alpha\in\mu_{d}\\\
\alpha\notin\\{\alpha_{1},\ldots,\alpha_{j-1}\\}\end{subarray}}|\mathcal{A}_{\alpha}(x;f)|.$

Then for any $J\geq 1$,

$|\mathcal{A}_{\alpha_{J}}(x;f)|\ll\frac{x}{\sqrt{J}}\frac{\log\Sigma}{\Sigma^{1/22}}.$

In particular,

$\max_{\alpha\in\mu_{d}}|\\{n\leq x:f(n)=\alpha\\}|\ll
x\frac{\log\Sigma}{\Sigma^{1/22}}.$

###### Proof of Corollary 3.1 assuming Theorem 1.2.

The second claim follows from the first with $J=1$ so it suffices to prove the
first.
By orthogonality of additive characters modulo $d$,

$\frac{1}{d}\sum_{0\leq\ell\leq d-1}\left|\sum_{n\leq
x}f^{\ell}(n)\right|^{2}=\sum_{n,m\leq x}\frac{1}{d}\sum_{0\leq\ell\leq
d-1}(f(n)\overline{f}(m))^{\ell}=|\\{n,m\leq x:f(n)=f(m)\neq 0\\}|.$

Next, we note that by positivity,

$\displaystyle|\mathcal{A}_{\alpha_{J}}(x;f)|^{2}$
$\displaystyle\leq\frac{1}{J}\sum_{1\leq j\leq
J}|\mathcal{A}_{\alpha_{j}}(x;f)|^{2}=\frac{1}{J}\sum_{\begin{subarray}{c}n,m\leq
x\\\ f(n)=f(m)\\\ f(n)\in\\{\alpha_{1},\ldots,\alpha_{J}\\}\end{subarray}}1$
$\displaystyle\leq\frac{1}{J}|\\{n,m\leq x:f(n)=f(m)\neq 0\\}|.$

Combining this with the previous equation and applying Theorem 1.2, we obtain

$|\mathcal{A}_{\alpha_{J}}(x;f)|\ll\frac{1}{\sqrt{J}}\left(\frac{1}{d}\sum_{0\leq\ell\leq
d-1}\left|\sum_{n\leq
x}f^{\ell}(n)\right|^{2}\right)^{1/2}\ll\frac{x}{\sqrt{J}}\frac{\log\Sigma}{\Sigma^{1/22}},$

as claimed. ∎

###### Proof of Corollary 1.3 assuming Theorems 1.1 and 1.2.

We may assume that $\eta\in(0,1)$ is smaller than any fixed constant, since
otherwise the claim is trivial. Set now $z:=\log(1/\eta)$ and factor
$d=\mathfrak{d}\mathfrak{D}$, where

$\mathfrak{d}:=\prod_{\begin{subarray}{c}p^{k}||d\\\ p\leq
z\end{subarray}}p^{k},\quad\mathfrak{D}:=\prod_{\begin{subarray}{c}p^{k}||d\\\
p>z\end{subarray}}p^{k}.$

Define $\psi:=\chi^{\mathfrak{d}}$. Then $\psi$ has order $\mathfrak{D}$,
which satisfies $P^{-}(\mathfrak{D})>z$. Since $d$ is squarefree, by the prime
number theorem we have $\mathfrak{d}\leq e^{(1+o(1))z}\leq\eta^{-2}$, and so
by assumption,

$\mathfrak{D}=d/\mathfrak{d}\geq
C_{4}\eta^{2}\rho\left(\frac{C_{5}}{\eta\delta}\right).$

Increasing $C_{4},C_{5}$ if needed, we have $\mathfrak{D}\geq
C_{1}\rho\left(\frac{C_{2}}{\eta\delta^{\prime}}\right)$, where $C_{1},C_{2}$
are as in Theorem 1.1, and $\delta^{\prime}:=2\delta/3$. Since
$\chi\in\mathcal{M}_{1}(q^{\theta};d)$ for $\theta>3/2$ for prime $q$ and
taking any $0<c_{4}<c_{3}$, that theorem thus implies that

$\Sigma=\min\Big{\\{}P^{-}(\mathfrak{D}),2+\sum_{\begin{subarray}{c}p\leq x\\\
\psi(p)\neq 0,1\end{subarray}}p^{-1}\Big{\\}}\geq\log(1/\eta)$

whenever $x>q^{\delta}$. By Corollary 3.1, if $\eta$ is sufficiently small
then

$\max_{\alpha^{\mathfrak{D}}=1}|\mathcal{A}_{\alpha}(x;\psi)|\ll
x\frac{\log\Sigma}{\Sigma^{1/22}}\ll\frac{x}{(\log(1/\eta))^{1/25}}.$

Since $\psi(n)=e(j/\mathfrak{D})$ whenever $\chi(n)=e(j/d)$, we deduce that

$\max_{\beta^{d}=1}|\mathcal{A}_{\beta}(x;\chi)|\leq\max_{\alpha^{\mathfrak{D}}=1}\sum_{\begin{subarray}{c}\beta^{d}=1:\\\
\beta^{\mathfrak{d}}=\alpha\end{subarray}}|\mathcal{A}_{\beta}(x;\chi)|=\max_{\alpha^{\mathfrak{D}}=1}|\mathcal{A}_{\alpha}(x;\psi)|\ll\frac{x}{(\log(1/\eta))^{1/25}},$

as claimed. ∎

###### Proof of Theorem 1 assuming Theorems 1.1 and 1.2.

Set $\eta=\delta$ and take $0<c_{1}\leq c_{4}/2$ small, so that
$\eta\delta\geq(\log q)^{-c_{4}}$ whenever $\delta\geq(\log q)^{-c_{1}}$. As

$\frac{1}{\delta^{2}}\ll c_{1}^{2}\frac{\log d}{\log\log(ed)},$

from (5) we have the required lower bound $d\geq
C_{4}\rho(\tfrac{C_{5}}{\eta\delta})^{-1}$, with $C_{4},C_{5}$ as given in the
statement of Corollary 1.3, whenever $c_{1}>0$ is chosen small enough.
Moreover, since $q>d$ it follows that

$\log(1/\eta)=\frac{1}{2}\min\Big{\\{}c_{1}\log\log q,\log\log
d-\log\log\log(ed)+O(1)\Big{\\}}\gg\log\log d.$

Corollary 1.3 thus implies the claim as long as $x>q^{\delta}$, as required. ∎

###  3.3. Proof of Theorem 1.2

Let $d\geq 2$, $x_{0}\geq 3$ and $f\in\mathcal{M}(x_{0};d)$. Let also $1\leq
x\leq x_{0}$. In this subsection we prove Theorem 1.2 by showing that for
_almost all_ $1\leq\ell\leq d-1$ the partial sums of $f^{\ell}$ up to $x$ are
small.
The proof of Theorem 1.2 relies on some understanding of the relative sizes of
the prime sums

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

There are two cases to consider:

  1. (1)

there is an index $1\leq m\leq d-1$ such that $\sigma_{m}$ contributes an
outsized amount to $\sum_{1\leq j\leq d-1}\sigma_{j}$;

  2. (2)

$\sigma_{m}$ is small for each $1\leq m\leq d-1$.

We would expect only the second of these cases to occur if the non-zero values
of $\\{f(p)\\}_{p\leq x}$ are (weakly) equidistributed in $\mu_{d}$, but are
not able to rule out either of them. We begin by treating the second case.
In the following lemma, we obtain lower bounds on the distances
$\mathbb{D}(f^{\ell},1;x)^{2}$, for almost all $1\leq\ell\leq d-1$. While this
is not enough to obtain the required cancellation in almost all partial sums
via (9) due to possible twists $n^{it_{\ell}}$, in Proposition 3.3 below we
will show that any minimizing $t_{\ell}$ are of effectively negligible size
if, conversely, many of the partial sums are assumed to be large.

######  Lemma 3.2.

Let $\varepsilon\in(0,1)$ be small and satisfy $\varepsilon P^{-}(d)>1$, and
assume that $\sigma_{m}<\varepsilon\sum_{1\leq j\leq d-1}\sigma_{j}$ for all
$1\leq m\leq d-1$. Then for all but $O(\varepsilon^{1/3}d)$ choices of
$1\leq\ell\leq d-1$ we have

$\mathbb{D}(f^{\ell},1;x)^{2}\geq\left(\frac{2}{3}+O(\varepsilon^{1/3})\right)\sum_{1\leq
j\leq d-1}\sigma_{j}.$

###### Proof.

Given $t\in\mathbb{R}$, observe first of all the inequality

$1-\cos(2\pi t)=2\sin^{2}(\pi\|t\|)\geq 8\|t\|^{2}.$

It follows that for any $\ell\neq 0$,

(10) $\mathbb{D}(f^{\ell},1;x)^{2}\geq\sum_{\begin{subarray}{c}p\leq x\\\
f(p)\neq 0,1\end{subarray}}\frac{1-\text{Re}(f^{\ell}(p))}{p}=\sum_{1\leq
j\leq d-1}(1-\cos(2\pi j\ell/d))\sum_{\begin{subarray}{c}p\leq x\\\
f(p)=e(j/d)\end{subarray}}\frac{1}{p}\geq 8\sum_{1\leq j\leq
d-1}\Big{\|}\frac{\ell j}{d}\Big{\|}^{2}\sigma_{j}.$

We now seek upper bounds for the variance

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

noting that here, $\tfrac{1}{12}=\int_{0}^{1}\|t\|^{2}dt$. The 1-periodic
function $t\mapsto\|t\|^{2}$ has the absolutely convergent Fourier series

$\|t\|^{2}=\frac{1}{12}+\frac{1}{2\pi^{2}}\sum_{r\neq
0}\frac{(-1)^{r}}{r^{2}}e(rt).$

Thus, expanding the square in $\Delta$ and inputting this expression yields

$\displaystyle\Delta$ $\displaystyle=\sum_{1\leq j_{1},j_{2}\leq
d-1}\sigma_{j_{1}}\sigma_{j_{2}}\frac{1}{d}\sum_{1\leq\ell\leq
d}\left(\Big{\|}\frac{\ell
j_{1}}{d}\Big{\|}^{2}-\frac{1}{12}\right)\left(\Big{\|}\frac{\ell
j_{2}}{d}\Big{\|}^{2}-\frac{1}{12}\right)$
$\displaystyle=\frac{1}{4\pi^{4}}\sum_{r_{1},r_{2}\neq
0}\frac{(-1)^{r_{1}+r_{2}}}{(r_{1}r_{2})^{2}}\sum_{1\leq j_{1},j_{2}\leq
d-1}\sigma_{j_{1}}\sigma_{j_{2}}\frac{1}{d}\sum_{1\leq\ell\leq
d}e\left(\frac{\ell}{d}(j_{1}r_{1}-j_{2}r_{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}r_{1},r_{2}\neq 0\\\
j_{1}r_{1}\equiv
j_{2}r_{2}\pmod{d}\end{subarray}}\frac{(-1)^{r_{1}+r_{2}}}{(r_{1}r_{2})^{2}}.$

Note first of all that in the inner double sum, if
$m=\max\\{(r_{1},d),(r_{2},d)\\}>1$ then $m\geq P^{-}(d)$, and thus also
$\max\\{|r_{1}|,|r_{2}|\\}\geq P^{-}(d)$. Since $(r_{1}r_{2},d)>1$ if and only
if $\max\\{(r_{1},d),(r_{2},d)\\}>1$, the contribution to $\Delta$ from
$r_{1},r_{2}\neq 0$ with $(r_{1}r_{2},d)>1$ is thus

$\ll\sum_{1\leq j_{1},j_{2}\leq
d-1}\sigma_{j_{1}}\sigma_{j_{2}}\sum_{\begin{subarray}{c}r_{1},r_{2}\neq 0\\\
\max\\{|r_{1}|,|r_{2}|\\}\geq
P^{-}(d)\end{subarray}}\frac{1}{(r_{1}r_{2})^{2}}\ll\frac{1}{P^{-}(d)}\left(\sum_{1\leq
j\leq d-1}\sigma_{j}\right)^{2}.$

We may henceforth restrict to $(r_{1}r_{2},d)=1$ in what follows.
Fix now $1\leq j_{1},j_{2}\leq d-1$ for the moment and let
$\lambda:=(j_{1},j_{2})$. Since $\lambda<d$ and $\lambda|d$ we have
$d/\lambda\geq P^{-}(d)$. Setting $J_{i}:=j_{i}/\lambda$, $i=1,2$, we see that
$j_{1}r_{1}\equiv j_{2}r_{2}\pmod{d}$ is equivalent to $J_{1}r_{1}\equiv
J_{2}r_{2}\pmod{d/\lambda}$. Since, moreover, $(J_{1},J_{2})=1$ and
$(r_{1}r_{2},d)=1$, we deduce that $(J_{1}J_{2},d/\lambda)=1$ also. Separating
the contribution of $\max\\{|r_{1}|,|r_{2}|\\}\geq d/\lambda$ from the
remainder, we find

$\displaystyle\Delta$
$\displaystyle=\frac{1}{4\pi^{4}}\sum_{\begin{subarray}{c}\lambda|d\\\
\lambda<d\end{subarray}}\sum_{\begin{subarray}{c}1\leq J_{1},J_{2}\leq
d/\lambda\\\ (J_{1},J_{2})=1\\\
(J_{1}J_{2},d/\lambda)=1\end{subarray}}\sigma_{\lambda J_{1}}\sigma_{\lambda
J_{2}}\left(\sum_{\begin{subarray}{c}1\leq|r_{1}|,|r_{2}|<d/\lambda\\\
(r_{1}r_{2},d)=1\\\ J_{1}r_{1}\equiv
J_{2}r_{2}\pmod{d/\lambda}\end{subarray}}\frac{(-1)^{r_{1}+r_{2}}}{(r_{1}r_{2})^{2}}+O\left(\frac{\lambda}{d}\right)\right)+O\left(\frac{1}{P^{-}(d)}\left(\sum_{1\leq
j\leq d-1}\sigma_{j}\right)^{2}\right)$ (11)
$\displaystyle=\frac{1}{4\pi^{4}}\sum_{\begin{subarray}{c}\lambda|d\\\
\lambda<d\end{subarray}}\sum_{\begin{subarray}{c}1\leq|r_{1}|,|r_{2}|<d/\lambda\\\
(r_{1}r_{2},d)=1\end{subarray}}\frac{(-1)^{r_{1}+r_{2}}}{(r_{1}r_{2})^{2}}\sum_{\begin{subarray}{c}1\leq
J_{1},J_{2}\leq d/\lambda\\\ (J_{1},J_{2})=1\\\ (J_{1}J_{2},d/\lambda)=1\\\
J_{1}r_{1}\equiv J_{2}r_{2}\pmod{d/\lambda}\end{subarray}}\sigma_{\lambda
J_{1}}\sigma_{\lambda J_{2}}+O\left(\frac{1}{P^{-}(d)}\left(\sum_{1\leq j\leq
d-1}\sigma_{j}\right)^{2}\right).$

Note that, fixing $1\leq|r_{1}|,|r_{2}|,J_{1}<d/\lambda$, any possible choice
of $J_{2}$ is unique and fixed by the congruence in the inner sum; calling it
$J_{2}(J_{1},r_{1},r_{2})$, say, we see by hypothesis that

$\sigma_{\lambda J_{2}(J_{1},r_{1},r_{2})}\ll\varepsilon\sum_{1\leq j\leq
d-1}\sigma_{j},$

and therefore the first expression in (11) is

$\ll\varepsilon\left(\sum_{1\leq j\leq
d-1}\sigma_{j}\right)\left(\sum_{\begin{subarray}{c}1\leq|r_{1}|,|r_{2}|<d\\\
(r_{1}r_{2},d)=1\end{subarray}}\frac{1}{(r_{1}r_{2})^{2}}\right)\sum_{\begin{subarray}{c}\lambda|d\\\
\lambda<d\end{subarray}}\sum_{\begin{subarray}{c}1\leq J\leq d/\lambda\\\
(J,d/\lambda)=1\end{subarray}}\sigma_{\lambda
J}\ll\varepsilon\left(\sum_{1\leq j\leq d-1}\sigma_{j}\right)^{2}.$

It follows, therefore, that

$\Delta\ll\left(\sum_{1\leq j\leq
d-1}\sigma_{j}\right)^{2}\left(\varepsilon+\frac{1}{P^{-}(d)}\right)\ll\varepsilon\left(\sum_{1\leq
j\leq d-1}\sigma_{j}\right)^{2}.$

By Chebyshev’s inequality, we therefore deduce that for all but
$O(\varepsilon^{1/3}d)$ choices of $1\leq\ell\leq d-1$,

$\sum_{1\leq j\leq d-1}\|\frac{\ell
j}{d}\|^{2}\sigma_{j}=\left(\frac{1}{12}+O(\varepsilon^{1/3})\right)\sum_{1\leq
j\leq d-1}\sigma_{j}.$

Therefore, invoking (10), we deduce that for all but $O(\varepsilon^{1/3}d)$
choices of $1\leq\ell\leq d-1$ we have

$\mathbb{D}(f^{\ell},1;x)^{2}\geq
8\cdot\left(\frac{1}{12}+O(\varepsilon^{1/3})\right)\sum_{1\leq j\leq
d-1}\sigma_{j}=\left(\frac{2}{3}+O(\varepsilon^{1/3})\right)\sum_{1\leq j\leq
d-1}\sigma_{j},$

as claimed. ∎

For $\varepsilon>0$ small, define

$\mathcal{C}_{d}(\varepsilon):=\Big{\\{}1\leq\ell\leq
d-1:\frac{1}{x}\Big{|}\sum_{n\leq
x}f^{\ell}(n)\Big{|}\geq\varepsilon\Big{\\}}.$

Note that $\ell\in\mathcal{C}_{d}(\varepsilon)$ if, and only if
$-\ell\in\mathcal{C}_{d}(\varepsilon)$.
The proof of Theorem 1.2 requires an analysis of the set
$\mathcal{C}_{d}(\varepsilon)$ for an appropriate, small choice of
$\varepsilon$. If $|\mathcal{C}_{d}(\varepsilon)|$ is small (in a precise
sense) then the conclusion of the theorem is trivial; what is of greater
interest are the ramifications of assuming that
$|\mathcal{C}_{d}(\varepsilon)|$ is in fact large.
If, say, $1\in\mathcal{C}_{d}(\varepsilon)$ then $f$ is $n^{it}$-pretentious,
for some $|t|\ll 1/\varepsilon^{2}$, say, by (9). We make the heuristic claim
that if $|\mathcal{C}_{d}(\varepsilon)|$ is large then $|t|$ must be quite
small.
Indeed, assume instead that $|t|$ were bounded away from 0. We expect the
pretentiousness of $f$ to propagate to powers $f^{\ell}$ and that, roughly
speaking, $f^{\ell}$ is $n^{i\ell t}$-pretentious. Thus, $f^{\ell}$ should
have large partial sums as well, at least for some range of $\ell$. On the
other hand, it can be shown (see (3.3) below) that

$\left|\sum_{n\leq x}f^{\ell}(n)\right|\ll\frac{x}{1+\ell|t|},$

which then forces the partial sums to be small when $\ell|t|$ is large. As
$|\mathcal{C}_{d}(\varepsilon)|$ is assumed large it must contain many large
values of $\ell$, which precludes this type of behaviour, and so we should
conclude that $|t|$ must in fact be quite small.
The following proposition gives a rigorous formulation of this intuition.

######  Proposition 3.3.

Let $d$ be a positive integer and let $c>0$ be chosen such that
$P^{-}(d)>1/c$. Set $m:=\lceil 2/c^{2}\rceil$ and for each $1\leq\ell\leq d-1$
choose
$t_{\ell}=t_{\ell}(\varepsilon)\in[-2m/\varepsilon^{2},2m/\varepsilon^{2}]$
such that

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

If $\varepsilon$ is sufficiently small, $|\mathcal{C}_{d}(\varepsilon)|\geq
cd$ and $m^{2}\log(1/\varepsilon)<\tfrac{1}{32}\log\log x$ then

$\max_{1\leq\ell\leq d-1}|t_{\ell}|\leq\frac{3\varepsilon^{-32m^{2}}}{\log
x}.$

######  Remark 7.

Note that if we assume that $d$ grows sufficiently slowly then we could argue
more simply from the pretentious triangle inequality and the minimal property
of $t_{\ell}$ that for any $1\leq\ell\leq d$,

$\mathbb{D}(1,n^{i(t_{\ell}-\ell
t_{1})};x)\leq\mathbb{D}(f^{\ell},n^{it_{\ell}};x)+\mathbb{D}(f^{\ell},n^{i\ell
t_{1}};x)\leq 2\mathbb{D}(f^{\ell},n^{i\ell t_{1}};x)\leq
2\ell\mathbb{D}(f,n^{it_{1}};x);$

hence, $t_{\ell}\approx\ell t_{1}$ and $dt_{1}\approx 0$ whenever
$\mathbb{D}(f,n^{it_{1}};x)$ is small (which is the case if $f$ has large
partial sums up to $x$ by (9)). The novelty of Proposition 3.3 is that the
same conclusion still holds, even when $d$ is fairly large, provided many of
the powers $f^{\ell}$ have large partial sums.

To prove Proposition 3.3 we will need the following inverse sumset result,
which follows from classical work of Freiman [4] in additive combinatorics
(see [27] for an accessible proof).

######  Lemma 3.4.

Let $c>0$. Let $G$ be a finite Abelian group and let $A\subset G$ be a
symmetric subset888We say that a subset $S$ of a finite Abelian group is
_symmetric_ whenever $s\in S$ if, and only if, $-s\in S$. Equivalently,
$-S:=\\{-s:s\in S\\}=S$. that satisfies $|A|\geq c|G|$. If $A$ is not
contained in a coset of a proper subgroup of $G$ then999Given a finite abelian
group $G$, sets $A,B\subseteq G$ and an integer $r\geq 2$ we define the sumset
$A+B$ as  $A+B:=\\{a+b:\,(a,b)\in A\times B\\},$ and inductively define
$rA:=A+(r-1)A$. $2^{k}A=G$ for some $1\leq
k\leq\lceil\frac{\log(1/c)}{\log(3/2)}\rceil$.

###### Proof.

Call $K:=1+\lceil\frac{\log(1/c)}{\log(3/2)}\rceil$. Since $A$ is symmetric,
we have $A=-A$. Now, by Freiman’s theorem, we see that if $B\subset G$ is
symmetric and $B$ is not contained in a coset of a proper subgroup of $G$ then
either $B+B=G$ or else $|B+B|\geq\frac{3}{2}|B|$. Applying this iteratively,
we find that if $j\geq 1$ and we assume that none of the sets
$A,2A,\ldots,2^{j-1}A$ is contained in a coset of a proper subgroup of $G$
then either $2^{j}A=G$, or else

$|G|\geq|2^{j}A|\geq\frac{3}{2}|2^{j-1}A|\geq\cdots\geq\left(\frac{3}{2}\right)^{j}|A|\geq\left(\frac{3}{2}\right)^{j}c|G|.$

If $j\geq K$ this is impossible, and so we deduce that $2^{j}A=G$ for some
$1\leq j\leq K-1$, as long as we can verify that $2^{j}A$ is not contained in
a coset of a proper subgroup of $G$ for any $1\leq j\leq K-1$.
But observe that if $B+B\subseteq b+H$ for some $H<G$ and $b\in G$ then for
any $b^{\prime}\in B$ we have $B\subseteq(b-b^{\prime})+H$. It follows by
induction that if $2^{j}A$ were contained in a coset of a proper subgroup of
$G$ for some $j\geq 1$ then the same is true of $2^{i}A$ for any $0\leq i\leq
j$. Since, by hypothesis, $A$ is not contained in a coset of a proper subgroup
of $G$ we may conclude that none of the iterated sets $2^{j}A$ are, and the
conclusion follows. ∎

######  Corollary 3.5.

Let $c>0$ and let $d\geq 1$ be an integer such that $P^{-}(d)>1/c$. If
$A\subseteq\mathbb{Z}/d\mathbb{Z}$ is symmetric with $|A|\geq cd$ then
$2^{j}A=\mathbb{Z}/d\mathbb{Z}$ for some $1\leq
j\leq\lceil\tfrac{\log(1/c)}{\log(3/2)}\rceil$.

###### Proof.

If $A=\mathbb{Z}/d\mathbb{Z}$ then the result is trivial, so we may assume
instead that $A$ is a proper subset of $\mathbb{Z}/d\mathbb{Z}$. By Lemma 3.4,
it suffices to verify that any symmetric subset $A$ in
$\mathbb{Z}/d\mathbb{Z}$ cannot be a subset of a coset of a proper subgroup of
$\mathbb{Z}/d\mathbb{Z}$. But if this were the case then $A\subset b+H$ for
some $H<G$ and $b\in G$, in which case

$cd\leq|A|\leq|b+H|=|H|,$

whereas if $H\neq G$ then $|H|=d^{\prime}$ for some $d^{\prime}|d$,
$d^{\prime}<d$. It follows that $d^{\prime}\leq d/P^{-}(d)<cd$, which is a
contradiction. The claim follows. ∎

###### Proof of Proposition 3.3.

Write $\mathcal{C}_{d}=\mathcal{C}_{d}(\varepsilon)$. By (9), for each
$\ell\in\mathcal{C}_{d}$ we have

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

where here $\tilde{t}_{\ell}\in[-1/\varepsilon^{2},1/\varepsilon^{2}]$ is
chosen to minimize $\min_{|t|\leq
1/\varepsilon^{2}}\mathbb{D}(f^{\ell},n^{it};x)$ (note that
$t_{\ell}\neq\tilde{t}_{\ell}$ in general). If $\varepsilon$ is small enough
(and thus $x$ is large enough), then upon rearranging we deduce that

(12) $\mathbb{D}(f^{\ell},n^{i\tilde{t}_{\ell}};x)^{2}\leq
2\log(1/\varepsilon)\text{ for all }\ell\in\mathcal{C}_{d}.$

Now, since $P^{-}(d)>1/c$ and $|\mathcal{C}_{d}|\geq cd$, by Corollary 3.5 we
know that $\mathbb{Z}/d\mathbb{Z}=J\mathcal{C}_{d}$ for some $J\leq
2^{\lceil\frac{\log(1/c)}{\log(3/2)}\rceil}\leq 2c^{-2}\leq m$. Thus, for any
$1\leq\ell\leq d-1$ we have a representation

$\ell\equiv r_{1}+\cdots+r_{\lambda}\pmod{d},$

where $r_{j}\in\mathcal{C}_{d}$ and $1\leq\lambda\leq m$. But by (12), (8) and
induction,

$\mathbb{D}(f^{r_{1}+\cdots+r_{\lambda}},n^{i(\tilde{t}_{r_{1}}+\cdots+\tilde{t}_{r_{\lambda}})};x)\leq\sum_{1\leq
j\leq\lambda}\mathbb{D}(f^{r_{j}},n^{i\tilde{t}_{r_{j}}};x)\leq
m\sqrt{2\log(1/\varepsilon)}.$

Since $\left|\sum_{1\leq j\leq\lambda}\tilde{t}_{r_{j}}\right|\leq
2m/\varepsilon^{2}$, by the minimality property for
$t_{\ell}\in[-2m/\varepsilon^{2},2m/\varepsilon^{2}]$ (7) yields

$\mathbb{D}(n^{it_{\ell}},n^{i(\tilde{t}_{r_{1}}+\cdots+\tilde{t}_{r_{\lambda}})};x)\leq\mathbb{D}(f^{\ell},n^{it_{\ell}};x)+\mathbb{D}(f^{r_{1}+\cdots+r_{\lambda}},n^{i(\tilde{t}_{r_{1}}+\cdots+\tilde{t}_{r_{\lambda}})};x)\leq
2m\sqrt{2\log(1/\varepsilon)}.$

By the Vinogradov-Korobov zero-free region for the Riemann zeta function, it
follows that if $|t|\geq 100$ then for large $x$,

$\mathbb{D}(1,n^{it};x)^{2}=\sum_{p\leq
x}\frac{1-\text{Re}(p^{it})}{p}=\log\log x-\log|\zeta(1+1/\log
x+it)|+O(1)\geq\frac{1}{4}\log\log x,$

so with $u_{\ell}:=t_{\ell}-\tilde{t}_{r_{1}}-\cdots-\tilde{t}_{r_{\lambda}}$
this would give the contradiction

$\frac{1}{4}\log\log
x\leq\mathbb{D}(1,n^{iu_{\ell}};x)^{2}\leq(2m\sqrt{2\log(1/\varepsilon)})^{2}=8m^{2}\log(1/\varepsilon),$

if $|u_{\ell}|\geq 100$. Thus, we may assume that $|u_{\ell}|\leq 100$. Taking
squares and instead using

$\mathbb{D}(1,n^{it};x)^{2}=\log(1+|t|\log x)+O(1)$

whenever $|t|\leq 100$, say, we thus deduce that

$\Big{|}t_{\ell}-\sum_{1\leq
j\leq\lambda}\tilde{t}_{r_{j}}\Big{|}\leq\frac{\varepsilon^{-8m^{2}}}{\log
x}.$

Now let $1\leq\ell_{1},\ell_{2}\leq d-1$. Choose any additive representations

$\ell_{1}\equiv r_{1}+\cdots+r_{\lambda_{1}}\pmod{d},\quad\ell_{2}\equiv
s_{1}+\cdots+s_{\lambda_{2}}\pmod{d},$

with $\lambda_{1},\lambda_{2}\leq m$, then by the same argument applied with
$\ell\in\\{\ell_{1},\ell_{2},\ell_{1}+\ell_{2}\\}$ we obtain, uniformly over
$\ell_{1},\ell_{2}\in\mathbb{Z}/d\mathbb{Z}$,

$\displaystyle|t_{\ell_{1}+\ell_{2}}-t_{\ell_{1}}-t_{\ell_{2}}|$
$\displaystyle\leq|t_{\ell_{1}+\ell_{2}}-(\tilde{t}_{r_{1}}+\cdots+\tilde{t}_{r_{\lambda_{1}}}+\tilde{t}_{s_{1}}+\cdots+\tilde{t}_{s_{\lambda_{2}}})|+|t_{\ell_{1}}-(\tilde{t}_{r_{1}}+\cdots+\tilde{t}_{r_{\lambda_{1}}})|+|t_{\ell_{2}}-(\tilde{t}_{s_{1}}+\cdots+\tilde{t}_{s_{\lambda_{2}}})|$
$\displaystyle\leq\frac{\varepsilon^{-8(2m)^{2}}}{\log
x}+2\frac{\varepsilon^{-8m^{2}}}{\log x}\leq
3\frac{\varepsilon^{-32m^{2}}}{\log x}.$

Since we may always select $t_{0}:=0$, and as $f^{\ell+kd}=f^{\ell}$ we can
choose $t_{\ell+kd}=t_{\ell}$ for all $k\in\mathbb{Z}$, the map
$\phi:\mathbb{Z}/d\mathbb{Z}\rightarrow\mathbb{R}$ given by $\phi(m):=t_{m}$
satisfies the approximate homomorphism condition

$|\phi(\ell_{1}+\ell_{2})-\phi(\ell_{1})-\phi(\ell_{2})|\leq
3\frac{\varepsilon^{-32m^{2}}}{\log
x},\quad\ell_{1},\ell_{2}\in\mathbb{Z}/d\mathbb{Z}.$

By a generalization due to Ruzsa of a result of Hyers [25, Statement (7.3)],
there is a genuine homomorphism
$\psi:\mathbb{Z}/d\mathbb{Z}\rightarrow\mathbb{R}$ such that

$\max_{\ell\in\mathbb{Z}/d\mathbb{Z}}|\phi(\ell)-\psi(\ell)|\leq
3\frac{e^{-32m^{2}}}{\log x}.$

But there are no non-trivial homomorphisms from $\mathbb{Z}/d\mathbb{Z}$ to
$\mathbb{R}$ since the latter is torsion-free. Hence, $\psi(\ell)=0$ for all
$\ell$ and we deduce that

$\max_{1\leq\ell\leq d-1}|t_{\ell}|\leq\frac{3\varepsilon^{-32m^{2}}}{\log
x},$

as claimed. ∎

With this last lemma in hand we may prove the following proposition, which
allows us to deal with the case in which some $\sigma_{m}$ is quite large.

######  Proposition 3.6.

Let $d\geq 2$, $\varepsilon\in(0,1)$ and $3\leq x\leq x_{0}$. Let $c>0$
satisfy $P^{-}(d)>1/c$, and assume that $|\mathcal{C}_{d}(\varepsilon)|\geq
cd$. Put $m:=\lceil 2/c^{2}\rceil$ and suppose that

$m^{2}\log(1/\varepsilon)<\frac{1}{32}\log\log x.$

Then for any $1\leq j,\ell\leq d-1$ and $\lambda\in(0,1)$ at least one of the
following bounds hold:

$\frac{1}{x}\left|\sum_{n\leq x}f^{\ell}(n)\right|\leq\varepsilon,$

or else

$\frac{1}{x}\left|\sum_{n\leq x}f^{\ell}(n)\right|\ll\|\ell
j/d\|^{-1}\left(\lambda\varepsilon^{-32m^{2}}+\log(e/\lambda)\left(\lambda^{1-2/\pi}+\frac{1}{\sigma_{j}}\right)+\frac{1}{\sqrt{\sigma_{j}}}+\frac{1}{(\log
x)^{1-2/\pi+o(1)}}\right).$

###### Proof.

We may assume that $x$ is as large, and $\varepsilon$ as small, as desired,
otherwise at least one of the alternatives is trivial. We may also assume that
$\sigma_{j}\geq 1$ and $\lambda\varepsilon^{-32m^{2}}<1/2$, since otherwise
the second alternative is trivial.
Suppose the first alternative fails. Arguing as in the proof of Proposition
3.3,

$\mathbb{D}(f^{\ell},n^{it_{\ell}};x)^{2}\leq
2\log(1/\varepsilon)<\frac{1}{16m^{2}}\log\log x.$

for $\varepsilon$ small enough. By [12, Lem. 7.1] we have

$\displaystyle\frac{1}{x}\sum_{n\leq x}f^{\ell}(n)$
$\displaystyle=\frac{x^{it_{\ell}}}{1+it_{\ell}}\frac{1}{x}\sum_{n\leq
x}f^{\ell}(n)n^{-it_{\ell}}+O\left(\frac{e^{\mathbb{D}(f^{\ell},n^{it_{\ell}};x)\sqrt{(2+o(1))\log\log
x}}}{\log x}\right)$ (13)
$\displaystyle=\frac{x^{it_{\ell}}}{1+it_{\ell}}\frac{1}{x}\sum_{n\leq
x}f^{\ell}(n)n^{-it_{\ell}}+O\left((\log
x)^{\tfrac{1}{2\sqrt{2}}-1+o(1)}\right).$

Let now $S_{j}:=\\{p\leq q:f(p)=e(j/d)\\}$ and define the completely additive
function

$\Omega_{S_{j}}(n):=\sum_{\begin{subarray}{c}p^{k}||n\\\ p\in
S_{j}\end{subarray}}k=\sum_{\begin{subarray}{c}mp=n\\\ p\in
S_{j}\end{subarray}}1,$

whose mean-value over $n\leq x$ is asymptotically

$\sum_{\begin{subarray}{c}p^{k}\leq x\\\ p\in
S_{j}\end{subarray}}\frac{1}{p^{k}}\left(1-\frac{1}{p}\right)+O\left(\sqrt{\frac{\log\log
x}{\log x}}\right)=\sigma_{j}+O\left(\sqrt{\frac{\log\log x}{\log x}}\right).$

By the Turán-Kubilius inequality [26, Thm. III.3.1] and complete
multiplicativity, we deduce that

$\displaystyle\frac{1}{x}\sum_{n\leq x}f(n)n^{-it_{\ell}}$
$\displaystyle=\frac{1}{x}\sum_{n\leq
x}f(n)n^{-it_{\ell}}\cdot\frac{\Omega_{S_{j}}(n)+(\sigma_{j}-\Omega_{S_{j}}(n))}{\sigma_{j}}$
$\displaystyle=\frac{1}{\sigma_{j}}\cdot\frac{1}{x}\sum_{\begin{subarray}{c}mp\leq
x\\\ p\in
S_{j}\end{subarray}}f^{\ell}(p)p^{-it_{\ell}}f^{\ell}(m)m^{-it_{\ell}}+O\left(\frac{1}{x\sqrt{\sigma_{j}}}\sum_{n\leq
x}\frac{|\Omega_{S_{j}}(n)-\sigma_{j}|}{\sqrt{\sigma_{j}}}\right)$
$\displaystyle=\frac{1}{\sigma_{j}}\sum_{\begin{subarray}{c}p\leq x\\\ p\in
S_{j}\end{subarray}}\frac{f^{\ell}(p)p^{-it_{\ell}}}{p}\frac{p}{x}\sum_{m\leq
x/p}f^{\ell}(m)m^{-it_{\ell}}+O\left(\frac{1}{\sqrt{\sigma_{j}}}\right).$

We split the sum over $p\leq x$ into the segments $p\leq x^{\lambda}$ and
$x^{\lambda}<p\leq x$. The contribution from the second segment to the above
is

$\ll\frac{1}{\sigma_{j}}\sum_{x^{\lambda}<p\leq
x}\frac{1}{p}\ll\frac{\log(e/\lambda)}{\sigma_{j}}.$

Now, for each $p\leq x^{\lambda}$ we apply a Lipschitz bound [12, Thm. 4],
which yields

$\frac{p}{x}\sum_{n\leq x/p}f^{\ell}(n)n^{-it_{\ell}}=\frac{1}{x}\sum_{n\leq
x}f^{\ell}(n)n^{-it_{\ell}}+O\left(\lambda^{1-2/\pi}\log(e/\lambda)+\frac{1}{(\log
x)^{1-2/\pi+o(1)}}\right).$

We thus conclude that

$\displaystyle\frac{1}{x}\sum_{n\leq x}f^{\ell}(n)n^{-it_{\ell}}$
$\displaystyle=\left(\frac{1}{\sigma_{j}}\sum_{\begin{subarray}{c}p\leq
x^{\lambda}\\\ p\in
S_{j}\end{subarray}}\frac{f^{\ell}(p)p^{-it_{\ell}}}{p}\right)\frac{1}{x}\sum_{n\leq
x}f^{\ell}(n)n^{-it_{\ell}}$
$\displaystyle+O\left(\frac{1}{\sqrt{\sigma_{j}}}+\log(e/\lambda)\left(\frac{1}{\sigma_{j}}+\lambda^{1-2/\pi}\right)+(\log
x)^{2/\pi-1+o(1)}\right).$

By Proposition 3.3, $|t_{\ell}|\log x\ll\varepsilon^{-32m^{2}}$, and so for
each $p\leq x^{\lambda}$ we find

$p^{-it_{\ell}}=1+O(\lambda\varepsilon^{-32m^{2}}),$

and therefore

$\displaystyle\frac{1}{\sigma_{j}}\sum_{\begin{subarray}{c}p\leq
x^{\lambda}\\\ p\in S_{j}\end{subarray}}\frac{f^{\ell}(p)p^{-it_{\ell}}}{p}$
$\displaystyle=\frac{1}{\sigma_{j}}\sum_{\begin{subarray}{c}p\leq x\\\ p\in
S_{j}\end{subarray}}\frac{f^{\ell}(p)}{p}+O\left(\lambda\varepsilon^{-32m^{2}}+\frac{\log(e/\lambda)}{\sigma_{j}}\right)$
$\displaystyle=e(\ell
j/d)+O\left(\lambda\varepsilon^{-32m^{2}}+\frac{\log(e/\lambda)}{\sigma_{j}}\right).$

Hence, appealing once again to [12, Lem. 7.1], we find

$\displaystyle\frac{1}{x}\sum_{n\leq x}f^{\ell}(n)=e(\ell
j/d)\frac{1}{x}\sum_{n\leq
x}f^{\ell}(n)+O\left(\frac{1}{\sqrt{\sigma_{j}}}+\log(e/\lambda)\left(\frac{1}{\sigma_{j}}+\lambda^{1-2/\pi}\right)+\lambda\varepsilon^{-32m^{2}}+(\log
x)^{\tfrac{2}{\pi}-1+o(1)}\right).$

Rearranging the above and using $|1-e(\ell j/d)|\gg\|\ell j/d\|$, the claim
follows. ∎

###### Proof of Theorem 1.2.

We may assume in what follows that $\Sigma$ (and thus also $x$ and $d$) is
larger than any specified constant, since otherwise the claim is trivial (by
adjusting the implicit constant appropriately).
Let $\varepsilon>0$ be a small parameter to be chosen later in terms of

$\Sigma:=\min\\{P^{-}(d),2+\sum_{\begin{subarray}{c}p\leq x\\\ f(p)\neq
0,1\end{subarray}}p^{-1}\\},$

subject only to the constraints

$\varepsilon\geq\Sigma^{-1/3}\geq P^{-}(d)^{-1/3}.$

Set $M:=\lceil 2/\varepsilon\rceil$. Note that as $\Sigma\leq\log\log x+O(1)$
we must also have

$32M^{2}\log(1/\varepsilon)<\log\log x,$

for $x$ large enough.
As above, write

$\mathcal{C}_{d}(\sqrt{\varepsilon})=\Big{\\{}1\leq\ell\leq
d-1:\frac{1}{x}\Big{|}\sum_{n\leq
x}f^{\ell}(n)\Big{|}\geq\varepsilon^{1/2}\Big{\\}}.$

We consider several cases.
Case 1: Suppose first that
$|\mathcal{C}_{d}(\sqrt{\varepsilon})|\leq\sqrt{\varepsilon}d$. Adding in the
contribution from $\ell=0$, we trivially have

$\mathcal{L}:=\frac{1}{d}\sum_{0\leq\ell\leq d-1}\left|\sum_{n\leq
x}f^{\ell}(n)\right|^{2}\leq\frac{|\mathcal{C}_{d}(\sqrt{\varepsilon})|+1}{d}x^{2}+\sqrt{\varepsilon}x^{2}\ll\sqrt{\varepsilon}x^{2}.$

Case 2: Suppose next that
$|\mathcal{C}_{d}(\sqrt{\varepsilon})|>\sqrt{\varepsilon}d$. For each
$1\leq\ell\leq d-1$ we choose $t_{\ell}\in[-2M/\varepsilon,2M/\varepsilon]$ so
that

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

Since $\sqrt{\varepsilon}P^{-}(d)\geq P^{-}(d)^{5/6}>1$, by Proposition 3.3 we
have

(14) $\max_{1\leq\ell\leq
d-1}|t_{\ell}|\leq\frac{3\varepsilon^{-(20/\varepsilon)^{2}}}{\log x}.$

As above, let $S_{j}:=\\{p\leq q:f(p)=e(j/d)\\}$ and define
$\sigma_{j}:=\sigma_{j}(x)=\sum_{\begin{subarray}{c}p\leq x\\\ p\in
S_{j}\end{subarray}}p^{-1}$. We consider two subcases.
Case 2.a) Suppose there is $1\leq m\leq d-1$ such that
$\sigma_{m}\geq\varepsilon\sum_{1\leq j\leq
d-1}\sigma_{j}\gg\varepsilon\Sigma$.
Take $J:=\left\lfloor\varepsilon^{-1/2}\right\rfloor$. By the Erdős-Turán
inequality [26, Thm. I.6.15] we have

$|\,|\\{1\leq\ell\leq d:\|\ell
m/d\|\leq\varepsilon^{1/2}\\}|-2\varepsilon^{1/2}d\,|\ll\frac{d}{J}+d\sum_{1\leq
k\leq J}\frac{1}{k}\left|\sum_{1\leq\ell\leq
d}e\left(\frac{klm}{d}\right)\right|\ll\varepsilon^{1/2}d+d^{2}\sum_{\begin{subarray}{c}1\leq
k\leq J\\\ d|km\end{subarray}}\frac{1}{k}\ll\varepsilon^{1/2}d,$

where in the last step we concluded that the sum over $k$ vanishes, since if
$k$ contributed non-trivially to the sum, i.e. $d|km$, then as $m<d$,

$1/\varepsilon<P^{-}(d)\leq d/m\leq k\leq J\leq 1/\varepsilon,$

a contradiction. It thus follows that

$\|\ell m/d\|>\varepsilon^{1/2}\text{ for all but
}O\left(\varepsilon^{1/2}d\right)\text{ choices of }1\leq\ell\leq d-1.$

By Proposition 3.6, we deduce that for each $\ell$ satisfying $\|\ell
m/d\|>\varepsilon^{1/2}$, either

$\Big{|}\sum_{n\leq x}f^{\ell}(n)\Big{|}\leq\sqrt{\varepsilon}x,$

or else that

$\displaystyle\frac{1}{x}\left|\sum_{n\leq
x}f^{\ell}(n)\right|\ll\Big{\|}\frac{\ell
m}{d}\Big{\|}^{-1}\left(\lambda\varepsilon^{-(20/\varepsilon)^{2}}+\log(e/\lambda)\left(\lambda^{1-2/\pi}+\frac{1}{\sigma_{m}}\right)+\frac{1}{\sqrt{\sigma_{m}}}\right),$

if $x\geq x_{0}(\varepsilon)$. We select

$\lambda:=\min\\{\varepsilon^{1+(20/\varepsilon)^{2}},e^{-\sqrt{\sigma_{m}}}\\},$

so that, using $\|\ell m/d\|>\varepsilon^{1/2}$, when $\varepsilon$ is small
enough we obtain, for all but $O(\varepsilon^{1/2}d)$ choices of $\ell$, that

$\frac{1}{x}\left|\sum_{n\leq
x}f^{\ell}(n)\right|\ll\varepsilon^{-1/2}\left(\varepsilon+\frac{1}{\sqrt{\sigma_{m}}}+\frac{\log(1/\varepsilon)}{\varepsilon^{2}\sigma_{m}}+\sigma_{m}^{1/2}e^{-\frac{1}{3}\sqrt{\sigma_{m}}}\right)\ll\varepsilon^{1/2}+\frac{1}{\sqrt{\varepsilon\sigma_{m}}}+\frac{\log(1/\varepsilon)}{\varepsilon^{5/2}\sigma_{m}}.$

Bounding trivially the $\ll\varepsilon^{1/2}d$ partial sums of $f^{\ell}$ for
$\|\ell m/d\|<\varepsilon^{1/2}$ and averaging, we obtain

$\mathcal{L}\ll\varepsilon^{1/2}x^{2}+x^{2}\left(\varepsilon+\frac{1}{\varepsilon\sigma_{m}}+\frac{\log(1/\varepsilon)^{2}}{\varepsilon^{5}\sigma_{m}^{2}}\right)\ll\left(\varepsilon^{1/2}+\frac{1}{\varepsilon^{2}\Sigma}+\frac{\log(1/\varepsilon)^{2}}{\varepsilon^{7}\Sigma^{2}}\right)x^{2}.$

Case 2.b) Suppose finally that $\sigma_{m}<\varepsilon\sum_{1\leq j\leq
d-1}\sigma_{j}$ for all $1\leq m\leq d-1$.
By Lemma 3.2, we find that for all but $O(\varepsilon^{1/3}d)$ choices of
$\ell$ we have

$\mathbb{D}(f^{\ell},1;x)^{2}\geq\left(\frac{2}{3}+O(\varepsilon^{1/3})\right)\Sigma.$

By the pretentious triangle inequality, we also have

$\mathbb{D}(f^{\ell},1;x)\leq\mathbb{D}(f^{\ell},n^{it_{\ell}};x)+\mathbb{D}(1,n^{it_{\ell}};x),$

and moreover by (14),

$\mathbb{D}(1,n^{it_{\ell}};x)^{2}=\log(1+|t_{\ell}|\log
x)+O(1)\leq\frac{400}{\varepsilon^{2}}\log(1/\varepsilon)+O(1).$

Using the inequality $(a+b)^{2}\leq 2(a^{2}+b^{2})$ we thus deduce that

$\mathbb{D}(f^{\ell},n^{it_{\ell}};x)^{2}\geq\frac{1}{2}\mathbb{D}(f^{\ell},1;x)^{2}-\mathbb{D}(1,n^{it_{\ell}};x)^{2}\geq\left(\frac{1}{3}+O(\varepsilon^{1/3})\right)\Sigma-\frac{400}{\varepsilon^{2}}\log(1/\varepsilon)\geq\left(\frac{1}{4}+O(\varepsilon^{1/3})\right)\Sigma,$

owing to the constraint $\varepsilon\geq\Sigma^{-1/3}$, and thus

$\frac{400}{\varepsilon^{2}}\log(1/\varepsilon)\leq
400\Sigma^{2/3}\log\Sigma\leq\frac{1}{20}\Sigma$

whenever $\Sigma$ is large enough. By (9), therefore, for all but
$O(\varepsilon^{1/3}d)$ choices of $\ell$ we obtain

$\frac{1}{x}\left|\sum_{n\leq
x}f^{\ell}(n)\right|\ll\frac{\varepsilon}{M}+\frac{1}{\log
x}+\mathbb{D}(f^{\ell},n^{it_{\ell}};x)^{2}e^{-\mathbb{D}(f^{\ell},n^{it_{\ell}};x)^{2}}\ll\varepsilon^{2}+\Sigma
e^{-\frac{1}{5}\Sigma},$

for sufficiently small $\varepsilon$, and therefore again bounding the partial
sums corresponding to the $O(\varepsilon^{1/3}d)$ exceptional $\ell$ we obtain
in this case,

$\mathcal{L}\ll
x^{2}\left(\varepsilon^{1/3}+\Sigma^{2}e^{-\frac{2}{5}\Sigma}\right).$

Combining all of the cases together, we obtain, in general,

$\mathcal{L}\ll
x^{2}\left(\varepsilon^{1/3}+\frac{1}{\varepsilon^{2}\Sigma}+\frac{\log(1/\varepsilon)^{2}}{\varepsilon^{7}\Sigma^{2}}+\Sigma^{2}e^{-\frac{2}{5}\Sigma}\right)\ll
x^{2}\left(\varepsilon^{1/3}+\frac{1}{\varepsilon^{2}\Sigma}+\frac{\log(1/\varepsilon)^{2}}{\varepsilon^{7}\Sigma^{2}}\right).$

We choose $\varepsilon=\Sigma^{-3/11}$, which yields the bound

$\mathcal{L}\ll
x^{2}\left(\Sigma^{-1/11}+\frac{(\log\Sigma)^{2}}{\Sigma^{1/11}}\right)\ll
x^{2}\frac{(\log\Sigma)^{2}}{\Sigma^{1/11}},$

as claimed. ∎

##  4\. Proof of Theorem 1.1

We now turn to the proof of Theorem 1.1, concerning lower bounds for the sum

$\sum_{\begin{subarray}{c}p\leq x\\\ f(p)\neq
0,1\end{subarray}}\frac{1}{p},\text{ with
}f\in\mathcal{M}_{1}(x_{0};d),\,x\geq x_{0}^{\delta}.$

We will use a sieve-theoretic argument, based on the obvious implication

$f(p)=1\,\forall\,p|n\Rightarrow f(n)=1,$

to derive data about _prime_ values of $f$ from the (weak) equidistribution of
_integer_ values of $f(n)$ at scale $x_{0}$.
Our general argument will allow us to handle $d\ll(\eta\delta)^{-1}e^{(\log
x_{0})^{c}}$ for some absolute constant $c>0$. To deal with the complementary
range of $d$ in the particular case that $f$ is an order $d$ character
$\chi\pmod{q}$, we use zero-density estimates for Dirichlet $L$-functions as
follows.

######  Proposition 4.1.

Fix $c\in(0,1)$. If $\chi$ is a primitive character modulo $q$ with order
$d\geq e^{(\log q)^{c}}$ then as $q\rightarrow\infty$,

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

###### Proof.

We will estimate the product

(15) $\prod_{1\leq\ell\leq d}|L(1+1/\log q,\chi^{\ell})|$

in two ways.
For the first, note that if $\chi^{\ell}$ is a non-exceptional character (see
e.g. [10, Sec. 4.2] for a precise definition) then, using e.g. [10, (4.3)] to
handle non-principal $\chi^{\ell}$ we have

$|L(1+1/\log q,\chi^{\ell})|=\exp\left(\text{Re}\left(-\sum_{p\leq
q}\log\Big{(}1-\frac{\chi^{\ell}(p)}{p^{1+1/\log
q}}\Big{)}+O(1)\right)\right)=\exp\left(\sum_{p\leq
q}\frac{\chi^{\ell}(p)}{p}+O(1)\right)$

for all but at most one $1\leq\ell\leq d-1$, which, if it exists, is real. The
estimate also holds when $\ell=d$ using properties of the Riemann zeta
function.
If $d$ is even then let $\ell_{0}\in\\{1,\ldots,d-1\\}$ be such that
$\chi^{\ell_{0}}$ is real (there is a unique such choice); otherwise, choose
$\ell_{0}$ arbitrarily from that set. From [26, Thms. II.8.20-II.8.21], we
derive in any case that

$|L(1+1/\log q,\chi^{\ell_{0}})|\prod_{p\leq
q}\left(1-\frac{\chi^{\ell_{0}}(p)}{p}\right)\gg\frac{1}{\sqrt{q}\log q},$

for large enough $q$. Therefore, by the preceding estimates and orthogonality
(varying the $O(1)$ term as needed),

(16) $\prod_{1\leq\ell\leq d}|L(1+1/\log
q,\chi^{\ell})|\geq\frac{1}{\sqrt{q}\log q}\exp\left(\sum_{1\leq\ell\leq
d}\left(\sum_{p\leq
q}\frac{\chi^{\ell}(p)}{p}+O(1)\right)\right)=\frac{1}{\sqrt{q}\log
q}\exp\left(d\left(\sum_{\begin{subarray}{c}p\leq q\\\
\chi(p)=1\end{subarray}}\frac{1}{p}+O(1)\right)\right).$

For the second estimation of (15) we invoke zero-density estimates. Let
$\theta\in(0,c)$ be fixed, and set

$\sigma_{0}:=1-\frac{1}{(\log q)^{1-\theta}},\quad T:=(\log q)^{3}.$

We define

$\displaystyle\mathcal{G}$
$\displaystyle:=\mathcal{G}(\sigma_{0},T):=\\{\chi^{\ell}\\}_{1\leq\ell\leq
d-1}\cap\\{\psi\pmod{q}:L(s,\psi)\neq 0\,\forall\,\sigma_{0}<\text{Re}(s)\leq
1,\,|\text{Im}(s)|\leq T\\}$ $\displaystyle\mathcal{B}$
$\displaystyle:=\mathcal{B}(\sigma_{0},T):=\\{\chi^{\ell}\\}_{1\leq\ell\leq
d}\backslash\mathcal{G}.$

If $1\leq\ell\leq d-1$ then by e.g. [26, Thm. II.8.18],

$|L(1+\frac{1}{\log q},\chi^{\ell})|\ll\log q;$

when $\ell=d$ this bound is also valid since by Mertens’ theorem

$|L(1+1/\log q,\chi_{0})|\ll\exp\left(\sum_{p}\frac{1}{p^{1+1/\log
q}}\right)\ll\exp\left(\sum_{p\leq q}\frac{1}{p}\right)\ll\log q.$

Therefore, there is a $C>0$ absolute such that

(17) $\displaystyle\prod_{1\leq\ell\leq d}|L(1+1/\log
q,\chi^{\ell})|\leq\prod_{\begin{subarray}{c}1\leq\ell\leq d\\\
\chi^{\ell}\in\mathcal{G}\end{subarray}}|L(1+1/\log q,\chi^{\ell})|\cdot(C\log
q)^{|\mathcal{B}|}.$

Since $(1-\sigma_{0})\log q\gg 1$, replacing $1$ with $1+1/\log q$ and
following the proof of [19, Lem. 5.4] _mutatis mutandis_ , we find that for
each $\ell\in\mathcal{G}$ and any $X\geq 2$,

$\log L(1+1/\log q,\chi^{\ell})=-\sum_{p\leq
X}\log\left(1-\frac{\chi^{\ell}(p)}{p^{1+1/\log
q}}\right)+O\left(\frac{1}{\log q}+(\log q)^{4}e^{-\frac{(\log
q)^{\theta}}{2}\frac{\log X}{\log q}}\right).$

Taking $X:=\exp(10(\log q)^{1-\theta}\log\log q)$ and bounding the prime sum
trivially, we obtain

$\log|L(1+1/\log q,\chi^{\ell})|\leq\log\log X+O(1)=(1-\theta+o(1))\log\log
q,$

for all $\ell\in\mathcal{G}$. Furthermore, the log-free zero density estimate
[18, (18.9)] shows that for some absolute constant $C>0$,

$|\mathcal{B}|\ll(qT)^{C(1-\sigma_{0})}\leq e^{2C(\log q)^{\theta}}=o(d),$

when $q$ is sufficiently large, as $\theta<c$. Invoking both of these
estimates in (17), we deduce that

$\prod_{1\leq\ell\leq d}|L(1+1/\log q,\chi^{\ell})|\leq(C\log
q)^{(1-\theta)(d-|\mathcal{B}|)}(C\log q)^{|\mathcal{B}|}\leq\left(C(\log
q)^{1-\theta+\theta\tfrac{|\mathcal{B}|}{d}}\right)^{d}=(\log
q)^{d(1-\theta+o(1))}.$

Comparing this with (16), we find

$\displaystyle\frac{1}{\sqrt{q}\log
q}\exp\left(d\left(\sum_{\begin{subarray}{c}p\leq q\\\
\chi(p)=1\end{subarray}}\frac{1}{p}+O(1)\right)\right)$
$\displaystyle\leq\prod_{1\leq\ell\leq d}|L(1+1/\log q,\chi^{\ell})|$
$\displaystyle\leq(\log
q)^{d(1-\theta+o(1))}=\exp\left(d(1-\theta+o(1))\sum_{p\leq
q}\frac{1}{p}\right).$

Since $(\sqrt{q}\log q)^{1/d}\ll 1$, on taking $d$th roots and rearranging we
obtain

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

for all $\theta\in(0,c)$, and the claim follows. ∎

###### Proof of Theorem 1.1.

The conclusion is strongest when $x=x_{0}^{\delta}$, so we assume this in what
follows.
(a) Write

$E_{\neq 0,1}(x):=\sum_{\begin{subarray}{c}p\leq x\\\ f(p)\neq
0,1\end{subarray}}\frac{1}{p},$

and as above set

$c_{f}=c_{f}(x_{0}):=\prod_{\begin{subarray}{c}p\leq x_{0}\\\
f(p)=0\end{subarray}}\left(1-\frac{1}{p}\right).$

Since $f$ weakly equidistributes at scale $x_{0}$, by definition we have

(18) $|\\{n\leq x_{0}:f(n)=1\\}|\ll c_{f}\frac{x_{0}}{d}.$

On the other hand, we observe that

(19) $|\\{n\leq x_{0}:f(n)=1\\}|\geq\sum_{n\leq x_{0}}g(n),$

where $g(n):=1_{P^{+}(n)\leq x_{0}^{\delta}}1_{p|n\Rightarrow f(p)=1}$ is a
1-bounded, non-negative multiplicative function. By [17, Thm. 2], there is an
absolute constant $\beta>0$ such that if $x_{0}$ is large enough then

(20) $\sum_{n\leq x_{0}}g(n)\gg x_{0}\prod_{\begin{subarray}{c}p\leq x_{0}\\\
f(p)=0\end{subarray}}\left(1-\frac{1}{p}\right)\cdot\prod_{\begin{subarray}{c}p\leq
x_{0}\\\ f(p)\neq
0\end{subarray}}\left(1-\frac{1}{p}\right)\left(1-\frac{1_{f(p)=1}1_{p\leq
x}}{p}\right)^{-1}\cdot\left(\sigma_{-}\Big{(}e^{\mathbb{D}(g,1;x_{0})^{2}}\Big{)}+O(e^{-(\log
x_{0})^{\beta}})\right),$

where we have written $\sigma_{-}(u):=u\rho(u)$. Evaluating the various
factors in this expression, we see that

$\displaystyle x_{0}\prod_{\begin{subarray}{c}p\leq x_{0}\\\
f(p)=0\end{subarray}}\left(1-\frac{1}{p}\right)\cdot\prod_{\begin{subarray}{c}p\leq
x_{0}\\\ f(p)\neq
0\end{subarray}}\left(1-\frac{1}{p}\right)\left(1-\frac{1_{f(p)=1}1_{p\leq
x}}{p}\right)^{-1}$ $\displaystyle\gg
c_{f}x_{0}\exp\left(-\sum_{\begin{subarray}{c}p\leq x\\\ f(p)\neq
0\end{subarray}}\frac{1-1_{f(p)=1}}{p}-\log(1/\delta)\right)=c_{f}x_{0}\delta
e^{-E_{\neq 0,1}(x)},$

and also

$\displaystyle
e^{\mathbb{D}(g,1;x_{0})^{2}}=\exp\left(\sum_{\begin{subarray}{c}p\leq
x_{0}\\\ f(p)=0\end{subarray}}\frac{1}{p}+\sum_{x<p\leq
x_{0}}\frac{1}{p}+E_{\neq 0,1}(x)\right)\ll(c_{f}\delta)^{-1}e^{E_{\neq
0,1}(x)}.$

Now suppose the conclusion of the proposition fails with $x=x_{0}^{\delta}$
and $c_{3}=\beta$, so that $E_{\neq 0,1}(x)<\log(1/\eta)$. Since $\sigma_{-}$
is decreasing with $u$, we deduce that

$\sigma_{-}(e^{\mathbb{D}(1,g;x_{0})^{2}})\geq\sigma_{-}\left(c_{f}^{-1}\frac{C^{\prime}}{\eta\delta}\right),$

for some absolute $C^{\prime}>0$, and thus on combining (18), (19) and (20) we
obtain the chain of estimates

(21) $c_{f}\frac{x_{0}}{d}\gg\sum_{n\leq x_{0}}g(n)\gg
c_{f}x_{0}\eta\delta\left(\sigma_{-}\left(c_{f}^{-1}\frac{C^{\prime}}{\eta\delta}\right)+O(e^{-(\log
x_{0})^{\beta}})\right).$

If $d\leq C_{5}(\eta\delta)^{-1}e^{(\log x_{0})^{\beta}}$, with $C_{5}>0$
sufficiently small, then the error term in (20) contributes

$\ll c_{f}x_{0}\eta\delta e^{-(\log x_{0})^{\beta}}\ll
C_{5}\frac{c_{f}x_{0}}{d}$

so upon rearranging we may delete this term from (21). From the definition of
$\sigma_{-}$, we thus get

$c_{f}\frac{x_{0}}{d}\gg\sum_{n\leq x_{0}}g(n)\gg c_{f}x_{0}\eta\delta\cdot
c_{f}^{-1}\frac{1}{\eta\delta}\rho\left(c_{f}^{-1}\frac{C^{\prime}}{\eta\delta}\right)\gg
x_{0}\rho\left(c_{f}^{-1}\frac{C^{\prime}}{\eta\delta}\right).$

Since $f\in\mathcal{M}_{1}(x_{0};d)$ by assumption we have $c_{f}\gg 1$,
whence we deduce that

$d\ll\rho(\tfrac{C^{\prime\prime}}{\eta\delta})^{-1}.$

for some absolute $C^{\prime\prime}>0$. Choosing $C_{1},C_{2}>0$ large enough,
we obtain a contradiction whenever $d\geq
C_{1}\rho\Big{(}\tfrac{C_{2}}{\eta\delta}\Big{)}$, and part (a) follows.
(b) When $d\geq C_{5}(\eta\delta)^{-1}e^{(\log x)^{\beta}}$ and $f=\chi$ is a
primitive character modulo a prime $q$ of order $d$ (taking
$x_{0}=q^{3/2+\varepsilon}$, say) we apply Proposition 4.1 with any
$c\in(\beta,1)$ to deduce that

$\sum_{\begin{subarray}{c}p\leq x\\\ \chi(p)\neq
0,1\end{subarray}}\frac{1}{p}\geq\sum_{\begin{subarray}{c}p\leq q\\\
\chi(p)\neq
1\end{subarray}}\frac{1}{p}-\log(1/\delta)+O(1)\geq(\beta-o(1))\log\log
q-\log(1/\delta).$

Since $\log(1/(\eta\delta))\leq c\log\log q$ for some $0<c<\beta$ we may lower
bound this last expression by

$\geq\log(1/\eta)+\Big{(}(\beta-o(1))\log\log
q-\log(1/\eta\delta)\Big{)}\geq\log(1/\eta)$

for large enough $q$, and the claim follows. ∎

###### Proof of Theorem 2.

We may assume that $d$ is larger (and thus $\delta$ is smaller) than any fixed
constant, otherwise $G(d)\ll 1$ and the claimed bound is trivial.
Taking $x_{0}=q^{3/2+\varepsilon}$ we have $\chi\in\mathcal{M}_{1}(x_{0};d)$.
Let $\eta=\delta$ and $0<c_{2}<c_{3}/2$, so that $\eta\delta>(\log q)^{-c}$
for some $c\in(0,c_{3})$. Taking $c_{2}>0$ smaller if needed we find, using
(5) that $d\geq C_{1}\rho(C_{2}/(\eta\delta^{\prime}))$ with
$\delta^{\prime}:=2\delta/3$, given that $1/\delta^{2}\ll c_{2}^{2}\frac{\log
d}{\log\log d}$. As in the proof of Theorem 1 we have

$\log(1/\eta)\gg\log\log d,$

and so by Theorem 1.1(b),

$\sum_{\begin{subarray}{c}p\leq x\\\ \chi(p)\neq
0,1\end{subarray}}\frac{1}{p}\geq\log(1/\eta)\gg\log\log d$

for $x>q^{\delta}$. Therefore,

$\Sigma=\min\Big{\\{}P^{-}(d),2+\sum_{\begin{subarray}{c}p\leq x\\\
\chi(p)\neq 0,1\end{subarray}}p^{-1}\Big{\\}}\gg G(d).$

The conclusion of the theorem now follows from Theorem 1.2. ∎

##  5\. Improvements to Pólya-Vinogradov on Average

Let $\varepsilon>0$ and let $\chi$ be a primitive character of order $d$
modulo a prime $q$. We define

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

To prove Theorem 3 we will show, using work of Granville and Soundararajan
[13], that the iterated sumsets of $\Xi_{d}(\varepsilon)$ satisfy rigid
conditions; see Lemma 5.3 below. As it turns out, this rigidity puts limits on
$|\Xi_{d}(\varepsilon)|$, at least when $d$ has no small prime factors.

######  Proposition 5.1.

There is an absolute constant $C>0$ such that if $k\geq 1$ and $\varepsilon>0$
satisfies $\varepsilon\geq C(\log q)^{-\tfrac{1}{3(2k+1)^{2}}}$ then

$|\Xi_{d}(\varepsilon)|\ll d\left(\frac{1}{k}+\frac{1}{P^{-}(d)}\right).$

To prove Proposition 5.1 we will need a slight extension of [13, Thm. 2],
which makes more precise the dependence on the number of characters in the
case that this grows with $q$.

######  Lemma 5.2.

Let $q\geq 3$ be large and let $3\leq g\leq\frac{\log\log q}{\log\log\log q}$
be odd. There is an absolute constant $C_{0}>0$ such that the following holds.
Let $\chi_{1},\ldots,\chi_{g}$ be primitive characters with respective
conductors $q_{j}\leq q$ and for which

$M(\chi_{j})>\sqrt{q_{j}}(\log q_{j})^{1-1/g}\text{ for all }1\leq j\leq g.$

Suppose in addition that $\chi_{1}\cdots\chi_{g}$ is trivial. Then as
$q\rightarrow\infty$,

$\prod_{1\leq j\leq g}\frac{M(\chi_{j})}{\sqrt{q_{j}}\log q}\leq
C_{0}^{g}(\log q)^{-\frac{1+o(1)}{2g}}.$

###### Proof.

By [10, Prop. 3], there is an absolute constant $A>0$ such that for each
$1\leq j\leq g$ there are:

  1. (i)

a primitive character $\xi_{j}\pmod{m_{j}}$ with $m_{j}\leq(\log
q)^{\tfrac{2}{g}}(\log\log q)^{4}$ and $\xi_{j}(-1)=-\chi_{j}(-1)$; and

  2. (ii)

a scale $1\leq N_{j}\leq q_{j}$, such that

$M(\chi_{j})\leq A\frac{\sqrt{q_{j}m_{j}}}{\phi(m_{j})}\left|\sum_{n\leq
N_{j}}\frac{\chi_{j}\overline{\xi}_{j}(n)}{n}\right|.$

By [13, Lem. 4.3], there is an absolute constant $B>0$ such that

$\left|\sum_{n\leq N_{j}}\frac{\chi_{j}\overline{\xi}_{j}(n)}{n}\right|\leq
B(\log N_{j})e^{-\frac{1}{2}\mathbb{D}(\chi_{j},\xi_{j};N_{j})^{2}}\leq B(\log
q)e^{-\frac{1}{2}\mathbb{D}(\chi_{j},\xi_{j};q)^{2}},$

using in the last step the fact that for any sequence
$\\{f(p)\\}_{p}\subset\mathbb{U}$ the map

$t\mapsto\sum_{p\leq t}\frac{2-(1-\text{Re}(f(p)))}{p}$

is non-decreasing. Choosing $D\geq 1$ absolute so that $\sqrt{m}\leq D\phi(m)$
for all $m\geq 1$ and then setting $C_{0}:=ABD$, we deduce that

$\frac{M(\chi_{j})}{\sqrt{q_{j}}\log q}\leq
C_{0}e^{-\frac{1}{2}\mathbb{D}(\chi_{j},\xi_{j};q)^{2}}.$

Taking the product over $1\leq j\leq g$ and using the inequality

$\sum_{1\leq j\leq
g}\mathbb{D}(\chi_{j},\xi_{j};q)^{2}\geq\frac{1}{g}\mathbb{D}(1,\xi_{1}\cdots\xi_{g};q)^{2}$

from the proof of [13, Lem. 3.3], we thus obtain

(22) $\prod_{1\leq j\leq g}\frac{M(\chi_{j})}{\sqrt{q_{j}}\log q}\leq
C_{0}^{g}e^{-\frac{1}{2g}\mathbb{D}(1,\xi_{1}\cdots\xi_{g};q)^{2}}.$

Set now $\xi:=\xi_{1}\cdots\xi_{g}$, which is non-trivial since
$\xi(-1)=(-1)^{g}\chi_{1}\cdots\chi_{g}(-1)=-1$. The conductor of $\xi$ is

$M:=[m_{1},\ldots,m_{g}]\leq m_{1}\cdots m_{g}\leq(\log q)^{2}(\log\log
q)^{4g}\leq(\log q)^{6},$

by our hypothesis on $g$. Thus, by the Siegel-Walfisz theorem (as in e.g. [13,
(3.1)]) we obtain

$\displaystyle\mathbb{D}(1,\xi;q)^{2}$ $\displaystyle\geq\sum_{M<p\leq
q}\frac{1-\text{Re}(\xi(p))}{p}\geq\sum_{\begin{subarray}{c}a\pmod{M}\\\
(a,M)=1\end{subarray}}(1-\text{Re}(\xi(a)))\sum_{\begin{subarray}{c}M<p\leq
q\\\ p\equiv a\pmod{M}\end{subarray}}\frac{1}{p}$
$\displaystyle=\frac{1+o(1)}{\phi(M)}\left(\phi(M)-\text{Re}\left(\sum_{a\pmod{M}}\xi(a)\right)\right)\log\log
q$ $\displaystyle=(1+o(1))\log\log q.$

We hence deduce from (22) that as $q\rightarrow\infty$,

$\prod_{1\leq j\leq g}\frac{M(\chi_{j})}{\sqrt{q_{j}}\log q}\leq
C_{0}^{g}(\log q)^{-\frac{1}{2g}(1+o(1))},$

as claimed. ∎

######  Lemma 5.3.

Let $\varepsilon>0$ and write $A:=\Xi_{d}(\varepsilon)$. There is an absolute
constant $C\geq 1$ such that whenever $k\geq 1$ and $\varepsilon\geq C(\log
q)^{-\tfrac{1}{3(2k+1)^{2}}}$,

$2kA\cap A=\emptyset.$

###### Proof.

Suppose for the sake of contradiction that $a\in 2kA\cap A$. Then we can write

$a_{1}+\cdots+a_{2k}-a\equiv 0\pmod{d},\quad a_{j}\in A\text{ for all }1\leq
j\leq 2k.$

Since $0\notin A$ and $q$ is prime, it follows also that $\chi^{a_{j}}$,
$\overline{\chi}^{a}$ are all primitive, and $\overline{\chi}^{a}\prod_{1\leq
j\leq 2k}\chi^{a_{j}}$ is trivial. For convenience, write
$a_{2k+1}\equiv-a\pmod{d}$, noting that
$M(\chi^{a_{2k+1}})=M(\overline{\chi}^{a})$.
Since $\varepsilon\log q\geq(\log q)^{1-1/(2k+1)}$, Lemma 5.2 yields

$\prod_{1\leq j\leq 2k+1}\frac{M(\chi^{a_{j}})}{\sqrt{q}\log q}\leq
C_{0}^{2k+1}(\log q)^{-\frac{1+o(1)}{2(2k+1)}}.$

On the other hand, since $a_{j}\in A$ for all $1\leq j\leq 2k+1$ (as $A$ is
symmetric), we obtain

$\prod_{1\leq j\leq 2k+1}\frac{M(\chi^{a_{j}})}{\sqrt{q}\log
q}\geq\varepsilon^{2k+1}\geq C^{2k+1}(\log q)^{-\tfrac{1}{3(2k+1)}},$

which is a contradiction whenever $C$ and $q$ are large enough. The claim
follows. ∎

Let $G$ be a finite Abelian group, written additively. For $k,\ell\geq 1$ we
say that $A\subseteq G$ is a _$(k,\ell)$ -set_ if $kA\cap\ell A=\emptyset$.
Lemma 5.3 shows that, under the claimed constraints on $k$ and $\varepsilon$,
$\Xi_{d}(\varepsilon)$ is a $(2k,1)$-set. It is clear that if $B\subseteq A$
and $A$ is a $(k,\ell)$-set then $B$ is also a $(k,\ell)$-set, so that
$(k,\ell)$-sets form a partially-order set under inclusion. We say that $A$ is
a _maximal $(k,\ell)$-set_ if $A$ is maximal with respect to this partial
order.

######  Theorem (Bajnok [1], Thm. 3; Hamidoune-Plagne [15], Thm. 2.4).

Let $k,\ell,n\geq 1$ with $k\neq\ell$. Suppose $G=\mathbb{Z}/n\mathbb{Z}$, and
let $A\subseteq G$ be a maximal $(k,\ell)$-set. Then

$|A|\leq\max_{f|n}\frac{n}{f}\left(1+\left\lfloor\frac{f-2}{k+\ell}\right\rfloor\right).$

###### Proof of Proposition 5.1.

By Lemma 5.3, it follows that $\Xi_{d}(\varepsilon)$ is contained inside of a
maximal $(2k,1)$-set, and so by the Bajnok-Hamidoune-Plagne theorem we obtain

$|\Xi_{d}(\varepsilon)|\leq\max_{f|d}\frac{d}{f}\left(1+\left\lfloor\frac{f-2}{2k+1}\right\rfloor\right).$

Note that when $f=1$ the term inside the floor function is
$-1/(2k+1)\in[-1,0)$, and so the expression is $0$. It follows that

$|\Xi_{d}(\varepsilon)|\leq d\max_{\begin{subarray}{c}f|d\\\
f>1\end{subarray}}\left(\frac{1}{f}+\frac{1}{2k+1}\right);$

the RHS is maximized at the smallest divisor of $d$ greater than 1, which is
$P^{-}(d)$, and the claim follows. ∎

###### Proof of Theorem 3.

Let $\varepsilon>0$ and $k\geq 1$ be parameters to be chosen later. Splitting
the sum over $j$ according to whether or not $j\in\Xi_{d}(\varepsilon)$,
Proposition 5.1 implies that

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

as long as $\varepsilon\geq C(\log q)^{-\tfrac{1}{3(2k+1)^{2}}}$. Taking
$k:=\left\lfloor\frac{1}{10}\sqrt{\frac{\log\log q}{\log\log\log
q}}\right\rfloor$ and letting $\varepsilon:=C(\log
q)^{-\frac{1}{3(2k+1)^{2}}}\leq C(\log\log q)^{-\tfrac{1}{2}}$, we obtain the
claimed bound. ∎

###### Proof of Corollary 4.

Note that since $d\geq 3$ is prime, $\chi^{\ell}$ has odd order $d$ for all
$\ell\not\equiv 0\pmod{d}$. Applying Lemma 5.2 with $\chi_{j}=\chi^{\ell}$ for
all $1\leq j\leq d$, we obtain (whether or not
$M(\chi^{\ell})\leq\sqrt{q}(\log q)^{1-1/d}$)

$M(\chi^{\ell})=\left(\prod_{1\leq j\leq d}\frac{M(\chi_{j})}{\sqrt{q}\log
q}\right)^{\frac{1}{d}}\sqrt{q}\log q\leq C_{0}(\sqrt{q}\log q)(\log
q)^{-\tfrac{1+o(1)}{2d^{2}}}$

for each $1\leq\ell\leq d-1$. Combined with Theorem 3, as $q\rightarrow\infty$
this gives

$\frac{1}{d}\sum_{1\leq\ell\leq d-1}M(\chi^{\ell})\ll(\sqrt{q}\log
q)\min\\{(\log q)^{-\tfrac{1}{3d^{2}}},\left(\frac{\log\log\log q}{\log\log
q}\right)^{1/2}+\frac{1}{d}\\}.$

The transition point in these bounds occurs for $d\asymp\sqrt{\frac{\log\log
q}{\log\log\log q}}$, and with a suitable implicit constant the claimed upper
bound follows. ∎

######  Remark 8.

Let $K:=\left\lfloor\sqrt{\frac{\log\log
q}{100\log(1/\varepsilon)}}\right\rfloor$, and for each $1\leq k\leq K$ let
$A_{k}\subseteq\mathbb{Z}/d\mathbb{Z}$ be a maximal $(2k,1)$-set that contains
$\Xi_{d}(\varepsilon)$. The work of Bajnok and Hamidoune-Plagne stated above
establishes an upper bound for each $|A_{k}|$, and therefore also for the
rightmost expression in the chain of inequalities

(23) $|\Xi_{d}(\varepsilon)|\leq|\bigcap_{1\leq k\leq K}A_{k}|\leq\min_{1\leq
k\leq K}|A_{k}|.$

It is reasonable to ask whether there could be a substantial difference in
size between the intersection of the $A_{k}$ and the minimal $|A_{k}|$.
However, since any symmetric set satisfies $(2k)A\subseteq(2k+2)A$ (since we
can augment any $k$-fold sum

$a_{1}+\cdots+a_{k}=a_{1}+\cdots+a_{k}+a^{\prime}+(-a^{\prime})$

for $a^{\prime}\in A$), it follows that any $(2(k+1),1)$-set is also a
$(2k,1)$-set, and it is possible therefore that $A_{k+1}\subseteq A_{k}$,
i.e., the sums are nested. In such an event, the latter inequality in (23) is
sharp.

## References

  * [1] B. Bajnok.  On the maximum size of a $(k,l)$-sum-free subset of an Abelian group.  Int. J. Number Theory, 5(6):953–971, 2009.
  * [2] J. W. Bober and L. Goldmakher.  Pólya-Vinogradov and the least quadratic nonresidue.  Math. Ann., 366:853–863, 2016.
  * [3] D.A. Burgess.  On character sums and primitive roots.  Proc. Lond. Math. Soc., 12(3):179–192, 1962.
  * [4] G.A. Freiman.  Groups and the inverse problems of additive number theory.  In Number-theoretic studies in the Markov spectrum and in the structural theory of set addition (Russian), pages 175–183. Kalinin. Gos. Univ., Moscow, 1973.
  * [5] J.B. Friedlander.  Integers free from large and small primes.  Proc. Lond. Math. Soc., 33(3):565–576, 1976.
  * [6] E. Fromm and L. Goldmakher.  Improving the Burgess bound via Pólya-Vinogradov.  Proc. Amer. Math. Soc., 147:461–466, 2019.
  * [7] L. Goldmakher.  Multiplicative mimicry and improvements of the Pólya-Vinogradov inequality.  Algebra Number Theory, 6(1):123–163, 2012.
  * [8] L. Goldmakher and Y. Lamzouri.  Large even order character sums.  Proc. Amer. Math. Soc., 142:2609–2614, 2014.
  * [9] A. Granville.  Smooth numbers: computational number theory and beyond.  In Algorithmic number theory: lattices, number fields, curves and cryptography, pages 267–323. Cambridge Univ. Press, vol. 44, Cambridge, 2008\.
  * [10] A. Granville and A.P. Mangerel.  Three conjectures about character sums.  arXiv:2112.12339 [math.NT].
  * [11] A. Granville and K. Soundararajan.  Upper bounds for $|{L}(1,\chi)|$.  Quart. J. Math., 53(3):265–284, 2002.
  * [12] A. Granville and K. Soundararajan.  Decay of mean values of multiplicative functions.  Can. J. Math., 55(6):1191–1230, 2003.
  * [13] 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.
  * [14] A. Granville and K. Soundararajan.  Large character sums: Burgess’ theorem and zeros of $L$-functions.  J. Euro. Math. Soc., 20(1):1–14, 2018.
  * [15] Y.o. Hamidoune and A. Plagne.  A new critical pair theorem applied to sum-free sets in Abelian groups.  Comment. Math. Helv., 79:183–207, 2004.
  * [16] A. Hildebrand.  A note on Burgess’ character sum estimate.  C.R. Math. Acad. Sci. Can., 8(1):35–37, 1986.
  * [17] A. Hildebrand.  Quantitative mean value theorems for nonnegative multiplicative functions II.  Acta Arith., 48:209–260, 1987.
  * [18] H. Iwaniec and E. Kowalski.  Analytic Number Theory.  AMS Colloquium Publications vol. 53, Providence, RI, 2004.
  * [19] 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.
  * [20] A.P. Mangerel.  Short character sums and the Pólya-Vinogradov inequality.  Quart. J. Math., 71(4):1281–1308, 2020.
  * [21] H.L. Montgomery and R.C. Vaughan.  Exponential sums with multiplicative coefficients.  Invent. Math., 43:69–82, 1977.
  * [22] K. K. Norton.  Numbers with small prime factors and the least $k$th power non-residue.  Memoirs of the AMS, 106, 1971.
  * [23] K.K. Norton.  A character sum estimate and applications.  Acta Arith., 85(1):51–78, 1998.
  * [24] R.E.A.C. Paley.  A theorem on characters.  J. London. Math. Soc., 7:28–32, 1932.
  * [25] I.Z. Ruzsa.  On the concentration of additive functions.  Acta Math. Acad. Sci. Hung., 36:215–232, 1980.
  * [26] G. Tenenbaum.  Introduction to Analytic and Probabilistic Number Theory.  Graduate Studies in Mathematics vol. 163, AMS Publications, Providence, RI, 2015.
  * [27] A. Walker.  A multiplicative analogue of Schnirelmann’s theorem.  Bull. Lond. Math. Soc., 48:1018–1028, 2016.