BORDER BASES FOR POLYNOMIAL RINGS OVER
NOETHERIAN RINGS

arXiv:1405.0472v5 [cs.SC] 2 Feb 2017

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

Abstract. The theory of border bases for zero-dimensional ideals has attracted
several researchers in symbolic computation due to their numerical stability and
mathematical elegance. As shown in (Francis & Dukkipati, J. Symb. Comp., 2014),
one can extend the concept of border bases over Noetherian rings whenever the corresponding residue class ring is finitely generated and free. In this paper we address
the following problem: Can the concept of border basis over Noetherian rings exists for ideals when the corresponding residue class rings are finitely generated but
need not necessarily be free modules? We present a border division algorithm and
prove the termination of the algorithm for a special class of border bases. We show
the existence of such border bases over Noetherian rings and present some characterizations in this regard. We also show that certain reduced Gröbner bases over
Noetherian rings are contained in this class of border bases.

1. Introduction
Gröbner bases theory for polynomial rings over fields gives an algorithmic technique
to determine a vector space basis of the residue class ring modulo a zero dimensional
ideal (Buchberger, 1965). The theory of Gröbner bases was extended to polynomial
rings over Noetherian commutative rings with unity a few decades ago (e.g. Trinks,
1978; Möller, 1988; Zacharias, 1978). For a good exposition on Gröbner bases over
rings one can refer to (Adams & Loustaunau, 1994).
Certain recent developments in cryptography and other fields have led to renewed
interest in polynomial rings over rings (Greuel et al., 2011). For instance, free residue
class rings over Z[x] called ideal lattices (Lyubashevsky & Micciancio, 2006) have been
shown to be isomorphic to integer lattices, an important cryptographic primitive (Ajtai, 1996) and certain cyclic lattices in Z[x] have been used in NTRU cryptographic
schemes (Hoffstein et al., 1998). Boolean polynomial rings over a boolean ring is
another important example of a polynomial ring over a ring since it can be used to
solve combinatorial puzzles like Sudoku (Sato et al., 2011). Another example is the
polynomial rings over Z/2k . They are used to prove the correctness of data paths in
system-on-chip design (Greuel et al., 2011).
Border bases, an alternative to Gröbner bases, are well studied for polynomial
rings over fields (Kehrein et al., 2005; Kehrein & Kreuzer, 2005). Though border
bases are restricted to zero dimensional ideals, the motivation for border bases comes
from the numerical stability of border bases over Gröbner bases (Stetter, 2004).
There has been considerable interest in the theory of border bases, from characterization (Kehrein & Kreuzer, 2005) to methods of computation (Kehrein & Kreuzer,
1

2

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

2006) to computational hardness (Ananth & Dukkipati, 2012). The concept of border bases can be easily extended to polynomial rings over rings if the corresponding
residue class ring has a free A-module representation w.r.t. some monomial order
and is finitely generated as an A-module (Francis & Dukkipati, 2014). In this paper,
we study border bases for ideals in polynomial rings over Noetherian commutative
rings in a more general set up.

2. Background & Preliminaries
2.1. Notations. A polynomial ring in indeterminates x1 , . . . , xn over a Noetherian,
commutative ring A is denoted by A[x1 , . . . , xn ]. Throughout this paper, the rings
we study are rings with unity. The set of all ideals of A is denoted by Id(A). When
A = k, where k is a field, we write it as k[x1 , . . . , xn ]. A monomial in indeterminates
x1 , . . . , xn is denoted by xα , where α ∈ Nn , and the set of all monomials is denoted
by Mn . By ‘term’ we mean cxα , where c ∈ A and c 6= 0. We will denote all the
terms in A[x1 , . . . , xn ] by Tn . Let T ⊆ Tn be a set of terms, possibly infinite. We
define the monomial part of T , denoted by Mon(T ), as Mon(T ) = {xα ∈ Mn : axα ∈
T, for some nonzero a ∈ A}.
P
A polynomial f is denoted by f = α∈Λ aα xα , where aα ∈ A, α ∈ Nn and Λ ⊆ Nn
is a finite set. Λ is called the support of the polynomial f , denoted by supp(f ). The
set of monomials appearing with nonzero coefficients in f is denoted by Mon(f ).
α
The set of all terms appearing in f is denoted by Ter(f ),
S i.e. Ter(f ) = {aα x |
α ∈ Λ}. If F is a set of polynomials then Mon(F ) = f ∈F Mon(f ). Similarly,
S
Ter(F ) = f ∈F Ter(f ). Given a set of terms T and an ideal a in A[x1 , . . . , xn ], the
set of residue class elements of T modulo a is denoted by T + a. That is T + a =
{axα + a : axαP
∈ T }. Given a set of polynomials F the span of F over A is given by
SpanA (F ) = { si=1 ai fi : ai ∈ A, fi ∈ F, s ∈ N}.
With respect to a monomial order ≺, the leading monomial, leading coefficient
and leading term of a polynomial f ∈ A[x1 , . . . , xn ] are denoted by Lm(f ), Lc(f ) and
Lt(f ) respectively. That is, we have Lt(f ) = Lc(f ) Lm(f ). Given a set of polynomials
S, possibly infinite, Lt(S) denotes the set of all leading terms of polynomials in S.
The leading term ideal (or initial ideal) of S is denoted by hLt(S)i and is given by
hLt(S)i = h{Lt≺ (f ) | f ∈ S}i. Similarly, the leading monomial ideal and the leading
coefficient ideal of S are denoted by hLm(S)i and hLc(S)i respectively. Note that the
leading coefficient ideal is an ideal in the coefficient ring, A. The ideal generated by
the polynomials f1 , . . . , fs is denoted by hf1 , . . . , fs i. Also a set of polynomials S is
said to be monic w.r.t. a monomial order if the leading coefficient of each polynomial
in S is 1.
2.2. Border bases over a field. Here we briefly recall definitions related to border
bases.
Definition 2.1. A finite set of monomials O ⊆ Mn is said to be an order ideal if it is
closed under forming divisors i.e., for xα ∈ Mn , if xβ ∈ O and xα |xβ , then xα ∈ O.

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

3

Definition 2.2. Let O be an order ideal. The border of O is the set ∂O = (x1 O ∪
. . . ∪ xn O) \ O. The first border closure of O is defined as the set O ∪ ∂O and it is
denoted by ∂O.
Note that ∂O is also an order ideal. By convention, if O = ∅, then we set ∂O = {1}.
Definition 2.3. Let O = {xα1 , . . . , xαs } be an order ideal, and let ∂O = {xβ1 , . . . , xβt }
be its border. A set of polynomials B = {b1 , . . . , bt } ⊆ k[x1 , . . . , xn ] is called an Oborder prebasis if the polynomials have the form
s
X
βj
bj = x −
cij xαi ,
i=1

where cij ∈ k for 1 ≤ i ≤ s and 1 ≤ j ≤ t.
Definition 2.4. Let O = {xα1 , . . . , xαs } be an order ideal and B = {b1 , . . . , bt } be
an O-border prebasis consisting of polynomials in a ⊆ k[x1 , . . . , xn ]. We say that the
set B is an O-border basis of a if the residue classes of xα1 , . . . , xαs form a k-vector
space basis of k[x1 , . . . , xn ]/a.
The existence and uniqueness of border bases are established in (Kehrein & Kreuzer,
2005). Given an ideal one can show that there exists a border bases that do not correspond to Gröbner bases for any term ordering. An example of such a border basis
is given in (Kehrein & Kreuzer, 2006).
2.3. The A-module A[x1 , . . . , xn ]/a. From now on, unless otherwise specified we
deal with polynomials over a Noetherian, commutative ring A. Given an ideal a in
A[x1 , . . . , xn ], using Gröbner basis methods one can give an A-module representation
of residue class ring A[x1 , . . . , xn ]/a if it is finitely generated (Francis & Dukkipati,
2014). We describe this briefly below and for more details one can refer to (Francis
& Dukkipati, 2014). The notation is mostly borrowed from (Adams & Loustaunau,
1994).
Let G = {gi : i = 1, . . . , t} be a Gröbner basis for a. For each monomial, xα , let
Jxα = {i : lm(gi ) | xα , gi ∈ G} and IJxα = h{lc(gi ) : i ∈ Jxα }i. Note that IJxα is
an ideal in A. We refer to IJxα as the leading coefficient ideal w.r.t. G. Let CJxα
represent a set of coset representatives of the equivalence classes in A/IJxα . Given a
m
P
polynomial, f ∈ A[x1 , . . . , xn ], let f =
ai xαi mod hGi, where ai ∈ A, i = 1, . . . , m.
i=1

If A[x1 , . . . , xn ]/hGi is an A-module generated by m elements, then corresponding to
the coset representatives, CJxα1 , . . . , CJxαm , there exists an A-module isomorphism,
φ : A[x1 , . . . , xn ]/hGi −→ A/IJxα1 × · · · × A/IJxαm
m
X
ai xαi + hGi 7−→ (c1 + IJxα1 , · · · , cm + IJxαm ),

(1)

i=1

where ci = ai mod IJxαi and ci ∈ CJxαi . We refer to A/IJxα1 ×· · ·×A/IJxαm as the Amodule representation of A[x1 , . . . , xn ]/a w.r.t. G. If IJxαi = {0}, we have CJxαi = A,
for all i = 1, . . . , m. This implies A[x1 , . . . , xn ]/a ∼
= Am , i.e. A[x1 , . . . , xn ]/a has an

