# Gap problems for integer-valued multiplicative functions

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

Motivated by questions about the typical sizes of gaps $|f(n+1)-f(n)|$ in the
sequence $(f(n))_{n}$, where $f$ is an integer-valued multiplicative function,
we investigate the set of solutions

$\\{n\in\mathbb{N}:f(n+a)=f(n)+b\\},\quad ab\neq 0.$

We formulate a conjecture classifying those multiplicative functions for which
this set has logarithmic density zero, and prove that the conjectured
classification is tight. Moreover, using techniques from additive
combinatorics building on previous work of the author, we show how to reduce
the classification problem to the study of _local power maps_ modulo prime
$\ell$, i.e., maps $g:\mathbb{N}\rightarrow\mathbb{Z}$ for which there is
$0\leq k_{\ell}<\ell-1$ such that

$g(n)\equiv n^{k_{\ell}}\pmod{\ell}\text{ for all }n\in\mathbb{N}.$

We prove a partial result towards our classification conjecture by employing a
strategy of N. Jones that uses Kummer theory to study local power maps modulo
many primes $\ell$.

##  1\. Introduction and Main Results

###  1.1. Motivation

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a multiplicative function that
takes positive integer values. It is natural to speculate about the growth and
distribution of the sequence of gaps $(|f(n+1)-f(n)|)_{n}$. Heuristics about
the independence of multiplicative and additive structure in integers suggests
that _unless $f$ has very rigid properties_ the following should hold true:

(1) if $f(n)\rightarrow\infty$ as $n\rightarrow\infty$ a.e. then
$|f(m+1)-f(m)|\rightarrow\infty$ as $m\rightarrow\infty$ a.e.

Conversely, if $|f(n+1)-f(n)|$ is bounded on a set of positive upper density
then we would expect that either:

  1. (i)

$f$ is bounded on a set of positive upper density, or

  2. (ii)

$f$ exhibits _rigid_ behaviour (to be made more precise shortly).

Problems relating to the sequence of gaps $|f(n+1)-f(n)|$ of a multiplicative
function $f:\mathbb{N}\rightarrow\mathbb{C}$ has inspired many interesting
previous works in the literature. For example, Kátai [10] conjectured that if
$|f(n+1)-f(n)|\rightarrow 0$ as $n\rightarrow\infty$ then $f(n)=n^{it}$ for
some $t\in\mathbb{R}$, a result that was proven by Wirsing (see the joint
paper [27]). On the basis of a conjecture of Erdős [2] about the average gaps
in the sequence of an additive function, Kátai [10] also conjectured that if,
as $x\rightarrow\infty$,

$\frac{1}{x}\sum_{n\leq x}|f(n)|\gg 1\text{ and }\frac{1}{x}\sum_{n\leq
x}|f(n+1)-f(n)|=o(1)$

then $f(n)=n^{s}$ for some $s\in\mathbb{C}$ with $\text{Re}(s)<1$, a result
that was more recently proved by Klurman [12]. In the other direction, Klurman
and the author [13], addressing a folklore conjecture, proved that if
$f:\mathbb{N}\rightarrow\mathbb{C}$ is completely multiplicative and takes
values on the unit circle then

$\liminf_{n\rightarrow\infty}|f(n+1)-f(n)|=0.$

In contrast to Kátai’s problems mentioned above, which address the “99%”
problem of when the gaps are _small for almost all_ $n$, our interest in this
paper is to understand the more challenging “1%” variant of this problem,
namely when the gaps are _bounded on a positive upper density set_.
It is certainly true that there are multiplicative functions for which (1)
does not hold. The simplest such example is to take the monomial $f(n)=n$, so
that $|f(n+1)-f(n)|=1$ for all $n$. This example can be generalised readily in
various ways.

######  Example 1.1.

Let $S$ be a set of odd primes that is _sparse_ in the sense that

$\sum_{p\in S}\frac{1}{p}<\infty.$

Let $p_{1},p_{2}\notin S$ be fixed primes and let $b\in\mathbb{N}$. Define a
completely multiplicative function $f$ at primes $p$ by

$f(p):=\begin{cases}p&\text{ if $p\notin S\cup\\{p_{1},p_{2}\\}$}\\\ bp&\text{
if $p\in\\{p_{1},p_{2}\\}$}\\\ 1&\text{ if $p\in S$.}\end{cases}$

Then whenever $n$ is chosen so that $p_{1}||n$, $p_{2}||(n+1)$ and so that
$n(n+1)$ has no prime factors from $S$, then $f(n+1)=f(n)+b$. Indeed,

$f(n)=bp_{1}\cdot\frac{n}{p_{1}}=bn,\quad
f(n+1)=bp_{2}\cdot\frac{n+1}{p_{2}}=bn+b,$

Using a zero-dimensional sieve it can easily be shown that this occurs for a
set of $n\in\mathbb{N}$ with natural density

$\frac{1}{p_{1}p_{2}}\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right)\prod_{p\in
S}\left(1-\frac{2}{p}\right)>0.$

Such examples are all morally similar in that $p|f(p)$ outside of a sparse set
of primes, and that for generic primes $p$ we more precisely have $f(p)=p$, as
in the .
As an application of the more general results in this paper (discussed in the
next subsection), we have the following consequence. In the statement, given a
set $A\subseteq\mathbb{N}$ we write

$dA:=\lim_{x\rightarrow\infty}\frac{|A\cap[1,x]|}{x},\quad\delta
A:=\lim_{x\rightarrow\infty}\frac{1}{\log x}\sum_{n\in
A\cap[1,x]}\frac{1}{n},$

whenever the limits exist.

######  Corollary 1.2.

Assume the222By the ERH we mean that for each number field $K/\mathbb{Q}$ the
Dedekind zeta function $\zeta_{K}$ of $K$ has no zeros in the half-plane
$\text{Re}(s)>1/2$. In fact, we do not need the full strength of this
hypothesis; see Remark 1.7 for a relevant discussion of this. Extended Riemann
Hypothesis. Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a multiplicative
function, such that

$d\\{n\in\mathbb{N}:|f(n)|\leq C\\}=0\text{ for all }C>0.$

Then either

$\delta\\{n\in\mathbb{N}:|f(n+1)-f(n)|\leq C\\}=0\text{ for all }C>0,$

or else precisely one of

(2) $\sum_{p|f(p)}\frac{1}{p}\text{ and }\sum_{f(p)\neq p}\frac{1}{p}$

converges.

We will deduce Corollary 1.2 from Theorem 1.6 below, in Section 8.

######  Remark 1.3.

We expect that the first alternative still holds even when
$\sum_{p|f(p)}1/p<\infty$ in (2), but are unable to prove it at present. We
leave this as an open problem to the interested reader.

###  1.2. Inhomogeneous problems relating shifted values of $f$

In proving Corollary 1.2 we are naturally led to the following general
problem.

######  Problem 1.4.

Let $a,b,A,B\in\mathbb{Z}$ with $aAB\neq 0$. Classify those multiplicative
functions $f:\mathbb{N}\rightarrow\mathbb{C}$ for which the set

(3) $\mathcal{N}_{f,a,b;A,B}:=\\{n\in\mathbb{N}:Af(n+a)=Bf(n)+b\\}$

satisfies333This statement should be understood as including the possibility
that $\delta\mathcal{N}_{f,a,b;A,B}$ does not exist.
$\delta\mathcal{N}_{f,a,b;A,B}\neq 0$.

In this paper we are especially concerned with the case where $A=B=1$ and
$b\neq 0$. Our work extends the classification theorems for complex-valued
multiplicative functions that was undertaken in [19], where we treated the
case $b=0$ and arbitrary non-zero $A,B$. The main result of that paper, [19,
Thm. 1.1], showed (in slightly more generality) that for any multiplicative
function $f:\mathbb{N}\rightarrow\mathbb{C}$ _at least one_ of the following
events must occur:

  1. (i)

the set of primes $\\{p:|f(p)|\neq 1\\}$ is _sparse_ in the sense that

$\sum_{p:|f(p)|\neq 1}\frac{1}{p}<\infty;$

  2. (ii)

for any non-zero integers $a,A,B$ the set

$\mathcal{N}_{f,a;A,B}^{\prime}:=\\{n\in\mathbb{N}:Af(n+a)=Bf(n)\neq 0\\}$

satisfies $\delta\mathcal{N}_{f,a;A,B}^{\prime}=0$.

It is not hard to show (see Lemma 8.2 below) that (i) occurs whenever $|f(n)|$
is bounded on a set of positive natural density, and thus $|f(n)|\to\infty$
_does not_ hold a.e. In view of the discussion in the previous section such
functions will be of little interest to us, and in the sequel we will on
occasion refer to these examples as _essentially bounded_. Thus, [19, Thm.
1.1] shows that if $f:\mathbb{N}\rightarrow\mathbb{C}$ is multiplicative and
_not_ essentially bounded, $\delta\mathcal{N}_{f,a;A,B}^{\prime}=0$ whenever
$aAB\neq 0$. We focus in this paper on characterising the set
$\mathcal{N}_{f,a,b;A,B}$ when $b\neq 0$ and $f$ takes _integer values_. In
contrast to the case $b=0$ the non-vanishing condition $f(n)f(n+a)\neq 0$ may
be removed.
In the remainder of the paper we will focus on the case $A=B=1$, though with
only minor modifications the same techniques may be applied to study the
general case $AB\neq 0$. In the sequel, therefore, given
$a,b\in\mathbb{Z}\backslash\\{0\\}$ and an arithmetic function
$f:\mathbb{N}\rightarrow\mathbb{Z}$ we abbreviate for convenience

$\mathcal{N}_{f,a,b}:=\mathcal{N}_{f,a,b;1,1}=\\{n\in\mathbb{N}:f(n+a)=f(n)+b\\}.$

###  1.3. Classifying examples for the inhomogeneous problem

Extending Example 1.1, it is not difficult to find
$f:\mathbb{N}\rightarrow\mathbb{Z}$ such that $f(n+a)=f(n)+b$, whenever $a|b$.
Indeed, let $a,b\in\mathbb{Z}\backslash\\{0\\}$ with $a|b$. Let $p_{1},p_{2}$
be distinct primes with $(p_{1}p_{2},a)=1$, and let $S$ be a sparse set of odd
primes not including $p_{1},p_{2}$. Then the completely multiplicative
function $f:\mathbb{N}\rightarrow\mathbb{Z}$ defined at primes via

$f(p)=\begin{cases}p&\text{ if }p\notin S\cup\\{p_{1},p_{2}\\}\\\ pb/a&\text{
if }p\in\\{p_{1},p_{2}\\}\\\ 1&\text{ if }p\in S,\end{cases}$

then $f(n+a)=f(n)+b$ whenever444In the sequel, given a set of primes $T$ we
write $(m,T)=1$ to mean that $p|m\Rightarrow p\notin T$.

$n\in\\{am\in\mathbb{N}:p_{1}||m,\,p_{2}||(m+1),(n(n+a),S)=1\\}.$

Once again, this set may be shown to have positive density

$\frac{1}{ap_{1}p_{2}}(1-1/p_{1})(1-1/p_{2})\prod_{p\in
S}\left(1-\frac{2}{p}\right).$

The classification problem for the inhomogeneous case therefore admits many
possible examples. The following conjecture gives a precise description of all
of these.

######  Conjecture 1.5.

Let $f:\mathbb{N}\rightarrow\mathbb{Z}$ be a multiplicative function that
satisfies

(4) $\sum_{p:|f(p)|\neq 1}\frac{1}{p}=\infty.$

Suppose $\delta(\mathcal{N}_{f,a,b})\neq 0$ for some non-zero
$a,b\in\mathbb{Z}$. Then the set $\mathcal{E}_{f}:=\\{p:|f(p)|\neq p\\}$
satisfies

$\sum_{p\in\mathcal{E}_{f}}\frac{1}{p}<\infty.$

Moreover, if $f$ is completely multiplicative then there is a divisor $d$ of
$a$ such that

$f(d)\mid b\text{ and }(a/d)\mid(b/f(d)).$

###  1.4. Partial result towards Conjecture 1.5

We give evidence towards Conjecture 1.5 by proving that its conclusion holds
for a non-trivial collection of multiplicative functions, which we motivate
presently.
According to Conjecture 1.5, any integer-valued multiplicative function $f$
which is not essentially bounded and for which
$\delta(\mathcal{N}_{f,a,b})\neq 0$ for some $a,b\in\mathbb{Z}$ non-zero must
necessarily satisfy $p|f(p)$ outside of a sparse set of primes $p$. It turns
out that the condition that $p|f(p)$ for “sufficiently many” $p$ is also
sufficient to showing that $f$ satisfies Conjecture 1.5.
Let $\mathcal{P}$ denote the set of all primes. To state our result, recall
that the _Dirichlet density_ of a set of primes
$\mathcal{S}\subseteq\mathcal{P}$, if it exists, is defined as

$d_{\text{Dir}}(\mathcal{S}):=\lim_{X\rightarrow\infty}\frac{1}{\log\log
X}\sum_{\begin{subarray}{c}p\leq X\\\
p\in\mathcal{S}\end{subarray}}\frac{1}{p}>0.$

######  Theorem 1.6.

Let $f:\mathbb{N}\rightarrow\mathbb{Z}$ be a multiplicative function. Assume
one of the following conditions555It is easily seen that if either (a) or (b)
holds then so does (4). holds:

  1. (a)

$d_{\text{Dir}}(\\{p\in\mathcal{P}:p|f(p)\\})>0$, or

  2. (b)

the Extended Riemann Hypothesis holds, and $\sum_{p|f(p)}p^{-1}=\infty$.

Suppose that $\delta(\mathcal{N}_{f,a,b})\neq 0$ for some pair of
$a,b\in\mathbb{Z}$ non-zero. Then the set $\mathcal{E}_{f}:=\\{p:|f(p)|\neq
p\\}$ satisfies

$\sum_{p\in\mathcal{E}_{f}}\frac{1}{p}<\infty.$

Moreover, if $f$ is completely multiplicative then there is a divisor $d$ of
$a$ such that

$f(d)\mid b\text{ and }(a/d)\mid(b/f(d)).$

######  Remark 1.7.

In fact, our arguments yield something slightly stronger than this. Define

$S_{f}:=\\{p\in\mathcal{P}:p|f(p)\\}.$

Then the unconditional conclusion of Theorem 1.6 holds as long as

$\sum_{\begin{subarray}{c}p\leq X\\\ p\in
S_{f}\end{subarray}}\frac{1}{p}\gg_{\varepsilon}(\log\log
X)^{1/2+\varepsilon},\quad X\rightarrow\infty.$

Moreover, we do not need the full strength of the Extended Riemann Hypothesis
in our conditional result either. Indeed, it suffices for a version of RH to
hold for the Dedekind zeta functions of an infinite family of Kummer
extensions. Moreover, a narrow zero-free region of Vinogradov-Korobov type
would also suffice. See Section 6.2 below for relevant details, and for
remarks regarding the quality of sufficient zero-free regions for this
problem. See also Remark 7.1 below for a discussion related to whether
considerations about $S_{f}$ are necessary in this problem.

###  1.5. A converse result

At first glance the conclusion of Conjecture 1.5 appears rather flexible, and
one might ask whether it could possibly be strengthened. We prove, however,
that the classification proposed in Conjecture 1.5 is tight. In particular:

  1. (i)

the exceptional set $\mathcal{E}_{f}$ can essentially be arbitrary,

  2. (ii)

the signs $f(p)/p$ for $p\notin\mathcal{E}_{f}$ are not significantly
restricted, and

  3. (iii)

the divisibility conditions given on $a$ and $b$ are necessary.

######  Proposition 1.8.

Let $a\in\mathbb{Z}$ be non-zero, let $d|a$ and let $b\neq a/d$ be an integer
multiple of $a/d$. Let $\mathcal{S}$ be a set of odd primes that satisfies

$\\{p\in\mathcal{P}:p|d\\}\subseteq\mathcal{S},\quad|\mathcal{S}\backslash\\{p\in\mathcal{P}:p|d\\}|\geq
2\text{ and }\sum_{p\in\mathcal{S}}\frac{1}{p}<\infty.$

Then there are uncountably many sets
$\mathcal{T}\subseteq\mathcal{P}\backslash\mathcal{S}$ with
$\sum_{p\in\mathcal{T}}p^{-1}=\infty$ for which a completely multiplicative
function $f=f_{\mathcal{T}}:\mathbb{N}\rightarrow\mathbb{Z}$ may be
constructed with the following properties:

  1. (i)

for each $p\notin\mathcal{S}$,

$f(p)=\begin{cases}-p&\text{ if }p\in\mathcal{T}\\\ p&\text{ if
}p\notin\mathcal{T},\end{cases}$

  2. (ii)

for each $p\in\mathcal{S}$, $|f(p)|\neq p$,

  3. (iii)

$f(d)|b$ and $(a/d)|(b/f(d))$, and

  4. (iv)

$\delta(\mathcal{N}_{f,a,b})\neq 0$.

When $\mathcal{T}=\emptyset$ there also exists a corresponding function
$f=f_{\emptyset}$ that satisfies the properties (i)-(iv).

######  Remark 1.9.

We highlight in passing the following relationship that our results bear with
Diophantine equations. Observe first of all that for any $d\geq 1$ the
function $f^{d}$ is integer-valued and multiplicative whenever $f$ is. We may
thus view $\mathcal{N}_{f^{d},a;A,B}^{\prime}$ as the locus of non-zero
solutions in $(X,Y)=(f(n),f(n+a))$ to the diagonal binary homogeneous equation

$AX^{d}-BY^{d}=0,\quad XY\neq 0.$

More generally, if $b\neq 0$ we may consider the corresponding666Naturally,
one might also allow the powers of $X$ and $Y$ here to differ. Similar
analysis applies in that case (treating two different multiplicative functions
$f^{k},f^{\ell}$), so we confine ourselves here to the case that they have the
same power. _inhomogeneous_ binary problems

$AX^{d}-BY^{d}=b$

(here the condition $XY\neq 0$ may be removed). In this direction, Problem 1.4
addresses the classification of multiplicative functions
$f:\mathbb{N}\rightarrow\mathbb{Z}$ for which the corresponding locus of
solutions $\mathcal{N}_{f^{d},a,b;A,B}$ satisfies
$\delta\mathcal{N}_{f^{d},a,b;A,B}\neq 0$. Thus, among integer solutions
$(X,Y)$ to an inhomogeneous binary problem we seek to understand how
frequently such solutions arise in the form $(f(n),f(n+a))$, for some integer
$n$. (We focus here on $d=1$, since the problem for larger $d$ may be studied
in the same way, replacing $f$ by $f^{d}$ as above.)

## Acknowledgments

We would like to thank Oleksiy Klurman for a stimulating conversation about
the contents of this paper, and for his encouragement.

## Notation and Conventions

Throughout the paper, the letters $a,b,d,m,n,k$ denote integers, and $p,\ell$
are reserved for primes.
We write $\mathcal{P}$ to denote the set of all primes.
Given $d\geq 1$ we denote by $\mu_{d}$ the set of $d$th order roots of unity.
We also write

$\mathbb{U}:=\\{z\in\mathbb{C}:|z|\leq 1\\}$

to denote the closed unit disc in the complex plane.
Given a set $\mathcal{A}$ of primes and $n\in\mathbb{N}$ we write
$(n,\mathcal{A})=1$ whenever $p\nmid n$ for all $p\in\mathcal{A}$.
Given a prime $\ell$ and an integer $m$ coprime to $\ell$, we write
$\text{ord}_{\ell}(m)$ to denote the order of $m\pmod{\ell}$ as an element of
the multiplicative group $(\mathbb{Z}/\ell\mathbb{Z})^{\times}$.
Given an integer $q\geq 1$ we write $\Xi_{q}$ to denote the group of Dirichlet
characters $\pmod{q}$. We denote by $\chi_{0}^{(q)}$ (or simply $\chi_{0}$
when the modulus is understood from context) the principal character
$\pmod{q}$. If $q$ is a prime power then we also denote by $\chi_{q}$ a
generator for $\Xi_{q}$.
Given a set of prime powers $\mathcal{S}$ and $n\in\mathbb{N}$ we write

$\omega_{\mathcal{S}}(n):=|\\{p^{\nu}\in\mathcal{S}:p^{\nu}||n\\}|.$

Given a prime $p$ and an integer $n$ we write

$\nu_{p}(n):=\max\\{\nu\geq 1:p^{\nu}|n\\}.$

Given a finite abelian group $(G,+)$, written additively, and given a set
$A\subseteq G$ and an integer $m\geq 1$ we write

$mA:=\\{a_{1}+\cdots+a_{m}:a_{i}\in A\\}$

to denote the _$m$ -fold sumset_ of $A$.
Given $n\in\mathbb{N}$ we write $\phi(n)$ to denote the Euler phi function. We
also write $P^{+}(1):=1$, and for $n>1$ let $P^{+}(n)$ denote the largest
prime factor of $n\in\mathbb{N}$. Finally, we write $d(n)$ to denote the
number of divisors of $n$.
Given a probability space $(\Omega,\mathcal{B},\mathbb{P})$ and a random
variable $X$ on $\Omega$ we write $\mathbb{E}(X)$ to denote the expectation of
$X$.
Finally, the following definitions will be used repeatedly in the sequel.

######  Definition 1.10.

Let $C>0$. We say that a subset $\mathcal{S}$ (finite or infinite) of prime
powers is _$C$ -sparse_ if

$\sum_{p^{\nu}\in\mathcal{S}}\frac{1}{p^{\nu}}\leq C.$

More generally, we say that $\mathcal{S}$ is _sparse_ if there is a $C>0$ for
which it is $C$-sparse.

######  Definition 1.11.

Given a set $\mathcal{A}\subset\mathbb{N}$ the _upper (natural) density_ and
_upper logarithmic density_ of $\mathcal{A}$ are, respectively,

$\overline{d}(\mathcal{A}):=\limsup_{x\rightarrow\infty}\frac{1}{x}|\mathcal{A}\cap[1,x]|,\quad\overline{\delta}(\mathcal{A}):=\limsup_{x\rightarrow\infty}\frac{1}{\log
x}\sum_{n\leq x}\frac{1_{\mathcal{A}}(n)}{n}.$

##  2\. Proof Ideas

###  2.1. Proof strategy for Theorem 1.6

To prove Theorem 1.6 we apply two version of the “projection method”
introduced in [19], namely the “archimedean” variant found there, as well as a
“non-archimedean” variant; see Section 5 for the details. The basic objective
of this method is to obtain information about the distribution of the
(possibly unbounded) sequence $(f(p))_{p}$ by “projecting” $f$ onto the closed
unit disc

$\mathbb{U}:=\\{z\in\mathbb{C}:|z|\leq 1\\}.$

in a way that preserves its multiplicative structure. Specifically, we study a
collection of _bounded_ multiplicative functions of the shape

