Algebraic Operations on Polynomials

For many kinds of practical calculations, the only operations you will need to perform on polynomials are essentially structural ones.

If you do more advanced algebra with polynomials, however, you will have to use the algebraic operations discussed in this tutorial.

You should realize that most of the operations discussed in this tutorial work only on ordinary polynomials, with integer exponents and rational-number coefficients for each term.

Reduction of polynomials.

Given two polynomials p(x) and q(x), one can always uniquely write ((p(x))/(q(x)))==a(x)+((b(x))/(q(x))), where the degree of b(x) is less than the degree of q(x). (RefLink[PolynomialQuotient, paclet:ref/PolynomialQuotient]) gives the quotient a(x), and (RefLink[PolynomialRemainder, paclet:ref/PolynomialRemainder]) gives the remainder b(x).

This gives the remainder from dividing (x^2) by 1+x:

PolynomialRemainder[x^2,x+1,x]

Here is the quotient of (x^2) and x+1, with the remainder dropped:

PolynomialQuotient[x^2,x+1,x]

This gives back the original expression:

Simplify[(x+1)%+%%]

Here the result depends on whether the polynomials are considered to be in x or y:

{PolynomialRemainder[x+y,x-y,x],PolynomialRemainder[x+y,x-y,y]}

(RefLink[PolynomialMod, paclet:ref/PolynomialMod]) is essentially the analog for polynomials of the function (RefLink[Mod, paclet:ref/Mod]) for integers. When the modulus m is an integer, (RefLink[PolynomialMod, paclet:ref/PolynomialMod])[poly,m] simply reduces each coefficient in poly modulo the integer m. If m is a polynomial, then (RefLink[PolynomialMod, paclet:ref/PolynomialMod])[poly,m] effectively tries to get a polynomial with as low a degree as possible by subtracting from poly appropriate multiples q m of m. The multiplier q can itself be a polynomial, but its degree is always less than the degree of poly. (RefLink[PolynomialMod, paclet:ref/PolynomialMod]) yields a final polynomial whose degree and leading coefficient are both as small as possible.

This reduces (x^2) modulo x+1. The result is simply the remainder from dividing the polynomials:

PolynomialMod[x^2,x+1]

In this case, (RefLink[PolynomialMod, paclet:ref/PolynomialMod]) and (RefLink[PolynomialRemainder, paclet:ref/PolynomialRemainder]) do not give the same result:

{PolynomialMod[x^2,a x+1],PolynomialRemainder[x^2,a x+1,x]}

The main difference between (RefLink[PolynomialMod, paclet:ref/PolynomialMod]) and (RefLink[PolynomialRemainder, paclet:ref/PolynomialRemainder]) is that while the former works simply by multiplying and subtracting polynomials, the latter uses division in getting its results. In addition, (RefLink[PolynomialMod, paclet:ref/PolynomialMod]) allows reduction by several moduli at the same time. A typical case is reduction modulo both a polynomial and an integer.

This reduces the polynomial (x^2)+1 modulo both x+1 and 2:

PolynomialMod[x^2+1,{x+1,2}]

(RefLink[PolynomialGCD, paclet:ref/PolynomialGCD])[(Subscript[poly, 1]),(Subscript[poly, 2])] finds the highest degree polynomial that divides the (Subscript[poly, i]) exactly. It gives the analog for polynomials of the integer function (RefLink[GCD, paclet:ref/GCD]).

(RefLink[PolynomialGCD, paclet:ref/PolynomialGCD]) gives the greatest common divisor of the two polynomials:

PolynomialGCD[(1-x)^2 (1+x) (2+x),(1-x) (2+x) (3+x)]

(RefLink[PolynomialExtendedGCD, paclet:ref/PolynomialExtendedGCD]) gives the extended greatest common divisor of the two polynomials:

{g,{r,s}}=PolynomialExtendedGCD[x^3+2x^2-x+1,x^4+x+2,x]

The returned polynomials r and s can be used to represent the GCD in terms of the original polynomials:

r(x^3+2x^2-x+1)+s(x^4+x+2) //Expand

