AN UPPER BOUND FOR ODD PERFECT NUMBERS

Pace P. Nielsen

Department of Mathematics, University of California, Berkeley, CA 94720, U.S.A.

                         pace@math.berkeley.edu

Received:1/31/03, Revised: 9/29/03, Accepted: 10/21/03, Published:10/22/03

Abstract

If N is an odd perfect number with k distinct prime factors then we show that N < 2^{4^{k}}. If some of the small prime factors of N are known then this bound can be further improved.

1. Introduction

Let N be a positive integer. For n, d ∈ ℤ_{+}, we say that N is an n/d-perfect number if σ(N)/N = n/d, where σ is the sum the divisors function. In the special case when n/d = 2, N is called a perfect number. Currently there are 39 known perfect numbers. They are all of the form 2^{p−1}(2^{p} − 1) with 2^{p} − 1 prime (p must also be prime). It is conjectured that all perfect numbers are of this form. Euler proved that this is indeed true if we restrict ourselves to the case when N is even. The problem is still open when N is odd, and this is probably the oldest unsolved problem in mathematics.

There are a number of results that restrict the size and arithmetic properties of possible odd perfect numbers. To give some examples, suppose that N is an odd perfect number with k distinct prime factors. Euler proved that one can write N = a^{2}(4b+1)^{4c+1} with a, b, c ∈ ℤ_{+}. E.Z. Chein in his doctoral thesis [2] and Hagis [5] independently proved that k ⩾ 8. Jenkins [9] showed that the largest prime factor of N must exceed 10^{7}; Iannuci [7], [8] proved that the second largest exceeds 10^{4} and the third largest exceeds 10^{2}. An extensive computer search by Brent, Cohen, and te Riele [1] demonstrated that N > 10^{300}.

In 1913, Dickson [4] proved that there are only finitely many odd perfect numbers with k distinct prime factors. In 1977, Pomerance [10] gave an explicit upper bound in terms of k. Heath-Brown [6] later improved the bound to N < 4^{4^{k}}, and Cook [3] reduced this further to N < D^{4^{k}} with D = (195)^{1/7}.

The methods of this paper slightly improve and generalize Cook’s bound. Throughout this paper we assume that n, d ∈ ℤ_{+}. Further, if we say that N is an n/d-perfect number we do not assume that n/d is written in lowest terms, unless explicitly stated.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A14 2

2. A Lemma and Some Notation

Lemma 1. Let r, a, b ∈ ℤ_{+} and let x_{1}, …, x_{r} be integers such that 1 < x_{1} < … < x_{r}. If

∏_{i=1}^{r} (1 − \frac{1}{x_{i}} ) ⩽ \frac{a}{b} < ∏_{i=1}^{r−1} (1 − \frac{1}{x_{i}} )  (∗)

then

a ∏_{i=1}^{r} x_{i} < (a + 1)^{2^{r}}.

Proof. This is just a summary of some results from [3]. For completeness we include the proof, which is by induction on r. The case r = 1 is easy, so assume that r ⩾ 2 and that the result holds (for any a and b) for each integer less than r.

Fix a ⩾ 1. Suppose that 1 < x_{1} < … < x_{r} are integers satisfying (∗) (for some b) with x_{1} ⋯ x_{r} maximal. Set n_{i} = (a + 1)^{2^{i−1}} + 1 for i < r and put n_{r} = (a + 1)^{2^{r−1}}. It is easy to see that 1 < n_{1} < … < n_{r} and

∏_{i=1}^{r} (1 − \frac{1}{n_{i}} ) = \frac{a}{a + 1} < ∏_{i=1}^{r−1} (1 − \frac{1}{n_{i}} ) .

Therefore ∏_{i=1}^{r} x_{i} ⩾ ∏_{i=1}^{r} n_{i}.

If ax_{1} < an_{1} = (a + 1)^{2} − 1 then multiplying (∗) through by \frac{x_{1}}{x_{1}−1} yields

∏_{i=2}^{r} (1 − \frac{1}{x_{i}} ) ⩽ \frac{ax_{1}}{b(x_{1} − 1)} < ∏_{i=2}^{r−1} (1 − \frac{1}{x_{i}} ) .