$|f|_{t}(n):=|f(n)|^{it},\quad f^{\chi}(n):=\chi(f(n)),\quad f(n)\neq 0,$

where $t\in\mathbb{R}$ and $\chi$ is a Dirichlet character, suitably chosen in
each case. The analysis of the functions $|f|_{t}$ will follow swiftly from
the corresponding work done in [19, Sec. 3]. The key novelty of the present
paper concerns our treatment of the compositions $f^{\chi}$. These ideas were
inspired by previous work [18] of the author in the context of studying
partial sums of Dirichlet characters of large order.

The Archimedean argument: As in Section 3 of [19], we use the compositions
$|f|_{t}(n):=|f(n)|^{it}$ (for $f(n)\neq 0$) to probe the magnitude of the
prime values $(|f(p)|)_{p}$. Our main result in that direction, Proposition
4.1, is the exact analogue of [19, Prop. 3.1]. It states that if
$\overline{\delta}(\mathcal{N}_{f,a,b})>\delta$ then there is
$0<r\ll_{\delta}1$ and a $O_{\delta}(1)$-sparse set $\mathcal{S}_{\delta}$ of
primes such that

(5) $|f(p)|/p^{r}\in(1/2,2)\text{ for all }p\notin\mathcal{S}_{\delta}.$

The proof follows the same lines as [19, Prop. 3.1]. The argument there
involved an analysis of those $f$ for which the set of $n$ that satisfies

(6) $f(n)\neq 0\text{ and }\frac{1}{2}<|f(n+a)/f(n)|<2$

has positive upper logarithmic density. For $n\in\mathcal{N}_{f,a,b}$ the
above chain of inequalities holds as long as $|f(n)|>2|b|$. We use the Turán-
Kubilius inequality (Lemma 3.1) and the fact that $|f(p)|\neq 1$ for _many_
primes $p$ to show that $|f(n)|>100|b|$, say, for all but a small subset of
$\mathcal{N}_{f,a,b}$ (see Lemma 4.3). In this way, we are able to apply the
arguments in [19, Sec. 3] to our problem.

The non-Archimedean argument: We use the compositions
$f^{\chi}(n):=\chi(f(n))$, where $\chi$ is a Dirichlet character of suitably
chosen conductor $q$, to obtain information about the distribution of
$(f(p)\pmod{q})_{p}$. We do this for many moduli $q$, which then sheds light
on the global behaviour of $f(p)$, outsider of a sparse set of primes $p$.

#### Shortcomings of the naïve approach

In analogy to the archimedean argument described above, we might study
functions $f$ for which

$\overline{\delta}\\{n\in\mathbb{N}:f(n+a)=f(n)+b\neq 0\\}>\delta$

by considering the implied congruence

$f(n+a)\equiv f(n)+b\pmod{q}$

for well-chosen _large_ primes $q$ that do not divide $f(n)f(n+a)$.
When $b=0$ the orthogonality relation for Dirichlet characters allows us to
relate the solutions to this congruence to averages

$\frac{1}{q-1}\sum_{\chi\pmod{q}}\frac{1}{\log x}\sum_{n\leq
x}\frac{\chi(f(n+a))\overline{\chi}(f(n)+b)}{n}=\frac{1}{q-1}\sum_{\chi\pmod{q}}\frac{1}{\log
x}\sum_{n\leq x}\frac{f^{\chi}(n+a)\overline{f^{\chi}}(n)}{n}.$

Crucially, the summands are of the form $g(n+a)\overline{g}(n)$, where $g$ is
a multiplicative function taking values in $\mathbb{U}$. Given the hypothesis
$\overline{\delta}(\mathcal{N}_{f,a,0})>\delta$, taking $q$ large enough
compared to $\delta$, we may ignore the contribution from the principal
character $\chi_{0}$, leading to a lower bound for the _non-trivial_
correlations

(7) $\max_{\begin{subarray}{c}\chi\pmod{q}\\\
\chi\neq\chi_{0}\end{subarray}}\left|\frac{1}{\log x}\sum_{n\leq
x}\frac{f^{\chi}(n+a)\overline{f^{\chi}}(n)}{n}\right|\gg\delta,$

for $\gg_{\delta}q$ primitive characters $\pmod{q}$. The theory of
correlations of multiplicative functions, specifically Tao’s theorem on binary
correlations of bounded multiplicative functions (see Theorem 3.5) can then be
fruitfully applied to deduce non-trivial information777In fact, this was the
approach taken in a previous version of [19], at least for integer-valued $f$.
It was realised thereafter that the theorem could be proven (in the broader
context of complex-valued functions) simply by bootstrapping the Archimedean
argument involving the compositions $|f|_{t}$. about $f$.
If we try to argue in the same fashion with $b\neq 0$ then the averaged
correlations

$\frac{1}{q-1}\sum_{\chi\pmod{q}}\frac{1}{\log x}\sum_{n\leq
x}\frac{\chi(f(n+a))\overline{\chi}(f(n)+b)}{n}$

arise. Here, the map $n\mapsto\overline{\chi}(f(n)+b)$ is _no longer
multiplicative_ if $q\nmid b$. Since $b$ is fixed and $q$ is meant to be large
as a function of $\delta$, we must have $q\nmid b$. Thus, a direct appeal to
Tao’s theorem is not possible here.
Since $\chi$ is periodic, one could naïvely circumvent this obstacle by
splitting the set of $n$ according to the residue class $f(n)\pmod{q}$ and
then applying orthogonality a second time. This yields

$\frac{1}{(q-1)^{2}}\sum_{\chi,\psi\pmod{q}}\left(\sum_{c\pmod{q}}\psi(c)\overline{\chi}(c+b)\right)\frac{1}{\log
x}\sum_{n\leq x}\frac{f^{\chi}(n+a)\overline{f^{\psi}}(n)}{n}.$

The bracketed sum (which is, up to a simple change of variables, a Jacobi sum)
has absolute value $\sqrt{q}$ whenever $\chi,\psi$ are distinct non-principal
characters. After removing the contributions from the cases that $\chi,\psi$
or $\chi\overline{\psi}$ are principal, we at best obtain the lower
bound888This bound, obtained by the triangle inequality, cannot in general be
improved upon given that the complex arguments of the Jacobi sums of
characters modulo $q$ are known to distribute uniformly on $S^{1}$ by work of
Katz and Zheng [11], and thus are difficult to control.

$\max_{\begin{subarray}{c}\chi,\psi\pmod{q}\\\ \chi\neq\psi\\\
\chi,\psi\neq\chi_{0}\end{subarray}}\left|\frac{1}{\log x}\sum_{n\leq
x}\frac{f^{\chi}(n+a)\overline{f^{\psi}}(n)}{n}\right|\gg\frac{\delta}{\sqrt{q}}.$

For $q=q(x)$ large relative to $\delta$, this lower bound is too small for
existing results about correlations of multiplicative functions to be
effective for general $f$.

#### An alternative strategy

Seeking a different approach, therefore, we observe the following. Suppose
$\ell$ is prime and $n\in\mathcal{N}_{f,a,b}$ satisfies $\ell||n$. Writing
$n=m\ell$ with $\ell\nmid m$, we have

$f(\ell m+a)=f(\ell)f(m)+b.$

Assume further that $(f(\ell),b)=1$, and let $q$ be a prime power that divides
$f(\ell)$. It follows that

(8) $f(\ell m+a)\equiv b\pmod{q}.$

It is this sort of congruence that we capture using the functions
$\\{f^{\chi}\\}_{\chi\pmod{q}}$, rather than $f(n+a)\equiv f(n)+b\pmod{q}$.
Besides avoiding the non-multiplicativity issue discussed earlier, this
approach allows us to bring to bear the quantitative theory of _mean values_
of multiplicative functions (over arithmetic progressions), which is currently
much better understood than that of _correlations_.
In order to apply this idea we use an estimate due to Elliott (see Lemma 3.2
below), which shows that for $X$ large, $\mathcal{N}_{f,a,b}$ contains
approximately the “expected” number of $n$ with $\ell||n$, i.e.,

(9)
$|\\{n\in\mathcal{N}_{f,a,b}:\ell||n\\}\cap[1,X]|\approx\frac{1}{\ell}\left(1-\frac{1}{\ell}\right)|\mathcal{N}_{f,a,b}\cap[1,X]|$

for all but a small set of primes $\ell$ (that may depend on $X$). As
$\overline{\delta}(\mathcal{N}_{f,a,b})>\delta$ we can find an infinite
increasing sequence $(x_{k})_{k}$ along which the right-hand side of (9) is
$\gg\delta x_{k}/\ell$ when $X=x_{k}$, outside of a small set of
exceptional999The dependence of the exceptional set on $x_{k}$ introduces a
complication, but is dealt with by suitably arranging the arguments in the
sequel. $\ell$. Moreover, most of those $\ell$ for which (9) holds satisfy
$(2b,f(\ell))=1$ and $\ell\nmid a$ (see Lemma 5.2). Thus, for any odd prime
power $q|f(\ell)$, orthogonality of Dirichlet characters modulo $q$ gives

$\frac{1}{\phi(q)}\sum_{\chi\pmod{q}}\overline{\chi}(b)\sum_{\begin{subarray}{c}n\leq
x_{k}\\\ n\equiv
a\pmod{\ell}\end{subarray}}f^{\chi}(n)\geq\sum_{\begin{subarray}{c}m\leq
x_{k}/\ell\\\ \ell\nmid m\end{subarray}}1_{f(m\ell+a)\equiv
b\pmod{q}}\gg\frac{\delta x_{k}}{\ell}.$

In particular, we find that for $\gg_{\delta}\phi(q)$ characters
$\chi\pmod{q}$ we have

$\left|\sum_{\begin{subarray}{c}n\leq x_{k}\\\ n\equiv
a\pmod{\ell}\end{subarray}}f^{\chi}(n)\right|\gg\frac{\delta x_{k}}{\ell}.$

Since $f^{\chi}$ is a bounded multiplicative function, work of Granville,
Harper and Soundararajan [6] implies (see Lemma 5.6) that as long as $\ell$ is
not too large, for any such $\chi$ we have

$\max_{\psi\pmod{\ell}}\left|\sum_{n\leq
x_{k}}f^{\chi}(n)\overline{\psi}(n)\right|\gg\delta x_{k}.$

This is the desired analogue of (7) in our circumstances, in which the
summands $n\mapsto f^{\chi}\overline{\psi}(n)$ are multiplicative functions.
By a quantitative version of Halász’s theorem (see Theorem 3.6) we deduce that
there are $\gg_{\delta}\phi(q)$ characters $\chi\pmod{q}$ for which there
exists a character $\psi_{\chi}$ modulo $\ell$ and a $t_{\chi}\in\mathbb{R}$
such that

(10) $\displaystyle\chi(f(p))\approx\psi_{\chi}(p)p^{it_{\chi}}\text{ for most
}p\leq x_{k}.$

A key point here is that the character groups $\Xi_{q}$ and $\Xi_{\ell}$ are
both cyclic. On this basis, we use inverse sumset theorems from elementary
additive combinatorics to study the set of $\chi$ satisfying (10). We show
more precisely that there is a _large_ subgroup $H=H_{k,q,\ell}\leq\Xi_{q}$ of
$\chi$ that satisfy (10) with

$t_{\chi}=0\text{ for all }\chi\in H.$

Moreover, the mapping $\gamma:\chi\mapsto\psi_{\chi}$ is a homomorphism whose
image lies in $\Xi_{\ell}$. Since $H$ and $\gamma(H)$ are both cyclic, we show
(see Proposition 5.4 below) that there is a positive integer
$D=O_{\delta}(1)$, independent of $k$ and $\ell$, a homomorphism

$\varphi:(\mathbb{Z}/\ell\mathbb{Z})^{\times}\rightarrow(\mathbb{Z}/q\mathbb{Z})^{\times}$

and an $O_{\delta}(1)$-sparse set of primes
$\mathcal{T}_{\ell}\subseteq\mathcal{P}\cap[2,x_{k}]$ such that the following
holds: if $p\leq x_{k}$, $p\notin\mathcal{T}_{\ell}$ then

$p\equiv a\pmod{\ell}\Rightarrow f(p)^{D}\equiv\varphi(a)\pmod{q}.$

(The exceptional set $\mathcal{T}_{\ell}$ depends on $\ell$ and $k$, which
introduces additional complications).
Assuming Conjecture 1.5 holds, we expect that if $q|f(\ell)$ then $q$ is a
power of $\ell$. In that case, taking $q=\ell$, $f^{D}$ is behaves (at least
along the primes) like an endomorphism $\varphi$ on
$(\mathbb{Z}/\ell\mathbb{Z})^{\times}$. Since this group is cyclic, it is easy
to show that any such endomorphism is a power map $a\mapsto a^{g_{\ell}}$, for
some $0\leq g_{\ell}<\ell-1$. Thus, we deduce that

(11) $f(p)^{D}\equiv p^{g_{\ell}}\pmod{\ell}\text{ for all but a sparse set
}p\in\mathcal{T}_{\ell},$

whenever $\ell$ is a prime (excluded from a sparse set) such that
$\ell|f(\ell)$.

#### Local-to-global principle for power maps

Given a prime $\ell$ let us say that a map $F:\mathbb{N}\rightarrow\mathbb{Z}$
is a _local power map modulo $\ell$_ if there exists an integer $k_{\ell}$
such that

(12) $F(n)\equiv n^{k_{\ell}}\pmod{\ell}\text{ for all }n\in\mathbb{N}.$

We say that $F$ is a _global power map_ if there is a non-negative integer $k$
such that

$F(n)=n^{k}\text{ for all }n\in\mathbb{N}.$

Obviously, any global power map is a local power map modulo any prime $\ell$.
Conversely, it is not difficult to show that if $F$ satisfies (12) with
$k_{\ell}=k$ for infinitely many $\ell$ then $F$ is a global power map. It is
reasonable to expect more generally that if $F$ is a local power map (without
restrictions on $k_{\ell}$) for _sufficiently many_ distinct primes $\ell$
then $F$ is a global power map. Such a local-to-global phenomenon for
multiplicative functions $F$ is the subject of a 1988 conjecture due to
Fabrykowski and Subbarao [3] (see Conjecture 6.1 and Lemma 6.2 for relevant
statements). Their conjecture states that if $F$ is a multiplicative function
that satisfies (12) modulo infinitely many primes $\ell$ then $F$ is a global
power map. As far as the author is aware the conjecture is still open in full
generality.
Using an ingenious argument based on applying the Chebotarev density theorem
to suitably chosen Kummer extensions of $\mathbb{Q}$, Jones [9] proved that
such a local-to-global phenomenon occurs provided the set of moduli $\ell$ for
which $F$ is a local power map modulo $\ell$ has positive upper density in the
primes, i.e.,

$\limsup_{X\rightarrow\infty}\frac{1}{\pi(X)}|\\{\ell\leq
X:\eqref{eq:LPMProp}\text{ holds with }\ell\\}|>0.$

Equation (11) shows that $F:=f^{D}$ is a local power map modulo $\ell$ along
the primes $p\notin\mathcal{T}_{\ell}$, for all primes $\ell$ in
$S_{f}:=\\{\ell\in\mathcal{P}:\ell|f(\ell)\\}$, outside of a sparse set.
Incorporating some additional ideas into Jones’ argument, we show a similar
local-to-global phenomenon for $f^{D}$ in our more restricted situation, under
the (weaker) assumption that $d_{\text{Dir}}(S_{f})>0$ (or indeed,
conditionally on ERH, that $\sum_{p|f(p)}p^{-1}=\infty$).
More precisely, we first show that if (11) holds for a set of primes with
positive Dirichlet density then $f(\ell)^{D}$ is a power of $\ell$ for all but
a sparse set of primes $\ell$ (see Proposition 6.3). Arguing by contradiction,
we show that if $f(\ell)$ is _not_ a power of $\ell$ for many $\ell$ then we
may cover the bulk of $S_{f}$ by _thin_ subsets of primes that are unramified
in suitably constructed Kummer extensions

$\mathbb{Q}(\zeta_{m},p_{1}^{1/m},p_{2}^{1/m},F(p_{1})^{1/m},F(p_{2})^{1/m}),\quad
m,p_{1},p_{2}\in\mathcal{P},\,p_{1}\neq p_{2}.$

Care is taken to ensure that the values $p_{1},p_{2},F(p_{1}),F(p_{2})$ are
multiplicatively independent, in order for the Galois groups of the extensions
to be suitably large. To do this we must deal with the possibility that the
exceptional sets $\mathcal{T}_{\ell}$ overlap. We succeed in showing in this
direction that the vast majority of primes $p$ belong to only _very few_ of
the sets $\mathcal{T}_{\ell}$.
Having done this, we show that if $|f(p)|=p^{\alpha_{p}}$ for all but a sparse
set of $p$ then $\alpha_{p}=1$ for all such $p$ (see Proposition 6.4). To do
this, we first prove that $\alpha_{p}$ is constant (outside of a sparse set of
$p$). This is accomplished by locating arbitrarily large primes $\ell$ and
primes $p_{\ell}\notin\mathcal{T}_{\ell}$ that are primitive roots
$\pmod{\ell}$ and that satisfy $|f(p_{\ell})|\ll p_{\ell}^{r}$, where $r$ is
the exponent from (5). To see why this is helpful, note that

$p_{\ell}^{D\alpha_{p_{\ell}}}=f(p_{\ell})^{D}\equiv
p_{\ell}^{g_{\ell}}\pmod{\ell},$

with $D\alpha_{p_{\ell}}=O_{\delta}(1)$ and $g_{\ell}<\ell-1$. If $p_{\ell}$
is a primitive root modulo $\ell$ and $\ell\geq\ell_{0}(\delta)$ then,
necessarily, $g_{\ell}=D\alpha_{p_{\ell}}.$ By pigeonholing over the possible
(integer) values of $\alpha_{p_{\ell}}=O_{\delta}(1)$ we find that

$g_{\ell}=D\alpha_{0}=O_{\delta}(1)\text{ for many }\ell.$

We then show that for each fixed prime $p\geq p_{0}(\delta)$ we may find one
of these $\ell$, large relative to $p$ and $\delta$, such that $f(p)^{D}\equiv
p^{D\alpha_{0}}\pmod{\ell}$, leading to the conclusion $|f(p)|=p^{\alpha_{0}}$
for all but a sparse set of $p$.
To show that $\alpha_{0}=1$ we must exploit the equation $f(n+a)=f(n)+b$,
which is linear in values of $(f(m))_{m}$, taking care to control the
influence of certain exceptional primes in the factorisations of $n$ and $n+a$
using elementary sieve theory.
Putting all of these arguments together, we obtain the first claim of Theorem
1.6. The conditions on $a,b$ are a simple consequence when $f$ is completely
multiplicative.

###  2.2. Proof strategy for Proposition 1.8

By hypothesis, $\mathcal{S}$ is a sparse set of primes such that
$\mathcal{S}_{d}:=\mathcal{S}\backslash\\{p:p|d\\}$ satisfies
$|\mathcal{S}_{d}|\geq 2$. Let $\mathcal{T}$ be a set of primes disjoint from
$\mathcal{S}$.
To prove Proposition 1.8 we construct the sets

$\mathcal{N}:=\\{dpm:p\in\mathcal{S}_{d},\,(m,\mathcal{S})=1\\},\quad\mathcal{N}_{\mathcal{T}}:=\\{dpm\in\mathcal{N}:\lambda_{\mathcal{T}}(m)=+1\\},$

where $\lambda_{\mathcal{T}}(m)$ is the completely multiplicative function
defined at primes via

$\lambda_{\mathcal{T}}(p)=\begin{cases}-1\text{ if }p\in\mathcal{T}\\\
+1\text{ if }p\notin\mathcal{T}.\end{cases}$

We then construct a completely multiplicative function $f=f_{\mathcal{T}}$
satisfying the conditions (i)-(iii) of the proposition (in particular that
$f(p)=\lambda_{\mathcal{T}}(p)p$ for all $p\notin\mathcal{S}$) such that

$\mathcal{N}_{\mathcal{T}}^{\prime}:=\\{n\in\mathbb{N}:n,n+a\in\mathcal{N}_{\mathcal{T}}\\}\subseteq\mathcal{N}_{f,a,b}.$

To verify (iv) it suffices to show that
$\overline{\delta}(\mathcal{N}_{\mathcal{T}}^{\prime})>0$ for uncountably many
$\mathcal{T}$. Note that when $\mathcal{T}=\emptyset$ we have
$\mathcal{N}=\mathcal{N}_{\mathcal{T}}$, and the positive density of
$\mathcal{N}_{\emptyset}^{\prime}$ (which is stronger than what we are aiming
for) follows from a zero-dimensional sieve estimate. In general, however, the
condition $\lambda_{\mathcal{T}}(m)=+1$ introduces a complication.
Writing $g(n):=1_{(n,\mathcal{S})=1}$, we reduce matters to showing that for
any pair of fixed, distinct primes $p_{1},p_{2}\in\mathcal{S}_{d}$, and fixed
integers $u,v\in\mathbb{Z}$ with $(u,p_{2})=(v,p_{1})=1$,

$\frac{1}{d\log x}\sum_{\begin{subarray}{c}n\leq x/(dp_{1}p_{2})\\\
\lambda_{\mathcal{T}}(np_{2}+u)=\lambda_{\mathcal{T}}(np_{1}+v)=+1\end{subarray}}\frac{g(np_{2}+u)g(np_{1}+v)}{n}\gg_{d,p_{1},p_{2}}1.$

Writing $1_{\lambda_{\mathcal{T}}(m)=+1}=(1+\lambda_{\mathcal{T}}(m))/2$, the
problem becomes one of estimating the correlations

$\frac{1}{d\log x}\sum_{n\leq
x/dp_{1}p_{2}}\frac{g\lambda_{\mathcal{T}}^{\eta_{1}}(np_{2}+u)g\lambda_{\mathcal{T}}^{\eta_{2}}(np_{1}+v)}{n},\text{
for each }(\eta_{1},\eta_{2})\in\\{0,1\\}^{2}.$

The sum with $(\eta_{1},\eta_{2})=(0,0)$ effectively reduces the problem to
the case $\mathcal{T}=\emptyset$, which is easily handled. The heart of the
matter is to handle the contributions from $(\eta_{1},\eta_{2})\neq(0,0)$, and
it suffices to show that these correlations are $o(1)$.
Appealing to Tao’s theorem once again, the correlations are $o(1)$ for all
$(\eta_{1},\eta_{2})\neq(0,0)$ as long as $\lambda_{\mathcal{T}}$ is _non-
pretentious_ , i.e., $\lambda_{\mathcal{T}}$ does not correlate with any
fixed, real Dirichlet character $\chi$ in the sense that

