OP Home Composites Cleared Against Pomerance ElevenSmooth |
Dr. Carl Pomerance has shared an elegant and sobering heuristic that shows Odd Perfect Numbers are very unlikely. This heuristic was originally communicated to Joshua Zelinsky in 2003, although Dr. Pomerance apparently had similar ideas earlier. Prior to this I had seen many unsubstantiated claims that odd perfect numbers probably do not exist, but I had never seen a quantitative argument about likelyhood.
Dr. Pomerance wrote:
Mathematically sophisticated people will understand this heuristic immediately. For the rest of us, I've attempted to restate this with more detail in the following sections.
It is well known fact that any odd perfect number must be of the form
The method is to consider an arbitrary number "m" and determine an upper bound on the "probability" that we can create a perfect number with this m. Then sum this probability up over all possible values of m to get the expected number of odd perfect numbers. Finally, conclude that the expected number is so small that it is unlikely any odd perfect numbers exist. (The number p needs no exponent because we permit p to divide m).
The following definitions and simple results from Number Theory are needed to follow the heuristic.
The Prime Number Theorem says the number of primes less than x is approximately x/ln(x)
Many web sites discuss this, including
Prime Pages and
Math World
The name "primorial" is a combination of "prime" and "factorial." It is the product of all prime numbers up to some value x, and is denoted as x#. The Prime Pages and Math World also discuss this.
Math World and this paper by Caldwell and Gallot also discuss the primorial asymptotics. The asymptotic expression ln(x#)~x is used in the heuristic.
This asymptotic expression can be derived heuristically by observing that as x increases, ln(x#) either stays the same or increases by ln(x), and the probability of increase is 1/ln(x), so the expected increase is 1.
The smallest number with "k" distinct prime divisors is the k^{th} primorial. So the most distinct prime divisors for any number up to x will be the the number of divisors of the largest primorial less than or equal to x. We know from the primorial asymptotic that this is ln(x)#. And we know from the Prime Number Theorem that the number of primes less than ln(x) is ln(x)/ln(ln(x)).
σ(x) gets larger than x by having many distinct prime factors.
The limiting case is when x is a primorial.
We can use the Primorial Asymptotic
and Merten's Theorem to bound the size of σ(m^{2}).
In order to make (p m^{2}) an odd perfect number, "p" must divide σ(m^{2}). Given a value for m, how many possible values of p are there?
σ(m^{2}) is no more than e^{γ}ln(ln(m))m^{2}
The number of distinct prime divisors of a number of this size is no more than
Given a value for m and a selection for p, to be a perfect number it is necessary that m^{2} divides σ(pm^{2}).
The probability that m^{2} divides a random number is 1/m^{2}. These are necessary but not sufficient conditions, so we will call numbers meeting these criteria odd perfect candidates.
The preceeding sections develop a probability that a particular value of "m"
can be part of an odd perfect candidate.
We can get the expected number of candidates by adding this
value up over a range.
Approximating the sum with an integral, the expected number of "m's" that
can be part of an odd perfect candidate, for m > a, is
There does seem to be one ray of hope. With the exception of 6, every even perfect number is also of the form pm^{2} with p dividing σ(m^{2}) and m^{2} dividing σ(pm^{2}). Hence this heuristic suggests no large perfect numbers of any kind, neither even nor odd. But we know of many large even perfect numbers, and we suspect they are infinite. Since the heuristic is wrong for even perfect numbers, perhaps it is also wrong for odd perfect numbers. The only point of weakness I see in the heuristic is that if you could get the probability that m^{2} divides σ(pm^{2}) up from 1/m^{2} to 1/(m ln(m)), then the integral would diverge, implying an infinite number of perfect candidates.
How would you do that? You would have to build some of the factors of σ(pm^{2}) into the definition of m, so that a smaller fraction of m^{2} relied on random luck to factor. This is what happens for even perfect numbers. This is also the method used to build factor chains in the search of odd perfect numbers. But I don't see a way to adapt the heuristic to account for this effect.
The argument to accept the Pomerance Heuristic for odd perfect numbers even though it fails for even perfect numbers is that Mersenne Primes consitiute a unique conspiracy to circumvent the randomness assumptions. Furthermore, there are precedences for special cases. Dr. Pomerance makes the argument exceptionally well when he writes:
The Pomerance Heuristic suggests there should be no large perfect numbers — neither even nore odd. Dr. Pomerance argues that Mersenne Primes are a grand conspiracy to circumvent the heuristic's randomness assumption, and that no such conspiracy exists for odd perfect numbers.
Personally, I find this argument strong enough that I intend to bias the odd perfect search in directions that will produce a higher incidence of useful side effects in the form of collectible factorizations. But I don't find the argument sufficiently overwhelming to cancel the search entirely. Advances in factoring technology have created new "low hanging fruit" that we can harvest and hope to uncover an odd conspiracy.