Title:
Computing Groebner bases with Hilbert Lucky Primes
Abstract: Groebner 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 Groebner bases, enormous growth of coefficients of intermediate polynomials can sometimes cause the computer to crash before the computation is complete. Computing the Groebner basis modulo a prime p eliminates this growth. Then for all but a finite number of ``unlucky'' primes, it is possible to recover the correct Groebner basis with rational coefficients using a Hensel lifting technique. In this talk I will give a brief introduction to Groebner bases and Buchberger's algorithm. Then I will discuss a p-adic algorithm for computing Groebner bases that finds a lucky prime with high probability. The Hilbert function of the ideal plays a role in determining whether or not a prime is lucky and also allows us to check the result of the algorithm for correctness. |