HINTS

Gröbner Basis can be used for

1. Finding the solution to simultaneous polynomial equations: The Gröbner Basis for I = <p₁,p₂,...p_m> can be used to solve exactly the simultaneous equations p₁ = p₂ = ... = p_m = 0. This is carried out by successive elimination of variables x₁, then x₂ etc. until the final polynomial is a univariate polynomial in x_r. This final polynomial equation can be solved by other symbolic/numerical techniques (e.g. Newton Raphson), and solutions for x_r substituted back to get successively x_r-1, x_r-2,...x₂,x₁
2. Determination of existence of solutions to simultaneous polynomial equations: There is no solution to this system if and only if the The Gröbner Basis contains 1 (unit polynomial). Example: to prove the obvious result that p₁ = x - 1 = 0 and p₂ = x - 3 = 0 have no simultaneous solution, enter 1,1,1,1;-1,1|1,1,1,1;-3,1 and observe that 1 appears in the Gröbner Basis. As a second example we prove the polynomials

   p1= x8 + x6 -3x4 -3x3 +8x2 +2x -5 p2= 3x6 +5x4 -4x2 -9x + 21

   are co-prime by showing the Gröbner Basis contains 1, and hence p₁ = p₂ = 0 has no solution (enter 1,1,1,8;1,1,1,6;-3,1,1,4;-3,1,1,3;8,1,1,2;2,1,1,1;-5,1|3,1,1,6;5,1,1,4;-4,1,1,2;-9,1,1,1;21,1 for this example).
3. Solution of simultaneous linear equations: Since linear equations are a special case of polynomial equations, Buchberger Algorithm also solves this problem, effectively generalizing Gaussian Elimination. Example: to solve

   3x - 2y + (11/2)z = 0 x + 4y + 3z + (4/3) = 0 -2x + y + (7/6)z - 3 = 0

   enter 3,1,1,1;-2,1,2,1;11,2,3,1|1,1,1,1;4,1,2,1;3,1,3,1;4,3|-2,1,1,1;1,1,2,1;7,6,3,1;-3,1 and the Gröbner Basis will give the solution for the last variable (in this case z=244/413) from which we can find first y, then x.
4. Finding the GCD of m Univariate Polynomials: This is the unique polynomial which divides without remainder into each of the polynomials p₁,p₂,...p_m. In the univariate case, setting the GCD equal to zero and solving (by other means) this equation is equivalent to solving the simultaneous univariate equations p₁ = p₂ = ... = p_m = 0. Example: to solve

   x8 - 5x7 + x6 - 5x5 = 0 x3 - 5x2 - 3x + 15 = 0 x2 - 4x - 5 = 0

   enter 1,1,1,8;-5,1,1,7;1,1,1,6;-5,1,1,5|1,1,1,3;-5,1,1,2;-3,1,1,1;15,1|1,1,1,2;-4,1,1,1;-5,1 and the Gröbner Basis will calculate x - 5 as the GCD of these three polynomials, also proving x = 5 is the only solution of the three equations.
5. Calculating max/min points of a function using Lagrange Multipliers:
   • single constraint We wish to find the critical points of a function f(x₁, x₂, x₃,...x_r) subject to a constraint g(x₁, x₂, x₃,...x_r) = 0. The Lagrange Multiplier solution to this is to write DEL(f) = a DEL(g) where a is a parameter, and DEL(f) is the r-vector (df/dx₁, df/dx₂, df/dx₃,...df/dx_r). We then have r+1 equations in r+1 unknowns:
     df/dx₁ = a dg/dx₁        df/dx₂ = a dg/dx₂        df/dx₃ = a dg/dx₃        ...  df/dx_r = a dg/dx_r        g=0
     We are not interested in the variable a so we put it lexicographically first, so it will be eliminated first. Example: find the maxima and minima of the polynomial f(x,y)=x²y - 2xy + y + 1 subject to the constraint x² + y² = 1. The equations above are

     ax - xy + y = 0 2ay - x2 + 2x -1 = 0 x2 + y2 - 1 = 0

     so enter 1,1,1,1,2,1;-1,1,2,1,3,1;1,1,3,1|2,1,1,1,3,1;-1,1,2,2;2,1,2,1;-1,1|1,1,2,2;1,1,3,2;-1,1 and the Gröbner Basis shows y satisfies y⁶ - (5/9)y⁴ = 0.
   • multiple constraints Let f(x₁,x₂, x₃,...x_r) be subject to m constraints g₁(x₁, x₂, x₃,...x_r) = 0, g₂(x₁, x₂, x₃,...x_r) = 0, g₃(x₁, x₂, x₃,...x_r) = 0, ....., g_m(x₁, x₂, x₃,...x_r) = 0. The Lagrange Multiplier solution is to write DEL(f) = a₁DEL(g₁) + a₂DEL(g₂) + a₃DEL(g₃) + .....+ a_mDEL(g_m). Along with the constraint equations, this gives (r+m) equations in (r+m) unknowns:
     df/dx₁ = a₁dg₁/dx₁ + a₂dg₂/dx₁ + a₃dg₃/dx₁ + ....+a_mdg_m/dx₁
     df/dx₂ = a₁dg₁/dx₂ + a₂dg₂/dx₂ + a₃dg₃/dx₂ + ....+a_mdg_m/dx₂
     df/dx₃ = a₁dg₁/dx₃ + a₂dg₂/dx₃ + a₃dg₃/dx₃ + ....+a_mdg_m/dx₃
     .
     .
     df/dx_r = a₁dg₁/dx_r + a₂dg₂/dx_r + a₃dg₃/dx_r + ....+a_mdg_m/dx_r
     g₁= 0,  g₂= 0,  g₃= 0,  ....., g_m= 0, 
     where the m Lagrange Multipliers a₁, a₂, a₃, ...., a_m should be put lexicographically first. (Trivial) example: find extrema of f(x,y,z) = z² - xyz + x subject to the two constraints g₁(x,y,z) = x - 1 = 0, g₂(x,y,z) = y - 2 = 0. Here r = 3 and m = 2, so with the ordering a₁, a₂, x, y, z we have the 5 equations

     a1 + yz - 1 = 0 a2 + xz = 0 xy - 2z = 0 x - 1 = 0 y - 2 = 0

     Enter 1,1,1,1;1,1,4,1,5,1;-1,1|1,1,2,1;1,1,3,1,5,1|1,1,3,1,4,1;-2,1,5,1|1,1,3,1;-1,1|1,1,4,1;-2,1 to find an extremum at (x,y,z) = (1,2,1).