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

2011-01-19T23:29:33Z

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.

J. T. B. Beard's algorithm to catch `perfect polynomials` - MathOverflow

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