THE DISTRIBUTION OF $\gcd(n,\varphi(n))$
Joshua Stucky

###### Abstract

Let $\varphi(n)$denote Euler’s phi function. In this paper, we study the
distribution of the numbers $(n,\varphi(n))$ and their divisors. Our results
generalize previous results of Erdös [2] and Pollack [6].

## 1\. Introduction

Let $\varphi(n)$ denote Euler’s phi function. Szele [9] showed that the
condition $(n,\varphi(n))=1$ is equivalent to the uniqueness of a group of
order $n$, and Erdös [2] subsequently showed that

$\sum_{\begin{subarray}{c}n\leq x\\\
(n,\varphi(n))=1\end{subarray}}1\sim\frac{x}{e^{\gamma}\log_{3}x}.$ (1.1)

Here and throughout, $\log x=\log_{1}x$ is the natural logarithm,
$\log_{k}x=\log(\log_{k-1}(x))$ is the $k$-fold iterated natural logarithm,
and $\gamma$ denotes the Euler-Mascheroni constant. Pollack [6] has given an
asymptotic expansion for the sum (1.1) of the form

$\sum_{\begin{subarray}{c}n\leq x\\\
(n,\varphi(n))=1\end{subarray}}1=\frac{x}{e^{\gamma}\log_{3}x}\bigg{(}1+\sum_{k=1}^{K}\frac{c_{k}}{(\log_{3}x)^{k}}\bigg{)}+O_{K}\left(\frac{x}{(\log_{3}x)^{K+2}}\right)$
(1.2)

for any integer $K\geq 1$, where $c_{k}$ are certain arithmetic constants.
Note that by Möbius inversion,

$\sum_{\begin{subarray}{c}n\leq x\\\
(n,\varphi(n))=1\end{subarray}}1=\sum_{d\leq x}\mu(d)\mathcal{A}_{d}(x),$

where $\mathcal{A}_{d}(x)$ denotes the congruence sum

$\mathcal{A}_{d}(x)=\sum_{\begin{subarray}{c}n\leq x\\\
d\mid(n,\varphi(n))\end{subarray}}1.$

In this paper, we consider the more general sums

$S_{g}(x):=\sum_{d\leq x}g(d)\mathcal{A}_{d}(x).$

One could consider a variety of arithmetic functions $g$ in the sum above. For
our purposes, we restrict our attention to $g$ being a multiplicative function
such that $\left|g(n)\right|\leq 1$ for all $n$. This is a fairly natural
class of arithmetic functions that already allows us to give some interesting
applications. Letting $f(n)=\sum_{d\mid n}g(d)$, we have

$S_{g}(x)=\sum_{n\leq x}f((n,\varphi(n))).$

Our main theorem, Theorem 1.1, furnishes an asymptotic for the sum $S_{g}$.
When $f$ (or, equivalently, $g$) has sufficient regularity over the primes, we
can obtain an asymptotic expansion of $S_{g}(x)$ with a level of precision
analogous to (1.2).

Note that if $f$ is a multiplicative function with $f(n)\in[0,1]$ for all $n$,
then by Möbius inversion, $\left|g(n)\right|\leq 1$. In particular, Theorem
1.1 allows us to obtain information about the distribution of $(n,\varphi(n))$
in any set $\mathcal{B}$ whose indicator function is multiplicative. Examples
of such sets include

  * •

sums of two squares (counted with or without multiplicity of representations)

  * •

$r$th powers (e.g. squares, cubes, etc.)

  * •

$r$-free numbers (e.g. squarefree or cubefree integers)

  * •

smooth numbers (i.e. integers free of large prime factors)

  * •

rough numbers (i.e. integers free of small prime factors)

If we instead take $g$ itself to be the indicator function of a set
$\mathcal{B}$ such that $g$ is multiplicative, we obtain information about the
distribution of the divisors of $(n,\varphi(n))$ that belong to $\mathcal{B}$.
In particular, if $\mathcal{B}=\mathbb{N}$ (i.e. $g(n)=1$), then we are able
to calculate the average order of the divisor function $\tau$ over
$(n,\varphi(n))$ (in fact, this was the original motivation for the present
work).

To further motivate our results, consider the following heuristic argument.
Let $P(d)$ denote the largest prime factor of $d$. When $n$ is of size $x$,
the condition $d\mid(n,\varphi(n))$ is roughly equivalent to $d\mid n$ and
$P(d)\leq\log_{2}x$. This phenomenon is apparent in Erdös’ [2] proof of (1.1)
and has been described more precisely by Erdös, Luca, and Pomerance (see
Theorem 8 of [1]). We then expect that

$S_{g}(x)\sim x\sum_{\begin{subarray}{c}d\leq x\\\
P(d)\leq\log_{2}x\end{subarray}}\frac{g(d)}{d}.$ (1.3)

When $g$ is multiplicative and does not grow too quickly, we expect the sum to
be well-approximated by the corresponding product over primes, and so we
conjecture that

$S_{g}(x)\sim x\prod_{p\leq\log_{2}x}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}.$ (1.4)

Our main theorem establishes this conjecture in a quantitative form for
bounded multiplicative functions.

######  Theorem 1.1.

Let $g$ be a multiplicative function such that $\left|g(n)\right|\leq 1$ for
all $n$. For any $K\geq 1$, as $x\to\infty$, we have

$S_{g}(x)=x\bigg{(}\prod_{p\leq\log_{2}x}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}\exp\left(\mathcal{Q}_{g}(x)\right)+O_{K}\left(\frac{x}{(\log_{3}x)^{K}}\right).$

where

$\mathcal{Q}_{g}(x)=-\sum_{p\leq\log_{2}x}\frac{g(p)}{p(\log
x)^{1/p}}+\sum_{p>\log_{2}x}\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)$

The sum $\mathcal{Q}_{g}(x)$ can be evaluated if $g$ (or $f$) is suitably
regular over the primes, and in Section 7, we give asymptotic expansions for
$S_{g}(x)$ for a variety of arithmetic functions $g$. Even if we cannot
evaluate these sums, we may estimate them uniformly since
$\left|g(p)\right|\leq 1$, and we obtain the following qualitative version of
(1.4).

######  Corollary 1.2.

With the hypotheses as in Theorem 1.1, we have

$S_{g}(x)=x\prod_{p\leq\log_{2}x}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}\left(1+O\left(\frac{1}{\log_{3}x}\right)\right).$
(1.5)

In particular, (1.5) holds uniformly for all multiplicative functions $g$ with
$\left|g(n)\right|\leq 1$ for all $n$.

###### Proof.

Note that $t\mapsto t(\log x)^{1/t}$ is decreasing for $t\leq\log_{2}x$. As
well, since $1-e^{-t}\leq t$ for all $t\geq 0$, we have

$1-\frac{1}{(\log x)^{1/p}}\leq\frac{\log_{2}x}{p}.$

Thus

$\displaystyle\bigg{|}-\sum_{p\leq\log_{2}x}\frac{g(p)}{p(\log
x)^{1/p}}+\sum_{p>\log_{2}x}\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\bigg{|}$
$\displaystyle\leq\frac{\pi(\log_{2}x)}{e\log_{2}x}+\sum_{p>\log_{2}x}\frac{\log_{2}x}{p^{2}}$
$\displaystyle\ll\frac{1}{\log_{3}x}.$

We also note that since $\left|g(p)\right|\leq 1$ for all $p$, we have

$\bigg{|}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{|}\geq\left(1-\frac{1}{p-1}\right),$

and so Merten’s theorem gives

$\prod_{p\leq\log_{2}x}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}\gg\frac{1}{\log_{3}x}.$

Taking $K=2$ in Theorem 1.1 now gives (1.5).

∎

Outline of the Paper. In Sections 2 and 3, we collect together a number of
preliminary results that we will need in our proof. Section 3 contains the
main technical tool used in the proof of Theorem 1.1, namely Corollary 3.4. We
prove Theorem 1.1 in Sections 4 – 6. We begin by cleaning and decomposing the
sum $S_{g}(x)$ in Section 4, removing numerous inconvenient terms and
isolating the parts of the summation variables that govern the behavior of
$S_{g}(x)$. After these manipulations, we apply Corollary 3.4 in Section 5 and
perform some final technical manipulations in Section 6 to complete the proof
of Theorem 1.1. Finally, in Section 7, we show how to evaluate the prime sums
$\mathcal{Q}_{g}(x)$ Theorem 1.1 for a variety of arithmetic functions $g$,
obtaining asymptotic expansions of $S_{g}(x)$ with a level of precision
analogous to (1.2).

Acknowledgments. The author would like to thank Paul Pollack for useful
discussions in the development of these results, and in particular for
suggesting the argument used in Section 4.5.

Notation. In addition to the notation already discussed, we make the following
conventions. The letters $p$ and $q$ always denote primes numbers. The
functions $P(n)$ and $p(n)$ are the largest and smallest prime factors of $n$,
respectively, and we set $P(1)=1$ and $p(1)=\infty$. The symbol
$\operatornamewithlimits{\sum\nolimits^{\flat}}$ denotes a sum over squarefree
integers. Throughout, we use $C$ to denote a positive absolute constant coming
from the error term in the prime number theorem. To keep our notation simple,
we may modify the value of $C$ at each occurrence. Thus we may write, for
example,

$\log_{3}x\exp(-C\sqrt{\log_{3}x})\ll\exp(-C\sqrt{\log_{3}x}).$

## 2\. Preliminaries

In this section, we collect together some preliminary results we will need in
our analysis. We begin with the following simple lemma which gives a useful
divisibility property for $\varphi$.

######  Lemma 2.1.

For any positive integers $a$ and $b$, we have $\varphi(a)\mid\varphi(ab)$. In
particular, if $d$ is a positive integer with $d\nmid\varphi(ab)$, then
$d\nmid\varphi(a)$.

###### Proof.

We write $b=b_{a}b^{\prime}$, where $b_{a}$ is the largest divisor of $b$
supported on the primes dividing $a$. Then

$\varphi(ab)=\varphi(ab_{a})\varphi(b^{\prime})=b_{a}\varphi(a)\varphi(b^{\prime})$

and the claim follows. ∎

We will need the following forms of Mertens’ theorems. These are
straightforward consequences of the prime number theorem with classical error
term $O(x\exp(-C\sqrt{\log x}))$.

######  Lemma 2.2.

There is an absolute constant $c$ such that, for all $x\geq 3$,

$\sum_{p\leq x}\frac{1}{p}=\log_{2}x+c+O(\exp(-C\sqrt{\log x})).$ (2.1)

We also have

$\prod_{p\leq x}\left(1-\frac{1}{p}\right)^{-1}=e^{\gamma}\log
x+O(\exp(-C\sqrt{\log x})).$ (2.2)

