10.4 Polynomials

A polynomial is a sum of terms which are coefficients times various powers of a “base” variable. For example, ‘2 x^2 + 3 x - 4’ is a polynomial in ‘x’. Some formulas can be considered polynomials in several different variables: ‘1 + 2 x + 3 y + 4 x y^2’ is a polynomial in both ‘x’ and ‘y’. Polynomial coefficients are often numbers, but they may in general be any formulas not involving the base variable.

The a f (calc-factor) [factor] command factors a polynomial into a product of terms. For example, the polynomial ‘x^3 + 2 x^2 + x’ is factored into ‘x*(x+1)^2’. As another example, ‘a c + b d + b c + a d’ is factored into the product ‘(a + b) (c + d)’.

Calc currently has three algorithms for factoring. Formulas which are linear in several variables, such as the second example above, are merged according to the distributive law. Formulas which are polynomials in a single variable, with constant integer or fractional coefficients, are factored into irreducible linear and/or quadratic terms. The first example above factors into three linear terms (‘x’, ‘x+1’, and ‘x+1’ again). Finally, formulas which do not fit the above criteria are handled by the algebraic rewrite mechanism.

Calc’s polynomial factorization algorithm works by using the general root-finding command (a P) to solve for the roots of the polynomial. It then looks for roots which are rational numbers or complex-conjugate pairs, and converts these into linear and quadratic terms, respectively. Because it uses floating-point arithmetic, it may be unable to find terms that involve large integers (whose number of digits approaches the current precision). Also, irreducible factors of degree higher than quadratic are not found, and polynomials in more than one variable are not treated. (A more robust factorization algorithm may be included in a future version of Calc.)

The rewrite-based factorization method uses rules stored in the variable FactorRules. See Rewrite Rules, for a discussion of the operation of rewrite rules. The default FactorRules are able to factor quadratic forms symbolically into two linear terms, ‘(a x + b) (c x + d)’. You can edit these rules to include other cases if you wish. To use the rules, Calc builds the formula ‘thecoefs(x, [a, b, c, ...])’ where x is the polynomial base variable and a, b, etc., are polynomial coefficients (which may be numbers or formulas). The constant term is written first, i.e., in the a position. When the rules complete, they should have changed the formula into the form ‘thefactors(x, [f1, f2, f3, ...])’ where each fi should be a factored term, e.g., ‘x - ai’. Calc then multiplies these terms together to get the complete factored form of the polynomial. If the rules do not change the thecoefs call to a thefactors call, a f leaves the polynomial alone on the assumption that it is unfactorable. (Note that the function names thecoefs and thefactors are used only as placeholders; there are no actual Calc functions by those names.)

The H a f [factors] command also factors a polynomial, but it returns a list of factors instead of an expression which is the product of the factors. Each factor is represented by a sub-vector of the factor, and the power with which it appears. For example, ‘x^5 + x^4 - 33 x^3 + 63 x^2’ factors to ‘(x + 7) x^2 (x - 3)^2’ in a f, or to ‘[ [x, 2], [x+7, 1], [x-3, 2] ]’ in H a f. If there is an overall numeric factor, it always comes first in the list. The functions factor and factors allow a second argument when written in algebraic form; ‘factor(x,v)’ factors ‘x’ with respect to the specific variable ‘v’. The default is to factor with respect to all the variables that appear in ‘x’.

The a c (calc-collect) [collect] command rearranges a formula as a polynomial in a given variable, ordered in decreasing powers of that variable. For example, given ‘1 + 2 x + 3 y + 4 x y^2’ on the stack, a c x would produce ‘(2 + 4 y^2) x + (1 + 3 y)’, and a c y would produce ‘(4 x) y^2 + 3 y + (1 + 2 x)’. The polynomial will be expanded out using the distributive law as necessary: Collecting ‘x’ in ‘(x - 1)^3’ produces ‘x^3 - 3 x^2 + 3 x - 1’. Terms not involving ‘x’ will not be expanded.

The “variable” you specify at the prompt can actually be any expression: a c ln(x+1) will collect together all terms multiplied by ‘ln(x+1)’ or integer powers thereof. If ‘x’ also appears in the formula in a context other than ‘ln(x+1)’, a c will treat those occurrences as unrelated to ‘ln(x+1)’, i.e., as constants.

