$SPAD/src/input groebner.input

Timothy Daly December 3, 2016

Abstract

Contents

2

Bernd Sturmfels
\verb|math.berkeley.edu/~bernd|
-- Gaussian Elimination
eq1:= 2*x + 3*y + 4*z - 5
eq2:= 3*x + 4*y + 5*z - 2
-- x-z+14
-- y+z-11
-- Euclidean Algorithm
eq3:= x^4 - 12*x^3 + 49*x^2 -78*x + 4
eq4:= x^5 - 5*x^4 + 5*x^3 + 5*x^2 - 6*x
gcd(eq3,eq4) -- x^2 - 3*x + 2
-- Simplex Algorithm
-- Minimize the linear function
--  P+N+D+Q (pennies, nickels, dimes, quarters)
-- (minimize number of coins used)
-- subject to
--  P>0, N>0, D>0, Q>0 and
--  P + 5N + 10D +25Q = 117
-- solution is
-- (P,N,D,Q) = (0,0,0,4.68) (117/25 == 4.68)
-- Require that the unknowns be non-negative integers
-- (P,N,D,Q) = (2,1,1,4)
-- Represent a collection C of coins by a polynomial
-- p^a * n^b * d^c * q^d in the variables p,n,d,q
-- e.g.2 pennies and 4 dimes is represented as p^2d^4
-- input set F = {p^5-n, p^10-d, p^25-q}
-- (e.g. 5 pennies = 1 nickel,
--      10 pennies = 1 dime,
--      25 pennies = 1 quarter
-- output set G = {p^5-n, n^2-d, d^2*n-q d^3-n*q}
-- expresses a more useful set of replacement rules
-- e.g. the expression d^3 - n*q translates to
-- replace 3 dimes with a nickel and a quarter
-- (e.g.  5 pennies can be replaced by a nickel)
-- (objective function: we are trying to minimize the number of coins )
-- Given a collection C of coins, we use rules encoded by G to transform
-- (in any order) C into a set of coins C with equal monetary value but
-- smaller number of elements
-- Example: (solving the prior problem):
-- p^17*n^10*d^5 -> (use p^5-n rule changing 32 coins to 28 coins)
--  p^12*n^11*d^5 -> ... p^2*n^13*d^5 ->
-- p^2*n^12*d^3*q -> p^2*n^13*d*q^2 .... -> p^2*n*d*q^4

-- Integer Programming and Groebner Bases
-- So Groebner Bases give a method of transforming an integer programming
-- feasible solution using local moves into a global optimum
-- So using the groebner basis is analogous to running the
-- Simplex Algorithm
-- To set up Groebner Basis:
-- Let K be a field, e.g. the rational numbers Q, the real numbers R,
-- or the complex numbers C
-- Form the set of polynomials K[x_1,..x_n] in variables x_1,...,x_n
-- with coefficients in K
-- this set K[x_1,...,x_n] is a ring (also called a polynomial ring)
-- it is also a K-vector space
-- for short, we may also write K[x] = K[x_1,...,x_n]
-- Given F, a finite set of polynomials in K[x_1,...,x_n]
-- The ideal generated by F (an ideal for a polynomial acts like a
-- prime number for integers) is:
-- <F>={p_1*f_1+\cdots+p_r*f_r | f_i \in F, p_i \in K[x]}
-- These are all the linear polynomial combinations of elements in F
-- Every ideal in the polynomial ring over the field K where
-- K[x_1,...,x_n] is finitely generated.
-- This means that any ideal I has the form <F> for a finite set of
-- polynomials F so we can write down the ideal.
-- Note: for the 1-variable ring K[x_1], every ideal is principal;
-- that means that I is generated by 1 polynomial. This is the
-- Euclidean Algorithm
-- For each example we have seen <F> = <G> In each example, the
-- polynomial consequences for each set generate the same ideal (that
-- is, the ideal generated by them are the same), but the modified
-- generators divulge more structure
-- IDEAL EQUALITY
-- How can you check that two ideals, the ideal generated by <F>
-- and the ideal generated by <G> are equal?
-- We need to show that each element of F is in <G> and each element
-- of G is in <F>.
-- So for the coins we need to show that d^3-n*q (in G) can be written in
-- terms of elements in F:
-- d^3-n*q = n*(p^25-q) - (p^20+p^10*d+d^2)*(p^10-d) + p^25*(p^5-n)
-- where p^25-q, p^10-d, and p^5-n are in <F> and d^3-n*q is in <G>
-- FIRST, to write a polynomial we choose an order of the monomials
-- this is called a "term order"
-- A term order (or monomial order) is a total order "<" on the set of
-- monomials x^a = (x_1^a_1)*(x_2^a_2)*...*(x_n^a_n) such that
-- (1) it is multiplicative: x^a < x^b => x^(a+c) < x^(b+c)
--     that is, multiplying by x^c does not change the order

-- (2) the constant monomial is smallest, that is,
--     1 < x^a for all a in N^n\{0}
-- there are many term orders
-- in one variable, there is only one order 1 < x < x^2 < x^3 < ....
-- for n=2, we have
-- Degree Lexicographic order (by total degree)
-- 1 < x_1 < x_2 < x_1^2 < x_1*x_2 < x_2^2 < x_1^3 < x_1^2*x_2 < ...
-- Purely Lexicographic order (ignore total degree)
-- 1 < x_1 < x_1^2 < x_x^3 < ... < x_2 < x_1*x_2 < x_1^2*x_x < ...
-- SECOND, we look at the initial monomials
-- Every polynomial f \in K[x_1,...x_n] has an initial monomial
-- (depending on the order) denoted by "in<"(f)
-- Example: if n=2 and our term order is degree-lex, then
-- "in<"(x_1 + 2*x_1^3*x_2^2 + 5*x_2^4 + 3*x_1^2*x_2^3) = 3*x_1^2*x_2^3
-- thus 3*x_1^2*x_2^3 is the "initial monomial"
-- "INITIAL IDEAL"
-- We can apply the same idea to compute the "Intial Ideal"
-- For every ideal I of K[x_1,...,x_n], we can form the initial ideal
-- of I (with respect to "in<") generated by all initial monomials of
-- polynomials in I
-- "in<"(I) = < "in<"(f) | f in in I >
-- THIRD welook at infinitely many polynomials in the ideal
-- and look at its initial monomial of each polynomial.
-- This set of monomials form the "Initial Ideal"
-- DEFINING GROEBNER BASES
-- A finite subset G of an ideal I is a Groebner basis of this ideal
-- (with respect to the term order "in<") if there is a finite set
--      { "in<"(g) | g is in G} }
-- generates "in<"(I), the initial ideal. This exists because Hilbert
-- proved that EVERY ideal is finitely generated.
-- Note that the word "basis" USUALLY implies a minimum generating set
-- but there is no minimality... we could call it a
-- "groebner generating set"
-- There are many, many groebner generating set. We can throw in
-- additional polynomials and still have a groebner basis. We would
-- like the smallest groebner basis, called a "reduced basis"
-- "REDUCED GROEBNER BASIS"
-- A groebner basis is called "reduced" if it satisfies the additional
-- properties:
-- (1) For each g in G, the coefficients of "in<"(g) equals 1 (monic)
-- (2) The set {"in<"(g) | g is in G} minimally generates "in<"(I)
--     that is, nothing can be removed