4

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

A-module basis and it is free. In this case, we define A[x1 , . . . , xn ]/a to have a “free
A-module representation w.r.t. G”. The necessary and sufficient condition for an
A-module A[x1 , . . . , xn ]/a to have a free A-module representation is given in (Francis
& Dukkipati, 2014). It makes use of the the concept of ‘short reduced Gröbner basis’
introduced in (Francis & Dukkipati, 2014) which we briefly describe below.
Definition 2.5. Let a be an ideal in A[x1 , . . . , xn ] and let G be its reduced Gröbner
basis as described in (Pauer, 2007). Consider the isomorphism in (1). G is called a
short reduced Gröbner basis if the size of the generating set of the leading coefficient
ideal, IJxα , of each leading monomial, xα in G, is minimal.
One can define reduced Gröbner bases over rings exactly as that of fields but
it may not exist in all the cases. The definition of reduced Gröbner basis given
by (Pauer, 2007) is a generalization of the concept over fields to rings that also
ensures the existence of such a basis for every ideal in the polynomial ring. The
short reduced Gröbner basis of an ideal is not to be confused with strong Gröbner
basis (Adams & Loustaunau, 1994, Definition 4.5.6.). Strong Gröbner basis exists
only if the coefficient ring is a PID. In a PID, strong Gröbner basis coincides with
the short reduced Gröbner basis.
Proposition 2.6. (Francis & Dukkipati, 2014, Proposition 3.12) Let a ⊆ A[x1 , . . . , xn ]
be a nonzero ideal such that A[x1 , . . . , xn ]/a is finitely generated. Let G be a short reduced Gröbner basis for a w.r.t. some monomial ordering, ≺. Then, A[x1 , . . . , xn ]/a
has a free A-module representation w.r.t. G if and only if G is monic.
Example 2.7. Let G = {3x, 5x, y} be the Gröbner basis of an ideal a in Z[x, y].
The short reduced Gröbner basis of a is given by Gred = {x, y}. It is monic and a
Z-module basis of Z[x, y]/a is given by {1 + a}.
With the above result the concept of border bases can be extended to ideals in
polynomial rings over rings, in the cases where the corresponding residue class rings
are finitely generated and have a free A-module representation w.r.t. some monomial
order (Francis & Dukkipati, 2014, Section 6). One can show that all the characterizations in (Kehrein & Kreuzer, 2005) hold true when the residue class ring is free. For
the sake of completeness, we state the definition of border bases in this case below.
Definition 2.8. Let O = {xα1 , . . . , xαs } be an order ideal and B = {b1 , . . . , bt } ⊆
A[x1 , . . . , xn ] be an O-border prebasis. Let a ⊆ A[x1 , . . . , xn ] be an ideal such that
A[x1 , . . . , xn ]/a is finitely generated and is a free A-module. Then B is said to be an
O-border basis if B ⊆ a and O forms an A-module basis for A[x1 , . . . , xn ]/a.
3. Order Functions and Border Prebasis Division Algorithm
The following notion that we introduce in this paper is crucial to the theory of border
bases that we develop here.
Definition 3.1 (Order Function). Let Id(A) be the set of all ideals in the ring,
A. A mapping I : Mn → Id(A) is said to be an order function if xβ | xα implies
I(xβ ) ⊆ I(xα ), for all xα , xβ ∈ Mn . From now on we denote I(xα ) by Ixα .

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

5

Clearly, the Gröbner basis of an ideal ‘fixes’ an order function. Consider the
leading coefficient ideal, IJxα that we constructed in Section 2.3 w.r.t. G. Since Jxα
is a saturated set, the mapping xα 7→ IJxα is an order function, which is denoted by
I (G) .
Definition 3.2. An order function I : Mn → Id(A) is said to be proper if it maps
only finitely many monomials to proper ideals in A.
Example 3.3. Consider the mapping I : N2 −→ Id(Z). Let I(1) = {0}, I(x1 ) = h3i
and every other monomial be mapped to h1i. We see that for any xα ∈ N2 such that
x1 | xα , h3i ⊆ I(xα ). Therefore, I is a proper order function.
We define order ideal with respect to a proper order function I.
Definition 3.4. For each xα ∈ Mn and a proper order function I, fix Cxα ⊆ A, a
set of coset representatives of A/Ixα . A set of terms OI ⊆ Tn is said to be an order
ideal w.r.t. I if for all xα ∈ Mn , cxα ∈ OI if and only if c ∈ Cxα .
Note that for each monomial xα , one can choose any set of coset representatives
of A/Ixα and with each choice we have a different order ideal.
Example 3.5. Consider the polynomial ring Z[x, y] and let the mapping I be such
that I1 = {0}, Ix = h4i, Iy = h3i, Ix2 = h2i and the rest of the monomials map to
h1i. I is clearly a proper order function. Let the set of coset representatives be the
following, C1 = Z, Cx = {0, 1, 2, 3}, Cy = {0, 1, 2}, Cx2 = {0, 1} and for all the other
monomials, xα , Cxα = {0}. Then, OI = {a1 , a2 x, a3 y, a4 x2 | a1 ∈ C1 , a2 ∈ Cx , a3 ∈
Cy , a4 ∈ Cx2 } is an order ideal corresponding to I.
Example 3.6. Now consider a polynomial ring
k[u1 , u2 ][x, y, z] and let I be an order function defined by I1 = {0}, Ix = {0},
Iy = hu21 i, Iz = hu22 −3u1 i, Ix2 = h0i, Ixy = hu21 , u22 −1i, Ixz = hu1 , u2 i and rest of the
monomials mapping to h1i. I is a proper order function. Let C1 , Cx , Cy , Cz , Cx2 , Cxy , Cxz
represent the nonzero set of coset representatives. Then O0 I = {a1 , a2 x, a3 y, a4 z, a5 x2 ,
a6 xy, a7 xz | a1 ∈ C1 , a2 ∈ Cx , a3 ∈ Cy , a4 ∈ Cz , a5 ∈ Cx2 , a6 ∈ Cxy , a7 ∈ Cxz } is
an order ideal corresponding to I.
In sequel, we write order ideal OI as O and its dependence on the order function
is implicitly assumed. It is important to note that unlike in the case of fields, the
order ideal in the case of polynomial rings over rings have both monic and nonmonic
monomials.
Given an order ideal O we introduce two types of borders: a monomial border
∂Om and a scalar border ∂Os .
Definition 3.7. Given an order ideal O the monomial border of O is defined as
∂Om = {x1 · Mon(O) ∪ . . . ∪ xn · Mon(O)} \ Mon(O).
Definition 3.8. Let O be an order ideal with respect to a proper order function I. For
each xα such that Ixα 6= h1i define ∂Oxα = {c1 xα , . . . , cs xα }, where Ixα = hc1 , . . . , cs i

6

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

