Counting decomposable univariate polynomials

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.

References in corpus (5)

• Composite lacunary polynomials and the proof of a conjecture of Schinzel
• Indecomposable polynomials and their spectrum
• On Ritt's decomposition Theorem in the case of finite fields
• Compositions and collisions at degree p^2
• Normal form for Ritt's Second Theorem

Cited by in corpus (2)

• Normal form for Ritt's Second Theorem
• A recombination algorithm for the decomposition of multivariate rational functions