## Counting classes of special polynomials dc.contributor.advisor von zur Gathen, Joachim dc.contributor.author Ziegler, Konstantin dc.date.accessioned 2020-04-20T21:52:02Z dc.date.available 2020-04-20T21:52:02Z dc.date.issued 20.04.2015 dc.identifier.uri http://hdl.handle.net/20.500.11811/6450 dc.description.abstract Most 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.language.iso eng dc.rights In Copyright dc.rights.uri http://rightsstatements.org/vocab/InC/1.0/ dc.subject univariate polynomials dc.subject multivariate polynomials dc.subject finite fields dc.subject counting special polynomials dc.subject enumerative combinatorics on polynomials dc.subject analytic combinatorics dc.subject generating functions dc.subject computer algebra dc.subject tame polynomial decomposition dc.subject wild polynomial decomposition dc.subject Ritt's Second Theorem dc.subject.ddc 510 Mathematik dc.title Counting classes of special polynomials dc.type Dissertation oder Habilitation dc.publisher.name Universitäts- und Landesbibliothek Bonn dc.publisher.location Bonn dc.rights.accessRights openAccess dc.identifier.urn https://nbn-resolving.org/urn:nbn:de:hbz:5n-39813 ulbbn.pubtype Erstveröffentlichung ulbbnediss.affiliation.name Rheinische Friedrich-Wilhelms-Universität Bonn ulbbnediss.affiliation.location Bonn ulbbnediss.thesis.level Dissertation ulbbnediss.dissID 3981 ulbbnediss.date.accepted 02.04.2015 ulbbnediss.institute Mathematisch-Naturwissenschaftliche Fakultät : Fachgruppe Informatik / Institut für Informatik ulbbnediss.fakultaet Mathematisch-Naturwissenschaftliche Fakultät dc.contributor.coReferee Franke, Jens
﻿