Some problems of Erdős on the sum-of-divisors function

Abstract

Let $\sigma (n)$ denote the sum of all of the positive divisors of $n$, and let $s(n) = \sigma (n)-n$ denote the sum of the proper divisors of $n$. The functions $\sigma (\cdot )$ and $s(\cdot )$ were favorite subjects of investigation by the late Paul Erdős. Here we revisit three themes from Erdős’s work on these functions. First, we improve the upper and lower bounds for the counting function of numbers $n$ with $n$ deficient but $s(n)$ abundant, or vice versa. Second, we describe a heuristic argument suggesting the precise asymptotic density of $n$ not in the range of the function $s(\cdot )$; these are the so-called nonaliquot numbers. Finally, we prove new results on the distribution of friendly $k$-sets, where a friendly $k$-set is a collection of $k$ distinct integers which share the same value of $\frac{\sigma (n)}{n}$.

1. Introduction

Let $\sigma (n)$ be the sum of the natural number divisors of $n$, so that $\sigma (n) = \sum _{d \mid n} d$. Let $s(n)$ be the sum of only the proper divisors of $n$, so that $s(n)=\sigma (n)-n$. Interest in these functions dates back to the ancient Greeks, who classified numbers as deficient, perfect, or abundant according to whether $s(n) < n$, $s(n)=n$, or $s(n) > n$, respectively. For example, $10$ is deficient, $12$ is abundant, and $6$ is perfect. The ancient Greeks also found and remarked on 2-cycles, where $s(n)=m$ and $s(m)=n$, calling such a pair amicable; for example, 220 and 284.

A conjecture of Catalan in 1888 8, as amended by Dickson in 1913 12, claims that for every positive integer $n$, the aliquot sequence $n,s(n),s(s(n)),\dots$ either terminates at 0 or enters some cycle, such as a perfect number, an amicable pair, or some longer cycle. Despite much numerical work, there are still 12 numbers $n<1000$ for which the conjecture is in doubt, the first being 276. This numerical work uncovered long stretches where some aliquot sequences grow monotonically and exponentially, and other stretches where they decay in like manner. This behavior was taken into account in the Guy–Selfridge 25 counter-conjecture that for asymptotically all even numbers $n$, the aliquot sequence starting with $n$ is unbounded.

It was proved by Lenstra 29 that for each $k$ there is an aliquot sequence that strictly increases for $k$ terms. Erdős 20 showed that this is common and, in fact, if $n$ is abundant, then but for a set of numbers $n$ of asymptotic density 0, the aliquot sequence starting with $n$ strictly increases for $k$ terms. In the same paper, Erdős claimed the analogous result for deficient numbers (with “increases” replaced with “decreases”), but this claim was retracted in 22. In that paper, the claim was shown for $k=2$. It is conjectured that the full claim holds, but this has never been shown.

These results assert that if $n$ is abundant, it is likely that $s(n)$ is also abundant, and similarly for deficient. Say $n$ is an aliquot reversal if this fails. More precisely, say $n$ is an up-down reversal if $n$ is nondeficient yet $s(n)$ is deficient, and say $n$ is a down-up reversal if $n$ is deficient and $s(n)$ is nondeficient.

Though the terminology is new to this paper, aliquot reversals have been studied for some time because of their connection with amicable pairs; in fact the lesser member of an amicable pair is an up-down reversal, while the larger member is a down-up reversal. Erdős was the first to prove, in 15, that the set of numbers involved in an amicable pair has vanishing asymptotic density, and he did this by showing that there are few up-down reversals. The count of up-down reversals was improved later by Rieger 40, by Erdős–Rieger 21, and by the second author (see 36). In that last paper it was shown that the number of $n\le x$ giving an up-down reversal is at most

$$\begin{equation} x/\exp ((c+o(1)) (\log _3{x} \log _4{x})^{1/2}), \text{ as }x\to \infty ,{\tag{1.1}} \end{equation}$$

for a certain absolute constant $c > 0$. Here, the subscripts indicate iteration of the natural log function. The proof uses results of Erdős 13 for the count of primitive nondeficient numbers. Incorporating an improvement on these results due to Avidon 3, this argument gives $c=1$. In 33, Corollary 1.5, the same upper estimate 1.1 was shown for the number of down-up reversals in $[1,x]$, but only with the smaller constant $c=\frac{1}{10}$.

Our first theorem is an improvement on these upper bounds.

Theorem 1.1.

Both the count of down-up reversals in $[1,x]$ and the count of up-down reversals in $[1,x]$ are bounded above by 1.1 with $c=\sqrt {3}$.

The proof uses recent results from 2 on the number of solutions $n$ to congruences of the form $\sigma (n)\equiv a\pmod {n}$.

The problem of obtaining lower bounds on the number of aliquot reversals does not seem to have been previously considered. Note that the upper bounds of the last paragraph just barely give density 0. In the following results we show there is a reason for this: reversals are fairly common. We prove the following.

Theorem 1.2.

The number of up-down reversals in $[1,x]$ is $\gg x/(\log _2{x})(\log _3{x})^3$.

Theorem 1.3.

The number of down-up reversals in $[1,x]$ is $\gg x/(\log _2{x})(\log _3{x})^2$.

One might wonder if these results lend support to the Catalan–Dickson conjecture or to the Guy–Selfridge counter-conjecture. It is helpful to think in terms of parity. In fact, $n$ and $s(n)$ have opposite parity precisely when $n$ is a square or a double of a square, and such $n$ comprise a very sparse set. In addition, it follows from the proof in 20 that for each fixed $k$, almost all $n$ have the same parity as $s_k(n)$ (the $k$th iterate of $s$ at $n$). Since an aliquot sequence terminates only if it hits a prime, a perhaps reasonable conjecture is that aliquot sequences beginning with even numbers usually either are unbounded or enter some cycle of even numbers. Numbers involved in such cycles have density 0 (see 28). Numerical evidence indicates that most numbers involved in these cycles are amicable (i.e., they are in a 2-cycle), and we know that amicable numbers are quite sparsely distributed (see 38). Thus, despite the fact that our results show nonmonotonicity is fairly common, the Guy–Selfridge point of view is believable. And some cases of nonmonotonicity are quite rare. For example, take numbers $n\equiv 6\pmod {12}$, $n>6$. They are abundant, but the number of them to $x$ with $s(n)$ deficient is $O(x^{1/2})$. Further, in a recent preprint of Bosma 6, it is shown that about $1/3$ of the even numbers to 1 million have their aliquot sequence still open beyond $10^{99}$. This evidence seems to put a chill on the Catalan–Dickson conjecture! On the other hand, it is hard to align this numerical evidence with the recent paper of Bosma–Kane 7 where it is shown that the geometric mean of $s(2n)/2n$ for $n \le x$ tends to a constant smaller than 1 as $x\to \infty$.

We remark that the lower bounds in Theorems 1.2, 1.3 are established for even numbers. It would be of interest to see what kind of lower bounds can be established for odd numbers.

We turn now to our second topic. Positive integers not in the range of $s(\cdot )$ are said to be nonaliquot, though the more colorful term untouchable (see Alanen 1) has also been used. The concept dates back to at least ca. 1000 CE 41. A useful initial observation is that if $p$ and $q$ are distinct primes, then $s(pq) = p+q+1$. A slightly stronger form of Goldbach’s conjecture is that every even integer $n \ge 8$ is a sum of two distinct primes. If so, then every odd $n \ge 9$ belongs to the range of $s(\cdot )$; noting that $s(2)=1$, $s(4)=3$, and $s(8)=7$, we would have that $5$ is the only odd nonaliquot number.

While the conjecture of the last paragraph remains out of reach, it follows from (independent) work of Chudakov, van der Corput, and Estermann that almost all even numbers can be written as a sum of two distinct primes. (See 46, Chapter 3 for a modern treatment.) Hence, the set of odd nonaliquot numbers has asymptotic density zero.

What about even numbers? In 18, Erdős proved that a positive proportion of even numbers are nonaliquot. By an elaboration of Erdős’s methods, Chen and Zhao 9 have shown that the nonaliquot even integers make up a set of lower density greater than $0.06$. (This improves earlier results reported in 5 and 44, Corollary 9.2, p. 64.) Erdős was unable to decide whether or not a positive proportion of even numbers do belong to the image of $s$, but this has been resolved affirmatively in very recent work of Luca and the second author 30.

In §3, refining some thoughts in 44, we propose a probabilistic model for $s(\cdot )$ that suggests a precise value for the density of nonaliquot numbers.

Conjecture 1.4.

The set of nonaliquot numbers has asymptotic density $\Delta$, where

$$\begin{equation*} \Delta = \lim _{y\to \infty }\frac{1}{\log {y}} \sum _{\substack{a \le y \\ 2\mid a}} \frac{1}{a}{\mathrm{e}}^{-a/s(a)}. \end{equation*}$$

At $y=2\cdot 10^{10}$, the expression inside the limit has value $0.171822$. Table 1 collects counts of nonaliquot numbers up to $10^{10}$; these counts are consistent with a limiting density of $\approx 0.17$.

Finally, we consider the distribution of the rational numbers $\frac{\sigma (n)}{n}$. We are interested here in statistics for

$$\begin{equation*} F(n;x) = \#\left\{m \le x: m\ne n,\nobreakspace \frac{\sigma (m)}{m} = \frac{\sigma (n)}{n}\right\}, \end{equation*}$$

thought of as a random variable on the set of natural numbers $n \le x$, equipped with the uniform measure. A theorem of Wirsing 47 asserts that an equation of the form $\frac{\sigma (n)}{n}=\alpha$ has at most $x^{o(1)}$ solutions $n \le x$, as $x\to \infty$, uniformly in $\alpha$. Thus, we have a pointwise bound $F(n;x) = x^{o(1)}$, as $x\to \infty$. The average behavior of $F(n;x)$ was determined by Erdős 17, Theorem 2; for a certain constant $c > 0$,

$$\begin{equation} \sum _{n \le x} F(n;x) \sim cx, \quad \text{as}\quad x\to \infty .{\tag{1.2}} \end{equation}$$

Note that $\sum _{n \le x} F(n;x)$ counts the number of ordered pairs of distinct integers $(n,m) \in [1,x]^2$ with $\frac{\sigma (n)}{n} = \frac{\sigma (m)}{m}$, and this is the way Erdős states his result.

Call a pair (unordered) of distinct integers $n$ and $m$ a friendly pair if $\frac{\sigma (n)}{n} = \frac{\sigma (m)}{m}$. Evidently, if $u$ is coprime to $nm$, then $un, um$ is also a friendly pair. Call the friendly pair $n,m$ primitive friendly if $n$ and $m$ have no nontrivial common unitary divisor. (We say $d$ is a unitary divisor of $n$, and write $d\parallel n$, if $d\mid n$ and $\gcd (d,n/d)=1$.) The key ingredient in Erdős’s proof of 1.2 is the convergence of $\sum \frac{1}{m}$, where $m$ runs over the larger members of the primitive friendly pairs (with multiplicities). We prove a substantially stronger result on the distribution of such pairs:

Theorem 1.5.

The number of primitive friendly pairs contained in $[1,x]$ is at most $x^{\frac{1}{2}+o(1)}$, as $x\to \infty$.

Erdős’s theorem on the convergence of $\sum \frac{1}{m}$ follows immediately by partial summation. The exponent $\frac{1}{2}$ appears to be the limit of our method, but the numerical data (see Table 2) suggest that this is not sharp. Perhaps the true count of primitive friendly pairs in $[1,x]$ is $x^{o(1)}$.