Next, we need Rankin’s trick in the following form.

######  Lemma 2.3.

For any $x\geq y\geq 10$, we have

$\sum_{\begin{subarray}{c}d>x\\\ P(d)\leq
y\end{subarray}}\frac{1}{d}\ll\frac{(\log y)^{3}}{x^{\frac{1}{\log y}}}.$
(2.3)

In the course of proving our results (specifically Proposition 3.2), we will
need to use the Fundamental Lemma of Sieve Theory. Of the versions available,
we will use the one due to Koukoulopolus (see [Koukoulopoulus], Theorem
18.11). The following lemma, which follows from the fundamental lemma, is
stated without proof in a slightly different form in [5]. For completeness, we
include a short proof.

######  Lemma 2.4.

Let $X$ and $Z$ be such that $2\leq Z\leq X^{1/2e^{2}}$, and let $\mathcal{Q}$
be a set of primes not exceeding $Z$. Let $(u,v]$ be an interval with $v-u=X$.
For each $q\in\mathcal{Q}$, choose a residue class $a_{q}\ (\textnormal{mod}\
q)$. Let $N(u,v;\mathcal{Q})$ be the number of integers $n\in(u,v]$ for which
$n\not\equiv a_{q}\ (\textnormal{mod}\ q)$ for any $q\in\mathcal{Q}$. Then

$N(u,v;\mathcal{Q})=X\prod_{q\in\mathcal{Q}}\left(1-\frac{1}{q}\right)\left(1+O\left(\exp\left(-\frac{\log
X}{\log Z}\right)\right)\right).$

###### Proof.

By the Chinese Remainder Theorem, we may choose an integer $a_{0}$ such that
$a_{q}\equiv a_{0}\ (\textnormal{mod}\ q)$ for each $q\in\mathcal{Q}$. We then
sieve the sequence $n-a_{0}$ since, for $q\in\mathcal{Q}$, $q\mid n-a_{0}$ if
and only if $n\equiv a_{0}\equiv a_{q}\ (\textnormal{mod}\ q)$. Thus

$N(u,v;\mathcal{Q})=\sum_{\begin{subarray}{c}u<n\leq v\\\
(n-a_{0},\mathcal{Q})=1\end{subarray}}1=\sum_{\begin{subarray}{c}u-a_{0}<n\leq
v-a_{0}\\\ (n,\mathcal{Q})=1\end{subarray}}1,$

where the condition $(n,\mathcal{Q})=1$ means that $n$ is free of primes in
$\mathcal{Q}$. To apply Theorem 18.11 of [4], we note that for any $d$,

$\sum_{\begin{subarray}{c}u-a_{0}<n\leq v-a_{0}\\\ n\equiv 0\
(\textnormal{mod}\ d)\end{subarray}}1=\frac{X}{d}+O(1).$

Moreover, for any $2\leq y_{1}<y_{2}\leq Z$, we have

$\prod_{\begin{subarray}{c}p\in\mathcal{Q}\cap(y_{1},y_{2}]\end{subarray}}\left(1-\frac{1}{p}\right)^{-1}\leq\prod_{y_{1}<p\leq
y_{2}}\left(1-\frac{1}{p}\right)^{-1}=\frac{\log y_{2}}{\log
y_{2}}\left(1+O\left(\frac{1}{\log y_{1}}\right)\right)$

by Lemma 2.2. Thus Axioms 1 and 2 of Theorem 18.11 of [4] are satisfied. We
take $u=\frac{\log X}{2\log Z}$ in the theorem and note that $u^{-u/2}\leq
e^{-u}$ so long as $\log u\geq 2$. That is, so long as $Z\leq X^{1/2e^{2}}$.

∎

To understand the product over primes appearing in Lemma 2.4, we need the
following result of Pomerance [8].

######  Lemma 2.5.

Let $a,m$ be positive integers with $(a,m)=1$ and let $p_{a,m}$ denote the
least prime $p\equiv a\ (\textnormal{mod}\ m)$. Then

$\sum_{\begin{subarray}{c}p\leq x\\\ p\equiv a\ (\textnormal{mod}\
m)\end{subarray}}\frac{1}{p}=\frac{\log_{2}x}{\varphi(m)}+\frac{1}{p_{a,m}}+O\left(\frac{\log(2m)}{\varphi(m)}\right).$

In particular,

$\sum_{\begin{subarray}{c}p\leq x\\\ p\equiv 1\ (\textnormal{mod}\
m)\end{subarray}}\frac{1}{p}=\frac{\log_{2}x}{\varphi(m)}+O\left(\frac{\log(2m)}{\varphi(m)}\right).$

## 3\. Main Technical Propositions

In this section, we prove several results that we will use to evaluate sums
involving the divisibility conditions $d\mid\varphi(n)$ and
$d\nmid\varphi(n)$. The first is a simple consequence of the Brun-Titchmarsh
inequality.

######  Proposition 3.1.

For any $x>1$ and $p<x$, we have

$\sum_{\begin{subarray}{c}n\leq x\\\
p\mid\varphi(n)\end{subarray}}1\ll\frac{x\log_{2}x}{p}.$

###### Proof.

If $p\mid\varphi(n)$, then either $p^{2}\mid n$ or $n$ is divisible by a prime
$q\equiv 1\ (\textnormal{mod}\ p)$. The Brun-Titchmarsh inequality and partial
summation then gives

$\sum_{\begin{subarray}{c}n\leq x\\\
p\mid\varphi(n)\end{subarray}}1\leq\frac{x}{p^{2}}+\sum_{\begin{subarray}{c}q\leq
x\\\ q\equiv 1\ (\textnormal{mod}\
p)\end{subarray}}\frac{x}{q}\ll\frac{x\log_{2}x}{p}.$

∎

The following proposition allows us to evaluate asymptotically sums involving
divisibility conditions on $\varphi(n)$.

######  Proposition 3.2.

Let $x$ be sufficiently large. Denote by $\alpha$ and $\beta$ the functions

$\alpha(d)=\prod_{p\mid
d}\left(1-\frac{1}{p-1}\right),\qquad\beta(d)=\sum_{p\mid d}\frac{\log p}{p}.$
(3.1)

Let $d$ be a positive squarefree integer such that the following hold:

  1. (i)

$d$ is odd and $1<d\leq\exp\left(\frac{1}{2}\sqrt{\log x}\right)$;

  2. (ii)

$\frac{\beta(d)d}{\varphi(d)}$ is bounded.

Then

$\sum_{\begin{subarray}{c}n\leq x\\\
(\varphi(n),d)=1\end{subarray}}1=\frac{x}{(\log
x)^{1-\alpha(d)}}\left(1+O\left(\frac{\beta(d)d}{\varphi(d)}\right)\right).$
(3.2)

If $\omega(d)\leq K$ for some $K\geq 1$, then

$\frac{\beta(d)d}{\varphi(d)}\ll_{K}\frac{\log p(d)}{p(d)}.$ (3.3)

###### Proof.

Let

$\mathcal{Q}=\bigcup_{p\mid d}\left\\{q:q\equiv 1\ (\textnormal{mod}\
p)\right\\},\qquad Q(z)=\prod_{\begin{subarray}{c}q\in\mathcal{Q}\\\ q\leq
z\end{subarray}}q$

and note that by the Chinese Remainder Theorem and Lemma 2.5,

$\displaystyle\sum_{\begin{subarray}{c}q\leq x\\\
q\in\mathcal{Q}\end{subarray}}\frac{1}{q}$
$\displaystyle=-\sum_{\begin{subarray}{c}l\mid d\\\
l>1\end{subarray}}\mu(l)\sum_{\begin{subarray}{c}q\leq x\\\ q\equiv 1\
(\textnormal{mod}\ l)\end{subarray}}\frac{1}{q}$
$\displaystyle=-\sum_{\begin{subarray}{c}l\mid d\\\
l>1\end{subarray}}\mu(l)\bigg{(}\frac{\log_{2}x}{\varphi(l)}+O\left(\frac{\log
l}{\varphi(l)}\right)\bigg{)}$
$\displaystyle=(1-\alpha(d))\log_{2}x+O\bigg{(}\sum_{l\mid d}\frac{\log
l}{\varphi(l)}\bigg{)}.$

To estimate the error term, let

$g_{d}(s)=\sum_{l\mid d}\frac{1}{\varphi(l)^{s}}.$

By the well-known inequalities

$\frac{l}{\log_{2}l}\ll\varphi(l)\leq l,$

we have $\log l\asymp\log\varphi(l)$, and so the error term above is

$\asymp\sum_{l\mid d}\frac{\log\varphi(l)}{\varphi(l)}=-g_{d}^{\prime}(1).$

But for $d$ squarefree,

$g_{d}(s)=\prod_{p\mid
d}\left(1+\frac{1}{(p-1)^{s}}\right)=\exp\bigg{(}\sum_{p\mid
d}\log\left(1+\frac{1}{(p-1)^{s}}\right)\bigg{)},$

and so

$-g_{d}^{\prime}(1)=\bigg{(}\sum_{p\mid
d}\frac{\log(p-1)}{p}\bigg{)}\prod_{p\mid
d}\left(1+\frac{1}{p-1}\right)=\frac{d}{\varphi(d)}\sum_{p\mid
d}\frac{\log(p-1)}{p}<\frac{\beta(d)d}{\varphi(d)}.$

Thus

$\sum_{\begin{subarray}{c}q\leq x\\\
q\in\mathcal{Q}\end{subarray}}\frac{1}{q}=(1-\alpha(d))\log_{2}x+O\left(\frac{\beta(d)d}{\varphi(d)}\right).$
(3.4)

Let $J\geq 2e^{2}$ be a parameter to be chosen. For the upper bound in (3.2),
we note that the condition $(\varphi(n),d)=1$ implies that $n$ is free of
primes $q\equiv 1\ (\textnormal{mod}\ p)$ for each prime $p\mid d$. In
particular, $n$ is free of all such primes $q\leq x^{1/J}$. By Lemma 2.4 with
$z=x^{1/J}$, the number of integers up to $x$ free of primes dividing $Q(z)$
is

$x\prod_{\begin{subarray}{c}q\leq x^{1/J}\\\
q\in\mathcal{Q}\end{subarray}}\left(1-\frac{1}{q}\right)\left(1+O\left(e^{-J}\right)\right).$

To evaluate the product over primes, we first write

