1 Introduction
Let
$s(n)$
denote the sum-of-proper-divisors function of an integer
$n$
, i.e.
$s(n)=\unicode[STIX]{x1D70E}(n)-n$
. The function
$s(\cdot )$
has been a source of fascination since the time of the ancient Greeks, who classified numbers as perfect, abundant, or deficient, according to whether
$s(n)=n$
,
$s(n)>n$
, or
$s(n)<n$
. Two thousand years later, the desire to understand statistical properties of
$s(n)$
played a motivating role in the early development of probabilistic number theory by figures such as Schoenberg, Davenport, Erdős, and Wintner.
It is interesting that the function
$s$
can map sets of asymptotic density 0 to sets of positive density. Indeed, if
$\mathscr{A}$
is the set of numbers
$pq$
, where
$p,q$
are primes, then
$\mathscr{A}$
has zero asymptotic density, yet
$s(\mathscr{A})$
has asymptotic density
$1/2$
, the latter claim coming from the fact that the Goldbach conjecture has at most a zero-density set of exceptions. We also know of sets
$\mathscr{A}$
of positive density such that
$s^{-1}(\mathscr{A})$
not only has zero density, but, in fact, is empty (see Erdős [Reference Erdős6]).
Our focus in this paper is on what can be said about
$s^{-1}(\mathscr{A})$
when
$\mathscr{A}$
has asymptotic density 0. Part of the landscape here is a conjecture proposed by Erdős, Granville, Pomerance, and Spiro [Reference Erdős, Granville, Pomerance, Spiro and Bateman7] (hereafter “EGPS”) in their study of the iterates of
$s(n)$
.
Conjecture 1.1. Let
$\mathscr{A}$
be a set of asymptotic density zero. Then
$s^{-1}(\mathscr{A})$
also has asymptotic density zero.
If true, a consequence (see [Reference Erdős, Granville, Pomerance, Spiro and Bateman7]) would be that for each fixed positive integer
$k$
, but for a set of numbers
$n$
of asymptotic density zero, if
$s(n)<n$
, then
$s_{k}(n)<s_{k-1}(n)<\cdots <n$
, where
$s_{j}$
is the
$j$
-fold iteration of
$s$
. With the inequality signs reversed, this is an unconditional theorem of Erdős. Another consequence of Conjecture 1.1 is given in [Reference Pollack, Pomerance, Butler, Cooper and Hurlbert17].
Some special cases of the EGPS conjecture can be read out of the literature. For example, it is proved in [Reference Pollack11] that if
$\mathscr{A}$
is the set of primes, then the counting function of
$s^{-1}(\mathscr{A})$
is
$O(x/\text{log}\,x)$
. In addition, Troupe showed in [Reference Troupe20] that
$s^{-1}(\mathscr{A}_{\unicode[STIX]{x1D716}})$
has density zero for each of the sets
$$\begin{eqnarray}\mathscr{A}_{\unicode[STIX]{x1D716}}=\{m:|\unicode[STIX]{x1D714}(m)-\log \log m|>\unicode[STIX]{x1D716}\log \log m\}.\end{eqnarray}$$
In [Reference Pollack12], it is shown that
$s^{-1}(\mathscr{A})$
has density zero when
$\mathscr{A}$
is the set of palindromes (in any given base). All of these arguments make critical use of structural features of
$\mathscr{A}$
; the methods do not carry over to arbitrary sets with similar counting functions.
In the present paper, we make some partial progress on Conjecture 1.1. In contrast with the aforementioned results, the structure of
$\mathscr{A}$
is irrelevant in the theorem, but we must assume a strong condition on the count of elements of
$\mathscr{A}$
.
Theorem 1.2. Let
$\unicode[STIX]{x1D716}=\unicode[STIX]{x1D716}(x)$
be a fixed function tending to
$0$
as
$x\rightarrow \infty$
. Suppose that
$\mathscr{A}$
is a set of at most
$x^{1/2+\unicode[STIX]{x1D716}(x)}$
positive integers. Then, as
$x\rightarrow \infty$
,
$$\begin{eqnarray}\#\{n\leqslant x:s(n)\in \mathscr{A}\}=o_{\unicode[STIX]{x1D716}}(x),\end{eqnarray}$$
uniformly in the choice of
$\mathscr{A}$
.
As an example, as
$s(n)<2n\log \log n$
for all large
$n$
and as there are only
$O_{b}(\sqrt{x\log \log x})$
base-
$b$
palindromes up to
$2x\log \log x$
, Theorem 1.2 implies the theorem of [Reference Pollack12] alluded to above.
Our proof of Theorem 1.2 is presented in §2. We borrow some ideas from recent work of Booker [Reference Booker3]; Booker’s arguments by themselves almost immediately give the slightly weaker result with
$x^{1/2+\unicode[STIX]{x1D716}(x)}$
replaced by
$x^{1/2-\unicode[STIX]{x1D716}}$
for any fixed (constant)
$\unicode[STIX]{x1D716}>0$
.
EGPS [Reference Erdős, Granville, Pomerance, Spiro and Bateman7, p. 170] point out that their Conjecture 1.1 would be a consequence of the following assertion about the sizes of elements in a fiber.
Hypothesis 1.3. For each positive number
$\unicode[STIX]{x1D703}$
there exists a constant
$C_{\unicode[STIX]{x1D703}}$
such that for all positive integers
$m$
there exist at most
$C_{\unicode[STIX]{x1D703}}$
numbers
$n\leqslant \unicode[STIX]{x1D703}m$
with
$s(n)=m$
.
The authors write in [Reference Erdős, Granville, Pomerance, Spiro and Bateman7]: “We are not sure we believe this hypothesis and in fact it may be possible to disprove it”. Our second theorem, shown in §3, disproves Hypothesis 1.3 in a strong way.
Theorem 1.4. There is a constant
$c>0$
for which the following holds. Let
$\unicode[STIX]{x1D6FC}$
and
$\unicode[STIX]{x1D716}$
be positive real numbers. There are infinitely many
$m$
with at least
$\exp (c\log m/\text{log}\,\log m)$
$s$
-preimages that lie in the interval
$(\unicode[STIX]{x1D6FC}(1-\unicode[STIX]{x1D716})m,\unicode[STIX]{x1D6FC}(1+\unicode[STIX]{x1D716})m)$
.
Our proof of Theorem 1.4 shows that
$c=1/7$
is admissible.
In §4, we use ideas presented in the previous sections to study solutions to equations of the form
$\unicode[STIX]{x1D70E}(n)=kn+a$
, where
$k$
and
$a$
are integers and
$k\geqslant 0$
. Such equations have been studied extensively by the second author over the course of his career, dating back to a 1975 paper [Reference Pomerance18], and are connected to many classical problems in number theory. We show that a conjecture in [Reference Anavi, Pollack and Pomerance2], that was modified in [Reference Pollack and Pomerance16], needs to be further modified. Furthermore, we show that an upper bound for the count of
$n\leqslant x$
satisfying
$\unicode[STIX]{x1D70E}(n)\equiv a~(\text{mod}~n)$
, which is given in [Reference Pomerance18], can be made uniform in
$a$
. In particular, we prove the following.
Theorem 1.5. For any integer
$a$
, the number of
$n\leqslant x$
with
$\unicode[STIX]{x1D70E}(n)\equiv a~(\text{mod}~n)$
is
$O(x/\text{log}\,x)$
, uniformly in
$a$
.
We remark that [Reference Pomerance18, Corollary 3] appears to give a uniform upper bound, but the dependence on
$a$
is suppressed in the notation.
Notation
Throughout this paper,
$n$
and
$m$
denote positive integers and
$\ell$
,
$p$
, and
$q$
are primes. We let
$P(n)$
and
$P^{-}(n)$
denote the largest and smallest prime factors of
$n$
, respectively, and we let
$\operatorname{rad}(n)=\prod _{p\mid n}p$
. We write
$\log _{k}x$
for the
$k$
th iterate of the natural logarithm function at
$x$
.
2 The preimages of very sparse sets: proof of Theorem 1.2
By replacing
$\unicode[STIX]{x1D716}(x)$
with
$\max \{\unicode[STIX]{x1D716}(x),1/\text{log}\,\log x\}$
, we can assume that
$x^{\unicode[STIX]{x1D716}(x)}\geqslant x^{1/\text{log}\,\log x}$
. We start by introducing a set
$\mathscr{E}$
of “exceptional preimages”. We let
$\mathscr{E}$
be the set of
$n\leqslant x$
such that at least one of the following holds:
(a)
$n$
has no prime factor in
$(1,\log x]$
;(b)
$n$
has a divisor in
$(x^{1/2-10\unicode[STIX]{x1D716}(x)},x^{1/2+10\unicode[STIX]{x1D716}(x)})$
;(c)
$n$
has a squarefull part exceeding
$x^{2\unicode[STIX]{x1D716}(x)}$
;(d)
$n\leqslant \sqrt{x}$
.
By a simple sieve (inclusion–exclusion), there are
$\ll x/\text{log}\,\log x$
numbers
$n\leqslant x$
satisfying (a). Known results on the distribution of divisors (see, e.g., the sharp result of Ford [Reference Ford8, Theorem 1]) imply that the number of
$n\leqslant x$
satisfying (b) is
$o(x)$
. The number of
$n\leqslant x$
satisfying (c) is
$\ll x^{1-\unicode[STIX]{x1D716}(x)}$
, which is also
$o(x)$
. Finally, the number of
$n$
satisfying (d) is trivially
$O(x^{1/2})$
. We conclude that
$\#\mathscr{E}=o(x)$
. Thus, for the sake of proving the theorem, it suffices to bound the number of non-exceptional
$n$
with
$s(n)\in \mathscr{A}$
.
We will show that for each
$a\in \mathscr{A}$
, the number of non-exceptional preimages of
$a$
is
$\ll x^{1/2-9\unicode[STIX]{x1D716}(x)}$
. As
$\#\mathscr{A}\leqslant x^{1/2+\unicode[STIX]{x1D716}(x)}$
, the theorem follows.
Let
$a\in \mathscr{A}$
, and let
$n$
be a non-exceptional preimage of
$a$
. Write
$n=de$
, where
$d$
is the largest divisor of
$n$
not exceeding
$\sqrt{x}$
. As
$n$
is non-exceptional,
$d\leqslant x^{1/2-10\unicode[STIX]{x1D716}(x)}$
.
As
$n>\sqrt{x}$
, we have
$e>1$
. Let
$p$
be any prime divisor of
$e$
. Then
$dp\mid n$
. By the choice of
$d$
, we have
$dp>\sqrt{x}$
, and, as
$n$
is non-exceptional,
$$\begin{eqnarray}dp\geqslant x^{1/2+10\unicode[STIX]{x1D716}(x)}.\end{eqnarray}$$
Thus,
$$\begin{eqnarray}p\geqslant x^{1/2+10\unicode[STIX]{x1D716}(x)}/d\geqslant x^{20\unicode[STIX]{x1D716}(x)}.\end{eqnarray}$$
If
$p$
divides both
$d$
and
$e$
, then
$n$
has squarefull part at least
$p^{2}\geqslant x^{40\unicode[STIX]{x1D716}(x)}$
, contradicting that
$n$
is non-exceptional. Hence,
$\operatorname{gcd}(d,e)=1$
.
Observe that
$$\begin{eqnarray}\displaystyle \frac{\unicode[STIX]{x1D70E}(e)}{e} & = & \displaystyle \mathop{\prod }_{p^{k}||e}\biggl(1+\frac{1}{p}+\cdots +\frac{1}{p^{k}}\biggr)\leqslant \mathop{\prod }_{p|e}\biggl(1+\frac{1}{p-1}\biggr)\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \exp \biggl(\mathop{\sum }_{p|e}\frac{1}{p-1}\biggr)\leqslant \exp \biggl(\frac{\unicode[STIX]{x1D714}(e)}{P^{-}(e)-1}\biggr)\leqslant \exp \biggl(\frac{2\unicode[STIX]{x1D714}(e)}{P^{-}(e)}\biggr),\nonumber\end{eqnarray}$$
where
$\unicode[STIX]{x1D714}(e)$
is the number of distinct primes dividing
$e$
. But
$\unicode[STIX]{x1D714}(e)\leqslant \log e/\text{log}\,2\leqslant \log x/\text{log}\,2$
whereas, from (2.2),
$P^{-}(e)\geqslant x^{20\unicode[STIX]{x1D716}(x)}\gg (\log x)^{2}$
. So,
$\exp (2\unicode[STIX]{x1D714}(e)/P^{-}(e))=1+O(\log x/P^{-}(e))$
, and hence
$$\begin{eqnarray}\frac{s(e)}{e}=\frac{\unicode[STIX]{x1D70E}(e)}{e}-1\ll \frac{\log x}{P^{-}(e)}.\end{eqnarray}$$
Keeping in mind that
$de=n\leqslant x$
, we deduce that
$$\begin{eqnarray}s(e)\ll e\frac{\log x}{P^{-}(e)}\leqslant \frac{x\log x}{d\cdot P^{-}(e)}\leqslant x^{1/2-10\unicode[STIX]{x1D716}(x)}\log x;\end{eqnarray}$$
here the last inequality follows from (2.1).
As
$\operatorname{gcd}(d,e)=1$
, we also have that
$$\begin{eqnarray}a=s(de)=\unicode[STIX]{x1D70E}(d)s(e)+s(d)e.\end{eqnarray}$$
So if
$g=\operatorname{gcd}(\unicode[STIX]{x1D70E}(d),s(d))$
, then
$g\mid a$
, and
$a/g=(\unicode[STIX]{x1D70E}(d)/g)s(e)+(s(d)/g)e$
. Hence,
$$\begin{eqnarray}s(e)(\unicode[STIX]{x1D70E}(d)/g)\equiv a/g~(\text{mod}~s(d)/g).\end{eqnarray}$$
As
$\unicode[STIX]{x1D70E}(d)/g$
and
$s(d)/g$
are relatively prime, given
$d$
we see that
$s(e)$
lies in a uniquely determined residue class modulo
$s(d)/g$
. Combined with (2.3), we deduce that the number of possibilities for
$s(e)$
is
$\ll 1+x^{1/2-10\unicode[STIX]{x1D716}(x)}\log x\cdot g/s(d)$
. Moreover,
$s(d)\geqslant d/P^{-}(d)\geqslant d/\text{log}\,x$
. So the number of choices for
$s(e)$
, given
$d$
, is
$$\begin{eqnarray}\ll 1+x^{1/2-10\unicode[STIX]{x1D716}(x)}(\log x)^{2}g/d.\end{eqnarray}$$
From (2.4),
$d$
and
$s(e)$
determine
$e$
, and hence this last displayed quantity is also a bound on the number of possibilities for
$n=de$
, given
$d$
.
We now sum the upper bound displayed above on possible values of
$g$
and
$d$
. Each
$d$
under consideration has the form
$gh$
, where
$h\leqslant x^{1/2-10\unicode[STIX]{x1D716}(x)}/g$
. Thinking of
$g$
as fixed and summing on
$d=gh$
gives a bound of
$\ll (\log x)^{3}x^{1/2-10\unicode[STIX]{x1D716}(x)}$
. Summing on the
$\unicode[STIX]{x1D70F}(a)$
divisors
$g$
of
$a$
bounds the number of possibilities for
$n$
by
$\ll \unicode[STIX]{x1D70F}(a)(\log x)^{3}x^{1/2-10\unicode[STIX]{x1D716}(x)}$
. As
$a<\unicode[STIX]{x1D70E}(n)\ll x\,\text{log}\,\log x$
, by the maximal order of the divisor function,
$\unicode[STIX]{x1D70F}(a)\leqslant x^{0.7/\text{log}\,\log x}$
for large
$x$
. As
$x^{0.7/\text{log}\,\log x}(\log x)^{3}<x^{1/\text{log}\,\log x}\leqslant x^{\unicode[STIX]{x1D716}(x)}$
for large
$x$
, we see that the number of
$n$
that arise in this way is
$\ll x^{1/2-9\unicode[STIX]{x1D716}(x)}$
, as claimed.
3 Disproof of Hypothesis 1.3: proof of Theorem 1.4
The following can be deduced from [Reference Alford, Granville and Pomerance1, Theorem 2.1].
Theorem 3.1. For each
$\unicode[STIX]{x1D716}>0$
and number
$x$
sufficiently large depending on
$\unicode[STIX]{x1D716}$
, there is a finite set
$\{m_{1},m_{2},\ldots ,m_{t}\}$
of integers, where
$t$
depends only on
$\unicode[STIX]{x1D716}$
and each
$m_{i}>\log x$
, with the following property. If
$m\leqslant x^{5/12-\unicode[STIX]{x1D716}}$
and
$m$
is not divisible by any of
$m_{1},\ldots ,m_{t}$
, then for each integer
$u$
coprime to
$m$
, there are
$\gg _{\unicode[STIX]{x1D716}}x/\unicode[STIX]{x1D711}(m)\log x$
primes
$p\leqslant x$
with
$p\equiv u~(\text{mod}~m)$
.
We prove the following result, which generalizes ideas of Prachar [Reference Prachar19] and Erdős [Reference Erdős5].
Theorem 3.2. There is a positive absolute constant
$c$
such that, for all pairs of integers
$a,b$
with
$a\neq 0,b>0$
, there are infinitely many integers
$k$
with more than
$\exp (c\log k/\text{log}\,\log k)$
representations as
$(bp+a)(bq+a)$
with
$p,q$
primes.
Proof of Theorem 3.2.
We fix a choice for
$a,b$
and let
$v=\max \{|a|,b\}$
. We choose
$x,\unicode[STIX]{x1D716}$
in Theorem 3.1 with
$x>\text{e}^{v}$
and
$\unicode[STIX]{x1D716}={\textstyle \frac{1}{13}}$
. Let
$\mathscr{E}$
be the smallest set of primes such that each exceptional
$m_{i}$
from Theorem 3.1 has a prime factor in
$\mathscr{E}$
. Let
$M$
be the product of all odd primes
${\leqslant}{\textstyle \frac{1}{3}}\log x$
that are not in
$\mathscr{E}$
and do not divide
$ab$
. As
$x>\text{e}^{v}$
, it follows that
$|a|,b<\log x$
, so the number of prime factors of
$ab$
is
$\ll \log \log x$
. We have
$\unicode[STIX]{x1D714}(M)\sim {\textstyle \frac{1}{3}}\log x/\text{log}\,\log x$
and
$M=x^{1/3+o(1)}$
. For each
$d\mid M$
, let
$r_{d}$
be the solution to
$br_{d}+a\equiv 0~(\text{mod}~d)$
. As
$a,b$
are coprime to
$d$
, we must have
$r_{d}$
coprime to
$d$
as well. Consider the primes
$p\leqslant x$
with
$bp+a\equiv 0~(\text{mod}~d)$
. These are the primes
$p\equiv r_{d}~(\text{mod}~d)$
. By Theorem 3.1 there are
$\gg x/\unicode[STIX]{x1D711}(d)\log x$
such
$p$
.
Now also look at primes
$q\leqslant x$
with
$(bq+a,M)=M/d$
. In order that
$r$
mod
$M$
be a coprime residue class with
$(br+a,M)=M/d$
, it is necessary and sufficient that
$$\begin{eqnarray}r\equiv -a/b~(\text{mod}~\ell )\quad \text{for all}~\ell \biggm\vert\frac{M}{d}\end{eqnarray}$$
and
$$\begin{eqnarray}r\not \equiv 0,-a/b~(\text{mod}~\ell )\quad \text{for all}~\ell \mid d.\end{eqnarray}$$
There are precisely
$\prod _{\ell \mid d}(\ell -2)$
such residue classes
$r~\text{mod}~M$
, and so the number of primes
$q\leqslant x$
belonging to one of these classes is
$$\begin{eqnarray}\gg \frac{x}{\log x}\frac{\mathop{\prod }_{\ell \mid d}(\ell -2)}{\unicode[STIX]{x1D711}(M)}.\end{eqnarray}$$
The number of pairs
$p,q$
is therefore
$$\begin{eqnarray}\gg \frac{x}{\unicode[STIX]{x1D711}(d)\log x}\cdot \frac{x\mathop{\prod }_{\ell \mid d}(\ell -2)}{\unicode[STIX]{x1D711}(M)\log x}=\frac{x^{2}}{\log ^{2}x}\cdot \frac{1}{\unicode[STIX]{x1D711}(M)}\mathop{\prod }_{\ell \mid d}\frac{\ell -2}{\ell -1}\gg \frac{x^{2}}{M\log ^{2}x}.\end{eqnarray}$$
Because of the condition
$(bq+a,M)=M/d$
, different values of
$d$
correspond to different values of
$q$
. Thus, we must have
$$\begin{eqnarray}\gg \frac{x^{2}\unicode[STIX]{x1D70F}(M)}{M\log ^{2}x}\end{eqnarray}$$
pairs
$p,q$
running over all values
$d$
. Map each pair
$p,q$
to
$(bp+a)(bq+a)\ll v^{2}x^{2}$
. The number of integers
$\ll v^{2}x^{2}$
divisible by
$M$
is
$\ll v^{2}x^{2}/M$
. By the Pigeonhole Principle, there exists some
$k\ll v^{2}x^{2}$
with
$\gg (x^{2}\unicode[STIX]{x1D70F}(M)/M\log ^{2}x)/$
$(v^{2}x^{2}/M)$
representations as
$(bp+a)(bq+a)$
, which is
$$\begin{eqnarray}\displaystyle \gg \frac{\unicode[STIX]{x1D70F}(M)}{v^{2}\log ^{2}x} & {>} & \displaystyle \frac{\unicode[STIX]{x1D70F}(M)}{\log ^{4}x}=\frac{2^{\unicode[STIX]{x1D714}(M)}}{\log ^{4}x}\nonumber\\ \displaystyle & = & \displaystyle \frac{2^{(1/3+o(1))(\log x/\text{log}\,\log x)}}{\log ^{4}x}=2^{(1/3+o(1))\log x/\text{log}\,\log x}\nonumber\\ \displaystyle & = & \displaystyle 2^{(1/6+o(1))\log (v^{2}x^{2})/\text{log}\,\log (v^{2}x^{2})}\geqslant 2^{(1/6+o(1))\log k/\text{log}\,\log k}.\nonumber\end{eqnarray}$$
As
$x$
can be arbitrarily large, this argument produces infinitely many integers
$k$
with at least
$\exp (c\log k/\text{log}\,\log k)$
representations as
$(bp+a)(bp+q)$
with
$p,q$
primes, where
$c=1/10$
.◻
Remark.
The best we can do using Theorem 3.1 would be to replace
${\textstyle \frac{1}{3}}$
with any number smaller than
${\textstyle \frac{5}{12}}$
, which gives the result for any number
$c<(5/24)\log 2$
. In particular,
$c=1/7$
works.
Proof of Theorem 1.4.
We may assume that
$0<\unicode[STIX]{x1D716}<1$
. It is well known that the values
$s(n)/n$
are dense in
$(0,\infty )$
. Thus, we may fix an integer
$n_{0}>1$
with
$$\begin{eqnarray}s(n_{0})/n_{0}\in (\unicode[STIX]{x1D6FC}^{-1}(1-{\textstyle \frac{1}{2}}\unicode[STIX]{x1D716}),\unicode[STIX]{x1D6FC}^{-1}(1+{\textstyle \frac{1}{2}}\unicode[STIX]{x1D716})).\end{eqnarray}$$
If
$p$
and
$q$
are distinct primes not dividing
$n_{0}$
, then
$$\begin{eqnarray}\displaystyle s(n_{0}pq) & = & \displaystyle \unicode[STIX]{x1D70E}(n_{0})(p+1)(q+1)-n_{0}pq\nonumber\\ \displaystyle & = & \displaystyle s(n_{0})pq+\unicode[STIX]{x1D70E}(n_{0})(p+q+1),\nonumber\end{eqnarray}$$
so that
$$\begin{eqnarray}s(n_{0})s(n_{0}pq)=(s(n_{0})p+\unicode[STIX]{x1D70E}(n_{0}))(s(n_{0})q+\unicode[STIX]{x1D70E}(n_{0}))+s(n_{0})\unicode[STIX]{x1D70E}(n_{0})-\unicode[STIX]{x1D70E}(n_{0})^{2}.\end{eqnarray}$$
By Theorem 3.2, there are infinitely many integers
$k$
having more than
$\exp (c\log k/\text{log}\,\log k)$
representations in the form
$$\begin{eqnarray}k=(s(n_{0})p+\unicode[STIX]{x1D70E}(n_{0}))(s(n_{0})q+\unicode[STIX]{x1D70E}(n_{0})),\end{eqnarray}$$
with
$p,q$
distinct and
$$\begin{eqnarray}p,q>\max \{n_{0},\unicode[STIX]{x1D70E}(n_{0})/n_{0}\cdot (s(n_{0})/n_{0}\cdot \unicode[STIX]{x1D716}/12)^{-1}\}.\end{eqnarray}$$
(These latter conditions on
$p$
and
$q$
exclude only
$O(1)$
representations of
$k$
.) Letting
$k$
be a large integer of this kind, define
$m$
in terms of
$k$
by
$$\begin{eqnarray}m=\frac{k+s(n_{0})\unicode[STIX]{x1D70E}(n_{0})-\unicode[STIX]{x1D70E}(n_{0})^{2}}{s(n_{0})}.\end{eqnarray}$$
Then
$m<k$
and
$m$
has at least
$\exp (c\log m/\text{log}\,\log m)$
representations in the form
$s(n_{0}pq)$
. Moreover,
$$\begin{eqnarray}m=s(n_{0}pq)\geqslant s(n_{0})pq\geqslant (n_{0}\unicode[STIX]{x1D6FC}^{-1}(1-{\textstyle \frac{1}{2}}\unicode[STIX]{x1D716}))pq=n_{0}pq\cdot \unicode[STIX]{x1D6FC}^{-1}(1-{\textstyle \frac{1}{2}}\unicode[STIX]{x1D716}).\end{eqnarray}$$
Thus,
$$\begin{eqnarray}n_{0}pq\leqslant \unicode[STIX]{x1D6FC}m(1-{\textstyle \frac{1}{2}}\unicode[STIX]{x1D716})^{-1}<(1+\unicode[STIX]{x1D716})\unicode[STIX]{x1D6FC}m.\end{eqnarray}$$
On the other hand, using the bounds on
$p,q$
,
$$\begin{eqnarray}\displaystyle \frac{s(n_{0}pq)}{n_{0}pq} & = & \displaystyle \frac{s(n_{0})}{n_{0}}+\frac{\unicode[STIX]{x1D70E}(n_{0})}{n_{0}}\biggl(\frac{1}{p}+\frac{1}{q}+\frac{1}{pq}\biggr)\nonumber\\ \displaystyle & {<} & \displaystyle \frac{s(n_{0})}{n_{0}}+\frac{s(n_{0})}{n_{0}}\cdot \frac{\unicode[STIX]{x1D716}}{4}<\unicode[STIX]{x1D6FC}^{-1}\biggl(1+\frac{7}{8}\unicode[STIX]{x1D716}\biggr).\nonumber\end{eqnarray}$$
Rearranging,
$$\begin{eqnarray}n_{0}pq>\unicode[STIX]{x1D6FC}\cdot s(n_{0}pq)(1+7\unicode[STIX]{x1D716}/8)^{-1}>(1-\unicode[STIX]{x1D716})\unicode[STIX]{x1D6FC}m.\end{eqnarray}$$
Thus,
$m$
has at least
$\exp (c\log m/\text{log}\,\log m)$
preimages
$n=n_{0}pq$
in
$((1-\unicode[STIX]{x1D716})\unicode[STIX]{x1D6FC}m,(1+\unicode[STIX]{x1D716})\unicode[STIX]{x1D6FC}m)$
.◻
Remark.
In [Reference Pollack, Pomerance, Butler, Cooper and Hurlbert17], the second author writes “it seems difficult to show there are infinitely many even
$n$
with
$\#s^{-1}(n)\geqslant 3$
”. This can now be shown. Following the above construction with
$n_{0}=2$
, one obtains infinitely many even
$m$
with more than
$\exp (c\log m/\text{log}\,\log m)$
$s$
-preimages of the form
$2pq$
.
4 Solutions to
$\unicode[STIX]{x1D70E}(n)=kn+a$
Solving
$s(n)=a$
is of course the same as solving
$\unicode[STIX]{x1D70E}(n)=n+a$
. In [Reference Anavi, Pollack and Pomerance2, Reference Pollack and Pomerance15], and [Reference Pomerance18] the authors study the more general equation
$$\begin{eqnarray}\unicode[STIX]{x1D70E}(n)=kn+a,\end{eqnarray}$$
for given
$k$
and
$a$
. In this context, an integer
$n$
is called a regular solution to (4.1) if
$$\begin{eqnarray}n=pm\quad \text{where}~p\nmid m,~\unicode[STIX]{x1D70E}(m)/m=k,~\text{and}~\unicode[STIX]{x1D70E}(m)=a.\end{eqnarray}$$
All other solutions are called sporadic. If there are any regular solutions at all, then there are
$\gg _{a,k}x/\text{log}\,x$
regular solutions up to
$x$
, for large
$x$
. In [Reference Anavi, Pollack and Pomerance2, Theorem 1], it is shown that the count of sporadic solutions is much smaller: for any integer
$k\geqslant 0$
and any integer
$a$
with
$|a|\leqslant x^{1/4}$
, the count of sporadic solutions up to
$x$
is at most
$x^{1/2+o(1)}$
, as
$x\rightarrow \infty$
, uniformly in
$k$
and
$a$
.
The authors of [Reference Anavi, Pollack and Pomerance2] claim it is plausible that the upper bound
$x^{1/2+o(1)}$
can be replaced with a bounded power of
$\log x$
, even in the wider range
$|a|\leqslant x/2$
. However, this is provably false in the case
$k=0$
, as shown by the method in Erdős [Reference Erdős4]. And it is provably false in the case
$k=1$
as there are infinitely many positive integers
$a$
with
$\gg a/\text{log}^{2}a$
representations as
$p+q+1$
where
$p,q$
are unequal primes (so that
$\unicode[STIX]{x1D70E}(pq)=pq+a$
). The first two authors of the present paper go on to state this as a conjecture in [Reference Pollack and Pomerance16, Conjecture 2.4], taking into account that
$k$
should not be 0 or 1.
Conjecture 4.1. Let
$k\geqslant 2$
. Let
$x\geqslant 3$
and
$a\in \mathbb{Z}$
with
$|a|\leqslant x/2$
. The number of solutions
$n\leqslant x$
to
$\unicode[STIX]{x1D70E}(n)=kn+a$
is
$\ll (\log x)^{C}$
, where both the implied constant and
$C$
are absolute constants.
This statement of Conjecture 4.1 in [Reference Pollack and Pomerance16] inadvertently omits the word “sporadic”, which is still needed. However, it turns out that confining attention to sporadic solutions is still not enough. For example, when
$k=3$
, there are values of
$a$
for which the equation
$\unicode[STIX]{x1D70E}(n)-3n=a$
has at least
$x^{1/2+o(1)}$
solutions with
$n\leqslant x$
of the form
$n=120pq$
. This construction depends on the fact that 120 is 3-perfect, i.e.,
$\unicode[STIX]{x1D70E}(120)=3\cdot 120$
. One might attempt to further salvage Conjecture 4.1 by barring constructions like
$\unicode[STIX]{x1D70E}(n)-3n=a$
with
$n=120pq$
. However, even with this modification, the upper bound on the number of solutions to
$\unicode[STIX]{x1D70E}(n)=kn+a$
given in Conjecture 4.1 is too small.
Proposition 4.2. Let
$k$
be a positive integer, and let
$C>0$
. There are infinitely many positive integers
$a$
for which the equation
$\unicode[STIX]{x1D70E}(n)=kn+a$
has more than
$(\log a)^{C}$
solutions
$n\leqslant a$
not of the form
$mp$
or
$mpq$
for any
$k$
-perfect number
$m$
.
By considering values of
$x=2a$
, we see that Conjecture 4.1 fails for every
$k$
, even after restricting
$n$
to sporadic solutions not of the form
$mpq$
for a
$k$
-perfect number
$m$
.
Proof (sketch).
Fix a positive integer
$n_{0}$
with
$\unicode[STIX]{x1D70E}(n_{0})/n_{0}>2k$
. We consider numbers
$n=n_{0}pq$
, where
$p,q$
are distinct primes not dividing
$n_{0}$
. Then, writing
$T=\unicode[STIX]{x1D70E}(n_{0})-kn_{0}$
, one finds that
$$\begin{eqnarray}T(\unicode[STIX]{x1D70E}(n)-kn)=(Tp+\unicode[STIX]{x1D70E}(n_{0}))(Tq+\unicode[STIX]{x1D70E}(n_{0}))+T\unicode[STIX]{x1D70E}(n_{0})-\unicode[STIX]{x1D70E}(n_{0})^{2}.\end{eqnarray}$$
(This is the analogue of (3.1).) Following the proof of Theorem 1.4, we produce infinitely many positive integers
$a$
that can be written as
$\unicode[STIX]{x1D70E}(n)-kn$
for more than
$\exp (c\log a/\text{log}\,\log a)$
numbers
$n=n_{0}pq$
. All of our
$n=n_{0}pq$
satisfy
$\unicode[STIX]{x1D70E}(n)/n\geqslant \unicode[STIX]{x1D70E}(n_{0})/n_{0}>2k$
, so that
$n<(\unicode[STIX]{x1D70E}(n)-kn)/k=a/k\leqslant a$
. Moreover,
$n$
does not have the form
$mpq$
for a for a
$k$
-perfect number
$m$
. Indeed, for any primes
$p$
and
$q$
, both
$\unicode[STIX]{x1D70E}(mp)/mp$
and
$\unicode[STIX]{x1D70E}(mpq)/mpq$
are bounded above by
$(\unicode[STIX]{x1D70E}(m)/m)(1+1/2)(1+1/3)=2k$
, whereas
$\unicode[STIX]{x1D70E}(n)/n>2k$
. As
$\exp (c\log a/\text{log}\,\log a)>(\log a)^{C}$
for large
$a$
, the proposition follows.◻
Thus, we cannot hope to get the bound of
$(\log x)^{C}$
stated in Conjecture 4.1. Instead, one might make the following conjecture.
Conjecture 4.3. Let
$k$
be a positive integer. Let
$x\geqslant 3$
and
$a\in \mathbb{Z}$
with
$|a|\leqslant x$
. The number of sporadic solutions
$n\leqslant x$
to
$\unicode[STIX]{x1D70E}(n)=kn+a$
is at most
$x^{1/2+o(1)}$
, as
$x\rightarrow \infty$
, uniformly in
$k,a$
.
We have the following variant.
Theorem 4.4. Let
$k$
be a positive integer. Let
$x\geqslant 3$
and
$a\in \mathbb{Z}$
. The number of sporadic solutions
$n\leqslant x$
to
$\unicode[STIX]{x1D70E}(n)=kn+a$
is at most
$x^{3/5+o_{k}(1)}$
, as
$x\rightarrow \infty$
, uniformly in
$a$
.
Note that the conclusion here is slightly weaker than that of [Reference Anavi, Pollack and Pomerance2, Theorem 1]: we have
$x^{3/5+o(1)}$
in place of
$x^{1/2+o(1)}$
, and the result is not claimed to be uniform in
$k$
. The advantage of Theorem 4.4 is that
$a$
is no longer restricted to satisfy
$|a|\leqslant x^{1/4}$
. However, for all solutions
$n\leqslant x$
, we have
$|a|=|\unicode[STIX]{x1D70E}(n)-kn|\ll _{k}x\log \log x$
.
Proof. We can assume
$a\neq 0$
; if
$a=0$
, we are counting multiply perfect numbers, and Hornfeck and Wirsing [Reference Hornfeck and Wirsing9] have shown that the count of such
$n\leqslant x$
is
$O(x^{\unicode[STIX]{x1D716}})$
for any fixed
$\unicode[STIX]{x1D716}>0$
.
If
$n=p$
is a prime solution to
$\unicode[STIX]{x1D70E}(n)=kn+a$
, then
$p(1-k)=a-1$
. If
$k\geqslant 2$
, this equation determines
$p$
, and so there is at most one solution with
$n$
prime. If
$k=1$
, then for there to be any solution we must also have
$a=1$
; but then
$n=p$
is a regular solution to
$\unicode[STIX]{x1D70E}(n)=kn+a$
, not a sporadic solution.
Thus, we may restrict attention to solutions
$n$
with at least two prime factors, counted with multiplicity. We write each such
$n$
in the form
$$\begin{eqnarray}n=n_{0}pq\quad \text{where}~q=P(n),~p=P(n/q).\end{eqnarray}$$
We now show that the cases
$n_{0}\leqslant x^{3/5}$
contribute at most
$x^{3/5+o(1)}$
solutions. To start with, we suppose that
$(pq,n_{0})=1$
and
$p\neq q$
.
Let
$T=\unicode[STIX]{x1D70E}(n_{0})-kn_{0}$
. If
$T=0$
, then
$$\begin{eqnarray}a=\unicode[STIX]{x1D70E}(n)-kn=\unicode[STIX]{x1D70E}(n_{0})(p+1)(q+1)-kn_{0}pq=kn_{0}(p+q+1).\end{eqnarray}$$
Thus,
$n_{0}$
and
$p+q+1$
are divisors of
$a$
. As
$|a|\ll x\log \log x$
, there are only
$x^{o(1)}$
divisors of
$a$
, and so there are only
$x^{o(1)}$
possibilities for
$n_{0}$
, as well as only
$x^{o(1)}$
possibilities for
$q$
, given
$p$
. As
$p\leqslant x^{1/2}$
, the case when
$T=0$
leads to only
$x^{1/2+o(1)}$
possibilities for
$n=n_{0}pq$
.
Now suppose that
$T\neq 0$
. Then (cf. (4.2)),
$$\begin{eqnarray}Ta-T\unicode[STIX]{x1D70E}(n_{0})+\unicode[STIX]{x1D70E}(n_{0})^{2}=(Tp+\unicode[STIX]{x1D70E}(n_{0}))(Tq+\unicode[STIX]{x1D70E}(n_{0})).\end{eqnarray}$$
If the left-hand side is non-vanishing, appealing once again to the maximal order of the divisor function we may conclude that there are only
$x^{o(1)}$
possibilities for
$p,q$
, and so only
$x^{3/5+o(1)}$
possibilities for
$n=n_{0}pq$
. If the left-hand side is
$0$
, then
$\unicode[STIX]{x1D70E}(n_{0})=-Tp$
or
$\unicode[STIX]{x1D70E}(n_{0})=-Tq$
. If
$\unicode[STIX]{x1D70E}(n_{0})=-Tp$
, then
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D70E}(n_{0}p) & = & \displaystyle -Tp(p+1)=kn_{0}p(p+1)-\unicode[STIX]{x1D70E}(n_{0})p(p+1)\nonumber\\ \displaystyle & = & \displaystyle kn_{0}p(p+1)-p\unicode[STIX]{x1D70E}(n_{0}p);\nonumber\end{eqnarray}$$
hence,
$\unicode[STIX]{x1D70E}(n_{0}p)=k\cdot n_{0}p$
. As
$$\begin{eqnarray}kn_{0}pq+a=\unicode[STIX]{x1D70E}(n_{0}pq)=\unicode[STIX]{x1D70E}(n_{0}p)(q+1)=kn_{0}p(q+1)=kn_{0}pq+kn_{0}p,\end{eqnarray}$$
we have
$$\begin{eqnarray}a=kn_{0}p=\unicode[STIX]{x1D70E}(n_{0}p).\end{eqnarray}$$
Therefore
$n=(n_{0}p)q$
is a regular solution to
$\unicode[STIX]{x1D70E}(n)=kn+a$
and so should not be counted here. A similar analysis applies when
$\unicode[STIX]{x1D70E}(n_{0})=-Tq$
.
It still remains to deal with the cases when either
$p$
or
$q$
divides
$n_{0}$
or
$p=q$
. If
$q$
divides
$n_{0}$
, then
$p=q$
. As there are only
$O(\log x)$
primes dividing
$n_{0}$
, there are only
$O(x^{3/5}\log x)$
possibilities for
$n=n_{0}pq$
. So we may suppose that
$q\nmid n_{0}$
. When
$p=q$
(and
$q\nmid n_{0}$
),
$$\begin{eqnarray}\displaystyle a & = & \displaystyle \unicode[STIX]{x1D70E}(n_{0}p^{2})-kn_{0}p^{2}\nonumber\\ \displaystyle & = & \displaystyle (\unicode[STIX]{x1D70E}(n_{0})-kn_{0})p^{2}+\unicode[STIX]{x1D70E}(n_{0})(p+1).\nonumber\end{eqnarray}$$
Given
$n_{0}$
, the final right-hand side is a polynomial in
$p$
of degree
$1$
or
$2$
, and so
$p$
is determined in at most two ways, yielding
$O(x^{3/5})$
possibilities for
$n$
. We are left with the case when
$p,q$
are distinct primes,
$q\nmid n_{0}$
, but
$p\mid n_{0}$
. In this case,
$p$
is determined in at most
$O(\log x)$
ways from
$n_{0}$
. Moreover,
$$\begin{eqnarray}a=\unicode[STIX]{x1D70E}(n_{0}pq)-kn_{0}pq=\unicode[STIX]{x1D70E}(n_{0}p)(q+1)-kn_{0}pq=q(\unicode[STIX]{x1D70E}(n_{0}p)-kn_{0}p)+\unicode[STIX]{x1D70E}(n_{0}p).\end{eqnarray}$$
Thus, as long as
$\unicode[STIX]{x1D70E}(n_{0}p)\neq kn_{0}p$
, we see
$q$
is determined by
$n_{0}$
and
$p$
, and hence
$n=n_{0}pq$
is determined in
$O(x^{3/5}\log x)$
ways. But if
$\unicode[STIX]{x1D70E}(n_{0}p)=kn_{0}p$
, it is easy to see from the last display that
$n=(n_{0}p)q$
is actually a regular solution rather than a sporadic solution.
Thus, we have shown that those cases where
$n_{0}\leqslant x^{3/5}$
contribute at most
$x^{3/5+o(1)}$
solutions. So we may assume that
$n_{0}>x^{3/5}$
and thus that
$$\begin{eqnarray}pq=n/n_{0}\leqslant x/n_{0}<x^{2/5}.\end{eqnarray}$$
Hence,
$p<x^{1/5}$
, and there is a divisor
$d_{0}$
of
$n$
in the interval
$(x^{2/5},x^{3/5}]$
. Indeed, we may choose
$d_{0}$
as a certain product of the largest several prime factors of
$n$
.
The rest of the argument follows the proof of the main theorem in [Reference Anavi, Pollack and Pomerance2].
With
$d_{0}$
chosen as above, we let
$d$
be the unitary divisor of
$n$
satisfying
$\operatorname{rad}(d)=\operatorname{rad}(d_{0})$
. Write
$n=de$
. Our strategy is to count the number of values of
$e$
corresponding to fixed
$d,d_{0}$
, then to sum on
$d,d_{0}$
. As
$$\begin{eqnarray}a=\unicode[STIX]{x1D70E}(d)\unicode[STIX]{x1D70E}(e)-kde,\end{eqnarray}$$
we have
$$\begin{eqnarray}kde\equiv a~(\text{mod}~\unicode[STIX]{x1D70E}(d)),\end{eqnarray}$$
and thus
$e$
is placed in a determined residue class modulo
$\unicode[STIX]{x1D70E}(d)/\text{gcd}(\unicode[STIX]{x1D70E}(d),kd)$
. As
$e\leqslant x/d$
, the number of possibilities for
$e$
, given
$d$
and
$d_{0}$
, is
$$\begin{eqnarray}\ll \frac{x\cdot \operatorname{gcd}(\unicode[STIX]{x1D70E}(d),kd)}{d\unicode[STIX]{x1D70E}(d)}+1\ll _{k}\frac{x\operatorname{gcd}(\unicode[STIX]{x1D70E}(d),d)}{d\unicode[STIX]{x1D70E}(d)}+1\ll \frac{x\operatorname{gcd}(\unicode[STIX]{x1D70E}(d),d)}{d^{2}}+1.\end{eqnarray}$$
Given
$d_{0}$
, the number of
$d\leqslant x$
with
$\operatorname{rad}(d_{0})=\operatorname{rad}(d)$
is
$x^{o(1)}$
(see, e.g., [Reference Pollack10, Lemma 4.2]), and so when summing on
$d,d_{0}$
the “
$+1$
” terms contribute at most
$x^{3/5+o(1)}$
. This is acceptable for us. We deal with the remaining terms as follows. Put
$g=\operatorname{gcd}(d,\unicode[STIX]{x1D70E}(d))$
; from (4.3), we have that
$g\mid a$
. Thus,
$$\begin{eqnarray}\mathop{\sum }_{d,d_{0}}\frac{x\operatorname{gcd}(\unicode[STIX]{x1D70E}(d),d)}{d^{2}}\leqslant x\mathop{\sum }_{g\mid a}\mathop{\sum }_{\substack{ d>x^{2/5} \\ g\mid d}}\frac{g}{d^{2}}\mathop{\sum }_{d_{0}\mid d}1.\end{eqnarray}$$
The inner sum is just
$\unicode[STIX]{x1D70F}(d)\leqslant x^{o(1)}$
. Now writing
$d=gh$
, and summing on
$h>x^{2/5}/g$
, we see that the above expression is
$$\begin{eqnarray}{\leqslant}x^{1+o(1)}\mathop{\sum }_{g\mid a}\frac{1}{g}\mathop{\sum }_{h>x^{2/5}/g}\frac{1}{h^{2}}\ll x^{3/5+o(1)}\mathop{\sum }_{g\mid a}1\leqslant x^{3/5+o(1)}.\end{eqnarray}$$
Collecting all of our estimates completes the proof of the theorem. ◻
We close with the following result, which makes the upper bound in [Reference Pomerance18, Corollary 3] completely uniform.
Proof Sketch of Theorem 1.5.
Let
$a$
be an arbitrary integer. We show there are at most
$O(x/\text{log}\,x)$
values of
$n\leqslant x$
with
$P(n)\mid \unicode[STIX]{x1D70E}(n)-a$
. Via standard estimates, we may assume that:
(a)
$x/\text{log}\,x<n\leqslant x$
;(b)
$P(n)>x^{1/\text{log}\,\log x}$
;(c)
$n$
is not divisible by a proper power larger than
$\log ^{2}x$
.
Let
$p=P(n)$
. By (b) and (c), we may assume that
$p^{2}\nmid n$
. Write
$n=pm$
, so that
$\unicode[STIX]{x1D70E}(n)=\unicode[STIX]{x1D70E}(m)(p+1)$
. We have
$$\begin{eqnarray}\unicode[STIX]{x1D70E}(m)\equiv a~(\text{mod}~p).\end{eqnarray}$$
Assume that
$p>x^{1/2}\log x$
and
$x$
is large. Then
$\unicode[STIX]{x1D70E}(m)<m\log x<p$
. Thus, for a given
$p$
, all of the solutions
$m_{1},m_{2},\ldots ,m_{t}$
to (4.4), have
$\unicode[STIX]{x1D70E}(m_{1})=\unicode[STIX]{x1D70E}(m_{2})=\cdots =\unicode[STIX]{x1D70E}(m_{t})$
. Now for any integer
$c$
, the number of solutions
$m\leqslant y$
to
$\unicode[STIX]{x1D70E}(m)=c$
is
${\leqslant}y^{1-(1+o(1))\log _{3}y/\text{log}_{2}\,y}$
as
$y\rightarrow \infty$
, uniformly in
$c$
. This is the
$\unicode[STIX]{x1D70E}$
-analogue of a result in [Reference Pollack and Pomerance13] (also see [Reference Pollack, Pomerance and Mollin14]) for
$\unicode[STIX]{x1D711}$
. So, there is an absolute constant
$y_{0}$
such that if
$y\geqslant y_{0}$
, then the number of solutions
$m\leqslant y$
to
$\unicode[STIX]{x1D70E}(m)=c$
is
${\leqslant}y^{1-1/\text{log}_{2}\,y}$
. But for
$O(x/\text{log}\,x)$
choices for
$n\leqslant x$
, we may assume that
$p\leqslant x/y_{0}$
. Thus, the number of
$m$
in (4.4) for a given
$p$
is at most
$(x/p)^{1-1/\text{log}\,_{2}(x/p)}$
. We now sum this expression on
$p$
with
$x^{1/2}\log x<p\leqslant x/y_{0}$
. If such a
$p$
is in an interval
$(x/\text{e}^{j+1},x/\text{e}^{j}]$
, then the number of
$m$
corresponding to
$p$
is at most
$\text{e}^{j(1-1/\text{log}\,j)}$
. Further, the number of choices for
$p$
in this interval is
$\ll x/(\text{e}^{j}\log (x/\text{e}^{j}))\ll x/(\text{e}^{j}\log x)$
, using
$p>x^{1/2}\log x$
. Thus, the number of choices for
$n$
is
$$\begin{eqnarray}\ll \frac{x}{\text{e}^{j/\text{log}\,j}\log x}.\end{eqnarray}$$
Summing on
$j$
gets us
$\ll x/\text{log}\,x$
.
We now assume that
$p\leqslant x^{1/2}\log x$
. This implies that
$m>x^{1/2}/\text{log}^{2}\,x$
. Let
$m=uq$
where
$q=P(m)$
. By standard estimates on smooth numbers, the number of integers
$mp\leqslant x$
with
$m>x^{1/2}/\text{log}^{2}\,x$
and
$P(m)\leqslant \log x$
is at most
$x^{1/2+o(1)}$
as
$x\rightarrow \infty$
, so we may assume that
$q>\log x$
, and so, by (c),
$q\nmid u$
. Thus, (4.4) implies that
$$\begin{eqnarray}\unicode[STIX]{x1D70E}(u)q\equiv a-\unicode[STIX]{x1D70E}(u)~(\text{mod}~p).\end{eqnarray}$$
We may assume that
$p\nmid \unicode[STIX]{x1D70E}(n)$
. Indeed, otherwise, there is a prime power
$r^{a}\mid n$
with
$p\mid \unicode[STIX]{x1D70E}(r^{a})$
, and as
$r^{a}>{\textstyle \frac{1}{2}}\unicode[STIX]{x1D70E}(r^{a})\geqslant {\textstyle \frac{1}{2}}p$
, (b) and (c) imply that
$a=1$
, that is,
$r\equiv -1~(\text{mod}~p)$
. As we may assume that
$x$
is large enough that
$p>3$
, we have
$r>p$
, contradicting
$p=P(n)$
. Thus, we may assume that
$p\nmid \unicode[STIX]{x1D70E}(u)$
in (4.5). Hence, given
$u,p$
, (4.5) completely determines
$q$
, using
$q<p$
. But the number of choices for
$u,p$
with
$up<x/\text{log}\,x$
and
$p=P(up)$
is
${<}x/\text{log}\,x$
, and so this estimate completes the proof.◻
Acknowledgements
The first author is supported by the National Science Foundation under Grant No. DMS-1402268. This work was completed while the second and third authors were in residence at the Mathematical Sciences Research Institute, during which time they were supported by the National Science Foundation under Grant No. DMS-1440140. The third author is also supported by an AMS Simons Travel Grant.