The function (RefLink[Resultant, paclet:ref/Resultant])[(Subscript[poly, 1]),(Subscript[poly, 2]),x] is used in a number of classical algebraic algorithms. The resultant of two polynomials a and b, both with leading coefficient one, is given by the product of all the differences (Subscript[a, i])-(Subscript[b, j]) between the roots of the polynomials. It turns out that for any pair of polynomials, the resultant is always a polynomial in their coefficients. By looking at when the resultant is zero, you can tell for what values of their parameters two polynomials have a common root. Two polynomials with leading coefficient one have k common roots if exactly the first k elements in the list (RefLink[Subresultants, paclet:ref/Subresultants])[(Subscript[poly, 1]),(Subscript[poly, 2]),x] are zero.

Here is the resultant with respect to y of two polynomials in x and y. The original polynomials have a common root in y only for values of x at which the resultant vanishes:

Resultant[(x-y)^2-2,y^2-3,y]

The function (RefLink[Discriminant, paclet:ref/Discriminant])[poly,x] is the product of the squares of the differences of its roots. It can be used to determine whether the polynomial has any repeated roots. The discriminant is equal to the resultant of the polynomial and its derivative, up to a factor independent of the variable.

This polynomial has a repeated root, so its discriminant vanishes:

Discriminant[(x-1)^2,x]

This polynomial has distinct roots, so its discriminant is nonzero:

Discriminant[x^4-1,x]

Gröbner bases appear in many modern algebraic algorithms and applications. The function (RefLink[GroebnerBasis, paclet:ref/GroebnerBasis])[{(Subscript[poly, 1]),(Subscript[poly, 2]),…},{(Subscript[x, 1]),(Subscript[x, 2]),…}] takes a set of polynomials, and reduces this set to a canonical form from which many properties can conveniently be deduced. An important feature is that the set of polynomials obtained from (RefLink[GroebnerBasis, paclet:ref/GroebnerBasis]) always has exactly the same collection of common roots as the original set.

The (((x+y))^2) is effectively redundant, and so does not appear in the Gröbner basis:

GroebnerBasis[{(x+y),(x+y)^2},{x,y}]

The polynomial 1 has no roots, showing that the original polynomials have no common roots:

GroebnerBasis[{x+y,x^2-1,y^2-2x},{x,y}]

The polynomials are effectively unwound here, and can now be seen to have exactly five common roots:

GroebnerBasis[{x y^2+2 x y+x^2+1,x y+y^2+1},{x,y}]

(RefLink[PolynomialReduce, paclet:ref/PolynomialReduce])[poly,{(Subscript[p, 1]),(Subscript[p, 2]),…},{(Subscript[x, 1]),(Subscript[x, 2]),…}] yields a list {{(Subscript[a, 1]),(Subscript[a, 2]),…},b} of polynomials with the property that b is minimal and (Subscript[a, 1])(Subscript[p, 1])+(Subscript[a, 2])(Subscript[p, 2])+…+b is exactly poly.

This writes (x^2)+(y^2) in terms of x-y and y+a, leaving a remainder that depends only on a:

PolynomialReduce[x^2+y^2,{x-y,y+a},{x,y}]

Functions for factoring polynomials.

(RefLink[Factor, paclet:ref/Factor]), (RefLink[FactorTerms, paclet:ref/FactorTerms]), and (RefLink[FactorSquareFree, paclet:ref/FactorSquareFree]) perform various degrees of factoring on polynomials. (RefLink[Factor, paclet:ref/Factor]) does full factoring over the integers. (RefLink[FactorTerms, paclet:ref/FactorTerms]) extracts the "content" of the polynomial. (RefLink[FactorSquareFree, paclet:ref/FactorSquareFree]) pulls out any multiple factors that appear.

Here is a polynomial, in expanded form:

t=Expand[2 (1+x)^2 (2+x) (3+x)]

(RefLink[FactorTerms, paclet:ref/FactorTerms]) pulls out only the factor of 2 that does not depend on x:

FactorTerms[t,x]

(RefLink[FactorSquareFree, paclet:ref/FactorSquareFree]) factors out the 2 and the term (((x+1))^2), but leaves the rest unfactored:

FactorSquareFree[t]

(RefLink[Factor, paclet:ref/Factor]) does full factoring, recovering the original form:

Factor[t]

Particularly when you write programs that work with polynomials, you will often find it convenient to pick out pieces of polynomials in a standard form. The function (RefLink[FactorList, paclet:ref/FactorList]) gives a list of all the factors of a polynomial, together with their exponents. The first element of the list is always the overall numerical factor for the polynomial.

The form that (RefLink[FactorList, paclet:ref/FactorList]) returns is the analog for polynomials of the form produced by (RefLink[FactorInteger, paclet:ref/FactorInteger]) for integers.

