The number of decomposable univariate polynomials. extended abstract
Joachim von zur Gathen · 2009
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 an approximation to the number of decomposable polynomials 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. A centerpiece of our approach is a decomposition algorithm in the wild case, which shows that sufficiently many polynomials are decomposable.