for some c1 , . . . , cs ∈ A. The scalar border of an order ideal is defined as
[
∂Os =
∂Oxα .
xα ∈Mn
Ixα 6=h1i

Definition 3.9. The border of the order ideal O, denoted as ∂O, is defined as ∂O =
∂Om ∪ ∂Os .
Example 3.10. Consider Example 3.5. The set of monic border terms that form
the monomial border is ∂Om = {xy, y 2 , x3 , x2 y} and the scalar border is ∂Os =
{4x, 3y, 2x2 }. Hence, the border of the order ideal is ∂O = {xy, y 2 , x3 , x2 y, 4x, 3y, 2x2 }.
Example 3.11. Consider Example 3.6. The monomials that form the monomial
border is ∂O0 m = {x3 , x2 y, x2 z, xy 2 , xyz, xz 2 , y 2 , yz, z 2 } and the scalar border is the
set ∂O0 s = {u21 y, (u22 − 3u1 )z, u21 xy, (u22 − 1)xy, u1 xz, u2 xz}. Hence border of the
order ideal is ∂O0 = {x3 , x2 y, x2 z, xy 2 , xyz, xz 2 , y 2 , yz, z 2 , u21 y, (u22 −3u1 )z, u21 xy, (u22 −
1)xy, u1 xz, u2 xz}.
We define ∂ 0 O = O and 0th border closure as ∂ 0 O = {axα | cxα ∈ O, for some c ∈
Cxα , c 6= 0 and a ∈ c+Ixα }. Note that in the case of fields these quantities are defined
as ∂ 0 O = ∂ 0 O = O (Kehrein & Kreuzer, 2006).
The definitions of first and higher order border closures are given below.
Definition 3.12. The first border closure ∂O of an order ideal O is defined as
∂O ={axα | ∃c ∈ A such that cxα ∈ O ∪ ∂Os ,
a ∈ A or xα ∈ ∂Om }.
Proposition 3.13. The first border closure, ∂O, of an order ideal, O is an order
ideal.
Proof. We fix Ixα = {0} for all xα ∈ ∂O. By Definition 3.12 three cases arises:
xα ∈ ∂Om or there exists c ∈ A such that cxα ∈ O or cxα ∈ ∂Os . Let xα ∈ ∂Om .
Suppose xβ |xα for some xβ ∈ Mn , then clearly, xβ ∈ Mon(O)∪∂Om . If xβ ∈ Mon(O),
then there exists some d ∈ Cxβ such that dxβ ∈ O. Therefore, in either case xβ ∈ ∂O.
In the second case, let cxα ∈ O. Suppose xβ |xα for some xβ ∈ Mn . By the closure
property of O, dxβ ∈ O for some d ∈ Cxβ . Therefore, xβ ∈ ∂O. In the third case,
let cxα ∈ ∂Os . Suppose xβ |xα for some xβ ∈ Mn . This implies that xβ ∈ Mon(O).
Thus, xβ ∈ ∂O.

The monomial part of the first border closure defined as the set of monomials in
∂O, is a finite set and it is represented as Mon(∂O). It is interesting to see that since
Ixα = {0} for all xα ∈ Mon(∂O), the scalar border for k ≥ 2 is an empty set and one
needs to consider only the monomial border.
Definition 3.14. The k th border of an order ideal O for k

1 is defined as

∂ k O = {x1 · Mon(∂ k−1 O) ∪ . . . ∪ xn · Mon(∂ k−1 O)} \ Mon(∂ k−1 O),
where Mon(∂ k−1 O) is the monomial part of the (k − 1)th border closure.

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

7

Definition 3.15. For k ≥ 2, the k th border closure of an order ideal is defined as
∂ k O = {axα | a ∈ A, xα ∈ ∂ k O ∪ ∂ k−1 Om }.
Example 3.16. Consider Example 3.5. The set of monic border terms that form
the monomial border is ∂Om = {xy, y 2 , x3 , x2 y} and the scalar border is ∂Os =
{4x, 3y, 2x2 }. The second border of the order ideal, O, is the set, ∂ 2 O = {xy 2 , y 3 ,
x4 , x3 y, x2 y 2 }.
Example 3.17. Consider Example 3.6. The second border of the order ideal, O0 is
the set, ∂ 2 O0 = {y 3 , y 2 z, yz 2 , z 3 , x4 , x3 y, x3 z, x2 y 2 , x2 yz, x2 z 2 , xy 3 , xyz 2 , xy 2 z, xz 3 }.
Remark 3.18. The k th border closure is an infinite set of terms for k ≥ 0. Further,
for k ≥ 1, ∂ k O is closed under division and hence the set of monomials corresponding
to it, Mon(∂ k O), mimics the case of fields.
The following example explains the borders and border closures of an order ideal.
Example 3.19. Let the order function I : M2 → Id(Z) be defined as follows: I1 = 0,
Ix = 0, Iy = h4i, Ixy = h2i and for other monomials I is mapped to h1i. The order
ideal corresponding to I, OI = {a, bx, cy, dxy : a, b ∈ Z, c ∈ {0, 1, 2, 3}, d ∈ {0, 1}}.
The 0th border closure is given by {a, bx, cy, dxy : a, b ∈ Z\{0}, c ∈ Z\h4i, d ∈ Z\h2i}.
Figure 1 shows a few terms from the 0th border closure.

Figure 1. 0th border closure
The first border is hx2 , 2xy, y 2 , x2 y, xy 2 , 4yi. The first border closure is given by
hax2 , bxy, cy 2 , dx2 y, exy 2 , f y : a, c, d, e ∈ Z, b ∈ h2i, f ∈ h4i. Figure 2 is an illustration of the same.
For k ≥ 2 the k th borders are exactly as that of fields. Figure 3 shows the borders for
k = 2, 3. Note that the figure depicts the borders and not the border closures.
We give below certain properties of order ideals, their borders and border closures.
These properties are analogous to the case of polynomial rings over fields.
Proposition 3.20. Let O be an order ideal and ∂Om be its monomial border. Then
(1) For k ≥ 1, the k th monomial border closure of O, Mon(∂ k O) is the following
disjoint union, Mon(O) ∪ ∂Om ∪ (∪ki=2 ∂ k O).

8

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

Figure 2. First border closure

Figure 3. 2nd , 3rd border closure
(2) For k ≥ 1, ∂ k Om = Mnk · Mon(O) \ Mn<k . Mon(O), where ∂ k Om = ∂ k O for
k ≥ 2.
(3) A monomial, xα ∈ Mn is divisible by xβ ∈ ∂Om if and only if xα ∈ Mn \
Mon(O).
Proof. (1) The proof is by induction on k. For k = 1, clearly the monomials in
the first border closure are elements of the set Om ∪ ∂Om . From the definition of
monomial border of O we have that Om and ∂Om are disjoint. Suppose that the claim
is true for the k th monomial border closure. For k + 1, ∂ k+1 Om = ∂ k Om ∪ ∂ k+1 O. It
is easy to verify that the sets ∂ k Om and ∂ k+1 O are disjoint.
(2) The claim follows from the observation that ∂ k O = ∂ k Om \ ∂ k−1 Om .
(3) We have xβ ∈ ∂Om . This implies that there exists xγ ∈ Om and an indeterminate
xi0 such that xβ = xi0 xγ . We have xi0 xγ |xα . If xα ∈ Om then xi0 xγ ∈ Om which is a
contradiction. Now consider a monomial xα ∈ Tn \ O. Then, xα ∈ ∂Om or xα ∈ ∂ k O
for some k ≥ 2. If xα ∈ ∂ k O then it implies that there exists a monomial xγ of degree
k − 1 and a xβ ∈ ∂Om such that xα = xγ xβ . The claim follows.

Now we introduce some concepts that are essential for the division algorithm.
Definition 3.21. The index of a term cxα w.r.t. an order ideal, O is defined as
indO (cxα ) = min{k ∈ N | cxα ∈ ∂ k O}.

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

9

Definition 3.22. Let f ∈ A[x1 , . . . , xn ] be any nonzero polynomial with support,
supp(f ), then the index of f w.r.t. an order ideal, O is defined as
indO (f ) =

max indO (cα xα ).

α∈supp(f )

Example 3.23. Consider Example 3.5. The set of monic border terms that form
the monomial border is ∂Om = {xy, y 2 , x3 , x2 y} and the scalar border is ∂Os =
{4x, 3y, 2x2 }. Then indO (3x) = 0, indO (xy) = 1 and indO (xy 2 + 8x + 7y) = 2.
Example 3.24. Consider Example 3.6. The monomials that form the monomial
border is ∂O0 m = {x3 , x2 y, x2 z, xy 2 , xyz, xz 2 , y 2 , yz, z 2 } and the scalar border is the
set ∂O0 s = {u21 y, (u22 − 3u1 )z, u21 xy, (u22 − 1)xy, u1 xz, u2 xz}. Then
indO0 ((3u2 + u2 )x) = 0, indO0 (u1 x2 y) = indO0 ((u21 + u2 )xz) = 1 and indO0 (xy 3 + 8x) =
2.
For any polynomial, the terms of highest index are grouped together to form a
border form analogous to the leading term in Gröbner bases theory. We define this
below.
Definition 3.25. Let f ∈ A[x1 , . . . , xn ] be a nonzero polynomial such that the
indO (f ) = i0 . The border form of f w.r.t. O is defined as
X
BFO (f ) =
cα x α ,
α∈supp(f ),cα ∈A
indO (cα xα )=i0

a polynomial in A[x1 , . . . , xn ].
Note that unlike leading term of a polynomial in Gröbner bases theory that is
always a monomial, border form can be a polynomial. The concept of leading term
ideal has an analogous form in border bases theory called the border form ideal.
Definition 3.26. The border form ideal of an ideal a in A[x1 , . . . , xn ] w.r.t. an order
ideal O is defined as
BFO (a) = hBFO (f ) | f ∈ ai.
Example 3.27. Consider Example 3.5. Let f = xy 2 + 2x2 y 2 + xy + 3x + 2. Then
the index of f w.r.t. the order ideal O is equal to 2. The border form of f is the
polynomial, BFO (f ) = xy 2 + 2x2 y 2 .
Example 3.28. Consider Example 3.6. Let f = 2xy 2 + (u1 − u2 )xz + 3x + 2. Then
the index of f w.r.t. the order ideal O0 is equal to 2. The border form of f is the
polynomial, BFO0 (f ) = 2xy 2 + (u1 − u2 )xz.
We now give the definition of border prebasis for an order ideal, O.
Definition 3.29. Let O be an order ideal, and ∂O = {c1 xα1 , . . . , cs xαs } be its border.
Let Cxαi be the set of coset representatives of A/Ixαi . A finite set of polynomials G
= {g1 , . . . , gs } ⊆ A[x1 , . . . , xn ] is said to be an O-border prebasis if gi = ci xαi − hi ,
where hi ∈ A[x1 , . . . , xn ] satisfying Ter(hi ) ⊆ O \ {axαi | a ∈ Cxαi }, i = 1, . . . , s.

10

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

Example 3.30. We consider Example 3.5. The set G = {g1 , . . . , g7 }, where g1 =
xy − x, g2 = y 2 − y, g3 = x3 − 2y, g4 = x2 y − x2 + 10, g5 = 4x − 2y, g6 = 3y − 3x and
g7 = 2x2 − x + 5 is an O-border prebasis but it is not acyclic. Let G0 = {g10 , . . . , g70 }
where g10 = xy − x, g20 = y 2 − y, g30 = x3 − x2 + 6, g40 = x2 y − y + 5, g50 = 4x − 7,
g60 = 3y − x and g70 = 2x2 − 2y − 3x which is also a O-border prebasis but it is acyclic
since the permutation of G0 , {g10 , g20 , g30 , g40 , g70 , g60 , g50 } satisfies the acyclicity condition.
Example 3.31. Consider Example 3.6. The set G =
{g1 , . . . , g15 }, where g1 = x3 − 3, g2 = x2 y − 3u1 y, g3 = x2 z − 2z, g4 = xy 2 − x + 10,
g5 = xyz − 11xy, g6 = xz 2 − u2 u21 x2 , g7 = y 2 − x + u1 u2 , g8 = yz − 3y + 2,
g9 = z 2 + 5xz + 11u1 x, g10 = u21 y + u2 x + 3, g11 = (u22 − 3u1 )z − u22 y, g12 =
u21 xy + 3u1 x − 2z, g13 = (u22 − 1)xy + 2x2 , g14 = u1 xz + 3u1 x2 , g15 = u2 xz +
2u1 xy + 4x2 − 4z − 10u1 y + 14 is an acyclic O-border prebasis since the following
permutation of G, {g1 , g2 , g3 , g4 , g5 , g6 , g7 , g8 , g9 , g14 , g15 , g13 , g12 , g11 , g10 } satisfies the
acyclicity condition.
Note that unlike in fields, for a monomial in the border of O, we can have more
than one polynomial in the O-border prebasis but only one polynomial corresponding
to a term in the border. With the definition of O-border prebasis, we now give a
procedure for division of any polynomial in A[x1 , . . . , xn ] with the O-border prebasis.
Algorithm 3.32. Let O be an order ideal. Let Mon(O) = {xα1 , . . . , xαt } be its
monomial part. Let ∂Om = {xβ1 , . . . , xβs0 } and ∂Os = {cs0 +1 xβs0 +1 , . . . , cs xβs } be its
monomial border and scalar border respectively. Let G = {g1 , . . . , gs } ⊆ A[x1 , . . . , xn ]
be an O-border prebasis. For f ∈ A[x1 , . . . , xn ] we perform the following steps.
(1) Initialize f1 = . . . = fs = 0, a1 = . . . = at = 0 and h = f .
(2) If h = 0 return (f1 , . . . , fs , a1 , . . . , at ).
(3) If indO (h) = 0 then find b1 , . . . , bt ∈ A such that h = b1 xα1 + . . . + bt xαt . Set
ai = bi for each 1 ≤ i ≤ t. Return (f1 , . . . , fs , a1 , . . . , at ).
(4) If indO (h) = 1 and h contains a term dxβ such that xβ ∈ ∂Om then goto
Step 5. Else, let h = d1 xγ1 + . . . + dj xγj such that indO (h) = indO (d1 xγ1 ) and
indO (d1 xγ1 ) ≥ . . . ≥ indO (dj xγj ). Find bµ+1 , . . . , bs ∈ A such that d1 xγ1 =
bs0 +1 (cs0 +1 xβs0 +1 ) + . . . + bs (cs xβs ). Subtract bs0 +1 gs0 +1 + . . . + bs gs from h, add
bi to fi for s0 + 1 ≤ i ≤ s and return to Step 2.
(5) Else, let h = d1 xγ1 +. . .+dj xγj such that indO (h) = indO (xγ1 ) and indO (d1 xγ1 ) ≥
. . . ≥ indO (dj xγj ). Determine xβi ∈ ∂Om with the smallest i such that
xγi = xµ xβi and deg(xµ ) = indO (h) − 1. Subtract d1 xµ gi from h, add d1 xµ to
fi and return to Step 2.
This procedure over rings differs from the case of fields only in Step 4. The termination of the above method is not assured because of the possibility that for a given
polynomial, f , a monomial in its support identified with index 0 in Step 3 may again
have an index 1 after Step 4. Therefore, we cannot assume the reduction in index
values at every step of the procedure.

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

11

4. Acyclic Border Prebases and Termination of Border Division
Algorithm
Here, we identify a special class of O-border prebases called acyclic O-border prebases
for which the termination of the border division algorithm can be established.
Definition 4.1. A O-border prebasis G = {g1 , . . . , gs } is said to be acyclic if there
k,
exists a permutation of G, {gi1 , . . . , gis } such that for any gij , gik , where j
exactly one of the following conditions are satisfied
(1) cj BFO (gij ) = ck BFO (gik ) for any cj , ck ∈ A or
(2) dj xαj ∈ ∂O and dj xαj ∈ supp(gij ) implies ck xαj ∈
/ supp(gik ) for some ck , dj ∈
A.
The ordered set of acyclic O-border prebasis that satisfies the permutation given
above is called a ‘well ordered’ acyclic O-border prebasis. We now show the correctness and termination of Algorithm 3.32 when the O-border prebasis is acyclic.
Proposition 4.2. (Border Division Algorithm) Consider a polynomial f ∈
A[x1 , . . . , xn ]. If the O-border prebasis G = {g1 , . . . , gs } is acyclic, then Algorithm
3.32 terminates for f and returns a tuple,
(f1 , . . . , fs , a1 , . . . , at ) ∈ (A[x1 , . . . , xn ])s × At
such that
f = f1 g1 + . . . + fs gs + a1 xα1 + . . . + at xαt ,
and deg(fi ) ≤ indO (f ), for i = 1, . . . , s with fi gi 6= 0.
Proof. We first describe the execution of the algorithm. In Step 4, indO (d1 xγ1 ) = 1
and d1 xγ1 ∈ SpanA (h∂OiA ). This implies that d1 ∈ Ixγ1 , where Ixγ1 is an ideal
generated by hu1 , . . . , uk i, ui xγ1 ∈ ∂Os , 1 ≤ i ≤ k. Thus, there exists l1 , . . . , lk ∈ A
P
P
such that d1 = ki=1 li ui . Hence, d1 xγ1 = ss0 +1 bi (ci xβi ), where ci xβi ∈ ∂Os and
bi = lj when ci xβi = uj xγ1 for some j ∈ {1, . . . , k}, and bi = 0, otherwise. The other
steps, due to the absence of scalar border terms, mimics the border basis division in
fields (Kehrein & Kreuzer, 2005, Proposition 3). We prove that the representation,
f = f1 g1 + . . . + fs gs + a1 xα1 + . . . + at xαt + h,
computed by the algorithm is valid in every step. Clearly, it is satisfied in Step 1.
In Step 4 we subtract (bs0 +1 gs0 +1 + . . . + bs gs ) from h. These bi s are then added to
fi s, i.e. fi = fi + bi , s0 + 1 ≤ i ≤ s. Similarly in Step 5, from h we subtract d1 xµ gi
and we add d1 xµ to fi . The constants a1 , . . . , at are modified only in Step 3. The
representation of f is valid because indO (h) = 0. If the algorithm terminates, h = 0
and we have a valid representation.
Now we prove that deg(fi ) ≤ indO (f ) for all i = 1, . . . , s. In Step 5 of the
algorithm, where we divide using the monomial border, our choice of the term d1 xµ
is such that
deg(dxµ ) = indO (h) − 1. In Step 4, where we divide using the scalar border, the
index of the intermediate polynomial, h is 1. The bi , i = 1, . . . , s are constants
and the degree of fi , i = 1, . . . , s are therefore zero. All the other steps in the

12

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

algorithm do not affect fi , i = 1, . . . , s. Also, in the algorithm the index of the
intermediate polynomial, h never increases. From the above steps, the inequality
deg(fi ) ≤ indO (f ) − 1 for all i = 1, . . . , s follows.
Next, we prove that the algorithm terminates on all inputs. In Step 4, indO (h) = 1
and Ter(h) ⊆ SpanA (Mon(O))∪SpanA (∂Os ) = SpanA (Mon(O)). We claim that Step
4 terminates after a finite number of steps for an acyclic O-border prebasis. Let h =
d1 xα1 +. . .+dt xαt . For simplicity, let us assume that the acyclic O-border prebasis, G
is well ordered. It can easily be seen that g1 will be used atmost once in Step 4, while
g2

G\{g1 ,g2 }

g1

G\{g1 ,g2 }

g2

g2 will be used at most twice (h −
→ h1 −−−−−→+ h2 −
→ h3 −−−−−→+ h4 −
→ h5 ).
2
Similarly, any gi will be used atmost O i ) times. For the set G, therefore Step
4 is executed at most O s3 ) times. All the other steps of the division correspond
to either order ideal, monomial border or the k th order border, k 1 and therefore
mimic the border division in fields. Hence, the termination is guaranteed by (Kehrein
& Kreuzer, 2005, Proposition 3).