$\prod_{\begin{subarray}{c}q\leq x^{1/J}\\\
q\in\mathcal{Q}\end{subarray}}\left(1-\frac{1}{q}\right)=\exp\bigg{(}\sum_{\begin{subarray}{c}q\leq
x^{1/J}\\\
q\in\mathcal{Q}\end{subarray}}\log\left(1-\frac{1}{q}\right)\bigg{)}=\exp\bigg{(}-\sum_{\begin{subarray}{c}q\leq
x^{1/J}\\\
q\in\mathcal{Q}\end{subarray}}\frac{1}{q}+O\bigg{(}\sum_{\begin{subarray}{c}q\leq
x^{1/J}\\\ q\in\mathcal{Q}\end{subarray}}\frac{1}{q^{2}}\bigg{)}\bigg{)}.$

The error term is

$\sum_{\begin{subarray}{c}q\leq x^{1/J}\\\
q\in\mathcal{Q}\end{subarray}}\frac{1}{q^{2}}\leq\sum_{p\mid d}\sum_{q\equiv
1\ (\textnormal{mod}\ p)}\frac{1}{q^{2}}\ll\sum_{p\mid
d}\frac{1}{p^{2}}\ll\frac{1}{p(d)},$

and so

$\prod_{\begin{subarray}{c}q\leq x^{1/J}\\\
q\in\mathcal{Q}\end{subarray}}\left(1-\frac{1}{q}\right)=\exp\bigg{(}-\sum_{\begin{subarray}{c}q\leq
x^{1/J}\\\
q\in\mathcal{Q}\end{subarray}}\frac{1}{q}\bigg{)}\left(1+O\left(\frac{1}{p(d)}\right)\right).$

By (3.4), the remaining sum over $q$ is

$\sum_{\begin{subarray}{c}q\leq x^{1/J}\\\
q\in\mathcal{Q}\end{subarray}}\frac{1}{q}=(1-\alpha(d))(\log_{2}x-\log
J)+O\left(\frac{\beta(d)d}{\varphi(d)}\right).$

and thus

$\prod_{\begin{subarray}{c}q\leq x^{1/J}\\\
q\in\mathcal{Q}\end{subarray}}\left(1-\frac{1}{q}\right)=\frac{J^{1-\alpha(d)}}{(\log
x)^{1-\alpha(d)}}\left(1+O\left(\frac{\beta(d)d}{\varphi(d)}\right)\right),$
(3.5)

since

$\frac{\beta(d)d}{\varphi(d)}\geq\beta(d)\geq\frac{1}{p(d)}.$

for $p(d)\geq 3$. Therefore

$\sum_{\begin{subarray}{c}n\leq x\\\
(\varphi(n),d)=1\end{subarray}}1\leq\frac{J^{1-\alpha(d)}x}{(\log
x)^{1-\alpha(d)}}\left(1+O\left(e^{-J}+\frac{\beta(d)d}{\varphi(d)}\right)\right).$

For the lower bound, note that if $(n,d)=1$ and $n$ is free of primes in
$\mathcal{Q}$, then $(\varphi(n),d)=1$. Thus

$\displaystyle\sum_{\begin{subarray}{c}n\leq x\\\
(\varphi(n),d)=1\end{subarray}}1\geq\sum_{\begin{subarray}{c}n\leq x\\\
(n,dQ(x))=1\end{subarray}}1$ $\displaystyle=\sum_{\begin{subarray}{c}n\leq
x\\\ (n,dQ(x^{1/J}))=1\end{subarray}}1-\sum_{\begin{subarray}{c}n\leq x\\\
(n,Q(x))>1\\\ (n,dQ(x^{1/J}))=1\end{subarray}}1$ (3.6)
$\displaystyle\geq\sum_{\begin{subarray}{c}n\leq x\\\
(n,dQ(x^{1/J}))=1\end{subarray}}1-\sum_{\begin{subarray}{c}n\leq x\\\
(n,Q(x))>1\\\ (n,Q(x^{1/J}))=1\end{subarray}}1.$

Reasoning as before, the first sum is

$\frac{\varphi(d)}{d}\frac{J^{1-\alpha(d)}x}{(\log
x)^{1-\alpha(d)}}\left(1+O\left(e^{-J}+\frac{\beta(d)d}{\varphi(d)}\right)\right).$

The hypotheses of the proposition imply that $\beta(d)$ is bounded, and so

$\frac{\varphi(d)}{d}=\exp\bigg{(}\sum_{p\mid
d}\log\left(1-\frac{1}{p}\right)\bigg{)}=\exp(O(\beta(d)))=1+O(\beta(d)),$

and so

$\sum_{\begin{subarray}{c}n\leq x\\\
(n,dQ(x^{1/J}))=1\end{subarray}}1=\frac{J^{1-\alpha(d)}x}{(\log
x)^{1-\alpha(d)}}\left(1+O\left(e^{-J}+\frac{\beta(d)d}{\varphi(d)}\right)\right).$

To bound the second sum in (3.6), note that the conditions $(n,Q(x))>1$,
$(n,Q(x^{1/J}))=1$ induce a factorization $n=AB$, where $A$ is the largest
divisor of $n$ supported on primes dividing $Q(x)/Q(x^{1/J})$. Every such $A$
satisfies $A\equiv 1\ (\textnormal{mod}\ l)$ for some $l\mid d$, $l>1$. We fix
$B$ and $l$ and count the number of corresponding $A$. Note that $1<A\leq x/B$
and that every prime dividing $A$ exceeds $x^{1/J}$. As well, $A=1+la$ for
some $a<x/lB$. If we assume for the moment that $\frac{\log x}{\log l}\geq
2K$, then $x/lB>x^{1/2J}$ since $B<x^{1-1/J}$. For any prime $q\leq x^{1/2J}$
with $q\nmid l$, we have $a\equiv\overline{l}(A-1)\ (\textnormal{mod}\ q)$.
Since every prime that divides $A$ is at least $x^{1/J}$, we have $A\not\equiv
0\ (\textnormal{mod}\ q)$, and so $a\not\equiv-\overline{l}\
(\textnormal{mod}\ q)$. Applying Lemma 2.4 to $a$ with
$a_{q}\equiv-\overline{l}\ (\textnormal{mod}\ q)$, the number of $A$
corresponding to a given $B$ and $l$ is

$\ll\frac{x}{lB}\prod_{\begin{subarray}{c}q\leq x^{1/2J}\\\ q\nmid
l\end{subarray}}\left(1-\frac{1}{q}\right)\leq\frac{x}{lB}\prod_{q\leq
x^{1/2J}}\left(1-\frac{1}{q}\right)\prod_{q\mid
l}\left(1-\frac{1}{q}\right)^{-1}\ll\frac{xJ}{\varphi(l)B\log x}.$

Summing over $l$, the number of $A$ corresponding to a given $B$ is

$\ll\frac{xJ}{B\log x}\sum_{\begin{subarray}{c}l\mid d\\\
l>1\end{subarray}}\frac{1}{\varphi(l)}.$

Mertens’ theorem then gives

$\displaystyle\sum\frac{1}{B}\leq\prod_{\begin{subarray}{c}q\leq x\\\
q\not\in\mathcal{Q}\end{subarray}}\left(1-\frac{1}{q}\right)^{-1}$
$\displaystyle=\prod_{\begin{subarray}{c}q\leq
x\end{subarray}}\left(1-\frac{1}{q}\right)^{-1}\prod_{\begin{subarray}{c}q\leq
x\\\ q\in\mathcal{Q}\end{subarray}}\left(1-\frac{1}{q}\right)$
$\displaystyle\ll\log x\exp\bigg{(}-\sum_{\begin{subarray}{c}q\leq x\\\
q\in\mathcal{Q}\end{subarray}}\frac{1}{q}\bigg{)}$ $\displaystyle\ll(\log
x)^{\alpha(d)}$

Therefore

$\sum_{\begin{subarray}{c}n\leq x\\\ (n,Q(x))>1\\\
(n,Q(x^{1/J}))=1\end{subarray}}1\ll\frac{xJ}{(\log
x)^{1-\alpha(d)}}\sum_{\begin{subarray}{c}l\mid d\\\
l>1\end{subarray}}\frac{1}{\varphi(l)}.$

Letting $\theta(d)$ denote the sum over $l$, we have shown

$\sum_{\begin{subarray}{c}n\leq x\\\
(\varphi(n),d)=1\end{subarray}}1=\frac{J^{1-\alpha(d)}x}{(\log
x)^{1-\alpha(d)}}\left(1+O\left(e^{-J}+\frac{\beta(d)d}{\varphi(d)}+J^{\alpha(d)}\theta(d)\right)\right).$

Since $p(d)\geq 3$, we have

$\alpha(d)=\prod_{p\mid
d}\left(1-\frac{1}{p-1}\right)\geq\exp\bigg{(}-\sum_{p\mid
d}\frac{2}{p-1}\bigg{)}\geq\exp\left(-\frac{4\beta(d)}{\log p(d)}\right)\geq
1-\frac{4\beta(d)}{\log p(d)},$

and also

$\displaystyle 1+\theta(d)=\prod_{p\mid
d}\left(1+\frac{1}{p-1}\right)\leq\exp\bigg{(}\sum_{p\mid
d}\frac{1}{p-1}\bigg{)}$ $\displaystyle\leq\exp\left(\frac{2\beta(d)}{\log
p(d)}\right)$ $\displaystyle=1+O\left(\frac{\beta(d)}{\log p(d)}\right).$

That is, both $1-\alpha(d)$ and $\theta(d)$ are $O\left(\frac{\beta(d)}{\log
p(d)}\right)$. If $p(d)\geq e^{2e^{2}}$, we choose $J=\log p(d)$ so that the
hypotheses of the proposition ensure that $\frac{\log x}{\log l}\geq 2J\geq
4e^{2}$ for every $l\mid d$, $l>1$ and $x$ sufficiently large. Since
$\alpha(d)\leq 1$, we then have $J^{\alpha(d)}\theta(d)\ll\beta(d)$ and

$J^{1-\alpha(d)}=\exp((1-\alpha(d))\log_{2}p(d))=1+O(\beta(d)).$

Therefore

$\sum_{\begin{subarray}{c}n\leq x\\\
(\varphi(n),d)=1\end{subarray}}1=\frac{x}{(\log
x)^{1-\alpha(d)}}\left(1+O\left(\frac{\beta(d)d}{\varphi(d)}\right)\right),$

if $p(d)\geq e^{2e^{2}}$. If $p(d)<e^{2e^{2}}$, the $\beta(d)\gg 1$, and so
(3.2) can only be an upper bound. In this case, the hypotheses of the
proposition and (3.4) imply that there is an absolute constant $C>0$ such that

$\sum_{\begin{subarray}{c}q\leq x\\\
q\in\mathcal{Q}\end{subarray}}\frac{1}{q}\geq(1-\alpha(d))\log_{2}x-C.$

The desired upper bound then follows from Brun’s sieve, specifically in the
form of Theorem 2.3 of [3].

To prove (3.3), we simply note that if $\omega(d)\leq K$, then