Here is a list of the factors of the polynomial in the previous set of examples. Each element of the list gives the factor, together with its exponent:

FactorList[t]

Factoring polynomials with complex coefficients.

(RefLink[Factor, paclet:ref/Factor]) and related functions usually handle only polynomials with ordinary integer or rational-number coefficients. If you set the option (RefLink[GaussianIntegers, paclet:ref/GaussianIntegers])->(RefLink[True, paclet:ref/True]), however, then (RefLink[Factor, paclet:ref/Factor]) will allow polynomials with coefficients that are complex numbers with rational real and imaginary parts. This often allows more extensive factorization to be performed.

This polynomial is irreducible when only ordinary integers are allowed:

Factor[1+x^2]

When Gaussian integer coefficients are allowed, the polynomial factors:

Factor[1+x^2,GaussianIntegers->True]

Irreducibility testing.

A polynomial is irreducible over a field F if it cannot be represented as a product of two nonconstant polynomials with coefficients in F.

This polynomial is irreducible over the rationals:

IrreduciblePolynomialQ[x^2+4]

Over the Gaussian rationals, the polynomial is reducible:

IrreduciblePolynomialQ[x^2+4,GaussianIntegers->True]

By default, algebraic numbers are treated as independent variables:

IrreduciblePolynomialQ[x^2+2 Sqrt[2]x+2]

Over the rationals extended by (RefLink[Sqrt, paclet:ref/Sqrt])[2], the polynomial is reducible:

IrreduciblePolynomialQ[x^2+2 Sqrt[2]x+2,Extension->Automatic]

Cyclotomic polynomials.

Cyclotomic polynomials arise as "elementary polynomials" in various algebraic algorithms. The cyclotomic polynomials are defined by (Subscript[C, n])(x)==(∏_k)(x-(e^(2πik/n))), where k runs over all positive integers less than n that are relatively prime to n.

This is the cyclotomic polynomial (Subscript[C, 6])(x):

Cyclotomic[6,x]

(Subscript[C, 6])(x) appears in the factors of (x^6)-1:

Factor[x^6-1]

Decomposing polynomials.

Factorization is one important way of breaking down polynomials into simpler parts. Another, quite different, way is decomposition. When you factor a polynomial P(x), you write it as a product (Subscript[p, 1])(x)(Subscript[p, 2])(x)... of polynomials (Subscript[p, i])(x). Decomposing a polynomial Q(x) consists of writing it as a composition of polynomials of the form (Subscript[q, 1])((Subscript[q, 2])(...(x)...)).

Here is a simple example of (RefLink[Decompose, paclet:ref/Decompose]). The original polynomial (x^4)+(x^2)+1 can be written as the polynomial ((OverBar[x])^2)+(OverBar[x])+1, where (OverBar[x]) is the polynomial (x^2):

Decompose[x^4+x^2+1,x]

Here are two polynomial functions:

(q1[x_]=1-2x+x^4;q2[x_]=5x+x^3;)

This gives the composition of the two functions:

Expand[q1[q2[x]]]

(RefLink[Decompose, paclet:ref/Decompose]) recovers the original functions:

Decompose[%,x]

(RefLink[Decompose, paclet:ref/Decompose])[poly,x] is set up to give a list of polynomials in x, which, if composed, reproduce the original polynomial. The original polynomial can contain variables other than x, but the sequence of polynomials that (RefLink[Decompose, paclet:ref/Decompose]) produces are all intended to be considered as functions of x.

Unlike factoring, the decomposition of polynomials is not completely unique. For example, the two sets of polynomials (Subscript[p, i]) and (Subscript[q, i]), related by (Subscript[q, 1])(x)==(Subscript[p, 1])(x-a) and (Subscript[q, 2])(x)==(Subscript[p, 2])(x)+a give the same result on composition, so that (Subscript[p, 1])((Subscript[p, 2])(x))==(Subscript[q, 1])((Subscript[q, 2])(x)). The Wolfram Language follows the convention of absorbing any constant terms into the first polynomial in the list produced by (RefLink[Decompose, paclet:ref/Decompose]).

Generating interpolating polynomials.

This yields a quadratic polynomial which goes through the specified three points:

InterpolatingPolynomial[{{-1,4},{0,2},{1,6}},x]

When x is 0, the polynomial has value 2:

%/.x->0