Our induction hypothesis then implies (ax_{1})x_{2} ⋯ x_{r} < (ax_{1} + 1)^{2^{r−1}} < (a + 1)^{2^{r}}. So we may as well assume that x_{1} ⩾ n_{1}.

If ax_{1}x_{2} < an_{1}n_{2} = (a + 1)^{4} − 1 then multiplying (∗) through by \frac{x_{1}x_{1}}{(x_{1}−1)(x_{2}−1)} yields

∏_{i=3}^{r} (1 − \frac{1}{x_{i}} ) ⩽ \frac{ax_{1}x_{2}}{b(x_{1} − 1)(x_{2} − 1)} < ∏_{i=3}^{r−1} (1 − \frac{1}{x_{i}} ) .

Our induction hypothesis implies (ax_{1}x_{2})x_{3} ⋯ x_{r} < (ax_{1}x_{2} + 1)^{2^{r−2}} < (a + 1)^{2^{r}}. So we may as well assume that x_{1}x_{2} ⩾ n_{1}n_{2}.

Continuing in this manner, we may as well assume ∏_{i=1}^{u} x_{i} ⩾ ∏_{i=1}^{u} n_{i} for each u < r. We already saw that this inequality also holds for u = r. But then Lemma 2 of [3] contradicts (∗) (for any b we might choose). Hence, in all cases, a ∏_{i=1}^{r} x_{i} < (a + 1)^{2^{r}}. □

Notation. Let S = {x_{1}, …, x_{r}} be a set of r distinct integers, each greater than 1, ordered under the usual ordering. We use the notation Π(S) = ∏_{i=1}^{r} x_{i}, with the convention that Π(∅) = 1. If a is a positive integer and r > 0 then we put

B(r, a) = ((a + 1)/a)^{2^{r}/(2^{r}−1)}.

By convention, we set B(0, a) = 1.

Let r, a, b > 0 and suppose we have the following inequalities:

∏_{i=1}^{r} (1 − \frac{1}{x_{i}} ) ⩽ \frac{a}{b} < ∏_{i=1}^{r−1} (1 − \frac{1}{x_{i}} ) .

Lemma 1 implies a ∏_{i=1}^{r} x_{i} < (a + 1)^{2^{r}}. A quick calculation shows that this is equivalent to Π(S) < (B(r, a)a)^{2^{r}−1}.

3. The Main Result

Before we prove the theorem we give an independent, but interesting, result:

Proposition 1. Let N be an odd perfect number with k distinct prime factors, and let

P = ∏_{p |N} p.

Then

N < P^{2^{k}−1}.

Proof. Let N = ∏_{i=1}^{k} p_{i}^{e_{i}} be the prime factorization of N. Then P = ∏_{i=1}^{k} p_{i}, and we set P′ = ∏_{i=1}^{k}(p_{i} − 1). Since N is an odd perfect number we find ∏_{i=1}^{k}(p_{i}^{e_{i}+1} − 1)/(p_{i} − 1) = σ(N) = 2N = 2 ∏_{i=1}^{k} p_{i}^{e_{i}}. Rewriting this, we obtain

∏_{i=1}^{k} (1 − \frac{1}{p_{i}^{e_{i}+1}} ) = \frac{2P′}{P} < 1.

Thus, the hypotheses of Lemma 1 hold with a = 2P′, b = P, and x_{i} = p_{i}^{e_{i}+1} (reordering the p_{i} if necessary). So Lemma 1 gives the second inequality below:

P N < 2P′P N = 2P′ ∏_{i=1}^{k} p_{i}^{e_{i}+1} < (2P′ + 1)^{2^{k}} ⩽ P^{2^{k}}.

This implies N < P^{2^{k}−1}. □

We now proceed with the proof of:

Theorem 1. If N is an odd n/d-perfect number with k distinct prime factors then

N < (d + 1)^{4^{k}}.

Proof. Much of our notation is taken from Heath-Brown [6]. Most of this proof is a direct strengthening of the algorithm given there.