(13) $\lim_{x\rightarrow\infty}\sum_{p\leq
x}\frac{1-\lambda_{\mathcal{T}}(p)\chi(p)}{p}=\infty\text{ for each real,
primitive }\chi.$

We show that this is the case almost surely for $\mathcal{T}$ _randomly
chosen_ (see Lemma 9.2). That is, we show that $\lambda_{\mathcal{T}}$ is non-
pretentious in the above sense if we let $\mathcal{T}$ be the outcome of a
random variable101010It should be noted that we may also _deterministically_
construct sets $\mathcal{T}$ for which $\lambda_{\mathcal{T}}$ is non-
pretentious in the above sense. For example, any set $\mathcal{T}$ with
Dirichlet density zero would suit our purposes. In any case, our probabilistic
construction is intended to indicate that this is generic behaviour.
$\mathbf{T}$, restricted to a set of probability 1, defined by

$\mathbf{T}:=\\{p\notin\mathcal{S}:X_{p}=1\\},$

where $(X_{p})_{p\notin\mathcal{S}}$ is a collection of i.i.d. Bernoulli
random variables with mean $1/2$. Equation (13) is proved using elementary
calculations in probability theory, see Section 9.

##  3\. Background and auxiliary results

###  3.1. Lemmas about additive functions

Recall that $g:\mathbb{N}\rightarrow\mathbb{C}$ is _additive_ if whenever
$n,m\in\mathbb{N}$ are coprime,

$g(mn)=g(m)+g(n).$

For an additive function, and $X\geq 2$ set

$A_{g}(X):=\sum_{p^{\nu}\leq
X}\frac{g(p^{\nu})}{p^{\nu}}\left(1-\frac{1}{p}\right),\quad
B_{g}(X):=\left(\sum_{p^{\nu}\leq
X}\frac{|g(p^{\nu})|^{2}}{p^{\nu}}\right)^{1/2}.$

In the sequel, the following example will reoccur several times. Given
$\mathcal{S}$ a set of prime powers define the additive function

$\omega_{\mathcal{S}}(n):=|\\{p^{\nu}||n:p^{\nu}\in\mathcal{S}\\}|.$

In this case,

(14) $A_{\omega_{\mathcal{S}}}(X)=\sum_{\begin{subarray}{c}p^{\nu}\leq X\\\
p^{\nu}\in\mathcal{S}\end{subarray}}\frac{1}{p^{\nu}}\left(1-\frac{1}{p}\right)=\sum_{\begin{subarray}{c}p^{\nu}\leq
X\\\
p^{\nu}\in\mathcal{S}\end{subarray}}\frac{1}{p^{\nu}}+O(1)=B_{\omega_{\mathcal{S}}}(X)^{2}+O(1).$

The function $A_{g}(X)$ is asymptotically the mean value of $g(n)$ for
$n\in[1,X]$, as $X\rightarrow\infty$. The following lemma allows us to
estimate how frequently and by how much $g(n)$ can deviate from $A_{g}(X)$.

######  Lemma 3.1 (Turán-Kubilius inequality).

Let $g:\mathbb{N}\rightarrow\mathbb{C}$ be an additive function, and let
$X\geq 3$. Then

$\frac{1}{X}\sum_{n\leq X}|g(n)-A_{g}(X)|^{2}\ll B_{g}(X)^{2}.$

The implicit constant is absolute.

###### Proof.

This is [1, Lem. 4.1]. ∎

The following “dual” form of Lemma 3.1 was discovered by Elliott.

######  Lemma 3.2 (Elliott).

Let $(a_{n})_{n}\subset\mathbb{C}$ be a sequence and let $X\geq 1$. Then

$\sum_{p^{\nu}\leq X}p^{\nu}\left|\sum_{\begin{subarray}{c}n\leq X\\\
p^{\nu}||n\end{subarray}}a_{n}-\frac{1}{p^{\nu}}\left(1-\frac{1}{p}\right)\sum_{n\leq
X}a_{n}\right|^{2}\ll X\sum_{n\leq X}|a_{n}|^{2}.$

###### Proof.

This is [1, Lem. 4.2]. ∎

###  3.2. Background on the pretentious distance

As in [19] we will make frequent use of the pretentious distance of Granville
and Soundararajan. Given arithmetic functions
$f,g:\mathbb{N}\rightarrow\mathbb{U}$ and $x\geq 2$ we define

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

We recall the following two forms of the _pretentious triangle inequality_
(see [7, Lem. 3.1]). For any $J\geq 1$ and 1-bounded arithmetic functions
$f,g,h,(f_{j})_{1\leq j\leq J},(g_{j})_{1\leq j\leq J}$ we have

(15) $\displaystyle\mathbb{D}(f,h;x)\leq\mathbb{D}(f,g;x)+\mathbb{D}(g,h;x),$
(16) $\displaystyle\mathbb{D}(f_{1}\cdots f_{J},g_{1}\cdots
g_{J};x)\leq\sum_{1\leq j\leq J}\mathbb{D}(f_{j},g_{j};x).$

Controlling the distance $\mathbb{D}(n^{it},1;x)$ uniformly in a range of $t$
is important in the study of mean values and correlations of 1-bounded
multiplicative functions. In this direction, Lemma 2.1 in [19] gave the
standard estimates

(17) $\displaystyle\mathbb{D}(1,n^{it};x)^{2}\geq\begin{cases}\log(1+|t|\log
x)+O(1)&\text{ if }|t|\leq 10\\\ (1/3-o(1))\log\log x&\text{ if }10\leq|t|\leq
x^{2}.\end{cases}$

In addition, in the sequel we will need to consider the distance between
$n^{it}$ and more general primitive Dirichlet characters $\chi$. In this
direction we will use the following standard fact repeatedly.

######  Lemma 3.3.

There is an absolute constant $C_{0}\geq 1$ such that for $C\geq C_{0}$ the
following is true. Let $x$ be sufficiently large relative to $C$, and let
$1\leq q\leq x^{1/(5C)}$ be a prime power. Let $\chi$ be a Dirichlet character
modulo $q$ and let $|t|\leq x^{2}$. If

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

then $\chi$ is principal and $|t|\ll_{C}\tfrac{1}{\log x}$.

###### Proof.

Assume first that $\chi$ is non-principal. By111111The bound in [14] is given
only in the range $|t|\leq 10x$, but the same argument extends to the full
range $|t|\leq x^{2}$. [14, Lem. 7.8] we have

$C\geq\mathbb{D}(\chi,n^{it};x)^{2}\geq\frac{1}{4}\log\left(\frac{\log x}{\log
q}\right)+O(1)\geq\frac{5}{4}C+O(1)>C$

if $C_{0}$ is sufficiently large and $C\geq C_{0}$. This contradiction implies
that $\chi$ must in fact be principal.
Next, we observe that

$C\geq\mathbb{D}(\chi_{0},n^{it};x)^{2}\geq\mathbb{D}(1,n^{it};x)^{2}+O(1).$

In light of (17), if $x$ is large enough we must have $|t|\leq 10$, and indeed
$|t|\log x\ll_{C}1$, as claimed. ∎

Finally, for real-valued multiplicative functions
$g:\mathbb{N}\rightarrow[-1,1]$ we will use the following.

######  Lemma 3.4.

Let $x\geq 3$. Let $g:\mathbb{N}\rightarrow[-1,1]$ be multiplicative, and let
$\chi$ be a fixed Dirichlet character. Put $\varepsilon_{\chi}:=1$ if $\chi$
is real-valued, and $\varepsilon_{\chi}=0$ otherwise. Then

$\inf_{\varepsilon_{\chi}\leq|t|\leq
x^{2}}\mathbb{D}(g,\chi(n)n^{it};x)\geq\frac{1}{4}\sqrt{\log\log
x}+O_{\chi}(1).$

Moreover, if $\chi$ is real-valued then

$\inf_{|t|\leq
1}\mathbb{D}(g,\chi(n)n^{it};x)\geq\frac{1}{3}\mathbb{D}(g,\chi;x)+O(1).$

###### Proof.

This is [20, Lem. C.1]. ∎

###  3.3. Auxiliary results about multiplicative functions

As in [19], Tao’s theorem on logarithmically-averaged binary correlations
plays a crucial role in our analysis.

######  Theorem 3.5 (Tao, [24]).

Let $\eta>0$ and let $a,c\in\mathbb{N}$, $b,d\in\mathbb{Z}$ satisfy $ad-bc\neq
0$. Let $g_{1},g_{2}:\mathbb{N}\rightarrow\mathbb{U}$ be 1-bounded
multiplicative functions with the property that for some $x\geq x_{0}(\eta)$,

$\frac{1}{\log x}\left|\sum_{n\leq
x}\frac{g_{1}(an+b)g_{2}(cn+d)}{n}\right|\geq\eta.$

Then there are primitive Dirichlet characters $\psi_{j}=\psi_{j,x}$ with
conductor $O_{\eta}(1)$ and real numbers $t_{j}=t_{j,x}$ with
$|t_{j}|=O_{\eta}(x)$ such that for $j=1,2$,

$\mathbb{D}(g_{j},\psi_{j}(n)n^{it_{j}};x)^{2}=\sum_{p\leq
x}\frac{1-{\text{Re}}(g_{j}(p)\overline{\psi}_{j}(p)p^{-it_{j}})}{p}=O_{\eta}(1).$

In addition, we will also need the following quantitative version of Halász’s
theorem on mean values of multiplicative functions, which provides similar but
more precise data about functions with large partial sums than Tao’s theorem.

######  Theorem 3.6 (Halász-Montgomery-Tenenbaum Inequality).

Let $x\geq 3$ and $T\geq 1$. Let $g:\mathbb{N}\rightarrow\mathbb{U}$ be a
multiplicative function. Then

$\frac{1}{x}\sum_{n\leq x}g(n)\ll(1+M_{g})e^{-M_{g}}+\frac{1}{T},$

where $M_{g}=M_{g}(x;T)$ is defined by

$M_{g}(x;T):=\min_{|t|\leq T}\mathbb{D}(g,n^{it};x)^{2}=\min_{|t|\leq
T}\sum_{p\leq x}\frac{1-{\text{Re}}(g(p)p^{-it})}{p}.$

###### Proof.

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

The following variant of Shiu’s theorem, which is a consequence of a result
due to Pollack [22], will allow us to work conveniently with sums over shifted
primes in Section 6.

######  Lemma 3.7.

Let $X\geq 2$ and let $k\geq 0$ be an integer. For each prime $p\leq X$ let
$\mathcal{E}_{p}\subseteq(\mathbb{Z}/p\mathbb{Z})^{\times}$ be a set of
$\nu(p)\leq k$ non-zero residue classes, and let

$\mathscr{S}:=\bigcap_{p\leq X}\\{n\leq
X:\,n\pmod{p}\notin\mathcal{E}_{p}\\}.$

Then, uniformly over all multiplicative functions
$f:\mathbb{N}\rightarrow\mathbb{R}$ that satisfy

$0\leq f(n)\leq d(n)\text{ for all }n,$

we have

$\sum_{\begin{subarray}{c}n\leq X\\\
n\in\mathscr{S}\end{subarray}}f(n)\ll_{k}\frac{X}{\log X}\exp\left(\sum_{p\leq
X}\frac{f(p)-\nu(p)}{p}\right).$

###### Proof.

This is immediate from [22, Thm. 1.1], taking $A_{1}=2$ in the definition of
$\mathscr{M}$ there, and $y=X$. ∎

##  4\. Applying the projection method: the archimedean argument

Given $a\in\mathbb{N}$, $b\in\mathbb{Z}\backslash\\{0\\}$ and a multiplicative
function $f:\mathbb{N}\rightarrow\mathbb{Z}$ recall the notation

$\mathcal{N}_{f,a,b}:=\\{n\in\mathbb{N}:f(n+a)=f(n)+b\\}.$

In this section we use the compositions $|f|_{t}:=|f|^{it}$ to study the
sequence of magnitudes $(|f(p)|)_{p}$ when
$\overline{\delta}(\mathcal{N}_{f,a,b})>0$. In most aspects this is identical
to the procedure in [19, Sec. 3], where $b=0$.

######  Proposition 4.1.

Let $f:\mathbb{N}\rightarrow\mathbb{Z}$ be a multiplicative function that
satisfies

(18) $\sum_{p:|f(p)|\neq
1}\frac{1}{p}=\infty,\quad\sum_{p:f(p)=0}\frac{1}{p}<\infty.$

Let $a\in\mathbb{N}$, $b\in\mathbb{Z}\backslash\\{0\\}$, and assume that
$\overline{\delta}(\mathcal{N}_{f,a,b})>\delta$ for some $\delta\in(0,1/2)$.
Then there is a $0<r\ll_{\delta}1$ and a $O_{\delta}(1)$-sparse sequence of
primes $\mathcal{S}_{\delta}$ such that

$\frac{1}{2}<|f(p)|/p^{r}<2\text{ for all }p\notin\mathcal{S}_{\delta}.$

######  Remark 4.2.

We may assume that for $f$ in Conjecture 1.5 the set
$\\{p\in\mathcal{P}:f(p)=0\\}$ is sparse, and thus Conjecture 1.5 classifies
all non-trivial functions for which $\overline{\delta}(\mathcal{N}_{f,a,b})>0$
for some $ab\neq 0$.
Indeed, suppose otherwise. Then the multiplicative function $1_{f(n)\neq 0}$
has vanishing logarithmic mean:

$\frac{1}{\log x}\sum_{n\leq x}\frac{1_{f(n)\neq
0}}{n}\ll\exp\left(-\sum_{\begin{subarray}{c}p\leq x\\\
f(p)=0\end{subarray}}\frac{1}{p}\right)=o(1),\quad x\rightarrow\infty.$

It follows that $f(n+a)=f(n)=0$ for a logarithmic density $1$ set of $n$. In
particular, $\delta(\mathcal{N}_{f,a,b})=0$ whenever $ab\neq 0$, contradicting
our hypothesis. There is therefore no loss in assuming both of the conditions
(18) here.

Let $\varepsilon\in(0,1)$. Note that if $n\in\mathcal{N}_{f,a,b}$ satisfies
$|f(n)|>|b|\varepsilon^{-1}$ then

$f(n+a)/f(n)\in(1-\varepsilon,1+\varepsilon).$

Our arguments treat precisely those $n$ for which such a condition holds. The
following lemma implies that the converse inequality
$|f(n)|\leq|b|\varepsilon^{-1}$ holds for very few $n$.

######  Lemma 4.3.

Assume that $f$ satisfies both conditions in (18). Then for any fixed $M\geq
1$ we have

$\frac{1}{\log x}\sum_{\begin{subarray}{c}n\leq x\\\ 0<|f(n)|\leq
M\end{subarray}}\frac{1}{n}=o(1).$

######  Remark 4.4.

It is not difficult to see that the proof furthermore implies the stronger
bound

$\frac{1}{x}|\\{n\leq x:0<|f(n)|\leq M\\}|=o(1)\text{ as }x\rightarrow\infty.$

###### Proof.

Let $\mathcal{S}:=\\{p^{\nu}:|f(p^{\nu})|\neq 0,1\\}$, and define
$\omega_{\mathcal{S}}(n)$ to be the number of prime powers
$p^{\nu}\in\mathcal{S}$ with $p^{\nu}||n$. Since $f$ takes integer values,
$|f(p^{\nu})|\geq 2$ for all $p^{\nu}\in\mathcal{S}$. Thus,

$\text{if }0<|f(n)|\leq M\text{ then
}\omega_{\mathcal{S}}(n)\leq\frac{\log(2M)}{\log 2}.$

According to (18), as $X\rightarrow\infty$ we have

$E_{\mathcal{S}}(X):=\sum_{\begin{subarray}{c}p^{\nu}\leq X\\\
p^{\nu}\in\mathcal{S}\end{subarray}}\frac{1}{p^{\nu}}\left(1-\frac{1}{p}\right)\geq\frac{1}{2}\sum_{\begin{subarray}{c}p\leq
X\\\ |f(p)|\neq 0,1\end{subarray}}\frac{1}{p}\rightarrow\infty.$

Furthermore, by Lemma 3.1 (and (14)),

$\frac{1}{X}\sum_{X\leq
n<2X}|\omega_{\mathcal{S}}(n)-E_{\mathcal{S}}(X)|^{2}\ll E_{S}(X),\quad X\geq
2.$

Therefore when $X\geq X_{0}(M)$ we have

$\displaystyle|\\{X\leq n<2X:0<|f(n)|\leq M\\}|$ $\displaystyle\leq|\\{X\leq
n<2X:|\omega_{\mathcal{S}}(n)-E_{\mathcal{S}}(X)|>E_{\mathcal{S}}(X)/2\\}|$
$\displaystyle\ll\frac{1}{E_{\mathcal{S}}(X)^{2}}\sum_{n\leq
2X}|\omega_{\mathcal{S}}(n)-E_{\mathcal{S}}(X)|^{2}\ll\frac{X}{E_{\mathcal{S}}(X)}.$

Set $z:=x^{1/E_{\mathcal{S}}(x)}\geq x^{1/(2\log\log x)}$. Taking a
logarithmic average and decomposing over dyadic scales,

$\displaystyle\frac{1}{\log x}\sum_{\begin{subarray}{c}n\leq x\\\ 0<|f(n)|\leq
M\end{subarray}}\frac{1}{n}$ $\displaystyle\leq\frac{1}{\log
x}\sum_{z<y=2^{j}\leq x}\frac{1}{y}|\\{y\leq n<2y:0<|f(n)|\leq
M\\}|+O\left(\frac{\log z}{\log x}\right)$ $\displaystyle\ll\frac{1}{\log
x}\sum_{z<y=2^{j}\leq x}\frac{1}{E_{\mathcal{S}}(y)}+\frac{1}{\sqrt{\log
x}}\ll\frac{1}{E_{\mathcal{S}}(z)},$

and the claim follows as $x$ (and thus also $z$) tends to infinity. ∎

###### Proof of Proposition 4.1.

Let $(X_{j})_{j}\subseteq\mathbb{N}$ be an infinite increasing subsequence on
which

$\overline{\delta}(\mathcal{N}_{f,a,b})=\lim_{j\rightarrow\infty}\frac{1}{\log
X_{j}}\sum_{\begin{subarray}{c}n\leq X_{j}\\\
f(n+a)=f(n)+b\end{subarray}}\frac{1}{n}.$

Given $n\in\mathbb{N}$ with $f(n)\neq 0$, define $g(n):=\log|f(n)|$. Observe
that

$\text{if }f(n+a)=f(n)+b\text{ with }f(n+a)f(n)\neq 0,\text{ and }|f(n)|\geq
10|b|$

then it follows that

$|g(n+a)-g(n)|=|\log|f(n+a)/f(n)||\leq\max\\{\log(1+|b/f(n)|),-\log(1-|b/f(n)|)\\}<\frac{1}{2},$

and in particular that

$1_{f(n+a)=f(n)+b}\leq 2\max\\{1-|g(n+a)-g(n)|,0\\}.$

In order to use this we first discard those $n$ for which $f(n)f(n+a)=0$ or
$0<|f(n)|\leq 10|b|$.
Let $j\geq j_{0}(\delta,|b|)$ be large and set $X=X_{j}$. Observe that since
$b\neq 0$, by Lemma 4.3 we have

$\displaystyle\frac{1}{\log X}\sum_{\begin{subarray}{c}n\leq X\\\
f(n+a)=f(n)+b\\\ f(n)f(n+a)=0\end{subarray}}\frac{1}{n}$
$\displaystyle\leq\frac{1}{\log X}\sum_{\begin{subarray}{c}n\leq X\\\
f(n+a)=b\end{subarray}}\frac{1}{n}+\frac{1}{\log
X}\sum_{\begin{subarray}{c}n\leq X\\\ f(n)=-b\end{subarray}}\frac{1}{n}$
$\displaystyle\ll\frac{1}{\log X}\sum_{\begin{subarray}{c}m\leq X\\\
0<|f(m)|\leq|b|\end{subarray}}\frac{1}{m}+\frac{a}{\log X}<\delta^{2}.$

Moreover, by the same argument we also have

$\frac{1}{\log X}\sum_{\begin{subarray}{c}n\leq X\\\ 0<|f(n)|\leq
10|b|\end{subarray}}\frac{1}{n}<\delta^{2}.$

Thus, if $j\geq j_{0}(\delta)$ we find that

$\displaystyle\delta\leq\frac{1}{\log X}\sum_{\begin{subarray}{c}n\leq X\\\
f(n+a)=f(n)+b\end{subarray}}\frac{1}{n}$ $\displaystyle=\frac{1}{\log
X}\sum_{\begin{subarray}{c}n\leq X\\\ f(n)f(n+a)\neq 0\\\ |f(n)|\geq
10|b|\end{subarray}}\frac{1_{f(n+a)=f(n)+b}}{n}+O(\delta^{2})$
$\displaystyle\leq\frac{2}{\log X}\sum_{\begin{subarray}{c}n\leq x\\\
f(n)f(n+a)\neq
0\end{subarray}}\frac{\max\\{1-|g(n+a)-g(n)|,0\\}}{n}+O(\delta^{2}).$

Recall the notation $|f|_{\beta}(n):=|f(n)|^{i\beta}$ for $n\in\mathbb{N}$
satisfying $f(n)\neq 0$ and $\beta\in\mathbb{R}$. Taking $B=\delta^{-2}$, this
is sufficient to establish the conclusion of [19, Lem. 3.2], namely that the
set

$\left\\{\alpha\in[-B,B]:\left|\frac{1}{\log X}\sum_{\begin{subarray}{c}n\leq
X\\\ f(n+a)f(n)\neq
0\end{subarray}}\frac{|f|_{\alpha}(n+a)|f|_{-\alpha}(n)}{n}\right|\geq\delta/16\pi\right\\}$

has Lebesgue measure $\geq\delta/16\pi$ for each $X$ along an infinite
subsequence of $(X_{j})_{j}$. As discussed in [19, Sec. 3], the conclusion of
[19, Prop. 3.1] follows from this, and so there is a $0\leq r\ll_{\delta}1$
and a set of primes $\mathcal{S}_{\delta}$ outside of which

$e^{-\delta^{2}}\leq|f(p)|/p^{r}\leq e^{\delta^{2}}.$

Since $\delta\in(0,1/2)$ we deduce that $e^{\delta^{2}}<2$, and so

$\sum_{p:|f(p)|/p^{r}\notin(1/2,2)}\frac{1}{p}\leq\sum_{p\in\mathcal{S}_{\delta}}\frac{1}{p}<\infty.$

Now if $r=0$ then as $f(p)\in\mathbb{Z}$,

$\sum_{p:|f(p)|\neq
1}\frac{1}{p}=\sum_{p:|f(p)|\notin(1/2,2)}\frac{1}{p}<\infty,$

a contradiction. Therefore, $r>0$ as required. ∎

######  Remark 4.5.

Given that $r>0$, we see that for $p\geq p_{0}(\delta)$,

