Counting classes of special polynomials
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 | https://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. | en |
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 |
Files in this item
This item appears in the following Collection(s)
-
E-Dissertationen (4162)