Counting decomposable multivariate polynomials (Q429753)

A polynomial \(f\) in \(r\) variables over a field \(F\) is decomposable if \(f=g\circ h\) with \(g\) univariate of degree at least 2. The author determines the dimension of the set of decomposables of degree \(\leq n\) when \(F\) is an algebraically closed field. He also finds an approximation to their number when \(F\) is the finite field of order a prime power. Further, he proves that the bound is exponentially decreasing in the input size. The methods used are derived by those developed by the author while studying reducible bivariate polynomials [Finite Fields Appl. 14, No. 4, 944--978 (2008; Zbl 1192.12003)]. From this it is shown that there are many more reducible or relatively irreducible bivariate polynomials than decomposable polynomials. The paper cites 21 references.