Sums of Small Divisors

The first 10,000 prime gaps, colored by size.

— PROBLEM STATEMENT —

The following problem originates (as far as I can tell) with Douglas Iannucci and was relayed to me via Brian Freidin. We define a function $f(n)$ by the divisor sum

$\displaystyle f(n):= \sum_{d \mid n,\,\,\, d \leq \sqrt{n}} d.$

Thus $f(n)$ is like the sum-of-divisors function $\sigma(n)$ , except it includes in its sum only the small divisors of $n$ . Whereas $\sigma(n)\geq n+1$ , the function $f(n)$ is much smaller. In fact, the trivial bound gives

$\displaystyle f(n) < \sum_{d \mid n} \sqrt{n} \leq d(n) \sqrt{n},$

and the divisor bound $d(n) \ll n^\epsilon$ for all $\epsilon>0$ gives $f(n) \ll n^{1/2+\epsilon}$ . In particular, $f(n) =o(n)$ , so it makes sense to pose the following question:

Question: For which $n$ do we have $f(n) \mid n$ ? Are there infinitely many $n$ for which this holds?

— SOME SIMPLE OBSERVATIONS —

The answer to the second half of our question is a resounding yes. The easiest way to prove this is to notice that $f(p)=1$ for all primes $p$ , hence $f(p) \mid p$ trivially.

So the real question we’d like to answer is the following:

Question: For which composite $n$ do we have $f(n ) \mid n$ ? Are there infinitely many composite $n$ for which this holds?

And now we have hit the nail on a non-trivial question. I suspect that the answer to the second half of this question is still yes, because (as we will see in a few sections), it follows from a laundry list of well-known conjectures in number theory.

But first, to get our feet wet, let’s prove some basic observations.

Proposition: If $f(n) \mid n$ and $n$ is a prime power, then $n$ is prime.

Proposition: If $f(n) \mid n$ and $n$ is a semiprime, then $n=6$ .

Proposition: If $f(n) \mid n$ and $n = p q r$ is a product of three primes, then $n$ is divisible by a square and satisfies one of the following:

(a) $n=12$ or $n=18$
(b) $n= p^2 (p^2+p+1)$ with $p^2+p+1$ prime,
(c) $n = p^2(p^2-p-1)$ with $p^2-p-1$ prime.

The first two Propositions are simple exercises and the third follows by casework on the size of $p$ , $q$ , and $r$ relative to $\sqrt{n}$ . This third Proposition is particularly interesting because we see in cases (b) and (c) the potential for infinitely many composite solutions. In fact, the set $\{n : f(n) \mid n\}$ would be infinite provided that the following conjecture holds:

Conjecture: There are infinitely many primes $p$ such that either $p^2+p+1$ or $p^2-p-1$ is simultaneously prime.

