Factorization patterns on nonlinear families of univariate polynomials over a finite field

Abstract

We estimate the number $|{\mathcal{A}}_{\mathbf{\lambda }}|$ of elements on a nonlinear family $\mathcal{A}$ of monic polynomials of ${\mathbb{F}}_q[T]$ of degree $r$ having factorization pattern $\mathbf{\lambda }:=1^{{\lambda }_1}{2}^{{\lambda }_2}\cdots r^{{\lambda }_r}$. We show that $|{\mathcal{A}}_{\mathbf{\lambda }}|=\mathcal{T}(\mathbf{\lambda })q^{r-m}+\mathcal{O}(q^{r-m-1/2})$, where $\mathcal{T}(\mathbf{\lambda })$ is the proportion of elements of the symmetric group of $r$ elements with cycle pattern $\mathbf{\lambda }$ and $m$ is the codimension of $\mathcal{A}$. We provide explicit upper bounds for the constants underlying the $\mathcal{O}$--notation in terms of $\mathbf{\lambda }$ and $\mathcal{A}$ with "good" behavior. We also apply these results to analyze the average--case complexity of the classical factorization algorithm restricted to $\mathcal{A}$, showing that it behaves as good as in the general case.

37 pages