$p\notin\mathcal{S}_{\delta}\Rightarrow|f(p)|\geq p^{r}/2>1.$

In particular, using Proposition 4.1 we conclude that

$\sum_{\begin{subarray}{c}p^{\nu}\leq X\\\ |f(p^{\nu})|\neq
0,1\end{subarray}}\frac{1}{p^{\nu}}=\log\log
X+O\left(1+\sum_{\begin{subarray}{c}p\leq X\\\
p\in\mathcal{S}_{\delta}\end{subarray}}\frac{1}{p}\right)=\log\log
X+O_{\delta}(1),$

which quantitatively refines the first hypothesis in (18).

##  5\. The non-Archimedean Argument: Reduction to local power maps

###  5.1. Setting up Proposition 5.4

The objective of this section is to prove Proposition 5.4. Since its precise
statement is somewhat technical we defer providing it for the moment and
roughly describe its content here.
Since
$\overline{d}(\mathcal{N}_{f,a,b})\geq\overline{\delta}(\mathcal{N}_{f,a,b})>\delta$
we can find an infinite increasing sequence $(x_{k})_{k}$ such that

(19) $|\mathcal{N}_{f,a,b}\cap[1,x_{k}]|\geq\delta x_{k},\quad k\geq k_{0}.$

Proposition 5.4 asserts that there are positive integers $A,D=O_{\delta}(1)$
such that at each such scale $x_{k}$, for the vast majority of primes
$\ell\leq x_{k}^{1/A}$ the power $f^{D}$ of $f$ behaves like a homomorphism

$\varphi:(\mathbb{Z}/\ell\mathbb{Z})^{\times}\rightarrow(\mathbb{Z}/q_{\ell}\mathbb{Z})^{\times}$

for any prime power $q_{\ell}|f(\ell)$ of our choice. More precisely, outside
of a sparse set $\mathcal{T}_{\ell}$ of primes $p\leq x_{k}$,

$f(p)^{D}\equiv\varphi(a)\pmod{q_{\ell}}\text{ whenever }p\equiv
a\pmod{\ell}.$

In the case that $\ell|f(\ell)$ we may select $q_{\ell}=\ell$, and deduce that
$f^{D}$ is (essentially) a _local power map_ modulo $\ell$, i.e. that for some
$0\leq g_{\ell}<\ell-1$,

$f(p)^{D}\equiv p^{g_{\ell}}\pmod{\ell},\quad
p\in[2,x_{k}]\backslash\mathcal{T}_{\ell}.$

In the next section we will see how to “glue” together these local conditions
to establish global information about $f$.
To this end, we begin by showing that $\mathcal{N}_{f,a,b}$ contains many
multiples of primes $\ell$ for which $(b,f(\ell))=1$. This will allow us to
show that

$f(n+a)=f(m\ell+a)\equiv b\pmod{q_{\ell}}$

for many multiples $n=m\ell\in\mathcal{N}_{f,a,b}$, a condition that we can
then study using the compositions $\\{f^{\chi}\\}_{\chi\pmod{q_{\ell}}}$.

######  Lemma 5.1.

Let $(x_{k})_{k}$ be the sequence for which (19) holds. Then there is a
collection of sets $\mathcal{P}_{\delta,k}$ of prime powers that satisfy

$\sum_{\begin{subarray}{c}p^{\nu}\leq x_{k}\\\
p^{\nu}\in\mathcal{P}_{\delta,k}\end{subarray}}\frac{1}{p^{\nu}}\ll\delta^{-2},\quad
k\geq 1$

such that if $k\geq k_{0}(\delta)$ and $p^{\nu}\leq x_{k}$,
$p^{\nu}\notin\mathcal{P}_{\delta,k}$ then

$|\\{n\leq x_{k}:n\in\mathcal{N}_{f,a,b},\,p^{\nu}||n\\}|\geq\frac{\delta
x_{k}}{4p^{\nu}}.$

###### Proof.

Let $k\geq k_{0}(\delta)$, and define $a_{n}:=1_{\mathcal{N}_{f,a,b}}(n)$ for
each $n\in\mathbb{N}$. For each $p^{\nu}\leq x_{k}$ define also

$\Delta_{p^{\nu}}(x_{k}):=\left|\frac{p^{\nu}}{x_{k}}\sum_{\begin{subarray}{c}n\leq
x_{k}\\\
p^{\nu}||n\end{subarray}}a_{n}-\left(1-\frac{1}{p}\right)\frac{1}{x_{k}}\sum_{n\leq
x_{k}}a_{n}\right|,$

and define

$\mathcal{P}_{\delta,k}:=\\{p^{\nu}\leq
x_{k}:\Delta_{p^{\nu}}(x_{k})>\delta/4\\}.$

By Lemma 3.2,

$\sum_{p^{\nu}\leq
x_{k}}\frac{\Delta_{p^{\nu}}(x_{k})^{2}}{p^{\nu}}\ll\frac{1}{x_{k}}\sum_{n\leq
x_{k}}|a_{n}|^{2}\ll 1,$

so that

$\sum_{\begin{subarray}{c}p^{\nu}\in\mathcal{P}_{\delta,k}\end{subarray}}\frac{1}{p^{\nu}}=\sum_{\begin{subarray}{c}p^{\nu}\leq
x_{k}\\\
\Delta_{p^{\nu}}(x_{k})>\delta/4\end{subarray}}\frac{1}{p^{\nu}}\leq\frac{16}{\delta^{2}}\sum_{p^{\nu}\leq
x_{k}}\frac{\Delta_{p^{\nu}}(x_{k})^{2}}{p^{\nu}}\ll\delta^{-2}.$

On the other hand, note that

$\sum_{\begin{subarray}{c}n\leq x_{k}\\\
p^{\nu}||n\end{subarray}}a_{n}=|\\{n\leq
x_{k}:n\in\mathcal{N}_{f,a,b},\,p^{\nu}||n\\}|,$

and using (19),

$\sum_{n\leq x_{k}}a_{n}=|\mathcal{N}_{f,a,b}\cap[1,x_{k}]|\geq\delta x_{k}.$

Hence, for each $p^{\nu}\leq x_{k}$ with $p^{\nu}\notin\mathcal{P}_{\delta,k}$
we have

$|\\{n\leq
x_{k}:n\in\mathcal{N}_{f,a,b},\,p^{\nu}||n\\}|\geq\frac{x_{k}}{p^{\nu}}\left(\delta\left(1-\frac{1}{p}\right)-\Delta_{p^{\nu}}(x_{k})\right)\geq\frac{\delta
x_{k}}{4p^{\nu}},$

as required. ∎

Set $\mathcal{P}_{f}:=\\{p^{\nu}:|f(p^{\nu})|\neq 0,1\\}$. Given
$m\in\mathbb{N}$ and $k\geq k_{0}(\delta)$ define also

$\mathcal{G}_{\delta,k}:=\mathcal{P}_{f}\backslash(\mathcal{P}_{\delta,k}\cup\mathcal{S}_{\delta}),\quad\mathcal{G}_{\delta,k;m}:=\\{p^{\nu}\in\mathcal{G}_{\delta,k}:(m,f(p^{\nu}))=1\\}.$

Combining Remark 4.5 and Lemma 5.1,

(20) $\sum_{\begin{subarray}{c}p^{\nu}\leq x_{k}\\\
p\in\mathcal{G}_{\delta,k}\end{subarray}}\frac{1}{p^{\nu}}=\sum_{\begin{subarray}{c}p^{\nu}\leq
x_{k}\\\
p^{\nu}\in\mathcal{P}_{f}\end{subarray}}\frac{1}{p^{\nu}}+O\left(\sum_{\begin{subarray}{c}p\leq
x_{k}\\\
p\in\mathcal{S}_{\delta}\end{subarray}}\frac{1}{p}+\sum_{\begin{subarray}{c}p^{\nu}\leq
x_{k}\\\
p^{\nu}\in\mathcal{P}_{\delta,k}\end{subarray}}\frac{1}{p^{\nu}}\right)=\log\log
x_{k}+O_{\delta}(1).$

The next lemma shows that (20) holds with $\mathcal{G}_{\delta,k}$ replaced by
$\mathcal{G}_{\delta,k;m}$, for any $m$ fixed.

######  Lemma 5.2.

For any $m\in\mathbb{N}$ we have

$\sum_{\begin{subarray}{c}p^{\nu}\leq x_{k}\\\
p^{\nu}\in\mathcal{G}_{\delta,k;m}\end{subarray}}\frac{1}{p^{\nu}}=\log\log
x_{k}+O_{\delta,\omega(m)}(1).$

###### Proof.

For each prime $\ell|m$ define the set

$\mathcal{B}_{\ell}:=\\{p^{\nu}\in\mathcal{P}_{f}:\ell|f(p^{\nu})\\},\quad\mathcal{B}_{m}:=\bigcup_{\ell|m}\mathcal{B}_{\ell}.$

Then $(m,f(p^{\nu}))>1$ if and only if $p^{\nu}\in\mathcal{B}_{m}$, i.e.,
$\mathcal{G}_{\delta,k;m}=\mathcal{G}_{\delta,k}\backslash\mathcal{B}_{m}$. We
will show that

(21) $\sum_{\begin{subarray}{c}p^{\nu}\leq x_{k}\\\
p^{\nu}\in\mathcal{B}_{m}\end{subarray}}\frac{1}{p^{\nu}}\ll_{\delta,\omega(m)}1,\quad
k\rightarrow\infty.$

Thus, assume for the sake of contradiction that (21) fails. For convenience,
given $\ell|m$ we introduce the notation

$B_{\ell}(y):=\sum_{\begin{subarray}{c}p^{\gamma}\leq y\\\
p^{\gamma}\in\mathcal{B}_{\ell}\end{subarray}}\frac{1}{p^{\gamma}},\quad y\geq
2,$

noting that $B_{m}(y)\rightarrow\infty$ as $y\rightarrow\infty$ by assumption.
Let $\nu:=\max_{\ell|m}\nu_{\ell}(b)$, and select
$k_{0}=k_{0}(\delta,\omega(m))$ sufficiently large so that

$B_{m}(x_{k})\geq\omega(m)\max\\{\delta^{-2},20(\nu+1)\\}\text{ for all }k\geq
k_{0}.$

By the union bound we have

(22)
$\max_{\ell|m}B_{\ell}(x_{k})\geq\frac{1}{\omega(m)}\sum_{\ell|m}B_{\ell}(x_{k})\geq\frac{1}{\omega(m)}B_{m}(x_{k})\geq\max\\{\delta^{-2},20(\nu+1)\\}.$

Let $\ell_{0}$ denote a prime factor of $m$ that maximises the left-hand side
of (22), and write

$\omega_{\ell_{0}}(n):=|\\{p^{\gamma}||n:p^{\gamma}\in\mathcal{B}_{\ell_{0}}\\}|=|\\{p^{\gamma}||n:\ell_{0}|f(p^{\gamma})\\}|,\quad
n\in\mathbb{N}.$

By Lemma 3.1,

$\displaystyle|\\{n\leq x_{k}:\omega_{\ell_{0}}(n)<B_{\ell_{0}}(x_{k})/2\\}|$
$\displaystyle\leq|\\{n\leq
x_{k}:|\omega_{\ell_{0}}(n)-B_{\ell_{0}}(x_{k})|>B_{\ell_{0}}(x_{k})/2\\}|$
$\displaystyle\ll\frac{1}{B_{\ell_{0}}(x_{k})^{2}}\sum_{n\leq
x_{k}}|\omega_{\ell_{0}}(n)-B_{\ell_{0}}(x_{k})|^{2}$ $\displaystyle\ll
x_{k}/B_{\ell_{0}}(x_{k}).$

Since $B_{\ell_{0}}(x_{k})\geq\delta^{-2}$, it follows that for all but
$O(\delta^{2}x_{k})$ integers $n\leq x_{k}$ we have

(23) $\min\\{\omega_{\ell_{0}}(n),\omega_{\ell_{0}}(n+a)\\}\geq
B_{\ell_{0}}(x_{k})/2\geq 10(\nu+1).$

If $\delta$ is small enough then by (19) there are $\geq\delta x_{k}/2$
integers $n\leq x_{k}$ for which

$f(n+a)=f(n)+b,$

and (23) holds. Now, since $f$ is multiplicative we have $f(p^{\gamma})|f(n)$
whenever $p^{\gamma}||n$, whence

$\ell_{0}^{\omega_{\ell_{0}}(n)}|f(n),\text{ i.e.
}\nu_{\ell_{0}}(f(n))\geq\omega_{\ell_{0}}(n).$

Therefore, by (23),

$\nu_{\ell_{0}}(f(n+a))\geq\min\\{\nu_{\ell_{0}}(f(n)),\nu_{\ell_{0}}(f(n+a))\\}\geq
10(\nu+1)>\nu_{\ell_{0}}(b).$

On the other hand, since $\nu_{\ell_{0}}(f(n))\neq\nu_{\ell_{0}}(b)$ the non-
archimedean property of $\nu_{\ell_{0}}$ yields

$\nu_{\ell_{0}}(f(n+a))=\nu_{\ell_{0}}(f(n)+b)=\min\\{\nu_{\ell_{0}}(f(n)),\nu_{\ell_{0}}(b)\\}\leq\nu_{\ell_{0}}(b),$

which is a contradiction. The claim follows. ∎

For $k\geq k_{0}(\delta)$ consider a prime $\ell\leq x_{k}$ with
$\ell\in\mathcal{G}_{\delta,k;2b}$. By choice, $f(\ell)$ is odd and

$\frac{\ell^{r}}{2}<|f(\ell)|<2\ell^{r}\text{ for some }0<r\ll_{\delta}1.$

In the sequel we fix121212Actually, any sufficiently large prime power divisor
of $f(\ell)$ would be suitable, but we make this choice for concreteness.

$q_{\ell}=\max\\{p^{\nu}:p^{\nu}||f(\ell)\\}.$

######  Remark 5.3.

Note that $q_{\ell}$ must be an odd prime power, so that the group of units
$(\mathbb{Z}/q_{\ell}\mathbb{Z})^{\times}$ is cyclic. We will use this
property several times in the sequel. Moreover, since $\omega(n)\leq
2\frac{\log n}{\log\log n}$ for all $n\geq n_{0}$, whenever $\ell$ is
sufficiently large we have

$q_{\ell}\geq|f(\ell)|^{1/\omega(|f(\ell)|)}\gg_{\delta}(\log\ell)^{1/2}.$

We are now in a position to state the main result of this section.

######  Proposition 5.4.

Let $f:\mathbb{N}\rightarrow\mathbb{Z}$ be a multiplicative function for which

$\sum_{p:|f(p)|\neq
1}\frac{1}{p}=\infty,\quad\sum_{p:f(p)=0}\frac{1}{p}<\infty.$

Assume moreover that there are positive integers $a\geq 1$ and $b\neq 0$, and
a $\delta\in(0,1/2)$ such that
$\overline{\delta}(\mathcal{N}_{f,a,b})>\delta$. Then there are integers
$A,D,k_{0},\ell_{0}=O_{\delta}(1)$ with $2|D$ such that the following holds.
If $k\geq k_{0}$ and
$\ell\in\mathcal{G}_{\delta,k;2b}\cap[\ell_{0},x_{k}^{1/A}]$ is prime then
there is a set of primes $\mathcal{T}_{\ell}\subseteq\mathcal{P}\cap[2,x_{k}]$
satisfying

$\sum_{\begin{subarray}{c}p\leq x_{k}\\\
p\in\mathcal{T}_{\ell}\end{subarray}}\frac{1}{p}=O_{\delta}(1)$

and a homomorphism

$\tilde{\rho}_{\ell}:(\mathbb{Z}/\ell\mathbb{Z})^{\times}\rightarrow(\mathbb{Z}/q_{\ell}\mathbb{Z})^{\times}$

such that for each $a\in(\mathbb{Z}/\ell\mathbb{Z})^{\times}$

(24) $p\equiv
a\pmod{\ell},\,p\in(\mathcal{P}\cap[2,x_{k}])\backslash\mathcal{T}_{\ell}\Rightarrow
f(p)^{D}\equiv\tilde{\rho}_{\ell}(a)\pmod{q_{\ell}}.$

Moreover, if $q_{\ell}$ is a power of $\ell$ then there is a $0\leq
g_{\ell}<\ell-1$ such that

(25) $p\in(\mathcal{P}\cap[2,x_{k}])\backslash\mathcal{T}_{\ell}\Rightarrow
f(p)^{D}\equiv p^{g_{\ell}}\pmod{\ell}.$

###  5.2. Deductions from pretentiousness

The proof of Proposition 5.4 relies on variants of the additive combinatorial
arguments employed in [19, Sec. 3], applied here to the groups of Dirichlet
characters to specific moduli. To deploy these we first need a few lemmas,
derived from the pretentious theory of multiplicative functions.
In the sequel, we assume that $\delta$ is smaller than any fixed absolute
constant (the condition $\overline{\delta}(\mathcal{N}_{f,a,b})>\delta$ can
only be weakened under this assumption). We also let $k_{0}(\delta)$ be larger
than any fixed constant in terms of $\delta$, and let $k\geq k_{0}(\delta)$.

######  Lemma 5.5.

For each prime
$\ell\in\mathcal{G}_{\delta,k;2b}\cap[\ell_{0}(\delta),\delta^{2}x_{k}]$ there
is a collection of non-principal characters $\mathcal{X}_{\ell}$ modulo
$q_{\ell}$ of size $|\mathcal{X}_{\ell}|\geq\delta\phi(q_{\ell})/8$ such that

(26) $\min_{\chi\in\mathcal{X}_{\ell}}\left|\sum_{\begin{subarray}{c}n\leq
x_{k}\\\ n\equiv a\pmod{\ell}\end{subarray}}f^{\chi}(n)\right|\geq\frac{\delta
x_{k}}{10\ell}.$

###### Proof.

Let $\ell\in\mathcal{G}_{\delta,k;2b}\cap[\ell_{0}(\delta),\delta^{2}x_{k}]$.
Since $\ell\in\mathcal{G}_{\delta,k}$, Lemma 5.1 yields

$|\\{m\leq x_{k}/\ell:\ell m\in\mathcal{N}_{f,a,b},\,\ell\nmid m\\}|=|\\{n\leq
x_{k}:n\in\mathcal{N}_{f,a,b},\,\ell||n\\}|\geq\frac{\delta x_{k}}{4\ell}.$

Suppose $\ell m\in\mathcal{N}_{f,a,b}$ with $\ell\nmid m$. Since
$q_{\ell}|f(\ell)$,

$f(\ell m+a)=f(\ell)f(m)+b\equiv b\pmod{q_{\ell}}.$

Thus, we find that

$\sum_{\begin{subarray}{c}n\leq x_{k}\\\ n\equiv
a\pmod{\ell}\end{subarray}}1_{f(n)\equiv
b\pmod{q_{\ell}}}=\sum_{\begin{subarray}{c}m\leq x_{k}/\ell\\\ f(\ell
m+a)\equiv b\pmod{q_{\ell}}\end{subarray}}1\geq\frac{\delta x_{k}}{4\ell}.$

Since $\ell\in\mathcal{G}_{\delta,k;2b}$ we have $(b,q_{\ell})=1$. Thus, by
the orthogonality of Dirichlet characters modulo $q_{\ell}$,

(27)
$\frac{1}{\phi(q_{\ell})}\sum_{\chi\pmod{q_{\ell}}}\overline{\chi}(b)\sum_{\begin{subarray}{c}n\leq
x_{k}\\\ n\equiv a\pmod{\ell}\end{subarray}}f^{\chi}(n)\geq\frac{\delta
x_{k}}{4\ell}.$

By Remark 5.3,

$\phi(q_{\ell})\geq q_{\ell}^{0.99}\geq(\log\ell)^{0.49}\text{ for
}\ell\geq\ell_{0}(\delta).$

Therefore, the contribution from the principal character modulo $q_{\ell}$ to
(27) is

$\leq\frac{1}{\phi(q_{\ell})}|\\{n\leq x_{k}:n\equiv
a\pmod{\ell}\\}|\leq\frac{\delta^{2}x_{k}}{\ell}.$

Now set

$\mathcal{X}_{\ell}:=\\{\chi\pmod{q_{\ell}}:\chi\neq\chi_{0},\,\eqref{eq:lowBdChar}\text{
holds}\\}.$

If $\delta$ is sufficiently small then by the triangle inequality and the
bound $\ell\leq\delta^{2}x_{k}$,

$\displaystyle\frac{\delta x_{k}}{4\ell}$
$\displaystyle\leq\frac{\delta^{2}x_{k}}{\ell}+\frac{1}{\phi(q_{\ell})}\sum_{\begin{subarray}{c}\chi\pmod{q_{\ell}}\\\
\chi\notin\mathcal{X}_{\ell}\cup\\{\chi_{0}\\}\end{subarray}}\left|\sum_{\begin{subarray}{c}n\leq
x_{k}\\\ n\equiv
a\pmod{\ell}\end{subarray}}f^{\chi}(n)\right|+\frac{1}{\phi(q_{\ell})}\sum_{\chi\in\mathcal{X}_{\ell}}\left|\sum_{\begin{subarray}{c}n\leq
x_{k}\\\ n\equiv a\pmod{\ell}\end{subarray}}f^{\chi}(n)\right|$
$\displaystyle<\frac{x_{k}}{\ell}\left(\delta^{2}+\frac{\delta}{10}\right)+\frac{|\mathcal{X}_{\ell}|}{\phi(q_{\ell})}\left(\frac{x_{k}}{\ell}+1\right)\leq\frac{x_{k}}{\ell}\left(\frac{\delta}{8}+\frac{|\mathcal{X}_{\ell}|}{\phi(q_{\ell})}\right)$

This conclusion follows upon rearranging. ∎

######  Lemma 5.6.

Let $\ell\in\mathcal{G}_{\delta,k;2b}$ be a prime satisfying
$\max\\{|a|,\ell_{0}(\delta)\\}<\ell\leq x_{k}^{1/A}$ for some
$A\geq\delta^{-10}$. Then for each $\chi\in\mathcal{X}_{\ell}$

$\min_{\psi\pmod{\ell}}\min_{|t|\leq\log
x_{k}}\mathbb{D}(f^{\chi},\psi(n)n^{it};x_{k})^{2}\leq 1.1\log(1/\delta).$

###### Proof.

Let $\chi\in\mathcal{X}_{\ell}$ and enumerate the characters
$\\{\psi\pmod{\ell}\\}=\\{\psi_{\chi,1},\psi_{\chi,2},\ldots,\psi_{\chi,\ell-1}\\}$
so that

$\min_{|t|\leq\log
x_{k}}\mathbb{D}(f^{\chi},\psi_{\chi,j}(n)n^{it};x_{k})\leq\min_{|t|\leq\log
x_{k}}\mathbb{D}(f^{\chi},\psi_{\chi,j+1}(n)n^{it};x_{k}),\quad 1\leq
j<\ell-1.$

