# J. T. B. Beard's algorithm to catch perfect polynomials

For any monic polynomial $P$ with coefficients in a finite field of order $q$, we put

$$\sigma(P) = \sum_{d \mid P, d \text{ monic}} d.$$

Observe that $P$ and $\sigma(P)$ have the same degree.

EDIT. $A$ means the full ring of polynomials in one variable $t$ over the finite field with $q$ elements.

Since there are a finite number of polynomials of a given degree in $A$ the sequence $$P, \sigma(P), \sigma(\sigma(P)), \ldots$$ must contain two equal terms.

The following algorithm (of J. T. B. Beard) seems to catch monic polynomials $P \in A$ with $\sigma(P)=P$ when $q$ is a prime number.

(i) Take $R=R_0$ a well chosen polynomial in $A.$

(ii) If $R=\sigma(R)$ STOP and output $R.$

(ii) if $R \neq \sigma(R)$ then replace $R$ by $$lcm(R,\sigma(R))$$ and come back to (ii)

Question: Take $q=2.$ For which polynomials $R_0$ l'algorithm stops after a finite number of steps. Assume that a polynomial $P \in A$ satisfies $P=\sigma(P).$ There exists a polynomial $R_0 \neq P$ and $R_0 \neq P(t+1),$ such that by taking $R=R_0$ in (i) the algorithm stops after a finite number of steps and outputs $P$?

Example: With $R_0=t$ we catch $P=t(t+1)$ that satisfies $P=\sigma(P).$ More involved examples can be obtained with a small computer program; (or by hand depending on taste...).

EDIT1: I tried recently to catch J. T. B. Beard himself to ask for this algorithm (and many other related questions in my mind...) but I got only some (nice) comments from people close to him in his last known position in the usa. No more news about him known by myself.

-
Is $A$ the set of monic polynomials of a fixed degree, or?! – Igor Rivin Jan 20 '11 at 1:26
Hum, I'm not sure if I understand you right. But given the definition, since $P | P$, then is what you are looking equivalent to $P$ such that $\sum_{d|P, d\neq p} d = 0$? Calling it "perfect" (even if it is established usage) feels a bit misleading to me. – Willie Wong Jan 20 '11 at 1:55
Have you done any experiments with $q=2$ to see for which polynomials the procedure seems to terminate? – Gerry Myerson Jan 20 '11 at 2:41
@Willie: Perhaps multiperfect is better. The idea is: multiperfect over the integers means loosely: $n$ divides $\sigma(n)$, so the notion can be also defined in $A$. But then you are forced to take $P=\sigma(P)$ since $P$ divides $\sigma(P)$ implies $P=\sigma(P)$ in $A.$ While over the integers you can take $\frac{\sigma(n)}{n}$ whatever you want (e.g. $=2$: define perfects, $=3$ define $3$-multiperfect numbers, $=8$: etc, etc.) over $A$ there is just one choice; (for the definition above of $\sigma$ of course). – Luis H Gallardo Jan 20 '11 at 9:03
@Willie, Luis: A more standard definition of $\sigma(P)$ (e.g. in Rosen Number Theory in Function Fields) is the sum of $\lvert d\rvert$ over monic d dividing P, which may explain the confusion. – Thomas Bloom Jan 20 '11 at 13:08