The border division algorithm gives us the remainder upon division by an acyclic
O-border prebasis as a part of its output. We now give a formal definition for
remainder.
Definition 4.3. Let O be an order ideal and Mon(O) = {xα1 , . . . , xαt }, its monomial part. Let G = {g1 , . . . , gs } be the O-border prebasis. The O-remainder of a
polynomial f w.r.t. G, if it exists, is given as
remO,G (f ) = a1 xα1 + . . . + at xαt ,
where f = f1 g1 + . . . + fs gs + a1 xα1 + . . . + at xαt and ai ∈ A for all i = 1, . . . , t is
a representation computed by the border division algorithm whenever the algorithm
terminates.
5. Order Span and Acyclic Border Bases
Consider the case when A[x1 , . . . , xn ]/a is finitely generated. Using the order function
we define a generating set for A[x1 , . . . , xn ]/a that also satisfies a weaker form of the
linear independence property.
Definition 5.1 (Order span). Let a be an ideal and let I be a proper order function
and B = {xα1 , . . . , xαm } be a finite set of monomials of size m such that xα ∈
/ B if
α
n
and only if Ixα = h1i, where x ∈ M . Let CIxα be the coset representatives of the
equivalence classes of A/Ixα . Then we say the set of residue classes of B forms an
order span for A[x1 , . . . , xn ]/a w.r.t. I if it satisfies the following properties.
(i) B + a generates A[x1 , . . . , xn ]/a as an A-module and
A[x1 , . . . , xn ]/a = {

m
X

ai xαi + a | ai ∈ CIxαi , xαi ∈ B}.

