Exceptional polynomials and the reducibility of substitution polynomials (Q922594)

Let \(F_ q\) denote the finite field of order \(q=p^ t\) with p prime. For a polynomial \(f\in F_ q[x]\), define \(\phi_ f(x,y)=f(y)-f(x)\) and let \(\phi_ f^*(x,y)=\phi_ f(x,y)/(y-x)\). Then f of degree \(>1\) is said to be an exceptional polynomial (EP) over \(F_ q\) if none of the irreducible factors of \(\phi_ f^*(x,y)\) over \(F_ q\) is absolutely irreducible, i.e. remains irreducible over \(\bar F_ q\), the algebraic closure of \(F_ q\). If one combines EPs with each other and with linear polynomials, then all known EPs come from cyclic polynomials, Dickson polynomials, linearized polynomials, and a fourth class of polynomials defined below. Thus to classify EPs it is sufficient to classify polynomials which are indecomposable under polynomial composition. The author obtains the following classification of indecomposable polynomials f for which \(\phi_ f\) is divisible by an irreducible quadratic over \(\bar F_ q\). In particular he proves: Let f(x) be an indecomposable polynomial in \(F_ q[x]\) such that \(\phi_ f\) is divisible by an irreducible quadratic over \(\bar F_ q\). Then \(f(x)=\alpha f^*(x+\beta)+\gamma\) where \(\alpha \neq 0,\beta,\gamma \in F_ q\) and either \(f^*\) is a Dickson polynomial of odd prime degree not equal to p or p is odd and \(f^*\) is a (p,2)-polynomial in \(C_ 4.\) The fourth class \(C_ 4\) of EPs indicated above is defined as follows. A linearized polynomial L has the form \(L(x)=\sum^{k}_{i=0}a_ ix^{p^ i}\). Suppose for \(s\geq 1\), \(a_ i=0\) unless \(s| i\). Then L is called a \(p^ s\)-polynomial.Let \(d>1\) be an integer with \(d| (p^ s-1)\) and \(p\nmid d\). Then \(L(x)=xM(x^ d)\) for some M(x). Let \(S(x)=xM^ d(x)\). Then the polynomial S is called a \((p^ s,d)\)- polynomial. The \((p^ s,d)\)-polynomials provide a fourth class \(C_ 4\) of EPs. The author also raises several questions and provides a framework for future research into the classification of EPs.