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

2018/07/20 by Matera, Guillermo, Pérez, Mariana, Privitelli, Melina
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1807.08052

Abstract

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

Related

• The distribution of factorization patterns on linear families of polynomials over a finite field
• On the enumeration of polynomials with prescribed factorization pattern
• Patterns In The Coefficients Of Powers Of Polynomials Over A Finite Field
• Factorization Statistics of Restricted Polynomial Specializations over\n Large Finite Fields
• Polynomial Factorization over Finite Fields By Computing Euler-Poincare Characteristics of Drinfeld Modules