Mathematics and Algorithms for Computer AlgebraPart 1c 1992 Dr Francis J. Wright – CBPF, Rio de JaneiroJuly 9, 20034: Polynomial algebra1 DefinitionsLet {x1, x2, . . . , xn} be a (finite) set of n symbols and let R be a commutativering with unity.Definition 1 The polynomials over R in the variables x1, x2, . . . , xnarethe formal sumsp =Xi1,...,in∈Npi1,...,inxi11· · · xinn,where the coefficients pi1,...,inare elements of R and only a finite num-ber of them are nonzero. The set of all such polynomials is denoted byR[x1, x2, . . . , xn].A polynomial of the form pi1,...,inxi11· · · xinnwith precisely one nonzerocoefficient is called a monomial. The monomorphism R → R[x1, x2, . . . , xn],c 7→ cx01· · · x0n, identifies the ground ring R with a subset of R[x1, x2, . . . , xn],and therefore a monomial of the form cx01· · · x0nis denoted simply c andcalled a constant (or occasionally a constant polynomial).If m, n ∈ N, 1 ≤ m < n, there is a natural isomorphismR[x1, . . . , xm][xm+1, . . . , xn] ∼ R[x1, x2, . . . , xn].The notation can be simplified by definingXipixi=Xi1,...,in∈Npi1,...,inxi11· · · xinn1in terms of the multi-index i = (i1, . . . , in), wherei + j = (i1+ j1, . . . , in+ jn) and xi= xi11· · · xinn.Then if p, q ∈ R[x1, x2, . . . , xn], c ∈ R, polynomial addition and multi-plication are defined byp + q =Xi(pi+ qi)xi, pq =XkXi,j, i+j=k(piqj)xk,where special cases of multiplication arecp =Xi(cpi)xi, − p =Xi(−pi)xi.With these operations R[x1, x2, . . . , xn] is a commutative ring with a unityelement which is the constant polynomial p = 1.If p =Pipixiis nonzero (i.e. at least one coefficient is nonzero) then thetotal degree of p isdeg p = max{i1+ · · · + in| pi6= 0}and the partial degree of p with respec t to xjisdegxjp = max{ij| pi6= 0},which is sometimes also denoted degjp.2 Arithmetic, simplification and rational expres-sionsIn an algebraic context there is no difference between performing arithmeticoperations and simplifying arithmetic expressions. Assuming that a canoni-cal representation is being used, then an arithmetic expression composed ofrational expressions is in general not in canonical form, even if the compo-nent rational expressions themselves are. The process of simplifying such anexpression requires any arithmetic operations to be performed first. If nec-essary, the result must then be put into canonical representation, althoughprobably the result of performing the arithmetic will already be canonical.Arithmetic on rational functions is completely analogous to arithmeticon rational numbers, if the integer operations underlying rational arithmetic2are replaced by operations on (possibly multivariate) polynomials. Hence,arithmetic on rational expressions is straightforward, given algorithms toperform multivariate polynomial addition, subtraction, multiplication andgcd computations, and I will not discuss it in further detail.Univariate polynomial arithmetic is analogous to integer arithmetic inwhich the integer base B is replaced by the p olynomial variable, which I willcall x. However, a polynomial has more structure than an integer, whichactually makes polynomial arithmetic simpler because there are no carriesbetween different powers of x. I will assume that the polynomials havecoefficients in some ring R, w hich might in fact be a field, and might beeither infinite or finite. Assuming the existence of algorithms to performarithmetic in the coefficient ring, the algorithms to perform the polynomialring operations are independent of the details of the coefficient ring R. I willdiscuss the complexity of polynomial arithmetic in terms of the number ofarithmetic operations required in R, but this is not the true total complexity,which does depend on the details of the R, and may depend on the size ofthe coefficients, as we saw would be the case if R = Z.2.1 Polynomial addition and subtractionIn the univariate case, the algorithm to add two polynomials p, q is essentiallythe same as the integer algorithm, and just requires a loop to run throughthe terms of the polynomials, in which the number of coefficient operationsis min(deg p, deg q) + 1. (Since there are no carries there is no compellingreason to increase this bound to max(deg p, deg q) + 1 as there was in theinteger case.) Just as for integers, subtraction can be performed using p−q =p+(−q). If it is reasonable to assume that negating the coefficients is a trivialoperation then the number of coefficient operations is min(deg p, deg q) + 1as for addition, otherwise it is deg q+1. The number of coeffic ient operationsfor either addition or subtraction is certainly O(max(deg p, deg q)).2.2 Polynomial multiplicationClassical univariate polynomial multiplication follows the first (unsatisfac-tory) integer multiplication algorithm. If m = deg p, n = deg q then there are(m+1)(n+1) coefficient multiplications and (m+1)(n+1)−(m+n−1) coef-ficient additions, so the number of coefficie nt operations required is O(mn).There are significantly faster polynomial multiplication algorithms based onthe fast Fourier transform (FFT), and analogous to the fastest integer multi-3plication algorithms. However, these fast algorithm are only as ymptoticallyfaster, which in practice means only for very high degrees.2.3 Multivariate polynomialsArithmetic on multivariate polynomials (multinomials) is accomplished bytaking advantage of the natural isomorphism referred to above, and regard-ing R[x1, x2, . . . , xr] as R[x1, . . . , xr−1][xr]. Then arithmetic on polynomialsin r variables is carried out by recursion on r; the routines call themselvesif r 6= 0 or call their analogues for performing arithmetic in the appropriatecoefficient domain if n = 0 (which is the base case that terminates the recur-sion). Note that this recursive approach to multinomial arithmetic matchesnicely with the recursive representation discussed in Notes 1.In order to bound the complexity of multinomial arithmetic, let us as-sume that the partial degrees of p, q ∈ R[x1, x2, . . . , xr] with respect to anyvariable are bounded respectively by m, n; then p, q contain respectivelyat most (m + 1)rand (n + 1)rmonomials. The complexity of multivariatearithmetic depe nds on the number of terms in each polynomial as in the uni-variate case, and hence the number of coefficient operations required to addor subtract p and q is O(max(m, n)r), and to multiply them is O((mn)r).3 Euclidean division and