Decomposition of Algebraic Functions

Functional decomposition—whether a functionf(x) can be written as a composition of functionsg(h(x)) in a non-trivial way—is an important primitive in symbolic computation systems. The problem of univariate polynomial decomposition was shown to have an efficient solution by Kozen and Landau (1989). Dickerson (1987) and Gathen (1990a) gave algorithms for certain multivariate cases. Zippel (1991) showed how to decompose rational functions. In this paper, we address the issue of decomposition of algebraic functions. We show that the problem is related to univariate resultants in algebraic function fields, and in fact can be reformulated as a problemofresultant decomposition. We characterize all decompositions of a given algebraic function up to isomorphism, and give an exponential time algorithm for finding a non-trivial one if it exists. The algorithm involves genus calculations and constructing transcendental generators of fields of genus zero.