The Polynom Package

Copyright 2000–2002

              Carsten Heinz <cheinz@gmx.de>

2002/01/10 Version 0.14

Abstract

The polynom package implements macros for manipulating polynomials, for example it can typeset long polynomial divisions. Such long divisions can be shown step by step. The main test case and application is the polynomial ring in one variable with rational coefficients.

1 Introduction

Donald Arseneau has contributed a lot of packages to the TEX community. In particular, he posted macros for long division on comp.text.tex, which were also published in the TUGboat [1]. With these definitions, one could just write \longdiv{12345}{13} to get the long division shown in Figure 1 (a). In fact, that

949 ; 13 \overline{)12345} ; \underline{11700} ; 645 ; \underline{520} ; 125 ; \underline{117} ; 8  \begin{aligned}& & X^{2} & + 2X & + 2 \\ X − 1) & X^{3} & + X^{2} & & − 1 \\ & − X^{3} & + X^{2} \\ & & 2X^{2} \\ & & − 2X^{2} & + 2X \\ & & & 2X & − 1 \\ & & & − 2X & + 2 \\ & & & & 1 \end{aligned}

    (a) \longdiv{12345}{13}  (b) \polylongdiv{X^3+X^2-1}{X-1}

Figure 1: Integer and polynomial long division

integer long division has been typeset using the code from the location cited. The polynom package allows to do the similar job with polynomials, see Figure 1 (b). Figure 2 shows partial long divisions.

An application of polynomial division is shown in Figure 3: the Euclidean algorithm to determine a greatest common divisor of two polynomials. Note that in the case here, a greatest common divisor is uniquely determined up to a scalar factor, so X − 1 and \frac{4}{9}X − \frac{4}{9} are both greatest common divisors in the example.

\polylongdiv[stage=1]

            {(X-1)(X^2+2X+2)+1}{X-1} X − 1) X^{3} + X^{2} − 1

\polylongdiv[stage=2]
            {(X-1)(X^2+2X+2)+1}{X-1}

\begin{aligned}& & X^{2} \\ X − 1) & X^{3} & + X^{2} & − 1 \end{aligned}

\polylongdiv[stage=3]
            {(X-1)(X^2+2X+2)+1}{X-1}

\begin{aligned}& & X^{2} \\ X − 1) & X^{3} & + X^{2} & − 1 \\ & − X^{3} & + X^{2} \end{aligned}

\polylongdiv[stage=4]
            {(X-1)(X^2+2X+2)+1}{X-1}

\begin{aligned}& & X^{2} \\ X − 1) & X^{3} & + X^{2} & − 1 \\ & − X^{3} & + X^{2} \\ & & 2X^{2} \end{aligned}

⋮

Figure 2: Stepwise polynomial long division. The whole division is shown with stage=10. Note that other printing styles, see table 7, might require one more stage to put the remainder next to the result

\begin{aligned}X^{4} − 2X^{3} + 2X^{2} − 2X + 1 & = (X^{3} + X^{2} − X − 1) · (X − 3) & + (6X^{2} − 4X − 2) \\ X^{3} + X^{2} − X − 1 & = (6X^{2} − 4X − 2) · (\frac{1}{6}X + \frac{5}{18}) & + (\frac{4}{9}X − \frac{4}{9}) \\ 6X^{2} − 4X − 2 & = (\frac{4}{9}X − \frac{4}{9}) · (\frac{27}{2}X + \frac{9}{2}) & + 0 \end{aligned}

         \polylonggcd {(X-1)(X-1)(X^2+1)} {(X-1)(X+1)(X+1)}

Figure 3: Euclidean algorithm with polynomials; the last nonzero remainder is a greatest common divisor

    \polyfactorize {(X-1)(X-1)(X^2+1)} (X^{2} + 1) (X − 1)^{2}

    \polyfactorize {2X^3+X^2-7X+3}

2 (X − \frac{1}{2}) (X + \frac{1}{2} + \frac{\sqrt{13}}{2}) (X + \frac{1}{2} − \frac{\sqrt{13}}{2})

    \polyfactorize {120X^5-274X^4+225X^3-85X^2+15X-1}

120 (X − 1) (X − \frac{1}{2}) (X − \frac{1}{3}) (X − \frac{1}{4}) (X − \frac{1}{5})

Figure 4: Factorizations of some polynomials

2 Commands

The tables 5 and 6 list the user commands defined by this package. Each ⟨cs_{...}⟩ stands either for a TEX control sequence to store the internal representation of the result, or it stands for a previously saved result to operate with. The polynomials ⟨a⟩ and ⟨b⟩ are ‘verbatim’ polynomials as you would type them in math mode:^{1} you may use +, -, *, \cdot, /, \frac, (, ), natural numbers, symbols like e, \pi, \chi, \lambda, and variables; the power operator ^with integer exponents can be used on symbols, variables, and parenthesized expressions. Never use variables in a nominator, denominator or divisor.

print long division a/b \polylongdiv[⟨keys⟩]{⟨a⟩}{⟨b⟩}
(maybe partially)  \polylongdiv[⟨keys⟩]⟨cs_{a}⟩⟨cs_{b}⟩
print Euclidean algorithm \polylonggcd{⟨a⟩}{⟨b⟩}
for gcd(a, b)  \polylonggcd⟨cs_{a}⟩⟨cs_{b}⟩
print factorization of the \polyfactorize{⟨a⟩}
polynomial a  \polyfactorize⟨cs_{a}⟩