This conjecture is probably true (but far from being proven), in that it is a consequence of Schinzel’s Hypothesis H. Roughly, this conjecture implies that any `nice’ collection of distinct irreducible polynomials will simultaneously produce primes for infinitely many inputs.

Schinzel’s Hypothesis H is extended by the Bateman–Horn Conjecture, which predicts asymptotics for the number of inputs that produce these simultaneous primes. For each of the polynomials $p^2\pm(p+1)$ , this amounts to

$\displaystyle \sim \frac{C X}{(\log X)^2}$

choices of $p \leq X$ that make both $p$ and $p^2\pm (p+1)$ both prime. Of course, modern number theory is a far ways from proving either of these very general conjectures.

— OTHER PARAMETRIZED FAMILIES —

A natural next step could be the classification of all $n$ with four prime factors such that $f(n) \mid n$ . I am wary of doing this for two reasons:

The number of cases to consider as regards distinct or non-distinct primes grows to 5, the number of partitions of 4.
Parametrized families for which many prime factors are made large in the limit will require Schinzel’s Hypothesis H again, or (at minimum) the Hardy–Littlewood k-tuple Conjecture.

For these reasons (which may be completely off-base), I think that a better route is to consider parametrized families of solutions in which only one or two prime factors is made large.

The simplest such family is one of the form $n = m \cdot p(t)$ , in which $m$ is some constant and $p(t)$ is assumed to take on infinitely many prime values. For sufficiently large primes $p(t)$ , we have

$f(m \cdot p(t)) = \sigma(m),$

so we are led to consider $m$ such that $\sigma(m) \mid m p(t)$ . Yet $\gcd(\sigma(m),p(t))=1$ in general, hence this forces $\sigma (m) \mid m$ , a contradiction.

The second simplest family would be of the form $n= m \cdot p(t) q(t)$ , in which $p(t)$ and $q(t)$ are expected to satisfy Schinzel’s Hypothesis H. But this will likely lead to another intractable problem unless we assume that $p(t)$ and $q(t)$ are both linear.

It’s hard to make sense of the outcome unless $p(t)$ and $q(t)$ have the same leading coefficient, so we suppose that $p(t)=t$ and $q(t)=t+k$ with $k > 0$ . It turns out that this does lead to an infinite family (for certain $k$ ), which we describe below:

Theorem A: Choose $m$ such that $2f(m) \mid \gcd(m,\sigma (m))$ . For any (sufficiently large) prime $p$ such that $p+\sigma(m)/f(m)$ is also prime, we have $f(n) \mid n$ for

$\displaystyle n:= m p \left( p+ \frac{\sigma(m)}{f(m)}\right).$

Theorem A is best understood in terms of prime gaps. If $m$ is fixed and there exist infinitely many pairs of primes that differ by $\sigma(m)/f(m)$ , then we have found an infinite set of solutions to $f(n) \mid n$ .

The most famous conjecture about prime gaps is the Twin Prime Conjecture, which claims that the prime gap two occurs infinitely often. There’s no real connection between Theorem A and the Twin Prime Conjecture (since $\sigma(m)/f(m)$ cannot be 2), but choosing $m=6$ gives $\sigma(m)/f(m)=4$ and relates our problem to the infinitude of cousin primes, primes $p$ such that $p+4$ is also prime.

Corollary: If $p$ is a cousin prime, then $n:= 6p(p+4)$ satisfies $f(n) \mid n$ .

Similarly, $m=28$ relates our question to the infinitude of prime pairs which differ by $8$ . It is a natural question to ask which (even) integers appear in the image of $\sigma(m)/f(m)$ . It is not all of them (see the exercises). A list of all the admissible $m \leq 10^7$ and the corresponding values for $\sigma(m)/f(m)$ are given below:

$m$	$\sigma(m)/f(m)$
6	4
28	8
496	32
8128	128

We seem to have produced a necessary and sufficient condition for generating even perfect numbers. The sufficiency is of course easy to check, and we obtain the following:

Corollary: Fix $q$ and choose $m = 2^{q-1} (2^q-1)$ such that $2^q-1$ is a Mersenne prime. For any (sufficiently large) prime $p$ such that $p+2^q$ is also prime, we have $f(n) \mid n$ for

$\displaystyle n:= 2^{q-1} (2^q-1) p \big( p+ 2^q\big).$

Another fun tidbit is revealed along the way. Since these $m=2^{q-1}(2^q-1)$ satisfy $2f(m) \mid \gcd(m,\sigma(m))$ , we have in particular that $f(m) \mid m$ . In other words,

Corollary: Let $m$ be an even perfect number. Then $f(m) \mid m$ .

Alas, the existence of infinitely many perfect numbers (or equivalently, of infinitely many Mersenne primes) is another open problem. (It is, however, widely believed.)

— CONCLUSIONS? —

Unfortunately, I cannot yet resolve the question of the infinitude of the set of $n$ (composite) such that $f(n) \mid n$ . The best we’ve done is show that it seems extremely likely to be true, and that it follows from any of the following statements:

Schinzel’s Hypothesis H
the Hardy–Littlewood k-tuple Conjecture
there exist infinitely many cousin primes (or any other class of prime pairs which differ by one more than a Mersenne prime)
there exist infinitely many Mersenne primes (or equivalently, there exist infinitely many even perfect numbers)

Still, I think that a clever argument might solve our problem without appeal to any of the conjectures listed above. My cautious optimism stems from the fact that Theorem A involves not just families of primes with gap 4, or of gap 28, but of gaps which lie in a somewhat large (and conjecturally infinite) set.

If other parametrized families of solutions to $f(n) \mid n$ come to light which reduce our question to the infinitude of twin primes, and then to the infinitude of cousin primes, etc., up to the infinitude of primes which differ by $246$ , then partial progress towards the twin prime conjecture would show that $f(n) \mid n$ for infinitely many composite $n$ .

More likely, it may be possible to show that our problem follows from the infinitude of simultaneous primes in the larger constellations $\{p,p+k_1,\ldots,p+k_r\}$ , for $(k_1,\ldots,k_r)$ in a sufficiently large class of $r$ -tuples. A theorem of Maynard (Theorem 1.2 in Small Gaps Between Primes) implies that at least one constellation would actually give infinitely many simultaneous primes, so long as the set of allowed $r$ -tuples was sufficiently large.

— EXERCISES —

Exercise 1. Prove that $\sigma(m)/f(m) \neq 2$ for any $m \geq 1$ .

Exercise 2. Prove that $\sigma(m)/f(m) \neq 46$ for any $m \geq 1$ . Hint: Find an effective lower bound for $\sigma(m)/f(m)$ to make this a finite computation.

Exercise 3. Find a value of $m$ for which $2f(m) \mid m$ and $f(m) \mid \sigma(m)$ that is not a perfect number. How many such $m$ are there less than $10^6$ ?