previous up next
Go backward to 4.7.4 Matrix Operations
Go up to 4.7 Arithmetic Notions
 RISC-Linz logo

4.7.5 Polynomials

We are used to think of a polynomial x+1 as a term with a variable x; the term can be manipulated according to various rules that preserve the value of the polynomial for any substitution of the variable. However, we need not introduce concepts like "terms" and "variables" in order to deal with polynomials; we can construct them directly from the basic material (functions and numbers) that we have introduced in the previous sections.

Definition 62 (Polynomials over the Reals) A  polynomial (Polynom) over the reals is an infinite sequence of real numbers, the  coefficients (Koeffizienten), of which only finitely many are different from 0:
p is polynomial : <=> p: N -> R /\  (exists k in N: forall i >= k: pi = 0).
The  degree (Grad) of a polynomial is zero, if all coefficients are zero; otherwise, it is the index of the largest non-zero coeffient:
deg(p) :=
   if forall i in N: pi = 0
      then 0
      else (such k in N: pk != 0 /\  (forall i > k: pi = 0)).
We denote by "Poly" the set of all polynomials over the reals:
Poly := {p in N -> R: p is polynomial}.

We then can define the following "number-like" operations on polynomials.

Definition 63 (Polynomial Operations) 
.Poly: R -> Poly
cPoly := such p in Poly: p0 = c /\  (forall i > 0: pi = 0)
x := such p in Poly: p0 = 0 /\  p1 = 1 /\  (forall i > 1: pi = 0)
+: Poly x Poly -> Poly
(p+q)i := pi + qi
-: Poly x Poly -> Poly
(p-q)i := pi - qi
-: Poly -> Poly
(-p)i := -(pi)
*: Poly x Poly -> Poly
(p*q)i := (sum0 <= j <= i pj * qi-j)

One can show that the polynomial operations satisfy the laws that also hold for the corresponding operations on numbers, e.g., p*1Poly = p and p*q = q*p.

The first operation maps a real number c in a unique way to a polynomial cPoly. Usually we write just c instead of cPoly, when the meaning is clear from the context, e.g., if p is a polynomial, then p+1 actually denotes p+1Poly.

Example  We have the following polynomial identities:
3Poly = [3, 0, 0, 0, 0, ...]
x = [0, 1, 0, 0, 0, ...]
x+3 = [3, 1, 0, 0, 0, ...]
x*x = [0, 0, 1, 0, 0, ...]
x*x+2*x+1 = [1, 2, 1, 0, 0, ...]
(x+1)*(x+2) = [2, 3, 1, 0, 0, ...]

The polynomial operations are closely related to their counterparts on R.

Proposition 62 (Constant Polynomials) For all real numbers a and b we have
aPoly+bPoly = (a+Rb)Poly,
aPoly-bPoly = (a-Rb)Poly,
-aPoly = (-Ra)Poly,
aPoly*bPoly = (a*Rb)Poly.

In other words, a property like 1+1=2 also holds for polynomials 1Poly and 2Poly and + interpreted as the polynomial addition. Above law says that R can be embedded into "Poly" in a sense that is discussed in Section Embedding Sets.

Definition Polynomial Operations answers the question what a polynomial x+1 is: it is the sum of two polynomials x and 1, i.e., the "variable" x in a polynomial is nothing but a particular (constant) polynomial! However, the view of x as a variable that can be substituted by a value is provided by the following operation.

Definition 64 (Polynomial Evaluation) 
[ ]: Poly x R -> R
p[a] := (sum0 <= i <= deg(p) pi*ai).

Example  Let p := 2+3*x+4*x*x, i.e., p = [2, 3, 4, 0, 0, 0, 0, ...]. Then
p[5] = 2*50+3*51+4*52 = 117.

The evaluation operation satisfies the following laws.

Proposition 63 (Evaluation Laws) For all polynomials p and q and all real numbers c and a, we have:
cPoly[a] = cPoly,
x[a] = aPoly,
(p+q)[a] = p[a] + q[a],
(p*q)[a] = p[a] * q[a].

When evaluating a polynomial p on a real number a, we thus just need to substitute aPoly for every occurence of x in the term describing p and then evaluate polynomial addition and multiplication. We can do this by simply using the rules for addition and multiplication over the real numbers.

Example  We have the following polynomial identities:
(x+1)[2] = 2+1 (= 3Poly)
(x*x)[2] = 2*2 (= 4Poly)
(x*x+2*x+1)[3] = 3*3+2*3+1 (= 16Poly)

In mathematical practice, we usually do not work with a fixed "polynomial variable" x. Instead we rather introduce a set R[x] of polynomials with coefficients in R (and correspondingly for other coefficent domains) such that the constant x denotes the polynomial [0, 1, 0, 0, 0, ...].

Example  2y+1 is an element of R[y] denoting the polynomial
[1, 2, 0, 0, 0, ...].

A multivariate polynomial is interpreted as a univariate polynomial whose coefficents are themselves polynomials.

Example  The bivariate polynomial
x2y+xy2+3x+2y+1
which can be written as
y*x2+(y2+3)*x+(2y+1)
is an element of R[y,x], i.e., (R[y])[x]:
[2y+1, y2+3, y, 0, 0, 0, ...].
The coefficient 2y+1 is an element of R[y]:
[1, 2, 0, 0, 0, ...].
Author: Wolfgang Schreiner
Last Modification: October 4, 1999
previous up next