Symbolic Computing
Theory
LT20, 4:00-5:00pm
Wed, 5 March 2003

Scope

In this second part of symbolic computing course, we shall highlight some of the problems and algorithms fundamental to symbolic computing.  We shall concentrate on few well-known algorithms, rather than covering systematically the so-called "theory".   Some of them includes:

1.  Concepts from abstract algebra, such as group, ring, and field.
2.  Euclid algorithm and extended Euclid algorithm of polynomials over a field (or integral domain?)
3. Chinese remainder theorem and application in symbolic computing.
4. Algorithms for factor a polynomial (over a field).

Perhaps the most exciting algorithms in symbolic computing are those of symbolic integration.  The Risch integration algorithm can tell you, under certain restriction (elementary functions, e.g, rational functions, exponential and logarithms), if an integrand can be explicitly integrated.  However, the theory requires rather deep abstract algebra, so we'll not cover in this course.
Interested students can read Chap 11 and 12 of  "Algorithms for Computer Algebra" by K. O. Geddes et al.

Group

The concept of group is used in many places, such as in physics and chemistry about symmetry, topological invariant in mathematics.   It is one of the basic concept in abstract algebra.  Here is the definition:

A Group (G;∘) is a nonempty set G, closed under a binary operation ∘ satisfying the axioms:

A1:   a ∘ (b ∘ c) = (a ∘ b) ∘ c   for all a, b, c ∈ G

A2:  There is an element e ∈ G such that 
	e ∘ a  =  a ∘ e = a    for all a ∈ G
	
A3:  For all a ∈ G, there is an elements (a^(-1)) ∈ G such that 
	a ∘ (a^(-1))  =  (a^(-1))∘ a  =  
          e

The axiom A1 is known as associativity, A2 defines the identity element e.  A3 asserts the existence of an inverse for each element.

If you have not touch upon abstract algebra, the concept is a bit strange and difficult to grasp.  A few examples will help.

1.  Consider the set  G = (0, 1) with two elements and the operation plus + mod 2 as the operation ∘.    We define a mod b as positive remainder of a when divided by b,  i.e. for integers r, a, b, q, 
	r = a mod b,  then  a = q*b + r,     0 ≤ r < b.
Then  (0 + 0)  mod 2 = 0, (1 + 0) mod 2 = 1, (0  + 1) mod 2 = 1, (1 + 1) mod 2 = 0, thus, the operation is CLOSED under ∘, i.e., + mod 2.  We denote this set and the operation with the notation ((Subscript[Z, 2]);  +)  (integer addition modulo 2).  We can display the operation (group multiplication) in a table as follows:

∘   | 0       1
___  ___  ___
0    |   0       1
1    |   1       0

Does the set G=(0,1) with the operation + mod 2 satisfy the definition of a group A1, A2, A3?  If the answer is yes, then it is a group.

A0:  the operation is closed.  For every a, b ∈ G (that is a and b is 0 or 1),  a + b mod 2 = 0 or 1 is also in G.
A1: associativity,  For every a,b,c ∈ G, we have
	(a ∘ b) ∘ c = (((a+b) mod 2) + c ) mod 2 = 
	(a+b+c) mod 2 = ( a + ((b+c) mod 2)) mod 2 
	= a ∘ (b ∘ c) = a ∘ b ∘ c,
so associativity is true.  This means that the order of evaluation is not important.  We can remove the grouping parenthesis without ambiguity. 
A2:  We have 0 ∘ 1 = 1 ∘ 0  = 1,
               and  0 ∘ 0 = 0
so 0 is the identity element e. 
A3:  For 0,  0 ∘ 0 = e = 0, so the inverse of 0 is 0. (why?)
        And  1 ∘ 1 = 0, so the inverse of 1 is 1.  Axiom A3 is also satisfied.

Thus we conclude that ((Subscript[Z, 2]);  +) is a group.

Is the set G  = (a,b,c) with the following operation a group?  If so, find identity element e and inverse of each elements:

∘     |    a     b      c
-----------------------
a    |    a      b      c
b    |    b      c      a
c    |     c      a      b

Abelian Group

Although in ordinary multiplication a*b or addition a+b, we have a*b=b*a, or a+b=b+a.  However, if a and b are matrices, then in general a b ≠ b a.  The definition of group says nothing about this.

An Abelian Group (or commutative group) is a group in which the binary operation ∘ satisfies the additional axiom:

A4:   a ∘ b  =  b ∘ a   for all a, b ∈ G.

The two examples given above are Abelian groups.  Here is an example of nonabelian group:
The set G consists of elements 
I = (({{1, 0}, {0, 1}})),	    A = (({{0, 1}, {1, 0}})),         B = (({{0, 1}, {-1, -1}}))
C = (({{-1, -1}, {0, 1}})),  D = (({{-1, -1}, {1, 0}})),    K = (({{1, 0}, {-1, -1}}))
with group multiplication ∘ defined as ordinary matrix multiplication.   The multiplication table works out to be:
∘   |    I    A   B   C   D   K
______________________
I   |    I    A     B    C   D   K
A  |   A    I     C    B   K    D
B  |   B   K     D   A    I    C
C  |   C   D    K    I     A   B
D  |   D   C     I    K    B   A
K  |   K   B    A    D    C    I
It is obvious that I is identity element e.  Matrix multiplication is associative.  Each element has an inverse (e.g., (A^(-1))=A, (B^(-1))=D).  But AB=C and BA = K, so G is not commutative.

Ring

A group have only one operation, a ring has two operations, we shall call it + and ∘.   A ring is closed under both operations, i.e., if a, b ∈ R, then  a+b and a∘b is also in R.  A ring satisfies the following axioms.

A ring (R; +, ∘) is a set R closed under two binary operations + and ∘.  

The elements under the operation +, denoted by (R; +), is an abelian group (satisfies A1 to A4 with respect to +).

∘ is associative and has an identity  (A1 and A2 with respective to ∘)  and

A5:   a ∘ (b  +  
              c)  =  (a∘b)  +  (a∘
              c)
         (b  +  c) ∘ 
          a  =  (b∘a)  +  (c∘a)
for all a, b, c ∈ R.

Because axiom A3 is not required for ∘, so an element of a ring may not have a multiplicative inverse.   If ∘ is commutative, it is then called a commutative ring.  A5 is known as distributive law.

Integral Domain

If we have an equation  a*b = a*c, can we say b=c (by cancelling a)?  this depends on what algebraic structure the set have (think of matrices, integral, or real numbers).  The integral domain axiomizes this fact.

An integral domain is a commutative ring which satisfies the additional axiom:

A6:   a ∘ b = a ∘ c    and a ≠ 0  implies 
         b = c for all a, b,c ∈ R.

Axiom A6 is known as cancellation law.

Field

A field (F; +, ∘) is a set satisfying:
(1)  (F; +) is an abelian group with respect to +, we use 0 to denote additive identity element.
(2)  (F-{0}; ∘) is an abelian group with respect to ∘.
(3)  ∘ is distributive over +, (i.e. A5).

For a field, each nonzero element has a multiplicative (∘) inverse.  Field is one of most "useful" and friendly algebraic structure, because we can do addition, subtract, multiplication and division in it.   Unfortunately, we still need to deal with integral domains many of times, as integers and polynomials belongs to them.

More examples on integral domains, and fields will be given in next lecture.