Computing grobner bases with hilbert lucky primes
Elizabeth A. Arnold, William W. Adams · 2000
Grobner bases have many applications in mathematics, computer science and engineering. The fact that they can be computed is at the heart of their usefulness. During the execution of Buchberger's algorithm for computing Grobner bases, many intermediate polynomials are computed and then discarded before the final Grobner basis is obtained. The coefficients of these polynomials can grow to enormous size, even if the coefficients of the generating polynomials and the polynomials in the Grobner basis are relatively small. This intermediate coefficient growth can sometimes cause the computer to crash before the computation is complete. Intermediate coefficient growth is also seen in greatest common divisor calculations for polynomials in one variable. p-adic algorithms are already successfully in place for GCD computations that limit this growth. In this thesis we propose an implementable algorithm that extends the p-adic GCD algorithm for polynomials in one variable to a p-adic algorithm for computing Grobner bases for polynomials in several variables. This is accomplished by defining a class of primes, based on the Hilbert function of the ideal, called “Hilbert lucky” primes. By using Hilbert lucky primes, we are able to find a “lucky” prime for the p-adic algorithm with high probability. Hilbert lucky primes also allow us to “lift” a Grobner basis with very little computation, and check the result of the algorithm for correctness. In fact, it is the concept of Hilbert lucky that allows the algorithm to be implemented.