-- (3) No trailing term of any g in G lies inside "in<"(I), that is,
--     if there is a polynomial in the basis with a non-leading
--     term that is a multiple of another leading term then this
--     trailing polynomial can be resolved.
-- "AUTO-REDUCTION" -- take any Groebner basis to a reduced
--                     Groebner basis
-- "UNIQUENESS of Reduced Groebner Bases
-- The reduced groebner basis is unique.
-- Theorem: Fixing an ideal I containing K[x_1,...,x_n] and a term
-- order "in<", there is a unique reduced Groebner basis for I
-- Question: can groebner basis be applied to cylindrical decomposition?

-- FINDING GROEBNER BASES
-- Let F be a subset of Q[x_1,...,x_n], that is, polynomials with
-- rational coefficients. There is a unique reduced Groebner basis
-- G for F.
-- Algorithm: F -> G
-- Given by Bruno Buchberger (1965) in his dissertation.
-- His advisor was Wolfgang Groebner
-- Applications to Algebraic Geometry
-- ALGEBRAIC GEOMETRY
-- Algebraic geometry is the study of solution sets of polynomials
-- in several unknowns.
-- If F is a set of polynomials, the variety of F over the complex
-- numbers C equals:
-- V(F) = {(z_1,...,z_n) \in C^n | f(z_1,...,z_n)=0 for all f \in F}
-- this is called a "variety", the set of common zeros. We choose the
-- vectors (z_1,...,z_n) which are zeros of the polynomials.
--
-- Note: The variety depends only on the ideal of F. That is, V(F)=V(<F>).
-- This is true because if a polynomial is a linear combination of other
-- polynomials then it vanishes whenever the linear combination vanishes.
-- So if G is a Groebner basis for F, the V(G)=V(F).
--
-- We work in the complex numbers so that the fundamental theorem of
-- algebra, that every nth degree polynomial has n roots, which is not
-- true in general over the reals.
--
-- Hilbert's Nullstellensatz (Theorem of zeros)
-- Theorem (David Hilbert, 1890):
-- V(F) is empty if and only if G={1},

