<< Chapter < Page Chapter >> Page >

Starting with a Gröbner basis, we can get a reduced Gröbner basis by multiplying by constants to clear any leading coefficients, throwing away any elements whose leading term is a proper multiple of another leading term, and then replacing each polynomial by the remainder upon dividing it by the rest (to clear out any terms divisible by any of the other leading terms). Moreover, reduced is all we need to impose to make our Gröbner bases unique:

Theorem Fix a term order on R [ x 1 , ... , x n ] . Then every ideal I R [ x 1 , ... , x n ] has a unique reduced Gröbner basis.

To prove uniqueness, suppose that G and G ˜ are two different reduced Gröbner bases for I . The set of leading terms of both G and G ˜ must simply by the minimal set of monomial generators of L T ( I ) , so if G G ' , it is because there is some f G and f ˜ G ˜ with L T ( f ) = L T ( f ˜ ) but f f ˜ . Then f - f ˜ I , so the remainder of f - f ˜ upon division by G is zero, since G is a Gröbner basis. However, since G and G ˜ are both reduced Gröbner bases, no non-leading term of f or f ˜ is divisible by any leading term in G . Since the leading terms of f and f ˜ cancel in f - f ˜ , no term of f - f ˜ is divisible by a leading term of G , so we see that no actual division occurs, and the remainder is f - f ˜ , so f - f ˜ = 0 , a contradiction.

Exercises

  1. Let I R [ x 1 , ... , x n ] be an ideal.
    1. The l th elimination ideal is defined to be the set
      I l = I R [ x l + 1 , ... , x n ] .
      Prove that I l is indeed an ideal of R [ x l + 1 , ... , x n ] . Recall that an ideal I of R = R [ x l + 1 , ... , x n ] is a subset of R such that:
      • 0 I ,
      • if f , g I then f + g I , and
      • if f I and g R , then g f I .
    2. Is I l an ideal of R [ x 1 , ... , x n ] ?
    3. Prove that the ideal I l + 1 R [ x l + 2 , ... x n ] is the first elimination ideal of I l R [ x l + 1 , ... , x n ] , i.e. that ( I l ) 1 = I l + 1 .
  2. Consider the system of equations
    x 2 + 2 y 2 = 3 x 2 + x y + y 2 = 3 .
    1. Let I = x 2 + 2 y 2 - 3 , x 2 + x y + y 2 - 3 . Find Gröbner bases for I Q [ x ] and I Q [ y ] .
    2. Find all solutions of the system over the complex numbers C .
    3. Which of the solutions are rational; that is, which solutions like in Q 2 ?
  3. Find all rational solutions ( x , y ) Q 2 and all complex solutions ( x , y ) C 2 of the system
    x 2 + 2 y 2 = 2 x 2 + x y + y 2 = 2 .
  4. Consider the system of equations
    t 2 + x 2 + y 2 + z 2 = 0 t 2 + 2 x 2 - x y - z 2 = 0 t + y 3 - z 3 = 0 .
    Suppose we want to eliminate t . Let
    I = t 2 + x 2 + y 2 + z 2 , t 2 + 2 x 2 - x y - z 2 , t + y 3 - z 3 R [ t , x , y , z ]
    be the corresponding ideal.
    1. Use lex order with t > x > y > z to compute a Gröbner basis for I , and then find a bass for I R [ x , y , z ] . You should get four generators, one of which has total degree 12.
    2. Compute a reduced Gröbner basis for the ideal I R [ x , y , z ] in grevlex order. This time, you should get a set of two generators.

Resultants

We've recently seen how Gröbner bases in lex order allow us to “eliminate” variables; for example, given two plane curves f ( x , y ) and g ( x , y ) , we expect their intersection to consist of finitely many points (unless they have a common factor), and to find those points, we find a polynomial in y alone (i.e. eliminate x ) in the ideal f , g whose roots are then the y -coordinates of the intersection points of f and g .

It turns out that, at least in this special case, there was an earlier (19th century) approach to the problem without using Gröbner bases, called resultants. Given two polynomials

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, The art of the pfug. OpenStax CNX. Jun 05, 2013 Download for free at http://cnx.org/content/col10523/1.34
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'The art of the pfug' conversation and receive update notifications?

Ask