Groebner Bases and elimination theory

• This page gathers important information regarding elimination theory (elimination of variables that is) and Groebner Bases (GB).
• It is written in a "lab research notebook" style.
• Main reference: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. Cox et al.

General definitions

• Given the algebraic variety V=Z(f1,...,fs)={f1=0,...,fs=0} we say that this is an Implicit Representation
• A Rational Parametric Representation of an algebraic variety V=Z(f1,...,fs) in Kn consists of rational functions r1,...rn such that V is the smallest variety containing {(x1,...,xn) in Kn such that x1=r1(t1,...,tm),...,xn=r(t1,...,tm)}
• A Polinomial Parametric Representation is a Rational Parametric Representation given by polynomials and not quotients of polynomials.
• The definition of an ideal is similar to the definition of a (vector) subspace: both have to be closed under addition and multiplication, except that, for a subspace, we multiply by scalars, whereas for an ideal, we multiply by polynomials. Further, notice that the ideal generated by polynomials f1,...,fs is similar to the span of a finite number of vectors v1,...,vs . In each case, one takes linear combinations, using field coefficients for the span and polynomial coefficients for the ideal generated.
• Lex ordering: let α = (α1, . . . , αn) and β = (β1, . . . , βn) ∈ Zn. We say α >lex β if, in the vector difference α − β ∈ Zn, the leftmost nonzero entry is positive. Used in dictionaries!
• Graded Lex Order: grlex orders by total degree first, then "breaks ties" using lex order.
• Fix a monomial order. A finite subset G = {g1, . . . , gt} of an ideal I is said to be a Groebner basis (or standard basis) if (LT(g1),...,LT(gt)) = (LT(I)). (i.e. their leading terms generate the ideal of leading terms) (p. 77)
• Equivalently, a set {g1,...,gt} ⊂ I is a Groebner basis of I if and only if the leading term of any element of I is divisible by one of the LT(gi) (p. 77)

Results

• Given a parametric representation for an algebraic variety, we can always find the defining equations.
• The method of Groebner bases is sort of combination of (matrix) row-reduction and division of polynomials.
• The division algorithm for polynomials of several variables achieves its full potential only when coupled with the GB (p. 66 main reference).
• Given polys f and f1,...,fn (in several variables). The fact that the remainder of the division of f by f1,...,fn is zero is sufficient BUT NOT necessary condition for f to be a member of the ideal generated by f1,...,fn. Its is sufficient and necessary exactly when we have a GB of the ideal.
• Hilbert Basis Theorem: Every ideal I ⊂ k[x1, . . . , xn] has a finite generating set. That is, I = (g1, . . . , gt) for some g1, . . . , gt ∈ I.
• Fix a monomial order. Then every ideal I ⊂ k[x1,...,xn] other than {0} has a Groebner basis.
• The remainder (in a division of polynomial f by polynomials f1,...,fn with several variables) is uniquely determined when we divide by a Groebner basis.
• Let G = {gt,...,gt} be a Groebner basis for an ideal I ⊂ k[x1,...,xn] and let f ∈ k[x1,...,xn]. Then f ∈ I if and only if the remainder on division of f by G is zero.
• Buchberger’s Algorithm: Let I = (f1,...,fs) be a polynomial ideal. Then a Groebner basis for I can be constructed in a finite number of steps. (p. 90)
• Ideal membership algorithm: given an ideal I = (f1,...,fs), we can decide whether a given polynomial f lies in I by looking at the remainder of the division of f by a GB of I.

GB, elimination and locus equations

• Given a GeoGebra locus set defined by the polynomials {f1(x1,...,xn,u1,u2), ..., fr(x1,...,xn,u1,u2)} we compute a Groebner basis for the ideal generated by f1,...,fr relative to any ordering which places polynomials involving x's greater than those which don't: for example, lexicographic ordering with x1 > x2 > ... > xn > u1 > u2. Taking only the elements of the basis which only involve u1 and u2 we get a set of equations describing the locus (or perhaps a superset of the locus). Hopefully if the locus set is one-dimensional, we will only obtain one equation.

Other

• Nice summary of GB properties ​http://en.academic.ru/dic.nsf/enwiki/208485 link