Census of Polynomials

Census of Polynomials

The Prime Number Theorem and a well-known result of Gauss count (approximately or exactly) the number of prime (or irreducible) elements in $\mathbb{Z}$ or  $\mathbb{F}_{q}[x]$. Leonard Carlitz, Stephen Cohen, and others considered multivariate polynomials. We now have an exact formula for their number, and similarly for squareful and relatively irreducible (irreducible and not absolutely irreducible) polynomials, and approximations for the decomposable ones.

This talk reports results on univariate decomposable polynomials $f= g \circ h = g(h) \in \mathbb{F}_{q}[x]$. The \emph{tame case}, where the characteristic $p$ of $\mathbb{F}_{q}$ does not divide $n = \degf$, is fairly well-understood, and we obtain closely matching upper and lower on the number of decomposable polynomials. In the opposite \emph{wild case}, the bounds are less satisfactory.

The core of this talk deals with the easiest instance of the wild case, where $n = p^{2}$. We may assume $g$ and $h$ to have degree $p$ and to be monic and original, that is, with constant coefficient $0$.

Besides the trivial case of $p$th power, the additive polynomials $f=x^{p^{2}} + ax^{p} + bx$ are of interest, but we exclude them from this talk.

Any $(g,h)$ yields a decomposable $f = g \circ h$, and the crux of the matter is to count the number of \emph{collisions}, where different $(g,h)$ yield the same $f$. Abhyankar introduced the \emph{projective polynomial} $\psi= y^{p+1}-uy+u$. There is an intimate connection between collisions and the roots of $\psi$. As an example, suppose that $l \mid p-1$, $m=(p-1)/l$ and $t \in \mathbb{F}_{q}^{\times}$ is a root of $\psi$. Then \begin{align*}f = x(x^{l(p+1)}-ux^{l}+u)& =(x(x^{l}-ut^{-1}))\circ (x(x^{l}-t)^{m})\\&= g \circ h.\end{align*}
While $g$ and $h$ depend on $t$, $f$ does not. Thus two distinct roots of $\psi$ yield a collision.

There is another, similar, type of collision from different roots of $\psi$. The main result is that these are all possibilities.

Work in progress is to simplify the current proof of this result which relies on the ramification theory of function fields, and to determine exactly the number of such collisions.

joint work with: Raoul Blankertz, Mark Giesbrecht, Alfredo Viola, Konstantin Ziegler.