Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields. (English) Zbl 1348.11094

von zur Gathen, Joachim; Viola, Alfredo; Ziegler, Konstantin

SIAM J. Discrete Math. 27, No. 2, 855-891 (2013).

Authors’ abstract: We present counting methods for some special cases of multivariate polynomials over a finite field, namely, the reducible ones, the \(s\)-powerful ones (divisible by the \(s\)th power of a nonconstant polynomial), and the relatively irreducible ones (irreducible but reducible over an extension field). One approach employs generating functions, and another one uses a combinatorial method. They yield exact formulas and approximations with relative errors that essentially decrease exponentially in the input size.

Reviewer: Astrid Reifegerste (Magdeburg)

MSC:

11T06	Polynomials over finite fields
12E20	Finite fields (field-theoretic aspects)
12Y05	Computational aspects of field theory and polynomials (MSC2010)
05A15	Exact enumeration problems, generating functions

Keywords:

multivariate polynomials; finite fields; combinatorics on polynomials; counting problems; generating functions; analytic combinatorics