Table 5: High-level user commands. The optional argument of the \polylongdiv command changes settings for the particular division

⟨cs_{a+b}⟩ ← a + b  \polyadd⟨cs_{a+b}⟩{⟨a⟩}{⟨b⟩}
\polyadd⟨cs_{a+b}⟩⟨cs_{a}⟩⟨cs_{b}⟩
⟨cs_{a−b}⟩ ← a − b  \polysub⟨cs_{a−b}⟩{⟨a⟩}{⟨b⟩}
\polysub⟨cs_{a−b}⟩⟨cs_{a}⟩⟨cs_{b}⟩
⟨cs_{ab}⟩ ← a · b  \polymul⟨cs_{ab}⟩{⟨a⟩}{⟨b⟩}
\polymul⟨cs_{ab}⟩⟨cs_{a}⟩⟨cs_{b}⟩
⟨cs_{a/b}⟩ ← ⌊a/b⌋  \polydiv⟨cs_{a/b}⟩{⟨a⟩}{⟨b⟩}
\polyremainder ← a mod b \polydiv⟨cs_{a/b}⟩⟨cs_{a}⟩⟨cs_{b}⟩
⟨cs_{gcd}⟩ ← gcd(a, b) \polygcd⟨cs_{gcd}⟩{⟨a⟩}{⟨b⟩}
\polygcd⟨cs_{gcd}⟩⟨cs_{a}⟩⟨cs_{b}⟩
print polynomial a  \polyprint{⟨a⟩}

                                    \polyprint⟨cs_{a}⟩

Table 6: Low-level user commands

1The scanner is based on the scanner of the calc package [2]. Read its documentation and the implementation part here if you want to know more.

Note, however, that the support of symbols is very limited and that there is neither support of functions like sin(x) or exp(x), nor of roots or exponents other than integers, for example \sqrt{π} or e^{x}. For teaching purposes this shouldn’t be a major drawback. Particularly because there is a simple workaround in some cases: the package doesn’t look at symbols closely, so define the function or ‘composed symbol’ like \sqrt{π} as a symbol. For example, you could write

    \newcommand\epowerx{e^x}
    \[\polylongdiv{\epowerx x^3-\epowerx x^2+\epowerx x-\epowerx}{x-1}\]

e^{x}x^{3} − e^{x}x^{2} + e^{x}x − e^{x} = (x − 1) (e^{x}x^{2} + e^{x})
− e^{x}x^{3} + e^{x}x^{2}
e^{x}x − e^{x}
(− e^{x}x + e^{x}) / 0

Here the quotient and remainder are written next to dividend and divisor. This ‘style=B-feature’ is discussed in the next section.

Let’s conclude this section with an example of the low-level commands. If we want to divide (X^{2}+X +1)(X −1)− \frac{π}{2} by X −1 and print quotient and remainder, we could do it like this:

    \polydiv\polya {(X^2+X+1)(X-1)-\frac\pi2} {X-1}
    `The quotient is \polyprint\polya,
    the remainder \polyprint\polyremainder.'

Of course, we all know the result, so it isn’t shown here. The calculation alone could also be done by, for example,

    \polymul\polya {X^2+X+1} {X-1}
    \polysub\polya \polya {\frac{\pi}{2}}
    \polydiv\polya \polya {X-1}

3 Keys

\polyset Predefined variables are X and x, the default style for printing long division is shown in Figure 1 (b), and the left and right delimiters are \left( and \right). The macro \polyset changes such default settings and accepts a comma separated list of ‘key=value’ pairs. This is implemented using the keyval package [3]. Possible keys and values are given in table 7. To make the style selection C clear and to use variables and delimiters other than the default, look at the output of the following example.

    \begin{center}
    \polyset{vars=XYZ\xi,  % make X, Y, Z, and \xi into variables
             style=C,      % use nonstandard style
             delims={[}{]}}% nongrowing brackets
    \polylongdiv{(\xi-1)(\xi^2+2\xi+2)+1}{\xi-1}
    \end{center}

[ ξ^{3} + ξ^{2}  − 2] ÷ [ξ − 1] = ξ^{2} + 2ξ + 2
(− ξ^{3} + ξ^{2}) / (2ξ^{2})
− 2ξ^{2} + 2ξ
2ξ − 2
(− 2ξ + 2) / 0

Afterwards previous settings are restored since the changes are made inside the center environment or, more generally, inside a group. The same \polylongdiv command now makes no sense. A constant would be divided by a constant.

vars=⟨token string⟩  make each token a variable
style=⟨A|B|C⟩  define style for long division
div=⟨token⟩  define division sign for

style=C, default is ÷

stage=⟨number⟩  print long division up to stage

⟨number⟩ (starting with 1)

delims={⟨left⟩}{⟨right⟩} define delimiters used for

parenthesized expressions

Table 7: Keys and values. The delims key has in fact an optional argument for use with growing delimiters. In this case you must specify invisible versions of the two delimiters. The default is delims=[{\left.}{\right.}]{\left(}{\right)}

References

[1] Barbara Beeton and Donald Arseneau.

Long division.

In Jeremy Gibbons’ Hey — it works!, TUGboat 18(2), June 1997, p. 75.

[2] Kresten Krab Thorup, Frank Jensen, and Chris Rowley. The calc package, Infix notation arithmetic in L^{A}TEX, 1998/07/07.

   Available from CTAN: macros/latex/required/tools.

[3] David Carlisle.

The keyval package, 1999/03/16.

   Available from CTAN: macros/latex/required/graphics.