In particular,

$\min_{\psi\pmod{\ell}}\min_{|t|\leq\log
x_{k}}\mathbb{D}(f^{\chi},\psi(n)n^{it};x_{k})^{2}=\min_{|t|\leq\log
x_{k}}\mathbb{D}(f^{\chi},\psi_{\chi,1}(n)n^{it};x_{k})^{2}=:M_{\chi}.$

By [6, Thm. 1.8], we have

$\left|\sum_{\begin{subarray}{c}n\leq x_{k}\\\ n\equiv
a\pmod{\ell}\end{subarray}}f^{\chi}(n)-\frac{\psi_{\chi,1}(a)}{\ell-1}\sum_{n\leq
x_{k}}f^{\chi}(n)\overline{\psi}_{\chi,1}(n)\right|\ll\frac{x_{k}}{\ell}\frac{\log
A}{A^{1-1/\sqrt{2}}}\ll\delta^{2}\frac{x_{k}}{\ell}.$

Writing $\psi_{\chi}=\psi_{\chi,1}$ for convenience, we combine this with (26)
and $\ell\nmid a$ to obtain

$\left|\sum_{n\leq
x_{k}}f^{\chi}(n)\overline{\psi}_{\chi}(n)\right|\geq\frac{\delta x_{k}}{20},$

for small enough $\delta$. Applying Theorem 3.6 with $T=\log x_{k}$, the left-
hand side of the previous estimate is

$\ll x_{k}(1+M_{\chi})e^{-M_{\chi}}+\frac{x_{k}\log\log x_{k}}{\log x_{k}}.$

We deduce upon rearranging that when $\delta$ is sufficiently small,
$M_{\chi}\leq 1.1\log(1/\delta)$, as claimed. ∎

From now on, given $\chi\pmod{q_{\ell}}$ we select a character $\psi_{\chi}$
modulo $\ell$ that satisfies

$\min_{\psi\pmod{\ell}}\min_{|t|\leq\log
x_{k}}\mathbb{D}(f^{\chi},\psi(n)n^{it};x_{k})=\min_{|t|\leq\log
x_{k}}\mathbb{D}(f^{\chi},\psi_{\chi}(n)n^{it};x_{k}),$

and refer to it as the _minimising character_ for $\chi$. (If more than one
such character exists modulo $\ell$ for a given $\chi$ we choose any of them.)
To prove Proposition 5.4 we will show the following.

######  Lemma 5.7.

Let $\delta\in(0,1/2)$ be small. Let $A\geq\delta^{-10}$, and let
$\ell\in\mathcal{G}_{\delta,k;2b}$ be a prime with
$\max\\{|a|,\ell_{0}(\delta)\\}<\ell\leq x_{k}^{1/A}$. Then there is a
(cyclic) subgroup $H_{\ell}=\langle\tilde{\chi}\rangle$ of the character group
$\pmod{q_{\ell}}$ satisfying the following properties:

  1. (i)

$|H_{\ell}|\gg_{\delta}\phi(q_{\ell})$

  2. (ii)

the minimising character $\psi=\psi_{\tilde{\chi}}$ for $\tilde{\chi}$
satisfies $\text{ord}(\psi)\mid|H_{\ell}|$

  3. (iii)

we have

(28) $\max_{0\leq
j\leq|H_{\ell}|-1}\mathbb{D}(f^{\tilde{\chi}^{j}},\psi^{j};x_{k})\ll_{\delta}1.$

The proof of Lemma 5.7 relies on the following inverse sumset lemma.

######  Lemma 5.8.

Let $\eta>0$ and $M\geq 1$. Let $G=\mathbb{Z}/M\mathbb{Z}$ be the cyclic group
of order $M$, and let $B\subseteq G$ be a symmetric131313We say that a subset
$B$ of a cyclic group $\mathbb{Z}/N\mathbb{Z}$ is _symmetric_ when $b\in B$ if
and only if $-b\in B$. subset with $|B|\geq\eta M$. Then there is an integer
$m=O_{\eta}(1)$ and a $d|M$ with $d\geq\eta M$ such that $mB=H$ is a subgroup
of $G$ with $|H|=d$.

###### Proof.

Consider the sequence of sumsets $(2^{i}B)_{i\geq 1}$, and let $j\geq 0$ be
minimal such that

$|2^{j+1}B|=|2^{j}B+2^{j}B|<\frac{3}{2}|2^{j}B|.$

Note that as $B$ is symmetric, so is $2^{j}B$. Thus, by a lemma due to Freiman
[5], $2^{j+1}B$ is in fact a subgroup of $G$. Since $|2^{j}B|\leq|G|$ we find

$M\geq|2^{j}B|\geq\left(\frac{3}{2}\right)^{j-1}|B|\geq\left(\frac{3}{2}\right)^{j-1}\eta
M,$

so that $j=O(\log(2/\eta))$. Taking $m=2^{j+1}=O_{\eta}(1)$, it follows that
$mB=H$ for some subgroup $H\leq G$.
Now $G$ is cyclic, so $H$ must be as well. By Lagrange’s theorem, $d=|H|$
divides $M$. Furthermore, as $|H|=|mB|\geq|B|\geq\eta M$ we find $d\geq\eta
M$, and the proof is complete. ∎

As in the proof of [18, Prop. 3.3], we will make crucial use of the following.

######  Lemma 5.9 (Ruzsa).

Let $(G,\cdot)$ be an abelian group, and let $K\geq 0$. Let
$\phi:G\rightarrow\mathbb{R}$ be a map satisfying

$|\phi(x\cdot y)-\phi(x)-\phi(y)|\leq K\text{ for all }x,y\in G.$

Then there is a genuine homomorphism $\psi:G\rightarrow\mathbb{R}$ such that

$\sup_{x\in G}|\phi(x)-\psi(x)|\leq K.$

###### Proof.

This is[23, Statement (7.3)]. ∎

###### Proof of Lemma 5.7.

Let $\max\\{|a|,\ell_{0}(\delta)\\}<\ell\leq x_{k}^{1/A}$ be a prime with
$\ell\in\mathcal{G}_{\delta,2b;k}$. Since $A\geq\delta^{-10}$, Lemma 5.6 shows
that there is a set $\mathcal{X}_{\ell}$ of non-principal characters $\chi$
modulo $q_{\ell}$ for which there is a choice of minimising141414If there are
several possible choices of $t_{\chi}$ pick the one of minimal absolute value.
$t_{\chi}\in[-\log x_{k},\log x_{k}]$ and $\psi_{\chi}\pmod{\ell}$ for which

$\mathbb{D}(f^{\chi},\psi_{\chi}(n)n^{it_{\chi}};x_{k})^{2}\leq
1.1\log(1/\delta).$

Let $\chi_{q_{\ell}}$ be a generator for the (cyclic) group of characters
modulo $q_{\ell}$, and for each $\chi\pmod{q_{\ell}}$ let
$m_{\chi}\in\mathbb{Z}/\phi(q_{\ell})\mathbb{Z}$ be such that
$\chi=\chi_{q_{\ell}}^{m_{\chi}}$. Below, given a set $\Xi$ of characters
modulo $q_{\ell}$ we define the _index set of $\Xi$_ to be

$\mathcal{I}(\Xi):=\\{m_{\chi}:\chi\in\Xi\\}\subset\mathbb{Z}/\phi(q_{\ell})\mathbb{Z}.$

Let now

$\tilde{\mathcal{X}_{\ell}}:=\\{\chi_{1}\overline{\chi}_{2}:\chi_{1},\chi_{2}\in\mathcal{X}_{\ell}\\}.$

We observe that if $\chi_{1}\overline{\chi}_{2}\in\tilde{\mathcal{X}_{\ell}}$,
with $\chi_{j}\in\mathcal{X}_{\ell}$ for $j=1,2$, then as
$f^{\chi_{1}\overline{\chi}_{2}}=f^{\chi_{1}}\overline{f^{\chi_{2}}}$ the
pretentious triangle inequality yields

$\displaystyle\min_{\psi\pmod{\ell}}\min_{|t|\leq 2\log
x_{k}}\mathbb{D}(f^{\chi_{1}\overline{\chi}_{2}},\psi(n)n^{it};x_{k})$
$\displaystyle\leq\mathbb{D}(f^{\chi_{1}\overline{\chi}_{2}},\psi_{\chi_{1}}\overline{\psi}_{\chi_{2}}(n)n^{i(t_{\chi_{1}}-t_{\chi_{2}})};x_{k})$
$\displaystyle\leq\sum_{j=1,2}\mathbb{D}(f^{\chi_{j}},\psi_{\chi_{j}}(n)n^{it_{j}};x_{k})$
(29) $\displaystyle\leq 2.2\sqrt{\log(1/\delta)}.$

We extend the definitions of $(\psi_{\chi},t_{\chi})$ to all
$\chi\in\tilde{\mathcal{X}_{\ell}}\backslash\mathcal{X}_{\ell}$ by selecting
these to satisfy

$\min_{\psi\pmod{\ell}}\min_{t_{\chi}\in[-2\log x_{k},2\log
x_{k}]}\mathbb{D}(f^{\chi},\psi(n)n^{it};x_{k})=\mathbb{D}(f^{\chi},\psi_{\chi}(n)n^{it_{\chi}};x_{k}).$

Now, consider the index set $\mathcal{I}(\tilde{\mathcal{X}_{\ell}})$.
Clearly, $0\in\mathcal{I}(\tilde{\mathcal{X}_{\ell}})$ and

$m\in\mathcal{I}(\tilde{X}_{\ell})\text{ if and only if
}-m\in\mathcal{I}(\tilde{X}_{\ell}).$

By Lemma 5.8, there is a positive integer $r_{\ell}=O_{\delta}(1)$ and a
subgroup $H_{\ell}$ of the group of characters $\pmod{q_{\ell}}$ with
$|H_{\ell}|\gg_{\delta}\phi(q_{\ell})$ such that

(30) $\mathcal{I}(H_{\ell})\subseteq
r_{\ell}\mathcal{I}(\tilde{\mathcal{X}_{\ell}})=\\{a_{1}+\cdots+a_{r_{\ell}}:a_{j}\in\mathcal{I}(\tilde{X}_{\ell})\text{
for }1\leq j\leq r_{\ell}\\}.$

Set $d_{\ell}:=|H_{\ell}|$. There is a choice of generator $\tilde{\chi}$ for
$H_{\ell}$ such that $m_{\ell}:=m_{\tilde{\chi}}$ satisfies
$m_{\ell}=\phi(q_{\ell})/d_{\ell}=O_{\delta}(1)$, and

$H_{\ell}=\\{\tilde{\chi}^{j}:\,0\leq j\leq
d_{\ell}-1\\}=\\{\chi_{q_{\ell}}^{jm_{\ell}}:\,0\leq j\leq d_{\ell}-1\\}.$

Together with (30), the above parametrisation of $H_{\ell}$ implies that for
each $0\leq j\leq d_{\ell}-1$ we have a representation

$jm_{\ell}=m_{\chi_{1}}+\cdots+m_{\chi_{r_{\ell}}},\text{ with
}m_{\chi_{i}}\in\mathcal{I}(\tilde{\mathcal{X}_{\ell}})\text{ for each }1\leq
i\leq r_{\ell}.$

This immediately implies that

(31)
$\tilde{\chi}^{j}=\chi_{1}\cdots\chi_{r_{\ell}},\quad\chi_{i}\in\tilde{\mathcal{X}}_{\ell}.$

Combining (31) with (16) and (5.2), we find

$\displaystyle\min_{\psi\pmod{\ell}}\min_{|t|\leq 2r_{\ell}\log
x_{k}}\mathbb{D}(f^{\tilde{\chi}^{j}},\psi(n)n^{it};x_{k})$
$\displaystyle\leq\mathbb{D}(f^{\chi_{1}}\cdots
f^{\chi_{r_{\ell}}},\psi_{\chi_{1}}\cdots\psi_{\chi_{r_{\ell}}}(n)n^{i(t_{\chi_{1}}+\cdots+t_{\chi_{r_{\ell}}})};x_{k})$
$\displaystyle\leq\sum_{1\leq s\leq
r_{\ell}}\mathbb{D}(f^{\chi_{s}},\psi_{\chi_{s}}(n)n^{it_{\chi_{s}}};x_{k})$
(32) $\displaystyle\leq r_{\ell}\max_{1\leq s\leq
r_{\ell}}\mathbb{D}(f^{\chi_{s}},\psi_{\chi_{s}}(n)n^{it_{\chi_{s}}};x_{k})\leq
2.2r_{\ell}\sqrt{\log(1/\delta)},$

uniformly in $0\leq j\leq d_{\ell}-1$.
Finally, we extend the definitions of $\psi_{\chi}$ and $t_{\chi}$ to the
remaining characters in $\Xi_{\ell}\backslash\tilde{\mathcal{X}_{\ell}}$ so
that

$\mathbb{D}(f^{\chi},\psi_{\chi}(n)n^{it_{\chi}};x_{k})=\min_{\psi\pmod{\ell}}\min_{|t|\leq
4r_{\ell}\log x_{k}}\mathbb{D}(f^{\chi},\psi(n)n^{it};x_{k}).$

We will show that the maps $\gamma_{\ell}:H_{\ell}\rightarrow\Xi_{\ell}$ and
$\theta_{\ell}:H_{\ell}\rightarrow\mathbb{R}$ given by

$\gamma_{\ell}(\chi):=\psi_{\chi},\quad\theta_{\ell}(\chi):=t_{\chi}\log
x_{k},$

have the following properties:

  1. (a)

$\gamma_{\ell}$ is a homomorphism on $H_{\ell}$, and

  2. (b)

there is $K=O_{\delta}(1)$ such that $\theta_{\ell}$ is a _$K$ -approximate
homomorphism_, i.e., such that

$\max_{\chi_{1},\chi_{2}\in
H_{\ell}}|\theta_{\ell}(\chi_{1}\chi_{2})-\theta_{\ell}(\chi_{1})\theta_{\ell}(\chi_{2})|\leq
K.$

Note that (32) implies that

(33) $\max_{\chi\in
H_{\ell}}\mathbb{D}(f^{\chi},\psi_{\chi}(n)n^{it_{\chi}};x_{k})\leq
2.2r_{\ell}\sqrt{\log(1/\delta)}.$

If $\tilde{\chi}^{j}$ has the representation (31) then, uniformly over all
$0\leq j\leq d_{\ell}-1$,

$\displaystyle\mathbb{D}(\psi_{\tilde{\chi}^{j}}\overline{\psi}_{\chi_{1}}\cdots\overline{\psi}_{\chi_{r_{\ell}}},n^{i(t_{\tilde{\chi}^{j}}-t_{\chi_{1}}-\cdots-
t_{\chi_{r_{\ell}}})};x_{k})$
$\displaystyle\leq\mathbb{D}(f^{\tilde{\chi}^{j}},\psi_{\tilde{\chi}^{j}}(n)n^{it_{\tilde{\chi}^{j}}};x_{k})+\mathbb{D}(f^{\chi_{1}}\cdots
f^{\chi_{r_{\ell}}},\psi_{\chi_{1}}\cdots\psi_{\chi_{r_{\ell}}}n^{i(t_{\chi_{1}}+\cdots+t_{\chi_{r_{\ell}}})};x_{k})$
$\displaystyle\leq 2r_{\ell}\max_{1\leq
s\leq{r_{\ell}}}\mathbb{D}(f^{\chi_{s}},\psi_{\chi_{s}}(n)n^{it_{\chi_{s}}};x_{k})\leq
4.4r_{\ell}\sqrt{\log(1/\delta)}.$

Since $r_{\ell}=O_{\delta}(1)$, Lemma 3.3 implies that for $\eta$ sufficiently
small in terms of $\delta$ and $\ell\leq x^{1/\eta}$ we have

$\psi_{\tilde{\chi}^{j}}=\psi_{\chi_{1}}\cdots\psi_{\chi_{r_{\ell}}},$

and moreover

$t_{\tilde{\chi}^{j}}=t_{\chi_{1}}+\cdots+t_{\chi_{r_{\ell}}}+O_{\delta}\left(\frac{1}{\log
x_{k}}\right).$

Similarly, if $\xi_{1},\xi_{2}\in H_{\ell}$ then by (32), (33), the minimal
property of $\psi_{\xi_{1}\xi_{2}}$ and $t_{\xi_{1}\xi_{2}}$, and (15) again,

$\displaystyle\mathbb{D}(\psi_{\xi_{1}\xi_{2}}\overline{\psi}_{\xi_{1}}\overline{\psi}_{\xi_{2}},n^{i(t_{\xi_{1}+\xi_{2}}-t_{\xi_{1}}-t_{\xi_{2}})};x_{k})$
$\displaystyle\leq\mathbb{D}(f^{\xi_{1}\xi_{2}},\psi_{\xi_{1}\xi_{2}}(n)n^{it_{\xi_{1}\xi_{2}}};x_{k})+\mathbb{D}(f^{\xi_{1}\xi_{2}},\psi_{\xi_{1}}\psi_{\xi_{2}}(n)n^{i(t_{\xi_{1}}+t_{\xi_{2}})};x_{k})$
$\displaystyle\leq
2\mathbb{D}(f^{\xi_{1}\xi_{2}},\psi_{\xi_{1}}\psi_{\xi_{2}}(n)n^{i(t_{\xi_{1}}+t_{\xi_{2}})};x_{k})$
$\displaystyle\leq
4\max_{s=1,2}\mathbb{D}(f^{\xi_{s}},\psi_{\xi_{s}}(n)n^{it_{\xi_{s}}};x_{k})\leq
8.8r_{\ell}\sqrt{\log(1/\delta)}.$

Thus, since $|t_{\xi_{1}\xi_{2}}-t_{\xi_{1}}-t_{\xi_{2}}|\leq 12r_{\ell}\log
x_{k}$ and $r_{\ell}=O_{\delta}(1)$, again by Lemma 3.3 we obtain that
whenever $\chi_{1},\chi_{2}\in H_{\ell}$,

$\displaystyle\gamma_{\ell}(\chi_{1}\chi_{2})$
$\displaystyle=\psi_{\chi_{1}\chi_{2}}=\psi_{\chi_{1}}\psi_{\chi_{2}}=\gamma_{\ell}(\chi_{1})\gamma_{\ell}(\chi_{2}),$
$\displaystyle\theta_{\ell}(\chi_{1}\chi_{2})$
$\displaystyle=t_{\chi_{1}\chi_{2}}\log x_{k}=(t_{\chi_{1}}+t_{\chi_{2}})\log
x_{k}+O_{\delta}(1)$
$\displaystyle=\theta_{\ell}(\chi_{1})+\theta_{\ell}(\chi_{2})+O_{\delta}(1).$

Thus, $\gamma_{\ell}$ is a homomorphism on $H_{\ell}$, while $\theta_{\ell}$
is a $K$-approximate homomorphism from $H_{\ell}$ to $\mathbb{R}$ for some
$K=O_{\delta}(1)$, confirming (a) and (b) above.
Note that there are no non-zero homomorphisms from a finite abelian group to
$\mathbb{R}$. By Lemma 5.9, (b) therefore implies

$\max_{\chi\in H_{\ell}}|t_{\chi}|=\max_{\chi\in
H_{\ell}}\left|\frac{\theta_{\ell}(\chi)}{\log x_{k}}\right|\leq\frac{K}{\log
x_{k}}.$

Taylor expanding $p^{it_{\chi}}$ for $p\leq x_{k}^{1/(3K)}$, we find that for
any $\chi\in H_{\ell}$,

$\mathbb{D}(1,n^{it_{\chi}};x_{k}^{1/(3K)})^{2}\leq\sum_{p\leq
x_{k}^{1/(3K)}}\frac{|1-p^{it_{\chi}}|}{p}\ll\frac{K}{\log x_{k}}\sum_{p\leq
x_{k}^{1/(3K)}}\frac{\log p}{p}=O_{\delta}(1).$

Combining this with (15) and (33),

(34) $\mathbb{D}(f^{\chi},\psi_{\chi}(n);x_{k})^{2}\leq
2\left(\mathbb{D}(f^{\chi},\psi_{\chi}(n)n^{it_{\chi}};x_{k}^{1/(3K)})^{2}+\mathbb{D}(1,n^{it_{\chi}};x_{k}^{1/(3K)})^{2}\right)+\sum_{x_{k}^{1/3K}\leq
p\leq x_{k}}\frac{2}{p}\ll_{\delta}1,$

uniformly over $\chi\in H_{\ell}$.
We can now complete the proof. By construction,
$|H_{\ell}|\gg_{\delta}\phi(q_{\ell})$, so (i) holds. Next, as $H_{\ell}$ is
cyclic, $\psi_{\tilde{\chi}}=\gamma_{\ell}(\tilde{\chi})$ generates the
subgroup $\gamma_{\ell}(H_{\ell})$ of $\Xi_{\ell}$. Since

$\psi_{\tilde{\chi}}^{d_{\ell}}=\gamma_{\ell}(\tilde{\chi})^{d_{\ell}}=\gamma_{\ell}(\tilde{\chi}^{d_{\ell}})$

is the trivial character modulo $\ell$, it follows that
$\psi=\psi_{\tilde{\chi}}$ has order dividing $d_{\ell}$, verifying (ii).
Finally, as each $\chi\in H_{\ell}$ is of the form $\tilde{\chi}^{j}$ for some
$0\leq j\leq d_{\ell}-1$, we have

$\psi_{\chi}=\gamma(\tilde{\chi})^{j}=\psi^{j},$

and so

$\max_{\chi\in H_{\ell}}\mathbb{D}(f^{\chi},\psi_{\chi};x_{k})=\max_{0\leq
j\leq d_{\ell}-1}\mathbb{D}(f^{\tilde{\chi}^{j}},\psi^{j};x_{k}).$

Thus, (iii) follows from (34). ∎

###### Proof of Proposition 5.4.

Let $A:=\delta^{-10}$. Let $\ell\in\mathcal{G}_{\delta,k;2b}$ be a prime with
$\max\\{|a|,\ell_{0}(\delta)\\}<\ell\leq x_{k}^{1/A}$. Let $\chi_{q_{\ell}}$
be a generator of the cyclic group $\Xi_{q_{\ell}}$. By Lemma 5.7, we find a
subgroup $H_{\ell}=\langle\tilde{\chi}\rangle\leq\Xi_{q_{\ell}}$ with
$|H_{\ell}|\gg_{\delta}\phi(q_{\ell})$ on which (28) holds. A choice of
generator $\tilde{\chi}=\chi_{q_{\ell}}^{m_{\ell}}$ can be made so that
$m_{\ell}=\phi(q_{\ell})/|H_{\ell}|=O_{\delta}(1)$. By (28),

