Quasi-Amicable Numbers are Rare

Paul Pollack University of Illinois at Urbana-Champaign Department of Mathematics 1409 West Green Street Urbana, IL 61801 USA

                     pppollac@illinois.edu

Abstract

Define a 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 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.

1 Introduction

Let s(n) := ∑_{d|n,d<n} d be the sum of the proper divisors of n. Given a natural number n, what can one say about the aliquot sequence at n defined as n, s(n), s(s(n)), …? From ancient times, there has been considerable interest in the case when this sequence is purely periodic. (In this case, n is called a sociable number; see Kobayashi et al. [11] for some recent results on such numbers.) An n for which the period is 1 is called perfect (see sequence \underline{A000396}), and an n for which the period is 2 is called amicable (see sequence \underline{A063990}). In the latter case, we call {n, s(n)} an amicable pair.

Let s^{−}(n) := ∑_{d|n,1<d<n} d be the sum of the nontrivial divisors of the natural number n, where nontrivial excludes both 1 and n. According to Lal and Forbes [12], it was Chowla who suggested studying quasi-aliquot sequences of the form n, s^{−}(n), s^{−}(s^{−}(n)), . . .. Call n quasi-amicable if the quasi-aliquot sequence starting from n is purely periodic of period 2 (see sequence \underline{A005276}). Thus, a quasi-amicable pair is a pair of distinct natural numbers n and m with s^{−}(n) = m and s^{−}(m) = n (e.g., n = 48 and m = 75). The numerical data, reproduced in Table 2 from sequence \underline{A126160}, suggests that the number of such pairs with a member ≤ N tends to infinity with N, albeit very slowly.

N # of quasi-amicable pairs with least member ≤ N
10^{5}  9
10^{6}  17
10^{7}  46
10^{8}  79
10^{9}  180
10^{10}  404
10^{11}  882
10^{12}  1946

While quasi-amicable pairs have been studied empirically (see [8, 12, 1, 10, 2], and cf. [14, 13], [9, section B5]), 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ős’s 1955 result [4] concerning amicable pairs: Theorem 1.1. The set of quasi-amicable numbers has asymptotic density zero. In fact, as ϵ ↓ 0, the upper density of the set of n satisfying

1 − ϵ < \frac{s^{−}(s^{−}(n))}{n} < 1 + ϵ  (1)

tends to zero.

Remark. With s replacing s^{−}, Theorem 1.1 follows from work of Erdős [4] and Erdős et al. [7, Theorem 5.1].

Notation

