GRÖBNER BASES OVER ALGEBRAIC NUMBER FIELDS

arXiv:1504.04564v2 [math.AC] 5 Aug 2015

DEREJE KIFLE BOKU, WOLFRAM DECKER, CLAUS FIEKER,
AND ANDREAS STEENPASS

Abstract. Although Buchberger’s algorithm, in theory, allows us to compute
Gröbner bases over any field, in practice, however, the computational efficiency
depends on the arithmetic of the ground field. Consider a field K = Q(α), a
simple extension of Q, where α is an algebraic number, and let f ∈ Q[t] be the
minimal polynomial of α. In this paper we present a new efficient method to
compute Gröbner bases in polynomial rings over the algebraic number field K.
Starting from the ideas of Noro [11], we proceed by joining f to the ideal to be
considered, adding t as an extra variable. But instead of avoiding superfluous
S-pair reductions by inverting algebraic numbers, we achieve the same goal by
applying modular methods as in [2, 3, 10], that is, by inferring information
in characteristic zero from information in characteristic p > 0. For suitable
primes p, the minimal polynomial f is reducible over Fp . This allows us to apply modular methods once again, on a second level, with respect to the factors
of f . The algorithm thus resembles a divide and conquer strategy and is in
particular easily parallelizable. At current state, the algorithm is probabilistic
in the sense that, as for other modular Gröbner basis computations, an effective final verification test is only known for homogeneous ideals or for local
monomial orderings. The presented timings show that for most examples, our
algorithm, which has been implemented in Singular [7], outperforms other
known methods by far.

1. Introduction
From the theoretical point of view, Gröbner bases computations can be done over
any field by using Buchberger’s algorithm (see, for example, [1, 6, 8]). In particular,
they can be performed over an algebraic number field, but the computation is often
inefficient if the arithmetic operations in this field are used directly. Consider a
simple extension K = Q(α) of Q. Let f ∈ Q[t] be the minimal polynomial of
α. The algebraic number field K can be represented as the residue class ring
Q[t]/hf i, and a Gröbner basis computation over K can then be reduced to one over
Q by joining f to the ideal to be considered. Unfortunately, this method is not
satisfactory in view of efficiency. One of the reasons for this is that over the field of
rational numbers, we often suffer from coefficient swell. Various methods to avoid
this have been investigated; the trace algorithm [13] and modular algorithms [2, 10]
are successful in this direction. But using these approaches, we still have to deal
with the complicated arithmetic in algebraic number fields, in particular with the
computation of inverses.
In this paper we present a new efficient method to compute Gröbner bases over
an algebraic number field. Starting from a polynomial ring over Q as explained
above, we apply the modular methods for computing Gröbner bases discussed in
[2, 3, 10] to pass to positive characteristic p. Choosing a set P of suitable prime
numbers, see Definition 5.2, the image fp of f in Fp [t] is, for p ∈ P, reducible
and square-free. We can thus again apply modular methods, with respect to the
factors f1,p , . . . , frp ,p of fp , passing to the rings Fp [t]/hfi,p i. As above, we avoid
Key words and phrases. Gröbner bases, algebraic number fields, factorization, Chinese remainder theorem, modular algorithms.
1

2

DEREJE K. BOKU, WOLFRAM DECKER, CLAUS FIEKER, AND ANDREAS STEENPASS

computing in quotient rings by joining fi,p to the ideal to be considered. Having
computed the corresponding reduced Gröbner basis for each of these factors, we
first recombine the results to a set of polynomials Gp over Fp [t]/hfp i using Chinese
remaindering for polynomials. In a second lifting step, the sets Gp , p ∈ P, are
then used to reconstruct a set of polynomials G over Q, via Chinese remaindering
for integers and rational reconstruction. Finally, we test whether G is indeed the
reduced Gröbner basis of the input ideal. If not, we enlarge P and repeat the
process.
In Section 2, we introduce some notation which is used throughout this article.
The structure of the new method is outlined in Section 3. Since this method relies
on the Chinese remainder algorithm applied to different domains, we shortly recall
the relevant theoretical background in Section 4. The core part of the proposed
algorithm is discussed in Section 5. Here we explain how modular methods are
applied on different levels and why our approach is considerably faster than other
known methods. The application of modular methods follows a well-known scheme,
see [3]. For reference, we recall the relevant parts of this scheme in Section 6. An
illustrating example is given in Section 7. Finally, Section 8 contains remarks on
the implementation of the new method in Singular [7] and timings comparing it
to other approaches. The benchmark problems which we used for the timings are
listed in the appendix.
2. Notation
Let K = Q(α) be an algebraic number field and let f ∈ Q[t] be the minimal
polynomial of the algebraic number α. Then every element of K can be written
as a linear combination of elements in {1, α, α2 , . . . , αd−1 } where d = deg f . Hence
we may regard every element of K as a polynomial in α with coefficients in Q. Let
X = {x1 , . . . , xn } be a set of variables, and let t be an extra variable. Consider
the polynomial rings S = Q(α)[X], T = Q[X, t], and Q[t]. Fix a global monomial
ordering 1 on the monoid of monomials Mon(X) and consider the product ordering
K := (1 , ) on Mon(X, t), where  is the global ordering on Mon(t). Note that
this implies X a K tb for all a ∈ Nn \ {(0, . . . , 0)} and b ∈ N.
e = {g1 (X, t), . . . , gs (X, t)} be a subset of T , let I ⊆ S be the ideal generated
Let H
e ∪ {f }.
by H := {g1 (X, α), . . . , gs (X, α)}, and let Ie ⊆ T be the ideal generated by H
e
Furthermore, let G ⊆ T be the reduced Gröbner basis (see [8, Definition 1.6.2]) of Ie
w.r.t. K . Let ϕ be the canonical homomorphism from T to S which leaves the xi
fixed and maps t to α. We will show, in Theorem 5.1, that the non-zero elements
e ⊆ S form the reduced Gröbner basis of I w.r.t. 1 .
of ϕ(G)
For a carefully chosen prime p (see Definition 5.2) which does not divide any
denominator of the coefficients of f and g1 (X, t), . . . , gs (X, t), we consider the map
from Q to Fp which sends ab to ab−1 ∈ Fp . Applying this map to the coefficients,
we write fp := (f mod p) ∈ Fp [t] and Iep := hg1 (X, t)p , . . . , gs (X, t)p , fp i ⊆ Fp [X, t].
Furthermore, for a polynomial q ∈ S and a set G ⊆ S, we use the following notation:
lm(q): the leading monomial of q,
Lm(G): the set of leading monomials of the elements in G,
lc(q): the leading coefficient of q,
lt(q): the leading term or head of q,
tail(q) := q − lt(q): the tail of q.
3. Structure of the New Method
Noro [11] has presented a modified version of Buchberger’s algorithm which computes Gröbner bases over an algebraic number field using the arithmetic in Q[t]/hf i.