By studying primitive friendly $k$-sets for integers $k\ge 2$, we are able to show that $F(n;x)$ has a limiting distribution. Set $N_k(x) = \#\{n \le x: F(n;x) \ge k\}$.

Theorem 1.6.

For each fixed nonnegative integer $k$, we have $N_k(x) = (\alpha _k+o(1)) x$, as $x\to \infty$, for some constant $\alpha _k$. Moreover, $\alpha _k \to 0$ as $k\to \infty$.

Clearly, $\alpha _0=1$. Though the constants $\alpha _k$ for $k\ge 1$ are effectively computable (via the proof of Theorem 1.6), we have not found good rigorous numerical estimates for them. However, explicit computations of $N_k(x)$ suggest that $\alpha _1= 0.0347\dots$, $\alpha _2 = 0.0028\dots$, $\alpha _3 = 0.00085\dots$, and $\alpha _4=0.000084\dots$; see Table 3.

Notation.

We use the Bachmann–Landau $\asymp$, $O$ and $o$-notations, with their usual meanings, as well as the associated Vinogradov $\ll$ and $\gg$ notations. $P(n)$ denotes the largest prime factor of $n$, with the convention that $P(1)=1$, and $\mathrm{rad}(n)$ denotes the largest squarefree divisor of $n$. We reserve the letter $p$, with or without subscripts or dashes, for primes. We write $v_p(n)$ for the exponent on the highest power of $p$ dividing $n$. The notation $\mathrm{gcud}(m,n)$ stands for the greatest common unitary divisor of $m$ and $n$. We use $\varphi$ for Euler’s totient function, $\omega$ for the number of prime divisors, $\Omega$ for the number of prime factors counted with multiplicity, and $\tau$ for the total number of divisors.

2. Aliquot reversals

2.1. Upper bounds

2.1.1. A structural lemma on primitive nondeficient numbers

The proof of Theorem 1.1 runs along similar lines as the proof of the main theorem of 36. In particular, the primitive nondeficient numbers play a critical role. (These are numbers $n$ with $\sigma (n)/n\ge 2$ and for each proper divisor $d$ of $n$, $\sigma (d)/d<2$.) The main new ingredient is a lemma that is perhaps of independent interest: Almost all primitive nondeficient numbers $n$ have $P(n) \lessapprox n^{1/3}$.

We will deduce the lemma from the results of 2 concerning solutions $n$ to the congruence $\sigma (n)\equiv a\pmod {n}$. In that paper, $n$ is called a regular solution if

$$\begin{equation*} n =pm, \quad \text{where}\quad p \nmid m,\nobreakspace m \mid \sigma (m),\nobreakspace \text{and } \sigma (m)=a. \end{equation*}$$

(It is straightforward to check that these numbers $n$ are solutions of the congruence.) In the remaining case, $n$ is called sporadic. Note that regular solutions can exist only when $a > 0$. The following is a slightly less precise form of 2, Theorem 1.

Proposition 2.1.

The number of sporadic solutions $n \le x$ to $\sigma (n)\equiv a\pmod {n}$ is at most $x^{1/2+o(1)}$, as $x\to \infty$, uniformly for $|a| \le x^{1/4}$.

The restriction $|a| \le x^{1/4}$ is inconvenient for our purposes. We can ameliorate this as follows. Call a sporadic solution $n$ to $\sigma (n)\equiv a\pmod {n}$ convenient if all of the following hold:

(i)

$k:=\frac{\sigma (n)-a}{n}$ is an integer at least $2$,

(ii)

if $d$ is a unitary divisor of $n$ with $d<n$, then $\frac{\sigma (d)}{d} < k$,

(iii)

there is a prime $q>P(n)$ with $\frac{\sigma (nq)}{nq} > k$.

Proposition 2.2.

The number of convenient solutions $n \le x$ to $\sigma (n)\equiv a\pmod {n}$ is at most $x^{1/2+o(1)}$, as $x\to \infty$, uniformly in $a$ with $|a| \le x$.

Sketch of the proof.

Hornfeck and Wirsing 27, Satz 2 have shown that there are $x^{o(1)}$ multiply perfect numbers $n\le x$; hence, we may assume that $a\ne 0$.

While not phrased this way in 2, the proof of 2, Theorem 1 when $a\ne 0$ is handled there by reduction to the convenient case. Indeed, Lemma 5 in 2 asserts that if $n$ is a sporadic solution to $\sigma (n)\equiv a\pmod {n}$ and $n > 6a^2\log (6|a|)$, then $n$ is convenient. In our setup here, we start by assuming $n$ is convenient. Thus, the conclusion of 2, Lemma 5 holds trivially. Moreover, only the convenience hypothesis is needed in the proofs of Lemmas 6 and 7 from 2. That is, both of those lemmas hold with the assumption of convenience replacing the hypothesis “$n$ is a sporadic solution satisfying $n > 6a^2\log (6|a|)$”.

With these lemmas in place, we can again run the proof of 2, Theorem 1. It proceeds exactly as before, except that now there is no need to assume $n > 6a^2\log (6|a|)$. That assumption was responsible for the restriction $|a| \le x^{1/4}$, which can now also be dispensed with. Following the proof through, we deduce that there are at most $x^{1/2+o(1)}$ convenient solutions $n\le x$, uniformly for $|a| \le x$.

■

We now deduce the key lemma.

Lemma 2.3.

Fix $\epsilon > 0$. The number of primitive nondeficient $n \le x$ with $P(n) > n^{1/3+\epsilon }$ is $O_{\epsilon }(x^{1-\epsilon })$, as $x\to \infty$.

Proof.

After a dyadic subdivision argument, it is enough to prove the claimed upper bound for the number of primitive nondeficient $n\in (x,2x]$ with $P(n)>x^{1/3+\epsilon }$. By 27 or 47, the number of perfect $n \le 2x$ is $x^{o(1)}$, as $x\to \infty$. Thus, we can assume that $n$ is abundant. We can also assume $P(n)^2 \nmid n$, since otherwise $n$ belongs to a set of size at most $2x \sum _{p > x^{1/3+\epsilon }} p^{-2} \ll x^{2/3-\epsilon }$. Write $n=pm$, where $p = P(m)$. Since $n=mp$ is primitive nondeficient,

$$\begin{equation*} 2 > \frac{\sigma (m)}{m} > \frac{2}{\sigma (p)/p} > 2- 2x^{-{1}/{3}-\epsilon }. \end{equation*}$$

Hence,

$$\begin{equation*} -2m x^{-{1}/{3}-\epsilon } < a:= \sigma (m)-2m < 0 \end{equation*}$$

and

$$\begin{equation*} |a|< 2m x^{-1/3-\epsilon } \le 4 \frac{x}{p} x^{-1/3-\epsilon } = 4 x^{2/3-\epsilon }/p. \end{equation*}$$

The integer $m$ is a sporadic solution to $\sigma (m) \equiv a\pmod {m}$. Moreover, conditions (i)–(iii) in the definition of a convenient solution are easily verified for $m$, with $k=2$ and $q=p$.

Fixing $a$ and $p$, Proposition 2.2 shows that the number of corresponding values of $m \le 2x/p$ is $O_{\epsilon }((x/p)^{1/2+\epsilon /2})$. Summing on $a\in (-4 x^{2/3-\epsilon }/p,0)$, the number of possibilities for $m$ given $p$ is

$$\begin{equation*} \ll _{\epsilon } \frac{x^{2/3-\epsilon }}{p} \cdot \left(\frac{x}{p}\right)^{1/2+\frac{1}{2}\epsilon } \ll \frac{x^{7/6-\frac{1}{2}\epsilon }}{p^{3/2}}. \end{equation*}$$

Summing on $p>x^{1/3+\epsilon }$ gives a final upper bound of $O_{\epsilon }(x^{1-\epsilon })$, as desired.

■

Remark.

The proof can be improved to achieve the upper bound $x^{1-\frac{3}{2}\epsilon +o(1)}$, as $x\to \infty$. For our purposes, any power-savings upper bound is sufficient.

It would be desirable to prove Lemma 2.3 with a smaller exponent than $\frac{1}{3}$. If the lemma holds with $\frac{1}{R}$ (say), then the arguments below show that Theorem 1.1 holds with $c=\sqrt {R}$. In particular, if $R$ can be taken arbitrarily large, we would have a qualitative improvement over any bound of the shape 1.1. Such an improvement would follow from a conjecture posed in 2:

Conjecture 2.4.

Let $x\ge 3$, and let $a$ be an integer with $|a| \le x/2$. Let $k$ be an integer with $k \ge 2$. The number of solutions $n \le x$ to $\sigma (n) = kn+a$ is

$$\begin{equation*} \ll (\log {x})^C, \end{equation*}$$

where both the implied constant and $C$ are absolute constants.

Remark.

This is a corrected form of the conjecture as it appeared in 2. The original formulation allowed $k=0$ and $k=1$; these cases must be excluded to account for popular values $a$ of $\sigma (n)$ or $s(n)$.

2.1.2. Proof of Theorem 1.1

Let

$$y=y(x)=\frac{\log _2x}{2\log _3x}.$$

We begin with a lemma.

Lemma 2.5.

The number of integers $n\le x$ for which $\sigma (n)$ is not divisible by every integer $m \le y$ is $O(x/\log _2x)$.

Proof.

We use 36, Theorem 2, which asserts that for coprime integers $\ell ,k$ with $k>0$, the number of integers $n\le x$ such that no prime $p\equiv \ell \pmod k$ has $p \parallel n$ is $O(x/(\log x)^{1/\varphi (k)})$, uniformly. Applied with $\ell =-1, k=m$ the result implies that the number of $n$ counted in the lemma is

$$\begin{equation*} \ll \sum _{m\le y}\frac{x}{(\log x)^{1/\varphi (m)}} \le \sum _{m\le y}\frac{x}{(\log x)^{1/m}} \le \sum _{m\le y}\frac{x}{(\log _2x)^2} \ll \frac{x}{\log _2x}. \end{equation*}$$■

For future reference we state the result of Avidon 3 mentioned in the introduction.

Lemma 2.6.

The number of primitive nondeficient numbers $a\le t$ is at most

$$t/\exp ((1+o(1))\sqrt {\log t\log _2t}),\quad t\to \infty .$$

We shall also use a result of Toulmonde 45, Théorème 1 (see the discussion in §10) on the modulus of continuity of the distribution function for $\sigma (n)/n$.

Lemma 2.7.

If $\alpha$ is in the range of $\sigma (n)/n$, then uniformly for $T\ge 3$, the number of integers $m\le x$ with

$$\alpha -\frac{1}{T}\le \frac{\sigma (m)}{m}<\alpha$$

is $\ll x/\exp (\frac{1}{5}\sqrt {\log T\log _2 T})$.

Proof of Theorem 1.1.