(35) $\sum_{p\leq
x_{k}}\frac{1}{p}\text{Re}\left(1-\frac{1}{|H_{\ell}|}\sum_{0\leq
j\leq|H_{\ell}|-1}(\tilde{\chi}(f(p))\overline{\psi}(p))^{j}\right)=\frac{1}{|H_{\ell}|}\sum_{0\leq
j\leq|H_{\ell}|-1}\mathbb{D}(f^{\tilde{\chi}^{j}},\psi^{j};x_{k})^{2}\ll_{\delta}1.$

By Lemma 5.7(ii), $\psi^{|H_{\ell}|}$ is principal. Thus, for $p\leq x_{k}$ we
have

$\frac{1}{|H_{\ell}|}\sum_{0\leq
j\leq|H_{\ell}|-1}(\tilde{\chi}(f(p))\overline{\psi}(p))^{j}=1_{\tilde{\chi}(f(p))\overline{\psi}(p)=1}.$

Inserting this into (35), we find

$\sum_{\begin{subarray}{c}p\leq x_{k}\\\
\tilde{\chi}(f(p))\neq\psi(p)\end{subarray}}\frac{1}{p}=\sum_{p\leq
x_{k}}\frac{1}{p}(1-1_{\tilde{\chi}(f(p))=\psi(p)})\ll_{\delta}1.$

Note that $\psi$ takes values in the set $\mu_{\phi(q_{\ell})}$ of roots of
unity of order $\phi(q_{\ell})$. As $\chi_{q_{\ell}}$ is a bijection from
$(\mathbb{Z}/q_{\ell}\mathbb{Z})^{\times}$ onto that set, there is an induced
map

$\rho_{\ell}:(\mathbb{Z}/\ell\mathbb{Z})^{\times}\to(\mathbb{Z}/q_{\ell}\mathbb{Z})^{\times}$

such that

$\chi_{q_{\ell}}(\rho_{\ell}(a))=\psi(a)\text{ for all
}a\in(\mathbb{Z}/\ell\mathbb{Z})^{\times}.$

It is easily checked that $\rho_{\ell}$ is a homomorphism: since
$\chi_{q_{\ell}}$ is a bijection it suffices to show that

$\chi_{q_{\ell}}(\rho_{\ell}(ab))=\chi_{q_{\ell}}(\rho_{\ell}(a)\rho_{\ell}(b))\text{
for any }a,b\in(\mathbb{Z}/\ell\mathbb{Z})^{\times},$

and by definition,

$\chi_{q_{\ell}}(\rho_{\ell}(ab))=\psi(ab)=\psi(a)\psi(b)=\chi_{q_{\ell}}(\rho_{\ell}(a))\chi_{q_{\ell}}(\rho_{\ell}(b))=\chi_{q_{\ell}}(\rho_{\ell}(a)\rho_{\ell}(b)).$

Finally, set

$\mathcal{T}_{\ell}:=\\{p\leq x_{k}:\tilde{\chi}(f(p))\neq\psi(p)\\}$

and let $p\leq x_{k}$ with $p\notin\mathcal{T}_{\ell}$. As
$\tilde{\chi}=\chi_{q_{\ell}}^{m_{\ell}}$, we deduce that

$\text{if }p\equiv a\pmod{\ell}\text{ then
}f(p)^{m_{\ell}}\equiv\rho_{\ell}(a)\pmod{q_{\ell}}.$

Since $m_{\ell}=O_{\delta}(1)$ uniformly over all
$\ell\in\mathcal{G}_{\delta,k;2b}\cap[2,x_{k}^{1/A}]$ (sufficiently large
relative to $\delta$ and $|a|$), there is an integer $M=O_{\delta}(1)$,
independent of $k$, such that $m_{\ell}|M!$ for all such $\ell$. If we set
$D:=2M!$ and define the homomorphism
$\tilde{\rho}_{\ell}(a):=\rho_{\ell}(a)^{D/m_{\ell}}\pmod{q_{\ell}}$, we
obtain the conclusion (24) uniformly over all
$\ell\in\mathcal{G}_{\delta,k;2b}\cap[2,x_{k}^{1/A}]$ sufficiently large, as
required.
Suppose now that $q_{\ell}$ is a power of $\ell$, for
$\ell\in\mathcal{G}_{\delta,k;2b}$. Composing the homomorphism
$\tilde{\rho}_{\ell}$ with the projection
$(\mathbb{Z}/q_{\ell}\mathbb{Z})^{\times}\twoheadrightarrow(\mathbb{Z}/\ell\mathbb{Z})^{\times}$,
we obtain an endomorphism

$\rho^{\ast}_{\ell}:(\mathbb{Z}/\ell\mathbb{Z})^{\times}\to(\mathbb{Z}/\ell\mathbb{Z})^{\times}.$

Since $(\mathbb{Z}/\ell\mathbb{Z})^{\times}$ is cyclic, select $u$ to be a
primitive root modulo $\ell$ and define $0\leq g_{\ell}<\ell-1$ implicitly
from the formula $\rho^{\ast}_{\ell}(u)\equiv u^{g_{\ell}}\pmod{\ell}$. Then
whenever $p\notin\mathcal{T}_{\ell}$, $p\neq\ell$, and $p\equiv
u^{\theta_{p}}\pmod{\ell}$ we find

$f(p)^{D}\equiv\rho^{\ast}_{\ell}(u^{\theta_{p}})\pmod{\ell}\equiv\rho^{\ast}_{\ell}(u)^{\theta_{p}}\pmod{\ell}\equiv
u^{g_{\ell}\theta_{p}}\pmod{\ell}\equiv p^{g_{\ell}}\pmod{\ell},$

and (25) follows as well. ∎

##  6\. Local and global power maps

###  6.1. The Fabrykowski-Subbarao Conjecture and a result of N. Jones

Let $\ell$ be a prime. Recall that a a map $F:\mathbb{N}\rightarrow\mathbb{Z}$
is said to be a _local power map_ modulo $\ell$ if there is an integer $0\leq
g_{\ell}<\ell-1$ such that

$F(n)\equiv n^{g_{\ell}}\pmod{\ell}\text{ for all }n\in\mathbb{N}.$

If $F$ is a completely multiplicative function then $F$ is a local power map
modulo $\ell$ if and only if

(36) $F(p)\equiv p^{g_{\ell}}\pmod{\ell}\text{ for all }p\in\mathcal{P}.$

For comparison, the conclusion of Proposition 5.4 states that the map
$F(n)=f(n)^{D}$ satisfies

(37) $F(p)\equiv p^{g_{\ell}}\pmod{\ell}\text{ for all }p\leq
x_{k},\,p\notin\mathcal{T}_{\ell},$

for each $\ell\in\mathcal{G}_{\delta,k;2b}\cap[\ell_{0},x_{k}^{1/A}]$ with
$\ell|f(\ell)$. That is, $f^{D}$ behaves like a local power map at all such
primes $\ell$, with the complications arising from the exceptional set
$\mathcal{T}_{\ell}$ and the potential dependence of $g_{\ell}$ on the scale
$x_{k}$.
Fabrykowski and Subbarao conjectured that a multiplicative function that is a
local power map modulo infinitely many primes must be a global power map,
i.e., a monomial.

######  Conjecture 6.1 (Fabrykowski-Subbarao, [3]).

Suppose $F:\mathbb{N}\rightarrow\mathbb{Z}$ is a multiplicative function such
that for infinitely many primes $\ell$,

$F(n+\ell)\equiv F(n)\pmod{\ell}\text{ for all $n\in\mathbb{N}$.}$

Then there is a non-negative integer $k$ such that $F(n)=n^{k}$ for all
$n\in\mathbb{N}$.

######  Lemma 6.2.

Conjecture 6.1 is equivalent to the following statement:
Let $F:\mathbb{N}\rightarrow\mathbb{Z}$ be a completely multiplicative
function for which there is an infinite sequence of primes $S_{F}$ with the
property that for each $\ell\in S_{F}$ there is an integer $0\leq
g_{\ell}<\ell-1$ such that

(38) $F(n)\equiv n^{g_{\ell}}\pmod{\ell}\text{ for all }n\in\mathbb{N}.$

Then there is a non-negative integer $k$ such that $F(n)=n^{k}$ for all
$n\in\mathbb{N}$.

###### Proof.

Conjecture 6.1 trivially implies this conjecture, so it suffices to show that
if $f$ satisfies the hypotheses of Conjecture 6.1 then it must be completely
multiplicative and satisfy (38) for some $0\leq g_{\ell}<\ell-1$ and each
$\ell\in S_{F}$.
For $d\in\mathbb{N}$ let $S_{F}(d):=\\{\ell\in S_{F}:\ell\nmid d\\}$, and let
$m,n\in\mathbb{N}$. For each $\ell\in S_{F}(mn)$ select distinct primes
$q_{m},q_{n}$ such that $q_{k}\equiv k\pmod{\ell}$ for each $k\in\\{m,n\\}$;
such primes exist by Dirichlet’s theorem on primes in arithmetic progressions.
It follows that $q_{m},q_{n}$ are coprime, and moreover $mn\equiv
q_{m}q_{n}\pmod{\ell}$. Thus, $F(mn)\equiv F(q_{m}q_{n})\pmod{\ell}$, and
moreover by multiplicativity we get

$F(q_{m}q_{n})=F(q_{m})F(q_{n}).$

This implies that

$F(mn)\equiv F(q_{m}q_{n})\pmod{\ell}\equiv F(q_{m})F(q_{n})\pmod{\ell}\equiv
F(m)F(n)\pmod{\ell}.$

We thus obtain that

$\ell|(F(mn)-F(m)F(n))\text{ for all }\ell\in S_{F}(mn).$

Since $S_{F}$ is an infinite set, so is $S_{F}(mn)$, and we deduce that
$F(mn)=F(m)F(n)$. As $m,n$ were arbitrary, $F$ must be completely
multiplicative.
Next, fix $\ell\in S_{F}$ and let $\chi_{\ell}$ be a generator of
$\Xi_{\ell}$. By (a), $F^{\chi_{\ell}}$ is a completely multiplicative
function, and moreover since $F$ is periodic modulo $\ell$ we have

$F^{\chi_{\ell}}(n+\ell)=F^{\chi_{\ell}}(n)\text{ for all }n\in\mathbb{N}.$

Thus, $F^{\chi_{\ell}}$ is completely multiplicative, periodic modulo $\ell$
and satisfies $F^{\chi_{\ell}}(n)=0$ whenever $\ell|n$. By definition,
$F^{\chi_{\ell}}$ must be a Dirichlet character modulo $\ell$. Since
$\chi_{\ell}$ generates the group of such characters there must therefore
exist $0\leq g_{\ell}<\ell-1$ such that

$\chi_{\ell}(F(n))=F^{\chi_{\ell}}(n)=\chi_{\ell}^{g_{\ell}}(n)=\chi_{\ell}(n^{g_{\ell}})\text{
for all }n.$

Since $\chi_{\ell}$ is injective on $\mathbb{Z}/\ell\mathbb{Z}$, we deduce
that $F(n)\equiv n^{g_{\ell}}\pmod{\ell}$ for all $n$, as required. ∎

Conjecture 6.1 remains open, but partial results exist under the assumption
that $S_{F}(X)$ grows somewhat quickly. In particular, N. Jones [9] proved
that if $\limsup_{X\rightarrow\infty}S_{F}(X)/\pi(X)>0$ then $F$ must be a
monomial.
In light of the similarities between (37) and (36), we apply Jones’ method to
derive structural information about $f$ (through $f^{D}$) provided
sufficiently many $\ell|f(\ell)$.
For $X\geq 2$ define

$S_{f}:=\\{\ell\in\mathcal{P}:\,\ell|f(\ell)\\}\subseteq\mathcal{P}_{f},\quad
S_{f}(X):=|S_{f}\cap[2,X]|.$

Using Jones’ method, we prove the following.

######  Proposition 6.3.

Let $f:\mathbb{N}\rightarrow\mathbb{Z}$ be a multiplicative function for which

$\sum_{p:|f(p)|\neq
1}\frac{1}{p}=\infty,\quad\sum_{p:f(p)=0}\frac{1}{p}<\infty,$

and also that

$\lim_{X\rightarrow\infty}\frac{1}{\log\log X}\sum_{\begin{subarray}{c}p\leq
X\\\ p\in S_{f}\end{subarray}}\frac{1}{p}>0.$

Suppose moreover that there are integers $a\geq 1$ and $b\neq 0$, and a
$\delta\in(0,1/2)$ such that $\overline{\delta}(\mathcal{N}_{f,a,b})>\delta$.
Then the set

(39) $\\{\ell\in\mathcal{P}:\ell^{\prime}\nmid f(\ell)\text{ for all
}\ell^{\prime}\neq\ell\\}$

is $O_{\delta}(1)$-sparse.
The same conclusion holds under the assumption of the Extended Riemann
Hypothesis, provided that

$\sum_{p\in S_{f}}\frac{1}{p}=\infty.$

That is, if $\ell|f(\ell)$ for a positive Dirichlet density set of primes
$\ell$ then, outside of an $O_{\delta}(1)$-sparse set,
$f(\ell)=\ell^{\alpha_{\ell}}$ for some $\alpha_{\ell}\in\mathbb{N}$.
As a complement to Proposition 6.3, we classify all multiplicative functions
$f$ for which $f(\ell)$ is a power of $\ell$ for all but a sparse set of
$\ell$.

######  Proposition 6.4.

Assume that $f$ satisfies the hypotheses of Proposition 6.3, and that the set

(40) $\\{\ell\in\mathcal{P}:\ell^{\prime}\nmid f(\ell)\text{ for all
}\ell^{\prime}\neq\ell\\}$

is sparse. Then the following properties must hold:

  1. (i)

$|f(\ell)|=\ell$ for all but an $O_{\delta}(1)$-sparse set of primes $\ell$

  2. (ii)

if $f$ is completely multiplicative then there is a divisor $d|a$ such that
$f(d)|b$, and $a/d$ divides $b/f(d)$.

###  6.2. Proof of Proposition 6.3

We prove Proposition 6.3 by appealing to elements of the work [9]. As a first
step towards applying the ideas therein, we address the nature of the
exceptional sets $\mathcal{T}_{\ell}$, for $\ell\in\mathcal{G}_{\delta,k;2b}$.
Below, given a prime $p\leq x_{k}$ we set

$\mathcal{T}(p):=\\{\ell\in\mathcal{G}_{\delta,k;2b}\cap[2,x_{k}]:p\in\mathcal{T}_{\ell}\\}.$

We would like to show that for many primes $p$, $\mathcal{T}(p)$ is a _small_
subset of $\mathcal{G}_{\delta,k;2b}\cap[2,x_{k}]$, as then we can deduce
information on the behaviour of $f(p)^{D}\pmod{\ell}$ for many primes
$\ell\in\mathcal{G}_{\delta,k;2b}$. This is implied by the following simple
lemma.

######  Lemma 6.5.

With the notation of Proposition 5.4, let $y_{k}:=x_{k}^{1/A}$, let
$\mathcal{U}\subseteq\mathcal{G}_{\delta,k;2b}\cap[\ell_{0},y_{k}]$ be a non-
empty set of primes and put $\mathcal{U}(x):=\mathcal{U}\cap[2,x]$. Let $2\leq
P\leq x_{k}$ and let $\tau\in(0,1)$. Then the set of primes $p\leq P$ for
which

(41)
$\sum_{\ell\in\mathcal{T}(p)\cap\mathcal{U}(y_{k})}\frac{1}{\ell}>\tau\sum_{\ell\in\mathcal{U}(y_{k})}\frac{1}{\ell}$

holds satisfies

$\sum_{\begin{subarray}{c}p\leq P\\\ \eqref{eq:TpBig}\text{
holds}\end{subarray}}\frac{1}{p}\ll_{\delta}\tau^{-1}.$

###### Proof.

By Proposition 5.4 we have

$\max_{\begin{subarray}{c}\ell\in\mathcal{G}_{\delta,k;2b}\\\
\ell_{0}\leq\ell\leq y_{k}\end{subarray}}\sum_{\begin{subarray}{c}p\leq
x_{k}\\\ p\in\mathcal{T}_{\ell}\end{subarray}}\frac{1}{p}\ll_{\delta}1.$

Thus, by Markov’s inequality

$\sum_{\begin{subarray}{c}p\leq P\\\ \eqref{eq:TpBig}\text{
holds}\end{subarray}}\frac{1}{p}\leq\tau^{-1}\left(\sum_{\ell\in\mathcal{U}(y_{k})}\frac{1}{\ell}\right)^{-1}\sum_{p\leq
P}\frac{1}{p}\sum_{\begin{subarray}{c}\ell\in\mathcal{U}(y_{k})\\\
\ell\in\mathcal{T}(p)\end{subarray}}\frac{1}{\ell}=\tau^{-1}\left(\sum_{\ell\in\mathcal{U}(y_{k})}\frac{1}{\ell}\right)^{-1}\sum_{\begin{subarray}{c}\ell\in\mathcal{U}(y_{k})\end{subarray}}\frac{1}{\ell}\sum_{\begin{subarray}{c}p\leq
P\\\ p\in\mathcal{T}_{\ell}\end{subarray}}\frac{1}{p}\ll_{\delta}\tau^{-1},$

as claimed. ∎

We will also need the following well-known result.

######  Lemma 6.6 (Brun-Titchmarsh Inequality).

Let $x\geq 100$ and let $1\leq q<x/50$. Then

$\max_{\begin{subarray}{c}a\pmod{q}\\\
(a,q)=1\end{subarray}}\pi(x;q,a)\ll\frac{x}{\phi(q)\log(x/q)}.$

###### Proof.

This follows from [8, Thm. 6.6]. ∎

We will also use a “Brun-Titchmarsh” variant of the Chebotarev density
theorem, due to Lagarias, Montgomery and Odlyzko [15]. To state this we recall
some algebraic preliminaries.
Given a Galois number field $L/\mathbb{Q}$ and a rational prime $p$ that does
not ramify in $L$, let $\mathfrak{p}\subseteq L$ be an ideal lying above $p$.
Let $\mathcal{O}_{L}$ denote the ring of integers of $L$, and set
$F_{\mathfrak{p}}:=\mathcal{O}_{L}/\mathfrak{p}\mathcal{O}_{L}$,
$F_{p}:=\mathbb{Z}/p\mathbb{Z}$ as the respective residue fields of
$\mathfrak{p}$ in $L$ and $p$ in $\mathbb{Q}$. Writing $D_{\mathfrak{p}}$ to
denote the decomposition group of $\mathfrak{p}$, we recall that the
_Frobenius element_ $\text{Frob}_{p}$ associated to $p$ is the conjugacy class
in the Galois group $G:=\text{Gal}(L/\mathbb{Q})$ of the Frobenius
automorphisms of $\mathfrak{p}$ in $\text{Gal}(F_{\mathfrak{p}}/F_{p})$,
viewed as an element of $D_{\mathfrak{p}}$ (this class being independent of
the choice of $\mathfrak{p}$ above $p$). That is,

$\text{Frob}_{p}(\beta)\equiv\beta^{p}\pmod{\mathfrak{p}}\text{ for all
}\beta\in\mathcal{O}_{L}.$

Given a union of conjugacy classes $\mathcal{C}$ of elements of $G$, we let

$\pi_{\mathcal{C}}(x,L/\mathbb{Q}):=|\\{p\leq x:\,p\text{ unramified in
}L,\,\text{Frob}_{p}\in\mathcal{C}\\}|.$

######  Theorem 6.7 (Lagarias-Odlyzko [16]; Lagarias-Montgomery-Odlyzko [15]).

Let $L/\mathbb{Q}$ be a Galois number field with Galois group $G$ and absolute
discriminant $D_{L}$. Let $\mathcal{C}\subseteq G$ be a union of conjugacy
classes of $G$. Then there are absolute constants $C_{1},C_{2}>0$ such that if

(42) $\log x\geq C_{1}(\log D_{L})(\log\log D_{L})(\log\log\log(C_{2}D_{L}))$

then we have

$\pi_{\mathcal{C}}(x,L/\mathbb{Q})\ll\frac{|\mathcal{C}|}{|G|}\pi(x),$

the implicit constant being absolute.
Under the assumption of ERH, we may replace (42) by the range

$x\gg(\log D_{L})^{2}(\log\log D_{L})^{4}.$

In the sequel, by a _Kummer extension_ of $\mathbb{Q}$ we mean a number field
$L/\mathbb{Q}$ of the form

$L=\mathbb{Q}(\zeta_{m},\alpha_{1}^{1/m},\ldots,\alpha_{d}^{1/m}),$

where $m>1$ is an integer, $\zeta_{m}$ is a primitive $m$th root of unity, and
$\alpha_{1},\ldots,\alpha_{d}\in\mathbb{Q}^{+}$ with $d\geq 1$. Note that $L$
is the splitting field of the polynomial $\prod_{1\leq i\leq
d}(X^{m}-\alpha_{i})$, thus necessarily Galois.

###### Proof of Proposition 6.3.

We will give full details of the proof of the unconditional part of
Proposition 6.3. As the details are largely the same we simply give a sketch
of the necessary modifications required for the ERH-conditional part in Remark
6.8, below.
We follow the strategy of the proof of [9, Thm. 1.7] with $K=\mathbb{Q}$ and
$A=\mathbb{N}$ in the notation there, but must take care to deal with those
primes $p$ for which the local power condition $f(p)^{D}\equiv
p^{g_{\ell}}\pmod{\ell}$ fails.
Let $\mathcal{L}_{f}$ be the set of primes in (39). We assume for the sake of
contradiction that $\mathcal{L}_{f}$ is not sparse, i.e., that

$L_{f}(y):=\sum_{\begin{subarray}{c}\ell\leq y\\\
\ell\in\mathcal{L}_{f}\end{subarray}}\frac{1}{\ell}\rightarrow\infty,\quad
y\rightarrow\infty.$

Let $X\geq X_{0}(\delta)$ and suppose $k\geq k_{0}(\delta)$ is chosen large
enough so that $y_{k}=x_{k}^{1/A}\geq X$, where $A$ is as given in Proposition
5.4. By assumption, there is $s_{f}>0$ such that

$\sum_{\begin{subarray}{c}\ell\leq X\\\ \ell\in
S_{f}\end{subarray}}\frac{1}{\ell}\sim s_{f}\log\log X,\quad
X\rightarrow\infty.$

To obtain a contradiction we will show on the other hand that as
$X\rightarrow\infty$,

$\sum_{\begin{subarray}{c}\ell\leq X\\\ \ell\in
S_{f}\end{subarray}}\frac{1}{\ell}=o(\log\log X).$

Applying Lemma 5.2, note that