GRÖBNER BASES OVER ALGEBRAIC NUMBER FIELDS

3

Instead of computing in the ring (Q[t]/hf i)[X], one might as well add the minimal
polynomial f to the ideal to be considered and work over Q[X, t], see Theorem 5.1.
In this situation, the elements of a reduced Gröbner basis are, except f itself, all
monic in (Q[t])[X], that is, they are of the form X a + (lower terms), see the proof
of Theorem 5.1. Noro noticed that during the execution of Buchberger’s algorithm,
many (superfluous) intermediate basis elements of the form tb X a + (lower terms)
are computed before a monic element X a + (lower terms) is generated. Of course,
each additional basis element produces new S-pairs which usually make the subsequent computation inefficient. Noro has resolved this problem by making each
generated basis element monic in (Q[t])[X] before it is added to the basis. For this,
the inverse of an algebraic number has to be computed which is in general computationally expensive. Instead, we use a different approach to reduce the number of
basis elements which are computed before a monic element X a + (lower terms) is
generated.
The new method computes the reduced Gröbner basis of the input ideal in three
steps: In the first step, for a suitable prime p such that fp ∈ Fp [t] is reducible and
e
e
square-free, see Definition 5.2, we compute
Q the reduced Gröbner basis Gp of Ip over
Fp w.r.t. K , as follows: Let fp = 1≤i≤rp fi,p be the irreducible factorization
e p ∪ {fi,p }i ⊆ Fp [X, t]. For each i ∈
of fp over Fp , with rp > 1. Set Iei,p := hH
e i,p of Iei,p . Using the Chinese
{1, . . . , rp }, we compute the reduced Gröbner basis G
remainder algorithm
(see Algorithm 1 below), we determine a set of
 for polynomials

e
e
polynomials Gp ≡ Gi,p \ {fi,p } mod fi,p which together with fp is the reduced
Gröbner basis of Iep with high probability (see Remark 5.6). Note that, at this step
of the algorithm, computing modulo the different factors of the minimal polynomial
e p i) is, from the theoretical point of view, just
fi,p (by adding them to the ideal hH
the same as computing modulo several prime numbers, see Section 4.
In the second step, following [2, 10], we use the Chinese remainder algorithm for
integers together with rational reconstruction to lift these results to the reduced
e of I.
e In the last step, we lift G
e to a Gröbner basis G of I over K
Gröbner basis G
by mapping t to α (see Theorem 5.1).
The idea of the algorithm is based on the concepts of modular methods and
univariate polynomial factorization over finite fields. For the former we need the
Chinese remainder theorem.
4. Factorization and the Chinese Remainder Algorithm
The well-known Chinese remainder theorem is essential for our algorithm.
Theorem 4.1 ([14, Corollary 5.3]). Let R be a Euclidean domain and let m1 , . . . ,
mr ∈ R be coprime elements so that gcd(mi , mj ) = 1 for 0 ≤ i < j ≤ r. Let
m = m1 · · · mr be the product of these elements. Then R/hmi is isomorphic to the
product ring R/hm1 i × . . . × R/hmr i via the isomorphism
R/hmi → R/hm1 i × . . . × R/hmr i ,
a 7→ (a mod m1 , . . . , a mod mr ) .
For our purpose, we need this theorem in the following two incarnations.
Corollary 4.2. Let p1 , . . . , pk be distinct prime numbers, and let N = p1 · · · pk be
their product. Then we have the following isomorphism:
Z/hN i ∼
= Fp × . . . × Fp .
1

k

The second application of the Chinese remainder theorem refers to univariate
polynomial rings over finite fields.

4

DEREJE K. BOKU, WOLFRAM DECKER, CLAUS FIEKER, AND ANDREAS STEENPASS

Corollary 4.3. Let f1,p , . . . , frp ,p ∈ Fp [t] be pairwise coprime polynomials, and let
fp = f1,p · · · frp ,p be their product. Then we have the ring isomorphism
Fp [t]/hfp i ∼
= Fp [t]/hf1,p i × . . . × Fp [t]/hfrp ,p i .
The proof of Theorem 4.1 is constructive (see [14, Theorem 5.2, Corollary 5.3])
and yields the Chinese remainder algorithm. For reference, we state it here in the
form of Corollary 4.3, see Algorithm 1.
Algorithm 1 Chinese Remainder Algorithm (CRA) for polynomials
Input: q1 , . . . , qrp ∈ Fp [t], f1,p , . . . , frp ,p ∈ Fp [t] pairwise coprime.
Output: g ∈ Fp [t] such that g ≡ qi mod fi,p for 1 ≤ i ≤ rp .
1: g ←− 0
Q
2: fp ←−
1≤i≤rp fi,p
3: for i = 1, . . . , rp do
fp
4:
hi ←−
fi,p
5:
by the Extended Euclidean Algorithm [14, Algorithm 3.14], compute si , ti ∈
Fp [t] such that
si hi + ti fi,p = 1
ci ←− NF(qi si , fi,p )
(ci is the remainder in Fp [t] on dividing qi si by fi,p )
7:
g ←− g + ci hi
8: return g

6:

Remark 4.4.
a) Since ci hi ≡ 0 mod fj,p for j 6= i and ci hi ≡ qi si hi ≡ qi mod fi,p , we
have
g ≡ ci hi ≡ qi mod fi,p .
Hence, the algorithm works correctly.
b) Although stated here for Fp [t], Algorithm 1 works for polynomial rings over
any ground field.
c) Instead of q1 , . . . , qrp ∈ Fp [t], Algorithm 1 can also be applied coefficientwise to polynomials with coefficients in Fp [t].
5. Gröbner Bases using Factorization and Modular Methods
As Noro does (see [11, Theorem 1]), we rely on the following result whose proof
we give for the lack of reference.
e be the reduced Gröbner basis of Ie w.r.t. K . Then (G
e\
Theorem 5.1. Let G
{f })|t=α is the reduced Gröbner basis of I w.r.t. 1 .
Consider the ring homomorphism
ϕ : T −→ S, t 7−→ α, xi 7−→ xi .
Since ϕ is the identity map on Q[X], we get an isomorphism
S∼
= T /hf i .
e = I. We are now ready to prove Theorem 5.1.
Clearly, ϕ(I)

