A Polynomial Variant of Perfect Numbers

Luis H. Gallardo and Olivier Rahavandrainy UMR CNRS 6205 Laboratoire de Mathématiques de Bretagne Atlantique 6, Av. Le Gorgeu C.S. 93837 Cedex 3, F-29238 Brest France

                  Luis.Gallardo@univ-brest.fr
           Olivier-Felix.Rahavandrainy@univ-brest.fr

Abstract

We study the binary polynomials A such that the sum of all their divisors D ≠ A is a perfect polynomial, and A is a power of an irreducible polynomial.

1 Introduction

We will work with binary polynomials, i.e., polynomials in one variable over the finite field 𝔽_{2}. In order to describe our work, we require some terminology. Let A ∈ 𝔽_{2}[x] be a polynomial. We say that A is even if A has a linear factor; otherwise A is odd. We let ℕ denote the set of positive integers. A polynomial A ∈ 𝔽_{2}[x] is Mersenne if A = 1 + x^{a}(x + 1)^{b} for some a, b ∈ ℕ. If A is irreducible, then we say that A is Mersenne prime.

We let ω(A) denote the number of distinct irreducible (or prime) factors of A over 𝔽_{2}, we let σ(A) denote the sum of all divisors of A, including 1 and A, (e.g., σ(0) = 0, σ(1) = 1, σ(x) = x+1, σ(x^{2}) = x^{2}+x+1, σ(x^{2}+x) = x^{2}+x, σ(x^{2}+x+1) = 1+(x^{2}+x+1) = x^{2}+x). We explain in more detail why σ(x^{2}) = x^{2}+x+1 and σ(x^{2}+x+1) = x^{2}+x. Indeed, since the list of all divisors of x^{2} is [1, x, x^{2}], their sum 1+x+x^{2} gives σ(x^{2}) and σ(x^{2}+x+1) = 1+(x^{2}+x+1) because P = x^{2} + x + 1 is irreducible so that σ(P) = 1 + P.

Observe that σ is a multiplicative function (i.e., σ(XY) = σ(X)σ(Y), provided that gcd(X, Y) = 1 in 𝔽_{2}[x]). If σ(A) = A, then we say that A is perfect. The first examples (besides 0 and 1) of perfect polynomials are those of the form x^{2^{n}−1}(x+1)^{2^{n}−1} = (x^{2}+x)^{2^{n}−1}, where n ∈ ℕ. We call them trivial perfect. Canaday [2, Theorem 17] proved that these are the only perfect polynomials A with ω(A) = 2. Gallardo and Rahavandrainy [5, 7] obtained some results about odd perfect polynomials, but we do not know (as in the integer case) whether or not there exist odd perfect polynomials. Mersenne primes play an important role for (the known) nontrivial perfect polynomials over 𝔽_{2}, that we call sporadic perfect. Proposition 1 contains the list of all known sporadic perfect polynomials. Indeed, up to two exceptions, they all have factorizations with only Mersenne primes as odd divisors. We are unable to describe a general form of sporadic perfect polynomials, in contrary to what happens in the integer case, where any even perfect number n = 2^{p−1}(2^{p}−1), in which both p and 2^{p} − 1 are prime numbers, has exactly two distinct prime factors f_{1} = 2 and f_{2} = 2^{p} − 1. The set of Mersenne prime numbers, as well as the set of Mersenne prime polynomials are examples of sets for which we do not know whether they are finite. Testing irreducibility for polynomials (in particular for trinomials) over a finite field, remains difficult, even if the problem has been addressed several times. Brent et al., Fredricksen and Wisniewski, Swan, and Zierler [1, 4, 12, 13] obtained several results for trinomials. A difficulty in working over 𝔽_{2}[x] is that, in contrast to the set ℤ of integers, we have no order relation in 𝔽_{2}[x], an important tool in many proofs of results for perfect numbers. In the Online Encyclopedia of Integer Sequences (OEIS) [10], one finds several sequences related to binary polynomials, e.g., \underline{A001037}, that count for every degree n, the number of irreducible binary polynomials of degree n.