-- that is, the set of equations have no common zeros.
-- so if the groebner basis is {1} then there are no solutions.
-- Easy direction: if G={1} then V(F)=V(G)={}
-- Example: F={x^2+x*y-10, x^3+x*y^2-25, x^4+x*y^3-70}
-- What about the variety? Are there any points that satisfies all of
-- them? Here, G={1}, so there are no common solutions.
-- Geometrically these three equations represent 3 curves in the plane
-- and since G={1} they have NO point in common.
-- Replacing 25 by 26 we get:
-- F={x^2+x*y-10, x^3+x*y^2-26, x^4+x*y^3-70}
-- and thus G={x-2,y-3} and
-- so the "variety of G" is V(F)=V(G)={(2,3)}
-- STANDARD MONOMIALS
-- What do we do if the Groebner basis is complicated?
-- Suppose I is a subset of Q[x_1,...,x_n] an ideal, "in<" is the term
-- order. A monomial x^a = x_1^a_1*x_2^a_2*...*x_n^a^n is "STANDARD"
-- for our ideal with respect to the given term order if and only if
-- it is not in the initial ideal, that is, x^a \notin "in<"(I)
-- Another way to say this is that the monomial x^a is not a multiple
-- of any of the leading terms of the initial monomials
-- Example: If n=3 and "in<"(I)= < x_1^3, x_2^4, x_3^5 >, the number
-- of "standard monomials" is 60 (= 3*4*5). So the standard monomials
-- are of the form x_1^a*x_2^b*x_3^c where a is at most 2, b is at
-- most 3, and c is at most 4.
-- If "in<"(I) = < x_1^3, x_2^4, x_1*x_3^4 >, then the number of
-- "standard monomials" is infinite. That is, there are infinitely
-- many monomials NOT divisible by any of the three leading terms.
-- For instance, every power of x_3 is standard, 1, x_3, x_3^2, ...
-- are all standard monomials. This is an infinite set.
-- If the Groebner basis is 1 G={1} then every monomial is divisible
-- by 1, and is in the initial ideal.
-- Thus, there are no standard monomials. So the variety is empty
-- if there are no standard monomials.
-- If there ARE standard monomials then the number and structure of
-- these standard monomials gives us important information about
-- the ideal.
-- FUNDAMENTAL THEOREM OF ALGEBRA
-- A univariate polynomial of degree D always has D complex solutions.
-- There is a natural generalization to the set of polynomials in any
-- number of variables
-- Theorem: The number of standard monomials equals #V(I), where the
-- zeros are counted with multiplicity.