$\sum_{\begin{subarray}{c}\ell\leq X\\\ \ell\in
S_{f}\end{subarray}}\frac{1}{\ell}\leq\sum_{\begin{subarray}{c}\ell\leq X\\\
\ell\in
S_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}+\sum_{\begin{subarray}{c}\ell\leq
x_{k}\\\
\ell\notin\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}=\sum_{\begin{subarray}{c}\ell\leq
X\\\ \ell\in
S_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}+O_{\delta}(1),$

so we focus on bounding the contribution from
$S_{f}\cap\mathcal{G}_{\delta,k;2b}$.
Let $2\leq Y\leq Z\leq(\log X)^{1/6}$, with $Y,Z$ being chosen later as
slowly-growing functions of $X$ that satisfy

$\frac{\log Z}{\log Y},\,\frac{\log\log X}{\log Z}\rightarrow\infty,\text{ as
}X\rightarrow\infty.$

We also set $P:=\tfrac{1}{10}Y^{1/(r+1)}$, with $r$ given by Proposition 4.1.
In the sequel, for $m\geq 1$ we define the sets

$\mathfrak{P}_{m}:=\\{\ell\in\mathcal{S}_{f}\cap\mathcal{G}_{\delta,k;2b}:\ell\equiv
1\pmod{m}\\},\quad\mathfrak{P}_{m}(y):=\mathfrak{P}_{m}\cap[2,y].$

We have the trivial upper bound

$\displaystyle\sum_{\begin{subarray}{c}\ell\leq X\\\ \ell\in
S_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}$
$\displaystyle\leq\sum_{\begin{subarray}{c}\ell\leq X\\\ \ell\not\equiv
1\pmod{m}\\\ \forall\
m\in[Y,Z]\end{subarray}}\frac{1}{\ell}+\sum_{\begin{subarray}{c}Y\leq m\leq
Z\\\ m\text{
prime}\end{subarray}}\sum_{\begin{subarray}{c}\ell\in\mathfrak{P}_{m}(X)\end{subarray}}\frac{1}{\ell}$
(43) $\displaystyle=:\mathcal{E}(X)+\sum_{\begin{subarray}{c}Y\leq m\leq Z\\\
m\text{ prime}\end{subarray}}\mathcal{H}_{m}(X).$

Step 1: Estimation of $\mathcal{E}(X)$
Observe that if $\ell\leq Y$ the condition $m\nmid(\ell-1)$ is trivial for all
$Y\leq m\leq Z$. On the other hand, if $v>Y$ then by Lemma 3.7,

$\displaystyle\sum_{\begin{subarray}{c}\ell\leq v\\\ \ell\not\equiv
1\pmod{m}\\\ \forall\,m\in[Y,Z]\end{subarray}}1$
$\displaystyle\leq\sum_{\begin{subarray}{c}n\leq v\\\ n\not\equiv 1\pmod{m}\\\
\forall\,m\notin[Y,\min\\{v,Z\\}]\end{subarray}}1_{p|n\Rightarrow p>v^{1/10}}$
$\displaystyle\ll\frac{v}{\log
v}\exp\left(-\sum_{Y<p\leq\min\\{v,Z\\}}\frac{1}{p}+\sum_{v^{1/10}<p\leq
v}\frac{1}{p}\right)$ $\displaystyle\ll\frac{\log
Y}{\log\min\\{v,Z\\}}\frac{v}{\log v}.$

Thus, by partial summation we obtain

$\displaystyle\mathcal{E}(X)$ $\displaystyle\leq\sum_{\ell\leq
Y}\frac{1}{\ell}+\int_{Y}^{X}\left(\sum_{\begin{subarray}{c}\ell\leq v\\\
\ell\not\equiv 1\pmod{m}\\\
\forall\,m\in[Y,Z]\end{subarray}}1\right)\frac{dv}{v^{2}}+O\left(\frac{1}{\log
Y}\right)$ $\displaystyle\ll\log\log Y+(\log Y)\int_{Y}^{Z}\frac{dv}{v(\log
v)^{2}}+\frac{\log Y}{\log Z}\int_{Z}^{X}\frac{dv}{v\log v}$ (44)
$\displaystyle\ll\log\log Y+\frac{\log Y}{\log Z}\log\log X.$

In the remainder of the argument we will show that for each prime $m\in[Y,Z]$,

$\mathcal{H}_{m}(X)\ll\frac{1}{m^{2}}\log\log X+\frac{1}{m}\log Z.$

Step 2: Constructing a suitable Kummer extension
In [9, Sec. 5], in order to bound quantities analogous to $\mathcal{H}_{m}(X)$
Jones makes heavy use of Kummer theory, which is well-exposed in his article.
We will merely quote as a black box the relevant facts about Kummer
extensions, as needed.
For the time being, fix a prime $m\in[Y,Z]$. We claim that we can find primes
$p_{1},p_{2}\leq P$ with the properties

  1. (i)

$p_{1},p_{2}\notin\mathcal{S}_{\delta}$,

  2. (ii)

$p_{1}\nmid f(p_{2})$ and $p_{2}\nmid f(p_{1})$, and

  3. (iii)

for both $p=p_{1}$ and $p=p_{2}$ we have

(45)
$\sum_{\ell\in\mathcal{T}(p)\cap\mathfrak{P}_{m}(X)}\frac{1}{\ell}\leq\frac{1}{100}\sum_{\ell\in\mathfrak{P}_{m}(X)}\frac{1}{\ell}.$

Recall that by assumption, $L_{f}(P)\rightarrow\infty$ with $P$, so we assume
that $P$ (and thus $X$) are as large as desired in an absolute sense. Applying
Lemma 6.5 with $\mathcal{U}=\mathfrak{P}_{m}\cap[2,X]$, we see that the set of
primes $p\leq P$ with

(46)
$\sum_{\ell\in\mathcal{T}(p)\cap\mathfrak{P}_{m}(X)}\frac{1}{\ell}>\frac{1}{100}\sum_{\ell\in\mathfrak{P}_{m}(X)}\frac{1}{\ell}$

has a sum of reciprocals satisfying

(47) $\sum_{\begin{subarray}{c}p\leq P\\\ \eqref{eq:largeTp}\text{
holds}\end{subarray}}\frac{1}{p}\ll_{\delta}1.$

Let $P_{1}\in[2,P]$ be chosen minimally so that $L_{f}(P_{1})\geq
L_{f}(P)^{1/2}$. By (47) and Proposition 4.1,

$\sum_{\begin{subarray}{c}p\leq P_{1}\\\ p\in\mathcal{L}_{f}\backslash
S_{\delta}\\\ \eqref{eq:largeTp}\text{ fails}\end{subarray}}\frac{1}{p}\geq
L_{f}(P_{1})-\sum_{\begin{subarray}{c}p\leq x_{k}\\\ p\in
S_{\delta}\end{subarray}}\frac{1}{p}+O_{\delta}\left(1\right)\geq\frac{1}{2}L_{f}(P)^{1/2}.$

Thus, we may select $p_{1}\in(\mathcal{L}_{f}\backslash
S_{\delta})\cap[2,P_{1}]$ such that (45) holds for $p=p_{1}$. Furthermore,
taking $r^{\prime}:=10(r+1)$ and combining (21) and (47), we have

$\displaystyle\sum_{\begin{subarray}{c}P_{1}^{r^{\prime}}\leq p\leq P\\\
p\in\mathcal{L}_{f}\backslash S_{\delta}\\\ \eqref{eq:largeTp}\text{ fails}\\\
p_{1}\nmid f(p)\end{subarray}}\frac{1}{p}$
$\displaystyle\geq\sum_{\begin{subarray}{c}P_{1}\leq p\leq P\\\
p\in\mathcal{L}_{f}\end{subarray}}\frac{1}{p}-\sum_{\begin{subarray}{c}p\leq
P\\\ p_{1}|f(p)\end{subarray}}\frac{1}{p}-\sum_{\begin{subarray}{c}P_{1}\leq
p\leq
P_{1}^{r^{\prime}}\end{subarray}}\frac{1}{p}-\sum_{\begin{subarray}{c}p\leq
x_{k}\\\ p\in
S_{\delta}\end{subarray}}\frac{1}{p}-\sum_{\begin{subarray}{c}p\leq P\\\
\eqref{eq:largeTp}\text{ holds}\end{subarray}}\frac{1}{p}$
$\displaystyle=L_{f}(P)-L_{f}(P_{1})-B_{p_{1}}(P)-O_{\delta}\left(1\right)\geq
L_{f}(P)-2L_{f}(P)^{1/2}$ $\displaystyle\geq\frac{1}{2}L_{f}(P),$

for $P$ sufficiently large. Thus, we may select
$p_{2}\in(\mathcal{L}_{f}\backslash\mathcal{S}_{\delta})\cap[P_{1}^{r^{\prime}},P]$
with $p_{1}\nmid f(p_{2})$ and such that (46) fails and thus (45) holds for
$p=p_{2}$. Moreover, since $p_{1}\notin\mathcal{S}_{\delta}$ we have
$|f(p_{1})|\leq 2p_{1}^{r}<2P_{1}^{r^{\prime}/2}\leq p_{2}$, so $p_{2}\nmid
f(p_{1})$. The primes $p_{1},p_{2}$ thus satisfy the required conditions (i),
(ii) and (iii) above.
Now, let $\zeta_{m}$ be a primitive root of unity of order $m$, let
$F(n):=f(n)^{D}$ and denote by $L_{m}$ the Kummer extension

$L_{m}:=\mathbb{Q}(\zeta_{m},p_{1}^{1/m},p_{2}^{1/m},F(p_{1})^{1/m},F(p_{2})^{1/m}).$

Let also $p_{3}\notin\\{p_{1},p_{2}\\}$ be a prime such that $p_{3}|f(p_{1})$.
Following the proof of Case 1 of Lemma 5.8 of [9] (which is the only case of
interest to us there given our assumption on $\mathcal{L}_{f}$), we find upon
setting $c_{f}:=\nu_{p_{3}}(F(p_{1}))$ that

$[L_{m}:\mathbb{Q}(\zeta_{m})]\geq m^{3}\text{ whenever $m>c_{f}$}.$

The condition $m>c_{f}$ is automatically satisfied when $m\geq Y$ and $X$ is
sufficiently large, since by virtue of $p_{1}\leq P\leq Y^{1/(r+1)}$ we find

$c_{f}\leq 2\log|f(p_{1})|<(r+1)\log P\leq\log Y.$

Since also $[\mathbb{Q}(\zeta_{m}):\mathbb{Q}]=m-1$ for prime $m$, the tower
property for degrees of number fields yields

(48) $[L_{m}:\mathbb{Q}]\geq m^{3}(m-1)\text{ for all }Y\leq m\leq Z.$

For later reference, we note that the set of $p$ that ramify in $L_{m}$ are
precisely those dividing the absolute discriminant $D_{L_{m}}$, and by [9,
Lem. 5.2],

$D_{L_{m}}\text{ divides
}(p_{1}p_{2}f(p_{1}p_{2}))^{[L_{m}:\mathbb{Q}]}m^{5[L_{m}:\mathbb{Q}]}.$

In particular, $\ell\equiv 1\pmod{m}$ is unramified whenever $\ell\nmid
p_{1}p_{2}f(p_{1}p_{2})$. Furthermore, as $P^{r+1}<Y\leq m$, and since
$|f(p_{i})|\leq P^{r+1}$ for $i=1,2$, the trivial bound
$[L_{m}:\mathbb{Q}]\leq m^{4}(m-1)$ leads to

(49) $\log D_{L_{m}}\leq[L_{m}:\mathbb{Q}]\log(P^{2(r+2)}m^{5})\ll m^{5}\log
m,$

a bound that we will invoke shortly.
Step 3: Estimation of $\mathcal{H}_{m}(X)$ using Theorem 6.7
Having defined $L_{m}$, we now split

$\displaystyle\mathcal{H}_{m}(X)=\sum_{\ell\in\mathfrak{P}_{m}(X)}\frac{1}{\ell}\leq\sum_{\begin{subarray}{c}\ell\in\mathfrak{P}_{m}(X)\\\
\ell\nmid p_{1}p_{2}f(p_{1}p_{2})\\\ f(p_{i})^{D}\equiv
p_{i}^{g_{\ell}}\pmod{\ell}\\\
i=1,2\end{subarray}}\frac{1}{\ell}+\sum_{\begin{subarray}{c}\ell|p_{1}p_{2}f(p_{1}p_{2})\\\
\ell\equiv
1\pmod{m}\end{subarray}}\frac{1}{\ell}+\sum_{\begin{subarray}{c}\ell\in\mathfrak{P}_{m}(X)\\\
p_{1}\text{ or }p_{2}\in\mathcal{T}_{\ell}\end{subarray}}\frac{1}{\ell}.$

Since $p_{1},p_{2}\leq P$ and $p_{1},p_{2}\notin\mathcal{S}_{\delta}$, we have

$\max\\{p_{1},p_{2},|f(p_{1})|,|f(p_{2})|\\}\leq P^{r+1}<Y\leq m.$

Thus, $\ell\nmid p_{1}p_{2}f(p_{1}p_{2})$ for any prime $\ell\equiv
1\pmod{m}$, as each of these must obviously exceed $m$. In particular,

$\sum_{\begin{subarray}{c}\ell|p_{1}p_{2}f(p_{1}p_{2})\\\ \ell\equiv
1\pmod{m}\end{subarray}}\frac{1}{\ell}=0.$

Furthermore, by the union bound, the definition of $\mathcal{T}(p_{i})$ and
property (iii) above, we have

$\sum_{\begin{subarray}{c}\ell\in\mathfrak{P}_{m}(X)\\\ p_{1}\text{ or
}p_{2}\in\mathcal{T}_{\ell}\end{subarray}}\frac{1}{\ell}\leq\sum_{\ell\in\mathcal{T}(p_{1})\cap\mathfrak{P}_{m}(X)}\frac{1}{\ell}+\sum_{\ell\in\mathcal{T}(p_{2})\cap\mathfrak{P}_{m}(X)}\frac{1}{\ell}\leq\frac{1}{50}\sum_{\ell\in\mathfrak{P}_{m}(X)}\frac{1}{\ell}=\frac{1}{50}\mathcal{H}_{m}(X).$

Thus, upon rearranging we deduce that

(50)
$\mathcal{H}_{m}(X)\ll\sum_{\begin{subarray}{c}\ell\in\mathfrak{P}_{m}(X)\\\
\ell\nmid p_{1}p_{2}f(p_{1}p_{2})\\\ f(p_{i})^{D}\equiv
p_{i}^{d_{\ell}}\pmod{\ell}\\\ i=1,2\end{subarray}}\frac{1}{\ell}.$

Note that the primes in the sum on the right-hand side of (50) are all
unramified in $L_{m}$, and by [9, Cor. 5.11] there is a conjugacy class
$\mathcal{C}_{4}$ of prime ideals of $L_{m}$ such that

$\text{if }\ell\in\mathfrak{P}_{m}(X)\text{ and }\ell\nmid
p_{1}p_{2}f(p_{1}p_{2})\text{ then }\text{Frob}_{\ell}\in\mathcal{C}_{4}.$

Let now $2\leq\tilde{X}\leq X$ be defined implicitly by

$\log\tilde{X}=CZ^{5}(\log Z)^{3},$

where $C>0$ is a large absolute constant to be specified shortly. Splitting
the sum in (50) at $X$ and applying partial summation, we deduce that

(51) $\mathcal{H}_{m}(X)\ll\sum_{\begin{subarray}{c}\ell\leq X\\\ \ell\equiv
1\pmod{m}\\\
\text{Frob}_{\ell}\in\mathcal{C}_{4}\end{subarray}}\frac{1}{\ell}\ll\sum_{\begin{subarray}{c}m<\ell\leq\tilde{X}\\\
\ell\equiv
1\pmod{m}\end{subarray}}\frac{1}{\ell}+\int_{\tilde{X}}^{X}\frac{\pi_{\mathcal{C}_{4}}(v,L_{m}/\mathbb{Q})}{v^{2}}dv+\frac{1}{m\log\tilde{X}}.$

By Lemma 6.6 and partial summation,

$\displaystyle\sum_{\begin{subarray}{c}m<\ell\leq\tilde{X}\\\ \ell\equiv
1\pmod{m}\end{subarray}}\frac{1}{\ell}$
$\displaystyle\ll\sum_{\begin{subarray}{c}m<n\leq m^{10}\\\ n\equiv
1\pmod{m}\end{subarray}}\frac{1}{n}+\int_{m^{10}}^{\tilde{X}}\frac{\pi(v;m,1)}{v^{2}}dv+\frac{1}{m\log
m}$ $\displaystyle\ll\frac{\log
m}{m}+\frac{1}{m}\log\log\tilde{X}\ll\frac{1}{m}\log Z.$

Next, as $p_{1}\neq p_{2}$ we have
$[\mathbb{Q}(\zeta_{m},p_{1}^{1/m},p_{2}^{1/m}):\mathbb{Q}]=m^{2}(m-1)$, so we
may combine (48) with [9, Lem. 5.12] to obtain

$\frac{|\mathcal{C}_{4}|}{\text{Gal}(L_{m}/\mathbb{Q})}\leq\frac{2}{m(m-1)}.$

Moreover, for each $Y\leq m\leq Z$ and each $\tilde{X}\leq v\leq X$ (with $C$
chosen sufficiently large in the definition of $\tilde{X}$) Theorem 6.7 gives

$\pi_{\mathcal{C}_{4}}(v,L_{m}/\mathbb{Q})\ll\frac{|\mathcal{C}_{4}|}{|\text{Gal}(L_{m}/\mathbb{Q})|}\pi(v)\ll\frac{v}{m^{2}\log
v}.$

Inserting this bound into (51) for $v\geq\tilde{X}$, and bounding trivially
elsewhere, we obtain

$\mathcal{H}_{m}(X)\ll\frac{1}{m^{2}}\int_{\tilde{X}}^{X}\frac{dv}{v\log
v}+\frac{1}{m}(\log Z+1)\ll\frac{1}{m^{2}}\log\log X+\frac{1}{m}\log Z,$

uniformly over primes $m\in[Y,Z]$.
Concluding the proof:
Summing over the primes $Y\leq m\leq Z$ and inserting the resulting bound
together with (44) into (6.2), we obtain

(52) $\sum_{\begin{subarray}{c}\ell\leq X\\\ \ell\in
S_{f}\end{subarray}}\frac{1}{\ell}\ll\left(\frac{\log Y}{\log
Z}+\frac{1}{Y\log Y}\right)\log\log X+(\log Z)\log\left(\frac{\log Z}{\log
Y}\right)+\log\log Y.$

We now select

$Y=(\log\log X)^{1/2},\quad Z=\exp((\log\log X)^{1/2}),$

so that $Y\leq Z\leq(\log X)^{1/6}$, as needed. Then

$\sum_{\begin{subarray}{c}\ell\leq X\\\ \ell\in
S_{f}\end{subarray}}\frac{1}{\ell}\ll(\log\log X)^{1/2}\log\log\log X,$

which is $o(\log\log X)$ as $X\rightarrow\infty$, as claimed. ∎

######  Remark 6.8.

The constraint $\log y\gg m^{5}(\log m)^{3}$ required to apply Theorem 6.7
limited the choices of $Y$ and $Z$ in the above proof, and we may do much
better by assuming the Extended Riemann Hypothesis. As stated in Theorem 6.7,
for any conjugacy class $\mathcal{C}\subseteq\text{Gal}(L/K)$ one has under
ERH that

$\pi_{\mathcal{C}}(y,L/\mathbb{Q})\ll\frac{|\mathcal{C}|}{|G|}\frac{y}{\log
y}\text{ for }y\gg(\log D_{L})^{2}(\log\log D_{L})^{4}.$

In particular, when $L=L_{m}$ with $m\in[Y,Z]$ as in the proof above, we may
instead take $\tilde{X}=Z^{10}(\log Z)^{6}$.
Using $\tilde{X}>Y$ and keeping track only of the primes $\tilde{X}<\ell\leq
X$ (which has the effect that the first term in each of the bounds (44) and
(51) can be removed), the above proof gives

(53) $\sum_{\begin{subarray}{c}\tilde{X}<\ell\leq X\\\
\ell\in\mathcal{S}_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}\ll\left(\frac{\log
Y}{\log Z}+\frac{1}{Y\log Y}\right)\log\log X+\frac{\log\log
Z}{\log\tilde{X}},$

which is valid as long as $X$ is sufficiently large subject to the upper bound
$X\leq x_{k}$.
Set now $J:=\lfloor\log\log X\rfloor$. For each $j_{0}\leq j\leq J$, where
$j_{0}\gg_{\delta}1$, take

$Y_{j}=j^{12},\,Z_{j}=\exp(j^{20}),\,\tilde{X}_{j}=Z_{j}^{10}(\log
Z_{j})^{6}\text{ and }X_{j}=e^{e^{j}}.$

Applying (53) with $X,\tilde{X},Y$ and $Z$ replaced by
$X_{j},\tilde{X}_{j},Y_{j}$ and $Z_{j}$, respectively, we find

$\sum_{\begin{subarray}{c}X_{j-1}<\ell\leq X_{j}\\\
\ell\in\mathcal{S}_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}\leq\sum_{\begin{subarray}{c}\exp(20j^{20})<\ell\leq
X_{j}\\\
\ell\in\mathcal{S}_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}\leq\sum_{\begin{subarray}{c}\tilde{X}_{j}<\ell\leq
X_{j}\\\
\ell\in\mathcal{S}_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}\ll\frac{1}{j^{10}}$

(the constructions of the extensions $L_{m}$ may be relativised to
$m\in[Y_{j},Z_{j}]$, as long as $Y_{j},Z_{j}$ are sufficiently large with
respect to $\delta$). Since $X_{J}\leq X<X_{J+1}$, summing over $j_{0}\leq
j\leq J$ yields

$\sum_{\begin{subarray}{c}\ell\leq X\\\
\ell\in\mathcal{S}_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}\leq\sum_{j_{0}+1\leq
j\leq J}\sum_{\begin{subarray}{c}X_{j-1}<\ell\leq X_{j}\\\ \ell\in
S_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}+O_{\delta}(1)\ll\sum_{j>j_{0}}\frac{1}{j^{10}}+O_{\delta}(1)\ll_{\delta}1.$

Combined with Lemma 5.2, we thus obtain

$\sum_{\begin{subarray}{c}\ell\leq X\\\ \ell\in
S_{f}\end{subarray}}\frac{1}{\ell}\leq\sum_{\begin{subarray}{c}\ell\leq X\\\
\ell\in
S_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}+\sum_{\begin{subarray}{c}\ell\leq
x_{k}\\\
\ell\notin\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}\ll_{\delta}1,$

uniformly over $k$, and thus over $X$. We hence deduce assuming ERH that
$S_{f}$ must be $O_{\delta}(1)$-sparse, which contradicts the hypotheses of
Proposition 6.3.

######  Remark 6.9.