Gallardo and Rahavandrainy [8] proved (under a mild condition) that all even perfect polynomials over 𝔽_{2} which are products of Mersenne primes are equal to nine of the eleven known sporadic perfect polynomials, all of which are even. More precisely, M_{11a} and M_{11b} (see below) are the unique (known) sporadic perfect polynomials that are not a product of Mersenne primes (since P_{4c} is not a Mersenne prime polynomial).

Cengiz et al. [3] proved the following proposition, part (b) of which is due to Canaday [2].

Proposition 1. (a) A possible new even perfect polynomial must have a degree exceeding 200.

(b) Let P_{2} = x^{2}+x+1, P_{3a} = x^{3}+x+1, P_{3b} = P_{3a}(x+1), P_{4a} = x^{4}+x^{3}+1, P_{4b} = P_{4a}(x+1), and P_{4c} = x^{4} + x + 1. The list of all known sporadic perfect polynomials M_{∗} ∈ 𝔽_{2}[x], in non-decreasing order of their degrees, and factored in terms of prime polynomials P_{∗}, is M_{5a} = x(x + 1)^{2}P_{2}, M_{5b} = (x + 1)x^{2}P_{2}, M_{11a} = x(x + 1)^{2}P_{2}^{2}P_{4c}, M_{11b} = x^{2}(x+1)P_{2}^{2}P_{4c}, M_{11c} = x^{3}(x+1)^{4}P_{4a}, M_{11d} = x^{4}(x+1)^{3}P_{4b}, M_{15a} = x^{3}(x+1)^{6}P_{3a}P_{3b}, M_{15b} = x^{6}(x + 1)^{3}P_{3a}P_{3b}, M_{16} = x^{4}(x + 1)^{4}P_{4a}P_{4b}, M_{20a} = x^{4}(x + 1)^{6}P_{3a}P_{3b}P_{4b}, M_{20b} = x^{6}(x + 1)^{4}P_{3a}P_{3b}P_{4a}.

Canaday [2, Theorem 1, Theorem 2] also proved the following.

Lemma 2. Every odd perfect polynomial over 𝔽_{2} is a square.

This result is the analogue of the well known fact that any odd perfect number n > 1 (i.e., n equals the sum of all its proper positive divisors), can be written as n = p^{4k+1}m^{2}, where k is a non-negative integer, p is an odd prime number congruent to 1 modulo 4, and m is a positive integer.

A special perfect polynomial is an odd perfect polynomial that equals the square of a square-free polynomial. Gallardo and Rahavandrainy [5, Theorem 5.3, Theorem 5.5] proved the following.

Lemma 3. Let A ∈ 𝔽_{2}[x] be a special perfect polynomial and P a prime divisor of A. Then ω(A) ≥ 10, deg(P) ≥ 30, deg(P) is even, and P ≡ 1 (mod x^{2} + x + 1).

Gallardo and Rahavandrainy [6, Lemma 2.6]) also proved the following.

Lemma 4. Let P be a Mersenne prime and m a positive integer. Then σ(P^{2m}) is square-free.

We now have two more results.

Lemma 5. Let P be a Mersenne polynomial (prime or not) and n ∈ ℕ such that S = 1 + P + ⋯ + P^{2^{n}−1} is perfect. Then P = 1 + (x^{2} + x)^{a} with a = \frac{2^{m}−1}{2^{n}−1} for some multiple m of n.

Proof. Put P = 1 + x^{a}(x + 1)^{b}. The polynomial S = 1 + P + ⋯ + P^{2^{n}−1} = (1 + P)^{2^{n}−1} = (x^{a}(x + 1)^{b})^{2^{n}−1} is trivial perfect. So, (2^{n} − 1)a = (2^{n} − 1)b = 2^{m} − 1 for some integer m. Thus, a = b and 2^{n} −1 divides 2^{m} −1. Therefore, 2^{n} −1 = gcd(2^{n} −1, 2^{m} −1) = 2^{gcd(n,m)} −1, i.e., n divides m.

Lemma 6. Let P be a prime in 𝔽_{2}[x] and let h be a positive integer. Then σ(P^{2h}) is not a square.

Proof. Assume, contrary to what we want to prove, that A = σ(P^{2h}) is a square in 𝔽_{2}[x]. Thus A′ = 0, where A′ is the formal derivative of A relative to x. Observe that P′ ≠ 0. Since A = (1 + P)(1 + P + ⋯ + P^{h−1})^{2} + P^{2h}, one has