$\sum_{p\mid d}\frac{\log p}{p}\ll K\frac{\log p(d)}{p(d)}.$

and

$\frac{d}{\varphi(d)}=\prod_{p\mid
d}\left(1-\frac{1}{p}\right)^{-1}\leq\prod_{r=1}^{K}\left(1-\frac{1}{p_{r}}\right)^{-1},$

where $p_{r}$ denotes the $r$th prime. We have $p_{r}\ll r\log r$, and so
(2.2) gives

$\prod_{r=1}^{K}\left(1-\frac{1}{p_{r}}\right)^{-1}\ll\log p_{K}\ll\log K.$

∎

The asymptotic formula (3.2) is not quite suitable for our purposes. To put it
into a form more amenable for calculations, we need the following estimate for
the function $\alpha(d)$ appearing in Proposition 3.2.

######  Lemma 3.3.

Let

$\alpha_{1}(d)=\sum_{p\mid d}\frac{1}{p-1}.$

If $K\geq 1$ and $\omega(d)\leq K$, then

$\left|1-\alpha(d)-\alpha_{1}(d)\right|\leq\frac{4e^{K}}{p(d)^{2}}.$

###### Proof.

Expanding the product in the definition of $\alpha(d)$ and grouping the terms
depending on the value of $\omega(g)$, we have

$1-\alpha(d)=-\sum_{\begin{subarray}{c}g\mid d\\\
g>1\end{subarray}}\frac{\mu(g)}{\varphi(g)}=\alpha_{1}(d)-\sum_{k=2}^{\omega(d)}(-1)^{k}\sum_{\begin{subarray}{c}g\mid
d\\\ \omega(g)=k\end{subarray}}\frac{1}{\varphi(g)}.$

The triangle inequality and binomial theorem then imply

$\displaystyle\left|1-\alpha(d)-\alpha_{1}(d)\right|$
$\displaystyle\leq\sum_{k=2}^{\omega(d)}\frac{1}{k!}\bigg{(}\sum_{p\mid
d}\frac{1}{p-1}\bigg{)}^{k}\leq\sum_{k=2}^{\omega(d)}\frac{1}{k!}\left(\frac{\omega(d)}{p(d)-1}\right)^{k}\leq\frac{4}{p(d)^{2}}\sum_{k\geq
2}\frac{K^{k}}{k!}\leq\frac{4e^{K}}{p(d)^{2}}.$

∎

Combining this with (3.2), we deduce the following consequences of Proposition
3.2. These are the forms of Proposition 3.1 that we will use most often in
applications.

######  Corollary 3.4.

Let the notation and hypotheses be as in Proposition 3.2 and let $\alpha_{1}$
be as in Lemma 3.3. If $K\geq 1$ and $\omega(d)\leq K$, and if
$p(d)>2\sqrt{e^{K}\log_{2}x}$, then

$\sum_{\begin{subarray}{c}n\leq x\\\
(\varphi(n),d)=1\end{subarray}}1=\frac{x}{(\log
x)^{\alpha_{1}(d)}}\left(1+O_{K}\left(\frac{\log
p(d)}{p(d)}+\frac{\log_{2}x}{p(d)^{2}}\right)\right),$ (3.7)

We also have

$\sum_{\begin{subarray}{c}n\leq x\\\
d\mid\varphi(n)\end{subarray}}1=x\prod_{p\mid d}\left(1-\frac{1}{(\log
x)^{1/(p-1)}}\right)+O_{K}\left(x\left(\frac{\log
p(d)}{p(d)}+\frac{\log_{2}x}{p(d)^{2}}\right)\right)$ (3.8)

and

$\sum_{\begin{subarray}{c}n\leq x\\\ d\nmid\varphi(n)\end{subarray}}1\ll
x\sum_{p\mid d}(\log x)^{-1/(p-1)}.$ (3.9)

###### Proof.

To prove (3.7), note that by Lemma 3.3, we have, for some
$\left|\theta\right|\leq 1$,

$\displaystyle\frac{1}{(\log x)^{1-\alpha(d)}}=\frac{1}{(\log
x)^{\alpha_{1}(d)+4e^{K}\theta p(d)^{-2}}}$ $\displaystyle=\frac{1}{(\log
x)^{\alpha_{1}(d)}}\exp\left(\frac{4e^{K}\theta\log_{2}x}{p(d)^{2}}\right)$
$\displaystyle=\frac{1}{(\log
x)^{\alpha_{1}(d)}}\left(1+O_{K}\left(\frac{\log_{2}x}{p(d)^{2}}\right)\right).$

The estimate (3.7) now follows by inserting this into (3.2) and applying
(3.3).

For (3.8), Möbius inversion gives

$\sum_{\begin{subarray}{c}n\leq x\\\
d\mid\varphi(n)\end{subarray}}1=\sum_{g\mid
d}\mu(g)\sum_{\begin{subarray}{c}n\leq x\\\ (g,\varphi(n))=1\end{subarray}}1.$

Applying (3.7), we then have

$\displaystyle\sum_{\begin{subarray}{c}n\leq x\\\
d\mid\varphi(n)\end{subarray}}1$ $\displaystyle=\sum_{g\mid
d}\mu(g)\sum_{\begin{subarray}{c}n\leq x\\\ (g,\varphi(n))=1\end{subarray}}1$
$\displaystyle=\sum_{\begin{subarray}{c}n\leq
x\end{subarray}}1+\sum_{\begin{subarray}{c}g\mid d\\\
g>1\end{subarray}}\mu(g)\frac{x}{(\log
x)^{\alpha_{1}(g)}}\left(1+O_{K}\left(\frac{\log
p(g)}{p(g)}+\frac{\log_{2}x}{p(g)^{2}}\right)\right)$
$\displaystyle=x\prod_{p\mid d}\left(1-\frac{1}{(\log
x)^{1/(p-1)}}\right)+O_{K}\bigg{(}x\left(\frac{\log
p(d)}{p(d)}+\frac{\log_{2}x}{p(d)^{2}}\right)\bigg{)}.$

To prove (3.9), note that if $d\nmid\varphi(n)$, then $p\nmid\varphi(n)$ for
some $p\mid d$. Thus

$\sum_{\begin{subarray}{c}n\leq x\\\
d\nmid\varphi(n)\end{subarray}}1\leq\sum_{p\mid
d}\sum_{\begin{subarray}{c}n\leq x\\\ p\nmid\varphi(n)\end{subarray}}1.$

Applying (3.7) then gives (3.9).

∎

## 4\. Cleaning and Decomposition of $S_{g}(x)$

Recall that $g$ is a multiplicative function bounded by 1. For notational
simplicity, we suppress the subscript notation and write $S(x)=S_{g}(x)$. We
then have

$S(x)=\sum_{d\leq x}g(d)\sum_{\begin{subarray}{c}n\leq x\\\
d\mid(n,\varphi(n))\end{subarray}}1=\sum_{d\leq
x}g(d)\sum_{\begin{subarray}{c}n\leq\frac{x}{d}\\\
d\mid\varphi(nd)\end{subarray}}1.$

To evaluate this sum, we need to perform some substantial cleaning and
decomposition to remove inconvenient terms and isolate the portions of the
variables $n$ and $d$ that govern the behavior of the sum. The net result of
our manipulations, as well as the total error incurred as a result, can be
seen in equation (4.8) at the end of this section.

For brevity, let $y=\log_{2}x$. As stated in the introduction, the condition
$d\mid(n,\varphi(n))$ is roughly equivalent to $d\mid n$ and $P(d)\leq y$.
Consequently, we expect the behavior of the congruence sums
$\mathcal{A}_{d}(x)$ to be governed primarily by the prime factors of $d$ that
are close to $y$. More precisely, it turns out that this behavior is governed
by the prime factors $p$ that are close to $y$ on the logarithmic scale, i.e.

$1-\varepsilon\leq\frac{\log p}{\log y}\leq 1+\varepsilon,$

where the specific $\varepsilon$ we consider depends on the desired precision
(the parameter $K$) of the asymptotic expansion given in Theorem 1.1.
Moreover, we expect the prime factors $p$ to affect the congruence sum
$\mathcal{A}_{d}(x)$ in different ways depending as $p>y$ or $p<y$. This
discussion motivates us to decompose the variable $d$ in the following way.
Let $U,V\in[1,\sqrt{y}]$ be two parameters to be chosen and write

$d=sm\ell,$ (4.1)

where

  * •

$P(s)\leq\frac{y}{V}$,

  * •

$p(m)>\frac{y}{V}$ and $P(m)\leq Uy$,

  * •

$p(\ell)>Uy$.

### 4.1. Initial Truncation

For technical reasons, it will be convenient to know that $d$ is much smaller
than $x$. As such, before introducing the above decomposition of $d$, we first
show that the contribution of large $d$ is negligible. Let

$D=\exp((\log_{3}x)^{2}),\qquad D^{\prime}=(\log_{2}x)\exp(\sqrt{\log_{3}x}),$

and let $S^{(1)}$ be the sum $S$ but restricted to $d\leq D$. We have

$\left|S(x)-S^{(1)}(x)\right|\leq\sum_{\begin{subarray}{c}D<d\leq
x\end{subarray}}\sum_{\begin{subarray}{c}n\leq\frac{x}{d}\\\
P(d)\mid\varphi(nd)\end{subarray}}1=\bigg{(}\sum_{\begin{subarray}{c}D<d\leq
x\\\ P(d)\leq D^{\prime}\end{subarray}}+\sum_{\begin{subarray}{c}D<d\leq x\\\
P(d)>D^{\prime}\end{subarray}}\bigg{)}\sum_{\begin{subarray}{c}n\leq\frac{x}{d}\\\
P(d)\mid\varphi(nd)\end{subarray}}1=\Sigma_{1}+\Sigma_{2},$

say. To estimate $\Sigma_{1}$, we use Rankin’s trick in the form of (2.3):

$\Sigma_{1}=\sum_{\begin{subarray}{c}D<d\leq x\\\ P(d)\leq
D^{\prime}\end{subarray}}\sum_{\begin{subarray}{c}n\leq\frac{x}{d}\\\
P(d)\mid\varphi(nd)\end{subarray}}1\leq\sum_{\begin{subarray}{c}d>D\\\
P(d)\leq D^{\prime}\end{subarray}}\frac{x}{d}\ll x\frac{(\log
D^{\prime})^{3}}{D^{1/\log D^{\prime}}}\ll\frac{x}{\sqrt{\log_{2}x}}.$

To estimate $\Sigma_{2}$, we note that if $P(d)\mid\varphi(nd)$, then at least
one of the following holds:

  1. 1.

$P(d)^{2}\mid d$;

  2. 2.

$P(d)\mid n$;

  3. 3.