If N = 1 then everything holds, so assume N > 1. Let N = ∏_{p |N} p^{e(p)} be the prime factorization of N. Let S be any set (possibly empty) of distinct primes dividing N. Since N is odd and d/n = N/σ(N) ≠ 1, it follows that d/n has an odd numerator when written in lowest terms. Hence

∏_{p∈S} (1 − \frac{1}{p}) ≠ \frac{d}{n},

where, by convention, the product equals 1 if S = ∅.

Case 1: ∏_{p∈S} (1 − \frac{1}{p}) > \frac{d}{n}.

Set d′ = d ∏_{p∈S} p = dΠ(S) and n′ = n ∏_{p∈S}(p − 1). Since ∏_{p∈S}(1 − (1/p)) > d/n we have d′/n′ < 1. We also calculate

∏_{p |N} (1 − \frac{1}{p}) < ∏_{p |N} \frac{p − 1}{p − \frac{1}{p^{e(p)}}} = ∏_{p |N} \frac{p^{e(p)}}{\frac{p^{e(p)+1}−1}{p−1}} = \frac{N}{σ(N)} = \frac{d}{n}.

So we have

∏_{p |N, p∉S} (1 − \frac{1}{p}) < \frac{d′}{n′} < 1.

These last two inequalities imply that we can pick a non-empty, ordered set of distinct prime divisors of N, say S′ = {p_{1}, …, p_{w}}, such that S′ ∩ S = ∅ and such that the following inequalities hold:

∏_{i=1}^{w} (1 − \frac{1}{p_{i}} ) ⩽ \frac{d′}{n′} < ∏_{i=1}^{w−1} (1 − \frac{1}{p_{i}} ) .

Fix such a set S′. Then, letting B = B(w, d′) where w = |S′|, Lemma 1 implies

Π(S′) < (Bd′)^{2^{w}−1}

and hence

Π(S ∪ S′) ⩽ (Bd)^{2^{w}−1} (Π(S))^{2^{w}} .  (1)

Also, from the definition of S′ we have

∏_{p∈S∪S′} (1 − \frac{1}{p}) < \frac{d}{n}.  (2)

Notice, as remarked above, that equality can’t hold in (2).

Case 2: ∏_{p∈S} (1 − \frac{1}{p}) < \frac{d}{n}.

We define n′ and d′ as in Case 1. Let S′ = ∅ and w = 0, and set B = B(w, d′) = 1. Then both inequalities (1) and (2) hold in this case also. (In fact, equality holds in (1), but we don’t need this fact.)

We have shown in the two cases above that for any choice of S we can pick another set of prime divisors of N disjoint from S, namely S′, such that inequalities (1) and (2) hold. We now continue with the proof in the general case.

Let d′′ = dΠ(S ∪ S′) and n′′ = n ∏_{p∈S∪S′}(p − 1). Inequality (2) says n′′/d′′ < 1. Now,

∏_{p∈S∪S′} \frac{1 − \frac{1}{p^{e(p)+1}}}{1 − \frac{1}{p}} = ∏_{p∈S∪S′} \frac{\frac{p^{e(p)+1}−1}{p−1}}{p^{e(p)}} ⩽ \frac{σ(N)}{N} = \frac{n}{d}

so that

∏_{p∈S∪S′} 1 − \frac{1}{p^{e(p)+1}} ⩽ \frac{n′′}{d′′} < 1.  (3)

Then, just as above, we can pick a non-empty subset S′′ ⊆ S ∪ S′, for which Lemma 1 implies:

∏_{p∈S′′} p^{e(p)+1} ⩽ (B′n′′)^{2^{v}−1}  (4)

with v = |S′′|, B′ = B(v, n′′).

As in Heath Brown’s paper we let V = ∏_{p∈S′′} p^{e(p)}, U = N/V, and T = (S ∪ S′) − S′′. However we differ in our definition of δ by setting δ = d ∏_{p∈S′′}(p^{e(p)+1} − 1)/(p − 1). Finally, we let ν = δσ(U)/U.

We now deduce a long chain of inequalities. First, we calculate

\frac{δ + 1}{δ}δΠ(T) = \frac{δ + 1}{δ}d ∏_{p∈S′′} \frac{p^{e(p)+1} − 1}{(p − 1)p}Π(S ∪ S′)

