On coefficients of powers of polynomials and their compositions over finite fields

Abstract

For any given polynomial $f$ over the finite field ${\mathbb{F}}_q$ with degree at most $q-1$, we associate it with a $q\times q$ matrix $A(f)=(a_{ik})$ consisting of coefficients of its powers $(f(x){)}^k={\sum }_{i=0}^{q-1}{a}_{ik}{x}^i$ modulo $x^q-x$ for $k=0,1,\dots ,q-1$. This matrix has some interesting properties such as $A(g\circ f)=A(f)A(g)$ where $(g\circ f)(x)=g(f(x))$ is the composition of the polynomial $g$ with the polynomial $f$. In particular, $A(f^{(k)})=(A(f){)}^k$ for any $k$-th composition $f^{(k)}$ of $f$ with $k\ge 0$. As a consequence, we prove that the rank of $A(f)$ gives the cardinality of the value set of $f$. Moreover, if $f$ is a permutation polynomial then the matrix associated with its inverse $A(f^{(-1)})=A(f{)}^{-1}=PA(f)P$ where $P$ is an antidiagonal permutation matrix. As an application, we study the period of a nonlinear congruential pseduorandom sequence $\bar{a}=\{a_0,a_1,a_2,...\}$ generated by $a_n=f^{(n)}(a_0)$ with initial value $a_0$, in terms of the order of the associated matrix. Finally we show that $A(f)$ is diagonalizable in some extension field of ${\mathbb{F}}_q$ when $f$ is a permutation polynomial over ${\mathbb{F}}_q$.