$P(d)\nmid n$ and $P(d)\mid\varphi(n)$.

The contribution to $\Sigma_{2}$ of the first case is

$\sum_{\begin{subarray}{c}D<d\leq x\\\ P(d)>D^{\prime}\\\ P(d)^{2}\mid
d\end{subarray}}\sum_{n\leq\frac{x}{d}}1\leq\sum_{p>D^{\prime}}\frac{x}{p^{2}}\sum_{\begin{subarray}{c}d>D/p^{2}\\\
P(d)\leq p\end{subarray}}\frac{1}{d}\ll x\sum_{p>D^{\prime}}\frac{\log
p}{p^{2}}\ll\frac{x}{D^{\prime}}$

and the contribution of the second case satisfies the same estimate. For the
third case, we use Proposition 3.1 to see that this contribution is at most

$\displaystyle\sum_{\begin{subarray}{c}D<d\leq x\\\
P(d)>D^{\prime}\end{subarray}}\sum_{\begin{subarray}{c}n\leq\frac{x}{d}\\\
P(d)\mid\varphi(n)\end{subarray}}1$
$\displaystyle\ll\sum_{\begin{subarray}{c}D<d\leq x\\\
P(d)>D^{\prime}\end{subarray}}\frac{x\log_{2}x}{dP(d)}\ll\sum_{p>D^{\prime}}\frac{x\log_{2}x}{p^{2}}\sum_{\begin{subarray}{c}d>D\\\
P(d)\leq p\end{subarray}}\frac{1}{d}\ll\frac{x\log_{2}x}{D^{\prime}}.$

Combining the three estimates above, we have

$\Sigma_{2}\ll x\exp(-\sqrt{\log_{3}x}),$

and so

$S(x)=S^{(1)}(x)+O\left(x\exp(-\sqrt{\log_{3}x})\right)$ (4.2)

since $\sqrt{\log_{2}x}\gg\exp(\sqrt{\log_{3}x})$.

### 4.2. Reduction to Primes Close to $y$

Recall that we expect the behavior of the congruence sums $\mathcal{A}_{d}(x)$
to be governed primarily by the prime factors of $d$ that are close to $y$ in
the logarithmic scale. To make this precise, we begin by decomposing $S^{(1)}$
using (4.1). We have

$S^{(1)}(x)=\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\sum_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq
Uy\end{subarray}}\sum_{\begin{subarray}{c}\ell\leq\frac{D}{sm}\\\
p(\ell)>Uy\end{subarray}}g(sm\ell)\sum_{\begin{subarray}{c}n\leq\frac{x}{sm\ell}\\\
sm\ell\mid\varphi(sm\ell n)\end{subarray}}1.$

The contribution of $\ell>1$ may be estimated in a similar manner as our
truncation above: the summation conditions imply that
$P(\ell)\mid(n,\varphi(n))$, and so arguing as before, the contribution to
$S^{(1)}$ of $\ell>1$ is

$\ll\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\sum_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq
Uy\end{subarray}}\sum_{\begin{subarray}{c}1<\ell\leq\frac{D}{sm}\\\
p(\ell)>Uy\end{subarray}}\frac{x\log_{2}x}{sm\ell P(\ell)}\ll
x\log_{2}x\bigg{(}\sum_{\begin{subarray}{c}d\leq D\\\ P(d)\leq
Uy\end{subarray}}\frac{1}{d}\bigg{)}\sum_{p>Uy}\frac{1}{p^{2}}\sum_{\begin{subarray}{c}\ell\geq
1\\\ p(\ell)>Uy\\\ P(\ell)\leq p\end{subarray}}\frac{1}{\ell}\ll\frac{x}{U}.$

Thus

$S^{(1)}(x)=S^{(2)}(x)+O\left(x\exp(-\sqrt{\log_{3}x})+\frac{x}{U}\right),$
(4.3)

where

$S^{(2)}(x)=\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\sum_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq
Uy\end{subarray}}g(sm)\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\
sm\mid\varphi(smn)\end{subarray}}1.$

Next, we show that we may ignore the condition $s\mid\varphi(smn)$ with
negligible error. We begin by writing

$\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\ sm\mid\varphi(smn)\\\
(n,m)=1\end{subarray}}1=\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\
m\mid\varphi(smn)\\\
(n,m)=1\end{subarray}}1-\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\
m\mid\varphi(smn)\\\ s\nmid\varphi(smn)\\\ (n,m)=1\end{subarray}}1.$

To estimate the second sum, we apply (i) of Lemma 2.1, ignore the conditions
involving $m$, and then use (3.9) to see that

$\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\ m\mid\varphi(smn)\\\
s\nmid\varphi(smn)\\\
(n,m)=1\end{subarray}}1\leq\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\
s\nmid\varphi(n)\end{subarray}}1\ll\frac{x}{sm}\sum_{p\mid s}\frac{1}{(\log
x)^{1/p}}.$

Here we have used that the fact that $\log(x/sm)\asymp\log x$ since $sm\leq
D$. The contribution to $S^{(2)}$ of these $n$ is then

$\ll\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\sum_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq Uy\end{subarray}}\frac{x}{sm}\sum_{p\mid
s}\frac{1}{(\log x)^{1/p}}\ll x\log y\sum_{p\leq\frac{y}{V}}\frac{1}{p(\log
x)^{1/p}}.$

Since the function $t\mapsto t(\log x)^{1/p}$ is decreasing for
$t\leq\log_{2}x$, the sum over primes is

$\leq\pi\left(\frac{y}{V}\right)\frac{V}{y(\log x)^{V/y}}\ll\frac{1}{e^{V}\log
y}.$

Therefore

$S^{(2)}(x)=S^{(3)}(x)+O\left(x\exp(-\sqrt{\log_{3}x})+\frac{x}{U}+\frac{x}{e^{V}}\right),$
(4.4)

where

$S^{(3)}(x)=\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\sum_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq
Uy\end{subarray}}g(sm)\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\
m\mid\varphi(mn)\\\ (n,m)=1\end{subarray}}1.$

Here the divisibility condition should actually be $m\mid\varphi(smn)$.
However, since $p(m)>P(s)$, we have $(m,s\varphi(s))=1$, and therefore the two
divisibility conditions are equivalent in our ranges of $s$ and $m$.

### 4.3. Restriction to Squarefree Moduli

Next, we remove from $S^{(3)}$ those $m$ which are not squarefree as well as
those $m$ for which $(m,n)>1$. The contribution of those $m$ which are not
squarefree is at most

$\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\sum_{\frac{y}{V}<p\leq
Uy}\sum_{\begin{subarray}{c}m\leq\frac{D}{sp^{2}}\\\ p(m)>\frac{y}{V}\\\
P(m)\leq
Uy\end{subarray}}\frac{x}{smp^{2}}\ll\frac{xV}{y}\ll\frac{x}{\sqrt{y}}$

by our restriction $V\leq\sqrt{y}$. This error may be absorbed into the error
of (4.4), and we now consider the sum

$\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq
Uy\end{subarray}}g(sm)\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\
m\mid\varphi(mn)\end{subarray}}1=\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq Uy\end{subarray}}g(sm)\sum_{g\mid
m}\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\ m\mid\varphi(mn)\\\
(n,m)=g\end{subarray}}1.$

The contribution of $g>1$ is trivially bounded by

$\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq Uy\end{subarray}}\sum_{\begin{subarray}{c}g\mid
m\\\ g>1\end{subarray}}\frac{x}{smg^{2}}\ll x\log
y\sum_{\begin{subarray}{c}g>1\\\ p(g)>\frac{y}{V}\\\ P(g)\leq
Uy\end{subarray}}\frac{x}{g^{2}}\ll\frac{xV\log y}{y},$

and again this may be absorbed into the error term in (4.4). Thus

$S^{(3)}(x)=S^{(4)}(x)+O\left(x\exp(-\sqrt{\log_{3}x})+\frac{x}{U}+\frac{x}{e^{V}}\right),$
(4.5)

where

$S^{(4)}(x)=\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq
Uy\end{subarray}}g(sm)\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\
m\mid\varphi(mn)\\\ (n,m)=1\end{subarray}}1.$

### 4.4. Final Cleaning

Our goal is now to simplify the divisibility condition in the inner sum above.
Heuristically, one expects that $(m,\varphi(m))$ is the largest divisor of $m$
supported on the primes $\leq\log_{2}m$ (see Theorem of 8 of [1]). For $m$
considered in the sums above, however, we have by the Prime Number Theorem
that

$\log_{2}m\leq\log_{2}\bigg{(}\prod_{\frac{y}{V}<p\leq Uy}p\bigg{)}\sim\log
y+\log(U+V)\ll\log y<\frac{y}{V}$

if $y$ is sufficiently large. Thus we expect $(m,\varphi(m))=1$ for most $m$.
Moreover, if $(m,n\varphi(m))=1$, then the conditions $m\mid\varphi(mn)$ and
$m\mid\varphi(n)$ are equivalent. As such, we may replace the divisibility
condition on $m$ with $m\mid\varphi(n)$ by making an error of at most the
contribution from those $m$ with $(m,\varphi(m))>1$.

To estimate this error, we note that since $m$ is squarefree, if
$(m,\varphi(m))>1$, then $m$ is divisible by a pair of primes $p,q$ such that
$q\equiv 1\ (\textnormal{mod}\ p)$. The contribution of these $m$ to
$S^{(4)}(x)$ is bounded by

$\displaystyle x\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\frac{1}{s}\sum_{\frac{y}{V}<p\leq
Uy}\sum_{\begin{subarray}{c}q\leq y\\\ q\equiv 1\ (\textnormal{mod}\
p)\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
P(m)\leq Uy\\\ p(m)>\frac{y}{V}\\\ pq\mid m\end{subarray}}\frac{1}{m}$
$\displaystyle\ll x\log y\sum_{\frac{y}{V}<p\leq
Uy}\frac{1}{p}\sum_{\begin{subarray}{c}q\leq Uy\\\ q\equiv 1\
(\textnormal{mod}\ p)\end{subarray}}\frac{1}{q}$ $\displaystyle\ll x\log
y\log_{2}y\sum_{p>\frac{y}{V}}\frac{1}{p^{2}}$
$\displaystyle\ll\frac{xV\log_{2}y}{y}.$

This error may be absorbed into the error of (4.4). The condition $(n,m)=1$
may now be removed at the cost of the same error we made when introducing it,
and so

$S^{(4)}(x)=S^{(5)}(x)+O\left(x\exp(-\sqrt{\log_{3}x})+\frac{x}{U}+\frac{x}{e^{V}}\right),$
(4.6)

where