= \frac{δ + 1}{δ}d ∏_{p∈S′′} \frac{p^{e(p)+1} (1 − \frac{1}{p^{e(p)+1}} )}{(p − 1)p}Π(S ∪ S′)

⩽ \frac{δ + 1}{δ} \frac{n′′}{d′′} d ∏_{p∈S′′} \frac{p^{e(p)+1}}{(p − 1)p}Π(S ∪ S′)  by inequality (3).

Since S′′ ≠ ∅ and δ ∈ ℤ_{+}, it is clear that \frac{δ+1}{δ} ∏_{p∈S′′} \frac{1}{(p−1)p} < 1. Therefore, continuing the previous inequality, we find

\frac{δ + 1}{δ} \frac{n′′}{d′′} d ∏_{p∈S′′} \frac{p^{e(p)+1}}{(p − 1)p}Π(S ∪ S′) < \frac{n′′}{d′′} d ( ∏_{p∈S′′} p^{e(p)+1}) Π(S ∪ S′)

< \frac{n′′}{d′′} d(B′n′′)^{2^{v}−1}Π(S ∪ S′)  by inequality (4)

= \frac{1}{d′′} d(n′′ + 1)^{2^{v}}Π(S ∪ S′)  by definition of B′.

We again appeal to Lemma 1, in the form of inequality (1), to obtain

\frac{1}{d′′} d(n′′ + 1)^{2^{v}}Π(S ∪ S′) ⩽ \frac{d}{d′′} (n′′ + 1)^{2^{v}}(Bd)^{2^{w}−1}Π(S)^{2^{w}}  by inequality (1)

= \frac{1}{Bd′′} (n′′ + 1)^{2^{v}}(BdΠ(S))^{2^{w}}

= \frac{1}{B} (\frac{n′′ + 1}{d′′})^{2^{v}} (d′′)^{2^{v}−1}(BdΠ(S))^{2^{w}}.

As remarked above, inequality (2) is equivalent to n′′/d′′ < 1. Therefore, we know that (n′′ + 1)/d′′ ⩽ 1. So our chain of inequalities continues as follows:

\frac{1}{B} (\frac{n′′ + 1}{d′′})^{2^{v}} (d′′)^{2^{v}−1}(BdΠ(S))^{2^{w}} ⩽ \frac{1}{B} (d′′)^{2^{v}−1}(BdΠ(S))^{2^{w}}

= \frac{1}{B} (dΠ(S ∪ S′))^{2^{v}−1}(BdΠ(S))^{2^{w}}  from the definition of d′′

⩽ \frac{1}{B} (d(Bd)^{2^{w}−1}Π(S)^{2^{w}})^{2^{v}−1}(BdΠ(S))^{2^{w}}  by inequality (1).

This last quantity is just (B^{2^{w}−1})^{2^{v}}(dΠ(S))^{2^{w+v}}. A short calculation, using the definition of B, yields

(B^{2^{w}−1})^{2^{v}}(dΠ(S))^{2^{w+v}} ⩽ ((\frac{d′ + 1}{d′}) dΠ(S))^{2^{w+v}} .

Equality holds above, except in the case w = 0. Now, since d′ ⩾ d, we also have

((\frac{d′ + 1}{d′}) dΠ(S))^{2^{w+v}} ⩽ ((\frac{d + 1}{d}) dΠ(S))^{2^{w+v}} .

Putting the last two pages of inequalities together, we arrive at

\frac{δ + 1}{δ}δΠ(T) < ((\frac{d + 1}{d}) dΠ(S))^{2^{w+v}} .  (5)

In essence, we have re-proven Lemma 2 from Heath-Brown [6], but with our inequality (5) replacing his inequality (iv). One can easily check that all of the necessary conditions of his lemma hold under our construction. To finish the proof we follow the inductive process described on page 196 of [6], with the only change being that we put inequality (5) in place of Heath-Brown’s inequality (iv), everywhere it occurs. This yields

N < ((\frac{d + 1}{d}) d)^{4^{k}} = (d + 1)^{4^{k}}.

