Counting decomposable multivariate polynomials
arXiv:0811.4726
Abstract
A polynomial f (multivariate over a field) is decomposable if f = g(h) with g univariate of degree 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 relative error in our approximations is exponentially decaying in the input size.
v2: 21 pages, simplification in the proof of Theorem 4.1