$S^{(5)}(x)=\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
p(m)>\frac{y}{V}\\\ P(m)\leq
Uy\end{subarray}}g(sm)\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\
m\mid\varphi(n)\end{subarray}}1.$

### 4.5. Final Truncation

We aim to apply Proposition 3.2 in the form of Corollary 3.4. To do so, the
variable $m$ must have a bounded number of prime factors. Let $K\geq 1$ be a
fixed positive integer. We perform one last truncation and restrict our
attention to those $m$ with $\omega(m)\leq K$. We write

$S^{(5)}(x)=S^{(6)}(x)+E(x),$

where

$S^{(6)}(x)=\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
P(m)\leq y\\\ p(m)>\frac{y}{V}\\\ \omega(m)\leq
K\end{subarray}}g(sm)\sum_{\begin{subarray}{c}n\leq\frac{x}{sm}\\\
m\mid\varphi(n)\end{subarray}}1$ (4.7)

and $E(x)=S^{(5)}(x)-S^{(6)}(x)$. To estimate $E(x)$, we bound the sums over
$n$ trivially and use the binomial theorem to see that

$\left|E(x)\right|\leq\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
P(m)\leq Uy\\\ p(m)>\frac{y}{V}\\\ \omega(m)\geq
K+1\end{subarray}}\frac{x}{sm}\leq x\sum_{\begin{subarray}{c}s\geq 1\\\
P(s)\leq\frac{y}{V}\end{subarray}}\frac{1}{s}\sum_{k\geq
K+1}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m>1\\\
P(m)\leq Uy\\\ p(m)>\frac{y}{V}\\\ \omega(m)=k\end{subarray}}\frac{1}{m}\ll
x\log y\sum_{k\geq K+1}\frac{1}{k!}\bigg{(}\sum_{\frac{y}{V}<p\leq
Uy}\frac{1}{p}\bigg{)}^{k}.$

Using (2.1) and the fact that $U,V\leq\sqrt{y}$, the sum over primes is

$\log\left(\frac{\log(Uy)}{\log(y/V)}\right)+O\left(\exp(-C\sqrt{\log(y/V)})\right)\leq\mathcal{C}\frac{\log
U+\log V}{\log y}.$

for some positive absolute constant $\mathcal{C}$. Therefore

$E(x)\ll x\log y\sum_{k\geq K+1}\frac{\mathcal{C}^{K}}{k!}\left(\frac{\log
U+\log V}{\log y}\right)^{k}\ll_{K}x\log y\left(\frac{\log U+\log V}{\log
y}\right)^{K+1}.$

Combining all of our estimates in this section, we find that

$S(x)=S^{(6)}(x)+O_{K}\left(x\exp(-\sqrt{\log_{3}x})+\frac{x}{U}+\frac{x}{e^{V}}+\log
y\left(\frac{\log U+\log V}{\log y}\right)^{K+1}\right),$ (4.8)

where $S^{(6)}$ is given by (4.7).

## 5\. Evaluation of $S^{(6)}(x)$

We now apply Proposition 3.2 in the form of Corollary 3.4 to the inner sum
over $n$ in $S^{(6)}(x)$, and we have

$\displaystyle S^{(6)}(x)$ $\displaystyle=x\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\leq\frac{D}{s}\\\
P(m)\leq Uy\\\ p(m)>\frac{y}{V}\\\ \omega(m)\leq
K\end{subarray}}\frac{g(sm)}{sm}\prod_{p\mid
m}\left(1-\frac{1}{(\log(x/sm))^{1/(p-1)}}\right)$
$\displaystyle\qquad+O_{K}\bigg{(}D+\sum_{\begin{subarray}{c}s\leq D\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}1<m\leq\frac{D}{s}\\\
P(m)\leq Uy\\\ p(m)>\frac{y}{V}\\\ \omega(m)\leq
K\end{subarray}}\frac{x}{sm}\left(\frac{\log
p(m)}{p(m)}+\frac{\log_{2}x}{p(m)^{2}}\right)\bigg{)}.$

Here the error term $O(D)$ arises from the contribution of $m=1$. The error
term contributes at most

$\left(\frac{V\log
y}{y}+\frac{V^{2}\log_{2}x}{y^{2}}\right)\sum_{\begin{subarray}{c}m\geq 1\\\
P(m)\leq Uy\end{subarray}}\frac{x}{m}\ll x\frac{V\log y(\log y+V)}{y}.$ (5.1)

To evaluate the main term, we would like $\log x$ in the product rather than
$\log(x/sm)$. Note that

$1-\frac{1}{(\log(x/sm))^{1/(p-1)}}=\left(1-\frac{1}{(\log
x)^{1/(p-1)}}\right)\left(1+O\left(\frac{\log D}{p\log x}\right)\right)$

and also

$\prod_{p\mid m}\left(1+O\left(\frac{\log D}{p\log
x}\right)\right)=1+O\left(\frac{K\log D}{p(m)\log x}\right).$

The contribution of the error term above may be absorbed into (5.1). Next, we
extend the sums over $s$ and $m$ to all integers. Using Rankin’s trick in the
form of (2.3), the contribution of $sm>D$ is bounded by

$x\sum_{\begin{subarray}{c}n>D\\\ P(n)\leq
Uy\end{subarray}}\frac{1}{n}\ll\frac{x(\log
y)^{3}}{D^{\frac{1}{\log(Uy)}}}\ll\frac{x}{(\log_{2}x)^{\frac{1}{4}}}.$

The error term $O(D)$ may be absorbed into this term, and so

$\displaystyle S^{(6)}(x)$ $\displaystyle=x\sum_{\begin{subarray}{c}s\geq 1\\\
P(s)\leq\frac{y}{V}\end{subarray}}\operatornamewithlimits{\sum\nolimits^{\flat}}_{\begin{subarray}{c}m\geq
1\\\ P(m)\leq Uy\\\ p(m)>\frac{y}{V}\\\ \omega(m)\leq
K\end{subarray}}\frac{g(sm)}{sm}\prod_{p\mid m}\left(1-\frac{1}{(\log
x)^{1/(p-1)}}\right)$
$\displaystyle\qquad+O_{K}\bigg{(}\frac{x}{(\log_{2}x)^{\frac{1}{4}}}+x\frac{V\log
y(\log y+V)}{y}\bigg{)}.$

The condition $\omega(d)\leq K$ may now be removed with the same error as when
we introduced it, and the main term of $S^{(6)}(x)$ may now be written as the
product

$x\prod_{p\leq\frac{y}{V}}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}\prod_{\frac{y}{V}<p\leq
Uy}\left(1+\frac{g(p)}{p}\left(1-\frac{1}{(\log x)^{1/(p-1)}}\right)\right).$
(5.2)

We simplify the second product slightly by noting that

$(\log x)^{-1/(p-1)}=(\log
x)^{-1/p}\left(1+O\left(\frac{\log_{2}x}{p^{2}}\right)\right)=(\log
x)^{-1/p}+O\left(\frac{\log_{2}x}{p^{2}}\right).$

In the range of $p$ in the second product, we then have

$1+\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/(p-1)}}\right)=\left(1+\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\right)\left(1+O\left(\frac{V}{p^{2}}\right)\right).$

Then since

$\prod_{\frac{y}{V}<p\leq
Uy}\left(1+O\left(\frac{V}{p^{2}}\right)\right)=1+O\left(\frac{V^{2}}{y\log
y}\right),$

the product in (5.2) is

$x\prod_{p\leq\frac{y}{V}}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}\prod_{\frac{y}{V}<p\leq
Uy}\left(1+\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\right)\left(1+O\left(\frac{V^{2}}{y\log y}\right)\right).$

The contribution of the error term is

$\ll\frac{V^{2}}{y\log y}\prod_{p\leq
Uy}\left(1-\frac{1}{p}\right)^{-1}\ll\frac{V^{2}}{y},$

and this may be absorbed into (5.1). Thus

$\displaystyle S^{(6)}(x)$
$\displaystyle=x\prod_{p\leq\frac{y}{V}}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}\prod_{\frac{y}{V}<p\leq
Uy}\left(1+\frac{g(p)}{p}\left(1-\frac{1}{(\log x)^{1/p}}\right)\right)$
$\displaystyle\qquad+O_{K}\bigg{(}\frac{x}{(\log_{2}x)^{\frac{1}{4}}}+x\frac{V\log
y(\log y+V)}{y}+\log y\left(\frac{\log U+\log V}{\log
y}\right)^{K+1}\bigg{)}.$

Inserting the above calculations into (4.8), we find that

$S(x)=x(\mathcal{P}(x)+\mathcal{E}(x)),$ (5.3)

where

$\mathcal{P}(x)=\prod_{p\leq\frac{y}{V}}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}\prod_{\frac{y}{V}<p\leq
Uy}\left(1+\frac{g(p)}{p}\left(1-\frac{1}{(\log x)^{1/p}}\right)\right)$

and

$\left|\mathcal{E}(x)\right|\ll_{K}\exp(-{\textstyle\frac{1}{2}}\sqrt{\log_{3}x})+\frac{1}{U}+\frac{1}{e^{V}}+\log
y\left(\frac{\log U+\log V}{\log y}\right)^{K+1}+\frac{V\log y(\log y+V)}{y}.$
(5.4)

## 6\. Conclusion

It remains to evaluate the product $\mathcal{P}(x)$. To do so, we first write

$\mathcal{P}(x)=\mathcal{M}(x)\mathcal{P}_{1}(x)\mathcal{P}_{2}(x),$

where

$\displaystyle\mathcal{M}(x)$ $\displaystyle=\prod_{p\leq
y}\bigg{(}\sum_{j\geq 0}\frac{g(p^{j})}{p^{j}}\bigg{)}$
$\displaystyle\mathcal{P}_{1}(x)$ $\displaystyle=\prod_{\frac{y}{V}<p\leq
y}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}^{-1}\left(1+\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\right)$ $\displaystyle\mathcal{P}_{2}(x)$
$\displaystyle=\prod_{y<p\leq Uy}\left(1+\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\right).$

Note that

$\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}^{-1}=1-\frac{g(p)}{p}+O\left(\frac{1}{p^{2}}\right),$

and so

$\displaystyle\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}^{-1}\left(1+\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\right)$ $\displaystyle=1-\frac{g(p)}{p(\log
x)^{1/p}}+O\left(\frac{1}{p^{2}}\right)$
$\displaystyle=\left(1-\frac{g(p)}{p(\log
x)^{1/p}}\right)\left(1+O\left(\frac{1}{p^{2}}\right)\right).$

Thus

$\mathcal{P}(x)=\mathcal{M}(x)\mathcal{P}_{1}^{*}(x)\mathcal{P}_{2}(x)+O\left(\frac{V}{y}\right),$

where

