Factorization Patterns in F_<i>q</i> [<i>x</i>]

Abstract

The finite field F q has q elements, where q = p k for prime p and k ∈ N. Then F q [ x ] is a unique factorization domain and its polynomials can be bijectively associated with their unique (up to order) factorizations into irreducibles. Such a factorization for a polynomial of degree n can be viewed as conforming to a specific template if we agree that factors with higher degree will be written before those with lower degree, and factors of equal degree can be written in any order. For example, a polynomial f ( x ) of degree n may factor into irreducibles and be written as ( a )( b )( c ), where deg a ≥ deg b ≥deg c . Clearly, the various partitions of n correspond to the templates available for these canonical factorizations and we identify the templates with the possible partitions. So if f ( x ) is itself irreducible over F q , it would belong to the template [ n ], and if f ( x ) split over F q , it would belong to the template [n] Our goal is to calculate the cardinalities of the sets of polynomials corresponding to available templates for general q and n. With this information, we characterize the associated probabilities that a randomly selected member of F q [ x ] belongs to a given template. Software to facilitate the investigation of various cases is available upon request from the authors.