Counting decomposable univariate polynomials

DOI10.1017/S0963548314000388MaRDI QIDQ5364223zbMATH OpenFDO

Authors Joachim von zur Gathen

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.0054

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomials over finite fields (11T06) Polynomials in general fields (irreducibility, etc.) (12E05) Special polynomials in general fields (12E10)

Abstract: A univariate polynomial f over a field is decomposable if it is the composition f = g(h) of two polynomials g and h whose degree is at least 2. We determine the dimension (over an algebraically closed field) of the set of decomposables, and an approximation to their number over a finite field. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well understood, and we obtain exponentially decreasing error bounds. The wild case, where p divides n, is more challenging and our error bounds are weaker.

Recommendations

• The number of decomposable univariate polynomials
• Lower bounds for decomposable univariate wild polynomials
• Survey on counting special types of polynomials
• Counting decomposable multivariate polynomials
• Tame decompositions and collisions

Cites work

• scientific article; zbMATH DE number 3765926 (Why is no real title available?)
• scientific article; zbMATH DE number 1467743 (Why is no real title available?)
• scientific article; zbMATH DE number 1827103 (Why is no real title available?)
• Compositions and collisions at degree \(p^2\)
• Counting decomposable multivariate polynomials
• Counting reducible and singular bivariate polynomials
• Decomposition of algebraic functions
• Functional decomposition of polynomials: the tame case
• Functional decomposition of polynomials: the wild case
• Indecomposable polynomials and their spectrum
• Lower bounds for decomposable univariate wild polynomials
• Normal form for Ritt's second theorem
• On Ritt's decomposition theorem in the case of finite fields
• On composite lacunary polynomials and the proof of a conjecture of Schinzel
• Polynomial decomposition algorithms
• Prime and composite polynomials
• Ritt's Second Theorem in arbitrary characteristic.
• Sur la composition des polynômes
• The number of decomposable univariate polynomials

Cited in

(13)

• On decomposition of sub-linearised-polynomials
• Counting invariant subspaces and decompositions of additive polynomials
• Compositions and collisions at degree p^2
• Counting decomposable multivariate polynomials
• Survey on counting special types of polynomials
• Interpolation by decomposable univariate polynomials
• Compositions and collisions at degree \(p^2\)
• An approximate decomposition of a multivariate polynomial and its application
• Tame decompositions and collisions
• The number of decomposable univariate polynomials
• Lower bounds for decomposable univariate wild polynomials
• Counting decomposable polynomials with integer coefficients
• Tame decompositions and collisions

This page was built for publication: Counting decomposable univariate polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364223)