$\mathcal{P}_{1}^{*}(x)=\prod_{\frac{y}{V}<p\leq y}\left(1-\frac{g(p)}{p(\log
x)^{1/p}}\right).$

We further investigate the products $\mathcal{P}_{1}^{*}$ and
$\mathcal{P}_{2}$ by noting that if $p\leq y$, then

$1+\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)=\exp\left(\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)+O\left(\frac{1}{p^{2}}\right)\right),$

and if $p>y$, then

$1-\frac{g(p)}{p(\log x)^{1/p}}=\exp\left(-\frac{g(p)}{p(\log
x)^{1/p}}\right)\left(1+O\left(\frac{1}{p^{2}}\right)\right).$

Thus

$\displaystyle\mathcal{P}_{1}^{*}(x)\mathcal{P}_{2}(x)$
$\displaystyle=\exp\bigg{(}-\sum_{\frac{y}{V}<p\leq y}\frac{g(p)}{p(\log
x)^{1/p}}+\sum_{y<p\leq Uy}\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\bigg{)}\prod_{\frac{y}{V}<p\leq
Uy}\left(1+O\left(\frac{1}{p^{2}}\right)\right)$
$\displaystyle=\exp\bigg{(}-\sum_{\frac{y}{V}<p\leq y}\frac{g(p)}{p(\log
x)^{1/p}}+\sum_{y<p\leq Uy}\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\bigg{)}\left(1+O\left(\frac{V}{y\log y}\right)\right).$

Arguing as in the proof of Corollary 1.2, we have

$\bigg{|}\sum_{\frac{y}{V}<p\leq y}\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)-\sum_{y<p\leq Uy}\frac{g(p)}{p(\log
x)^{1/p}}\bigg{|}\ll\frac{1}{\log_{3}x}.$

The contribution of the error term may thus be absorbed into $\mathcal{E}(x)$
in (5.3), and so

$S(x)=x\bigg{(}\mathcal{M}(x)\exp\bigg{(}-\sum_{\frac{y}{V}<p\leq
y}\frac{g(p)}{p(\log x)^{1/p}}+\sum_{y<p\leq
Uy}\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\bigg{)}+\mathcal{E}(x)\bigg{)},$

where $\mathcal{E}(x)$ satisfies (5.4). To complete the proof of Theorem 1.1,
we note that

$\bigg{|}\sum_{p\leq\frac{y}{V}}\frac{g(p)}{p(\log
x)^{1/p}}\bigg{|}\ll\frac{1}{e^{V}\log y}$

and

$\bigg{|}\sum_{p>Uy}\frac{g(p)}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)\bigg{|}\ll\frac{1}{U\log y}.$

As noted in the introduction, $\mathcal{M}(x)\ll\log y$, and so the
contribution of the sums above may be absorbed into $\mathcal{E}(x)$. We have

$\left|\mathcal{E}(x)\right|\ll_{K}\exp(-{\textstyle\frac{1}{2}}\sqrt{\log_{3}x})+\frac{1}{U}+\frac{1}{e^{V}}+\log
y\left(\frac{\log U+\log V}{\log y}\right)^{K+1}+\frac{V\log y(\log y+V)}{y},$

and we conclude the proof of Theorem 1.1 by choosing $U=(\log_{3}x)^{K}$ and
$V=\log_{3}x$, and so

$\left|\mathcal{E}(x)\right|\ll_{K}x\frac{(\log_{4}x)^{K+1}}{(\log_{3}x)^{K}}.$

This is not quite the error term in Theorem 1.1, but since $K$ was arbitrary,
our argument also implies the estimate

$\left|\mathcal{E}(x)\right|\ll_{K}x\frac{(\log_{4}x)^{K+2}}{(\log_{3}x)^{K+1}}\ll_{K}\frac{x}{(\log_{3}x)^{K}}.$

## 7\. Evaluation of Prime Sums

We now consider the expression given in Theorem 1.1 for a variety of
arithmetic functions $g$. First, we need the following consequence of the
Prime Number Theorem with classical error term. Throughout this section, we
regard $K$ is a fixed positive integer governing the precision of our
asymptotic formulas.

######  Lemma 7.1.

For any integer $K\geq 1$, we have

$\displaystyle\sum_{p\leq\log_{2}x}\frac{1}{p(\log x)^{1/p}}$
$\displaystyle=\frac{1}{\log_{3}x}\sum_{k=0}^{K}\frac{a_{k}}{(\log_{3}x)^{k}}+O_{K}\left(\frac{1}{(\log_{3}x)^{K+2}}\right),$
$\displaystyle\sum_{p>\log_{2}x}\frac{1}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)$
$\displaystyle=\frac{1}{\log_{3}x}\sum_{k=0}^{K}\frac{b_{k}}{(\log_{3}x)^{k}}+O_{K}\left(\frac{1}{(\log_{3}x)^{K+2}}\right),$

where

$\displaystyle a_{k}$ $\displaystyle=\int_{1}^{\infty}\frac{(\log
t)^{k}}{te^{t}}\,dt,$ $\displaystyle b_{k}$
$\displaystyle=\int_{1}^{\infty}\frac{(-\log
t)^{k}}{t}\left(1-\frac{1}{e^{1/t}}\right)\,dt.$

###### Proof.

We first truncate to only large values of $p$. As in our proof of Theorem 1.1,
we put $y=\log_{2}x$ for brevity. As already noted, the function $t\mapsto
t(\log x)^{1/t}$ is decreasing for $t\leq y$. Thus for any $A\leq\sqrt{y}$, we
have

$\sum_{p\leq\frac{y}{A}}\frac{1}{pe^{y/p}}\ll\frac{1}{e^{A}\log y}.$

To evaluate the remaining sum, we use the Prime Number Theorem in the form

$\pi(t)=\int_{2}^{t}\frac{1}{\log z}\,dz+R(t),$

where

$R(t)\ll t\exp(-C\sqrt{\log t}).$

Integrating by parts, we have

$\sum_{\frac{y}{A}<p\leq
y}\frac{1}{pe^{y/p}}=\int_{\frac{y}{A}}^{y}\frac{1}{t(\log
t)e^{y/t}}\,dt+O\left(A\exp(-C\sqrt{\log y})\right).$

Changing variables $t\to\frac{y}{t}$, the integral is

$\int_{1}^{A}\frac{1}{t(\log y-\log t)e^{t}}\,dt=\frac{1}{\log
y}\int_{1}^{A}\frac{1}{te^{t}}\left(1-\frac{\log t}{\log y}\right)^{-1}dt.$

If $\left|z\right|\leq\frac{1}{2}$, we have

$\frac{1}{1-z}=\sum_{k=0}^{K}z^{k}+O\left(\frac{1}{z^{K+1}}\right)$

uniformly in $K$. Since $t\leq A\leq\sqrt{y}$, we have

$\int_{1}^{A}\frac{1}{te^{t}}\left(1-\frac{\log t}{\log
y}\right)^{-1}dt=\sum_{k=0}^{K}\frac{1}{(\log y)^{k}}\int_{1}^{A}\frac{(\log
t)^{k}}{te^{t}}\,dt+O_{K}\left(\frac{1}{(\log y)^{K+1}}\right).$

The tails of the integrals are

$\int_{A}^{\infty}\frac{(\log t)^{k}}{te^{t}}\,dt\ll_{K}\frac{(\log
A)^{k}}{Ae^{A}},$

and so

$\frac{1}{\log y}\int_{1}^{A}\frac{1}{te^{t}}\left(1-\frac{\log t}{\log
y}\right)^{-1}dt=\frac{1}{\log y}\sum_{k=0}^{K}\frac{a_{k}}{(\log
y)^{k}}+O_{K}\left(\frac{1}{Ae^{A}}+\frac{1}{(\log y)^{K+2}}\right).$

Choosing $A=\log y$, we obtain the first equality of the lemma, and the second
follows by a similar argument.

∎

The coefficients $a_{k}$ and $b_{k}$ actually arise from the Laurent series of
$\Gamma(s)$ around $s=0$, where $\Gamma$ is the usual gamma function. To see
this, let

$F(s)=\int_{1}^{\infty}\left(1-\frac{1}{e^{1/t}}\right)\frac{t^{-s}}{t}\,dt-\int_{1}^{\infty}\frac{t^{s}}{te^{t}}\,dt$

and observe that $b_{k}-a_{k}=F^{(k)}(0)$. Changing variables $t\to t^{-1}$ in
the first integral, we have

$F(s)=\int_{0}^{1}\left(1-\frac{1}{e^{t}}\right)\frac{t^{s}}{t}\,dt-\int_{1}^{\infty}\frac{t^{s}}{te^{t}}\,dt=\frac{1}{s}-\Gamma(s).$

### 7.1. Asymptotics for Indicator Functions

Let $\mathcal{B}$ be a set of integers whose indicator function $f$ is
multiplicative. Then, as stated in the introduction, we have

$f(n)=\sum_{d\mid n}g(d)$

for a multiplicative function $g$ with $\left|g(n)\right|\leq 1$ for all $n$.
More specifically, we have $g(p^{j})=f(p^{j})-f(p^{j-1})$ for all $j\geq 1$,
and in particular, $g(p)=f(p)-1$. Thus

$\displaystyle\mathcal{Q}_{g}(x)$
$\displaystyle=-\sum_{p\leq\log_{2}x}\frac{f(p)-1}{p(\log
x)^{1/p}}+\sum_{p>\log_{2}x}\frac{f(p)-1}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)$ (7.1)
$\displaystyle=\mathcal{Q}_{f}(x)+\frac{1}{\log_{3}x}\sum_{k=0}^{K}\frac{a_{k}-b_{k}}{(\log_{3}x)^{k}}+O_{K}\left(\frac{1}{(\log_{3}x)^{K+2}}\right)$

by Lemma 7.1. Likewise

$\displaystyle\prod_{p\leq\log_{2}x}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}$
$\displaystyle=\prod_{p\leq\log_{2}x}\left(1-\frac{1}{p}\right)\bigg{(}\sum_{j\geq
0}\frac{f(p^{j})}{p^{j}}\bigg{)}$
$\displaystyle=\frac{1}{e^{\gamma}\log_{3}x}\prod_{p\leq\log_{2}x}\bigg{(}\sum_{j\geq
0}\frac{f(p^{j})}{p^{j}}\bigg{)}+O\left(\exp(-C\sqrt{\log_{3}x})\right)$

by (2.1). Thus, for certain coefficients $c_{k}$, we have

$\sum_{\begin{subarray}{c}n\leq x\\\
(n,\varphi(n))\in\mathcal{B}\end{subarray}}1=\mathcal{F}(x)\frac{x}{e^{\gamma}\log_{3}x}\bigg{(}1+\sum_{k=1}^{K}\frac{c_{k}}{(\log_{3}x)^{k}}\bigg{)}+O_{K}\left(\frac{1}{(\log_{3}x)^{K+2}}\right),$
(7.2)

