A highly abundant number is a positive integer \( n \) that holds the record (among it and smaller numbers) for the biggest sum of divisors \( \sigma(n) \). While cleaning up some citations on the Wikipedia article, I ran across an unsolved problem concerning these numbers, posed by Jaycob Coleman and listed on the OEIS entry for them: are all sufficiently large highly abundant numbers practical?

A practical number n has the property that all numbers up to \( n \) can be expressed as sums of distinct divisors of \( n \). This can be tested by looking at the factorization of \( n \): define the \( \lt p \)-smooth part of \( n \) to be the product of the prime factors of \( n \) that are less than \( p \). Then \( n \) is practical if and only if, for each prime factor \( p \) of \( n \), \( p \) is at most one more than the sum of divisors of the \( \lt p \)-smooth part of n. So, for instance, the highly abundant number \( 10 \) is not practical: the \( \lt 5 \)-smooth part of \( 10 \) is \( 2 \), and \( 5 \) is too big compared to \( \sigma(2)=3 \). Also, \( 3 \) is not practical as its \( \lt 3 \)-smooth part is only one. Are these the only exceptions?

As with other questions involving record-holders for multiplicative functions, the highly abundant numbers can be thought of as solutions to special instances of the knapsack problem: if we define the size of a prime power \( p^i \)to be \( \log p \), and we define its profit to be the logarithm of the factor \( (p^{i+1}-1)/(p^i-1) \) by which including \( p^i \) as a divisor of \( n \) would cause σ to increase (relative to the next lower power of \( p \)), then the factorization of \( n \) is given by the set of prime powers whose sizes add to at most \( \log n \) and whose profits add to the largest number possible. I don't know how to use this knapsack view of the problem directly (in part because knapsack is a hard problem) but it is helpful in thinking about showing that certain factors must be present or absent because they would lead to a better knapsack solution.

For instance, suppose that \( n \) is highly abundant, let \( p \) be the smallest prime that does not divide \( n \), and let \( P \) be the largest prime factor of \( n \). Then it must be true that \( P\lt p^2 \). For, if not, let \( q=\lfloor P/p \rfloor \). We could replace \( P \) in the factorization of \( n \) by \( pq \), giving a smaller number than \( n \) with a bigger contribution to \( \sigma \): at least \( (p+1)q \), versus at most \( P+1 \), or smaller if \( P \) appears to a higher power than one.

Based on this fact, it's straightforward to show that all highly abundant numbers that are divisible by four are practical. More strongly the same is true for other numbers \( n \) that are divisible by four and have the same inequality for \( p \) and \( P \). For, if the first missing prime \( p \) is \( 3 \), then the sum of divisors of the \( \lt p \)-smooth part is at least \( 7 \), big enough to cover any prime factor \( P \) that satisfies the inequality. And for each additional prime factor of \( n \) smaller than \( p \), the bound on \( P \) grows by at most four (by Bertrand's postulate) and the sum of divisors of the smooth part grows by at least four, so this sum of divisors always remains large enough to satisfy the condition for being practical.

But in their early work on highly abundant numbers, Alaoglu and Erdős observed that \( 210 \) is the largest highly abundant number to include only one factor of two in its prime factorization. All larger highly abundant numbers are divisible by four, and by the argument above they are all practical. The remaining cases are small enough to test individually, and they are all practical. So Jaycob Coleman's conjecture is true.

Update: this claim about \( 210 \) is obviously wrong. \( 630 \) is highly abundant and is also not divisible by four. So here's a better argument along the same lines. The case \( p=2 \) is easy to handle: \( P \) can only be \( 3 \), so \( n \) is a power of three. If it is not \( 3 \) itself, we could replace a factor of \( 9 \) in it by a factor of \( 8 \), getting a smaller number with a bigger contribution to \( \sigma \) (\( 15 \) vs \( 13 \)). So the only odd highly abundant number is \( 3 \). Similarly, if the first missing prime is \( 3 \), then \( n \) must be \( {2,5,7} \)-smooth. If it is divisible by \( 25 \), we can replace this factor by \( 24 \) (with a contribution of at least \( 32 \) to \( \sigma \) instead of \( 31 \)) and if it is divisible by \( 7 \), we can replace this factor by \( 6 \) (with a contribution greater than \( 8 \) to \( \sigma \) instead of \( 8 \)). So the only possible highly abundant numbers that are even but not divisible by \( 3 \) are powers of two and their multiples by five, and the only one of those that can be impractical is \( 10 \).

Next, suppose that the first missing prime is \( 5 \), and there is only one factor of two. The \( \lt 5 \)-smooth part is at least \( 6 \) and its sum of divisors is \( 12 \), big enough to cover all primes less than \( 11 \), and if any of these primes is a factor of \( n \) then including it in the smooth part boosts the sum of divisors to large enough to cover all remaining factors. Similarly, if there is more than one factor of three, then the sum of divisors of the smooth part is at least \( 39 \), covering all possible prime factors. So the only possible impractical numbers in this case are not divisible by \( 5 \), \( 7 \), or \( 11 \) but are divisible by exactly one factor of \( 2 \) or \( 3 \) and may be divisible by \( 13 \), \( 17 \), \( 19 \), or \( 23 \). A factor of \( 13 \) can be replaced by a factor of \( 10 \) (contributing \( 14 \) to \( \sigma \) in either case, so giving a smaller number with the same sum of divisors). A factor of \( 17 \) can be replaced by a factor of \( 15 \) (contributing \( 19.5 \) to \( \sigma \) instead of \( 18 \)). A factor of \( 19 \) can be replaced by a factor of \( 18 \) (contributing \( 23.5 \) instead of \( 20 \)) and a factor of \( 23 \) can be replaced by a factor of \( 20 \) (contributing \( 30 \) instead of \( 24 \)). So none of these cases give rise to new exceptions.

Finally, if the first missing prime is \( 7 \), then the \( \lt 7 \)-smooth part is at least \( 30 \) and its sum of divisors is at least \( 72 \), big enough to cover all primes less than \( 49 \), and from here we can use the same Bertrand postulate argument.




Comments:

None: I'm glad you've taken an interest in my conjecture
2015-02-28T05:55:53Z

I'm beginning to understand your argument and I find it convincing, but I would await someone else's approval. Regarding your correction, I'm pretty sure you can use Daniel Fischer's proof that every highly abundant number greater than 630 is divisible by 12, but maybe you wanted something more brief?

Might a similar method resolve my analogous question for the records of the arithmetic derivative here, or be applied to the records of the sum of squares, cubes, etc., of the divisors of n?

I think these are interesting questions, but I don't know of any significant implications to make them appeal to a wider audience.

Somewhat related, let sigma(n) be the sum of divisors of n. Does n/gcd(n,sigma(n)) practical imply n is practical? This would imply every multiply-perfect number is practical (and therefore even), to which no exceptions are known so far. Of course that one is surely much more difficult.

-Jaycob Coleman

11011110: RE: I'm glad you've taken an interest in my conjecture 2015-02-28T07:55:13Z

Mostly I didn't use Fischer's proof because I hadn't noticed and followed that link, and after finding the problem with A+E wanted something self-contained. But as you say my argument for e.g. 3 being the only odd highly abundant number is significantly shorter than his.

Re could similar ideas be used for those other records? My guess is yes, because the main ingredient I'm using is just that the function we're taking records of is multiplicative. This lets us gain information about the factorization of its argument by comparing different terms that might be factors in terms of how they contribute to the function, and understanding the factorization is in turn what we need to prove that something is practical.