\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 <n}} d$, e.g., $n=6160$.
\end{rmk}

\section{Acknowledgements}
The author thanks the National Science Foundation for their generous support (under award DMS-0802970).

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{BN77}
W.~E. Beck and R.~M. Najar, More reduced amicable pairs, \emph{Fibonacci
  Quart.} \textbf{15} (1977), 331--332.

\bibitem{BN93}
W. E. Beck and R. M. Najar,
Reduced and augmented amicable pairs to {$10^8$}, \emph{Fibonacci
  Quart.} \textbf{31} (1993), 295--298.

\bibitem{erdos46}
P.~Erd\H{o}s, Some remarks about additive and multiplicative functions,
  \emph{Bull. Amer. Math. Soc.} \textbf{52} (1946), 527--537.

\bibitem{erdos55}
P.~Erd\H{o}s, On amicable numbers, \emph{Publ. Math. Debrecen}
\textbf{4} (1955), 108--111.

\bibitem{erdos58}
P.~Erd\H{o}s, Remarks on number theory. {I}. {O}n primitive {$\alpha
  $}-abundant numbers, \emph{Acta Arith.} \textbf{5} (1958), 25--33.

\bibitem{erdos74}
P.~Erd\H{o}s, On the distribution of numbers of the form {$\sigma(n)/n$} and
  on some related questions, \emph{Pacific J. Math.} \textbf{52} (1974), 59--65.

\bibitem{EGPS90}
P.~Erd\H{o}s, A.~Granville, C.~Pomerance, and C.~Spiro, On the normal
  behavior of the iterates of some arithmetic functions, \emph{Analytic Number Theory ({A}llerton {P}ark, {IL}, 1989)}, Progr. Math., Vol.~85, Birkh\"auser,
  Boston, 1990, pp.~165--204.

\bibitem{garcia68}
M.~Garcia, N\'{u}meros casi amigos y casi sociables, \emph{Revista Annal}
  (1968).

\bibitem{guy04}
R.~K. Guy, \emph{Unsolved Problems in Number Theory}, 3rd ed.,
Problem Books in Mathematics, Springer-Verlag, 2004.

\bibitem{HL77}
P.~Hagis, Jr. and G.~Lord, Quasi-amicable numbers, \emph{Math. Comp.}
  \textbf{31} (1977), 608--611.

\bibitem{KPP09}
M.~Kobayashi, P.~Pollack, and C.~Pomerance, On the distribution of
  sociable numbers, \emph{J. Number Theory} \textbf{129} (2009), 1990--2009.

\bibitem{LF71}
M.~Lal and A.~Forbes, A note on {C}howla's function, \emph{Math. Comp.}
  \textbf{25} (1971), 923--925.

\bibitem{mishima10}
H.~Mishima, Table of quasi-amicable pairs under $10^{10}$, online at
\href{http://www.asahi-net.or.jp/~kc2h-msm/mathland/math09/math09t2.htm}{\tt http://www.asahi-net.or.jp/$\sim$kc2h-msm/mathland/math09/math09t2.htm}.

\bibitem{pedersen10}
J. M. Pedersen, Tables of aliquot cycles,
online at \\
  \href{http://amicable.homepage.dk/tables.htm}{\tt http://amicable.homepage.dk/tables.htm}.

\bibitem{pollack10}
P.~Pollack, Powerful amicable numbers, \emph{Colloq. Math.} \textbf{122} (2011), 103--123.

\bibitem{pomerance77}
C.~Pomerance, On the distribution of amicable numbers, \emph{J. Reine Angew.
  Math.} \textbf{293/294} (1977), 217--222.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11A25; Secondary 11N37.


\noindent \emph{Keywords: } 
aliquot sequence, quasi-aliquot sequence, quasi-amicable pair,
augmented amicable pair.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000396},
\seqnum{A005276},
\seqnum{A007992},
\seqnum{A015630},
\seqnum{A063990}, and
\seqnum{A126160}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 26 2010;
revised version received  April 16 2011.
Published in {\it Journal of Integer Sequences}, April 21 2011.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