where

$\mathcal{F}(x)=\bigg{(}\prod_{p\leq\log_{2}x}\sum_{j\geq
0}\frac{f(p^{j})}{p^{j}}\bigg{)}\exp(\mathcal{Q}_{f}(x)).$

In fact, the coefficients $c_{k}$ are exactly the coefficients in (1.2). We
now specialize $f$ to certain sets $\mathcal{B}$.

####  7.1.1 $r$th Powers

If $\mathcal{B}$ is the set of $r$th powers for some $r\geq 2$, then $f(p)=0$
for all $p$, and so $\mathcal{Q}_{f}(x)=0$. Likewise

$\prod_{p\leq\log_{2}x}\sum_{j\geq
0}\frac{f(p^{j})}{p^{j}}=\prod_{p\leq\log_{2}x}\left(1-\frac{1}{p^{r}}\right)^{-1}=\zeta(r)+O\left(\frac{1}{(\log_{2}x)^{r-1}\log_{3}x}\right),$

and so (7.2) gives

$\sum_{\begin{subarray}{c}n\leq x\\\
(n,\varphi(n))=m^{r}\end{subarray}}1=\frac{\zeta(r)x}{e^{\gamma}\log_{3}x}\bigg{(}1+\sum_{k=1}^{K}\frac{c_{k}}{(\log_{3}x)^{k}}\bigg{)}+O_{K}\left(\frac{x}{(\log_{3}x)^{K+2}}\right).$
(7.3)

The above argument also works if $r=0$ upon noting that $\mathcal{F}(x)=1$ in
this case, and so we recover (1.2) by a different proof than that originally
given by Pollack in [7].

####  7.1.2 $r$-free Integers

If $\mathcal{B}$ is the set of integers free of $r$th powers of primes, then
$f(p^{j})=0$ for $j\geq r$. In particular, $f(p)=1$, and so
$\mathcal{Q}_{g}(x)=0$ by (7.1). Thus

$\displaystyle\prod_{p\leq\log_{2}x}\sum_{j\geq
0}\frac{f(p^{j})}{p^{j}}=\prod_{p\leq\log_{2}x}\bigg{(}\sum_{j\leq
r-1}\frac{1}{p^{j}}\bigg{)}$
$\displaystyle=\prod_{p\leq\log_{2}x}\left(1-\frac{1}{p}\right)^{-1}\left(1-\frac{1}{p^{r}}\right)$
$\displaystyle=\frac{e^{\gamma}x\log_{3}x}{\zeta(r)}+O\left(\exp(-C\sqrt{\log_{3}x})\right)$

by (2.2). Therefore

$\sum_{\begin{subarray}{c}n\leq x\\\ (n,\varphi(n))\ \text{is
$r$-free}\end{subarray}}1=\frac{x}{\zeta(r)}+O_{K}\left(\frac{x}{(\log_{3}x)^{K+2}}\right).$
(7.4)

####  7.1.3 Sums of Squares

If $\mathcal{B}$ is the set of integers representable as a sum of two squares,
then

$f(p^{j})=\begin{cases}1&\text{if $p=2$ or $p\equiv 1\ (\textnormal{mod}\
4)$},\\\ 1&\text{if $p\equiv 3\ (\textnormal{mod}\ 4)$ and $j$ is even},\\\
0&\text{if $p\equiv 3\ (\textnormal{mod}\ 4)$ and $j$ is odd}.\end{cases}$

Thus

$\prod_{p\leq\log_{2}x}\sum_{j\geq
0}\frac{f(p^{j})}{p^{j}}=2\prod_{\begin{subarray}{c}p\leq\log_{2}x\\\ p\equiv
1\ (\textnormal{mod}\
4)\end{subarray}}\left(1-\frac{1}{p}\right)^{-1}\prod_{\begin{subarray}{c}p\leq\log_{2}x\\\
p\equiv 3\ (\textnormal{mod}\
4)\end{subarray}}\left(1-\frac{1}{p^{2}}\right)^{-1}.$

We rewrite the square of the sum as

$\displaystyle\bigg{(}\prod_{p\leq\log_{2}x}\sum_{j\geq
0}\frac{f(p^{j})}{p^{j}}\bigg{)}^{2}$
$\displaystyle=2\prod_{p\leq\log_{2}x}\left(1-\frac{1}{p}\right)^{-1}\prod_{p\leq\log_{2}x}\left(1-\frac{\chi_{4}(p)}{p}\right)^{-1}\prod_{\begin{subarray}{c}p\leq\log_{2}x\\\
p\equiv 3\ (\textnormal{mod}\
4)\end{subarray}}\left(1-\frac{1}{p^{2}}\right)^{-1}$ $\displaystyle=\frac{\pi
e^{\gamma}\log_{3}x}{2}\prod_{p\equiv 3\ (\textnormal{mod}\
4)}\left(1-\frac{1}{p^{2}}\right)^{-1}\left(1+O\left(\exp(-C\sqrt{\log_{3}x})\right)\right),$

where $\chi_{4}$ is the nontrivial Dirichlet character mod 4. Thus

$\prod_{p\leq\log_{2}x}\bigg{(}\sum_{j\geq
0}\frac{g(p^{j})}{p^{j}}\bigg{)}=\frac{\sqrt{\pi}B}{\sqrt{e^{\gamma}\log_{3}x}}\left(1+O\left(\exp(-C\sqrt{\log_{3}x})\right)\right),$

where $B$ is the usual Landau-Ramanujan constant given by

$B^{2}=\frac{1}{2}\prod_{p\equiv 3\ (\textnormal{mod}\
4)}\left(1-\frac{1}{p^{2}}\right)^{-1}.$

To evaluate $\mathcal{Q}_{g}(x)$, we note that

$\mathcal{Q}_{g}(x)=\sum_{\begin{subarray}{c}p\leq\log_{2}x\\\ p\equiv 3\
(\textnormal{mod}\ 4)\end{subarray}}\frac{1}{p(\log
x)^{1/p}}-\sum_{\begin{subarray}{c}p>\log_{2}x\\\ p\equiv 3\
(\textnormal{mod}\ 4)\end{subarray}}\frac{1}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right).$

The prime number theorem for primes $p\equiv 3\ (\textnormal{mod}\ 4)$ states
that

$\pi(x;3,4)=\frac{1}{2}\int_{2}^{x}\frac{dt}{\log t}+O\left(t\exp(-C\sqrt{\log
t})\right).$

Arguing as in the proof of Lemma 7.1, we have

$\displaystyle\sum_{\begin{subarray}{c}p\leq\log_{2}x\\\ p\equiv 3\
(\textnormal{mod}\ 4)\end{subarray}}\frac{1}{p(\log x)^{1/p}}$
$\displaystyle=\frac{1}{2\log_{3}x}\sum_{k=0}^{K}\frac{a_{k}}{(\log_{3}x)^{k}}+O_{K}\left(\frac{1}{(\log_{3}x)^{K+2}}\right),$
$\displaystyle\sum_{\begin{subarray}{c}p>\log_{2}x\\\ p\equiv 3\
(\textnormal{mod}\ 4)\end{subarray}}\frac{1}{p}\left(1-\frac{1}{(\log
x)^{1/p}}\right)$
$\displaystyle=\frac{1}{2\log_{3}x}\sum_{k=0}^{K}\frac{b_{k}}{(\log_{3}x)^{k}}+O_{K}\left(\frac{1}{(\log_{3}x)^{K+2}}\right).$

Combining all of the estimates above, we find that there are constants $d_{k}$
such that

$\sum_{\begin{subarray}{c}n\leq x\\\
(n,\varphi(n))\in\mathcal{B}\end{subarray}}1=\frac{\sqrt{\pi}Bx}{\sqrt{e^{\gamma}\log_{3}x}}\bigg{(}1+\sum_{k=1}^{K}\frac{d_{k}}{(\log_{3}x)^{k}}\bigg{)}+O_{K}\left(\frac{1}{(\log_{3}x)^{K+\frac{3}{2}}}\right).$
(7.5)

### 7.2. The Average Number of Divisors of $(n,\varphi(n))$

We conclude by studying the average number of divisors of $(n,\varphi(n))$,
which was the original motivation for this work. In this case, we have
$f(n)=\tau(n)$, so $g(n)=1$. Combining Theorem 1.1 and Lemma 7.1, we have

$\sum_{n\leq
x}\tau((n,\varphi(n)))=e^{\gamma}x\log_{3}x\exp\bigg{(}\frac{1}{\log_{3}x}\sum_{k=0}^{K}\frac{b_{k}-a_{k}}{(\log_{3}x)^{k}}\bigg{)}+O_{K}\left(\frac{x}{(\log_{3}x)^{K}}\right).$

In particular, there exist constants $c_{k}^{\prime}$ such that

$\sum_{n\leq
x}\tau((n,\varphi(n)))=e^{\gamma}x\log_{3}x\bigg{(}1+\sum_{k=1}^{K}\frac{c_{k}^{\prime}}{(\log_{3}x)^{k}}\bigg{)}+O_{K}\left(\frac{x}{(\log_{3}x)^{K}}\right).$
(7.6)

## References

  * [1] P. Erdős, F. Luca, and C. Pomerance.  On the proportion of numbers coprime to a given integer.  In Anatomy of integers, volume 46 of CRM Proc. Lecture Notes, pages 47–64. Amer. Math. Soc., Providence, RI, 2008.
  * [2] P. Erdös.  Some asymptotic formulas in number theory.  J. Indian Math. Soc. (N.S.), 12:75–78, 1948.
  * [3] H. Halberstam and H.-E. Richert.  Sieve methods.  London Mathematical Society Monographs, No. 4. Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974.
  * [4] D. Koukoulopoulos.  The distribution of prime numbers, volume 203 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, [2019] ©2019.
  * [5] N. Lebowitz-Lockard, P. Pollack, and A. S. Roy.  Distribution mod p of Euler’s Totient and the Sum of Proper Divisors.  Michigan Mathematical Journal, pages 1 – 24, 2023.
  * [6] P. Pollack.  Numbers which are orders only of cyclic groups.  Proc. Amer. Math. Soc., 150(2):515–524, 2022.
  * [7] P. Pollack.  Numbers which are orders only of cyclic groups.  Proc. Amer. Math. Soc., 150(2):515–524, 2022.
  * [8] C. Pomerance.  On the distribution of amicable numbers.  J. Reine Angew. Math., 293(294):217–222, 1977.
  * [9] T. Szele.  Über die endichen Ordnungszahlen, zu denen nur eine Gruppe gehört.  Comment. Math. Helv., 20:265–267, 1947.