Show simple item record

Counting classes of special polynomials

dc.contributor.advisorvon zur Gathen, Joachim
dc.contributor.authorZiegler, Konstantin
dc.description.abstractMost integers are composite and most univariate polynomials over a finite field are reducible. The Prime Number Theorem and a classical result of Gauß count the remaining ones, approximately and exactly.
In two or more variables, the situation changes dramatically. Most multivariate polynomials are irreducible. We present counting results for some special classes 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). These numbers come as exact formulas and as approximations with relative errors that essentially decrease exponentially in the input size.
Furthermore, a univariate polynomial f over a field F is decomposable if f = g o h with nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials. The tame case, where the characteristic p of F does not divide n = deg f, is fairly well understood, and the upper and lower bounds on the number of decomposable polynomials of degree n match asymptotically. In the wild case, where p does divide n, the bounds are less satisfactory, in particular when p is the smallest prime divisor of n and divides n exactly twice.
There is an obvious inclusion-exclusion formula for counting. The main issue is then to determine, under a suitable normalization, the number of collisions, where essentially different components (g, h) yield the same f. In the tame case, Ritt's Second Theorem classifies all collisions of two such pairs. We provide a normal form for collisions of any number of compositions with any number of components. This generalization yields an exact formula for the number of decomposable polynomials of degree n coprime to p. For the wild case, we classify all collisions at degree n = p^2 and obtain the exact number of decomposable polynomials of degree p^2.
dc.rightsIn Copyright
dc.subjectunivariate polynomials
dc.subjectmultivariate polynomials
dc.subjectfinite fields
dc.subjectcounting special polynomials
dc.subjectenumerative combinatorics on polynomials
dc.subjectanalytic combinatorics
dc.subjectgenerating functions
dc.subjectcomputer algebra
dc.subjecttame polynomial decomposition
dc.subjectwild polynomial decomposition
dc.subjectRitt's Second Theorem
dc.subject.ddc510 Mathematik
dc.titleCounting classes of special polynomials
dc.typeDissertation oder Habilitation
dc.publisher.nameUniversitäts- und Landesbibliothek Bonn
ulbbnediss.affiliation.nameRheinische Friedrich-Wilhelms-Universität Bonn
ulbbnediss.instituteMathematisch-Naturwissenschaftliche Fakultät : Fachgruppe Informatik / Institut für Informatik
ulbbnediss.fakultaetMathematisch-Naturwissenschaftliche Fakultät
dc.contributor.coRefereeFranke, Jens

Files in this item


This item appears in the following Collection(s)

Show simple item record

The following license files are associated with this item: