Quantitative analysis of problems in computer algebra: Grobner bases and the Nullstellensatz

Candidate: Dube,Thomas William

Abstract

This thesis presents new quantitative results concerning multi-variate polynomial ideals. Since these ideals are the basic objects of (computational) algebraic geometry, these results have important ramifications in algebraic algorithms, particularly in the solving of simultaneous equations. Furthermore, all the new theorems are proven using only constructive techniques and basic algebra. In many cases, the proofs provide algorithms for constructing the objects which the theorems describe. Among the results assembled here, three are of particular importance. The first shows that every ideal and residue class ring can be decomposed into simple pieces called cones. Next, the cone decomposition is used to produce a new upper bound on the degree of polynomials which appear in a reduced Grobner basis. Finally, a new tight upper bound for the exponent in Hilbert's Nullstellensatz is demonstrated.