□

4. Explicit Calculations and Examples

Corollary 1. If N is an odd perfect number (OPN) then

N < 2^{4^{k}}.

Corollary 2. If N is an OPN and 5||N then

N < 5 · 4^{4^{k−1}}.

Proof. Let N′ = N/5. Then N′ is an odd 5/3-perfect number. Applying the theorem to N′ gives the result. □

Corollary 3. If N is an OPN with 5||N and 3^{2}||N then

N < 45 · 14^{4^{k−2}}.

Our first corollary is only a slight improvement on the bounds given by Cook in [3]. However, our last two corollaries demonstrate a method that further decreases the upper bound on OPN’s when one knows which small prime factors divide N. These methods, in conjunction with [1], [9], [7], and [8] (and some brute force), are sufficient to produce a new proof that odd perfect numbers must have at least seven factors. Unfortunately, these bounds are still not strong enough to give better results.

One might be able to lower these bounds further if the inequality given in Lemma 1 could be improved. There are two clear (but difficult) ways this might be done. First, the proof of Lemma 1 doesn’t take full advantage of the integer b. Rather, it just uses the fact that b > a, and reduces to the case b = a + 1 to prove the needed inequalities. One might be able to generalize the methods of [3] to take advantage of this.

Second, if one looks carefully at the proof of the theorem given above, we only invoke Lemma 1 when the integers in question are relatively prime and are prime powers. This assumes much more stringent requirements on the x_{i} than given in the statement of Lemma 1.

To demonstrate both the strength and weakness of the bound above, we have the following:

Example. Let N = 3^{2}7^{2}11^{2}13^{2}22021. Clearly 22021 = 19^{2}61 is not prime. We want to pretend that 22021 is prime by redefining σ. Let σ′(x) = σ(x) for all x such that gcd(x, 22021) = 1, and set σ′(22021^{n}) = (22021^{n+1} − 1)/(22021 − 1) (parodying the rule σ(p^{n}) = (p^{n+1} − 1)/(p − 1) for any prime p). As pointed out by Descartes, σ′(N) = 2N, so that N is a spoof perfect number!

If we restricts ourselves to numbers that can be expressed as a power of 22021 and other factors relatively prime to 19 and 61, and if we replace σ by σ′, then the proof of the above theorem still goes through. So it should be true that for N = 3^{2}7^{2}11^{2}13^{2}22021 we have N < 2^{4^{5}}. In fact 2^{4^{5}}/N ≈ 4.407×10^{317}. This demonstrates one of the difficulties in proving the non-existence of OPN’s.

References

[1] R. P. Brent, G. L. Cohen, and H. J. J. te Riele, Improved techniques for lower bounds for odd perfect numbers, Math. Comp. 57 (1991), 857-868.

[2] Joseph E. Z. Chein, An odd perfect number has at least 8 prime factors, Ph.D. thesis, Pennsylvania State University, 1979.

[3] R. J. Cook, Bounds for odd perfect numbers, Number theory (Ottowa, ON, 1996), 67-71, CRM Proc. Lecture Notes 19 (1999).

[4] L. E. Dickson Finiteness of odd perfect and primitive abundant numbers with n-distinct prime factors, Amer. J. Math. 35 (1913), 413-422.

[5] P. Hagis, Jr., Outline of a proof that every odd perfect number has at least eight prime factors, Math. Comp. 35 (1980), 1027-1032.

[6] D. R. Heath-Brown, Odd perfect numbers, Math. Proc. Camb. Phil. Soc. 115 (1994), 191-196.

[7] D. E. Ianucci, The second largest prime divisor of an odd perfect number exceeds ten thousand, Math. Comp. 68 (1999), 1749-1760.

[8] D. E. Ianucci, The third largest prime divisor of an odd perfect number exceeds one hundred, Math. Comp. 69 (2000), 867-879.

[9] P. Jenkins, Odd perfect numbers have a factor that exceeds 10^{7}, Math. Comp. 72 (2003), 1549-1554.

[10] C. Pomerance, Multiple perfect numbers, Mersenne primes and effective computability, Math. Ann. 266 (1997), 195-206.