Grobuer Basis Algorithms for Polynomial Ideal Theory over Noetherian Commutative Rings

One of the fundamental problems in commutative algebra and algebraic geometry is to understand the nature of the solution space of a system of multivariate polynomial equations over a field k, such as real or complex numbers. An important algorithmic tool in this study is the notion of Groebner bases (Buchberger (1965)). Given a system of polynomial equations, f1= 0,..., fm = 0, Groebner basis is a “canonical generating set of the ideal generated by f1,...., fm, that can answer, constructively, many questions in computational ideal theory. It generalizes several concepts of univariate polynomials like resultants to the multivariate case, and answers decisively the ideal membership problem. The dimension of the solution set of an ideal I called the affine variety, an important concept in algebraic geometry, is equal to the Krull dimension of the corresponding coordinate ring, k[x1,...,xn]/I. Groebner bases were first introduced to compute k-vector space bases of k[x1,....,xn]/I and use that to characterize zero-dimensional solution sets. Since then, Groebner basis techniques have provided a generic algorithmic framework for computations in control theory, cryptography, formal verification, robotics, etc, that involve multivariate polynomials over fields. The main aim of this thesis is to study problems related to computational ideal theory over Noetherian commutative rings (e.g: the ring of integers, Z, the polynomial ring over a field, k[y1,…., ym], etc) using the theory of Groebner bases. These problems surface in many domains including lattice based cryptography, control systems, system-on-chip design, etc. Although, formal and standard techniques are available for polynomial rings over fields, the presence of zero divisors and non units make developing similar techniques for polynomial rings over rings challenging. Given a polynomial ring over a Noetherian commutative ring, A and an ideal I in A[x1,..., xn], the first fundamental problem that we study is whether the residue class polynomial ring, A[x1,..., xn]/I is a free A-module or not. Note that when A=k, the answer is always ‘yes’ and the k-vector space basis of k[x1,..., xn]/I plays an important role in computational ideal theory over fields. In our work, we give a Groebner basis characterization for A[x1,...,xn]/I to have a free A-module representation w.r.t. a monomial ordering. For such A-algebras, we give an algorithm to compute its A-module basis. This extends the Macaulay-Buchberger basis theorem to polynomial rings over Noetherian commutative rings. These results help us develop a theory of border bases in A[x1,...,xn] when the residue class polynomial ring is finitely generated. The theory of border bases is handled as two separate cases: (i) A[x1,...,xn]/I is free and (ii) A[x1,...,xn]/I has torsion submodules. For the special case of A = Z, we show how short reduced Groebner bases and the characterization for a free A-module representation help identify the cases when Z[x1,...,xn]/I is isomorphic to ZN for some positive integer N. Ideals…