BIB-VERSION:: CS-TR-v2.1
ID:: CORNELLCS//TR94-1410
ENTRY:: 1995-07-31
REVISION:: July 31, 1995; to fix typo in tag
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Decomposition of Algebraic Functions
AUTHOR:: Kozen, Dexter
AUTHOR:: Landau, Susan 
AUTHOR:: Zippel, Richard
DATE:: February 1994
PAGES:: 24
ABSTRACT::
Functional decomposition--whether a function $f(x)$ can be written as a 
composition of functions $g(h(x))$ in a nontrivial 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 [8]. Dickerson [5] and von zur Gathen [11] gave algorithms for certain 
multivariate cases. Zippel [13] 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 problem of resultant 
decomposition. We give an algorithm for finding a nontrivial decomposition of 
a given algebraic function if it exists. The algorithm involves genus 
calculations and constructing transcendental generators of fields of genus 
zero.
END:: CORNELLCS//TR94-1410
BODY::
Decomposition of Algebraic Functions
Dexter Kozen*
Susan Landau**
Richard Zippel*
TR 94-1410
February 1994
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
* Computer Science Department, Cornell University, Ithaca, NY 14853.
** Computer Science Department, University of Massachusefts, Amherst, MA 01003.
Decomposition of Algebraic Functions
Dexter Kozen*
Cornell University
kozen?cs.cornell.edu
Susan Landaut
University of Massachusetts, Amherst
landau?cs umass.edu
Richard Zippel*
Cornell University
rz?cs.cornell.edu
February 8,1994
Abstract
Functional decomposition whether a function f(r) can be written as a composi-
tion of functions g(h(x)) in a nontrivial 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 [8]. Dickerson [5] and von zur Ga-
then [11] gave algorithms for certain multivariate cases. Zippel [13] 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 ?dds,
and in fact can be reformulated as a problem of resultant decomposition. We give an
algorithm for finding a nontrivial decomposition of a given algebraic function if it exists.
The algorithm involves genus calculations and constructing transcendental generators
of fields of genus zero.
1 Introduction
Fnnctional decomposition is the problem of representing a given function f(x) as a compo-
sition of "smaller" functions g(h(x)). Decomposition of polynomials is useful in simplifying
the representation of field extensions of high degree, and is provided as a primitive by all
major symbolic algebra systems.
The first analyzed algorithms for polynomial decomposition were provided in 1985 Barton
and Zippel [2] and Alagar and Thanh [?], who gave algorithms for the problem of decom-
posing univariate polynomials over fields of characteristic zero. Both solutions involved
polynomial factorization and took exponential time. Kozen and Landan [8] discovered a
*Computer Science Department, Cornell University, Ithaca, NY 14853
tComputer Science Department, University of Massachusetts, Amherst, MA 01003
simple and efficient polynomial time solution that does not require factorization and works
in characteristic zero and whenever the degree of h does not divide the characteristic of the
underlying field, and NC algorithms for irreducible polynomials over finite fields and all
polynomials over characteristic zero. Dickerson [5] and von zur Gathen [11] gave algorithms
for certain multivariate cases. In addition, von zur Gathen also found algorithms for the
case in which the degree of h divides the characteristic of the field [12]. Zippel [13] showed
how to decompose rational functions.
In this paper we address the decomposition problem for algebraic functions. We show
that the problem bears an interesting and useful relationship to univariate resultants over
algebraic function fields, and in fact can be reformulated as a certain resultant decomposition
problem: whether some power of a given irreducible bivariate polynomial f(x, z) can be
expressed as the resultant with respect to y of two other bivariate polynomials g(x, y),
h(y, z). We determine necessary and sufficient conditions for an algebraic function to have a
nontrivial decomposition, and classify all such decompositions up to isomorphism. We give
an exponential-time algorithm for finding a nontrivial decomposition of a given algebraic
function if one exists. The algorithm involves calculating the genus of certain algebraic
function fields and constructing transcendental generators of fields of genus zero.
The paper is organized as follows. In 2, we review the basic properties of univariate
resultants, state the decomposition problem for algebraic functions, and describe the re-
lationship between the two. In 3 we prove a general theorem that characterizes the set
of all possible decompositions of an algebraic function. In 4 we give an exponential time
algorithm for the decomposition problem. We conclude in 5 with an example.
2 Resultants and Algebraic Functions
2.1 The Univariate Resultant
Here we review some basic facts about the univariate resultant; see [7, 14] for a detailed
introduction.
The resnitant of two polynomials
g(y) =
with respect to y is the polynomial
res?(g,h) =
afl(y--Hoi)
bf[(y--HPj)
j=1
= bm
anbm H(P5 --H
fi 9(p).
h(p)=o
The resultant vanishes iff 9 and h have a common root. It can be calculated as the determi-
nant of a certain (m + n) x + n) matrix containing the coefficients of 9 and A.
2
The following are some useful etementary properties.
res?(g,h) = (?l)mnres?(h,g)
res?(gig2, h)			=			res?(gi, h)			res?(g?, A)
res?(g, h1A2)			=			res?(g, A1)			res?(g, A2)
res?(c,A)			=
res?(?,l)			=			res?(l,A)			= 1
res?(y,y--HQ)			=			9(p)
We extend the definition to pairs of rational functions 91(Y)/92(Y) and h1(y)/A2(y) as
follows:
res?(91, h1 = ?r?e5Yy((9?:AA?)?r?eSf?((9?2:A2)
92
This quantity is defined if neither 91, A2 nor 92, h1 have a common root. It is easily checked
that this definition reduces to the previous one in the case of polynomials, and that all the
properties listed above still hold, taking m = deggi --H deg?2 and n = deg A1 --H deg A2.
2.2 R,esultants and Decomposition
Algebraic functions of z over K are usually defined as elements of some finite extension
of K(z), the field of rational functions of z. Over algebraically closed fields K, they can
be represented more concretely as multivalued functions K H 2K or binary relations on
K defined by their minimum polynomials. Let K be algebraically closed, and let a be an
algebraic function of ? with irreducible equation f(a, ?) = 0, f(x, z) e K[x, z]. Let
V(f) = ?(a,c) I f(a,c) = 0)			C K2
be the irreducibte affine curve generated by f. We say that a is decomposable if there
exist polynomials y(x,y) and A(y,z) such that V(f) = V(g) 0 V(A), the relation-theoretic
composition of the curves V(g) and V(A). The relational composition operator 0 can be
expressed algebraically in terms of the univariate resultant:
V(f) = V(g) 0 V(A)
= ?(i,c) ?bE K (a,b) c V(g), (b,c) c V(A))
= t(a,c) I 3bE K g(a,b) = 0, h(b,c) = 0)
= ?(a, c) I resy(9(a, y), A(y, c)) = 0)
= V(res?(9(x,y),A(y,z)))
By the Nullstellensatz, this occurs iff
f(x,z)k = res?(?(x,y),A(y,z))
(1)
for some k > 0. Regarding f(x, z)k and f(x, z) as representations of the same curve, the
decomposilion problem then becomes: given an irreducible polynomial f(x, z), do there exist
polynomials 9(x, y) and A(y, z) and a positive integer k such that fk = res?(?, A)?
3
Under this definition, every bivariate polynomial f is decomposable in infinitely many
ways:
2.4 Monic Decompositions
resy(f(x,yk),yk --H			=
II f(x,pk)
Pk=z
fi f(x,z)
pk=z
fk
(2)
However, these decompositions are trivial in a sense to be made precise in the next sec-
tion. We will show that up to isomorphism there are only finitely many nontrivial minimal
decompositions.
2.3 Irreducible Decompositions
A nontrivial decomposition f = res?(y, h) is called irreducible if both g and h are irreducible
as polynomials in K[x, y] and K[y, z], respectively. By the multiplicativity of the resultant,
every decomposition factors into a product of irreducible decompositions.
A decomposition f = res?(g, h) is called monic if g E K(y)[x] and h E K(z)[y] are monic.
The next result says that we can restrict our attention to monic decompositions without loss
of generality.
Then
Lemma 1 Let f ? K[x,z], ? e K[x,yJ, h E K[y,z], g, h irreducible,
irreducible polynomial. Let f, g, and h be the monic associates of?f,
K(y)[x], and K(z)[y] respectively. Then f = res?(g,h) iff f= res?(g,h).
f a power of an
g, h in K(z)[x],
Proof. Let fn(z), gm(y), and he(z) be the lead coefficients of f, g and h, respectively. Let
u(z) = res?(gm, h). ?d?e??Q?dc??9rn
res?(g, h) = res,(gm, h) res?(g, h?) res?(g, ?)
But since g and ? are monic, so is res?(g, ?), therefore if f = res?(g, h) = u res?(g, ?), then
u = f? and f= res?(g%h).
Conversely, if f = res?(g, h), then uf = j4res?(g, h). Remove common factors to get
vf = w res?(g, h), where v, w ? K[z] are relatively prime. Now f has no factor in K[z],
so w ?s a unit. Likewise, if v were of nonzero degree, then it would have a root a e K,
and res?(g(x, y), h(y, a)) would vanish identically. But this can happen only in degenerate
cases in which one of g, h does not depend on one of its variables, contrary to assumption.
Therefore v is also a unit.			5
4
3 A Characterization of All Decompositions
In this section we give a characterization of all possible irreducible decompositions of an
algebraic function that can arise. We assume that K is algebraically closed.
Let ? be transcendental over K. We work in a fixed algebraic closure ? of K(?). Let a be
a nonconstant algebraic function of ? with monic minimum polynomial f(x, ?) e K(?)[x] of
degree n. By results of the previous section, the functional decomposition problem reduces
to the problem of finding all monic irreducible decompositions of the form
f(x,?)k = res?(g(x,y),h(y,?))
--H fi g(x,P).
Let A be the set of conjugates of a over K(?), IA = n. Let Sym A denote the field
symmetric functions of A. This is the smallest field containing all the coefficients of f(x, ?).
Note that Sym A properly contains K, for otherwise f(x, ?) would factor into linear factors
since K is algebraically closed, contradicting the assumption that a is nonconstant.
Now consider the following condition on algebraic functions ? of ?:
Condition 2 The minimum polynomialg(x,P) of a over `((P) divides f(x,?).
If p is algebraic over K(?), then g exists, since a is algebraic over K(?) and ? is algebraic over
K(P). A subtle but important point to note is that Condition 2 does not imply that f(x, ?)
factors over K(P). Indeed, K(P) need not contain the coefficients of f or f/g. We give an
example of this in Section 5. The following theorem states that any P satisfying Condition 2
uniquely determines a monic irreducible decomposition of a; moreover, all monic irreducible
decompositions of a arise in this way.
Theorem 3 Let a be an algebraic function of ? with monic minimal polynomial f(x, ?) Ei
K(?)[x] of degree n. Let p be algebraic over K(?) with monic minimal polynomial h(y, ?) E
K(?)[y] of degree . Let g(x, P) ? K(P)[x] of degree in be the monic minimal polynomial of
a over K(P). If? satisfies Condition 2, i.e. if g(x, P) divides f(x, ?), then
f(x,z)Unm = res?(g(x,y),h(y,z))
is a monic irreducible decomposition of a. Moreover, all monic irreducible decompositions
of a arise in this way.
Proof. Let B = Bp C A be the set of roots of g(x,P). If ?I is a conjugate of ? over
K(?), let B? be the set of roots of g(x, n). The set B? is the image of B under any Calois
automorphism over K(?) mapping t3 to n For any such conjugate n? IB?I = IBI = in and
c A since the Galois group over K(?) preserves A setwise.
By the symmetry of the action of the Calois group on A, each 6 ? A occurs in the same
number of the B?, say k. We determine k by counting in two ways the number of pairs (6, n)
such that ? Ei B?. First, it is the number of conjugates ? of ? times the size of each B?, or
?in. Second, it is the number of 6 c A times the number of B? containing 6, or nk. Equating
5
these two values gives k = rn/n, the exponent in the statement of the theorem. Moreover,
it follows from the same argument that
f(x,?)k = fl(x??)k
--H 6EA? H(x--H?
h(?,?)=O 6EB?
- fi y(x,?)
--H res?(y(x,y),h(y,?))
Since ? is transcendental over K, we might as well replace it with the indeterminate z to get
f(x,z)k = res?(y(x,y),h(y,z))
The decomposition is monic and irreducible by definition.
Now we show that every monic irreducible decomposition of ? arises in this way. Suppose
f(x,z)k = res?(g(x,y),h(y,z))
is such a decomposition. Let p be a common root of g(o, y) and h(y, ?). Such a ? exists,
since f(a, ?) vanishes, hence so does the resultant res?(g(o, y), h(y, ?)). Then ? is algebraic
over K(?) with minimum polynomial h(y, ?), g(x, ?) is the minimum polynomial of ? over
K(p), and
f(x,?)k = res?(g(x,y),h(y,?))
- fi g(x,?).
Since g(x, P) is one of the factors in the product, it divides f(x, ?).			5
At this juncture we make a few observations about minimal decompositions and unique-
ness.
Minimal decompositions There may exist ? of arbitrarily high degree over K(?) satis-
fying Condition 2. For example, for any k, ? = ?k? gives the decomposition
--H z)k = res?(x --H ?k, ?k --H
This is also the situation with (2) above. However, we can bound the search as follows.
Observe that if there exists a ? satisfying Condition 2 with factor g(x, ?) of f, say with
roots B C A, then a will have the same degree over any subfield of K(?) containing the
coefficients of 9. Furthermore, any such subfield is again a purely transcendental extension
of K by L'iwth's Theorem (see [10, 14]), so a transcendental generator of that subfield would
give a decomposition with the same g and smaller degree A and smaller k. For a given g,
the degree of A and exponent k are minimized by taking the smallest subfield containing the
coefficients of 9, namely Sym B.
6
Nontrivial decompositions If the minimum polynomial g(x, p) of & over A'(P) is f (as
would occur in the case = ?), then the minimal decomposition with this g occurs when
? is a transcendental generator of Sym A. Since Sym A C A?(?), ? would be a rational
function of ? and h would be linear of the form y --H u(?), u E K(z), giving the decomposition
f(x,z) = res?(g(x,y),y--Hu(z))
= g(x,u(z))
In this case & is the composition of an algebraic function and a rational function.
In case g(x, ?) is linear, say g = x --H v(P), the smallest field containing the coefficients of
g is K(v(P)), so by using v(P) instead of P we would obtain the trivial decomposition
f(x,z) = res?(x--Hy,h(y,z))
--H h(x,z)
To find a nontrivial decomposition, we must find a ? such that k(f3) does not contain &.
Uniqueness up to linear composition factors The decomposition determined by p
essentially depends only on the field I??(P), not on the choice of transcendental generator P.
Any other transcendental generator of A'(P) is related to P by a nonsingular fractional linear
transformation
aP+b
c?+d ` ad--Hbc#O,
which extends to an automorphism of K(p). Any two decompositions defined with respect
to two transcendental generators of the same field are equivalent up to invertible composition
factors of the form (cz + d)y --H (az + b).
One can see from the above observations that up to fractional linear transformations,
there are only finitely many minimal irreducible monic decompositions, at most one for each
subset of A. We have thus reduced the decomposition problem to the problem of finding a
subset B C A such that the field Sym B is a purely transcendental extension of K, and
then finding a transcendental generator Pof Sym B. Such a ? is automatically algebraic
over K(?), since Sym B C K(A), the splitting field of f over
The problem of determining whether a given field extension K(&i,... , &n) is a purely
transcendental extension is essentially the problem of determining the genus of algebraic
function fields. We discuss these issues in the next section.
4 An Algorithm
As determined in the previous section, the key question in decomposing an iueducible poly-
nomial f is determining whether f has a factor g whose coefficients lie in a purely transcen-
dental extension of k. Equivalently, we want to know when the field Sym B of symmetric
functions in the roots B of g is isomorphic to a rational function field over K, i.e. is of genus
zero. We outline our approach in the following procedure.
7
1. Let K(?, ?) be a finite extension of K(?) over which f factors, and let g be one of the
monic irreducible factors. The coefficients of g all lie in K(?, ?), so 9 can be written
For each such 9, perform steps 2 and 3.
2. Let u be one of the coefficients Uj of 9 not in K. Construct the field K(uo,... , urn-i).
This is the field Sym B, where B is the set of roots of 9. We have two cases:
(a) If K(uo,...,um--Hi) = K(u), we are done: u is a transcendental generator of
Sym B.
If K(uo,... , um?i) # K(u), construct a primitive element 0 of the extension such
that K(uo,... ,um?i) = K(u,O). Compute the genus of K(u,O) by the Hurwitz
genus formula or in some other fashion. An efficient algorithm is given in [3].
If the genus is nonzero, then no decomposition arises from this factor of f. If
the genus is zero, compute a rational generator p of K(u, 0). Coates [4], Trager
[9], and Huang and lerardi [6] give efficient algorithms for computing rational
generators. The coefficients of 9 can then be written as rational functions of ?.
3. Let h(y, ?) be the minimal polynomial of ? over A'(?). Return g(x, y) and h(y, z) as
the decomposition factors.
Under suitable assumptions about the complexity of operations in K, the complexity
of the algorithm as given above is exponential in the worst case, since there are an expo-
nentially many potential factors. For each such factor, the computation for that factor can
be performed in polynomial time in the size of the representation of the algebraic numbers
needed to express the result, or exponential time in the bit complexity model [6].
5 An Example
The following gives an example of a decomposition involving a ? such that g(x, P) divides
f(x, ?), but f(x, ?) does not factor over K(P). Consider the polynomial
f(x,z) = x4 --Hzx2(r+1)+z3(r+l)2
Let ? be transcendental over K, and let
2
2
--H x2--Hy(xtl)
--H 2 ?? + ?3
8
g(x,y)
h(y,z)
Then ? and ? are conjugates over K(?) with minimum polynomial h(y, ?), and
thus Theorem 3 says that g and h should give a decomposition of f. Indeed,
0			1
res?(g(x,y),h(y,z)) =			x2			--H(x+1) --Hz			= f(x,z)
0			x2			z3
To show f(x, ?) does not factor over A?(?), it suffices to show that its trace ? is not in K(P).
But ? is a root of the irreducible polynomial h(p, z), therefore is algebraic of degree three
over
Acknowledgement5
We thank John Little, Paul Pedersen, Moss Sweedler and Barry Trager for their help.
This work was supported by the U.S. Army Research Office through the ACSyAM branch
of the Mathematical Sciences Institute of Cornell University under contract DAAL03-91-C-
0027, the National Science Foundation under grants CCR-9204630 and CCR-8806096, and
the Advanced Research Projects Agency of the Department of Defense under Office of Naval
Research grant N00014-92-J-1989. This work was performed while the second author was
visiting the Cornell University Computer Science Department.
References
[1] V. 5. ALAGAR AND M. THANH, Fast polynomial decomposition alyorithms, in Proc. EURO-
CAL85, Springer-Verlag Lect. Notes in Comput. Sci. 204, 1985, pp. 150 153.
[2] D. R. BARToN AND R. E. ZIPPEL, Polynomial decomposition algorithms, J. Symb. Comp., 1
(1985), pp. 159--H168.
[3] G. A. BLISS, Algebraic Functions, Amer. Math. Soc., 1933.
[4] J. CoATES, Construction of rational functions on a curve, Proc. Camb. Phil. Soc., 68 (1970),
pp. 105--H123.
[5] M. DICKERSoN, Polynomial decomposition algorithmsfor multivariate polynomials, Tech. Rep.
TR87-826, Comput. Sci., Cornell Univ., April 1987.
[6] M.-D. HUANG AND D. lERARDI, Efficient algorithms for the effective Riemann-Roch problem
and for addition in the Jacobian of a curve, in Proc. 32nd Symp. Found. Comput. Sci., IEEE,
November 1991.
[7] D. lERARDI AND D. KoZEN, Parallel resultant computation, in Synthesis of Parallel Aigo-
rithms, J. Reif, ed., Morgan Kaufn?ann, 1993, pp. 679--H720.
[8] D. KoZEN AND 5. LANDAU, Polynomial decomposition aigorithms, J. Symb. Comput., 7
(1989), pp. 445--H456.
9
[9] B. M. TRAGER, Integration of Algebraic Functions, PliD thesis, Massachusetts Institute of
Technology, Cambridge, MA, September 1984.
[10] B. L. VAN DER WAERDEN, Algebm, vol. t, Frederick Ungar, fifth ed., 1970.
[11] J. V0N ZUR GATHEN, Functional decomposition of polynomials: the tame case, J. Symb.
Comput., 9 (1990), pp. 281--H299.
[12] , Functional decomposition of polynomials: the wild case, J. Symb. Comput., 10 (1990),
pp. 437--H452.
(13] R. E. ZIPPEL, Rational function decomposition, in International Symposium on Symbolic and
Algebraic Computation, 5. Watt, ed., New York, July 1991, ACM, pp. 1--H6.
[14] , Effective Polynomial Computation, Kiuwer Academic Press, Boston, 1993.
10