Let $\epsilon >0$ be fixed. Suppose $n\le x$ is nondeficient with $s(n)$ deficient, and let $a$ be the least nondeficient number that divides $n$. If each prime power dividing $a$ is at most $y$, then Lemma 2.5 implies that but for $O(x/\log _2x)$ choices for $n$, we may assume that $a\mid \sigma (n)$. This in turn implies that $a\mid s(n)$, contradicting that $s(n)$ is deficient. Thus, $a$ has a prime power divisor exceeding $y$. If $a>y^{3-\epsilon }$, then Lemma 2.6 implies that the number of $n\le x$ divisible by such a primitive nondeficient number $a$ is at most $x/\exp ((1+o(1))\sqrt {(3-\epsilon )\log _3x\log _4x})$ as $x\to \infty$. Hence we may assume that $a\le y^{3-\epsilon }$ and $a$ is divisible by a prime power $q>y$. If $q$ is a proper power, the number of $n\le x$ divisible by such a large power is $O(x/\sqrt {\log _2x})$, so we may assume that $q$ is prime and $q>a^{1/3+\epsilon /9}$. But then, by Lemma 2.3, the number of $n\le x$ divisible by such a primitive nondeficient $a$ is $O_\epsilon (x/y^{\epsilon /9})$. Since $\epsilon$ may be taken arbitrarily close to 0, our result follows.

The argument for down-up reversals is similar, but more difficult. Suppose $n\le x$ is deficient and $s(n)$ is not deficient, and let $a$ be the least nondeficient number dividing $s(n)$. Again, by Lemma 2.5, if each prime power dividing $a$ is at most $y$, then we may assume that $a\mid \sigma (n)$. This implies that $a\mid n$, contradicting $n$ deficient. Thus, we may assume $a$ has some prime power divisor greater than $y$.

Write $n=mp$ where $p=P(n)$. By standard results on the distribution of integers all of whose prime factors are small (see 10), we may assume that $p>x^{1/\log _3x}$ and $p\nmid m$. We have $s(n)=ps(m)+\sigma (m)\equiv 0\pmod a$. Let $a'=\gcd (a,s(m))$. The congruence implies that $a'\mid \sigma (m)$, so that $a'\mid m$. The congruence also implies that $p$ is in a residue class modulo $a/a'$.

We first assume that

$$a\le Z:=x^{1/2\log _3x}.$$

Given $a,m,a'$, by the Brun–Titchmarsh inequality, the number of choices for $p\le x/m$ is

$$\ll \frac{x}{m\varphi (a/a')\log (x/m(a/a'))} \ll \frac{x\log _3x}{m\varphi (a/a')\log x} \ll \frac{x\log _3x}{m(a/a')\log x},$$