--
-- Look at the Ideal I and choose a term order.
-- Calculate a Groebner basis
-- Look at the set of initial monomials
-- and consider the set of standard monomials,
-- those monomials not divisible by elements of the leading terms.
-- The fundamental theorem states:
-- The number of standard monomials is equal to the complex variety
-- defined by the system of equations where zeros have multiplicity,
-- just like the one-dimensional case. In the 1-dimensional case,
-- the ideal will be a single polynomial of degree d and it will be
-- the reduced groebner basis and there are exactly d standard
-- monomials: {1, x, x^2, x^3, ..., x^(d-1)}
-- Example: F={x^2*z-y, x^2+x*y-y*z, x*z^2+x*z-x}
-- Then, using purely lex order x > y > z, we get the reduced groebner
-- basis G={ x^2-y*z-y, x*y+y, x*z^2+x*z-x, y*z^2+y*z-y, y^2-y*z }
-- The leading terms generate the initial ideal. these are:
-- {x^2, x*y, x*z^2, y*z^2, y^2}
-- Every power of z is standard, that is,
-- {1, z, z^2, ...} are standard since these does not occur as a
-- multiple of the leading terms so #V(F) is infinite.
-- So "the cardinality of the complex variety V(F) is infinte"
-- Replacing x^2*z-y with x^2*z-1 in F, we get
-- G={ x-2*y*z+2*y+z, y^2+y*z+y-z-3/2, z^2+z-1 }
-- The leading terms generate the initial ideal. these are:
--  the leading terms are {x, y^2, z^2}
-- so that #V(F)=4 because they are {1, y, z, y*z}
-- so there are 4 complex points.
-- There are 3 algebraic surfaces in algebraic space.
-- Example 1 has infinite intersections, Example 2 intersects in
-- 4 points.
-- "DIMENSION OF A VARIETY"
-- Calculating the dimension of a variety
-- Think of dimension intuitively: points have dimension 0, curves
-- have dimension 1, a surface has dimension 2, ...
-- Again given a system of polynomial equations
-- Calculate the groebner basis with respect to some term order
-- Inspect the set of standard monomials.
-- From that set we can read off the dimension of the variety as:
-- Let S be a subset of {x_1,...,x_n} have maximal cardinality with
-- the property that no monomial in the variables in S appears in
-- "in<"(I) That is, the set S has the property that every monomial

-- that you can form out of the variables in S is standard. Every
-- monomial S is a standard monomial.
-- Theorem: dim V(I)=#S ("The dimension of the variety is equal to the
-- cardinality of the largest subset of the variables with the property
-- that every monomial in those variables is standard.
-- An ideal in a ring plays the same role that a normal subgroup plays
-- in a group. It allows you to form quotient structures. If you have a
-- normal subgroup in a group you can form a quotient group, likewise if
-- you have an ideal in a ring you can form a quotient ring.
-- RESIDUE RING
-- Theorem: The set of standard monomials is a Q-vector-space-basis
-- for the residue ring Q[x_1,...,x_n]/I. That is, modulo the ideal I,
-- every polynomial f can be written uniquely as a Q-linear
-- combination of standard monomials.
-- The polynomial ring, and every quotient thereof by an ideal, is a
-- Q vector space. If I is the zero ideal, if you have the entire
-- polynomial ring, then the set of ALL monomials forms a Q vector
-- space basis.
-- Take a residue ring modulo an ideal then the vector space becomes
-- smaller and you have to take a subset of monomials as a basis and
-- that subset will be the standard monomials with respect to any
-- term order that you and I agree upon.
-- What does it mean to be a basis for a vector space? I means 2
-- things: It means you generate and you are linearly independent.
-- To be a basis means that every vector can be written uniquely
-- as a Q-linear combination of the basis elements.
-- Equivalently, if we work modulo an ideal I, every polynomial f can
-- be written uniquely as a Q-linear combination of standard monomials.
-- Given f, there is an algorithm (the division algorithm or the
-- normal form algorithm) that produces this representation (called
-- the normal form of f) in Q[x_1,...,x_n]
-- Favorite Groebner Basis
-- We are working in a polynomial ring of m x n variables
-- Let G be the set of d x d subdeterminants of an m x n matrix of
-- unknowns. The polynomials will be homogeneous of degree d having
-- n! terms. There are m choose d ways of picking the rows
-- and n choose d ways of picking the columns making the
-- subdeterminants.
-- There is a term order which makes G the reduced Groebner basis
-- for the ideal it generates.
-- Why do we care? What does it mean for an n x m matrix to have all of

