J. T. B. Beard's algorithm to catch perfect polynomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T03:23:04Z http://mathoverflow.net/feeds/question/52560 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52560/j-t-b-beards-algorithm-to-catch-perfect-polynomials J. T. B. Beard's algorithm to catch perfect polynomials Luis H Gallardo 2011-01-19T23:29:33Z 2011-01-21T14:01:26Z <p>For any monic polynomial $P$ with coefficients in a finite field of order $q$, we put</p> <p>$$\sigma(P) = \sum_{d \mid P, d \text{ monic}} d.$$</p> <p>Observe that $P$ and $\sigma(P)$ have the same degree.</p> <p>EDIT. $A$ means the full ring of polynomials in one variable $t$ over the finite field with $q$ elements.</p> <p>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. </p> <p>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.</p> <p>(i) Take $R=R_0$ a <code>well chosen</code> polynomial in $A.$</p> <p>(ii) If $R=\sigma(R)$ STOP and output $R.$</p> <p>(ii) if $R \neq \sigma(R)$ then replace $R$ by $$lcm(R,\sigma(R))$$ and come back to (ii)</p> <p>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$?</p> <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...).</p> <p>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.</p>