A′ = P′(1 + P + ⋯ + P^{h−1})^{2} ≠ 0, a contradiction.

This proves the lemma.

Remember that a positive integer n ∈ ℕ is perfect if σ(n) = 2n (a property which is equivalent to the definition used in the paragraph after Lemma 2).

Lescot [9] recently proved the following:

Theorem 7. Consider the following equation in which σ(n) is the sum of all positive divisors of n.

σ(n) = (σ(n) − 2n)^{2}.  (1)

One has (a) If n satisfies (1) and if n is a prime power, then n ∈ {1, 3}.

(b) If m is a perfect number for which 2m − 1 is a prime number, then n = m(2m − 1) satisfying (1).

(c) If n satisfies (1) and if n is even, then there is an even perfect number m such that n/m = 2m − 1.

We cannot generalize condition (1) to 𝔽_{2}[x]. Indeed, by considering degrees, the equation σ(A) = (σ(A) − 2A)^{2} in 𝔽_{2}[x] implies that σ(A) ∈ {0, 1}. So, it has only the trivial solutions A = 0 or A = 1. However, a generalization of (1) to the equation σ(A) = C^{2} in 𝔽_{2}[x], is possible. There are many solutions, e.g., A = x^{4} + x and C = x^{2} + x, in which C divides A, or A = x^{6} + x^{4} + x^{3} + x and C = x^{3} + x^{2}, in with C does not divide A. Even adding more constraints, such as C | A or ω(A) = ω(C), one has (for example) a solution A = x(x^{2} + x + 1)(x + 1)^{5} and C = x(x + 1)(x^{2} + x + 1). The full solution of the equation might be very difficult to obtain, since a possible solution is A = C^{2}, with C^{2} being an odd perfect polynomial. Since in characteristic 2, the analogue of squares are indeed the expressions of the form C^{2} + C, a possible appropriate generalization would be the following equation in the unknown A,

σ(A) = C^{2} + C.  (2)