-- its d x d subdeterminants vanish? That means that the matrix has rank
-- of at most d-1. So given this example,
-- Example: d = n = 3, m = 4
-- dim V(G) = 12 - 2 = 10
-- "in<"(I) =
--   <x_11*x_22*x_33, x_11*x_22*x_43, x_11*x_32*x_43, x_21*x_32*x_43>
-- S = {x_11,...,x_43}\{x_11,x_21}
-- This ideal is the so-called "determinental variety" consisting of
-- all m x n matrices of of rank at most d-1. Lets look at the
-- dimension of the variety.
-- If we take a 4x3 matrix then m is 4 and d is 3. So we are
-- considering the 4 3x3 determinants we can form out of such a matrix
-- of unknowns.  Now the way the term order works is that the leading
-- monomials, the initial monomials, are the diagonal products. The
-- 3x3 determinant has 6 terms, one for each permutation of the 3
-- element set, and the leading term will be the main diagonal term
-- and the groebner basis property says that the initial ideal will be
-- generated by the first leading term, x_11*x_22*x33. The second
-- determinant will be x_11*x_22*x_43, and so on.
-- How many degrees of freedom do you have in forming a 4x3 matrix of
-- rank at most 2? What is the dimension of this variety? Well,
-- standard monomials tell you the answer. We are supposed to pick a
-- subset S of maximal cardinality in our 12 variables with the
-- property that every monomial in that subset is standard. The
-- largest cardinality that you can pick is 10. So if we take the 10
-- variables ( ,x_12,x_13,x_14, ,x_22,x_23,x_24, x_31,x_32,x_33,x_34,
-- x_41,x_42,x_43,x_44) Every monomial that you can pick is
-- standard. It does not lie in this initial ideal and we conclude
-- that the dimension of this variety is 10.
-- Suppose somebody gives you a set of polynomials such as the 4 3x3
-- determinants that we just saw. And you also have a term order so
-- you know which term is the leading term.  How can you test whether
-- a set G of polynomials is a groebner basis?  Can you believe that
-- those 4 3x3 determinants really are a groebner basis?  You need to
-- be convinced that the leading monomial of any polynomial in the
-- ideal, any of the possibly infinite polynomials of the ideal, is a
-- multiple of one of the leading terms.
-- TESTING FOR GROEBNER BASIS
-- Question: How to test whether a finite set G of polynomials is a
-- Groebner basis?  Take g,g' polynomials in G and form an
-- Subtraction-polynomial (S-polynomial) which is the stingiest linear
-- combination that knocks out the leading term, that is, form the
-- S-polynomial m'g-mg' where m,m' are monomials of lowest degree such

-- that m'*"in<"(g)=m*"in<"(g') with respect to the agreed-upon term
-- order.  g has a leading term and g' has a leading term. We want to
-- find the smallest (lowest degree) linear combination that kills the
-- leading term.
-- Theorem (Buchberger's Criterion): G is a Groebner basis if and only
-- if every S-polynomial formed by the pairs g,g' from G has normal
-- form zero with respect to G.  Normal form was the process of
-- replacing monomials that are multiples of current leading monomials
-- by lower stuff running the division algorithm with respect to the
-- suspected groebner basis.
-- So if you form any pair, lets say G has 5 polynomials, and you look
-- at all 10 possible pairs and calculate the S-pair, reduce with
-- respect to the suspected groebner basis and if all 10 reductions
-- come out with the zero polynomial then you can be certain that the
-- given polynomials were a groebner basis. This criterion is the
-- basic building block of Buchberger's algorithm. The algorithm which
-- we have used all along for transforming the input set F into the
-- output set G that is supposed to form a groebner basis.
-- BUCHBERGER'S ALGORITHM
-- INPUT:  Finite list F of polynomials in Q[x_1,...,x_n] and
--         term order
-- OUTPUT: The unique reduced Groebner basis G for the ideal generated
--         by <F> with respect to that term order
-- STEP 1: Apply Buchberger's Criterion to chack whether F is a Groebner
--         basis
--         A) Look at every pair
--         B) Form the S-pair
--         C) Reduce it
--         D) if every reduction has a zero result then it is a
--            groebner basis
-- STEP 2: If "yes", the F is a Groebner basis. Go to step 4
-- STEP 3: If "no", we found p=normalf(m'g-mg') to be nonzero.
--         Buchberger's Criterion returns a "witness" for the fact
--         that we did not have a Groebner basis, p.
--         Set F=F union {p} and go to Step 1
-- STEP 4: Replace F by the reduced Groebner basis G (apply
--         "autoreduction") and output G. Autoreduction takes any
--         Groebner basis and replaces it with the corresponding
--         unique groebner basis. To autoreduce:
--         A) Make all polynomials monic (leading coefficients are 1)
--         B) Throw out unnecessary polynomials
--         C) take trailing terms and replace them by non-trailing
--            terms
--
-- This algorithm terminates in a finite number of steps and outputs
-- G, a unique reduced Groebner basis with respect to the chosen
-- term order.