The a x (calc-expand) [expand] command expands an expression by applying the distributive law everywhere. It applies to products, quotients, and powers involving sums. By default, it fully distributes all parts of the expression. With a numeric prefix argument, the distributive law is applied only the specified number of times, then the partially expanded expression is left on the stack.

The a x and j D commands are somewhat redundant. Use a x if you want to expand all products of sums in your formula. Use j D if you want to expand a particular specified term of the formula. There is an exactly analogous correspondence between a f and j M. (The j D and j M commands also know many other kinds of expansions, such as ‘exp(a + b) = exp(a) exp(b)’, which a x and a f do not do.)

Calc’s automatic simplifications will sometimes reverse a partial expansion. For example, the first step in expanding ‘(x+1)^3’ is to write ‘(x+1) (x+1)^2’. If a x stops there and tries to put this formula onto the stack, though, Calc will automatically simplify it back to ‘(x+1)^3’ form. The solution is to turn simplification off first (see Simplification Modes), or to run a x without a numeric prefix argument so that it expands all the way in one step.

The a a (calc-apart) [apart] command expands a rational function by partial fractions. A rational function is the quotient of two polynomials; apart pulls this apart into a sum of rational functions with simple denominators. In algebraic notation, the apart function allows a second argument that specifies which variable to use as the “base”; by default, Calc chooses the base variable automatically.

The a n (calc-normalize-rat) [nrat] command attempts to arrange a formula into a quotient of two polynomials. For example, given ‘1 + (a + b/c) / d’, the result would be ‘(b + a c + c d) / c d’. The quotient is reduced, so that a n will simplify ‘(x^2 + 2x + 1) / (x^2 - 1)’ by dividing out the common factor ‘x + 1’, yielding ‘(x + 1) / (x - 1)’.

The a \ (calc-poly-div) [pdiv] command divides two polynomials ‘u’ and ‘v’, yielding a new polynomial ‘q’. If several variables occur in the inputs, the inputs are considered multivariate polynomials. (Calc divides by the variable with the largest power in ‘u’ first, or, in the case of equal powers, chooses the variables in alphabetical order.) For example, dividing ‘x^2 + 3 x + 2’ by ‘x + 2’ yields ‘x + 1’. The remainder from the division, if any, is reported at the bottom of the screen and is also placed in the Trail along with the quotient.

Using pdiv in algebraic notation, you can specify the particular variable to be used as the base: pdiv(a,b,x). If pdiv is given only two arguments (as is always the case with the a \ command), then it does a multivariate division as outlined above.

The a % (calc-poly-rem) [prem] command divides two polynomials and keeps the remainder ‘r’. The quotient ‘q’ is discarded. For any formulas ‘a’ and ‘b’, the results of a \ and a % satisfy ‘a = q b + r’. (This is analogous to plain \ and %, which compute the integer quotient and remainder from dividing two numbers.)

The a / (calc-poly-div-rem) [pdivrem] command divides two polynomials and reports both the quotient and the remainder as a vector ‘[q, r]’. The H a / [pdivide] command divides two polynomials and constructs the formula ‘q + r/b’ on the stack. (Naturally if the remainder is zero, this will immediately simplify to ‘q’.)

The a g (calc-poly-gcd) [pgcd] command computes the greatest common divisor of two polynomials. (The GCD actually is unique only to within a constant multiplier; Calc attempts to choose a GCD which will be unsurprising.) For example, the a n command uses a g to take the GCD of the numerator and denominator of a quotient, then divides each by the result using a \. (The definition of GCD ensures that this division can take place without leaving a remainder.)

While the polynomials used in operations like a / and a g often have integer coefficients, this is not required. Calc can also deal with polynomials over the rationals or floating-point reals. Polynomials with modulo-form coefficients are also useful in many applications; if you enter ‘(x^2 + 3 x - 1) mod 5’, Calc automatically transforms this into a polynomial over the field of integers mod 5: ‘(1 mod 5) x^2 + (3 mod 5) x + (4 mod 5)’.

Congratulations and thanks go to Ove Ewerlid (ewerlid@mizar.DoCS.UU.SE), who contributed many of the polynomial routines used in the above commands.

See Decomposing Polynomials, for several useful functions for extracting the individual coefficients of a polynomial.