Remark 8. There are many solutions of (2); for example, A = x^{4} + x^{3} + x^{2} and C = x^{2} + x or A = x^{4} + x and C = x^{2}. One non-trivial possibility is to ask for solutions of (2) with A = P, a prime polynomial, so that a complete solution of (2) amounts to finding all prime polynomials P ∈ 𝔽_{2}[x] of the form P = C^{2} +C +1. We found some of them by computation, e.g., {(P = x^{2}+x+1, C = x), (P = x^{4}+x+1, C = x^{2}+x), (P = x^{8}+x^{6}+x^{4}+x^{3}+x^{2}+x+1, C = x^{4}+x^{3}+x}, but a complete theoretical description of all solutions appears to be out of reach.

As an analogue to (1) over the ring 𝔽_{2}[x], we propose, instead, the following condition (in which the polynomial A is the unknown). Condition 9. A in 𝔽_{2}[x] satisfies

σ(A) + A is perfect.  (3)

It might be impossible to find all polynomials A for which Condition 9 holds.

Observe that any prime polynomial P satisfies (3), since 1 is perfect. Moreover, any perfect polynomial A also satisfies (3), since 0 is a perfect polynomial, but (warning!) it is currently impossible (to our knowledge) to give examples of perfect polynomials besides those already described. Moreover, for a given perfect polynomial M ∈ 𝔽_{2}[x]\𝔽_{2}, possible solutions A of the equation σ(A)+A = M have a degree that exceeds the degree of M, since both A and σ(A) are monic with same degree. Hence, there are potentially infinitely many candidates A to check, so that we cannot find all solutions of the equation by means of a computer. We checked the special case where M = M_{5a} = x(x+1)^{2}(x^{2}+x+1) = x^{5}+x^{4}+x^{2}+x for all A up to degree 8. Indeed, it suffices to check the A’s with 6 ≤ deg(A) ≤ 8, finding two solutions, A = x^{7}+x^{4}+x^{2}+x = x(x+1)^{3}(x^{3}+x^{2}+1), and A = x^{7}+x^{6}+x^{4}+x^{3} = x^{3}(x^{2}+x+1)(x+1)^{2}.

More generally, we obtain the following result:

Theorem 10. (i) Let A ∈ 𝔽_{2}[x] be such that (3) holds.

(a) If A = P^{k}, with P prime and k > 1, then k is even.

(b) If A = P^{2^{n}}, with P a Mersenne prime and n ≥ 2, then P = 1 + x + x^{2}, so that A = (1 + x + x^{2})^{2^{n}}.

(c) If A = P^{2^{n}u}, with P a Mersenne prime, n ≥ 1 and u ≥ 3 odd, then P = 1+x+x^{2}, and (1 + P + ⋯ + P^{u−1})^{2^{n}} is odd perfect.

(d) Assume that n = 1 in (c). Put R = 1 + P + ⋯ + P^{u−1} (with P = 1 + x + x^{2}). Then R is square-free, S = R^{2} is odd perfect, ω(S) ≥ 10, u ≥ 4391, so that deg(S) ≥ 17560, the degree of every prime divisor Q of R is even, and Q ≡ 1 (mod P). Moreover, if Q is a prime divisor of R that has the minimal possible degree, then deg(Q) ≥ 30.

(e) If A = B · K, with B = σ(A) + A and gcd(B, K) = 1, then σ(K) = K + 1.

(ii) If B ∈ 𝔽_{2}[x] is a nonzero perfect polynomial, K ∈ 𝔽_{2}[x] is prime not dividing B, then A = B · K satisfies (3).

Remark 11. Inspired by Theorem 10(c), let P = x^{2} + x + 1 ∈ 𝔽_{2}[x], n be a non-negative integer, and v ∈ ℕ. If A = (1 + P + ⋯ + P^{2^{v}−1})^{2^{n}} is perfect, then n = 0 and A is trivial perfect. Indeed,

A = (\frac{1 + P^{2^{v}}}{1 + P} )^{2^{n}} = (1 + P^{2^{n}})^{2^{v}−1} = (1 + P)^{2^{n}·(2^{v}−1)} = (x(x + 1))^{2^{n}·(2^{v}−1)}.  (4)

The result now follows from (4) and [2, Lemma 1]. However, for completeness and clarity, we give the details. Let a = 2^{n}(2^{v} − 1). Since A is perfect, we get from (4) that x^{a}(x + 1)^{a} = σ(x^{a})σ((x + 1)^{a}). Thus (x + 1)^{a} divides σ(x^{a}). Comparing degrees we get

σ(x^{a}) = (x + 1)^{a}.  (5)

We claim that n = 0. Assume, contrary to what we want to prove, that n ≥ 1. Then (5) is impossible since (x + 1)^{a} is a square in 𝔽_{2}[x]. But 1 + x + ⋯ + x^{a} is not a square in 𝔽_{2}[x], hence a = 2^{v} − 1. This proves the result.

2 Some computational results

1. We set R_{u}^{2^{n}} = (1 + P + ⋯ + P^{u−1})^{2^{n}} (with P = 1 + x + x^{2}) in part (c) of Theorem 10. Then, by using a straightforward gp-PARI program, we checked that for every odd number u with 1 < u < 4391, one has R_{u}^{2} ≠ σ(R_{u}^{2}). The computation took about 30 hours. As a consequence, we obtained in (d) that R_{u}^{2} is not perfect for all odd numbers u between 3 and 4389. We also considered the cases when n = 2 and n = 3, with a reduced upper bound for u. More precisely, we obtained that R_{u}^{4} is not perfect when u is odd and 1 < u < 4001, and that R_{u}^{8} is not perfect when u is odd, and 1 < u < 2001. The whole computation, including the case n = 1, took about 50 hours.

2. Let u > 1 be an odd integer, n a positive integer, and P any odd polynomial in 𝔽_{2}[x], and R_{u} = 1 + P + ⋯ + P^{u−1}. Inspired by part (c) of Theorem 10, in which a possible new odd perfect polynomial appears, one might ask the more general (and possibly unanswerable) question:

Is R_{u}^{2^{n}} perfect ?

In the special case when R_{u} is prime, the answer is clearly no. However, consider, for instance, the case when ω(R_{u}) > 1 and R_{u} is square-free (cf. Lemma 4, when P is a Mersenne prime and ω(R_{u}) > 1). In this case, we are unable to give an answer. In the special case when P = x^{2} + x + 1, it follows by computation, that one may conjecture that R_{u} is prime if and only if u is a prime number such that 2 is a primitive root modulo u (i.e., u belongs to the OEIS sequence \underline{A001122}). Surely, by [11, Theorem 2.47], 1 + x + ⋯ + x^{u−1} is prime if and only if u belongs to the sequence \underline{A001122} and u − 1 belongs to the sequence \underline{A071642}.

3. An odd integer 2m−1 appears when considering perfect numbers, since an even perfect number has the form n = m(2m − 1), with m = 2^{p−1} and a prime number 2m − 1 = 2^{p} − 1, as observed in the Introduction. But in 𝔽_{2}[x] we do not know the form of a general perfect polynomial. There is no “natural” candidate to replace 2m − 1. Moreover, it is easy to check that a positive integer p is prime if and only if σ(p) = p + 1, whereas for an A ∈ 𝔽_{2}[x], only the implication: A prime ⟹ σ(A) = A + 1 is correct. For example, when the degree of A is at most 10, the polynomials A ∈ {x^{4} + x^{2}, x^{10} + x^{9} + x^{8} + x^{6} + x^{5} + x^{4} + 1} are composite, since x^{4} + x^{2} = x^{2}(x + 1)^{2} and x^{10} + x^{9} + x^{8} + x^{6} + x^{5} + x^{4} + 1 = (x^{3} + x + 1)(x^{3} + x^{2} + 1)(x^{4} + x + 1). However, one has σ(A) = A + 1.

Furthermore, we do not know what happens when k > 2 in Theorem 10(a). Indeed, we do not know what happens, even in the case when k = 2, provided that A is not Mersenne.

In fact, when k = 2, all known primes P for which σ(P^{2}) + P^{2} = P + 1 is perfect, belong to {x^{2} +x+1, x^{5} +x^{2} +1, x^{5} +x^{4} +x^{2} +x+1}. This is proved by a computation when P = M + 1, and M is sporadic perfect. The proof when M is trivial perfect, i.e., when M = (x(x + 1))^{2^{n}−1} for some positive integer n, is as follows. One can see that P = M + 1 = (x(x + 1))^{2^{n}−1} + 1 is divisible by x^{2} + x + 1, provided that n ≥ 2. Thus, P is prime only in the special case when n = 1, for which we obtain P = x^{2} + x + 1.

Thus, for k = 2, the non-trivial case remains unknown: P is a prime such that, with A = P^{2}, one has that M = σ(A) + A = 1 + P is an even perfect polynomial of degree d ≥ 201 (see Proposition 1).

3 Proof of Theorem 10

(i) (a) Assume, contrary to what we want to prove, that S = σ(P^{k}) + P^{k} = σ(P^{k−1}) is perfect, but k > 1 is odd. By Lemma 6 we obtain that S is not a square. Thus, S is not a square and S is odd. This contradicts Lemma 2.

(b) In this case, A = P^{k} with k = 2^{n}, and P is Mersenne prime. Put P = x^{a}(x+1)^{b}+1 for some positive integers a, b. One has that S = σ(P^{k}) + P^{k} = σ(P^{2^{n}−1}) = (1 + P)^{2^{n}−1} = (x^{a}(x + 1)^{b})^{2^{n}−1}. Hence, S is trivial perfect and a = b by Lemma 5. But P prime implies that a = b = 1. So, A = (x^{2} + x + 1)^{2^{n}}.

(c) Put P = 1+x^{a}(x+1)^{b} and Q(u) = σ(P^{u−1}). Observe that σ(A)+A = σ(P^{k−1}) = K · L where K = (1 + P)^{2^{n}−1} and L = Q(u)^{2^{n}}. Observe also that u odd implies that K, L are coprime. Since K · L is perfect and K, L are coprime, one has

K · L = σ(K) · σ(L).  (6)

We claim that K and σ(L) are coprime. In order to prove the claim, it suffices to prove that D = gcd(1 + P, σ(L)) equals 1. Since 1 + P = x^{a}(x + 1)^{b}, in order to prove that D = 1, it suffices to prove that σ(L) is odd. By Lemma 4, Q(u) = ∏_{j=1}^{r} Q_{j} for some positive integer r and for some pairwise distinct, odd prime polynomials Q_{j}. Then one has

σ(L) = ∏_{j=1}^{r} σ(Q_{j}^{2^{n}}).  (7)

Since n ≥ 1, 2^{n} is even. Thus, by substituting x = 0 and x = 1 in any σ(Q_{j}^{2^{n}}) we obtain 1. In other words, σ(Q_{j}^{2^{n}}) is odd for any j. It follows then from (7) that σ(L) is odd, thereby proving the claim. Since gcd(K, σ(L)) = 1, it follows from (6) that K divides σ(K), and even that K = σ(K) since K and σ(K) have the same degree. Again, (6) implies that L = σ(L). It follows that L is odd and perfect. Finally, by part (b), K = σ(K) implies that P = 1 + x + x^{2}. This proves the result.

(d) By Lemma 4, R is square-free, since P is Mersenne prime. Putting n = 1 in part (c), we obtain that S is odd perfect and that P = 1 + x + x^{2}. Since S is a special perfect polynomial, all the other statements, besides the numerical lower bound of u, follow from Lemma 3. A simple computation in gp-PARI proves that for any odd number 1 < u ≤ 4389 one has S ≠ σ(S), so that u ≥ 4391 and deg(S) = 2 deg(R) = 4(u − 1) ≥ 17560, thereby proving the result.

(e) One has σ(A) = σ(B)σ(K) = Bσ(K) because B is perfect. On the other side, σ(A) = A + B = BK + B = B(K + 1). Therefore, σ(K) = K + 1, since B is nonzero.

Let us now compute S = A+σ(A). One has S = BK +σ(B)σ(K) = BK +B(K +1) = B, since σ(B) = B and σ(K) = K + 1. Thus S = B is perfect.

4 Acknowledgments

We are grateful to the referee and to the editor for detailed comments. We thank Reinhardt Euler and Rob Scott for help on removing many English mistakes.

References

[1] R. P. Brent, S. Larvala, and P. Zimmermann, A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377, Math. Comput. 72 (2003), 1443–1452.

[2] E. F. Canaday, The sum of the divisors of a polynomial, Duke Math. J. 8 (1941), 721–737.

[3] U. C. Cengiz, P. Pollack, and E. Treviño, Counting perfect polynomials, Finite Fields Appl. 47 (2017), 242–255.

[4] H. M. Fredricksen and R. Wisniewski, On Trinomials x^{n} + x^{2} + 1 and x^{8l±3} + x^{k} + 1 irreducible over GF (2), Inf. Control 50 (1981), 58–63.

[5] L. H. Gallardo and O. Rahavandrainy, Odd perfect polynomials over 𝔽_{2}, J. Théor. Nombres Bordeaux 19 (2007), 165–174.

[6] L. H. Gallardo and O. Rahavandrainy, Characterization of sporadic perfect polynomials over 𝔽_{2}, Funct. Approx. Comment. Math. 55 (2016), 7–21.

[7] L. H. Gallardo and O. Rahavandrainy, There is no odd perfect polynomial over 𝔽_{2} with four prime factors, Port. Math. 66 (2009), 131–145.

[8] L. H. Gallardo and O. Rahavandrainy, On Mersenne polynomials over 𝔽_{2}, Finite Fields Appl. 59 (2019), 284–296.

[9] P. Lescot, On an arithmetical question related to perfect numbers, Math. Gaz. 104 (2020), 20–26.

[10] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2019.

[11] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, Cambridge University Press, 1996.

[12] R. G. Swan, Factorization of polynomials over finite fields, Pacific J. Math. 12 (1962), 1099–1106.

[13] N. Zierler, On x^{n} + x + 1 over GF (2), Inf. Control 16 (1970), 502–505.

2010 Mathematics Subject Classification: Primary 11T55; Secondary 11T06. Keywords: sum of divisors, perfect polynomial, finite field, characteristic 2.

(Concerned with sequences \underline{A001037}, \underline{A001122}, and \underline{A071642}.)

Received February 29 2020; revised versions received August 3 2020; August 4 2020; September 3 2020; October 2 2020. Published in Journal of Integer Sequences, October 11 2020.

Return to Journal of Integer Sequences home page.