i=1

Pm

αi

(ii) If i=1 ai x + a = 0, where m ∈ N, xαi ∈ B and ai 6= 0 for all i = 1, . . . , m,
then for some j ∈ {1, . . . , m}, aj ∈ Ixαj .

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS
0

13

0

(iii) If there exists an order function I such that Ixα ⊆ Ixα for some xα ∈ Mn and
0
0
0
0
B = {xα : Ixα 6= h1i} satisfies (i) and (ii) w.r.t. I , then I = I.
P
Remark 5.2. The linear independence property requires that if ki=1 ai xαi + a = 0
then for all i ∈ {1, . . . , k}, ai ∈ Ixαi . Therefore, the second condition in Definition 5.1
is a weaker form of the linear independence property. In fact, in the case of fields
and residue class rings with a free A-module representation, the second condition
automatically implies the linear independence property.
Remark 5.3. The third condition in Definition 5.1 can be interpreted as a minimality
condition on the spanning set. Over fields, linear independence of the spanning set
ensures minimality but over rings it has to be specified separately. Consider the
0
ideal a = h4x1 , x1 2 , x2 i in Z[x1 , x2 ]. Let I and I be two order functions. Define
0
I1 = 0, Ix1 = h2i and for all the other monomials xα , Ixα = h1i. Similarly define I1 =
0
0
0
0, Ix1 = h4i and for all the other xα ∈ M2 , Ixα = h1i. Both I and I satisfy the first
0
two conditions of the order span. However, since Ix1 (= h4i) ( Ix1 (= h2i), it is w.r.t.
0
the second order function, I that we define the order span of Z[x1 , x2 ]/h4x1 , x1 2 , x2 i.
Corollary 5.4. Let a be an ideal such that A[x1 , . . . , xn ]/a is finitely generated. Let
G = {g1 , . . . , gt } be a Gröbner basis of an ideal a and I (G) the order function fixed
by G. Then,
(1) The order function I (G) is proper,
(2) The finite order span of A[x1 , . . . , xn ]/a w.r.t. I (G) is given by
B = {xα : lt(gi ) - axα , for some nonzero a ∈ A, gi ∈ G}
We now provide a better interpretation of the mapping described by (1) in terms
of order span.
Proposition 5.5. Let a be an ideal in A[x1 , . . . , xn ]. Let I be a proper order function
/ B,
and B = {xα1 , . . . , xαm } be a finite set of monomials of size m such that if xα ∈
α
n
Ixα = h1i, where x ∈ M . Consider a mapping,
φ : A[x1 , . . . , xn ]/a −→ A/Ixα1 × · · · × A/Ixαm
f + a 7−→ (c1 + Ixα1 , · · · , cm + Ixαm ),
where ci ∈ CIxαi for all i ∈ {1, . . . , m}. Then, φ is an isomorphism if B forms an
order span for A[x1 , . . . , xn ]/a.
Proof. Let B form an order span for A[x1 , . . . , xn ]/a. We first show that the mapping
φ is well defined. Consider a polynomial f ∈ A[x1 , . . . , xn ]. Suppose
φ(f + a) = (c1 + Ixα1 , · · · , cm + Ixαm ) and
φ(f + a) = (c01 + Ixα1 , · · · , c0m + Ixαm ),
where ci , c0i ∈ CIxαi , for all i = 1, . . . , m. This implies (ci − c0i ) ∈ Ixαi , i = 1, . . . , m.
Since the difference of two different coset representatives cannot give the zero coset,
we have ci = c0i for all i = 1, . . . , m. Thus φ is well defined.

14

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

Clearly, φ is a surjective map by construction. We now have to prove that φ is an
injective mapping. Consider a polynomial f ∈ A[x1 , . . . , xn ] such that φ(f + a) =
(0, . . . , 0). Let us assume that f ∈
/ a. Since B forms an order span for A[x1 , . . . , xn ]/a,
m
P
we can obtain ci ∈ CIxαi , i = 1, . . . , m such that f =
ci xαi mod a. Further, atleast
i=1

one of the ci , i ∈ {1, . . . , m}, is nonzero. This implies that φ(f + a) also maps to
(c1 , . . . , cm ). Therefore φ is not a well defined mapping. This is a contradiction and
f ∈ a. Thus, the kernel of φ, ker(φ) = {0 + a}. This implies that φ is an injective
mapping. Hence, it follows that φ is an isomorphism.

Definition 5.6. Let a be an ideal such that A[x1 , . . . , xn ]/a is a finitely generated Amodule. Let O be an order ideal and G = {g1 , . . . , gs } be an acyclic O-border prebasis
consisting of polynomials in a. G is an acyclic O-border basis of a if Mon(O) is an
order span of A[x1 , . . . , xn ]/a.
The next proposition shows that these polynomials indeed generate the ideal in a.
Proposition 5.7. Let a be an ideal such that A[x1 , . . . , xn ]/a is finitely generated as
an A-module. Let O be an order ideal and let G = {g1 , . . . , gs } be an acyclic O-border
basis for a. Then a is generated by G.
Proof. Let Mon(O) = {xα1 , . . . , xαt } be the monomial part of O and G = {g1 , . . . , gs }
be an acyclic O-border basis of a. Consider, f ∈ a. By Algorithm 4.2, we have
f1 , . . . , fs ∈ A[x1 , . . . , xn ] and a1 , . . . , at ∈ A such that
f = f1 g1 + . . . + fs gs + a1 xα1 + . . . + at xαt .
(2)
P
Pt
Ps
t
Now, f − i=1 fi gi ∈ a. This implies, i=1 ai xαi ∈ a. Let h = i=1 ai xαi . Suppose
h 6= 0, then ai ∈
/ Ixαi \ {0}, for all i = 1, . . . , t. If ai ∈ Ixαi , for all i = 1, . . . , t, then
indO (h) = 1. Then, (2) is not a valid output of Algorithm 4.2. But we are also
given that G is P
an acyclic border basis of a. The order span property of border basis
implies that if ti=1 ai xαi ∈ a for ai 6= 0 for all i = 1, . . . , t, then ai ∈PIxαi for some
i ∈ {1, . . . , t}. This is a contradiction. Hence, h = 0. We have, f = si=1 fi gi . The
other inclusion follows from the fact that G ⊆ a.

We need to verify if an acyclic O-border basis exists for every ideal, a in A[x1 , . . . , xn ].
We first address, below, whether an acylic O-border basis for a given an order ideal,
O, exists. We also prove the uniqueness of the acyclic O-border basis.
Theorem 5.8. Let O be an order ideal, and let a be an ideal such that A[x1 , . . . , xn ]/a
is a finitely generated A-module. If Mon(O) is an order span then there exists a
unique acyclic O-border basis for a.
Proof. Let Mon(O) = {xα1 , . . . , xαt } be the monomial part of O, and let ∂O =
{c1 xβ1 , . . . , cs xβs } be the border of O. We now prove that an O-border basis exists
for a. Since Mon(O) is an order span basis, for each ci xβi ∈ ∂O one can find
P
(i)
(i)
aj xαi s ∈ O such that ci xβi = tj=1 aj xαj mod a. We define G as
βi

G = {ci x −

t
X
j=1

(i)

aj xαj | 1 ≤ i ≤ s}.

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

15

Clearly,
G is an acyclic O-border prebasis. Now, G ⊆ a and A[x1 , . . . , xn ]/a =
P
{ ai xαi + a | xαi ∈ Mon(O) and ai ∈ A}. Hence, G is an O-border basis of a.
To prove the uniqueness of O-border basis, consider two acyclic O-border bases
for a. Let G = {g1 , . . . , gt } and G = {g10 , . . . , gt0 } such that
βi

gi = ci x −

t
X

(i)

(i)

0(i)

0(i)

aj xαj , where each aj xαj ∈ O and,

j=1

gi0 = ci xβi −

t
X

aj xαj , where each aj xαj ∈ O.

j=1

We have,
gi −

gi0

=

t
X

(i)
aj x α j

j=1

−

t
X

0(i)

aj xαj ∈ a.

j=1

This implies,
t
X
0(i)
(i)
(aj − aj )xαj ∈ a.
j=1
(i)

0(i)

Since aj and aj are coset representatives of A/Ixαj and the difference of two dif0(i)
(i)
ferent cosets cannot be a zero coset, we have aj = aj . Therefore, gi = gi0 . Hence,
the acyclic O-border basis of a is unique.

Thus, the question of existence of a border basis for an ideal reduces to the following
questions. Given an ideal a, (i) does there always exist a proper order function, I
such that the monomial part of the order ideal, Mon(O) constructed from I forms
an order span for A[x1 , . . . , xn ]/a and (ii) will the corresponding O-border basis be
acyclic. We use the theory of Gröbner bases to establish the result.
Theorem 5.9. Given an ideal a such that A[x1 , . . . , xn ]/a is finitely generated as
an A-module, there always exists an acyclic border basis of a corresponding to some
order ideal, O.
Proof. Let ≺ be a monomial order on A[x1 , . . . , xn ]. Let G0 = {g10 , . . . , gt0 } be a
Gröbner basis of a. Consider the order function fixed by G, I (G) . Since A[x1 , . . . , xn ]/a
is finitely generated, the mapping is proper. Let O≺ be the order ideal corresponding to I (G) . It follows from Corollary 5.4 that Mon(O≺ ) forms an order span. Let
∂O≺ = {c1 xβ1 , . . . , cs xβs } be the border of O≺ . Let G be the O≺ -border prebasis
constructed along the same lines as in the proof of Theorem 5.8. Therefore, each
polynomial gi in G is of the form,
gi = ci xβi −

t
X
j=1

(i)

where ci xβi ∈ ∂O and each aj xαj ∈ O.

(i)

aj xαj , i = 1, . . . , s,

16

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS
(i)

For any gi ∈ G, monomial ordering imposes that for every nonzero aj xαj , xαj ≺
xβi . Also, for two distinct border terms ci xβi and cj xβj such that xβi 6= xβj , either
xβi ≺ xβj or xβj ≺ xβi . The acyclic property of G follows from these two observations.
Theorem 5.8 implies that G forms a unique acyclic O≺ -border basis for a.

For any polynomial f ∈ A[x1 , . . . , xn ], given an acylic O-border prebasis, G and
an order ideal, O, O-remainder of f is denoted by remO,G (f ) (Definition 4.3).
Proposition 5.10. Let a ⊆ A[x1 , . . . , xn ] be an ideal such that A[x1 , . . . , xn ]/a is
finitely generated as an A-module and G ⊆ a be an acyclic O-border basis of a. For
any f ∈ A[x1 , . . . , xn ], f ∈ a if and only if remO,G (f ) = 0.
Proof. Let Mon(O) = {xα1 , . . . , xαt } be the monomial part of O and G = {g1 , . . . , gs }
be an acyclic O-border basis of a. By Algorithm 4.2, we have f1 , . . . , fs ∈ A[x1 , . . . , xn ]
and a1 , . . . , at ∈ A such that
f=

s
X

fi gi + remO,G (f ),

(3)

i=1

P
aj x . If remO,G (f ) = 0 then f = si=1 fi gi . Hence f ∈ a.
P
Now let f ∈ a. Then f − si=1 fi gi ∈ a. This implies, remO,G (f ) ∈ a. Suppose
remO,G (f ) is not equal to zero. The proof proceeds along the same lines as the
proof of Proposition 5.7, where we take h = remO,G (f ) and arrive at a contradiction.
Hence, when f ∈ a the remainder of f w.r.t. G is zero.


where remO,G (f ) =

Pt

j=1

αj

The above proposition enables us to solve the ideal membership problem provided
the acyclic border basis of the ideal is known. However, it must be noted that the
remainder on division by an acyclic O-border basis for any f ∈ A[x1 , . . . , xn ] is not
unique.
Below we define the normal form of a polynomial w.r.t. an acyclic border basis.
Definition 5.11. Let a be an ideal such that A[x1 , . . . , xn ]/a is finitely generated
as an A-module. Let G ⊆ a be an acyclic O-border basis for a. Let Mon(O) =
{xα1 , . . . , xαt } be the monomial part of O, CIxαi be the set of coset representatives of
the equivalence classes A/Ixαi and f be any polynomial in A[x1 , . . . , xn ]. Let r be a
polynomial given by r = a1 xα1 + · · · + at xαt , where ai ∈ CIxαi , 1 ≤ i ≤ t. Then r is
said to be the normal form of f if f = r mod a.
The normal form of a polynomial is denoted by NFO,G (f ). We now prove that
every polynomial f in A[x1 , . . . , xn ] has a unique normal form.
Proposition 5.12. Let a ⊆ A[x1 , . . . , xn ] be an ideal such that A[x1 , . . . , xn ]/a is
finitely generated as an A-module. Let G ⊆ a be an acyclic O-border basis for a. For
any polynomial f in A[x1 , . . . , xn ], the normal form of f is unique.
Proof. Let Mon(O) = {xα1 , . . . , xαt } be the monomial part of O. Let s0 ≤ t be the
number of monomials in the scalar border, ∂Os and G = {g1 , . . . , gs } be an acyclic

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

17

O-border basis of a. The existence of a normal form, NFO,G (f ) for any polynomial
f ∈ A[x1 , . . . , xn ] is a consequence of the following equality,
A[x1 , . . . , xn ]/a = {

k
X

ai xαi + a | ai ∈ CIxαi }.

i=1

Now, we prove the uniqueness of the normal form of f . Let r1 and r2 be two different
normal forms for f . Then f = r1 mod a and
P f = r2 mod a. This
P implies, r1 =
r2 mod a. Therefore, r1 − r2 ∈ a. Let r1 = ti=1 bi xαi and r2 = ti=1 b0i xαi , where
P
bi and b0i are coset representatives in CIxαi . Then, r1 − r2 = ti=1 (bi − b0i )xαi . If
r1 6= r2 , then there is atleast one i such that bi 6= b0i . This implies that bi − b0i 6= 0.
Since bi and b0i are coset representatives of distinct cosets, bi − b0i ∈
/ Ixαi . Therefore,
(r1 − r2 ) ∈
/ a. Hence a contradiction. Thus r1 = r2 and the normal form of a
polynomial is unique.

The below result states that if we can associate a monomial order to an order ideal
O, then the reduced Gröbner basis of a w.r.t. to that monomial order is a subset of
the acyclic border basis associated with O.
Proposition 5.13. Let a be an ideal. Let ≺ be a monomial order. Let O≺ be an order
ideal corresponding to ≺ such that Mon(O) forms an order span for A[x1 , . . . , xn ]/a.
Then Pauer reduced Gröbner basis (Pauer, 2007) of a w.r.t. ≺ is a subset of the
acyclic O-border basis of a.
Proof. Let Mon(O≺ ) = {xα1 , . . . , xαt } be the monomial part of O≺ and ∂O≺ =
{c1 xβ1 , . . . , cs xβs } be the border of O≺ . Let G = {g1 , . . . , gs } be the acyclic O≺ -border
basis for a. The acyclic O≺ -border basis is constructed as in the proof of Theorem 5.9.
Since G is an acyclic O≺ -border basis we have from Proposition 5.10 that for any
f ∈ a, f reduces to zero. This implies that G is a Gröbner basis of a. Further,
hLt(a)i is generated by ∂O≺ . Recall that, hLc(α, a)i = hLc(f ) : f ∈ a, Lm(f ) = xα i
and hLc(< α, a)i = hLc(f ) : f ∈ a, α ∈ deg(f ) + Mn , Lm(f ) 6= xα i. Clearly, for
each monomial xα , in the monomial part, Mon(O≺ ), hLc(α, a)i = Ixα . From the
definition of order ideal hLc(α, a)i 6= h1i. For each monomial xα in the monomial
border, ∂O≺m , hLc(α, a)i = h1i. Also, for each monomial xα ∈ Lm(G), we have
Gen(α, a) = {η(a, hLc(< α, a)i) : a ∈ Gen(hLc(α, a)i)} \ {0},
where η(a, hLc(< α, a)i) maps to an element in the coset a + hLc(< α, a)i. Consider
the set, ∂O≺red = {cxα ∈ ∂O≺ : c ∈
/ hLc(< α, a)i}. This set contains all the terms of
α
the form cx in the border ∂O≺ such that c cannot be expressed as a combination
of leading coefficients of those monomials that properly divide xα . Clearly, ∂O≺red ⊆
∂O≺ . Let Gred ⊆ G consist of polynomials in G with the border term in ∂O≺red . It
can easily be seen that hLt(a)i = h∂O≺red i. Therefore, Gred is a Gröbner basis for a.
Also, it is clear from the construction of ∂O≺red that Gen(α, a) = {c : cxα ∈ ∂O≺red }.
We now prove that G satisfies the two properties of Pauer’s reduced Gröbner basis.

18

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

The bijectivity of the map,
φ : {g ∈ Gred : deg(g) = α} −→ Gen(α, a)
φ(g) 7−→ Lc(g)
follows from the observation that corresponding to each border term cxβ ∈ ∂O≺ ,
there is exactly one polynomial g ∈ G such that the border term in g is cxβ . If we
had not considered the reduced border ∂O≺red , then for all g ∈ G \ Gred , φ(g) will
map to zero. Also, each polynomial gi ∈ Gred is of the form,
ci x β i −

t
X

(i)

(i)

aj xαj where ci xβi ∈ ∂O≺ and aj xαj ∈ O≺ .

j=1
(i)

(i)

Since for each aj xαj , aj ∈ A/Ixαj we have that
(i)
(i)
η(aj , hLc(αj , a)i) = aj . Hence Gred satisfies the second condition of Pauer’s reduced
Gröbner basis. Therefore, Gred is a reduced Gröbner basis for a.

Theorem 5.14. Let a be a nonzero ideal in A[x1 , . . . , xn ], O be an order ideal and
∂O = {c1 xβ1 , . . . , cs xβs } be its border. Let Mon(O) = {xα1 , . . . , xαt } be the monomial
part of O and G = {g1 , . . . , gs } be an acyclic O-border prebasis. Then the following
statements are equivalent.
G is an acyclic O-border basis for a.
G
f ∈ a if and only if f −
→+ 0.
fP∈ a if and only if there exists f1 , . . . , fs ∈ A[x1 , , . . . , xn ] such that f =
s
i=1 fi gi and max{deg(fi ) | fi gi 6= 0, i = 1, . . . , s} = indO (f ) − 1.
(iv) The border form of a, BFO (a) = hc1 xβ1 , . . . , cs xβs i.

(i)
(ii)
(iii)

Proof. (i) ⇒ (ii). The claim follows from the proof of Proposition 5.10.
(ii) ⇒ (iii). Let f ∈ a. By the border division algorithm, there exists
Ps f 1 , . . . , f s ∈
A[x1 , , . . . , xn ], deg(fi ) ≤ indO (f ) − 1, 1 ≤ i ≤ s such that f =
i=1 fi gi . Assume that max{deg(fi )} indO (f ) − 1. It can easily be verified that indO (fi gi ) ≤
indO (gi ) + deg(fi ). The definition of O-border prebasis implies that indO (gi ) = 1.
Thus indO (fi gi ) ≤ deg(fi ) + 1 indO (f ) − 1 + 1. Thus indO (fi gi ) indO (f ). Also
it can be seen that, indO (f + g) ≤ max{indO (f ), indO (g)}, when either indO (f ) ≥ 1
or indP
O (g) ≥ 1. Thus,
indO ( si=1 fi gi ) indO (f ). This is a contradiction. Hence max{deg(fi )} = indO (f )−
1.
(iii) ⇒ (iv) Since each gi ∈ a and BFO (gi ) = ci xβi , we have hc1 xβ1 , . . . , cs xβs i ⊆
BFO (a). Consider a polynomial f ∈ a. Suppose indO (f ) ≥ 1, then by Definitions 3.22
and 3.25 each term in BFO (f ) is divisible by cxβ ∈ ∂O. Hence, it follows that
BFO (f ) ∈ hc1 xβ1 , . . . , cs xβs i.
Let I be the proper order function associated with the order ideal O. Now let us
assume
there exists a polynomial f ∈ a \ {0} such that indO (f ) = 0 i.e.,
Pt that αthe
i
f = i=1P
ci x where ci ∈
/ Ixαi . Then by hypothesis, there exist fi s, 1 ≤ i ≤ s, such
s
that f = i=1 fi gi and max{deg(fi ) | fi gi 6= 0, i = 1, . . . , s} = 0 − 1 = −1. This is

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

19

not possible since deg(f ) ≥ 0 for all f ∈ A[x1 , . . . , xn ]. This implies that f = 0 which
is a contradiction. Therefore, indO (f ) ≥ 1. Thus, BFO (a) ⊆ hc1 xβ1 , . . . , cs xβs i. The
claim follows.
(iv) ⇒ (i). Consider a polynomial f ∈ A[x1 , . . . , xn ]. By the border division algorithm, we have f1 , . . . , fs ∈ A[x1 , . . . , xn ] and a1 , . . . , at ∈ A such that
f = f1 g1 + · · · + fs gs + a1 xα1 + · · · + at xαt .
P
P
Since si=1 fi gi ∈ a, f = h mod a, where h = tj=1 aj xαj . We are given that the
O-border prebasis, G is acyclic. Without loss of generality, let us assume that G is
well ordered. Find the smallest i for which the border term in gi belongs to ∂Os and
assume that the monomial in the border term is xα1 . Let G1 ⊆ G represent all the
polynomials for which the border monomial is xα1 and let |G1 | = s1 .
Let the ideal Ixα1 be generated by {c1 , . . . , cs1 } and let b1 ∈ CIxα1 be the coset
representative of a1 + Ixα1 . Then there exist d1 , . . . , ds1 ∈ A such that
(a1 − b1 ) = d1 c1 + · · · + ds1 cs1 .
Let h1 = h − d1 g1 + · · · + ds1 gs1 . Therefore we have,
h1 = b1 xα1 + b02 xα2 + · · · + b0t xαt ,
where b0i ∈ A, i ∈ {2, . . . , t}. Further, h1 = h mod a. Repeating the above process
for the remaining monomials in ∂Os in the same sequence as the well ordered basis,
we get
hs0 = b1 xα1 + . . . + bs0 xαs0 + bs0 +1 xαs+1 + · · · + bt xαt ,
where each bi is a coset representative in CIxαi . Note that for xαi , s0 + 1 ≤ i ≤ t,
Ixαi = {0} and bi ∈ A. The acyclicity of the basis ensures that at each stage, i, all
bj , j i will not be modified. Further, at every stage i, the intermediate polynomial,
hi = hi−1 mod a. Therefore, hs0 = h mod a which implies that f = hs0 mod a.
Further, each bi is a coset representative in CIxαi where xαi ∈ Mon(O). Hence,
P
A[x1 , . . . , xn ]/a = { ti=1 ai xαi + a | ai ∈ CIxαi }.
To prove the secondPcondition of the order span definition (Definition 5.1), consider
a polynomial f = ti=1 ai xαi ∈ a. Then, there exists an i ∈ {1, . . . , t} such that
ai xαi ∈ BFO (f ). By hypothesis we have, BFO (a) = hc1 xβ1 , . . . , cs xβs i. Since BFO (a)
is an ideal generated by terms, we have ai xαi ∈ BFO (a). Thus, there exists terms
di xγi , 1 ≤ i ≤ s such that
s
X
ai x α i =
(di xγi )(ci xβi ).
i=1
β

Since for all x |x

αi

Ixβ ⊆ Ixαi , we have ai ∈ Ixαi .
0

Consider a proper order function, I such that for any xα ∈ Mon(A[x1 , . . . , xn ]),
0
0
0
0
either Ixα ( Ixα or Ixα = Ixα . Let O be the order ideal associated with I and
0
0
0
0
∂O = {c1 xβ1 , . . . , cl xβl } be the corresponding border. Assume that Mon(O ) satisfies
0
0
(i) and (ii). Consider the ideal, A = hc1 xβ1 , . . . , cl xβl i. We have, A ( BFO (a)
0
since Ixα ( Ixα for some xα . Consider cω xω ∈ BFO (a) \ A. Let h denote the
remO,G (cω xω ). Then each non zero term in h is of the form dγ xγ such that dγ ∈ A/Ixγ

20

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS
0

0

and xγ ∈ Mon(O). Since dγ ∈
/ Ixγ , it is not an element of Ixγ . Also, cω ∈
/ Ixω .
0
Therefore, Mon(O ) fails to satisfy Condition (ii) of the definition of order span for
cω xω −h and therefore we have a contradiction. Thus G = {g1 , . . . , gs } is an O-border
basis for a.

6. A Full Example
In this section, we illustrate the concepts given in this paper with an example.
Example 6.1. Let us consider the polynomial ring, Z[x, y]. Let I be an order function such that I1 = {0}, Ix = {0}, Iy = {0}, Ixy = {0}, Iy2 = {0}, Ix2 = h2i,
Ix2 y = h2i and the rest of the monomials map to h1i. Therefore, CI1 = CIx = CIy
= CIxy = CIy2 = Z and CIx2 = CIx2 y = {0, 1}. The set,
O ={a1 , a2 x, a3 y, a4 xy, a5 y 2 , a6 x2 , a7 x2 y |
a1 , a2 , a3 , a4 , a5 ∈ Z, a6 , a7 ∈ {0, 1}}
is an order ideal corresponding to I. The monomial part of O is the set Mon(O) =
{1, x, y, x2 , y 2 , xy, x2 y}. The scalar border of the order ideal is ∂Os = {2x2 , 2x2 y}
and the monomial border is ∂Om = {x3 , y 3 , xy 2 , x2 y 2 , x3 y}. Thus the border of O is
the union of the scalar border and the monomial border, i.e.,
∂O = ∂Om ∪ ∂Os = {x3 , y 3 , xy 2 , x2 y 2 , x3 y, 2x2 , 2x2 y}.
Consider the set G = {g1 , g2 , g3 , g4 , g5 , g6 , g7 }, where g1 = x3 − x, g2 = y 3 − y, g3 =
xy 2 −xy, g4 = x2 y 2 −x2 y, g5 = x3 y−xy, g6 = 2x2 y−y 2 −y and g7 = 2x2 +2xy−y 2 −
2x − y. The set G is an O-border prebasis for the ideal a = hg1 , g2 , g3 , g4 , g5 , g6 , g7 i.
It is also clear that the O-border prebasis satisfies the properties of acyclicity. Hence
G is an acyclic O-border prebasis.
The set G is a Gröbner basis for a with deglex order with x > y. The proof of
Theorem 5.9 implies that the set G is an acyclic O-border basis for a. Hence the
border form ideal of a is generated by the border terms i.e.,
BFO (a) = hx3 , y 3 , xy 2 , x2 y 2 , x3 y, 2x2 , 2x2 yi.
Now we demonstrate the border division algorithm (Algorithm 4.2) for a polynomial,
f = x4 + 2x3 y 2 + x2 + 4xy + 15 w.r.t. G. We have Mon(O) = {xα1 , . . . , xα7 },
where xα1 = 1, xα2 = x, xα3 = y, xα4 = x2 , xα5 = y 2 , xα6 = xy and xα7 = x2 y.
The monomial border is ∂Om = {b1 , . . . , b5 } and the scalar border is ∂Os = {b6 , b7 },
where b1 = x3 , b2 = y 3 , b3 = xy 2 , b4 = x2 y 2 , b5 = x3 y, b6 = 2x2 y and b7 = 2xy.
(1) Initialize f1 = f2 = f3 = f4 = f5 = f6 = f7 = 0, l1 = l2 = l3 = l4 = l5 = l6 =
l7 = 0 and h = x4 + 2x3 y 2 + x2 + 4xy + 15.
(2) Since indO (h) = 2, Step 5 of the algorithm is executed. We have x4 = xb1
and deg(x) = indO (h) − 1. Hence, we have f1 = f1 + x and h = x4 + 2x3 y 2 +
x2 + 4xy + 15 − x(x3 − x). Thus, h = 2x3 y 2 + 2x2 + 4xy + 15. Return to Step
2.

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

21

(3) Again, indO (h) = 2 and we return to Step 5 of the algorithm. We have x3 y 2 =
xb4 and deg(x) = indO (h) − 1. After the reduction step we have f4 = f4 + 2x
and h = 2x3 y 2 + 2x2 + 4xy + 15 − 2x(x2 y 2 − x2 y) = 2x3 y + 2x2 + 4xy + 15.
We return to Step 2.
(4) In this step, indO (h) = 1 and the polynomial h has the monomial x3 y in its
support. Since x3 y ∈ ∂Om , we go to Step 5. We have x3 y = 1 · b5 and
deg(1) = indO (h) − 1. We perform the operation f5 = f5 + 2 and h =
2x3 y + 2x2 + 4xy + 15 − 2(x3 y − xy). Hence, h = 2x2 + 6xy + 15. We return
to Step 2.
(5) We have indO (h) = 1 and none of the terms in h are in the monomial border,
∂Om . Hence, we perform Step 4 of the algorithm. We have 2x2 = 1·b1 . Thus,
we have f7 = f7 + 1 and h = 2x2 + 6xy + 15 − 1(2x2 + 2xy − y 2 − 2x − y).
Hence, h = 4xy + y 2 + 2x + y + 15.
(6) We have indO (h) = 0 and Step 3 of the algorithm is executed. We have
l1 = l1 + 15, l2 = l2 + 2, l3 = l3 + 1, l4 = l4 + 0, l5 = l5 + 1, l6 = l6 + 4 and
l7 = l7 + 0. The algorithm terminates and returns (f1 , . . . , f7 , l1 , . . . , l7 ).
Thus we have the following representation for f ,
f =xg1 + 0g2 + 0g3 + 1g4 + 2g5 + 0g6 + 1g7 +
15 + 2x + y + 0x2 + 1y 2 + 4xy + 0x2 y.
The O-remainder of f is remO,G (f ) = 15 + 2x + y + y 2 + 4xy. Since the remainder
is not equal to zero, by Proposition 5.10, f ∈
/ a. For this example, the normal form
of f is equal to the O-remainder,
NFO,G (f ) = remO,G (f ) = 15 + 2x + y + y 2 + 4xy.
7. Concluding Remarks
The theory of border bases is popular in the symbolic computation community owing
to its numerical stability and mathematical elegance. In (Francis & Dukkipati, 2014)
it has been shown that border bases can be extended to polynomial rings over rings if
the corresponding residue class ring is free and if one can find its free representation
with respect to a monomial order by using Gröbner bases. In this paper we attempted
to extend the theory to a much more general case.
A theory was built for a special class of generators of the ideal called acyclic border
bases. We proved that the set of acyclic border bases contains all the reduced Gröbner
bases associated with all term orders. A future direction in this work is to determine
an algorithmic characterization for border bases in this case.
References
Adams, W. W. & Loustaunau, P. (1994). An Introduction to Gröbner Bases, vol. 3 of Graduate
Studies in Mathematics. American Mathematical Society.
Ajtai, M. (1996). Generating hard instances of lattice problems (Extended Abstract). In: Proceedings of the 1996 ACM Symposium on the Theory of Computing, STOC (Miller, G. L., ed.).
ACM.

22

AMBEDKAR DUKKIPATI, NITHISH PAI AND MARIA FRANCIS

Ananth, P. V. & Dukkipati, A. (2012). Complexity of Gröbner basis detection and border basis
detection. Theoretical Computer Science 459, 1–15.
Buchberger, B. (1965). An Algorithm for Finding a Basis for the Residue Class Ring of a ZeroDimensional Polynomial Ideal (in German). Ph.D. thesis, University of Innsbruck, Austria.
(reprinted in ?).
Francis, M. & Dukkipati, A. (2014). On reduced Gröbner bases and Macaulay-Buchberger basis
theorem over noetherian rings. Journal of Symbolic Computation 65, 1–14.
Greuel, G.-M., Seelisch, F. & Wienand, O. (2011). The Gröbner basis of the ideal of vanishing
polynomials. Journal of Symbolic Computation 46(5), 561–570.
Hoffstein, J., Pipher, J. & Silverman, J. (1998). NTRU: A ring-based public key cryptosystem. In: Algorithmic Number Theory (Buhler, J., ed.), vol. 1423 of Lecture Notes in Computer
Science. Springer.
Kehrein, A. & Kreuzer, M. (2005). Characterizations of border bases. Journal of Pure and
Applied Algebra 196(2-3), 251–270.
Kehrein, A. & Kreuzer, M. (2006). Computing border bases. Journal of Pure and Applied
Algebra 205(2), 279–295.
Kehrein, A., Kreuzer, M. & Robbiano, L. (2005). An algebraist’s view on border bases. In:
Solving Polynomial Equations (Dickenstein, A. & Emiris, I. Z., eds.), vol. 14 of Algorithms
and Computation in Mathematics. Springer, pp. 169–202.
Lyubashevsky, V. & Micciancio, D. (2006). Generalized compact knapsacks are collision resistant. In: ICALP (2).
Möller, H. M. (1988). On the construction of Gröbner bases using syzygies. Journal of Symbolic
Computation 6(2-3), 345–359.
Pauer, F. (2007). Gröbner bases with coefficients in rings. Journal of Symbolic Computation
42(11-12), 1003–1011.
Sato, Y., Inoue, S., Suzuki, A., Nabeshima, K. & Sakai, K. (2011). Boolean Gröbner bases.
Journal of Symbolic Computation 46(5), 622–632.
Stetter, H. J. (2004). Numerical Polynomial Algebra. Society for Industrial and Applied Mathematics.
Trinks, W. (1978). Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen.
Journal of Number Theory 10(4), 475–488.
Zacharias, G. (1978). Generalized Gröbner Bases in Commutative Polynomial Rings. Master’s
thesis, MIT,Cambridge,MA.

Example 7.1. We consider Example 3.5. The set G = {g1 , . . . , g7 }, where g1 =
xy − x, g2 = y 2 − y, g3 = x3 − 2y, g4 = x2 y − x2 + 10, g5 = 4x − 2y, g6 = 3y − 3x and
g7 = 2x2 − x + 5 is an O-border prebasis but it is not acyclic. Let G0 = {g10 , . . . , g70 }
where g10 = xy − x, g20 = y 2 − y, g30 = x3 − x2 + 6, g40 = x2 y − y + 5, g50 = 4x − 7,
g60 = 3y − x and g70 = 2x2 − 2y − 3x which is also a O-border prebasis but it is acyclic
since the permutation of G0 , {g10 , g20 , g30 , g40 , g70 , g60 , g50 } satisfies the acyclicity condition.
Example 7.2. Consider Example 3.6. The set G =
{g1 , . . . , g15 }, where g1 = x3 − 3, g2 = x2 y − 3u1 y, g3 = x2 z − 2z, g4 = xy 2 − x + 10,
g5 = xyz − 11xy, g6 = xz 2 − u2 u21 x2 , g7 = y 2 − x + u1 u2 , g8 = yz − 3y + 2,
g9 = z 2 + 5xz + 11u1 x, g10 = u21 y + u2 x + 3, g11 = (u22 − 3u1 )z − u22 y, g12 =
u21 xy + 3u1 x − 2z, g13 = (u22 − 1)xy + 2x2 , g14 = u1 xz + 3u1 x2 , g15 = u2 xz +
2u1 xy + 4x2 − 4z − 10u1 y + 14 is an acyclic O-border prebasis since the following
permutation of G, {g1 , g2 , g3 , g4 , g5 , g6 , g7 , g8 , g9 , g14 , g15 , g13 , g12 , g11 , g10 } satisfies the
acyclicity condition.
E-mail address: ad@csa.iisc.ernet.in, nithish.pai@conduent.com, mariaf@csa.iisc.ernet.in

BORDER BASES FOR POLYNOMIAL RINGS OVER NOETHERIAN RINGS

23

Dept. of Computer Science & Automation, Indian Institute of Science, Bangalore
- 560012