GRÖBNER BASES OVER ALGEBRAIC NUMBER FIELDS

5

Proof. Without loss of generality, we may assume that Ie 6= h1i. Let
e = {m1 (X, t), . . . , ma (X, t), ma+1 (X, t)}
G
e We first prove that f ∈ G.
e Suppose f ∈
e Then
be the reduced Gröbner basis of I.
/ G.
0
0
e
there exists a non-zero non-constant polynomial f ∈ G ∩ Q[t] with deg f < deg f .
Hence
e = hϕ(f 0 ), ϕ(G
e \ {f 0 })i = h1i
I = ϕ(I)
since ϕ(f 0 ) is invertible in S. This implies Ie = h1i, a contradiction. So, f = mi (X, t)
for some i, say i = a + 1. Then we have
e \ {f }) = {m1 (X, α), . . . , ma (X, α)}
ϕ(G
e \ {f })|t=α =: G .
= (G
The result follows easily once we show that the leading coefficient of m(X, t), considered as an element in the polynomial ring Q[t], is equal to 1 for all m(X, t) ∈
e \ {f }. To prove this statement, suppose there is an index 1 ≤ j ≤ a such that
G
lt(mj (X, t)) = c · X δ with c ∈ Q[t] and deg c > 0. Clearly, c is monic. Write
mj (X, t) = c · X δ + V (X, t)
where V (X, t) = tail(mj (X, t)), which implies that V (X, t) does not contain any
term divisible by X δ . We have deg c < deg f and therefore gcd(c, f ) = 1 since f is
irreducible. Thus, by the extended Euclidean algorithm (see [14, Algorithm 3.14]),
there exist a, b ∈ Q[t] such that a · c + b · f = 1. Considering the polynomial
a · mj (X, t) + b · f · X δ , we have
e 3 a · mj (X, t) + b · f · X δ
hGi
= (a · c + b · f ) · X δ + a · V (X, t)
= X δ + a · V (X, t) =: F (X, t) .
But lt(F (X, t)) = X δ divides c · X δ = lt(mj (X, t)) which is a contradiction to the
e
choice of G.

The notion of primes which are admissible of type A w.r.t. a monic irreducible
polynomial, which is essential for our algorithm, is defined as follows:
Definition 5.2. Let f ∈ Q[t] be as given above. Let p be a prime not dividing any
numerator or any denominator of the coefficients occurring in f . We say that p is
admissible of type A Q
w.r.t. f if fp is reducible and square-free over Fp . In this case,
we write fp as fp = 1≤i≤rp fi,p .
For a non-zero polynomial g ∈ T considered as a polynomial in X over Q[t], that
is, g ∈ (Q[t])[X], let Sg be the set of all distinct coefficients (in Q[t]) of g of degree
greater than or equal to 1. That is,

Sg = lcQ[t] (u) | u is a term of g with deg(lcQ[t] (u)) ≥ 1 .
With notation as above, the notion of primes which are admissible of type B
w.r.t. a monic irreducible polynomial and a set of polynomials is defined as follows:
e = {g1 (X, t), . . . , gs (X, t)} be as given above.
Definition 5.3 (Weak version). Let H
Let p be a prime not dividing any numerator or any denominator of the coefficients
e We say that p is admissible of type B w.r.t. f and H
e if p is
occurring in H.
e none of the elements in Sg is
admissible of type A w.r.t. f and if, for each g in H,
divisible by any of the factors of fp over Fp .

6

DEREJE K. BOKU, WOLFRAM DECKER, CLAUS FIEKER, AND ANDREAS STEENPASS

To see the relevance of this definition, consider the ideal
J = hx2 + xy + t, x + y + t − 1i =: hh1 , h2 i ⊆ Q[x, y, t]
and the minimal polynomial f = t3 + t + 1. If p = 3, then fp ≡ (t − 1)(t2 + t − 1) =:
f1,p · f2,p mod p and, using the degree reverse lexicographic ordering with x  y,
the reduced Gröbner bases of the ideals Jp + hf1,p i and Jp + hf2,p i in Fp [x, y, t] are
{1} and {t2 + t − 1, y + 1, x + t + 1}, respectively. In this case, Algorithm 1 cannot
be applied since the sizes of these sets do not fit. The calculation suggests that the
reason for this is that the element t − 1 ∈ Sh2 vanishes when reduced w.r.t. the set
{t − 1, t2 + t − 1}.
Next, consider the ideal J 0 = hx2 + xy + t, t2 x + yi =: hg1 , g2 i. Here, the
reduced Gröbner bases of the ideals Jp0 + hf1,p i and Jp0 + hf2,p i are {1} and {t2 +
t − 1, x + yt − t, y 2 − 1}, respectively. Again the sizes of these sets do not coincide,
hence, we still cannot apply Algorithm 1. Moreover, none of the coefficients in
Sg1 and Sg2 is divisible by either f1,p or f2,p which shows that the condition in
Definition 5.3 is not sufficient. Indeed, the element t2 ∈ Sg2 vanishes when reduced
w.r.t. the set {t2 + t − 1, t − 1}. Therefore, we may impose a stronger condition by
e none of the elements in Sg vanishes when reduced w.r.t.
saying that for all g ∈ H
the set {f1,p , . . . , frp ,p } (in some order) and thus reduce the probability that the
reconstruction fails. In the following example we see that this condition is still not
sufficient.
Consider the ideal J 00 = hx2 + xy + t, tx + y + ti =: hk1 , k2 i. The reduced
Gröbner bases of the ideals Jp00 + hf1,p i and Jp00 + hf2,p i are {t − 1, x − 1, y − 1} and
{t2 + t − 1, x + yt − y + t + 1, y 2 + yt + y + t − 1}, respectively. Although none of
the elements in Sk1 and Sk2 vanishes when reduced w.r.t. the set {t2 + t − 1, t −
1}, and the sizes of these sets coincide, we see that applying Algorithm 1 yields
{t2 − t + 1, x − 1, y 2 t2 + y 2 t − y 2 + yt2 + yt + t2 + t + 1} which is not the desired
result because the reduced Gröbner basis of Jp00 + hfp i is {t2 + t − 1, y + 1, x + t + 1}.
In practice, however, it is very unlikely that this case happens. It is, nevertheless,
important to address this problem. A possible way to handle this difficulty is to
refine Definition 5.3 as follows:
e = {g1 (X, t), . . . , gs (X, t)} be as
Definition 5.4 (Strong version). Let f and H
given above. Let p be an a prime which is admissible of type A w.r.t. f , and
write f = f1,p · · · frp ,p as in Definition 5.2. Suppose that p does not divide any
e For i = 1, . . . , rp ,
numerator or any denominator of the coefficients occurring in H.
e p ∪ {fi,p }i, and let G
e i,p be the reduced Gröbner basis of the ideal Iei,p .
set Iei,p := hH
e if for all indices i, j with i 6= j
We say that p is admissible of type B w.r.t. f and H
e i,p and G
e j,p coincide, and
a) the sizes of G
e
e j,p \ {fj,p }).
b) Lm(Gi,p \ {fi,p }) = Lm(G
In the above examples, the prime number 3 is not admissible of type B w.r.t.
t3 + t + 1 and the generators of each of the ideals J, J 0 and J 00 in the sense
of Definition 5.4. This is because in the first two cases, both conditions of this
definition are violated whereas in the third case, the second condition is not satisfied.
For the rest of our discussion we use the strong version of this definition.
We now turn our attention to the notion of lucky primes:
Definition 5.5 ([10]). Let Ie be an ideal given as above and let p be a prime number.
e be the reduced Gröbner basis of Ie and let G
e p be the reduced
Furthermore, let G
e
e
e p ) = Lm(G).
e
Gröbner basis of Ip . Then p is called lucky for I if and only if Lm(G
e
Otherwise p is called unlucky for I.

GRÖBNER BASES OVER ALGEBRAIC NUMBER FIELDS

Input

Ie

e 1,p
G
1

···

ep
G
1

···

Iep2

Iep1

e r ,p
G
p1 1

e 1,p
G
2

···

ep
G
2

e r ,p
G
p2 2

7

···

Iepk

e 1,p
G
k

···

···

level 1

e r ,p
G
pk
k

ep
G
k

level 2

level 3

Modular Reconstruction (over Q)
Figure 1. General scheme for the new algorithm
Since f is independent of X, we get, by Corollary 4.3, the isomorphism
Fp [X, t]/hfp i ∼
= Fp [X, t]/hf1,p i × . . . × Fp [X, t]/hfrp ,p i .
e H,
e and f be as above. Let p be a prime which is both admissible
Remark 5.6. Let I,
e as well as lucky for I.
e We work over Fp [X, t] equipped
of type B w.r.t. f and H
e p is the reduced
with the product ordering K . Suppose a set of polynomials G
e p \ {fp }) mod fi,p ⊆
Gröbner basis of the ideal Iep . For i = 1, . . . , rp , set Si := (G
Fp [X, t]/hfi,p i. Then for each i, the set Si ∪ {fi,p } is the reduced Gröbner basis of
e i,p be the
the ideal Iei,p (as in Definition 5.4) with high probability. Conversely, let G
0
e p be the set of polynomials that is obtained by
reduced Gröbner basis of Iei,p . Let G
applying Algorithm 1 coefficient-wise to the input


e 1,p \ {f1,p }, . . . , G
e r ,p \ {fr ,p }), (f1,p , . . . , fr ,p ) .
(G
p
p
p
e 0p ∪ {fp } is the reduced Gröbner basis of the ideal Iep with high probThen the set G
e p with high probability.
e 0p ∪ {fp } = G
ability. Hence, we have G
The main innovation of our new algorithm, which is illustrated in Figure 1, is as
follows: Instead of computing the reduced Gröbner bases at level 1, our algorithm
computes them at level 2. For the primes satisfying the conditions in Definition 5.4
(and only for those), the Chinese remainder algorithm for polynomials then come p i at this level are expected to be the
bines these results at level 3. The ideals hG
i
same as the ideals Iepi at level 1 with high probability (see Remark 5.6). The remaining parts of the computation are carried out in the same way as in the modular
algorithms described in [10].
Now we give a brief description of the new algorithm. In the beginning, randomly
choose a set P of prime numbers which are admissible of type A w.r.t. f . At level 2,
given a prime p ∈ P, factorize f ∈ Q[t] over Fp and compute, for each i, the reduced
e i,p of the ideal Iei,p corresponding to the i-th factor. If the prime p is
Gröbner basis G
e then lift these results via Chinese remaindering
admissible of type B w.r.t. f and H,
e p of Iep with high
for polynomials (at level 3) to obtain the reduced Gröbner basis G

8

DEREJE K. BOKU, WOLFRAM DECKER, CLAUS FIEKER, AND ANDREAS STEENPASS

probability. Repeat this process for every prime p ∈ P which is admissible of
type B, in the same way as in the modular algorithms in [10].
The main reason why the method to compute Gröbner bases over algebraic
number fields described above is faster than other known methods, see Section 8,
is that factorizing the minimal polynomial f in positive characteristic allows us to
compute in rings with minimal polynomials of degree much less than deg f : Experiments have shown that the performance of Gröbner basis computations over
simple algebraic extensions depends heavily on the degree of the minimal polynomial. Additionally, the computations are carried out over finite fields which avoids
the problem known as coefficient swell, and we do not directly use the computationally expensive arithmetic in K. Finally, the new method is a priori easily
parallelizable.
6. Modular Algorithms
e the modular algorithm
To compute the reduced Gröbner basis of the ideal I,
described in [10] first chooses a set of primes P and computes the reduced Gröbner
e p of Iep for each p ∈ P. It then uses the Chinese remainder algorithm and
bases G
e over Q with high
rational reconstruction to obtain the reduced Gröbner basis G
probability. Finally, it verifies the correctness of the result obtained in this way.
ep |
One of the problems after computing the set of reduced Gröbner bases GP := {G
p ∈ P} is that P may contain unlucky primes. To deal with such unlucky primes,
the following method is used, see [3]:
DeleteUnluckyPrimesSB ([10]): We define an equivalence relation on (GP,
P) by
e p , p) ∼ (G
e q , q) :⇐⇒ Lm(G
e p ) = Lm(G
eq ) .
(G
Then the equivalence class of largest cardinality1 is stored in (GP, P), the others
are deleted.
e p , p ∈ P, have the same set of leading monomials. Hence, we can
Now, all G
apply the Chinese remainder algorithm for integers and the rational reconstruction
algorithm to the coefficients of the Gröbner bases in GP to obtain a reduced Gröbner
e of Ie with high probability. Since we cannot check, however, whether P is
basis G
sufficiently large, a final verification step is needed. Since this may be expensive,
e we first perform a test in positive characteristic:
especially if Ie 6= hGi,
pTestSB ([10]): We randomly choose a prime p ∈
/ P which is admissible of
e We test if including this prime in the set P would improve
type B w.r.t. f and H.
e mapped to
the result. That is, explicitly test whether Ie reduces to zero w.r.t G
e
ep .
Fp [X, t], and vice-versa, whether G mapped to Fp [X, t] reduces to zero w.r.t. G
The advantage of this test is that it accelerates the algorithm enormously. Algorithm 2 is a modified version of Algorithm 1 in [10] (which is implemented in
Singular [7] in the library modstd.lib [9]), in the sense that we do apply modular methods not only once, but twice, where the second application is with respect
to the factors of the minimal polynomial f .
Now, taking Theorem 5.1 into account, we can compute a Gröbner basis of an
ideal in K[X] = Q(α)[X] as in Algorithm 3: We first map α to t and join the
minimal polynomial f ∈ Q[t] to the ideal to be considered. Then, after applying
Algorithm 2, we only need to map t back to α to get a Gröbner basis of the input
ideal.
1Here, we have to use a weighted cardinality count if Algorithm 2 requires more than one round
of the loop, see [3, Remark 5.7].

GRÖBNER BASES OVER ALGEBRAIC NUMBER FIELDS

9

Algorithm 2 Modified modular Gröbner bases algorithm over Q
e f i ⊆ T = Q[X, t] where H
e = {g1 (X, t), . . . , gs (X, t)} and
Input: an ideal Ie = hH,
f ∈ Q[t] is irreducible.
e ⊆ T , a Gröbner basis of Ie w.r.t. K .
Output: G
1: choose P, a set of random primes which are admissible of type A w.r.t. f
2: GP ←− {}
3: loop
4:
for p ∈ P do
Q
5:
factorize fp ∈ Fp [t] into irreducible factors fp = 1≤i≤rp fi,p
6:
for i = 1, . . . , rp do
e p ∪ {fi,p }i ⊆ Fp [X, t]
7:
Iei,p ←− hH
e i,p of Iei,p w.r.t. K
8:
compute the reduced Gröbner basis G
e over Fp then
9:
if p is admissible of type B w.r.t. f and H

e 1,p \ {f1,p }, . . . ,
10:
apply Algorithm 1 coefficient-wise to the input
G


e r ,p \ {fr ,p } , f1,p , . . . , fr ,p to obtain a set of polynomials G
ep ⊆
G
p
p
p
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

Fp [X, t]
e p ←− G
e p ∪ {fp }
G
else
e p ←− 0
G
ep }
GP ←− GP ∪ {G
(GP, P) ←− DeleteUnluckyPrimesSB(GP, P)
e ⊆ T by applying the Chinese remainder algorithm and the
lift (GP, P) to G
Farey rational map
e G,
e P) then
if pTestSB(I,
e
e then
if I reduces to zero w.r.t. G
e
e then
if G is the reduced Gröbner basis of hGi
e
return G
enlarge P

Algorithm 3 Modular Gröbner basis algorithm over K = Q(α) (nfmodStd)
Input: I = hg1 (X, α), . . . , gs (X, α)i ⊆ S = K[X].
Output: G ⊆ S, a Gröbner basis of I w.r.t. 1 .
e via the map sending α to t
1: map I to hHi
e
e
2: I ←− hHi + hf i
e of Ie w.r.t. K = (1 ,
3: call Algorithm 2 to compute the reduced Gröbner basis G
)
e to G via the map sending t to α
4: lift G
5: return G
Algorithm 2 is probabilistic in the sense that the test in lines 17 to 18 does
e = I.
e If I is homogeneous, however, the result G of Algonot guarantee that hGi
rithm 3 can be verified along the lines of [2, Theorem 7.1]. With this test included,
Algorithm 3 is deterministic.
Remark 6.1. Some parts of Algorithm 2 are inherently parallelizable. In the current implementation, see Section 8, we could easily take advantage of this thanks
to Singular’s parallel framework. We have, first of all, parallelized the for-loop
starting in line 4. This corresponds to the modular computations on level 1, see Figure 1. Besides this, we also make use of parallelization for the selection of primes

10 DEREJE K. BOKU, WOLFRAM DECKER, CLAUS FIEKER, AND ANDREAS STEENPASS

in line 1, for the application of the Farey rational map in line 16, and for the final
test in line 19. The for-loop starting in line 6, which corresponds to the modular
computations on level 2, is inherently parallelizable as well, but experiments have
shown that a parallel implementation of this step does not yield any further speedup
for our test cases.
7. Example
The following example illustrates how the new algorithm works:
Consider the ideal I = hx2 + ay, axy − x + ai ⊂ Q(a)[x, y] where a is a zero of the
polynomial f = t2 + 1 ∈ Q[t]. A Singular computation shows that the reduced
Gröbner basis of I with respect to the degree reverse lexicographical ordering (dp
in Singular) with x  y is
{y 2 + ax + ay, xy + ax + 1, x2 + ay} .
In the following, we show how this basis is obtained using our method: At level 1,
let us choose k = 2 with p1 = 5 and p2 = 13. At level 2, we have fp1 ≡ (t − 2)(t + 2)
mod p1 and fp2 ≡ (t − 5)(t + 5) mod p2 . Now, corresponding to each factor, we
compute, using Singular, the reduced Gröbner bases of the following ideals:
Ie1,p = hx2 + ty, txy − x + t, t − 2i ,
1

Ie2,p1 = hx2 + ty, txy − x + t, t + 2i ,
Ie1,p2 = hx2 + ty, txy − x + t, t − 5i ,
Ie2,p2 = hx2 + ty, txy − x + t, t + 5i .
>
>
>
>
>
>

ring r = 5, (x,y,t), (dp(2),dp(1));
ideal I1p1 = x2+ty, txy-x+t, t-2;
ideal I2p1 = x2+ty, txy-x+t, t+2;
option(redSB);
ideal S1 = std(I1p1);
S1;
S1[1]=t-2
S1[2]=y2+2x+2y
S1[3]=xy+2x+1
S1[4]=x2+2y
> ideal S2 = std(I2p1);
> S2;
S2[1]=t+2
S2[2]=y2-2x-2y
S2[3]=xy-2x+1
S2[4]=x2-2y
The Chinese remainder algorithm for polynomials combines these results at
level 3 to obtain the reduced Gröbner basis of Iep1 with high probability, as follows:
> list l = S1, S2;
> list m = t-2, t+2;
// CRA for polynomials (coefficient-wise):
> ideal G1p1 = chinrempoly(l, m);
> Gp1;
Gp1[1]=t2+1
Gp1[2]=y2+xt+yt
Gp1[3]=xy+xt+1
Gp1[4]=x2+yt

GRÖBNER BASES OVER ALGEBRAIC NUMBER FIELDS

11

Similarly, the reduced Gröbner basis of Iep2 , with high probability, is
> Gp2;
Gp2[1]=t2+1
Gp2[2]=y2+xt+yt
Gp2[3]=xy+xt+1
Gp2[4]=x2+yt
It is not hard to see that the primes p1 and p2 are admissible of type B w.r.t. f
e = {x2 + ty, txy − x + t}. Furthermore, it is also clear that they are lucky
and H
e f i. At this point we have to change the current base ring in
primes for Ie = hH,
Singular to characteristic zero in order to apply the Chinese remainder algorithm
for integers and to pull the modular coefficients back to the rational numbers.
/* Chinese remaindering for integers */
> ring s = 0, (x,y,t), (dp(2),dp(1));
> list l = imap(r, Gp1), imap(r, Gp2);
> intvec m = 5, 13;
> ideal j = chinrem(l, m);
> j;
j[1]=t2+1
j[2]=y2+xt+yt
j[3]=xy+xt+1
j[4]=x2+yt
/* rational reconstruction */
> j = farey(j, 5*13);
> j;
j[1]=t2+1
j[2]=y2+xt+yt
j[3]=xy+xt+1
j[4]=x2+yt
Note that the computed result already coincides with the reduced Gröbner basis
stated above. To simplify the presentation, we therefore skip some of the steps in
Algorithm 2, such as the final test. However, we have to map the result back to
the ring Q(a)[x, y] in Singular:
> ring sr = (0,a), (x,y,t), (dp(2),dp(1));
> minpoly = a2+1;
> ideal G = imap(s, j);
> G = subst(G, t, a);
> G = simplify(G, 2); // erase the zero entries
> G; // G is the reduced Groebner basis of I
G[1]=y2+ax+ay
G[2]=xy+ax+1
G[3]=x2+ay
Thus we get the same result as the one we mentioned at the beginning.
8. Implementation and Timings
We implemented Algorithm 3 in Singular in the library nfmodstd.lib [4] and
compared its performance against the implementation of [10, Algorithm 1] in the
Singular library modstd.lib (the command is modStd), the Singular command
std, and the Magma [5, 12] command GroebnerBasis. For modStd, we added
the minimal polynomial f to the given input ideal I (considered as an ideal in a
polynomial ring over a polynomial ring) and computed the reduced Gröbner basis
e + hf i w.r.t. K . For GroebnerBasis and std, we computed
of the ideal Ie = hHi

12 DEREJE K. BOKU, WOLFRAM DECKER, CLAUS FIEKER, AND ANDREAS STEENPASS

Example
Min. deg.
Ideal
Poly. of mi
I1
m1
2
I2
m2
5
I3a
m3
7
I3b
m3
7
I4
m4
6
I5
m5
12
I6
m6
2
I7
m7
8
I8
m8
7

Magma
Singular
Groebner
modStd
nfmodStd
std
Basis
1 c.
32 c.
1 c. 32 c.
1241.98
1.51
1.24
0.37
0.22 0.13
error
70.55
19.59
4.79
1.89 0.61
0.90
143.79
9.34
3.27 0.51
314.00 11212.00 1118.78 97.43 19.23
265.53 9163.38 567.03 686.01 99.41
2061.95
3321.28 256.58 430.23 71.47
2.93 8931.13
197.20
47.54 24.26
8.99
0.90
2044.08 195.41
8.54 1.87
- 15477.87 15274.97 4787.49 92.99 23.89

Table 1. Total running times in seconds for computing a Gröbner basis
of the considered ideals with the corresponding minimal polynomial via
GroebnerBasis, std, modStd and nfmodStd, using 1 core and 32 cores
where applicable

the reduced Gröbner basis of the ideal I over an algebraic number field with the
minimal polynomial f . Note that the implementation of our algorithm is internally
linked with the existing implementation of Algorithm 1 in [10].
We have nine benchmark problems to demonstrate the superiority of our new
algorithm (see appendix). The cyclic ideal Cn in n variables has become a benchmark problem for Gröbner basis techniques. For our algorithm, we have replaced
the coefficients of this ideal by a random element in Q(a) where a is an algebraic
number (see, for example, the ideal I6 in the appendix). Some of the benchmark
problems are chosen from [2, 11] (the ideals I1 and I2 are from [2], I6 and I7 are
from [11]) where the coefficients are replaced by a random algebraic number. The
minimal polynomials, selected for our computations, are:
m1 = a2 + 1 ,
m2 = a5 + a2 + 2 ,
m3 = a7 − 7a + 3 ,
m4 = a6 + a5 + a4 + a3 + a2 + a + 1 ,
m5 = a12 − 5a11 + 24a10 − 115a9 + 551a8 − 2640a7
+ 12649a6 − 2640a5 + 551a4 − 115a3 + 24a2 − 5a + 1 ,
m6 = a2 + 5a + 1 ,
m7 = a8 − 16a7 + 19a6 − a5 − 5a4 + 13a3 − 9a2 + 13a
+ 17 , and
m8 = a7 + 10a5 + 5a3 + 10a + 1 .
With respect to these minimal polynomials, timings are conducted by using
Singular 4.0.2 and Magma V2.21-2 on a Dell PowerEdge R720 machine with
two Intel Xeon E5-2690 CPUs, 16 cores and 32 threads in total, 2.9-3.8 GHz, and
192 GB of RAM running the Gentoo Linux operating system.
The results are summarized in Table 1. Some of the computations in Magma
did not finish within 12 hours. This is indicated by a dash (-). Note that in all
those cases, the computation also occupied an excessive amount of memory, more

GRÖBNER BASES OVER ALGEBRAIC NUMBER FIELDS

13

than 100 GB at the point when we interrupted it. All timings are in seconds. We
use the degree reverse lexicographical ordering (dp in Singular) for all examples.
In our implementation, the number of primes which are chosen in line 1 of
Algorithm 2 depends on the number of cores. For our timings, we started with 10
primes on one core and 25 primes on 32 cores. The runtime depends heavily on the
splitting behaviour of the minimal polynomial modulo the chosen primes. Finding
the optimal strategy for this is still under active research.
Remark 8.1. We understand that Magma has no parallel version of the Gröbner
basis algorithm which works over algebraic number fields. Therefore we have conducted the timings in Magma using one core only.
From Table 1, we see that the Singular commands std and modStd perform
well in comparison to the Magma command GroebnerBasis. However, one can see
that our algorithm nfmodStd is even much faster.
9. Acknowledgments
We would like to thank Gerhard Pfister for many fruitful discussions.
References
[1] W. W. Adams and P. Loustaunau. An introduction to Gröbner bases. American Mathematical
Society, 1994.
[2] E. A. Arnold. Modular algorithms for computing Gröbner bases. J. Symb. Comput.,
35(4):403–419, 2003.
[3] J. Böhm, W. Decker, C. Fieker, and G. Pfister. The use of bad primes in rational reconstruction. To appear in Math. Comp., 2015. http://arxiv.org/abs/1207.1651.
[4] D. K. Boku, W. Decker, and C. Fieker. nfmodstd.lib. A Singular 4-0-2 library for computing
Gröbner bases of ideals in polynomial rings over algebraic number fields, 2015. Included in
Singular 4-0-2 as algemodstd.lib and renamed to nfmodstd.lib for subsequent releases.
[5] W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. J.
Symb. Comput., 24(3-4):235–265, 1997. Computational algebra and number theory (London,
1993).
[6] D. Cox, J. Little, and D. O’Shea. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra. Springer, New York, third edition,
2007.
[7] W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 4-0-2 – A computer
algebra system for polynomial computations, 2015. http://www.singular.uni-kl.de.
[8] G.-M. Greuel and G. Pfister. A Singular introduction to commutative algebra. With contributions by Olaf Bachmann, Christoph Lossen and Hans Schönemann. Springer, Berlin, second
extended edition, 2007.
[9] A. Hashemi, G. Pfister, H. Schönemann, A. Steenpass, and S. Steidel. modstd.lib. A Singular 4-0-2 library for computing Gröbner bases of ideals using modular methods, 2014.
[10] N. Idrees, G. Pfister, and S. Steidel. Parallelization of modular algorithms. J. Symb. Comput.,
46(6):672–684, 2011.
[11] M. Noro. An efficient implementation for computing Gröbner bases over algebraic number
fields. In Mathematical software – ICMS 2006. Second international congress on mathematical software, Castro Urdiales, Spain, September 1–3, 2006. Proceedings, pages 99–109.
Springer, 2006.
[12] The Magma Group. The Magma Computational Algebra System V2.21-2, 2015. http://
magma.maths.usyd.edu.au.
[13] C. Traverso. Gröbner trace algorithms. In P. Gianni, editor, Symbolic and Algebraic Computation, volume 358 of Lecture Notes in Computer Science, pages 125–138. Springer, 1989.
[14] J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press,
Cambridge, third edition, 2013.

Appendix
The following are the benchmark problems used to demonstrate the efficiency
of Algorithm 3. They are available in the source code of the Singular library
nfmodstd.lib [4].

14 DEREJE K. BOKU, WOLFRAM DECKER, CLAUS FIEKER, AND ANDREAS STEENPASS

(1) ring R = (0,a), (x,y,z), dp;
minpoly = (a^2+1);
poly f1 = (a+8)*x^2*y^2+5*x*y^3+(-a+3)*x^3*z+x^2*y*z;
poly f2 = x^5+2*y^3*z^2+13*y^2*z^3+5*y*z^4;
poly f3 = 8*x^3+(a+12)*y^3+x*z^2+3;
poly f4 = (-a+7)*x^2*y^4+y^3*z^3+18*y^3*z^2;
ideal I1 = f1,f2,f3,f4;
(2) ring R = (0,a), (x,y,z), dp;
minpoly = (a^5+a^2+2);
poly f1 = 2*x*y^4*z^2+(a-1)*x^2*y^3*z+(2*a)*x*y*z^2+7*y^3
+(7*a+1);
poly f2 = 2*x^2*y^4*z+(a)*x^2*y*z^2-x*y^2*z^2+(2*a+3)*x^2*y*z
-12*x+(12*a)*y;
poly f3 = (2*a)*y^5*z+x^2*y^2*z-x*y^3*z+(-a)*x*y^3+y^4
+2*y^2*z;
poly f4 = (3*a)*x*y^4*z^3+(a+1)*x^2*y^2*z-x*y^3*z+4*y^3*z^2
+(3*a)*x*y*z^3+4*z^2-x+(a)*y;
ideal I2 = f1,f2,f3,f4;
(3) ring R = (0,a), (v,w,x,y,z), dp;
minpoly = (a^7-7*a+3);
poly f1 = (a)*v+(a-1)*w+x+(a+2)*y+z;
poly f2 = v*w+(a-1)*w*x+(a+2)*v*y+x*y+(a)*y*z;
poly f3 = (a)*v*w*x+(a+5)*w*x*y+(a)*v*w*z+(a+2)*v*y*z
+(a)*x*y*z;
poly f4 = (a-11)*v*w*x*y+(a+5)*v*w*x*z+(a)*v*w*y*z+(a)*v*x*y*z
+(a)*w*x*y*z;
poly f5 = (a+3)*v*w*x*y*z+(a+23);
ideal I3a = f1,f2,f3,f4,f5;
(4) ring R = (0,a), (u,v,w,x,y,z), dp;
minpoly = (a^7-7*a+3);
poly f1 = (a)*u+(a+2)*v+w+x+y+z;
poly f2 = u*v+v*w+w*x+x*y+(a+3)*u*z+y*z;
poly f3 = u*v*w+v*w*x+(a+1)*w*x*y+u*v*z+u*y*z+x*y*z;
poly f4 = (a-1)*u*v*w*x+v*w*x*y+u*v*w*z+u*v*y*z+u*x*y*z
+w*x*y*z;
poly f5 = u*v*w*x*y+(a+1)*u*v*w*x*z+u*v*w*y*z+u*v*x*y*z
+u*w*x*y*z+v*w*x*y*z;
poly f6 = u*v*w*x*y*z+(-a+2);
ideal I3b = f1,f2,f3,f4,f5,f6;
(5) ring R = (0,a), (w,x,y,z), dp;
minpoly = (a^6+a^5+a^4+a^3+a^2+a+1);
poly f1 = (a+5)*w^3*x^2*y+(a-3)*w^2*x^3*y+(a+7)*w*x^2*y^2;
poly f2 = (a)*w^5+(a+3)*w*x^2*y^2+(a^2+11)*x^2*y^2*z;
poly f3 = (a+7)*w^3+12*x^3+4*w*x*y+(a)*z^3;
poly f4 = 3*w^3+(a-4)*x^3+x*y^2;
ideal I4 = f1,f2,f3,f4;
(6) ring R = (0,a), (w,x,y,z), dp;
minpoly = (a^12-5*a^11+24*a^10-115*a^9+551*a^8-2640*a^7
+12649*a^6-2640*a^5+551*a^4-115*a^3+24*a^2-5*a+1);
poly f1 = (2*a+3)*w*x^4*y^2+(a+1)*w^2*x^3*y*z+2*w*x*y^2*z^3
+(7*a-1)*x^3*z^4;
poly f2 = 2*w^2*x^4*y+w^2*x*y^2*z^2+(-a)*w*x^2*y^2*z^2
+(a+11)*w^2*x*y*z^3-12*w*z^6+12*x*z^6;

GRÖBNER BASES OVER ALGEBRAIC NUMBER FIELDS

15

poly f3 = 2*x^5*y+w^2*x^2*y*z-w*x^3*y*z-w*x^3*z^2+(a)*x^4*z^2
+2*x^2*y*z^3;
poly f4 = 3*w*x^4*y^3+w^2*x^2*y*z^3-w*x^3*y*z^3
+(a+4)*x^3*y^2*z^3+3*w*x*y^3*z^3+(4*a)*y^2*z^6-w*z^7
+x*z^7;
ideal I5 = f1,f2,f3,f4;
(7) ring R = (0,a), (u,v,w,x,y,z), dp;
minpoly = (a^2+5*a+1);
poly f1 = u+v+w+x+y+z+(a);
poly f2 = u*v+v*w+w*x+x*y+y*z+(a)*u+(a)*z;
poly f3 = u*v*w+v*w*x+w*x*y+x*y*z+(a)*u*v+(a)*u*z+(a)*y*z;
poly f4 = u*v*w*x+v*w*x*y+w*x*y*z+(a)*u*v*w+(a)*u*v*z
+(a)*u*y*z+(a)*x*y*z;
poly f5 = u*v*w*x*y+v*w*x*y*z+(a)*u*v*w*x+(a)*u*v*w*z
+(a)*u*v*y*z+(a)*u*x*y*z+(a)*w*x*y*z;
poly f6 = u*v*w*x*y*z+(a)*u*v*w*x*y+(a)*u*v*w*x*z
+(a)*u*v*w*y*z+(a)*u*v*x*y*z+(a)*u*w*x*y*z
+(a)*v*w*x*y*z;
poly f7 = (a)*u*v*w*x*y*z-1;
ideal I6 = f1,f2,f3,f4,f5,f6,f7;
(8) ring R = (0,a), (w,x,y,z), dp;
minpoly = (a^8-16*a^7+19*a^6-a^5-5*a^4+13*a^3-9*a^2+13*a+17);
poly f1 = (-a^2-1)*x^2*y+2*w*x*z-2*w+(a^2+1)*y;
poly f2 = (a^3-a-3)*w^3*y+4*w*x^2*y+4*w^2*x*z+2*x^3*z+(a)*w^2
-10*x^2+4*w*y-10*x*z+(2*a^2+a);
poly f3 = (a^2+a+11)*x*y*z+w*z^2-w-2*y;
poly f4 = -w*y^3+4*x*y^2*z+4*w*y*z^2+2*x*z^3+(2*a^3+a^2)*w*y
+4*y^2-10*x*z-10*z^2+(3*a^2+5);
ideal I7 = f1,f2,f3,f4;
(9) ring R = (0,a), (t,u,v,w,x,y,z), dp;
minpoly = (a^7+10*a^5+5*a^3+10*a+1);
poly f1 = v*x+w*y-x*z-w-y;
poly f2 = v*w-u*x+x*y-w*z+v+x+z;
poly f3 = t*w-w^2+x^2-t;
poly f4 = (-a)*v^2-u*y+y^2-v*z-z^2+u;
poly f5 = t*v+v*w+(-a^2-a-5)*x*y-t*z+w*z+v+x+z+(a+1);
poly f6 = t*u+u*w+(-a-11)*v*x-t*y+w*y-x*z-t-u+w+y;
poly f7 = w^2*y^3-w*x*y^3+x^2*y^3+w^2*y^2*z-w*x*y^2*z
+x^2*y^2*z+w^2*y*z^2-w*x*y*z^2+x^2*y*z^2+w^2*z^3
-w*x*z^3+x^2*z^3;
poly f8 = t^2*u^3+t^2*u^2*v+t^2*u*v^2+t^2*v^3-t*u^3*x
-t*u^2*v*x-t*u*v^2*x-t*v^3*x+u^3*x^2+u^2*v*x^2
+u*v^2*x^2+v^3*x^2;
ideal I8 = f1,f2,f3,f4,f5,f6,f7,f8;

16 DEREJE K. BOKU, WOLFRAM DECKER, CLAUS FIEKER, AND ANDREAS STEENPASS

Dereje Kifle Boku, Department of Mathematics, University of Kaiserslautern, Erwin-Schrödinger-Str., 67663 Kaiserslautern, Germany
E-mail address: boku@mathematik.uni-kl.de
Wolfram Decker, Department of Mathematics, University of Kaiserslautern, ErwinSchrödinger-Str., 67663 Kaiserslautern, Germany
E-mail address: decker@mathematik.uni-kl.de
Claus Fieker, Department of Mathematics, University of Kaiserslautern, ErwinSchrödinger-Str., 67663 Kaiserslautern, Germany
E-mail address: fieker@mathematik.uni-kl.de
Andreas Steenpass, Department of Mathematics, University of Kaiserslautern, Erwin-Schrödinger-Str., 67663 Kaiserslautern, Germany
E-mail address: steenpass@mathematik.uni-kl.de