where for the last step we use that $a$ is primitive nondeficient, so that $\varphi (a/a')\gg a/a'$. We have $a'\mid m$, so summing the displayed upper bound over $m$ and then over $a'$, we get that the number of choices is

$$\ll \frac{\tau (a)}{a}x\log _3x.$$

We can restrict to $a$ which have no proper prime power divisor in $(y,Z]$. Indeed, by an argument analogous to that just seen, the number of $n$ as above for which $s(n)$ is divisible by a given prime power $\ell ^{v} \le Z$ is $O(x\tau (\ell ^v)\ell ^{-v}\log _3{x})=O(xv\ell ^{-v}\log _3x)$. Summing over proper prime powers $\ell ^{v} >y$, we find that only a negligible set of $n$ arise in this manner. Since $a\le Z$, we may assume that $a$ is divisible by a prime $\ell >y$.

We now wish to find a good upper bound for the sum of $\tau (a)/a$ as $a$ runs over primitive nondeficient numbers divisible by a prime greater than $y$. We first assume that $a\le y^{3-\epsilon }$. Then $P(a)>a^{1/3+\epsilon /9}$. Using $\tau (a)=a^{o(1)}$ as $a\to \infty$ and Lemma 2.3 we have $\sum \tau (a)/a\le y^{-\epsilon /9+o(1)}$, which is sufficient for our needs. So now assume that $a> y^{3-\epsilon }$. If also $\tau (a)\le \exp (\epsilon \sqrt {\log a\log _2a})$, a brief calculation with Lemma 2.6 suffices.

Now assume that $y^{3-\epsilon }<a\le Z$ and $\tau (a)>\exp (\epsilon \sqrt {\log a\log _2a})$. We forget at this point that $a$ is running over primitive nondeficient integers. For each fixed positive integer $j$,

$$\begin{equation} \sum _{k\le T}\frac{\tau (k)^j}{k} \le \prod _{p \le T} \left(1+\frac{2^j}{p} + O_j\left(\frac{1}{p^2}\right)\right)\ll _j(\log T)^{2^j}. {\tag{2.1}} \end{equation}$$

Let $T\ge y^{3-\epsilon }$ and consider values of $k\in (T,T^2]$ with

$$\tau (k)>z(T):=\exp (\epsilon \sqrt {\log T\log _2T}).$$

We have

$$\sum _{\substack{T<k\le T^2\\\tau (k)>z(T)}}\frac{\tau (k)}{k} \le \frac{1}{z(T)^{j-1}}\sum _{T<k\le T^2}\frac{\tau (k)^j}{k} \ll _j\frac{(\log T)^{2^j}}{z(T)^{j-1}}.$$

Thus, letting $T$ range over numbers of the form $(y^{3-\epsilon })^{2^i}$, for $i=0, 1, 2, \dots$,

$$\sum _{\substack{a>y^{3-\epsilon }\\\tau (a)>z(a)}}\frac{\tau (a)}{a} \ll _j\frac{(\log y)^{2^j}}{z(y^{3-\epsilon })^{j-1}}.$$

If we choose $j=\lceil \epsilon ^{-1}\rceil$, and let $\epsilon$ be arbitrarily small, this estimate completes the argument in the case $a\le Z$.

Now we assume $a>Z$. Since $a\mid s(n)$ and $s(n)\le n$, we have $a\le x$. Consider the “$Z$-prefix” divisor $b$ of $a$. This is the largest divisor of $a$ in $[1,Z]$ with each prime dividing $b$ bounded above by each prime dividing $a/b$. We may assume that

$$\begin{equation} b>Z^{1/3}. {\tag{2.2}} \end{equation}$$

Indeed, if $b\le Z^{1/3}$, then every prime factor of $a/b$ is greater than $Z^{2/3}$, so that

$$\frac{\sigma (a/b)}{a/b}= 1+O\left(\frac{\log x}{Z^{2/3}}\right),$$

since $a/b$ has fewer than $\log x$ distinct prime factors. Also, since $b$ is deficient, we have

$$\frac{\sigma (b)}{b}\le 2-\frac{1}{b}\le 2-\frac{1}{Z^{1/3}}.$$

The last two displays imply that for $x$ sufficiently large, we have $a$ deficient, a contradiction. Thus, we have 2.2.

Let $\mathscr{B}$ denote the set of integers $b\in (Z^{1/3},Z]$ which are the $Z$-prefix for some primitive nondeficient $a\in (Z,x]$. We will show that there are very few integers $n\le x$ with $s(n)$ divisible by some member of $\mathscr{B}$. To do this, we show that the set $\mathscr{B}$ is rather sparse.

Let $Y:=Z^{1/\log _2x}$, and assume that $b\in \mathscr{B}$ and $P(b)>Y$. Then, as above,

$$\frac{\sigma (a/b)}{a/b}= 1+O\left(\frac{\log x}{Y}\right),$$

so for $a$ to be nondeficient, there is some absolute constant $c>0$ such that

$$2>\frac{\sigma (b)}{b}\ge 2-\frac{c\log {x}}{Y}.$$

By Lemma 2.7, for $t\in (Z^{1/3},Z]$, the number of integers $b\le t$ which satisfy the last display is at most $t/\exp (\frac{1}{8}\sqrt {\log x/\log _3x})$ for all sufficiently large $x$. (Here $8$ could be replaced with any number exceeding $5\sqrt {2}$.)

We also wish to count the number of $b\in \mathscr{B}$, $b\le t$ with $P(b)\le Y$. For this we ignore the condition $b\in \mathscr{B}$ and use only a standard result in 10: the number of such $b$ is at most $t/(\log x)^{\frac{1}{4}\log _3x}$ for all sufficiently large $x$.

As in the case $a\le Z$, we find that the number of integers $n\le x$ with $b\mid s(n)$ for some $b\in \mathscr{B}$ (and assuming $n=pm$ with $p>x^{1/\log _3x}$ and $p\nmid m$) is

$$\ll x\log _3x\sum _{b\in \mathscr{B}}\frac{\tau (b)}{b}.$$

Again as before we treat the cases of $\tau (b)$ small and large separately. If $\tau (b)\le (\log x)^{\frac{1}{8}\log _3x}$, then our estimates for the number of $b\le t$ suffice to give an acceptable estimate. If $\tau (b)>(\log x)^{\frac{1}{8}\log _3x}$, we use 2.1 with $j=2$, getting

$$\sum _{\substack{Z^{1/3}<b\le Z\\\tau (b)>(\log x)^{\frac{1}{8}\log _3x}}} \frac{\tau (b)}{b} \le \frac{1}{(\log x)^{\frac{1}{8}\log _3x}}\sum _{Z^{1/3}<b\le Z}\frac{\tau (b)^2}{b} \ll (\log x)^{4-\frac{1}{8}\log _3x}.$$

This too is sufficiently small, so completing our proof.

■

2.2. Lower bounds

Here we prove Theorems 1.2, 1.3.

Proof of Theorem 1.2.

Let $x$ be large, let $k$ be the least integer with $2^k>\log _2 x$, and let $p$ be a prime with $2^k<p<2^{k+1}-1$. We shall consider numbers $n=2^kpmq\le x$ where $x^{1/6}<m\le x^{1/3}$ and $q$ is prime with $q>x^{1/3}$. Since $2^kp$ is abundant, such numbers $n$ are abundant. With no further restrictions on the parameters $m,q$, the number of $n$’s created in this way is $\gg x/\log _2x\log _3x$. We will show that with some mild restrictions on $m,q$ we can be assured that $s(n)$ is deficient, and these restrictions will only reduce our count by a factor of $(\log _3x)^2$.

We shall want the numbers $m$ to satisfy:

(i)

$2^k\mid \sigma (m)$,

(ii)

$p\nmid \sigma (m)$,

(iii)

$m$ has no prime factors below $(\log _2x)^2$.

We can ensure $m$ satisfies (ii) and (iii) by eliminating those $m$ divisible by any of

•

a proper prime power $r^{\alpha } \ge p/2$,

•

a prime $r \equiv -1\pmod {p}$,

•

a prime $r \le (\log _2{x})^2$.

Let $t \in [x^{1/6},x^{1/3}]$. By Brun’s sieve 26, Theorem 2.2, there is an absolute constant $\eta > 0$ such that the number of $m \le t$ divisible by no prime $r \le t^{\eta }$ in the second or third bullet points is

$$\begin{multline*} \gg t \prod _{r \le (\log _2{x})^2}\left(1-\frac{1}{r}\right) \prod _{\substack{r \le t^{\eta } \\ r\equiv -1\ (\text{mod}\,{p})}}\left(1-\frac{1}{r}\right) \\ \gg \frac{t}{\log _3{x}} \exp \bigg (-\sum _{\substack{r \le t^{\eta } \\r\equiv -1\ (\text{mod}\,{p})}} \frac{1}{r}\bigg ) \gg \frac{t}{\log _3{x}}. \end{multline*}$$

(The sum on $r$ here is $O(1)$, by the Brun–Titchmarsh inequality and the bound $p \gg \log _2{t}$.) The number of $m \le t$ divisible by some prime $r > t^{\eta }$ with $r\equiv -1\pmod {p}$ is $\ll t\sum _{t^{\eta } < r \le t,\nobreakspace r\equiv -1\pmod {p}} \frac{1}{r} \ll t/p \ll t/\log _2{x}$, which is $o(t/\log _3{x})$, as $x\to \infty$. Finally, the number of $m\le t$ divisible by some proper prime power $r^{\alpha } \ge p/2$ is $\ll t/\sqrt {p} \ll t/\sqrt {\log _2{x}}$, and this is also $o(t/\log _3{x})$. Thus, there are $\gg t/\log _3{x}$ values of $m \le t$ satisfying (ii) and (iii). In fact, this is the correct order of magnitude for this count, since (iii) by itself already implies an upper bound of the same form.

We now turn to (i). We apply the Turán–Kubilius inequality 43, Theorem 1, p. 302 to investigate the normal order of the additive function $v_2(\sigma (m))$. Uniformly for $x^{1/6}\le t\le x^{1/3}$,

$$\begin{equation*} \sum _{p^v \le t} v_2(\sigma (p^v)) p^{-v}(1-p^{-1}) \sim 2\log _2{x} \end{equation*}$$

and

$$\begin{equation*} \sum _{p^v \le t} v_2(\sigma (p^v)) p^{-v} \ll \log _2{x}. \end{equation*}$$

Hence, the number of positive integers $m\!\le \! t$ where $v_2(\sigma (m))\! <\! \log _2{x}$ is $O(t/\log _2 x)$. Since $k \ll \log _3{x}$, this is also an upper bound on the number of failures of (i).

We conclude that there are $\asymp t/\log _3{x}$ values of $m\le t$ satisfying all of (i)–(iii). By partial summation,

$$\begin{equation} \sum _{m} \frac{1}{m} \asymp \frac{\log {x}}{\log _3{x}}, {\tag{2.3}} \end{equation}$$

where the sum is over $m \in (x^{1/6},x^{1/3}]$ satisfying (i)–(iii).

For each $m$, let $f_0(m)=\sum _{r\mid m}1/r$, where $r$ runs over primes. Using that $m$ is free of prime factors up to $(\log _2{x})^2$ gives

$$\begin{equation*} \sum _{m} \frac{1}{m} f_0(m) = \sum _{r > (\log _2{x})^2} \frac{1}{r} \sum _{m:\nobreakspace r\mid m}\frac{1}{m} \le \sum _{r > (\log _2{x})^2} \frac{1}{r^2} \prod _{\substack{p \le x \\ p > (\log _2{x})^2}} (1-1/p)^{-1}, \end{equation*}$$

which is $\ll \frac{\log {x}}{(\log _2{x})^2 (\log _3{x})^2}$. In what follows, we will assume that

$$\begin{equation} f_0(m)\le \frac{1}{2(\log _2x)^2}. {\tag{2.4}} \end{equation}$$

Note that discarding contrary values of $m$ changes $\sum _{m}\frac{1}{m}$ only by $O(\log {x}/(\log _3{x})^2)$ and so preserves the validity of 2.3.

We now complete the construction of a number $n=2^kpmq$ by choosing a prime $q\in (x^{1/3},x/2^kpm]$. Suppose an odd prime $r$ divides $s(n)$. Then

$$s(n)=qs(2^kpm)+\sigma (2^kpm)\equiv 0\pmod r.$$

If $r\mid s(2^kpm)$, then $r\mid \sigma (2^kpm)$, so that $r\mid 2^kpm$. Such a prime $r$ cannot be 2 by assumption, and it cannot be $p$, since $p\nmid \sigma (2^k)$ and $p\nmid \sigma (m)$. Thus, $r\mid m$, and so $r>(\log _2x)^2$. We conclude that if $2<r\le (\log _2x)^2$ and $r\mid s(n)$, then $r\nmid s(2^kpm)$. We now restrict the $q$’s that are available to us by removing for each odd prime $r\le (\log _2x)^2$ a single coprime residue class that will ensure that $r\nmid s(n)$. By another application of Brun’s sieve, this cuts down the number of choices for $q$ by a factor proportional to $\log _3x$. For a surviving prime $q$, let

$$f_1(q)=\sum _{\substack{2<r<x^{1/4}\\r\nmid m\\r\mid s(2^kpmq)}}\frac{1}{r}.$$

If $r \mid s(2^kpmq)$ and $r\nmid m$, then as we have seen, $q$ is in a fixed residue class mod $r$. Using that $q$ also avoids one residue class modulo each prime not exceeding $(\log _2{x})^2$, the Brun–Titchmarsh inequality implies that the average value of $f_1(q)$, over surviving primes $q$, is $\ll 1/((\log _2x)^2 \log _3{x})$. Keeping 2.4 in mind, we conclude that there are $\gg \frac{\pi (x/2^k pm)}{\log _3{x}} \gg \frac{x}{2^kpm \log {x}\log _3{x}}$ values of $q$ for which

$$\begin{equation} \sum _{\substack{r>2\\r\mid s(2^kpmq)}}\frac{1}{r}\le \frac{1}{(\log _2x)^2}. {\tag{2.5}} \end{equation}$$

We finally note that for $m,q$ chosen as above, we have $2^{k+1}\mid \sigma (2^kpmq)$, so that $2^k\nobreakspace \parallel\nobreakspace s(2^kpmq)$. Hence, $s(2^kpmq)/2^k$ has only odd prime factors. From 2.5, we conclude that $s(2^kpmq)$ is deficient. The theorem then follows with the estimate:

$$\begin{align*} \sum _p\sum _m\sum _q1&\gg \sum _p\sum _m\frac{x}{2^kpm\log x\log _3x}\gg \sum _p\frac{x}{2^kp(\log _3x)^2} \\ &\gg \frac{x}{2^k(\log _3x)^3}\gg \frac{x}{\log _2x(\log _3x)^3}, \end{align*}$$

where we have used 2.3.

■

Proof of Theorem 1.3.

We take $k$ as the least integer with $2^k> 10\log _2 x$. We consider numbers $n=2^kmqr\le x$ with $q,r$ primes, $x^{1/8}<m\le x^{1/4}$, $x^{1/4}<q\le x^{1/3}$, and $r> x^{1/3}$. As in the last proof, we impose some conditions on $m$. Namely, we insist that $m$ satisfy all of

(i$'$)

$m$ has no prime factors below $(\log _2x)^2$,

(ii$'$)

$2^k\mid \sigma (m)$,

(iii$'$)

2.4 holds,

(iv$'$)

for $I:=[2^k,2^{k+1}-1)$, we have $\sum _{p \in I,\,p \nmid \sigma (m)} \frac{1}{p} >\frac{1}{10} \frac{1}{\log _3{x}}$.

We will show we can construct a collection of such $m$ that satisfies

$$\begin{equation} \sum _{m} \frac{1}{m} \gg \frac{\log {x}}{\log _3{x}}. {\tag{2.6}} \end{equation}$$

It will turn out that the most stringent restriction is the first one.

By an elementary sieve, those $m \in (x^{1/8},x^{1/4}]$ satisfying (i$'$) have

$$\begin{equation} \sum _{m}\frac{1}{m} \sim \frac{1}{16\mathrm{e}^{\gamma }} \frac{\log {x}}{\log _3{x}}, {\tag{2.7}} \end{equation}$$

as $x\to \infty$. By arguments seen above, restricting $m$ further to satisfy (ii$'$) changes the value of $\sum _{m}\frac{1}{m}$ by $O(\log {x}/\log _2{x})$, and restricting $m$ to satisfy (iii$'$) affects the sum only by $O(\log {x}/(\log _3{x})^2)$. Hence, 2.7 still holds if $m$ is restricted to satisfy all of (i$'$)–(iii$'$).

We now turn to (iv$'$). Changing $\sum _{m}\frac{1}{m}$ by $O(\log {x}/\sqrt {\log _2{x}})$, we can assume that $m$ is not divisible by any proper prime power exceeding $5\log _2{x}$. If $p\in I$ and $p\mid \sigma (m)$, then there is a prime power $\ell ^\alpha \parallel m$ with $p\mid \sigma (\ell ^\alpha )$; since $\ell ^{\alpha } > p/2 > 5\log _2{x}$, it follows that $\alpha =1$. Let

$$\begin{equation*} f_2(m) = \sum _{\substack{p \in I \\ p \mid \sigma (m)}} \frac{1}{p}. \end{equation*}$$

Using that $m \le x^{1/4}$ and that $m$ is free of prime factors up to $(\log _2{x})^2$, we see that as $x\to \infty$,

$$\begin{align*} \sum _{m} \frac{1}{m} f_2(m) &\le \sum _{p \in I} \frac{1}{p} \sum _{\ell \, \equiv \, 1\kern -5pt\pmod {p}}\nobreakspace \sum _{m:\nobreakspace \ell \mid m}\frac{1}{m} \\ &\le \left(\frac{1}{8}+o(1)\right) \frac{\log {x}}{\log _3{x}} \cdot \sum _{p \in I} \frac{1}{p} \sum _{\substack{\ell \le x \\ \ell \, \equiv \, 1\kern -5pt\pmod {p}}} \frac{1}{\ell }. \end{align*}$$

From 36, Theorem 1 and Remark 1, the final sum on $\ell$ is at most $(1+o(1)) \frac{\log _2{x}}{p}$, as $x\to \infty$, uniformly for $p \in I$. Inserting this estimate above,

$$\begin{equation*} \sum _{m} \frac{1}{m} f_2(m) \le \left(\frac{1}{8}+o(1)\right) \frac{\log {x}}{\log _3{x}} \log _2{x} \cdot \sum _{p \in I}\frac{1}{p^2} \le \left(\frac{1}{80}+o(1)\right) \frac{\log {x}}{(\log _3{x})^2}. \end{equation*}$$

Hence, the contribution to the left-hand side of 2.7 from those values of $m$ with $f_2(m) \ge \frac{1}{2 \log _3{x}}$ is at most $(\frac{1}{40}+o(1))\frac{\log {x}}{\log _3{x}}$. Since $\frac{1}{16\mathrm{e}^{\gamma }} - \frac{1}{40} > \frac{1}{100}$, after discarding these $m$ we may still assert 2.6. Moreover, since $\sum _{p \in I} \frac{1}{p} \sim \frac{\log {2}}{\log _3{x}}$ and $\log {2} - \frac{1}{2} > \frac{1}{10}$, we have

$$\begin{equation*} \sum _{\substack{p \in I \\ p \nmid \sigma (m)}} \frac{1}{p} > \frac{1}{10} \frac{1}{\log _3{x}} \end{equation*}$$

for all remaining $m$ (and all large $x$).

Note that for any choice of distinct primes $q,r$ greater than $m$, the number $2^kmqr$ is deficient; indeed, for large $x$,

$$\begin{align*} \frac{\sigma (2^k mqr)}{2^k mqr} &< 2\left(1-\frac{1}{2^{k+1}}\right) \left(\prod _{p \mid m} \left(1 + \frac{1}{p-1}\right)\right) \left(1 + \frac{1}{x^{1/8}}\right)^2 \\ &< 2\left(1-\frac{1}{40\log _2 x}\right) \left(1+O\left(\frac{1}{(\log _2{x})^2}\right)\right) \left(1+ O\left(\frac{1}{x^{1/8}}\right)\right), \end{align*}$$

and this is $< 2(1-\frac{1}{80\log _2{x}}) < 2$. We shall show that with some mild restrictions on $q,r$, we will have $s(2^kmqr)$ abundant. For $m$ satisfying the above restrictions, let $S(m)$ be the set of primes $p\in I$ with $p\nmid \sigma (m)$ and let $S_m$ be the product of the members of $S(m)$.

We next consider primes $q\in (x^{1/4},x^{1/3}]$. They are chosen with the requirements that both $q+1$ and $s(2^kmq)$ are coprime to $S_m$. We have $s(2^kmq)=qs(2^km)+\sigma (2^km)$. By our choices of $k,m$, we have $\sigma (2^km)$ coprime to $S_m$. So for a prime $p\mid \gcd (s(2^kmq),S_m)$, $q$ is in a particular residue class mod $p$. Similarly this holds too for $p\mid q+1$. Thus, the density of the primes $q$ which avoid these classes is at least

$$\begin{equation*} \prod _{p\mid S_m}\frac{p-3}{p-1}\sim 1,\nobreakspace \text{ as }\nobreakspace x\to \infty . \end{equation*}$$

So, almost all of the primes $q\in (x^{1/4},x^{1/3}]$ may be used, and for these primes $q$, we have $\gcd (s(2^kmq),S_m)=1$ and $\gcd (q+1,S_m)=1$.

We now choose primes $r\in (x^{1/3},x/(2^kmq)]$ with $\gcd (s(2^kmqr),S_m)>1$. For such a prime $r$, $s(2^kmqr)$ is abundant. Let $p\mid S_m$. Note that for any prime $r\nmid 2^kmq$, we have $s(2^kmqr)=rs(2^kmq)+\sigma (2^kmq)$. Further, we have $p\nmid s(2^kmq)$ and $p\nmid \sigma (2^kmq)$. By the prime number theorem for progressions, the fraction of $r$ with $p\mid s(2^kmqr)$ is asymptotically $1/(p-1)$. Similarly, if $pp'\mid S_m$, the fraction of choices for $r$ with $pp'\mid s(2^kmqr)$ is asymptotically $O(1/pp')$. Since

$$\begin{equation*} \sum _{p\mid S_m}\frac{1}{p-1}\gg \frac{1}{\log _3x},\quad \sum _{pp'\mid S_m}\frac{1}{pp'}\ll \frac{1}{(\log _3x)^2}, \end{equation*}$$

we have that the proportion of primes $r$ with $\gcd (s(2^kmqr),S_m)>1$ is $\gg 1/\log _3x$.

Putting these thoughts together, we have that the number of choices for $m,q,r$ is

$$\begin{equation*} \sum _m\sum _q\sum _r1\gg \sum _m\sum _q\frac{x}{2^kmq\log x\log _3x} \gg \sum _m\frac{x}{2^km\log x\log _3x} \gg \frac{x}{2^k(\log _3x)^2}. \end{equation*}$$

Since $2^k\ll \log _2 x$, this completes the proof of the theorem.

■

3. The density of nonaliquot numbers

3.1. A heuristic argument

For a positive integer $y$, let

$$A_y=\mathrm{lcm}[1,2,\dots ,y].$$

For a positive integer $a\mid A_y$, let

$$T_a=\{n:\gcd (n,A_y)=a\},$$

and let $T_a(x)$ denote the set of members of $T_a\cap [1,x]$. We assume that $s$ maps $T_a$ to $T_a$ for each $a\mid A_y$. This is asymptotically true if $n>{\mathrm{e}}^{{\mathrm{e}}^y}$ and $y\to \infty$. Further, we assume that for $n\in T_a$ we have $\sigma (n)/n\approx \sigma (a)/a$. This is asymptotically true up to sets of vanishing density as $y\to \infty$. We assume in addition that $s$ is a random map subject to the prior assumptions.

Now suppose $a$ is even. If $s(m)\in T_a(x)$, then $m\in T_a$ and $m\le x/(\sigma (a)/a-1)=(a/s(a))x$, so that $m\in T_a((a/s(a))x)$. The probability that an integer $n\in T_a(x)$ is not in the range of $s$ is about

$$\left(1-\frac{1}{|T_a(x)|}\right)^{|T_a((a/s(a))x)|}.$$

Now $|T_a(x)|\sim (\varphi (A_y)/aA_y)x$, so the above probability is asymptotically

$$\exp \left(-\frac{a}{s(a)}\right).$$

We thus would have that the density $\Delta$ of even numbers not in the range of $s$ is

$$\begin{equation} \Delta =\lim _{y\to \infty }\frac{\varphi (A_y)}{A_y} \sideset{}{^{*}}{\sum }_{a\mid A_y}\frac{1}{a}{\mathrm{e}}^{-a/s(a)}, {\tag{3.1}} \end{equation}$$

where the $*$ indicates that $a$ runs over even numbers. Since almost all odd numbers are in the image of $s$, $\Delta$ is also the density of nonaliquot numbers.

We now prove that the limit 3.1 exists. Let

$$P_y=\frac{\varphi (A_y)}{A_y}=\prod _{p\le y}\left(1-\frac{1}{p}\right), \quad S_y={\sideset{}{^{*}}{\sum }_{P(a)\le y}}\,\frac{1}{a}\mathrm{e}^{-a/s(a)}, \quad S_y'={\sideset{}{^{*}}{\sum }_{a\mid A_y}}\,\frac{1}{a}\mathrm{e}^{-a/s(a)}.$$

Note that $S_y'\le S_y$. The difference comes from those $a$ with $P(a)\le y$ and $a\nmid A_y$. Such a number $a$ is divisible by $p^k$ for some prime power $p^k > y$ and $p\le y$. Writing $a= p^k a'$, we have

$$\begin{equation} {\sideset{}{^{*}}{\sum }_{\substack{P(a) \le y \\ a\nmid A_y}}}\, \frac{1}{a}{\mathrm{e}}^{-a/s(a)} \le \sum _{p \le y}\sum _{k > \frac{\log {y}}{\log {p}}} \frac{1}{p^k} \sum _{P(a') \le y} \frac{1}{a'} \ll \log {y} \sum _{p \le y} \frac{1}{y} \ll 1. {\tag{3.2}} \end{equation}$$

Since, by Mertens’ theorem, $P_y\sim \mathrm{e}^{-\gamma }/\log y$ as $y\to \infty$, we have

$$P_yS_y-P_yS_y'\ll \frac{1}{\log y}.$$

Thus the limit in 3.1 exists if and only if $\lim _{y\to \infty }P_yS_y$ exists, in which case this latter limit is also $\Delta$.

For a prime $q$, we have $P_q=P_{q-1}(1-\frac{1}{q})$ and, for $q > 2$,

$$S_q-S_{q-1}={\sideset{}{^{*}}{\sum }_{P(a) < q}}\sum _{i\ge 1}\frac{1}{aq^i}{\mathrm{e}}^{-aq^i/s(aq^i)} >{\sideset{}{^{*}}{\sum }_{P(a) < q}}\sum _{i\ge 1}\frac{1}{aq^i}{\mathrm{e}}^{-a/s(a)}=\frac{1}{q-1}S_{q-1}.$$

Thus,

$$P_qS_q>P_{q-1}\left(1-\frac{1}{q}\right)S_{q-1}\left(1+\frac{1}{q-1}\right) =P_{q-1}S_{q-1}.$$

Since $P_yS_y$ is always at most $\frac{1}{2}$, it follows that the limit in 3.1 exists and

$$\begin{equation} \Delta =\lim _{y\to \infty }\frac{{\mathrm{e}}^{-\gamma }}{\log y}\, {\sideset{}{^{*}}{\sum }_{a\mid A_y}}\, \frac{1}{a}{\mathrm{e}}^{-a/s(a)} =\lim _{y\to \infty }\frac{{\mathrm{e}}^{-\gamma }}{\log y}\, {\sideset{}{^{*}}{\sum }_{P(a)\le y}}\, \frac{1}{a}{\mathrm{e}}^{-a/s(a)}. {\tag{3.3}} \end{equation}$$

We would like to compute a numerical approximation to $\Delta$, and it may seem that the first expression in 3.3 is more easily computed than the second, since it involves a finite sum while the latter involves an infinite sum. However, we claim the infinite sum can be replaced with the sum over $a\le y$, while changing ${\mathrm{e}}^{-\gamma }$ to 1. That is,

$$\begin{equation} \Delta =\lim _{y\to \infty }\frac{1}{\log y} {\sideset{}{^{*}}{\sum }_{a\le y}}\,\frac{1}{a}{\mathrm{e}}^{-a/s(a)}. {\tag{3.4}} \end{equation}$$

The equation 3.4 may be proved as follows: Introduce a parameter $z\ge 2$, which will eventually be chosen as a slow-growing function of $y$. Define $h_z(n) = \sum _{d \mid n,\nobreakspace 1<d\le z} 1/d$. For even $a$,

$$\begin{equation*} 0 \le {\mathrm{e}}^{-\frac{a}{s(a)}} - {\mathrm{e}}^{-\frac{1}{h_{z}(a)}} ={\mathrm{e}}^{-\frac{a}{s(a)}} \left(1-{\mathrm{e}}^{\frac{1}{s(a)/a} -\frac{1}{h_z(a)}}\right) \ll {\mathrm{e}}^{-\frac{a}{s(a)}} \left(\frac{s(a)}{a}-h_z(a)\right). \end{equation*}$$

Thus,

$$\begin{align} 0 \le {\sideset{}{^{*}}{\sum }_{a \le y}}\, \frac{1}{a} {\mathrm{e}}^{-\frac{a}{s(a)}} - {\sideset{}{^{*}}{\sum }_{a \le y}}\, \frac{1}{a} {\mathrm{e}}^{-\frac{1}{h_{z}(a)}} &\ll {\sideset{}{^{*}}{\sum }_{a\le y}}\, \frac{1}{a} {\mathrm{e}}^{-\frac{a}{s(a)}} \sum _{\substack{d \mid a \\ d>z}} \frac{1}{d} \\ &\le \sum _{d > z} \frac{1}{d} {\sideset{}{^{*}}{\sum }_{\substack{a \le y \\ d \mid a}}}\, \frac{1}{a} \le \log {y} \sum _{d > z}\frac{1}{d^2} \ll \frac{1}{z}\log {y}.{\tag{3.5}} \end{align}$$

A nearly identical computation gives

$$\begin{equation} {\sideset{}{^{*}}{\sum }_{P(a) \le y}}\, \frac{1}{a} {\mathrm{e}}^{-a/s(a)} -{\sideset{}{^{*}}{\sum }_{P(a) \le y}}\, \frac{1}{a} {\mathrm{e}}^{-\frac{1}{h_{z}(a)}} \ll \frac{1}{z}\log {y}. {\tag{3.6}} \end{equation}$$

Note that $h_z(a) = h_z(\gcd (a,A_z))$, and that when $a$ is even, $d=\gcd (a,A_z)$ is also even. Hence, for all large $y$ we have

$$\begin{align*} {\sideset{}{^{*}}{\sum }_{P(a) \le y}}\, \frac{1}{a} {\mathrm{e}}^{-\frac{1}{h_z(a)}} & =\sum _{\substack{d\mid A_z\\2\mid d}}\sum _{\substack{P(a)\le y\\\gcd (a,A_z)=d}} \frac{1}{a}\mathrm{e}^{-\frac{1}{h_z(d)}} = \sum _{\substack{d \mid A_z\\2 \mid d}} {\mathrm{e}}^{-\frac{1}{h_z(d)}}{\sum _{\substack{P(a) \le y \\ d\mid a}}}\, \frac{1}{a} \sum _{\substack{j \mid a/d \\ j \mid A_z/d}} \mu (j) \\ &= \sum _{\substack{dj\mid A_z\\2\mid d}}\mu (j) {\mathrm{e}}^{-\frac{1}{h_z(d)}} {\sum _{\substack{P(a) \le y \\ dj \mid a}}}\, \frac{1}{a} = \sum _{\substack{dj\mid A_z \\ 2\mid d}}\frac{\mu (j) {\mathrm{e}}^{-\frac{1}{h_z(d)}}}{dj} {\sum _{P(a) \le y}}\, \frac{1}{a}. \end{align*}$$

Again almost identically, we have

$$\sideset{}{^{*}}{\sum }_{a\le y}\frac{1}{a}\mathrm{e}^{-\frac{1}{h_z(d)}}= \sum _{\substack{dj\mid A_z\\2\mid d}}\frac{\mu (j)}{dj}\mathrm{e}^{-\frac{1}{h_z(d)}} \sum _{a\le y/dj}\frac{1}{a}.$$

By Mertens’ theorem (with the elementary error estimate shown in 43, Theorem 10, p. 17),

$$\begin{equation*} \frac{1}{\log {y}}\sum _{P(a) \le y} \frac{1}{a} = \frac{{\mathrm{e}}^{\gamma }}{\log {y}} \sum _{a \le y} \frac{1}{a} + O\left(\frac{1}{\log {y}}\right) = \frac{{\mathrm{e}}^{\gamma }}{\log {y}} \sum _{a \le y/dj} \frac{1}{a} + O\left(\frac{\log (dj)+1}{\log {y}}\right). \end{equation*}$$

Making this substitution, we find that

$$\begin{equation} \Bigg |\frac{\mathrm{e}^{-\gamma }}{\log y}\sideset{}{^{*}}{\sum }_{P(a)\le y}\frac{1}{a}\mathrm{e}^{-\frac{1}{h_z(a)}} -\frac{1}{\log y}\sideset{}{^{*}}{\sum }_{a\le y}\frac{1}{a}\mathrm{e}^{-\frac{1}{h_z(a)}}\Bigg | \ll \frac{1}{\log y}\sum _{dj\mid A_z}\frac{\log dj}{dj} \ll \frac{(\log z)^3}{\log y}. {\tag{3.7}} \end{equation}$$

By choosing $z=\exp ((\log y)^{1/4})$, say, from 3.2, 3.5, 3.6, and 3.7, we see that

$$\Bigg |\frac{{\mathrm{e}}^{-\gamma }}{\log y}\sideset{}{^{*}}{\sum }_{a\mid A_y} \frac{1}{a}{\mathrm{e}}^{-a/s(a)} - \frac{1}{\log y}\sideset{}{^{*}}{\sum }_{a\le y} \frac{1}{a}{\mathrm{e}}^{-a/s(a)}\Bigg | \ll \frac{1}{(\log y)^{1/4}}.$$

Thus, 3.4 follows. This completes the heuristic justification of Conjecture 1.4.

3.2. Computations

The following strategy was used to construct Table 1. Explicit computations on Goldbach’s conjecture have shown that every even number in $[8,4\cdot 10^{18}]$ is a sum of two distinct primes $p$ and $q$ (see 31). Hence, $5$ is the only odd nonaliquot number up to $10^{18}$. In 39, §5, an algorithm is described that enumerates the elements of $s(\mathbf{N}) \cap [1,N]$ in time $\tilde{O}(N)$. We ran the algorithm to $N=10^{10}$. We made one modification, necessitated by memory constraints: Instead of using a 0-1 array to record which numbers had appeared so far, the even numbers in the range of $s$ were written to disk as they were found by the algorithm, and sorted later with the GNU sort utility. The final data file required 36.1 GB.

On the computation of an approximation for $\Delta$, this is straightforward using 3.4 for large values of $y$. Note that $\Delta$ is effectively computable, since the above calculations show that for each fixed integral value of $z\ge 2$,

$$\lim _{y\to \infty }\frac{\mathrm{e}^{-\gamma }}{\log y} \sum _{\substack{dj\mid A_z\\2\mid d}}\frac{\mu (j)}{dj}\mathrm{e}^{-\frac{1}{h_z(d)}}\sum _{P(a)\le y}\frac{1}{a} = \sum _{\substack{dj\mid A_z\\2\mid d}}\frac{\mu (j)}{dj}\mathrm{e}^{-\frac{1}{h_z(d)}}$$

is within $4/z$ of $\Delta$. We have not used this approach, but we record some intermediate values for the expression in 3.4 at $y=10^j$ and $2\cdot 10^j$ for $6\le j\le 10$:

$$\begin{align*} &10^6\kern -2pt: 0.166923,\nobreakspace 2{\cdot }10^6\kern -2pt: 0.167484,\nobreakspace 10^7\kern -2pt: 0.168599,\nobreakspace 2{\cdot }10^7\kern -2pt: 0.169014,\nobreakspace 10^8\kern -2pt: 0.169857,\\ &2{\cdot }10^8\kern -2pt: 0.170176,\nobreakspace 10^9\kern -2pt: 0.170834,\nobreakspace 2{\cdot }10^9\kern -2pt: 0.171088,\nobreakspace 10^{10}\kern -2pt: 0.171617,\nobreakspace 2{\cdot }10^{10}\kern -2pt:\,0.171822. \end{align*}$$

3.3. A $\varphi$ analogue

Let $s_\varphi (n)=n-\varphi (n)$. As with $s(n)$, partial results on Goldbach’s conjecture imply that the range of $s_\varphi (\cdot )$ contains all odd numbers but for a set of asymptotic density 0. Little is known about even values. In 19 Erdős asks if a positive proportion of even numbers are of the form $s_\varphi (n)$ and if a positive proportion of even numbers are not of the form $s_\varphi (n)$. The proof in 30 does give a positive proportion of evens that are of the form $s_\varphi (n)$, but the even numbers not of this form remain an enigma. However, as with $s(n)$ the problem is amenable to calculation and heuristics. Let $U_\varphi (x)$ denote the number of integers in $[1,x]$ not of the form $s_\varphi (n)$. By an analogous algorithm from 39, we have extended the calculations of that paper 100-fold; see Table 4. The data file had 42.1 GB. (This file is larger than the one with nonaliquots since there are more even numbers $n$ with $s_\varphi (n)\le 10^{10}$ than there are with $s(n)\le 10^{10}$.)

The conjectural density is

$$\begin{equation} \Delta _\varphi :=\lim _{y\to \infty }\frac{1}{\log y}{\sideset{}{^{*}}{\sum }_{a\le y}}\,\frac{1}{a} \mathrm{e}^{-a/s_\varphi (a)}. {\tag{3.8}} \end{equation}$$

At $y=2\cdot 10^{10}$ this expression rounds to $0.090595$. It is difficult to say if the actual counts are supportive of the conjectural density $\Delta _\varphi$; the evidence is somewhat less compelling than with the nonaliquots. At least the count densities seem to have peaked and are now slowly descending, perhaps to the limit $\Delta _\varphi$. With both the nonaliquots and the $\varphi$ analogues, the heuristic is very much an “at infinity” type of argument, while the counts are definitely very finite. It might be of some interest to try to do a statistical sample of random numbers that are much larger than our exhaustive counts, but it is not clear how one would decide if a given very large number $n$ is of the required form.

Here are the intermediate calculations of the expression in 3.8 for various values of $y$:

$$\begin{align*} &10^6\kern -2pt: 0.089193,\nobreakspace 2{\cdot }10^6\kern -2pt: 0.089353,\nobreakspace 10^7\kern -2pt: 0.089673,\nobreakspace 2{\cdot }10^7\kern -2pt: 0.089791,\nobreakspace 10^8\kern -2pt: 0.090033,\\ &2{\cdot }10^8\kern -2pt: 0.090124,\nobreakspace 10^9\kern -2pt: 0.090312,\nobreakspace 2{\cdot }10^9\kern -2pt: 0.090385,\nobreakspace 10^{10}\kern -2pt: 0.090536,\nobreakspace 2{\cdot }10^{10}\kern -2pt:\,0.090595. \end{align*}$$

4. Primitive friendly pairs

We begin by collecting some results needed for the proof of Theorem 1.5. The following lemma says that we have a strong bound on the number of solutions to $\frac{\sigma (n)}{n}=\alpha$, even if we specify only the denominator of $\alpha$. For the proof of this result, in a more precise form, see 32, Theorem 4.1.

Lemma 4.1.

The number of $n \le x$ for which $\sigma (n)/n$ can be written as a fraction with a given denominator $d$ is at most $x^{o(1)}$, as $x\to \infty$, uniformly in $d \le x$.

The next lemma is implicit in the proof of 23, Theorem 11; for an explicit statement and proof, see 32, Lemma 4.2.

Lemma 4.2.

Let $m$ be an integer in $[1,x]$. The number of integers $n \in [1, x]$ for which $\mathrm{rad}(n) \mid m$ is $x^{o(1)}$, as $x\to \infty$, uniformly in $m$.

The next result, which was inspired by Erdős’s method of proof in 16, appears as 35, Lemma 3.1.

Lemma 4.3.

Given a natural number $m$, the following algorithm outputs a unitary divisor $a$ of $m$ with $\gcd (a,\sigma (a))=1$. Moreover, at most $x^{o(1)}$ inputs $m \leq x$ correspond to the same output $a$, as $x\to \infty$.

Algorithm A.

Proof of Theorem 1.5.

Suppose that $n$ and $n'$ form a primitive friendly pair contained in $[1,x]$. Write $n=N_1 N_2$, where $N_1$ is squarefree, $N_2$ is squarefull, and $\gcd (N_1, N_2)=1$. Define $n_2$ and $n_3$ by the equation $N_2 = n_2 n_3$, where $n_2$ is the output of Algorithm A when $m=N_2$. Note that $n_2$ and $n_3$ are coprime squarefull integers, since $n_2$ is a unitary divisor of $N_2$. Write

$$\begin{equation*} \frac{\sigma (n)}{n} = \frac{\sigma (n')}{n'} = \frac{A}{B}, \quad \text{where} \quad \gcd (A,B)=1, \end{equation*}$$

and let $U=\mathrm{rad}(\mathrm{gcud}(B,n_2))$. Define $N_1', N_2', n_2', n_3', U'$ analogously, but now with reference to $n'$ instead of $n$. Since $\mathrm{gcud}(n_2,n_2')=1$, it follows that $\gcd (U,U')=1$. With $L= \lceil \log {x}\rceil$, choose $\theta _1, \theta _2, \theta _3, \delta \in \{\frac{1}{L}, \frac{2}{L}, \dots , \frac{L-1}{L}, 1\}$ for which

$$\begin{equation*} N_1 \in [\mathrm{e}^{-1} x^{\theta _1}, x^{\theta _1}], \quad n_2 \in [\mathrm{e}^{-1}x^{\theta _2}, x^{\theta _2}], \quad n_3 \in [\mathrm{e}^{-1} x^{\theta _3}, x^{\theta _3}],\text{ and } U \in [\mathrm{e}^{-1}x^{\delta }, x^{\delta }]. \end{equation*}$$

Define $\theta _1', \theta _2', \theta _3', \delta '$ analogously. Finally, choose $\theta \in \{\frac{1}{L}, \frac{2}{L}, \dots , \frac{L-1}{L}, 1\}$ with

$$\begin{equation*} B \in [\mathrm{e}^{-1} x^{\theta }, x^{\theta }]. \end{equation*}$$

So, running over all of the $L^9=x^{o(1)}$ possibilities for the $\theta _i$, the $\theta _i'$, $\delta$, $\delta '$, and $\delta _0$, we cover all possibilities for $n,n'$. Thus, it is enough to prove that the number of pairs $n, n'$ corresponding to a given choice of these variables is bounded by $x^{1/2+o(1)}$, as $x\to \infty$. We will establish four upper bounds on the number of these pairs $n, n'$. The theorem will follow by combining these upper bounds.

Our first upper bound uses that

$$\begin{equation} B^2\mid n_2 n_3 n_2' n_3'. {\tag{4.1}} \end{equation}$$

To prove this, write $B = B_1 B_2$, where $B_1$ is squarefree, $B_2$ is squarefull, and $\gcd (B_1, B_2)=1$. Since $B$ divides $n$ and $n'$, $B_2 \mid n_2 n_3$ and $B_2 \mid n_2' n_3'$, so that $B_2^2 \mid n_2 n_3 n_2' n_3'$. Now take a prime $p \mid B_1$. Since $n$ and $n'$ have no common unitary divisor, $p$ cannot exactly divide both $n$ and $n'$. So either $p^2 \mid n_2 n_3$ or $p^2 \mid n_2' n_3'$. Hence, $B_1^2\mid n_2 n_3 n_2' n_3'$ and 4.1 holds. By Lemma 4.3, given $n_2$ there are only $x^{o(1)}$ possibilities for $n_3$. Similarly, $n_2'$ determines $n_3'$ in at most $x^{o(1)}$ ways. Thus, $n_2$ and $n_2'$ determine the product $n_2 n_3 n_2' n_3'$ up to $x^{o(1)}$ possibilities. Now 4.1, along with the maximal order of the divisor function, shows that $n_2$ and $n_2'$ determine $B$ up to $x^{o(1)}$ possibilities. Invoking Lemma 4.1, $n_2, n_2'$ determine the pair $n, n'$ in at most $x^{o(1)}$ ways. Since the number of squarefull numbers in $[1,t]$ is $O(t^{1/2})$, the number of pairs is at most

$$\begin{equation} x^{\theta _2/2 + \theta _2'/2 + o(1)}, {\tag{4.2}} \end{equation}$$

as $x\to \infty$.

For a second upper bound, expanding the equation $\frac{A}{B} = \frac{\sigma (N)}{N}$, we find that $B \sigma (N_1) \sigma (n_2) \sigma (n_3) = A N_1 n_2 n_3$. Since $\gcd (n_2,\sigma (n_2))=1$,

$$\begin{equation*} n_2 \mid B \sigma (N_1) \sigma (n_3), \quad \text{so that}\quad \mathrm{rad}(n_2) \mid U \cdot \sigma (N_1) \sigma (n_3). \end{equation*}$$

By Lemma 4.2, the number of possibilities for $n=N_1 n_2 n_3$ is at most

$$\begin{equation} x^{\delta +\theta _1+\theta _3/2+o(1)}. {\tag{4.3}} \end{equation}$$

By Wirsing’s theorem (or Lemma 4.1), this is also a bound on the number of possibilities for the pair $n, n'$. A symmetric argument gives our third upper bound,

$$\begin{equation} x^{\delta '+\theta _1'+\theta _3'/2+o(1)}. {\tag{4.4}} \end{equation}$$

To prove the fourth upper bound, note that since $\gcd (U,U')=1$, we have $U^2U'^2\mid B$. Consequently, the number of possibilities for $B$ is

$$\begin{equation*} \ll \sum _{\substack{u_1\ge \mathrm{e}^{-1} x^{\delta }\\ u_2 \ge \mathrm{e}^{-1} x^{\delta '} }} \frac{x^{\theta }}{u_1^2 u_2^2 } \ll x^{\theta -\delta -\delta '}. \end{equation*}$$

By Lemma 4.1, the number of possibilities for the pair $n, n'$ is at most

$$\begin{equation} x^{\theta -\delta -\delta ' + o(1)}.{\tag{4.5}} \end{equation}$$

Taking the geometric mean of the four upper bounds 4.2, 4.3, 4.4, and 4.5, the number of possibilities for the pair $n, n'$ does not exceed

$$\begin{equation} x^{\frac{1}{4}(\theta _1 + \theta _1' + \frac{1}{2}(\theta _2 + \theta _2' + \theta _3 + \theta _3') + \theta ) + o(1)}. {\tag{4.6}} \end{equation}$$

Since $n = N_1 n_2 n_3 \le x$, we have $\theta _1 \le 1-\theta _2 - \theta _3 + o(1)$; similarly, $\theta _1' \le 1-\theta _2' - \theta _3' + o(1)$. From 4.1, $2\theta \le \theta _2 + \theta _3 + \theta _2' + \theta _3'+o(1)$. Substituting these bounds for $\theta _1, \theta _1'$ and $\theta$ into 4.6 gives a final upper bound of $x^{\frac{1}{2}+o(1)}$, as $x\to \infty$.

■

4.1. Computations

To compile Table 2, for each $n \le 10^{L}$, we found all solutions $m \le 10^{L}$ with $\frac{\sigma (n)}{n} = \frac{\sigma (m)}{m}$, recording only those solutions $m$ with $\mathrm{gcud}(m,n)=1$. To find the values of $m$, we used the gp script solveBA of Michel Marcus (see 42), which was based on an earlier program by Jan Munch Pedersen. The script solveBA uses a recursive algorithm to find all solutions $n$ up to a given limit satisfying an equation of the form $\frac{\sigma (n)}{n} = \frac{A}{B}$. The values of $\mathrm{gcud}(m,n)$ were computed using Algorithm B3 below.

Algorithm B1.

Algorithm B2.

Algorithm B3.

5. The distribution function for $F(n;x)$

Define a friendly $k$-set as a set of $k$ distinct integers all of which share the same value of $\frac{\sigma (n)}{n}$, and call such a set primitive if there is no $d>1$ that is a unitary divisor of each element. The proof of Theorem 1.6 will use the following crude upper bound on the count of primitive friendly $k$-sets.

Lemma 5.1.

Fix $k\ge 2$. The number of primitive friendly $k$-sets contained in $[1,x]$ is at most $x^{1-\frac{1}{k+1}+o(1)}$, as $x\to \infty$.

When $k=2$, Lemma 5.1 gives an upper bound of $x^{2/3+o(1)}$, which is inferior to the result of Theorem 1.5. However, the proof of Lemma 5.1 is substantially simpler.

Proof.

List the elements of the set as $n_1, \dots , n_k$. Write the common value of $\frac{\sigma (n_i)}{n_i}$ as $\frac{A}{B}$ in lowest terms. If $\mathrm{rad}(B) \le x^{1-\frac{1}{k+1}}$, then there are at most $x^{1-\frac{1}{k+1}+o(1)}$ possible values of $B$, by Lemma 4.2, and so also at most $x^{1-\frac{1}{k+1}+o(1)}$ possibilities for the $k$-set, by Lemma 4.1. So we suppose that $\mathrm{rad}(B) > x^{1-\frac{1}{k+1}}$.

Let $p$ be a prime dividing $B$. Then $p$ divides each $n_i$. Since $n_1, \dots , n_k$ is primitive friendly, it is impossible for $p$ to exactly divide each $n_i$. Thus, if $N=n_1\cdots n_k$, then $\mathrm{rad}(B)^{k+1} \mid N$. Hence, the number of possibilities for the integer $N \le x^k$ is at most

$$\begin{equation*} \sum _{r > x^{1-\frac{1}{k+1}}} \frac{x^k}{r^{k+1}} \ll x^{1-\frac{1}{k+1}}. \end{equation*}$$

From the maximal order of the $k$-fold divisor function, $N$ determines the set $\{n_1,\dots , n_k\}$ in at most $x^{o(1)}$ ways. The result follows.

■

Proof of Theorem 1.6.

We may assume $k \ge 1$, since when $k=0$ the asymptotic claimed in the theorem holds with $\alpha _0=1$. We begin by placing each primitive $(k+1)$-set in increasing order, $n_0 < n_1 < \dots < n_k$. We then list the primitive $(k+1)$-sets in increasing order of $n_k$, breaking ties arbitrarily. Say the $j$th tuple is labeled as $n_{0,j}, \dots , n_{k,j}$. Put

$$\begin{equation*} \mathscr{M}_{i,j}(x):= \{d n_{i,j}: 1\le d \le x/n_{k,j}\text{ and }\gcd (d,\prod _{\ell =0}^{k} n_{\ell ,j})=1 \}, \end{equation*}$$

and observe that a natural number $m \le x$ has at least $k$ friends in $[1,x]$ if and only if $m$ belongs to one of the sets $\mathscr{M}_{i,j}(x)$. For each $J \ge 1$, put

$$\begin{equation*} \alpha _k^{(J)} = \lim _{x\to \infty } \frac{1}{x} \cdot \#\bigcup _{\substack{1 \le j \le J \\ 0 \le i \le k}} \mathscr{M}_{i,j}(x). \end{equation*}$$

The existence of the limit follows from inclusion–exclusion. (Each finite intersection of the sets $\mathscr{M}_{i,j}(x)$ can be described as the set of numbers not exceeding a certain constant multiple of $x$ that satisfy certain congruence conditions.) The $\alpha _k^{(J)}$ are weakly increasing in $J$ and bounded by $1$; thus, it makes sense to set

$$\begin{equation*} \alpha _k = \lim _{J\to \infty } \alpha _k^{(J)}. \end{equation*}$$

Clearly, $\liminf _{x\to \infty } N_k(x)/x \ge \alpha _k$. We now show that $\limsup _{x\to \infty } N_k(x)/x \le \alpha _k$.

If $m \le x$ has at least $k$ friends in $[1,x]$, but $m\not \in \bigcup _{\substack{1 \le j \le J\\ 0 \le i \le k}} \mathscr{M}_{i,j}(x)$, then $m \in \mathscr{M}_{i,j}(x)$ for some $j > J$. Since $\#\mathscr{M}_{i,j}(x) \le \frac{x}{n_{k,j}}$, the number of these $m \le x$ is at most

$$\begin{equation*} (k+1)x \cdot \sum _{j > J} \frac{1}{n_{k,j}}. \end{equation*}$$

We now study the sum on $j$. Without the restriction to $j > J$, the sum converges (or is a finite sum). Indeed, from Lemma 5.1, the contribution to the unrestricted sum from those $j$ with $X \le n_{k,j} < 2X$ is bounded by $X^{-\frac{1}{k+2}+o(1)}$, as $X\to \infty$; the desired result now follows upon summing $X$ along the powers of $2$. So with the restriction to $j > J$, the series decays to $0$ as $J\to \infty$. Letting $x\to \infty$ and then $J\to \infty$, in that order, we get that $\limsup _{x\to \infty } N_k(x)/x\le \alpha _k$.

It remains to prove that $\alpha _k \to 0$. Since $k \cdot N_k(x)\le \sum _{n \le x} F(n;x)$, Erdős’s estimate 1.2 shows that $\alpha _k \ll 1/k$.

■

Remark.

(i)

A similar argument to the one just seen will show that each positive integral moment $\frac{1}{x}\sum _{n \le x} F(n;x)^k$ tends to a finite limit as $x\to \infty$. Here one uses that $F(n;x)^k$ can be viewed as the count of (ordered) friendly $(k+1)$-tuples in $[1,x]$ having final element $n$ and all other elements distinct from $n$. As a consequence, the $\alpha _k$ tend to zero more rapidly than any power of $k^{-1}$.

(ii)

The computations of $N_i(x)$, $i=1,\dots ,4$, reported in Table 3 were made with the aforementioned solveBA script.

We do not know how to show that each $\alpha _k$ is nonzero. This is equivalent to the assertion that the count of natural numbers $n$ with $\frac{\sigma (n)}{n}=\alpha$ is unbounded in $\alpha$, a conjecture mentioned already in 19. Note that this conjecture would follow from the infinitude of perfect numbers. Since the $\alpha _k$ may eventually vanish, we cannot show that the $\alpha _k$ are strictly decreasing. However, we can prove that the sequence is strictly decreasing until it hits zero.

Theorem 5.2.

If $\alpha _k > 0$, then $\alpha _{k} > \alpha _{k+1}$.

Proof.

Since $\alpha _k > 0$, there are examples of friendly $(k+1)$-sets. (When $k=0$, we consider every singleton subset of the natural numbers to be a friendly $(k+1)$-set.) Fix such a set $\{n_0 < n_1 < \dots < n_k\}$ once and for all, chosen to have $n_k$ as small as possible. This set is automatically primitive. Every integer of the form $m=dn_k$, with $d \le x/n_k$ and $\gcd (d, n_0 \cdots n_k)=1$, has at least $k$ friends in $[1,x]$. It suffices to show that $\gg x$ values of $d$ give rise to an $m$ with exactly $k$ friends in $[1,x]$.

Sort all of the primitive friendly $(k+2)$-sets in increasing order, and then list the sets in order of their largest entry. Say the $j$th set consists of $n_{0,j} < n_{1,j} < \dots < n_{k+1,j}$. With $J$ a large, fixed integer to be chosen later, we restrict attention to $d$ satisfying

$$\begin{equation} \frac{x}{n_k+1} < d \le \frac{x}{n_k} \quad \text{and}\quad d\equiv 1\pmod {\prod _{i=0}^{k} n_i \prod _{\substack{0 \le i \le k+1 \\ 1 \le j \le J}} n_{i,j}}. {\tag{5.1}} \end{equation}$$

Let $M_{J}$ be the modulus of this congruence. For large $x$, there are $\gg x/M_J$ values of $d$ satisfying 5.1. (The implied constant also depends on $k$ and the set $\{n_0, \dots , n_k\}$, but since these parameters are fixed, we ignore this in our notation.) We now show that for most of these $d$, the integer $M=d n_k$ has exactly $k$ friends in $[1,x]$.

If $m=dn_k$ has at least $k+1$ friends in $[1,x]$, then for some $j$,

$$\begin{equation*} d n_k = d' n_{i,j}, \quad \text{where}\quad d' \le x/n_{k+1,j} \text{ and } \gcd (d', \prod _{\ell =0}^{k+1}n_{\ell ,j})=1. \end{equation*}$$

In particular, $n_{i,j} \mid d n_k$. Suppose to begin with that $j \le J$. Then $\gcd (n_{i,j},d)=1$ from 5.1, and so $n_{i,j} \mid n_k$. Putting $e = n_k/n_{i,j}$,

$$\begin{equation*} d' = de \le \frac{x}{n_{k+1,j}},\quad \text{so that}\quad d\le \frac{x}{e\cdot n_{k+1,j}} \le \frac{x}{n_{k+1,j}}. \end{equation*}$$

Since $n_{0,j},\dots , n_{k,j}$ are in increasing order and make up a friendly $(k+1)$-set, we have $n_{k+1,j} > n_{k,j} \ge n_k$, by the initial choice of $n_k$. Hence, $n_{k+1,j} \ge n_{k}+1$, and so this last upper bound on $d$ contradicts 5.1. So we must have $j > J$. From $d n_k = d' n_{i,j}$ and $\gcd (d,M_J)=1$, we see that $\gcd (n_{i,j},M_J) \mid n_k$. In particular, $\gcd (n_{i,j},M_J) \ll 1$. Using $dn_k = d'n_{i,j}$ and 5.1, we see that $d'$ belongs to a fixed residue class modulo $n_K M_J/\gcd (n_{i,j}, n_K M_J)$. The number of these $d' \le x/n_{k+1,j}$ is at most

$$\begin{equation*} x \frac{\gcd (n_{i,j}, n_k M_J)}{n_k M_J \cdot n_{k+1,j}} +1 \ll \frac{x}{M_J \cdot n_{k+1,j}}+1. \end{equation*}$$

Hence, the number of $m=dn_k$ with $d$ satisfying 5.1 that have at least $k+1$ friends in $[1,x]$ is

$$\begin{equation*} \ll \sum _{i=0}^{k+1} \sum _{\substack{j > J\\ n_{k+1,j} \le x}} \left(\frac{x}{M_J \cdot n_{k+1,j}}+1\right). \end{equation*}$$

Since the sum on $j$ is only over $j > J$, and since we can take $J$ arbitrarily large, the main term here can be made smaller than any constant multiple of $x/M_J$, by the same argument used in the proof of Theorem 1.6. The error term is bounded by a power of $x$ less than $1$, by Lemma 5.1. So fixing $J$ large enough, we have that for large $x$, there are $\gg x/M_J \gg x$ values of $d$ satisfying 5.1 for which $m=d n_k$ has exactly $k$ friends in $[1,x]$, as desired.

■

6. Some final remarks

In the paper 17, which inspired our work above on friendly pairs, Erdős writes “I would like to call attention to three simple problems which as far as I know are still unsolved”. The problems are:

•

Are there infinitely many solutions to the equation $\sigma (n)=\varphi (m)$?

•

For each real number $c\ge 1$, is there an infinite sequence of pairs $m_k,n_k$ with $\sigma (m_k)=\sigma (n_k)$ and $m_k/n_k\to c$ as $k\to \infty$?

•

If $g(x)$ is the number of coprime pairs $a,b$ with $a<b\le x$ and $\sigma (a)=\sigma (b)$, do we have $g(x)/x\to \infty$ as $x\to \infty$?

We note that the first two problems have been recently solved in the affirmative (see 24, 34), and the third was “almost” solved in the affirmative (solved without the coprimality condition) in 1980 (see 37). It seems fitting to close this paper with a complete proof of the third problem.

Following an idea of Erdős 14, say $\theta >1$ is such that there are $y^\theta /(\log y)^{O(1)}$ primes $p\le y^\theta$ with $P(p+1)\le y$. Let $x$ be large, let $y=\log x$, let $\mathscr{S}$ be the set of primes $p\le y^\theta$ with $P(p+1)\le y$, let $n=\#\mathscr{S}$, and let $k=\lfloor \log x/\log (y^\theta )\rfloor$. Consider integers $a$ which are the product of $k$ distinct primes in $\mathscr{S}$. Since $\binom{n}{k}=x^{1-1/\theta +o(1)}$, as $x\to \infty$, there are $x^{1-1/\theta +o(1)}$ of these integers $a\le x$, each with $P(\sigma (a))\le y$. But, as was shown by Erdős (see 11), the number of integers to $x$ not divisible by any prime $>y$ is $x^{o(1)}$. Hence, there is one value $v$ such that $\sigma (a)=v$ has $x^{1-1/\theta +o(1)}$ solutions $a\le x$, as $x\to \infty$. It follows that there are $x^{2-2/\theta +o(1)}$ pairs $a<b\le x$ with $\sigma (a)=\sigma (b)$.

This would solve the third problem above if we had $\theta >2$ and if the pairs $a,b$ created were coprime. We know from 37 that $\theta >2$, the current record being a number slightly larger than $3.377$; see 4. Let $\epsilon >0$ be fixed but arbitrarily small, and let $k_0=\lfloor (1-\epsilon )k\rfloor$. The number of pairs $a,b$ which reduce to a coprime pair $a',b'$ with $\omega (a')=\omega (b')=j$ is at most

$$\binom{n}{j}^2\binom{n}{k-j}.$$

Summing this for $j\le k_0$ gives $x^{2-2/\theta -(1-1/\theta )\epsilon +o(1)}$. Thus, almost all of our pairs $a,b$ reduce to a pair $a',b'$ where $\omega (a')=\omega (b')>k_0$. In fact, there is some $j_0\in (k_0,k]$ where $x^{2-2/\theta +o(1)}$ pairs $a,b$ reduce to coprime pairs $a',b'$ with $\omega (a')=\omega (b')=j_0$. Each of these pairs comes from at most $\binom{n}{k-j_0}\le x^{(1-1/\theta )\epsilon +o(1)}$ pairs $a,b$, so there must be at least $x^{(2-\epsilon )(1-1/\theta )+o(1)}$ coprime pairs $a',b'\le x$ with $\sigma (a')=\sigma (b')$. If $\epsilon$ is sufficiently small, we see that $g(x)>x^{1.4}$ for all sufficiently large values of $x$.

Table 1.

Counts $U(x)$ of nonaliquots to various heights $x$ from $10^8$ through $10^{10}$, along with the corresponding densities $D(x)$.

$x$	$U(x)$	$D(x)$	$x$	$U(x)$	$D(x)$
100000000	16246940	0.1625	1000000000	165826606	0.1658
200000000	32721193	0.1636	2000000000	333261274	0.1666
300000000	49265355	0.1642	3000000000	501171681	0.1671
400000000	65855060	0.1646	4000000000	669372486	0.1673
500000000	82468000	0.1649	5000000000	837801755	0.1676
600000000	99107582	0.1652	6000000000	1006383348	0.1677
700000000	115764316	0.1654	7000000000	1175094232	0.1679
800000000	132438792	0.1655	8000000000	1343935989	0.1680
900000000	149128373	0.1657	9000000000	1512867678	0.1681
			10000000000	1681871718	0.1682

Table 2.

Counts of primitive friendly pairs. Here “Limit” is $L$ with the “Count” being the number of pairs to $10^L$ and “Exponent” being that $E$ such that Count = $10^{LE}$.

Limit	3	4	5	6	7	8	9	10	11
Count	9	19	38	66	148	292	548	966	1688
Exponent	.318	.320	.316	.303	.310	.308	.304	.298	.293

Table 3.

$N_1(x), N_2(x)$, $N_3(x)$, and $N_4(x)$ for $x=10^j$, with $3\le j \le 10$.

	$10^3$	$10^4$	$10^5$	$10^6$	$10^7$	$10^8$	$10^9$	$10^{10}$
$N_1(x)$	$37$	$348$	$3475$	$34746$	$347471$	$3474564$	$34745605$	$347456117$
$N_2(x)$	$3$	$30$	$283$	$2816$	$28089$	$280938$	$2809813$	$28097701$
$N_3(x)$	$0$	$12$	$82$	$857$	$8517$	$85365$	$853513$	$8535154$
$N_4(x)$	$0$	$0$	$10$	$85$	$853$	$8457$	$84605$	$845674$

Table 4.

Counts $U_\varphi (x)$ of numbers not in the range of $s_\varphi (\cdot )$ to various heights $x$ from $10^8$ through $10^{10}$, along with the corresponding densities $D_\varphi (x)$.

$x$	$U_\varphi (x)$	$D_\varphi (x)$	$x$	$U_\varphi (x)$	$D_\varphi (x)$
100000000	11355049	0.1136	1000000000	113482572	0.1135
200000000	22718595	0.1136	2000000000	226723208	0.1134
300000000	34079552	0.1136	3000000000	339811983	0.1133
400000000	45433178	0.1136	4000000000	452815609	0.1132
500000000	56783449	0.1136	5000000000	565739195	0.1131
600000000	68129835	0.1135	6000000000	678597689	0.1131
700000000	79472816	0.1135	7000000000	791405364	0.1131
800000000	90811869	0.1135	8000000000	904168542	0.1130
900000000	102146368	0.1135	9000000000	1016908189	0.1130
			10000000000	1129598504	0.1130