Manuel Kauers Hagenberg, December 17, 2002 RISC-Linz

Computer Algebra Exercises

Solution 1

Ex. (A) Let x, y ∈ ℤ with the digital representations

x = [x_{1}, x_{2}, …, x_{n}], y = [y_{1}, …, y_{n}]

with x_{i}, y_{i} ∈ {0, 1, …, 9} (i = 1, …, n). Then the classical algorithm works by first computing x · y_{i} for each i which takes linear time for each i, and so it takes O(n^{2}) time to determine all of them. In the next step, the x · y_{i} are padded with up to n − 1 zeroes taking overall O(n^{2}) time. Finally, the padded x · y_{i} · 10^{(}n − i) need to be added, which again takes O(n^{2}) time. Hence, the overall cost of classical multiplication is O(n^{2}).

Various improvements to polynomial multiplication have been suggested during the past. The easiest one I know of is the algorithm of Karatsuba. This is a divide and conquer algorithm. Let K be a field and p, q ∈ K[X] of degree n such that

p = p_{1}X^{n/2} + p_{0}, q = q_{1}X^{n/2} + q_{0}.

Then, compute p_{1} · q_{1}, p_{0} · q_{0}, and (p_{0} + p_{1}) · (q_{0} + q_{1}) recursively and return

p_{1} · q_{1}X^{n} + ((p_{0} + p_{1}) · (q_{0} + q_{1}) − p_{0} · q_{0} − p_{1} · q_{1})X^{n/2} + p_{0} · q_{0}

which is easily verified to be equal to p · q. The complexity of this algorithm is

T (1) = O(1), T (n) = 3T (n/2) + O(n)

which leads to T (n) = O(n^{log_{2} 3}) which is slightly better than O(n^{log_{2} 4}) = O(n^{2}).

Further improvement can be achived using FFT based algorithms which lead to a multiplication time of O(n log n).

Ex. (B) Definition: Let R be a commutative ring and p ∈ R with 1.

1. p is a unit if there exists an inverse q =: p^{−1} of p such that p · q = 1. (Example: every field element.) The set of all units of R is denoted as R^{×}.

2. p is a zero divisor if p ≠ 0 and there is a q ≠ 0 such that p · q = 0.

3. p is a prime element if p ∉ R^{×} ∪ {0} and

∀ u, v ∈ R : p | u · v ⟹ p | u ∨ p | v.

4. p is irreducible if p ∉ R^{×} ∪ {0} and

∀ u, v ∈ R : p = u · v ⟹ u ∈ R^{×} ∨ v ∈ R^{×}.

In general, primarity implies irreducibility. In factorial rings, primarity and irreducibility are equivalent.

Consider 2 ∈ ℤ[\sqrt{−5}] = \{a+b\sqrt{−5} : a, b ∈ ℤ\}. We claim that 2 is irreducible but not prime.

Proof: 2 is not prime, because 2 | 6 and 6 = (1 + \sqrt{−5})(1 − \sqrt{−5}) but 2 ∤ 1 + \sqrt{−5} and 2 ∤ 1 − \sqrt{−5}. On the other hand, to prove that 2 is irreducible, assume that

2 = (a + b\sqrt{−5}) · (c + d\sqrt{−5})
= ac + ad\sqrt{−5} + bc\sqrt{−5} − 5bd.

for a, b, c, d ∈ ℤ. We have to show that (a, b) or (c, d) is trivial. We rewrite the last equation as a system of polynomial equations over ℤ

ad + bc = 0, ac − 5bd = 2

and using Maple as shown in Ex. D below, we obtain

a = 2\frac{c}{c^{2} + 5d^{2}} , b = −2\frac{d}{c^{2} + 5d^{2}} .

To solve this in ℤ, c^{2} + 5d^{2} needs to be divisor of c and d. In ℤ this requires c^{2} + 5d^{2} ≤ |d| which is only possible for d = 0. With this, a = 2c/c^{2} is only satisfiable for c = ±1. But now, we have

2 = (a + b\sqrt{−5}) + \underbrace{(±1 + 0 · \sqrt{−5})}_{∈R^{×}},

which completes the proof.

Ex. (C) Implementation of lists is possible similar to the recursive definition of a list: If X is a set of elements, then x ∈ X is a list and for each x ∈ X and each list l, (x, l) is also a list.

In this implementation, the basic operations take the following costs:

Operation  Time complexity
Append a new element to the front O(1)
Remove an element from the front O(1)
Search for an element  O(n)
Invert a list  O(n)
Concatenation of two lists  O(n)

Ex. (D) Let p_{1}, p_{2}, p_{3} denote the respective lefthand side polynomials of rows 1, 2, and 3. Then, in Maple:

> solve({p1=0,p2=0,p3=0},{x,y});

{y = RootOf( Z^{2} + 1), x = 0}

> allvalues(%);

{x = 0, y = I}, {x = 0, y = −I}

and hence, Var(p_{1}, p_{2}, p_{3}) = {(0, i), (0, −i)}.

Ex. (E) In Maple:

> sum(i^2, i=1..n);

\frac{1}{3}(n + 1)^{3} − \frac{1}{2}(n + 1)^{2} + \frac{1}{6}n + \frac{1}{6}

> simplify(%);

\frac{1}{3}n^{3} + \frac{1}{2}n^{2} + \frac{1}{6}n