Throughout, p and q always denote prime numbers. We use σ(n) := ∑_{d|n} d for the sum of all positive divisors of n, and we let ω(n) := ∑_{p|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 y-smooth if P (n) ≤ y. For each n, its 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 ≪ notation, are employed with their usual meanings. Implied constants are absolute unless otherwise specified.

2 Proof of Theorem 1.1

In this section we give the proof of Theorem 1.1, assuming two preliminary results whose proofs are deferred to §3 and §4. Proposition 2.1. For each ϵ > 0, the set of natural numbers n with

\frac{σ(n + 1)}{n + 1} − ϵ < \frac{σ(s^{−}(n))}{s^{−}(n)} < \frac{σ(n + 1)}{n + 1} + ϵ.  (2)

has asymptotic density 1.

Remark. If n is prime, then s^{−}(n) = 0, and the expression σ(s^{−}(n))/s^{−}(n) is undefined. This does not contradict Proposition 2.1, since the set of primes has asymptotic density zero.

Proposition 2.2. As ϵ ↓ 0, the upper density of the set of natural numbers n for which

1 − ϵ < (\frac{σ(n)}{n} − 1) (\frac{σ(n + 1)}{n + 1} − 1) < 1 + ϵ  (3)

tends to zero.

Proof of Theorem 1.1. It suffices to prove the upper density assertion of the theorem. Let δ > 0. We will show that if ϵ > 0 is sufficiently small, then the upper density of the set of n for which (1) holds is at most 2δ. We start by assuming that both σ(n)/n ≤ B and σ(n + 1)/(n + 1) ≤ B, where B > 0 is chosen so that these conditions exclude a set of n of upper density at most δ. To see that such a choice is possible, we can use a first moment argument; indeed, since

∑_{n≤x} \frac{σ(n)}{n} = ∑_{n≤x} ∑_{d|n} \frac{1}{d} ≤ x ∑_{d≤x} \frac{1}{d^{2}} < 2x,

we can take B = 4/δ. Moreover, Proposition 2.1 shows that by excluding an additional set of density 0, we can assume that

|\frac{σ(s^{−}(n))}{s^{−}(n)} − \frac{σ(n + 1)}{n + 1}| < \frac{ϵ}{2B} .

Now write

\frac{s^{−}(s^{−}(n))}{n} = \frac{s^{−}(n)}{n} \frac{s^{−}(s^{−}(n))}{s^{−}(n)}

= (\frac{σ(n)}{n} − 1 − \frac{1}{n}) (\frac{σ(s^{−}(n))}{s^{−}(n)} − 1 − \frac{1}{s^{−}(n)}) .

If n is a large natural number satisfying (1) and our above conditions, then a short computation shows \frac{s^{−}(s^{−}(n))}{n} is within ϵ of the product (\frac{σ(n)}{n} − 1)(\frac{σ(n+1)}{n+1} − 1). (Keep in mind that since n is composite, we have s^{−}(n) ≥ \sqrt{n}.) Thus,

1 − 2ϵ < (\frac{σ(n)}{n} − 1) (\frac{σ(n + 1)}{n + 1} − 1) < 1 + 2ϵ.

Finally, Proposition (2.2) shows that if ϵ is chosen sufficiently small, then these remaining n make up a set of upper density < δ.

3 The proof of Proposition 2.1

3.1 Preparation

The proof of the proposition is very similar to the proof, due to Erdős, Granville, Pomerance, and Spiro, that s(s(n))/s(n) = s(n)/n + o(1), as n → ∞ along a sequence of density 1 (see Erdős et al. [7, p. 195]). We follow their argument, as well as the author’s adaptation [15], very closely.

We begin by recalling some auxiliary estimates. The first of these is due to Pomerance [16, Theorem 2]. Lemma 3.1. Let D be a natural number, and let x ≥ 2. The number of n ≤ x for which D ∤ σ(n) is ≪ x/(log x)^{1/φ(D)}.

For a given α, we call the natural number n an α-primitive number if σ(n)/n ≥ 1 + α while σ(d)/d < 1 + α for every proper divisor d of n. The following estimate is due to Erdős [5, p. 6]: Lemma 3.2. Fix a positive rational number α. There is a constant c = c(α) > 0 and an x_{0} = x_{0}(α) so that for x > x_{0}, the number of α-primitive n ≤ x is at most

\frac{x}{exp(c\sqrt{log x log log x})}.

As a consequence of Lemma 3.2, we obtain the following convergence result, which we will need to conclude the proof of Proposition 2.1. Lemma 3.3. Fix a positive rational number α. Then

∑_{a α-primitive} \frac{2^{ω(a)}}{a} < ∞.

Proof. We split the values of a appearing in the sum into two classes, putting those a for which ω(a) ≤ 20 log log a in the first class and all other a in the second. If a belongs to the first class, then 2^{ω(a)} ≤ (log a)^{20 log 2}, and Lemma 3.2 shows that the sum over these a converges (by partial summation). To handle the a in the second class, we ignore the αprimitivity condition altogether and invoke a lemma of Pollack [15, Lemma 2.4], according to which ∑_{a: ω(a)>20 log log a} \frac{2^{ω(a)}}{a} < ∞.

3.2 Proof proper

We proceed to prove Proposition 2.1 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. Lemma 3.4. Fix a natural number T. For each composite value of n with 1 ≤ n ≤ x, write

n + 1 = m_{1}m_{2} and s^{−}(n) = M_{1}M_{2},

where P (m_{1}M_{1}) ≤ T and every prime dividing m_{2}M_{2} exceeds T. Then, except for o(x) (as x → ∞) choices of n, we have m_{1} = M_{1}.

Proof. At the cost of excluding o(x) values of n ≤ x, we may assume that

m_{1} ≤ (log log x)^{1/2} (∏_{p≤T} p)^{−1} =: R.

Indeed, in the opposite case, n + 1 has a T -smooth divisor exceeding R, and the number of such n ≤ x is

≪ x ∑_{\begin{matrix}e T -smooth \\ e>R \end{matrix}} \frac{1}{e} = o(x),

as x → ∞. Here we use that the sum of the reciprocals of the T -smooth numbers is ∏_{p≤T} (1 − 1/p)^{−1} < ∞. Hence, m_{1} ∏_{p≤T} p ≤ (log log x)^{1/2}, and so Lemma 3.1 shows that excluding o(x) values of n ≤ x, we can assume that m_{1} ∏_{p≤T} p divides σ(n). Since

s^{−}(n) = σ(n) − (n + 1),

it follows that m_{1} is the T -smooth part of s^{−}(n). That is, m_{1} = M_{1}.

Proof of the lower bound half of Proposition 2.1. Fix δ > 0. We will show that the number of n ≤ x for which the left-hand inequality in (2) fails is smaller than 3δx, once x is large.

Fix B large enough that σ(n + 1)/(n + 1) ≤ B except for at most δx exceptional n ≤ x. That this is possible follows from the first moment argument used in the proof of Theorem 1.1 (e.g., we may take B = 4/δ again). Next, fix T large enough so that with m_{2} defined as in Lemma 3.4, we have

\frac{σ(m_{2})}{m_{2}} ≤ exp(ϵ/B)

except for at most δx exceptional n ≤ x. To see that a suitable choice of T exists, observe that

∑_{n≤x} log \frac{σ(m_{2})}{m_{2}} ≤ ∑_{n≤x} ∑_{\begin{matrix}p|n+1 \\ p>T \end{matrix}} log (1 + \frac{1}{p} + \frac{1}{p^{2}} + …)

≤ ∑_{n≤x} ∑_{\begin{matrix}p|n+1 \\ p>T \end{matrix}} \frac{1}{p − 1} ≤ 2x ∑_{p>T} \frac{1}{p(p − 1)} < \frac{2x}{T}.

Hence, we may take T = ⌈2B/(δϵ)⌉.

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 δx values of n ≤ x. This follows from Lemma 3.4 and the fact that the primes have density 0.

If n is not in any of the exceptional classes defined above, then

\frac{σ(s^{−}(n))}{s^{−}(n)} = \frac{σ(M_{1}M_{2})}{M_{1}M_{2}} ≥ \frac{σ(M_{1})}{M_{1}} = \frac{σ(m_{1})}{m_{1}} = \frac{σ(n + 1)/(n + 1)}{σ(m_{2})/m_{2}}

≥ \frac{σ(n + 1)}{n + 1} exp (−\frac{ϵ}{B} ) > \frac{σ(n + 1)}{n + 1} (1 − \frac{ϵ}{B} ) ≥ \frac{σ(n + 1)}{n + 1} − ϵ,

which is the desired lower bound. Note that at most 3δx values of n ≤ x are exceptional, as claimed.

Proof of the upper bound half of Proposition 2.1. We may suppose that 0 < ϵ < 1. Let δ > 0 be given. Fix η ∈ (0, 1) so small that the number of n ≤ x which are either prime or which fail to satisfy

P (n) > x^{η} and P (n)^{2} ∤ n  (4)

is smaller than δx, once x is large. The existence of such an η 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 1.1, choose a fixed number B ≥ 1 so that all but at most δx of the numbers n ≤ x satisfy

\frac{σ(n + 1)}{n + 1} ≤ B.  (5)

We fix rational numbers α_{1} and α_{2} satisfying

0 < α_{1} ≤ \frac{ϵ}{4B} , 0 < α_{2} ≤ \frac{α_{1}η}{12} .

Finally, we fix a natural number T which is sufficiently large, depending only on the α_{i}, δ, η, and B. The precise meaning of “sufficiently large” will be specified in the course of the proof.

Suppose that the right-hand inequality (2) fails for n, where we assume that n is composite and satisfies both (4) and (5). Write

n + 1 = m_{1}m_{2} and s^{−}(n) = M_{1}M_{2},

where P (m_{1}M_{1}) ≤ T and every prime dividing m_{2}M_{2} exceeds T. By Lemma 3.4, we can assume m_{1} = M_{1}, excluding at most δx values of n ≤ x. Thus,

\frac{σ(M_{2})/M_{2}}{σ(m_{2})/m_{2}} = \frac{σ(s^{−}(n))/s^{−}(n)}{σ(n + 1)/(n + 1)} ≥ 1 + \frac{ϵ}{σ(n + 1)/(n + 1)} ≥ 1 + \frac{ϵ}{B} ≥ 1 + 4α_{1}.

In particular,

\frac{σ(M_{2})}{M_{2}} ≥ 1 + 4α_{1}.  (6)

We can assume our choice of T was such that, apart from at most δx exceptional n ≤ x, we have

\frac{σ(m_{2})}{m_{2}} ≤ 1 + α_{1}.  (7)

Indeed, the argument for the analogous claim in the proof of the lower-bound shows it is sufficient that T > 2(δ log(1 + α_{1}))^{−1}. Henceforth, we assume (7). 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,

\frac{σ(M_{3})}{M_{3}} ≤ ∏_{p|M_{3}} (1 + \frac{1}{p − 1}) = ( ∏_{p|M_{3}} \frac{p^{2}}{p^{2} − 1}) ∏_{q|M_{3}} \frac{q + 1}{q}

≤ (∏_{p>T} \frac{p^{2}}{p^{2} − 1}) \frac{σ(m_{2})}{m_{2}} ≤ 1 + 2α_{1},

using (7) and assuming an initial appropriate choice of T. So from (6),

\frac{σ(M_{4})}{M_{4}} = \frac{σ(M_{2})/M_{2}}{σ(M_{3})/M_{3}} ≥ \frac{1 + 4α_{1}}{1 + 2α_{1}} ≥ 1 + α_{1}.

It follows that there is an α_{1}-primitive number a_{1} dividing M_{4}, where each prime dividing a_{1} exceeds T.

We claim next that there is a squarefree, α_{2}-primitive number a_{2} dividing a_{1} with

a_{2} ≤ a_{1}^{η/2}.

List the distinct prime factors of a_{1} in increasing order, say T < q_{1} < q_{2} < ⋯ < q_{t}, and put a_{0} := q_{1}q_{2} ⋯ q_{⌊ηt/2⌋}, so that

a_{0} ≤ (q_{1} ⋯ q_{t})^{⌊ηt/2⌋/t} ≤ a_{1}^{η/2}.

We will show that σ(a_{0})/a_{0} ≥ 1 + α_{2}; then we can take a_{2} as any α_{2}-primitive divisor of a_{0}. First, observe that ⌊ηt/2⌋ ≥ ηt/3. Otherwise, t < 6/η and

1 + α_{1} ≤ \frac{σ(a_{1})}{a_{1}} ≤ ∏_{1≤i≤t} (1 + \frac{1}{q_{i} − 1}) ≤ (1 + \frac{1}{T} )^{6/η} ≤ exp (\frac{6}{ηT} ) ,

which is false, assuming a suitable initial choice of T. It follows that

\frac{σ(a_{0})}{a_{0}} = ∏_{1≤i≤⌊ηt/2⌋} \frac{q_{i} + 1}{q_{i}} ≥ (∏_{p>T} \frac{p^{2} − 1}{p^{2}}) ∏_{1≤i≤⌊ηt/2⌋} \frac{q_{i}}{q_{i} − 1},

while

∏_{1≤i≤⌊ηt/2⌋} \frac{q_{i}}{q_{i} − 1} ≥ ( ∏_{1≤i≤t} \frac{q_{i}}{q_{i} − 1})^{⌊ηt/2⌋/t}

≥ (\frac{σ(a_{1})}{a_{1}})^{η/3} ≥ (1 + α_{1})^{η/3} ≥ 1 + \frac{α_{1}η}{6} .

Thus,

\frac{σ(a_{0})}{a_{0}} ≥ (∏_{p>T} \frac{p^{2} − 1}{p^{2}}) (1 + \frac{α_{1}η}{6} ) ≥ 1 + \frac{α_{1}η}{12} ≥ 1 + α_{2},

again assuming a suitable choice of T to justify the middle inequality.

Observe that a_{2} satisfies

a_{2} ≤ a_{1}^{η/2} ≤ (s^{−}(n))^{η/2} < x^{2η/3},

for large x. Write n = P r, where P = P (n). Then r > 1 (since n is composite) and also, by (4),

r ≤ x/P ≤ x^{1−η}.

Moreover, a_{2} divides

s^{−}(P r) = P (σ(r) − r) + σ(r) − 1,

and so

P (σ(r) − r) ≡ 1 − σ(r) (mod a_{2}).

We view this as a linear congruence condition on P modulo a_{2}. If there are any solutions, then D := gcd(σ(r) − r, a_{2}) | 1 − σ(r), and in this case there are exactly D solutions modulo a_{2}. Note that if there are any solutions, then D | 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 ≤ x/r. By the Brun–Titchmarsh inequality and the preceding remarks about D, we have that the number of possible values of n = P r is

≪ ∑_{a_{2} α_{2}-primitive T <a_{2}≤x^{2η/3}} ∑_{1<r≤x^{1−η}} ∑_{D|(a_{2},r−1) ; D squarefree} D\frac{x/r}{φ(a_{2}) log (x/(a_{2}r))}

≪ \frac{x}{η log x} ∑_{a_{2} α_{2}-primitive T <a_{2}≤x^{η/3}} \frac{1}{φ(a_{2})} ∑_{D|a_{2} ; D squarefree} D ∑_{\begin{matrix}1<r≤x^{1−η} \\ D|r−1 \end{matrix}} \frac{1}{r}.

The sum on r is ≪ \frac{1}{D} log x. Moreover, since a_{2} is α_{2}-primitive, we have

\frac{a_{2}}{φ(a_{2})} ≪ \frac{σ(a_{2})}{a_{2}} ≤ \frac{3}{2}(1 + α_{2}) ≪ 1,

and so φ(a_{2}) ≫ a_{2}. Thus, the remaining sum is

≪ \frac{x}{η} ∑_{a_{2} α_{2}-primitive T <a_{2}≤x^{2η/3}} \frac{1}{a_{2}} ∑_{D|a_{2} ; D squarefree} 1 ≪ \frac{x}{η} ∑_{a_{2} α_{2}-primitive a_{2}≥T} \frac{2^{ω(a_{2})}}{a_{2}} .

But if T was chosen sufficiently large, then this last sum is bounded by ηδx (by Lemma 3.3), leading to an upper bound of ≪ δx. Since the number of exceptional n appearing earlier in the argument is also ≪ δx, and δ > 0 was arbitrary, the proof is complete.

4 Proof of Proposition 2.2

We start by quoting two lemmas. The first was developed by Erdős [3] to estimate the decay of the distribution function of σ(n)/n near infinity. We state the lemma in a slightly stronger form which is supported by his proof. Lemma 4.1. For x > 0, the number of positive integers n ≤ x with σ(n)/n > y is

≤ x/ exp(exp((e^{−γ} + o(1))y)), as y → ∞,

uniformly in x, where γ is the Euler–Mascheroni constant.

The next lemma, also due to Erdős [6], supplies an estimate for how often σ(n)/n lands in a short interval; note the uniformity in the parameter a.

Lemma 4.2. Let x > t ≥ 2 and let a ∈ ℝ. The number of n ≤ x with a < σ(n)/n < a + 1/t is ≪ x/ log t.

The next two lemmas develop the philosophy that the rough size of σ(n)/n is usually determined by the small prime factors of n. Put h(n) := ∑_{d|n} \frac{1}{d}, so that h(n) = σ(n)/n. For each natural number T, set h_{T} (n) := ∑_{d|n,P (d)≤T} \frac{1}{d}. The next lemma says that h and h_{T} are usually close once T is large.

Lemma 4.3. Let ϵ > 0 and x ≥ 1. The number of n ≤ x with h(n) − h_{T} (n) > ϵ is ≪ x/(T ϵ).

Proof. Again, we use a first moment argument. We have

∑_{n≤x}(h(n) − h_{T} (n)) ≤ ∑_{n≤x} ∑_{\begin{matrix}d|n \\ d>T \end{matrix}} \frac{1}{d} ≤ x ∑_{d>T} \frac{1}{d^{2}} ≪ x/T,

from which the result is immediate.

Lemma 4.4. Let T be a natural number. Let S be any set of real numbers, and define ℰ (S) as the set of T -smooth numbers e for which h_{T} (e) − 1 ∈ S. Then for n ∈ ℕ, we have h_{T} (n) − 1 ∈ S precisely when n has T -smooth part e for some e ∈ ℰ (S). Moreover, the density of such n exists and is given by

∑_{e∈ℰ (S)} \frac{1}{e} ∏_{p≤T} (1 − 1/p) .  (8)

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 ℰ (S) is given by (8).

For each set of T -smooth numbers ℰ, let \overline{d}_{ℰ} and \underline{d}_{ℰ} denote the upper and lower densities of the set of n whose T -smooth part belongs to ℰ. If \overline{d}_{ℰ} = \underline{d}_{ℰ}, then the density of this set exists; denote it by d_{ℰ}.

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 ∏_{p≤T} p, so that the set of such n has density \frac{1}{e} ∏_{p≤T} (1−1/p). Since density is finitely additive, it follows that for any finite subset ℰ ⊂ ℰ (S),

d_{ℰ} = ∑_{e∈ℰ} \frac{1}{e} ∏_{p≤T} (1 − 1/p) .

Now let x > 0, and put ℰ (S) = ℰ_{1} ∪ ℰ_{2}, where ℰ_{1} = ℰ (S) ∩ [1, x] and ℰ_{2} = ℰ (S) \ ℰ_{1}. Then \underline{d}_{ℰ (S)} ≥ \underline{d}_{ℰ_{1}} for all x, and so letting x → ∞, we find that \underline{d}_{ℰ (S)} is bounded below by (8). On the other hand, \overline{d}_{ℰ (S)} ≤ \overline{d}_{ℰ_{1}} + \overline{d}_{ℰ_{2}}. But \overline{d}_{ℰ_{1}} is bounded above by (8) for all x, while \overline{d}_{ℰ_{2}} ≤ ∑\begin{matrix}e T -smooth \\ e>x \end{matrix} e^{−1} = o(1), as x → ∞. Thus, letting x → ∞, we obtain that \overline{d}_{ℰ (S)} is bounded above by (8).

Proof of Proposition 2.2. Let δ > 0 be sufficiently small. We will show that for

ϵ < exp(−4/δ),  (9)

the number of n ≤ x satisfying (3) is ≪ δ(log log \frac{1}{δ})x, for large x. Note that since δ log log \frac{1}{δ} → 0 as δ ↓ 0, this proves the proposition. In what follows, we fix δ and ϵ, always assuming that δ is small and that ϵ > 0 satisfies (9).

Put T := ϵ^{−1}δ^{−1}. We can assume that both n and n + 1 have T -smooth part ≤ log x. Indeed, for large x, this excludes a set of n size < δx, since

∑_{e T -smooth ; e>log x} \frac{1}{e} = o(1),

as x → ∞.

Let I be the closed interval defined by I := [exp(−1/δ), 2 log log \frac{1}{δ}]. For large x, Lemmas 4.1 and 4.2 imply that all but ≪ δx values of n ≤ x are such that h(n) − 1 ∈ I and h(n + 1) − 1 ∈ I. By Lemma 4.3, excluding ≪ δx additional values of n ≤ x, we can assume that h_{T} (n) ≥ h(n) − ϵ and h_{T} (n + 1) ≥ h(n + 1) − ϵ. Recalling the upper bound (9) on ϵ, we see that both h_{T} (n) − 1 and h_{T} (n + 1) − 1 belong to the interval J, where

J := [\frac{1}{2} exp(−1/δ), 2 log log \frac{1}{δ}] .

Moreover (always assuming δ sufficiently small),

(h_{T} (n) − 1)(h_{T} (n + 1) − 1) ≥ ((h(n) − 1) − ϵ)((h(n + 1) − 1) − ϵ) ≥ 1 − 5ϵ log log \frac{1}{δ}, (10)

and

(h_{T} (n) − 1)(h_{T} (n + 1) − 1) ≤ (h(n) − 1)(h(n + 1) − 1) ≤ 1 + ϵ.  (11)

Write J as the disjoint union of N := ⌈1/ϵ⌉ consecutive intervals J_{0}, J_{1}, …, J_{N−1}, each of length 1/N. We estimate, for each 0 ≤ i < N, the number of n for which h_{T} (n) − 1 belongs to J_{i}. Fix 0 ≤ i < N. Since h_{T} (n) − 1 belongs to J_{i}, (10) and (11) show that

h_{T} (n + 1) − 1 ∈ [\frac{1 − 5ϵ log log \frac{1}{δ}}{x_{i+1}} , \frac{1 + ϵ}{x_{i}}] =: J′_{i},  (12)

where x_{i} and x_{i+1} are the left and right endpoints of J_{i}, respectively. So in the notation of Lemma 4.4, n has T -smooth part e ∈ ℰ (J_{i}) and n+1 has T -smooth part 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′ ∏_{p≤T} p, where the number of allowable residue classes is ∏_{p|ee′}(p − 1) ∏_{p∤ee′,p≤T}(p − 2). For large x,

M ≤ (log x)^{2} ∏_{p≤T} p < (log x)^{3} ≤ x.

(Recall that e, e′ ≤ log x.) Thus, the Chinese remainder theorem shows that the number of such n ≤ x is

≪ \frac{x}{ee′} ∏_{p|ee′}(1 − 1/p) ∏_{\begin{matrix}p∤ee′ \\ p≤T \end{matrix}}(1 − 2/p)

≤ x (\frac{1}{e} ∏_{p≤T}(1 − 1/p)) (\frac{1}{e′} ∏_{p≤T}(1 − 1/p)) ∏_{p|ee′}(1 − 1/p)^{−1}.

But

∏_{p|ee′}(1 − 1/p)^{−1} = \frac{e}{φ(e)} \frac{e′}{φ(e′)} ≪ \frac{σ(e)}{e} \frac{σ(e′)}{e′} ≪ (log log \frac{1}{δ})^{2} ,

since h(e) − 1, h(e′) − 1 ≤ 2 log log \frac{1}{δ}. Summing over e ∈ ℰ (J_{i}) and e′ ∈ ℰ (J′_{i}), we find that the number of n under consideration is

≪ x (log log \frac{1}{δ})^{2} ( ∑_{e∈ℰ (J_{i})} \frac{1}{e} ∏_{p≤T}(1 − 1/p)) ( ∑_{e′∈ℰ (J′_{i})} \frac{1}{e′} ∏_{p≤T}(1 − 1/p)) .

Now sum over 0 ≤ i < N. We obtain that the number of remaining n satisfying (3) is ≪ Lx(log log \frac{1}{δ})^{2}, where

L : = sup_{0≤i<N} \{ ∑_{e′∈ℰ (J′_{i})} \frac{1}{e′} ∏_{p≤T}(1 − 1/p)\} ( ∑_{0≤i<N} \{ ∑_{e∈ℰ (J_{i})} \frac{1}{e} ∏_{p≤T}(1 − 1/p)\})

≤ sup_{0≤i<N} \{ ∑_{e′∈ℰ (J′_{i})} \frac{1}{e′} ∏_{p≤T}(1 − 1/p)\};

we use here that the J_{i} are disjoint, so that

∑_{0≤i<N} ∑_{e∈ℰ (J_{i})} \frac{1}{e} ≤ ∑_{e T -smooth} \frac{1}{e} = ∏_{p≤T}(1 − 1/p)^{−1}.

The proof will be completed by showing that L ≪ δ. It is enough to argue that each sum

∑_{e′∈ℰ (J′_{i})} \frac{1}{e′} ∏_{p≤T}(1 − 1/p)

is ≪ δ, uniformly for 0 ≤ i < N. By Lemma 4.4, this sum describes the density of those natural numbers m for which h_{T} (m)−1 ∈ J′_{i}. We split these m into two classes, according to whether h(m) − h_{T} (m) > ϵ or not. The set of m in the former class has upper density ≪ δ, by Lemma 4.3. Suppose now that h(m) belongs to the second class. From the expression (12) defining J′_{i} and a short computation, we see that h_{T} (m) is trapped within a specific interval of length

≪ exp(2/δ) (log log \frac{1}{δ})^{2} ϵ ≪ exp(3/δ)ϵ.

Since m belongs to the second class, h(m) is also trapped within a specific interval of length ≪ exp(3/δ)ϵ. By (9), exp(3/δ)ϵ ≤ exp(−1/δ), and so by Lemma 4.2, the upper density of the set of those m in the second class is

≪ \frac{1}{δ^{−1} + O(1)} ≪ δ,

assuming again that δ is sufficiently small.

Remark. Our argument also shows that the set of augmented amicable numbers has density zero (see sequences \underline{A007992}, \underline{A015630}). Here an augmented amicable number is an integer which generates a 2-cycle under iteration of the function s^{+}(n) := 1 + ∑_{d|n, d<n} d, e.g., n = 6160.

5 Acknowledgements

The author thanks the National Science Foundation for their generous support (under award DMS-0802970).

References

[1] W. E. Beck and R. M. Najar, More reduced amicable pairs, Fibonacci Quart. 15 (1977), 331–332.

[2] W. E. Beck and R. M. Najar, Reduced and augmented amicable pairs to 10^{8}, Fibonacci Quart. 31 (1993), 295–298.

[3] P. Erdős, Some remarks about additive and multiplicative functions, Bull. Amer. Math. Soc. 52 (1946), 527–537.

[4] P. Erdős, On amicable numbers, Publ. Math. Debrecen 4 (1955), 108–111.

[5] P. Erdős, Remarks on number theory. I. On primitive α-abundant numbers, Acta Arith. 5 (1958), 25–33.

[6] P. Erdős, On the distribution of numbers of the form σ(n)/n and on some related questions, Pacific J. Math. 52 (1974), 59–65.

[7] P. Erdős, A. Granville, C. Pomerance, and C. Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic Number Theory (Allerton Park, IL, 1989), Progr. Math., Vol. 85, Birkhäuser, Boston, 1990, pp. 165–204.

[8] M. Garcia, Números casi amigos y casi sociables, Revista Annal (1968).

[9] R. K. Guy, Unsolved Problems in Number Theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, 2004.

[10] P. Hagis, Jr. and G. Lord, Quasi-amicable numbers, Math. Comp. 31 (1977), 608–611.

[11] M. Kobayashi, P. Pollack, and C. Pomerance, On the distribution of sociable numbers, J. Number Theory 129 (2009), 1990–2009.

[12] M. Lal and A. Forbes, A note on Chowla’s function, Math. Comp. 25 (1971), 923–925.

[13] H. Mishima, Table of quasi-amicable pairs under 10^{10}, online at

    http://www.asahi-net.or.jp/∼kc2h-msm/mathland/math09/math09t2.htm.

[14] J. M. Pedersen, Tables of aliquot cycles, online at

    http://amicable.homepage.dk/tables.htm.

[15] P. Pollack, Powerful amicable numbers, Colloq. Math. 122 (2011), 103–123.

[16] C. Pomerance, On the distribution of amicable numbers, J. Reine Angew. Math. 293/294 (1977), 217–222.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11N37. Keywords: aliquot sequence, quasi-aliquot sequence, quasi-amicable pair, augmented amicable pair.

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

Received November 26 2010; revised version received April 16 2011. Published in Journal of Integer Sequences, April 21 2011.

Return to Journal of Integer Sequences home page.