One may ask whether the full strength of the ERH is actually needed in the
conditional proof. In fact, the success of our method relies only on the
convergence as $J\rightarrow\infty$ of the series

$\sum_{j_{0}<j\leq J}\sum_{\begin{subarray}{c}X_{j-1}<\ell\leq X_{j}\\\
\ell\in S_{f}\cap\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}.$

For this to work, it is enough to be able to take $Z_{j}$ so that $\log
Z_{j}\geq(\log\log X_{j})^{1+c}$ for some $c>0$. While this range of
parameters is not accessible using unconditional estimates in Theorem 6.7 (the
range available is rather of the form $\log Z_{j}\geq(\log\log X_{j})^{c}$,
with $c\in(0,1/5)$), it does hold if one assumes the existence of fairly
narrow zero-free regions for all of the Hecke $L$-functions of suitable cyclic
subfields of each of the extensions $L_{m}$, $m\in[Y,Z]$. For instance,
applying [16, Thm. 7.1], we see that if $\mathbb{Q}\subseteq E_{m}\subseteq
L_{m}$ has (cyclic) Galois subgroup $H_{m}\leq\text{Gal}(L_{m}/\mathbb{Q})$
then we have

$\psi_{\mathcal{C}}(x,L_{m}/\mathbb{Q}):=\sum_{\begin{subarray}{c}p^{k}\leq
x\\\ \text{Frob}_{p}\in\mathcal{C}\end{subarray}}\log
p\ll\frac{|\mathcal{C}|}{|\text{Gal}(L_{m}/\mathbb{Q})|}x$

as long as $m\leq Z\leq x^{1/6}$ (so that $n_{L_{m}}\leq\log D_{L_{m}}\ll
m^{5}\log m=o(x)$) and each of the Hecke $L$-functions
$L(s,\chi,L_{m}/E_{m})$, $\chi\in H_{m}$, has no zeroes in a region

$\text{Re}(s)>1-\delta_{m},\quad|\text{Im}(s)|\leq
T_{m},\quad\delta_{m}:=\frac{C(\log m+\log\log x)}{\log x},\,T_{m}:=m^{5}(\log
x)^{2}.$

To access the range $\log Z_{j}\geq(\log\log X_{j})^{1+c}$ it would suffice
therefore to have access to a zero-free region in which
$\text{Re}(s)>1-\frac{(\log\log X_{j})^{2}}{\log X_{j}}$ and
$|\text{Im}(s)|\ll\exp((\log\log X_{j})^{2+\varepsilon})$, for example. Any
such zero-free region would be implied by one for the corresponding Dedekind
zeta function $\zeta_{L_{m}}$, and thus something far weaker than ERH would
suffice.
The potential for such improvements under the assumption of weak zero-free
regions suggests a possible unconditional improvement to Proposition 6.3 by
invoking zero-density estimates. This seems reasonable in light of the fact
that in constructing the extensions $L_{m}$ we had a significant amount of
flexibility in the choice of primes satisfying conditions (i)-(iii) of Step 2,
and thus there are rather substantial collections of extensions that could be
produced in this way. However, currently existing zero-density estimates for
Dedekind zeta functions, such as those of [21] and [26] are effective for
collections of fields in which the Galois group is either of fixed or very
slowly growing size (see for instance [26, Thm. 1.1], where the quality of the
bound depends exponentially on the size $|G|$ of the Galois group of the
number fields in the collection). In our case, however,
$\text{Gal}(L_{m}/\mathbb{Q})$ grows polynomially with $m\in[Y,Z]$, which
unfortunately makes these latter results unsuitable.

###  6.3. Proof of Proposition 6.4

The proof of Proposition 6.4 relies on a few elementary sieve lemmas.

######  Lemma 6.10.

Let $C>0$ and let $S$ be a set of prime powers that is $C$-sparse. For each
$n\in\mathbb{N}$ write

$n_{S}:=\prod_{\begin{subarray}{c}p^{\nu}||n\\\ p^{\nu}\in
S\end{subarray}}p^{\nu}$

to denote the product of all prime factors of $n$ that belong to $S$. Then for
any $\varepsilon>0$ there is a $Z_{0}=Z_{0}(\varepsilon,C)$ such that if
$Z\geq Z_{0}$ then for any $X$ sufficiently large,

$N_{S}(X;Z):=|\\{n\leq X:n_{S}>Z\\}\ll\varepsilon X.$

###### Proof.

Since $n_{S}|n$ for each $n\in\mathbb{N}$ the claim is immediate if $Z>X$. We
assume henceforth that $Z\leq X$. As in Section 4, define

$\omega_{S}(n):=|\\{p^{k}||n:p^{k}\in S\\}|,\quad
E_{S}(Y):=\sum_{\begin{subarray}{c}p^{k}\leq Y\\\ p^{k}\in
S\end{subarray}}\frac{1}{p}.$

By assumption, $E_{S}(Y)\leq C$ for all $Y\geq 2$.
Let $Y_{1}=\sqrt{\log Z}$ and $Y_{2}=e^{\tfrac{1}{2}\sqrt{\log Z}}$. For
$Z_{0}$ large enough and $Z\geq Z_{0}$ we have $Y_{1}\geq 2C\geq 2E_{S}(X)$,
so that by Lemma 3.1,

$|\\{n\leq X:\omega_{S}(n)>Y_{1}\\}|\leq|\\{n\leq
X:|\omega_{S}(n)-E_{S}(X)|>Y_{1}/2\\}|\ll\frac{1}{Y_{1}^{2}}\sum_{n\leq
X}|\omega_{S}(n)-E_{S}(X)|^{2}\ll\frac{X}{Y_{1}}.$

Furthermore, we also note that

$|\\{n\leq X:\exists\ p^{\nu}||n,\ p^{\nu}\in S\text{ and
}p^{\nu}>Y_{2}\\}|\leq\sum_{\begin{subarray}{c}Y_{2}<p^{\nu}\leq X\\\
p^{\nu}\in S\end{subarray}}\sum_{\begin{subarray}{c}n\leq X\\\
p^{\nu}||n\end{subarray}}1\ll X\sum_{\begin{subarray}{c}p^{\nu}>Y_{2}\\\
p^{\nu}\in S\end{subarray}}\frac{1}{p^{\nu}}.$

Now for any $n\leq X$ satisfying $\omega_{S}(n)\leq Y_{1}$ and
$\max\\{p^{\nu}\in S:p^{\nu}||n\\}\leq Y_{2}$,

$n_{S}=\prod_{\begin{subarray}{c}p^{\nu}||n\\\ p^{\nu}\in
S\end{subarray}}p^{\nu}\leq Y_{2}^{\omega_{S}(n)}\leq Y_{2}^{Y_{1}}<Z.$

Consequently, by the union bound

$\displaystyle N_{S}(X;Z)$ $\displaystyle\leq|\\{n\leq
X:\omega_{S}(n)>Y_{1}\\}|+|\\{n\leq X:\exists\,p^{\nu}||n,\,p^{\nu}\in S\text{
and }p^{\nu}>Y_{2}\\}|$ $\displaystyle\ll
X\left(Y_{1}^{-1}+\sum_{\begin{subarray}{c}p^{\nu}>Y_{2}\\\ p^{\nu}\in
S\end{subarray}}\frac{1}{p^{\nu}}\right)\ll\varepsilon X,$

as long as $Z\geq Z_{0}$ and $Z_{0}$ is chosen large enough, as claimed. ∎

######  Lemma 6.11.

Given $\eta\in(0,1)$, define $\mathcal{R}_{\eta}$ to be the set of primes
$\ell$ such that

$|\\{a\in(\mathbb{Z}/\ell\mathbb{Z})^{\times}:\,a\text{ is a primitive
root}\\}|<\eta(\ell-1).$

Then as $X\rightarrow\infty$ we have

$\sum_{\begin{subarray}{c}\ell\leq X\\\
\ell\in\mathcal{R}_{\eta}\end{subarray}}\frac{1}{\ell}\ll\eta^{100}\log\log
X.$

###### Proof.

By partial summation, it suffices to show that

$|\mathcal{R}_{\eta}\cap[2,y]|\ll\eta^{100}\frac{y}{\log y},\quad y\geq
y_{0}.$

It is a classical fact that there are $\phi(\ell-1)$ distinct primitive roots
modulo a prime $\ell$. Thus, defining the multiplicative function
$g(n):=\left(n/\phi(n)\right)^{100}$, we have

$\ell\in\mathcal{R}_{\eta}\text{ if and only if }g(\ell-1)>\eta^{-100}.$

Note that $g(p^{k})=1+O(1/p)$ for all prime powers $p^{k}$, so that $g(n)\leq
d(n)$ for all sufficiently large $n\geq 1$. Markov’s inequality and Lemma 3.7
thus combine to yield

$\displaystyle|\mathcal{R}_{\eta}\cap[2,y]|\leq\eta^{100}\sum_{\ell\leq
y}g(\ell-1)\leq\eta^{100}\sum_{\begin{subarray}{c}n\leq y-1\\\
p|(n+1)\Rightarrow p>y^{1/10}\end{subarray}}g(n)$
$\displaystyle\ll\eta^{100}\frac{y}{\log y}\exp\left(\sum_{p\leq
y}\frac{g(p)-1_{p\leq y^{1/10}}}{p}\right)$
$\displaystyle\ll\eta^{100}\frac{y}{\log y},$

as claimed. ∎

######  Lemma 6.12.

Let $x>y\geq 10$ and let $1\leq L\leq\exp(\sqrt{\log y})$. Then, outside of a
single possible exception, for any prime $\ell\leq L$ we have

$\sum_{\begin{subarray}{c}y<p\leq x\\\
\text{ord}_{\ell}(p)=\ell-1\end{subarray}}\frac{1}{p}=\frac{\phi(\ell-1)}{\ell-1}\log\left(\frac{\log
x}{\log y}\right)+O(L^{-10}).$

###### Proof.

Let $a\in(\mathbb{Z}/\ell\mathbb{Z})^{\times}$, and write

$Q(X):=\exp((\log X)^{3/5}(\log\log X)^{-1/5}),\quad X\geq 3.$

By [17, Thm. 2], outside of possibly one $\ell\leq Q(X)$ (in case Siegel
zeroes exist) there is a positive real number $C(\ell,a)$ such that

$\sum_{\begin{subarray}{c}p\leq X\\\ p\equiv
a\pmod{\ell}\end{subarray}}\frac{1}{p}=\frac{1}{\ell-1}\log\log X-\log
C(\ell,a)+O\left(Q(X)^{-100}\right).$

Applying this with $X\in\\{y,x\\}$ and subtracting the two, we obtain

$\sum_{\begin{subarray}{c}y<p\leq x\\\ p\equiv
a\pmod{\ell}\end{subarray}}\frac{1}{p}=\frac{1}{\ell-1}\log\left(\log x/\log
y\right)+O\left(Q(y)^{-100}\right).$

Since $\ell\leq L\ll Q(y)$, upon summing over all $a\pmod{\ell}$ with
$\text{ord}_{\ell}(a)=\ell-1$ we obtain

$\sum_{\begin{subarray}{c}y<p\leq x\\\
\text{ord}_{\ell}(p)=\ell-1\end{subarray}}\frac{1}{p}=\frac{\phi(\ell-1)}{\ell-1}\log(\log
x/\log y)+O(LQ(y)^{-100})=\frac{\phi(\ell-1)}{\ell-1}\log(\log x/\log
y)+O(L^{-10}),$

as required. ∎

###### Proof of Proposition 6.4.

Let
$\mathcal{G}:=\\{\ell\in\mathcal{P}:\ell^{\prime}|f(\ell)\Rightarrow\ell^{\prime}=\ell\\}=\mathcal{P}\backslash\mathcal{L}_{f}$,
in the notation of the proof of Proposition 6.3. Thus for each
$\ell\in\mathcal{G}$ there is $\alpha_{\ell}\geq 1$ such that
$f(\ell)=\ell^{\alpha_{\ell}}$, and also

(54) $\sum_{\ell\notin\mathcal{G}}\frac{1}{\ell}<\infty.$

Moreover, if $\ell\notin\mathcal{S}_{\delta}$ (defined in Proposition 4.1) and
is large enough in terms of $\delta$ then $1<|f(\ell)|<2\ell^{r}$, so that

$1\leq\alpha_{\ell}\leq r+1\text{ for all
}\ell\in\mathcal{G}\backslash\mathcal{S}_{\delta},\,\ell\gg_{\delta}1.$

In particular, $\alpha_{\ell}=O_{\delta}(1)$ uniformly on
$\mathcal{G}\backslash\mathcal{S}_{\delta}$.
The remainder of the proof splits into the following steps:

  1. (a)

finding $\alpha_{0}\in\mathbb{N}$ such that
$\\{\ell\in\mathcal{P}:\,|f(\ell)|\neq\ell^{\alpha_{0}}\\}$ is
$O_{\delta}(1)$-sparse,

  2. (b)

showing that $\alpha_{0}=1$, and

  3. (c)

in the case that $f$ is completely multiplicative, showing that there is a
divisor $d_{0}|a$ such that $f(d_{0})|b$, and that $a/d_{0}$ divides
$b/f(d_{0})$.

Step (a): In order to show (a), we will prove that for each $P\geq 2$ there is
an integer $1\leq\alpha(P)\ll_{\delta}1$ such that

(55) $\sum_{\begin{subarray}{c}p\leq P\\\ |f(p)|\neq
p^{\alpha(P)}\end{subarray}}\frac{1}{p}=O_{\delta}(1).$

Since $\alpha(P)$ is an integer of bounded size, we can choose
$\alpha_{0}\in\mathbb{N}$ by the pigeonhole principle such that
$\alpha(P_{j})=\alpha_{0}$ on an infinite sequence $(P_{j})_{j}$. In this
case, we have

$\sum_{\begin{subarray}{c}p\leq P_{j}\\\ |f(p)|\neq
p^{\alpha_{0}}\end{subarray}}\frac{1}{p}=O_{\delta}(1)\text{ for all }j\geq
1,$

and since the latter sum is monotone in $j$, we deduce on taking
$j\rightarrow\infty$ that

$\sum_{p:|f(p)|\neq p^{\alpha_{0}}}\frac{1}{p}<\infty,$

the size of the series depending only on $\delta$. Our goal is therefore to
prove (55).
Let $P\geq 2$. Since the claim is trivial otherwise, we may assume that $P$ is
larger than any fixed constant depending only on $\delta$. Let $L_{1}\geq
e^{P}$, choose $k$ large enough so that $x_{k}\geq e^{(\log L_{1})^{5}}$ and
set $L_{2}:=\exp((\log x_{k})^{2/5})$. We begin by showing that there is a
large set of primes $\ell\in[L_{1},L_{2}]$ for which the exponents $g_{\ell}$
in (25) are all equal and of size $O_{\delta}(1)$.
Define $\mathcal{R}_{\delta}$ as in the statement of Lemma 6.11, and consider
the set

$\mathcal{G}^{\prime}:=(\mathcal{G}\cap\mathcal{G}_{\delta,k;2b})\backslash\mathcal{R}_{\delta}\subseteq\mathcal{G}\backslash\mathcal{S}_{\delta}.$

Combining (54) with Lemmas 5.2 and 6.11, we have

$\displaystyle\sum_{\begin{subarray}{c}L_{1}\leq\ell\leq L_{2}\\\
\ell\in\mathcal{G}^{\prime}\end{subarray}}\frac{1}{\ell}$
$\displaystyle\geq\sum_{\begin{subarray}{c}\ell\leq x_{k}\\\
\ell\in\mathcal{G}_{\delta,k;2b}\end{subarray}}\frac{1}{\ell}-\sum_{\begin{subarray}{c}\ell\leq
x_{k}\\\
\ell\notin\mathcal{G}\end{subarray}}\frac{1}{\ell}-\sum_{\begin{subarray}{c}\ell\leq
x_{k}\\\
\ell\in\mathcal{R}_{\delta}\end{subarray}}\frac{1}{\ell}-\sum_{\ell\in[2,L_{1}]\cup[L_{2},x_{k}]}\frac{1}{\ell}$
$\displaystyle\geq(1/5-\delta^{50})\log\log x_{k}.$

Now for each $\ell\in\mathcal{G}^{\prime}\cap[L_{1},L_{2}]$ we have

$\log\ell\leq\log L_{2}=(\log x_{k})^{2/5}\text{ and
}\phi(\ell-1)/(\ell-1)\geq\delta.$

Set $z_{k}:=\exp((\log x_{k})^{4/5})$, so that $L_{2}=e^{\sqrt{\log z_{k}}}$.
By Lemma 6.12, outside of possibly one prime $\ell_{0}$, for $\ell\leq L_{2}$
we have

$\sum_{\begin{subarray}{c}p\leq x_{k}\\\
\text{ord}_{\ell}(p)=\ell-1\end{subarray}}\frac{1}{p}\geq\sum_{\begin{subarray}{c}z_{k}<p\leq
x_{k}\\\
\text{ord}_{\ell}(p)=\ell-1\end{subarray}}\frac{1}{p}=\frac{\phi(\ell-1)}{\ell-1}\log(\log
x_{k}/\log z_{k})+O(1)\geq\frac{\delta}{5}\log\log
x_{k}+O(1),\quad\ell\in\mathcal{G}^{\prime}\cap[L_{1},L_{2}].$

Taking account of the primes not in
$\mathcal{G}^{\prime}\backslash\mathcal{T}_{\ell}$ using Lemma 5.2 and
Proposition 5.4, we find that

$\sum_{\begin{subarray}{c}p\leq x_{k}\\\
p\in\mathcal{G}^{\prime}\backslash\mathcal{T}_{\ell}\\\
\text{ord}_{\ell}(p)=\ell-1\end{subarray}}\frac{1}{p}\geq\sum_{\begin{subarray}{c}p\leq
x_{k}\\\
\text{ord}_{\ell}(p)=\ell-1\end{subarray}}\frac{1}{p}-\sum_{\begin{subarray}{c}p\leq
x_{k}\\\
p\notin\mathcal{G}\end{subarray}}\frac{1}{p}-\sum_{\begin{subarray}{c}p\leq
x_{k}\\\
p\in\mathcal{T}_{\ell}\end{subarray}}\frac{1}{p}\geq\frac{\delta}{5}\log\log
x_{k}+O_{\delta}(1).$

In particular, for each of the $\ell\in\mathcal{G}^{\prime}\cap[L_{1},L_{2}]$,
$\ell\neq\ell_{0}$, we may select a prime $p_{\ell}\notin\mathcal{T}_{\ell}$
that is a primitive root modulo $\ell$, such that
$f(p_{\ell})=p_{\ell}^{\alpha_{p_{\ell}}}$ for some
$\alpha_{p_{\ell}}=O_{\delta}(1)$. Since
$(\alpha_{p_{\ell}})_{\ell\in\mathcal{G}^{\prime}\cap[L_{1},L_{2}]}$ belongs
to a finite set of integers depending only on $\delta$, by the pigeonhole
principle there is an $\alpha=\alpha(P)$ with $1\leq\alpha\ll_{\delta}(1)$
(which might depend on $L_{1},L_{2}$ and $x_{k}$, thus on $P$) such that

$\mathcal{U}_{\alpha}:=\\{\ell\in\mathcal{G}^{\prime}\cap[L_{1},L_{2}]:\,\alpha_{p_{\ell}}=\alpha\\}$

satisfies

$\sum_{\begin{subarray}{c}\ell\in\mathcal{U}_{\alpha}\end{subarray}}\frac{1}{\ell}\gg_{\delta}\log\log
x_{k}.$

Fix $\ell\in\mathcal{U}_{\alpha}$ for the moment. As $\ell\in\mathcal{G}$,
$f(\ell)=\ell^{\alpha_{\ell}}=q_{\ell}$ in the notation of Proposition 5.4.
That result implies that for prime $p\leq x_{k}$,

$\text{if }p\in[2,x_{k}]\backslash\mathcal{T}_{\ell}\text{ then
}f(p)^{D}\equiv p^{g_{\ell}}\pmod{\ell},$

for some $0\leq g_{\ell}<\ell-1$. By choice, the prime $p_{\ell}$ satisfies

$p_{\ell}^{D\alpha}=f(p_{\ell})^{D}\equiv p_{\ell}^{g_{\ell}}\pmod{\ell}.$

Rearranging, we deduce using the fact that $p_{\ell}$ is a primitive root
modulo $\ell$ that

$p_{\ell}^{g_{\ell}-D\alpha}\equiv 1\pmod{\ell},\text{ or equivalently,
}(\ell-1)|(g_{\ell}-D\alpha).$

Since $1\leq D\alpha=O_{\delta}(1)$ uniformly in
$\ell\in\mathcal{U}_{\alpha}$, and $g_{\ell}<\ell-1$ by construction, we
deduce that

$g_{\ell}=D\alpha\text{ for all }\ell\in\mathcal{U}_{\alpha}.$

We are now in a position to prove (55). Since $P\leq\log L_{1}$, applying
Lemma 6.5 we get

(56)
$\sum_{\ell\in\mathcal{T}(p)\cap\mathcal{U}_{\alpha}}\frac{1}{\ell}<\frac{1}{2}\sum_{\ell\in\mathcal{U}_{\alpha}}\frac{1}{\ell}$

outside of a set of $p\leq P$ such that

$\sum_{\begin{subarray}{c}p\leq P\\\ \eqref{eq:TpShare}\text{
fails}\end{subarray}}\frac{1}{p}=O_{\delta}(1).$

Now suppose $p\leq P$ satisfies (56), and $p\notin\mathcal{S}_{\delta}$. Then
there is at least one prime $\ell\in\mathcal{U}_{\alpha}$ such that
$p\notin\mathcal{T}_{\ell}$, and

$f(p)^{D}\equiv p^{D\alpha}\pmod{\ell}.$

If $P$ is large enough then $\ell\geq L_{1}>P^{D(r+\alpha+1)}$, and thus

$\ell>(2p^{r})^{D}+p^{D\alpha}\geq|f(p)^{D}-p^{D\alpha}|.$

We therefore deduce that $f(p)^{D}=p^{D\alpha}$, and in particular
$|f(p)|=p^{\alpha}$, whenever $p\leq P$ satisfies (56).
It follows that if $p\leq P$ satisfies $|f(p)|\neq p^{\alpha}$ then either
(56) fails or $p\in\mathcal{S}_{\delta}$, and so we deduce from (56) that

$\sum_{\begin{subarray}{c}p\leq P\\\ |f(p)|\neq
p^{\alpha}\end{subarray}}\frac{1}{p}=O_{\delta}(1),$

where $\alpha=\alpha(P)$. This proves (55), as required.

Step (b): Next, we show that $\alpha_{0}=1$. Set

$\tilde{\mathcal{G}}:=\\{p\in\mathcal{G}\backslash\mathcal{S}_{\delta}:|f(p)|=p^{\alpha_{0}}\\},$