\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \DeclareMathAlphabet{\curly}{U}{rsfs}{m}{n} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Quasi-Amicable Numbers are Rare } \vskip 1cm \large Paul Pollack\\ University of Illinois at Urbana-Champaign\\ Department of Mathematics \\ 1409 West Green Street\\ Urbana, IL 61801\\ USA\\ \href{mailto:pppollac@illinois.edu}{\tt pppollac@illinois.edu}\\ \end{center} \vskip .2 in \begin{abstract} Define a \emph{quasi-amicable pair} as a pair of distinct natural numbers each of which is the sum of the nontrivial divisors of the other, e.g., $\{48, 75\}$. Here \emph{nontrivial} excludes both $1$ and the number itself. Quasi-amicable pairs have been studied (primarily empirically) by Garcia, Beck and Najar, Lal and Forbes, and Hagis and Lord. We prove that the set of $n$ belonging to a quasi-amicable pair has asymptotic density zero. \end{abstract} \newtheorem{thm}{Theorem}[section] \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{prob}[thm]{Problem} \newtheorem*{thmA}{Theorem A} \newtheorem*{thmB}{Theorem B} \newtheorem{conj}[thm]{Conjecture} \theoremstyle{definition} \newtheorem*{rmk}{Remark} \newtheorem*{rmks}{Remarks} \renewcommand{\phi}{\varphi} \def\1{\mathbb{1}} \def\Ss{\curly{S}} \def\B{\curly{B}} \def\N{\mathbb{N}} \def\D{\curly{D}} \def\E{\curly{E}} \def\C{\mathbb{C}} \def\Cc{\curly{C}} \def\F{\mathbb{F}} \def\ord{\mathrm{ord}} \def\Pp{\curly{P}} \def\Qq{\curly{Q}} \def\U{\curly{U}} \def\V{\curly{V}} \def\W{\curly{W}} \def\Z{\mathbb{Z}} \def\e{\mathrm{e}} \def\sm{s^{-}} \def\v{\nu} \def\R{\mathbb{R}} \def\rad{\mathrm{rad}} \section{Introduction} Let $s(n) := \sum_{d \mid n, d < n} d$ be the sum of the proper divisors of $n$. Given a natural number $n$, what can one say about the \emph{aliquot sequence at $n$} defined as $n, s(n), s(s(n)), \dots$? From ancient times, there has been considerable interest in the case when this sequence is purely periodic. (In this case, $n$ is called a \emph{sociable number}; see Kobayashi et al. \cite{KPP09} for some recent results on such numbers.) An $n$ for which the period is $1$ is called \emph{perfect} (see sequence \seqnum{A000396}), and an $n$ for which the period is $2$ is called \emph{amicable} (see sequence \seqnum{A063990}). In the latter case, we call $\{n, s(n)\}$ an \emph{amicable pair}. Let $s^{-}(n) := \sum_{d \mid n, 1 < d < n} d$ be the sum of the nontrivial divisors of the natural number $n$, where \emph{nontrivial} excludes both $1$ and $n$. According to Lal and Forbes \cite{LF71}, it was Chowla who suggested studying \emph{quasi-aliquot sequences} of the form $n, s^{-}(n), s^{-}(s^{-}(n)), \dots$. Call $n$ \emph{quasi-amicable} if the quasi-aliquot sequence starting from $n$ is purely periodic of period $2$ (see sequence \seqnum{A005276}). Thus, a \emph{quasi-amicable} pair is a pair of distinct natural numbers $n$ and $m$ with $\sm(n)= m$ and $\sm(m)=n$ (e.g., $n=48$ and $m=75$). The numerical data, reproduced in Table \ref{tbl:data} from sequence \seqnum{A126160}, suggests that the number of such pairs with a member $\leq N$ tends to infinity with $N$, albeit very slowly. While quasi-amicable pairs have been studied empirically (see \cite{garcia68, LF71, BN77, HL77, BN93}, and cf. \cite{pedersen10, mishima10}, \cite[section B5]{guy04}), it appears that very little theoretical work has been done. In this paper, we prove the following modest theorem, which is a quasi-amicable analogue of Erd\H{o}s's 1955 result \cite{erdos55} concerning amicable pairs: \begin{thm}\label{thm:main} The set of quasi-amicable numbers has asymptotic density zero. In fact, as $\epsilon \downarrow 0$, the upper density of the set of $n$ satisfying \begin{equation}\label{eq:NOTTOOCLOSE} 1-\epsilon < \frac{\sm(\sm(n))}{n} < 1+\epsilon \end{equation} tends to zero. \end{thm} \begin{rmk} With $s$ replacing $\sm$, Theorem \ref{thm:main} follows from work of Erd\H{o}s \cite{erdos55} and Erd\H{o}s et al. \cite[Theorem 5.1]{EGPS90}.\end{rmk} \subsection*{Notation} Throughout, $p$ and $q$ always denote prime numbers. We use $\sigma(n):=\sum_{d \mid n} d$ for the sum of all positive divisors of $n$, and we let $\omega(n):=\sum_{p \mid n}{1}$ stand for the number of distinct prime factors of $n$. We write $P(n)$ for the largest prime divisor of $n$, with the understanding that $P(1)=1$. We say that $n$ is \emph{$y$-smooth} if $P(n) \leq y$. For each $n$, its \emph{$y$-smooth part} is defined as the largest $y$-smooth divisor of $n$. The Landau--Bachmann $o$ and $O$-symbols, as well as Vinogradov's $\ll$ notation, are employed with their usual meanings. \emph{Implied constants are absolute unless otherwise specified}. \section{Proof of Theorem \ref{thm:main}} \begin{table}[bt] \begin{center} \begin{tabular}{l|r} $N$& \# of quasi-amicable pairs with least member $\leq N$ \\\hline\hline $10^5$ & 9 \\\hline $10^6$ & 17 \\\hline $10^7$ & 46 \\\hline $10^8$ & 79 \\\hline $10^9$ & 180 \\\hline $10^{10}$ & 404 \\\hline $10^{11}$ & 882 \\\hline $10^{12}$ & 1946 \\\hline \end{tabular}\label{tbl:data} \end{center} \end{table} In this section we give the proof of Theorem \ref{thm:main}, assuming two preliminary results whose proofs are deferred to \S\ref{sec:proof1} and \S\ref{sec:proof2}. \begin{prop}\label{lem:righthand} For each $\epsilon > 0$, the set of natural numbers $n$ with \begin{equation}\label{eq:righthand} \frac{\sigma(n+1)}{n+1}-\epsilon < \frac{\sigma(s^{-}(n))}{s^{-}(n)} < \frac{\sigma(n+1)}{n+1} + \epsilon. \end{equation} has asymptotic density $1$. \end{prop} \begin{rmk} If $n$ is prime, then $s^{-}(n)=0$, and the expression $\sigma(s^{-}(n))/s^{-}(n)$ is undefined. This does not contradict Proposition \ref{lem:righthand}, since the set of primes has asymptotic density zero. \end{rmk} \begin{prop}\label{lem:faraway} As $\epsilon \downarrow 0$, the upper density of the set of natural numbers $n$ for which \begin{equation}\label{eq:perverse} 1-\epsilon < \left(\frac{\sigma(n)}{n}-1\right)\left(\frac{\sigma(n+1)}{n+1}-1\right) < 1+ \epsilon \end{equation} tends to zero. \end{prop} \begin{proof}[Proof of Theorem \ref{thm:main}] It suffices to prove the upper density assertion of the theorem. Let $\delta > 0$. We will show that if $\epsilon > 0$ is sufficiently small, then the upper density of the set of $n$ for which \eqref{eq:NOTTOOCLOSE} holds is at most $2\delta$. We start by assuming that both $\sigma(n)/n \leq B$ and $\sigma(n+1)/(n+1) \leq B$, where $B >0$ is chosen so that these conditions exclude a set of $n$ of upper density at most $\delta$. To see that such a choice is possible, we can use a first moment argument; indeed, since \[ \sum_{n \leq x} \frac{\sigma(n)}{n} = \sum_{n \leq x} \sum_{d \mid n}\frac{1}{d} \leq x\sum_{d \leq x}\frac{1}{d^2} < 2x, \] we can take $B = 4/\delta$. Moreover, Proposition \ref{lem:righthand} shows that by excluding an additional set of density $0$, we can assume that \[ \left|\frac{\sigma(s^{-}(n))}{s^{-}(n)}-\frac{\sigma(n+1)}{n+1}\right| < \frac{\epsilon}{2B}. \] Now write \begin{align*} \frac{\sm(\sm(n))}{n} &= \frac{\sm(n)}{n} \frac{\sm(\sm(n))}{\sm(n)} \\ &= \left(\frac{\sigma(n)}{n}-1-\frac{1}{n}\right)\left(\frac{\sigma(\sm(n))}{\sm(n)}-1-\frac{1}{\sm(n)}\right). \end{align*} If $n$ is a large natural number satisfying \eqref{eq:NOTTOOCLOSE} and our above conditions, then a short computation shows $\frac{\sm(\sm(n))}{n}$ is within $\epsilon$ of the product $(\frac{\sigma(n)}{n}-1)(\frac{\sigma(n+1)}{n+1}-1)$. (Keep in mind that since $n$ is composite, we have $\sm(n) \geq \sqrt{n}$.) Thus, \[ 1-2\epsilon < \left(\frac{\sigma(n)}{n}-1\right)\left(\frac{\sigma(n+1)}{n+1}-1\right) < 1+ 2\epsilon. \] Finally, Proposition \eqref{lem:faraway} shows that if $\epsilon$ is chosen sufficiently small, then these remaining $n$ make up a set of upper density $< \delta$. \end{proof} \section{The proof of Proposition \ref{lem:righthand}}\label{sec:proof1} \subsection{Preparation} The proof of the proposition is very similar to the proof, due to Erd\H{o}s, Granville, Pomerance, and Spiro, that $s(s(n))/s(n) = s(n)/n + o(1)$, as $n\to\infty$ along a sequence of density $1$ (see Erd\H{o}s et al. \cite[p.\ 195]{EGPS90}). We follow their argument, as well as the author's adaptation \cite{pollack10}, very closely. We begin by recalling some auxiliary estimates. The first of these is due to Pomerance \cite[Theorem 2]{pomerance77}. \begin{lem}\label{lem:pombound} Let $D$ be a natural number, and let $x \geq 2$. The number of $n\leq x$ for which $D \nmid \sigma(n)$ is $\ll x/(\log{x})^{1/\phi(D)}$. \end{lem} For a given $\alpha$, we call the natural number $n$ an \emph{$\alpha$-primitive} number if $\sigma(n)/n \geq 1+\alpha$ while $\sigma(d)/d < 1+\alpha$ for every proper divisor $d$ of $n$. The following estimate is due to Erd\H{o}s \cite[p.\ 6]{erdos58}: \begin{lem}\label{lem:eprim} Fix a positive rational number $\alpha$. There is a constant $c=c(\alpha) > 0$ and an $x_0 = x_0(\alpha)$ so that for $x > x_0$, the number of $\alpha$-primitive $n\leq x$ is at most \[ \frac{x}{\exp(c\sqrt{\log x\log\log{x}})}. \] \end{lem} As a consequence of Lemma \ref{lem:eprim}, we obtain the following convergence result, which we will need to conclude the proof of Proposition \ref{lem:righthand}. \begin{lem}\label{lem:tech} Fix a positive rational number $\alpha$. Then \[ \sum_{a \text{ $\alpha$-primitive}} \frac{2^{\omega(a)}}{a} < \infty.\] \end{lem} \begin{proof} We split the values of $a$ appearing in the sum into two classes, putting those $a$ for which $\omega(a) \leq 20\log\log{a}$ in the first class and all other $a$ in the second. If $a$ belongs to the first class, then $2^{\omega(a)} \leq (\log{a})^{20\log{2}}$, and Lemma \ref{lem:eprim} shows that the sum over these $a$ converges (by partial summation). To handle the $a$ in the second class, we ignore the $\alpha$-primitivity condition altogether and invoke a lemma of Pollack \cite[Lemma 2.4]{pollack10}, according to which $\sum_{a:~\omega(a) > 20\log\log{a}} \frac{2^{\omega(a)}}{a} < \infty$. \end{proof} \subsection{Proof proper} We proceed to prove Proposition \ref{lem:righthand} in two stages; first we prove that the lower-bound holds almost always, and then we do the same for the upper bound. The following lemma is needed for both parts. \begin{lem}\label{lem:smallprimes} Fix a natural number $T$. For each composite value of $n$ with $1 \leq n \leq x$, write \[ n + 1= m_1 m_2 \quad\text{and}\quad s^{-}(n) = M_1 M_2,\] where $P(m_1 M_1) \leq T$ and every prime dividing $m_2 M_2$ exceeds $T$. Then, except for $o(x)$ (as $x\to\infty$) choices of $n$, we have $m_1 = M_1$. \end{lem} \begin{proof} At the cost of excluding $o(x)$ values of $n\leq x$, we may assume that \[ m_1 \leq (\log\log{x})^{1/2} \left(\prod_{p \leq T}p\right)^{-1} =: R.\] Indeed, in the opposite case, $n+1$ has a $T$-smooth divisor exceeding $R$, and the number of such $n \leq x$ is \[ \ll x \sum_{\substack{e \text{ $T$-smooth}\\ e >R}} \frac{1}{e} = o(x), \] as $x\to\infty$. Here we use that the sum of the reciprocals of the $T$-smooth numbers is $\prod_{p \leq T}(1-1/p)^{-1} < \infty$. Hence, $m_1 \prod_{p \leq T} p \leq (\log\log{x})^{1/2}$, and so Lemma \ref{lem:pombound} shows that excluding $o(x)$ values of $n\leq x$, we can assume that $m_1 \prod_{p \leq T} p$ divides $\sigma(n)$. Since \[ s^{-}(n) = \sigma(n) - (n+1), \] it follows that $m_1$ is the $T$-smooth part of $s^{-}(n)$. That is, $m_1 = M_1$.\end{proof} \begin{proof}[Proof of the lower bound half of Proposition \ref{lem:righthand}] Fix $\delta > 0$. We will show that the number of $n \leq x$ for which the left-hand inequality in \eqref{eq:righthand} fails is smaller than $3 \delta x$, once $x$ is large. Fix $B$ large enough that $\sigma(n+1)/(n+1) \leq B$ except for at most $\delta x$ exceptional $n\leq x$. That this is possible follows from the first moment argument used in the proof of Theorem \ref{thm:main} (e.g., we may take $B=4/\delta$ again). Next, fix $T$ large enough so that with $m_2$ defined as in Lemma \ref{lem:smallprimes}, we have \[ \frac{\sigma(m_2)}{m_2} \leq \exp(\epsilon/B) \] except for at most $\delta x$ exceptional $n \leq x$. To see that a suitable choice of $T$ exists, observe that \begin{align*} \sum_{n \leq x}\log\frac{\sigma(m_2)}{m_2} &\leq \sum_{n \leq x}\sum_{\substack{p \mid n+1\\ p > T}} \log\left(1 + \frac{1}{p} +\frac{1}{p^2} + \dots\right) \\ &\leq \sum_{n \leq x}\sum_{\substack{p \mid n+1 \\ p > T}}\frac{1}{p-1} \leq 2x \sum_{p > T}\frac{1}{p(p-1)} < \frac{2x}{T}. \end{align*} Hence, we may take $T =\lceil 2B/(\delta \epsilon)\rceil$. For large $x$, we have that $n$ is composite (so that $M_1$ is defined) and that $m_1 = M_1$, except for at most $\delta x$ values of $n \leq x$. This follows from Lemma \ref{lem:smallprimes} and the fact that the primes have density $0$. If $n$ is not in any of the exceptional classes defined above, then \begin{align*} \frac{\sigma(s^{-}(n))}{s^{-}(n)} &= \frac{\sigma(M_1 M_2)}{M_1 M_2} \geq \frac{\sigma(M_1)}{M_1} = \frac{\sigma(m_1)}{m_1} = \frac{\sigma(n+1)/(n+1)}{\sigma(m_2)/m_2}\\ &\geq \frac{\sigma(n+1)}{n+1}\exp\left(-\frac{\epsilon}{B}\right) > \frac{\sigma(n+1)}{n+1}\left(1-\frac{\epsilon}{B}\right) \geq \frac{\sigma(n+1)}{n+1}-\epsilon, \end{align*} which is the desired lower bound. Note that at most $3\delta x$ values of $n\leq x$ are exceptional, as claimed. \end{proof} \begin{proof}[Proof of the upper bound half of Proposition \ref{lem:righthand}] We may suppose that $0 < \epsilon < 1$. Let $\delta >0$ be given. Fix $\eta \in (0,1)$ so small that the number of $n\leq x$ which are either prime or which fail to satisfy \begin{equation}\label{eq:pvlarge} P(n) > x^{\eta}\quad\text{and}\quad P(n)^2 \nmid n \end{equation} is smaller than $\delta x$, once $x$ is large. The existence of such an $\eta$ follows either from Brun's sieve or well-known work of Dickman on smooth numbers. Next, using the first moment argument from the proof of Theorem \ref{thm:main}, choose a fixed number $B \geq 1$ so that all but at most $\delta x$ of the numbers $n\leq x$ satisfy \begin{equation}\label{eq:sigmabound} \frac{\sigma(n+1)}{n+1} \leq B.\end{equation} We fix rational numbers $\alpha_1$ and $\alpha_2$ satisfying \[ 0 < \alpha_1 \leq \frac{\epsilon}{4B}, \quad 0 < \alpha_2 \leq \frac{\alpha_1 \eta}{12}. \] Finally, we fix a natural number $T$ which is sufficiently large, depending only on the $\alpha_i$, $\delta$, $\eta$, and $B$. The precise meaning of ``sufficiently large'' will be specified in the course of the proof. Suppose that the right-hand inequality \eqref{eq:righthand} fails for $n$, where we assume that $n$ is composite and satisfies both \eqref{eq:pvlarge} and \eqref{eq:sigmabound}. Write \[ n +1 = m_1 m_2 \quad\text{and}\quad s^{-}(n) = M_1 M_2, \] where $P(m_1 M_1) \leq T$ and every prime dividing $m_2 M_2$ exceeds $T$. By Lemma \ref{lem:smallprimes}, we can assume $m_1 = M_1$, excluding at most $\delta x$ values of $n \leq x$. Thus, \[ \frac{\sigma(M_2)/M_2}{\sigma(m_2)/m_2} = \frac{\sigma(s^{-}(n))/s^{-}(n)}{\sigma(n+1)/(n+1)} \geq 1 + \frac{\epsilon}{\sigma(n+1)/(n+1)}\geq1+\frac{\epsilon}{B} \geq 1 + 4\alpha_1.\] In particular, \begin{equation}\label{eq:sigmaN2} \frac{\sigma(M_2)}{M_2} \geq 1+4\alpha_1. \end{equation} We can assume our choice of $T$ was such that, apart from at most $\delta x$ exceptional $n\leq x$, we have \begin{equation}\label{eq:n2small} \frac{\sigma(m_2)}{m_2} \leq 1+\alpha_1. \end{equation} Indeed, the argument for the analogous claim in the proof of the lower-bound shows it is sufficient that $T > 2(\delta \log(1+\alpha_1))^{-1}$. Henceforth, we assume \eqref{eq:n2small}. Now write $M_2 = M_3 M_4$, where every prime dividing $M_3$ divides $n+1$, while $M_4$ is coprime to $n+1$. Note that every prime dividing $M_3$ divides $m_2$. Hence, \begin{align*} \frac{\sigma(M_3)}{M_3} \leq \prod_{p \mid M_3}\left(1+\frac{1}{p-1}\right) &= \left(\prod_{p \mid M_3}\frac{p^2}{p^2-1}\right) \prod_{q \mid M_3}\frac{q+1}{q} \\ &\leq \left(\prod_{p > T}\frac{p^2}{p^2-1}\right) \frac{\sigma(m_2)}{m_2} \leq 1+2\alpha_1, \end{align*} using \eqref{eq:n2small} and assuming an initial appropriate choice of $T$. So from \eqref{eq:sigmaN2}, \[ \frac{\sigma(M_4)}{M_4} = \frac{\sigma(M_2)/M_2}{\sigma(M_3)/M_3} \geq \frac{1+4\alpha_1}{1+2\alpha_1} \geq 1+\alpha_1. \] It follows that there is an $\alpha_1$-primitive number $a_1$ dividing $M_4$, where each prime dividing $a_1$ exceeds $T$. We claim next that there is a squarefree, $\alpha_2$-primitive number $a_2$ dividing $a_1$ with \[ a_2 \leq a_1^{\eta/2}. \] List the distinct prime factors of $a_1$ in increasing order, say $T < q_1 < q_2 < \dots < q_t$, and put $a_0 := q_1 q_2 \cdots q_{\lfloor \eta t/2\rfloor}$, so that \[ a_0 \leq (q_1 \cdots q_t)^{\lfloor \eta t/2\rfloor/t} \leq a_1^{\eta/2}. \] We will show that $\sigma(a_0)/a_0 \geq 1+\alpha_2$; then we can take $a_2$ as any $\alpha_2$-primitive divisor of $a_0$. First, observe that $\lfloor \eta t/2 \rfloor \geq \eta t/3$. Otherwise, $t < 6/\eta$ and \[ 1+\alpha_1 \leq \frac{\sigma(a_1)}{a_1} \leq \prod_{1 \leq i \leq t }\left(1+\frac{1}{q_i-1}\right)\leq \left(1+\frac{1}{T}\right)^{6/\eta} \leq \exp\left(\frac{6}{\eta T}\right), \] which is false, assuming a suitable initial choice of $T$. It follows that \[ \frac{\sigma(a_0)}{a_0} = \prod_{1 \leq i \leq \lfloor \eta t/2\rfloor} \frac{q_{i}+1}{q_i} \geq \left(\prod_{p> T} \frac{p^2-1}{p^2}\right)\prod_{1 \leq i \leq \lfloor \eta t/2\rfloor}\frac{q_i}{q_{i}-1}, \] while \begin{align*} \prod_{1 \leq i \leq \lfloor \eta t/2\rfloor}\frac{q_i}{q_{i}-1}&\geq \left(\prod_{1 \leq i \leq t}\frac{q_i}{q_{i}-1}\right)^{\lfloor \eta t/2\rfloor/t}\\ &\geq \left(\frac{\sigma(a_1)}{a_1}\right)^{\eta/3} \geq (1+\alpha_1)^{\eta/3} \geq 1 + \frac{\alpha_1 \eta}{6}. \end{align*} Thus, \[ \frac{\sigma(a_0)}{a_0} \geq \left(\prod_{p> T} \frac{p^2-1}{p^2}\right) \left(1 + \frac{\alpha_1 \eta}{6}\right) \geq 1+\frac{\alpha_1 \eta}{12} \geq 1+\alpha_2, \] again assuming a suitable choice of $T$ to justify the middle inequality. Observe that $a_2$ satisfies \[ a_2 \leq a_1^{\eta/2} \leq (s^{-}(n))^{\eta/2} < x^{2\eta/3}, \] for large $x$. Write $n=Pr$, where $P=P(n)$. Then $r> 1$ (since $n$ is composite) and also, by \eqref{eq:pvlarge}, \[ r \leq x/P \leq x^{1-\eta}. \] Moreover, $a_2$ divides \begin{align*} s^{-}(Pr) = P(\sigma(r)-r)+\sigma(r)-1, \end{align*} and so \[ P(\sigma(r)-r) \equiv 1-\sigma(r)\pmod{a_2}.\] We view this as a linear congruence condition on $P$ modulo $a_2$. If there are any solutions, then $D:=\gcd(\sigma(r)-r,a_2) \mid 1-\sigma(r)$, and in this case there are exactly $D$ solutions modulo $a_2$. Note that if there are any solutions, then $D \mid r-1$. Also note that $D$ is squarefree, since $a_2$ is squarefree. We now sum over pairs $a_2$ and $r$, for each pair counting the number of possible values of $P \leq x/r$. By the Brun--Titchmarsh inequality and the preceding remarks about $D$, we have that the number of possible values of $n=Pr$ is \begin{multline*}\label{eq:nearfinal} \ll \sum_{\substack{a_2 \text{ $\alpha_2$-primitive}\\ T < a_2 \leq x^{2\eta/3}}}\sum_{1< r \leq x^{1-\eta}}\sum_{\substack{D \mid (a_2, r-1)\\ D \text{ squarefree}}} D\frac{x/r}{\phi(a_2)\log{(x/(a_2 r))}} \\ \ll \frac{x}{\eta \log{x}} \sum_{\substack{a_2 \text{ $\alpha_2$-primitive}\\ T < a_2 \leq x^{\eta/3}}}\frac{1}{\phi(a_2)} \sum_{\substack{D \mid a_2\\D \text{ squarefree}}}D \sum_{\substack{1 < r \leq x^{1-\eta} \\ D \mid r-1}}\frac{1}{r}. \end{multline*} The sum on $r$ is $\ll \frac{1}{D}\log{x}$. Moreover, since $a_2$ is $\alpha_2$-primitive, we have \[ \frac{a_2}{\phi(a_2)} \ll \frac{\sigma(a_2)}{a_2} \leq \frac{3}{2}(1+\alpha_2) \ll 1, \] and so $\phi(a_2) \gg a_2$. Thus, the remaining sum is \[ \ll \frac{x}{\eta} \sum_{\substack{a_2 \text{ $\alpha_2$-primitive}\\ T < a_2 \leq x^{2\eta/3}}} \frac{1}{a_2} \sum_{\substack{D\mid a_2\\ D \text{ squarefree}}} 1 \ll \frac{x}{\eta} \sum_{\substack{a_2 \text{ $\alpha_2$-primitive}\\ a_2 \geq T}} \frac{2^{\omega(a_2)}}{a_2}. \] But if $T$ was chosen sufficiently large, then this last sum is bounded by $\eta \delta x$ (by Lemma \ref{lem:tech}), leading to an upper bound of $\ll \delta x$. Since the number of exceptional $n$ appearing earlier in the argument is also $\ll \delta x$, and $\delta >0$ was arbitrary, the proof is complete. \end{proof} \section{Proof of Proposition \ref{lem:faraway}}\label{sec:proof2} We start by quoting two lemmas. The first was developed by Erd\H{o}s \cite{erdos46} to estimate the decay of the distribution function of $\sigma(n)/n$ near infinity. We state the lemma in a slightly stronger form which is supported by his proof. \begin{lem}\label{lem:erd1} For $x > 0$, the number of positive integers $n \leq x$ with $\sigma(n)/n > y$ is \[ \leq x/\exp(\exp((e^{-\gamma}+o(1))y)), \quad\text{as $y\to\infty$},\] uniformly in $x$, where $\gamma$ is the Euler--Mascheroni constant. \end{lem} The next lemma, also due to Erd\H{o}s \cite{erdos74}, supplies an estimate for how often $\sigma(n)/n$ lands in a short interval; note the uniformity in the parameter $a$. \begin{lem}\label{lem:erd2} Let $x > t \geq 2$ and let $a \in \R$. The number of $n \leq x$ with $a < \sigma(n)/n < a +1/t$ is $\ll x/\log{t}$. \end{lem} The next two lemmas develop the philosophy that the rough size of $\sigma(n)/n$ is usually determined by the small prime factors of $n$. Put $h(n) := \sum_{d \mid n}\frac{1}{d}$, so that $h(n)=\sigma(n)/n$. For each natural number $T$, set $h_T(n):= \sum_{d \mid n, P(d) \leq T} \frac{1}{d}$. The next lemma says that $h$ and $h_T$ are usually close once $T$ is large. \begin{lem}\label{lem:small2} Let $\epsilon > 0$ and $x \geq 1$. The number of $n \leq x$ with $h(n) - h_{T}(n) > \epsilon$ is $\ll x/(T\epsilon)$. \end{lem} \begin{proof} Again, we use a first moment argument. We have \[ \sum_{n \leq x} (h(n) - h_{T}(n)) \leq \sum_{n\leq x}\sum_{\substack{d \mid n\\ d >T}} \frac{1}{d} \leq x\sum_{d > T}\frac{1}{d^2} \ll x/T, \] from which the result is immediate. \end{proof} \begin{lem}\label{lem:smoothdiv} Let $T$ be a natural number. Let $S$ be any set of real numbers, and define $\E(S)$ as the set of $T$-smooth numbers $e$ for which $h_T(e) - 1\in S$. Then for $n \in \N$, we have $h_T(n) - 1\in S$ precisely when $n$ has $T$-smooth part $e$ for some $e \in \E(S)$. Moreover, the density of such $n$ exists and is given by \begin{equation}\label{eq:esum} \sum_{e \in \E(S)} \frac{1}{e} \prod_{p \leq T}\left(1-1/p\right) . \end{equation} \end{lem} \begin{proof} It is clear that $h_T(n)$ depends only on the $T$-smooth part of $n$. So it suffices to prove that the density of $n$ with $T$-smooth part in $\E(S)$ is given by \eqref{eq:esum}. For each set of $T$-smooth numbers $\E$, let $\overline{d}_\E$ and $\underline{d}_\E$ denote the upper and lower densities of the set of $n$ whose $T$-smooth part belongs to $\E$. If $\overline{d}_\E = \underline{d}_\E$, then the density of this set exists; denote it by $d_{\E}$. For each $T$-smooth number $e$, a natural number $n$ has $T$-smooth part $e$ precisely when $e$ divides $n$ and $n/e$ is coprime to $\prod_{p \leq T}p$, so that the set of such $n$ has density $\frac{1}{e}\prod_{p \leq T}(1-1/p)$. Since density is finitely additive, it follows that for any finite subset $\E \subset \E(S)$, \[ d_\E = \sum_{e \in \E} \frac{1}{e} \prod_{p \leq T}\left(1-1/p\right). \] Now let $x > 0$, and put $\E(S) = \E_1 \cup \E_2$, where $\E_1 = \E(S) \cap [1,x]$ and $\E_2 = \E(S)\setminus \E_1$. Then $\underline{d}_{\E(S)} \geq \underline{d}_{\E_1}$ for all $x$, and so letting $x\to\infty$, we find that $\underline{d}_{\E(S)}$ is bounded below by \eqref{eq:esum}. On the other hand, $\overline{d}_{\E(S)} \leq \overline{d}_{\E_1} + \overline{d}_{\E_2}$. But $\overline{d}_{\E_1}$ is bounded above by \eqref{eq:esum} for all $x$, while $\overline{d}_{\E_2} \leq \sum_{\substack{e \text{ $T$-smooth}\\ e> x}} e^{-1} = o(1)$, as $x\to\infty$. Thus, letting $x\to\infty$, we obtain that $\overline{d}_{\E(S)}$ is bounded above by \eqref{eq:esum}. \end{proof} \begin{proof}[Proof of Proposition \ref{lem:faraway}] Let $\delta >0$ be sufficiently small. We will show that for \begin{equation}\label{eq:issmall} \epsilon < \exp(-4/\delta), \end{equation} the number of $n\leq x$ satisfying \eqref{eq:perverse} is $\ll \delta (\log\log\frac{1}{\delta}) x$, for large $x$. Note that since $\delta \log\log\frac{1}{\delta} \to 0$ as $\delta \downarrow 0$, this proves the proposition. In what follows, we fix $\delta$ and $\epsilon$, always assuming that $\delta$ is small and that $\epsilon > 0$ satisfies \eqref{eq:issmall}. Put $T:= \epsilon^{-1} \delta^{-1}$. We can assume that both $n$ and $n+1$ have $T$-smooth part $\leq \log{x}$. Indeed, for large $x$, this excludes a set of $n$ size $< \delta x$, since \[ \sum_{\substack{e \text{ $T$-smooth} \\ e>\log{x}}}\frac{1}{e} = o(1), \] as $x\to\infty$. Let $I$ be the closed interval defined by $I:=\left[\exp(-1/\delta), 2\log\log{\frac{1}{\delta}}\right]$. For large $x$, Lemmas \ref{lem:erd1} and \ref{lem:erd2} imply that all but $\ll \delta x$ values of $n\leq x$ are such that $h(n)-1 \in I$ and $h(n+1)-1 \in I$. By Lemma \ref{lem:small2}, excluding $\ll \delta x$ additional values of $n \leq x$, we can assume that $h_T(n) \geq h(n)-\epsilon$ and $h_T(n+1)\geq h(n+1)-\epsilon$. Recalling the upper bound \eqref{eq:issmall} on $\epsilon$, we see that both $h_T(n)-1$ and $h_T(n+1)-1$ belong to the interval $J$, where \[ J:= \left[\frac{1}{2}\exp(-1/\delta), 2 \log\log \frac{1}{\delta}\right]. \] Moreover (always assuming $\delta$ sufficiently small), \begin{equation}\label{eq:perverse2} (h_T(n)-1)(h_T(n+1)-1) \geq ((h(n)-1)-\epsilon)((h(n+1)-1)-\epsilon)\geq 1-5 \epsilon \log\log\frac{1}{\delta}, \end{equation} and \begin{equation}\label{eq:perverse3} (h_T(n)-1)(h_T(n+1)-1) \leq (h(n)-1)(h(n+1)-1) \leq 1+\epsilon. \end{equation} Write $J$ as the disjoint union of $N:=\lceil 1/\epsilon\rceil$ consecutive intervals $J_0$, $J_1$, \dots, $J_{N-1}$, each of length $1/N$. We estimate, for each $0 \leq i < N$, the number of $n$ for which $h_T(n)-1$ belongs to $J_i$. Fix $0 \leq i < N$. Since $h_T(n)-1$ belongs to $J_i$, \eqref{eq:perverse2} and \eqref{eq:perverse3} show that \begin{equation}\label{eq:jipexpression} h_T(n+1) - 1\in \left[\frac{1-5\epsilon \log\log\frac{1}{\delta}}{x_{i+1}},\frac{1+\epsilon}{x_i}\right]=: J_i', \end{equation} where $x_i$ and $x_{i+1}$ are the left and right endpoints of $J_i$, respectively. So in the notation of Lemma \ref{lem:smoothdiv}, $n$ has $T$-smooth part $e\in \E(J_i)$ and $n+1$ has $T$-smooth part $e' \in \E(J_i')$. Clearly, $\gcd(e,e')=1$. That $n$ and $n+1$ have $T$-smooth parts $e$ and $e'$, respectively, amounts to a congruence condition on $n$ modulo $M:=ee'\prod_{p\leq T}p$, where the number of allowable residue classes is $\prod_{p \mid ee'}(p-1) \prod_{\substack{p\nmid ee', p \leq T}}(p-2)$. For large $x$, \[ M \leq (\log{x})^2 \prod_{p \leq T}{p} < (\log{x})^3 \leq x. \] (Recall that $e, e' \leq \log{x}$.) Thus, the Chinese remainder theorem shows that the number of such $n \leq x$ is \begin{multline*} \ll \frac{x}{ee'}\prod_{p \mid ee'}(1-1/p) \prod_{\substack{p \nmid ee'\\ p \leq T}}(1-2/p) \\\leq x\left(\frac{1}{e} \prod_{p \leq T}(1-1/p)\right)\left(\frac{1}{e'} \prod_{p \leq T}(1-1/p)\right) \prod_{p \mid ee'}(1-1/p)^{-1}. \end{multline*} But \[ \prod_{p \mid ee'}(1-1/p)^{-1} = \frac{e}{\phi(e)}\frac{e'}{\phi(e')} \ll \frac{\sigma(e)}{e} \frac{\sigma(e')}{e'} \ll \left(\log\log{\frac{1}{\delta}}\right)^2,\] since $h(e)-1, h(e')-1 \leq 2 \log\log\frac{1}{\delta}$. Summing over $e \in \E(J_i)$ and $e' \in \E(J_i')$, we find that the number of $n$ under consideration is \[ \ll x\left(\log\log{\frac{1}{\delta}}\right)^2 \left(\sum_{e \in \E(J_i)}\frac{1}{e} \prod_{p \leq T}(1-1/p)\right) \left(\sum_{e' \in \E(J_i')}\frac{1}{e'} \prod_{p \leq T}(1-1/p)\right). \] Now sum over $0 \leq i < N$. We obtain that the number of remaining $n$ satisfying \eqref{eq:perverse} is $\ll Lx (\log\log{\frac{1}{\delta}})^2$, where \begin{align*} L:&= \sup_{0 \leq i < N}\left\{\sum_{e' \in \E(J_i')}\frac{1}{e'} \prod_{p \leq T}(1-1/p)\right\} \left(\sum_{0 \leq i < N}\left\{\sum_{e \in \E(J_i)}\frac{1}{e} \prod_{p \leq T}(1-1/p)\right\}\right) \\ &\leq \sup_{0 \leq i < N}\left\{\sum_{e' \in \E(J_i')}\frac{1}{e'} \prod_{p \leq T}(1-1/p)\right\}; \end{align*} we use here that the $J_i$ are disjoint, so that \[ \sum_{0 \leq i < N} \sum_{e \in \E(J_i)}\frac{1}{e} \leq \sum_{e \text{ $T$-smooth}}\frac{1}{e} = \prod_{p \leq T}(1-1/p)^{-1}. \] The proof will be completed by showing that $L \ll \delta$. It is enough to argue that each sum \[ \sum_{e' \in \E(J_i')}\frac{1}{e'} \prod_{p \leq T}(1-1/p) \] is $\ll \delta$, uniformly for $0 \leq i < N$. By Lemma \ref{lem:smoothdiv}, this sum describes the density of those natural numbers $m$ for which $h_T(m)-1 \in J_i'$. We split these $m$ into two classes, according to whether $h(m)-h_T(m) > \epsilon$ or not. The set of $m$ in the former class has upper density $\ll \delta$, by Lemma \ref{lem:small2}. Suppose now that $h(m)$ belongs to the second class. From the expression \eqref{eq:jipexpression} defining $J_i'$ and a short computation, we see that $h_T(m)$ is trapped within a specific interval of length \[ \ll \exp(2/\delta)\left(\log\log \frac{1}{\delta}\right)^2 \epsilon \ll \exp(3/\delta) \epsilon. \] Since $m$ belongs to the second class, $h(m)$ is also trapped within a specific interval of length $\ll \exp(3/\delta) \epsilon$. By \eqref{eq:issmall}, $\exp(3/\delta)\epsilon \leq \exp(-1/\delta)$, and so by Lemma \ref{lem:erd2}, the upper density of the set of those $m$ in the second class is \[ \ll \frac{1}{\delta^{-1} + O(1)} \ll \delta,\] assuming again that $\delta$ is sufficiently small.\end{proof} \begin{rmk} Our argument also shows that the set of \emph{augmented amicable numbers} has density zero (see sequences \seqnum{A007992}, \seqnum{A015630}). Here an augmented amicable number is an integer which generates a $2$-cycle under iteration of the function $s^{+}(n) := 1 +\sum_{\substack{d \mid n,~d