-- Why must this terminate?
-- Every ideal in a polynomial ring is finitely generated.
-- Thus, Every initial monomial ideal is finitely generated.
-- Hilbert's Basis Theorem implies that there is no infinite ascending
-- chain of ideals. Let F={f_1,...,f_d}. Each nonzero p=normalf(m'f-mf')
-- gives a strict inclusion:
-- <"in<"(f_1),...,"in<"(f_d)> is a subset of
-- <"in<"(f_1),...,"in<"(f_d),"in<"(p)>. This chain of strictly
-- contained ideals must terminate.
-- Suppose Buchberger's Criterion returns a witness, a non-zero
-- polynomial p which is a normal form not zero. If p is a nonzero
-- normal form then each term in p has the property that it is not in
-- the current initial ideal, none of the terms in p is divisible by a
-- current inital monomial.  That means that if we take the initial
-- term of p and throw it into the current initial ideal that the
-- initial ideal gets strictly larger.  Hilbert proved that there is a
-- finite chain. Therefore we terminate.
-- AN EXAMPLE
-- Take the case of polynomials in 1 variable. If you input 1 variable
-- polynomials then the algorithm simulates the euclidean algorithm.
-- Example: n=1, F={x^2+3*x-4, x^3-5*x+4}
-- The initial ideal is {x^2, x^3}. There are infinitely many
-- polynomials in the ideal. Is it the case that the two polynomials
-- form a groebner basis?
-- Is it the case that every polynomial in the ideal, of which there are
-- infinitely many, its initial ideal is a multiple of x^2 or x^3
-- STEP 1: form the S-poly
--  Here we try to form a subtraction polynomial to knock out the leading
--  term which happens if we multiply x^2 by x and x^3 by 1 and subtract:
--         x*(x^2+3*x-4) - 1*(x^3-5*x+4) = 3*x^2+x-4
--  3*x^2+x-4 is not yet in normal form with respect to the current
--  polynomials. Indeed, the 3*x^2 is a multiple of the x^2 leading term
--  so we can multiply the x^2 leading term polynomial by 3 and
--  subtract and the  result of that is the normal form
--  That is, we compute
--    (3*x^2+x-4) - 3*(x^2+3*x-4) = -8*x+8
--  and that result IS a normal form, but nonzero.
--         It has a nonzero normal form p = -8*x+8
-- Therefore F is not a Groebner basis
-- STEP 3: We enlarge F by adding p
--         The new set F union {p} is a groebner basis
-- so we have
--  F = {x^2+3*x-4, x^3-5*x+4, -8*x+8}
--  Notice that the new leading monomial -8*x is not a multiple of either

--  x^2 or x^3
-- On the next iteration the new polynomial will pass the test and we
-- end up going to step 4.
-- STEP 4: Take the current non-reduced Groebner basis consisting of
--           3 polynomials: {x^2+3*x-4, x^3-5*x+4, -8*x+8}
--           and replace it by the corresponding unique reduced
--           groebner basis.
--       The reduced Groebner basis is G={x-1}
-- SUMMARY
-- Groebner bases and the Buchberger algorithm are fundamental in
-- algebra Applications include optimization, coding, robotics,
-- statistics, etc
-- Advanced algebraic geometry algorithms: elimination theory,
--   computing cohomology, resulution of singularities, etc.
-- Structures that generalize polynomials also apply, such as
--   noncommutative polynomials, differential operators

References

[1] nothing