Counting polynomials over finite fields: Random properties and algorithms
Daniel Panario (Carleton University, Canada)
In this talk we survey old and new results about counting univariate polynomials over finite fields. For example, we are interested in questions such as:
- How many irreducible factors a polynomial is expected to have?
- How often will it be squarefree or k-free?
- What is the expected largest (smallest) degree among its irreducible factors?
- How is the degree distribution among its irreducible factors?
- How often a polynomial is m-smooth (all irreducible factors of degree ≤m)?
- How often two polynomials are m-smooth and coprime?
- How is the degree distribution among the irreducible factors of the gcd of several polynomials?
- What is the expected degree of the splitting field of a polynomial?
We show a methodology that can be systematically employed to study this type of problems. This framework has two basic components: generating functions to express the properties of interest, and asymptotic analysis when exact estimations are not possible. This generic methodology naturally relates finite fields and their applications to combinatorics, number theory, and average-case analysis of polynomial factorization algorithms.
Talk slides (PDF).