Complex Polynomial Systems
Introduction
The Mathematica functions Reduce, Resolve, and FindInstance allow you to solve a wide variety of problems that can be expressed in terms of equations and inequalities. The functions use a collection of algorithms applicable to classes of problems satisfying particular properties, as well as a set of heuristics that attempt to reduce the given problem to a sequence of problems that can be solved using the algorithms. This tutorial describes the algorithms used to solve the class of problems known as complex polynomial systems. It characterizes the structure of the returned answers and describes the options that affect various aspects of the methods involved.
A complex polynomial system is an expression constructed with polynomial equations and inequations
combined using logical connectives and quantifiers
An occurrence of a variable x inside _{x} or _{x} is called a bound occurrence, and any other occurrence of x is called a free occurrence. A variable x is called a free variable of a complex polynomial system if the system contains a free occurrence of x. A complex polynomial system is quantifierfree if it contains no quantifiers.
Here is an example of a complex polynomial system with free variables x, y, and z.
In Mathematica, quantifiers are represented using the functions Exists ( ) and ForAll ( ).
Any complex polynomial system can be transformed to the prenex normal form
where each Q_{i} is a quantifier or , and (x_{1}, ..., x_{n};y_{1}, ..., y_{m}) is quantifierfree.
Any quantifierfree complex polynomial system can be transformed to the disjunctive normal form
where each _{i, j} is a polynomial equation or inequation.
Reduce, Resolve, and FindInstance always put complex polynomial systems in the prenex normal form, with quantifierfree parts in the disjunctive normal form, and subtract the sides of the equations and inequations to put them in the form
In all the tutorials for complex polynomial system solving, assume that the system has been transformed to this form.
Reduce can solve arbitrary complex polynomial systems. The solution (possibly after expanding with respect to ) is a disjunction of terms of the form
where x_{1}, ..., x_{n} are the free variables of the system, each g_{i} is a polynomial, each r_{i} is an algebraic function expressed using radicals or Root objects, and any terms of the conjunction ( 2) may be absent. Each r_{i} (x_{1}, ..., x_{i1}) is well defined, that is, no denominators or leading terms of Root objects in r_{i} become zero for any (x_{1}, ..., x_{i1}) satisfying the preceding terms of the conjunction ( 2).
Resolve can eliminate quantifiers from arbitrary complex polynomial systems. If no variables are specified, the result is a logical combination of terms
where f and g are polynomials, and each x_{i} is a free variable of the system. With variables specified in the input, Resolve gives the same answer as Reduce.
This eliminates quantifiers from the system ( 1).
Out[2]=  

FindInstance can handle arbitrary complex polynomial systems giving instances of complex solutions, or an empty list for systems that have no solutions. If the number of instances requested is more than one, the instances are randomly generated from the full solution of the system, and therefore they may depend on the value of the RandomSeed option. If one instance is requested, a faster algorithm that produces one instance is used, and the instance returned is always the same.
This finds a solution for the system ( 1).
Out[3]=  

The main tool used in solving complex polynomial systems is the Gröbner basis algorithm [ 1], which is available in Mathematica as the GroebnerBasis function.
Gröbner Bases
Theory
This section gives a very brief introduction to the theory of Gröbner bases. It presents only the properties that are necessary to describe the algorithms used by Mathematica in solving complex polynomial systems. For a more complete presentation see, for example, [ 1, 2]. Note that what [ 2] calls a monomial, [ 1] calls a term, and vice versa. This tutorial uses the terminology of [ 1].
A monomial in x_{1}, ..., x_{n} is an expression of the form x_{1}^{e1}...x_{n}^{en} with nonnegative integers e_{i}.
Let M=M (x_{1}, ..., x_{n}) be the set of all monomials in x_{1}, ..., x_{n}. A monomial order is a linear order on M, such that 1t for all tM, and t_{1}t_{2} implies t_{1}st_{2}s for all t_{1}, t_{2}, s M.
Let R be a field, the domain of integers, or the domain of univariate polynomials over a field. Let Quot and Rem be functions R^{2}R defined as follows. If R is a field, Quot (a, b)=a/b, and Rem (a, b)=0. If R is the domain of integers, Quot and Rem are the integer quotient and remainder functions, with b/2<Rem (a, b)≤b/2. If R is the domain of univariate polynomials over a field, Quot and Rem are the polynomial quotient and remainder functions.
A product t=a m, where a is a nonzero element of R and m is a monomial, is called a term.
Let be a monomial order on M, and let fR[x_{1}, ..., x_{n}]\{0}. The leading monomial LM (f) of f is the largest monomial appearing in f, the leading coefficient LC (f) of f is the coefficient at LM (f) in f, and the leading term LT (f) of f is the product LC (f)LM (f).
A Gröbner basis of an ideal I in R[x_{1}, ..., x_{n}], with respect to a monomial order , is a finite set G of polynomials, such that for each fI, there exists gG, such that LT (g) divides LT (f). Every ideal I has a Gröbner basis (see [ 1] for a proof).
Let pR[x_{1}, ..., x_{n}]\{0}, and let mR[x_{1}, ..., x_{n}] be a monomial. A term t=a m is reducible modulo p, if LM (p) divides m, and a≠Rem (a, LC (p)). If t is reducible modulo p, the reduction of t modulo p is the polynomial
Note that if Rem (a, LC (p))≠0, then LT (Red (t, p))=Rem (a, LC (p))m; otherwise, LM (Red (t, p))m.
Let fR[x_{1}, ..., x_{n}], and let P be an ordered finite subset of R[x_{1}, ..., x_{n}]\{0}. f is reducible modulo P if f contains a term reducible modulo an element of P. The reduction Red (f, P) of f modulo P is defined by the following procedure. While the set RT of terms of f reducible modulo an element of P is not empty, take the term tRT with the largest monomial, take the first pP, such that t is reducible modulo p, and replace the term t in f with Red (t, p). Note that the monomials of terms t chosen in subsequent steps of the procedure form a descending chain, and each monomial can appear at most k times, where k is the number of elements of P, hence the procedure terminates.
A Gröbner basis G is semireduced if for all gG, g is not reducible modulo G\{g}, and if R is the domain of integers, LC (g)>0.
The Mathematica function GroebnerBasis returns semireduced Gröbner bases. In the following discussion, all Gröbner bases are assumed to be semireduced. Note that this is not the same as reduced Gröbner bases defined in the literature, since here the basis polynomials are not required to be monic. For a fixed monomial order, every ideal has a unique reduced Gröbner basis. Semireduced Gröbner bases defined here are only unique up to multiplication by invertible elements of R (see Property 2).
Property 1: Let G be a Gröbner basis of an ideal I in R[x_{1}, ..., x_{n}], and let fR[x_{1}, ..., x_{n}]. Then fI iff Red (f, G)=0.
This is a simple consequence of the definitions.
Property 2: Let G={g_{1}, ...g_{k}} and H={h_{1}, ...h_{m}} be two Gröbner bases of an ideal I with respect to the same monomial order , and suppose that elements of G and H are ordered by their leading monomials. Then k=m, and for all 1≤i≤k, if R is the domain of integers, g_{i}=h_{i}; otherwise, g_{i}=c_{i} h_{i} for some invertible element c_{i} of R.
Proof: If LM (f)=LM (g), then LT (f) is reducible modulo g or LT (g) is reducible modulo f. Hence the leading monomials of the elements of a Gröbner basis are all different. Without loss of generality, assume k≤m. For induction, fix j≤k and suppose that for all i<j, g_{i}=c_{i} h_{i} for some invertible element c_{i} of R. If R is the domain of integers, c_{i}=1. Without loss of generality, assume LM (g_{j})LM (h_{j}). Since g_{j} belongs to I, there exists i such that LT (h_{i}) divides LT (g_{j}). Then LM (h_{i})LM (g_{j}), and so i≤j. If i<j, then g_{j} would be reducible modulo h_{i} and also modulo g_{i}=c_{i} h_{i}, which is impossible, since G is semireduced. Hence i=j, and LM (g_{j})=LM (h_{j}), and LT (h_{j}) divides LT (g_{j}). Similarly, LT (g_{j}) divides LT (h_{j}). Therefore, there exists an invertible element c_{j} of R, such that LT (g_{j})=c_{j}LT (h_{j}). If R is the domain of integers, LC (g_{j}) and LC (h_{j}) are positive, and so c_{j}=1. Let r=c_{j}h_{j}g_{j}. Suppose r≠0. Since r belongs to I, LT (r) must be divisible by LT (g_{i}), for some i<j. Let and be the coefficients at LM (r) in g_{j} and h_{j}. If R is a field, the term LM (r) of g_{j} is reducible modulo g_{i}, which contradicts the assumption that G is semireduced. If R is the domain of univariate polynomials over a field,
and so either g_{j} is reducible modulo g_{i}, or h_{j} is reducible modulo h_{i}=c_{i}g_{i}, which contradicts the assumption that G and H are semireduced. Finally, let R be the domain of integers. Since neither g_{j} is reducible modulo g_{i} nor h_{j} is reducible modulo h_{i}=g_{i}, LC (g_{i})/2<≤LC (g_{i})/2 and LC (g_{i})/2< ≤LC (g_{i})/2. Hence LC (g_{i})<LC (r)=<LC (g_{i}), which is impossible, since LT (r) is divisible by LT (g_{i}). Therefore r=0, and so g_{j}=c_{j} h_{j}. By induction on j, for all j≤k, g_{j}=c_{j} h_{j}. If k<m, then h_{k+1} would be reducible modulo some g_{j}, with j≤k, and hence h_{k+1} would be reducible modulo h_{j}=c_{j}^{1}g_{j}. Therefore k=m, which completes the proof of Property 2.
Property 3: Let I be an ideal in R[x_{1}, ..., x_{n}], let fR[x_{1}, ..., x_{n}], and let G be a Gröbner basis of the ideal <I, 1y f> in R[x_{1}, ..., x_{n}, y]. Then f belongs to the radical of I iff G={c} for an invertible element c of R.
If an ideal contains invertible elements of R, GroebnerBasis always returns {1}.
belongs to the ideal J=<I, 1y f> for any nonnegative integer k. Hence, if f belongs to the radical of I, then 1 belongs to J. Since G is a Gröbner basis of J, it must contain an element c whose leading coefficient divides 1. Hence c is an invertible element of R. Since G is semireduced and c divides any term, G={c}. Now suppose that G={c} for an invertible element c of R. Then 1 belongs to J, and so
where each a_{i} belongs to I, and each b_{i} belongs to R[x_{1}, ..., x_{n}]. Hence comparing coefficients at powers of y leads to the following equations modulo I: b_{0}1, b_{i}b_{i1}f, for 1≤i≤m1, and b_{m1}f0. Then, b_{i}f^{i}, for 0≤i≤m1, and f^{m}0 modulo I. Therefore, f belongs to the radical of I, which completes the proof of Property 3.
The following more technical property is important for solving complex polynomial systems.
Property 4: Let G be a Gröbner basis of an ideal I in [x_{1}, ..., x_{n}, y] with a monomial order that makes monomials containing y greater than monomials not containing y, let h be the element of G with the lowest positive degree d in y, let c (x_{1}, ..., x_{n}) be the leading coefficient of h in y, and let {h_{1}, ..., h_{s}} be all elements of G that do not depend on y. Then for any polynomial pI and any point (a_{1}, ..., a_{n, }b) if c (a_{1}, ..., a_{n})≠0, h_{i} (a_{1}, ..., a_{n})=0, for 1≤i≤s, and h (a_{1}, ..., a_{n}, b)= 0, then p (a_{1}, ..., a_{n}, b)= 0.
Proof: Consider the pseudoremainder r of the division of p by h as polynomials in y.
Since p and h belong to I, so does r. By Property 1, reduction of r by G must yield zero. Since the degree of r in y is less than d, r cannot be reduced by any of the elements of G that depend on y. Hence
and so r (a_{1}, ..., a_{n}, b)=0. Since c (a_{1}, ..., a_{n})≠0, ( 1) implies that p (a_{1}, ..., a_{n}, b)= 0, which completes the proof of Property 4.
Mathematica Function GroebnerBasis
The Mathematica function GroebnerBasis finds semireduced Gröbner bases. This section describes GroebnerBasis options used in the solving of complex polynomial systems.
  
CoefficientDomain  Automatic  the type of objects assumed to be coefficients 
Method  Automatic  the method used to compute the basis 
MonomialOrder  Lexicographic  the criterion used for ordering monomials 
GroebnerBasis options used in the solving of complex polynomial systems.
CoefficientDomain
This option specifies the domain R of coefficients. With the default Automatic setting, the coefficient domain is the field generated by numeric coefficients present in the input.
Integers  the domain of integers 
InexactNumbers[prec]  inexact numbers with precision prec 
Polynomials[x]  the domain of polynomials in x 
RationalFunctions  the field of rational functions in variables not on the variable list given to GroebnerBasis 
Rationals  the field of rational numbers 
Available settings for CoefficientDomain.
Note that the coefficient domain R also depends on the setting of the Modulus option of GroebnerBasis. With Modulus>p, for a prime number p, the coefficient domain is the field _{p}, or the field of rational functions over _{p} if CoefficientDomain>RationalFunctions.
Method
With the default setting Method>Automatic, GroebnerBasis normally uses a variant of the Buchberger algorithm. Another algorithm available is the Gröbner walk, which computes a Gröbner basis in an easier monomial order and then transforms it to the required harder monomial order. This is often faster than directly computing a Gröbner basis in the required order, especially if the input polynomials are known to be a Gröbner basis for the easier order. With the Method>Automatic setting, GroebnerBasis uses the Gröbner walk for the default CoefficientDomain>Rationals and MonomialOrder>Lexicographic.
GroebnerBasis[polys,vars,Method>{"GroebnerWalk","InitialMonomialOrder">order_{1}},MonomialOrder>order_{2}] 
 find a Gröbner basis in order_{1} and use the Gröbner walk algorithm to transform it to a Gröbner basis in order_{2} 
Transforming Gröbner bases using the Gröbner walk algorithm.
MonomialOrder
This option specifies the monomial order. The value can be either one of the named monomial orders or a weight matrix. The following table gives conditions for x_{1}^{d1}...x_{n}^{dn} x_{1}^{e1}...x_{n}^{en}.
Lexicographic  d_{1}=e_{1}...d_{i1}=e_{i1} 
DegreeLexicographic  d_{1}+...+d_{n}<e_{1}+...+e_{n} (d_{1}+...+d_{n}=e_{1}+...+e_{n}d_{1}=e_{1}...d_{i1}=e_{i1}d_{i}<e_{i}) 
DegreeReverseLexicographic  d_{1}+...+d_{n}<e_{1}+...+e_{n} (d_{1}+...+d_{n}=e_{1}+...+e_{n}d_{n}=e_{n}...d_{i+1}=e_{i+1}d_{i}<e_{i}) 
Monomial orders.
Quantifier elimination needs an order in which monomials containing quantifier variables are greater than monomials not containing quantifier variables. The Lexicographic order satisfies this condition, but the following EliminationOrder usually leads to faster computations.
where d denotes total degree, X denotes free variables, Y denotes quantifier variables, m_{i} and n_{i} are monomials, and _{DRL} denotes the DegreeReverseLexicographic order.
Using EliminationOrder requires the GroebnerBasis syntax with elimination variables specified.
GroebnerBasis[polys,xvars,yvars,MonomialOrder>EliminationOrder] 
 find a Gröbner basis in EliminationOrder 
Gröbner basis in elimination order.
By default, GroebnerBasis with MonomialOrder>EliminationOrder drops the polynomials that contain yvars from the result, returning only basis polynomials in xvars. To get all basis polynomials, the value of the system option EliminateFromGroebnerBasis from the GroebnerBasisOptions group must be changed. ( Mathematica changes the option locally in the quantifier elimination algorithm.) The option value can be changed with
  
"EliminateFromGroebnerBasis"  True  whether GroebnerBasis with MonomialOrder>EliminationOrder should remove polynomials containing elimination variables 
System option EliminateFromGroebnerBasis.
This eliminates y from . The answer is a polynomial whose zeros are the Zariski closure of the projection of the solution set of the two original equations on the (x_{1}, x_{2}) plane.
Out[4]=  

The exact description of the projection of the solution set on the (x_{1}, x_{2}) plane depends on all basis polynomials. Note that the second basis polynomial cannot be zero if x_{1} or x_{2} are zero.
Out[6]=  

This resets the system option to its default value. 
Resolve gives the exact description of the projection of the solution set on the (x_{1}, x_{2}) plane.
Out[8]=  

Decision Problems
A decision problem is a system with all variables existentially quantified, that is, a system of the form
where x_{1}, ..., x_{n} are all variables in . Solving a decision problem means deciding whether it is equivalent to True or to False, that is, deciding whether the quantifierfree system of polynomial equations and inequations (x_{1}, ..., x_{n}) has solutions.
Solving this decision problem proves that a quadratic equation with a zero determinant cannot have two different roots.
Out[9]=  

solving any decision problem can be reduced to solving a finite number of decision problems of the form
By Hilbert's Nullstellensatz and Property 3 of Gröbner bases
has complex solutions iff
with an arbitrary monomial order, is different than {1}.
When Mathematica solves a decision problem, the monomial order used by the GroebnerBasis computation is MonomialOrder>EliminationOrder, with {z} specified as the elimination variable list. This setting corresponds to the monomial ordering in which monomials containing z are greater than those that do not contain z, and the ordering of monomials not containing z is degree reverse lexicographic. If there is no inequation condition, there is no need to introduce z, and Mathematica uses MonomialOrder>DegreeReverseLexicographic.
Quantifier Elimination
For any complex polynomial system there exists an equivalent quantifierfree complex polynomial system. This follows from Chevalley's theorem, which states that a projection of a quasialgebraically constructible set (a solution set of a quantifierfree system of polynomial equations and inequations) is a quasialgebraically constructible set [ 3]. Quantifier elimination is the procedure of finding a quantifierfree complex polynomial system equivalent to a given complex polynomial system. In Mathematica, quantifier elimination for complex polynomial systems is done by Resolve. It is also used by Reduce and FindInstance as the first step in solving or finding instances of solutions of complex polynomial systems.
Eliminating quantifiers from this system gives a condition for quadratic equations to have at least two different zeros.
Out[12]=  

For complex polynomial systems Mathematica uses the following quantifier elimination method. Given the identities
eliminating quantifiers from any complex polynomial system can be reduced to a finite number of single existential quantifier eliminations from systems of the form
To eliminate the quantifier from ( 1), Mathematica first computes the Gröbner basis of equations
with a monomial order that makes monomials containing y greater than monomials not containing y.
The monomial order used is EliminationOrder, with {y} specified as the elimination variable list and all basis polynomials kept.
If G contains no polynomials that depend on y, then a quantifierfree system equivalent to ( 1) can be obtained by equating all elements of G to zero, and asserting that at least one coefficient of g as a polynomial in y is not equal to zero. Otherwise let h be the element of G with the lowest positive degree d in y, let c (x_{1}, ..., x_{n}) be the leading coefficient of h in y, and let {h_{1}, ..., h_{s}} be all elements of G that do not depend on y. Now ( 1) can be split into a disjunction of two systems
To eliminate the quantifier from ( 2), the quantifier elimination procedure is called recursively. Since the ideal generated by {c, f_{1}, ..., f_{k}} strictly contains the ideal generated by {f_{1}, ..., f_{k}}, the Noetherian property of polynomial rings guarantees finiteness of the recursion.
If c belongs to the radical of the ideal generated by {f_{1}, ..., f_{k}}, which is exactly when 1 belongs to
( 3) is equivalent to False. Otherwise let
be the pseudoremainder of the division of g^{d} by h as polynomials in y. Then ( 3) is equivalent to the quantifierfree system
To show that ( 3) implies ( 4), suppose that (a_{1}, ..., a_{n}) satisfies ( 3). Then c (a_{1}, ..., a_{n})≠ 0 and there exists b, such that
Since {h_{1}, ..., h_{s}} and h belong to the ideal generated by {f_{1}, ..., f_{k}},
and h (a_{1}, ..., a_{n}, b)=0. Hence
To show that ( 4) implies ( 3), suppose that (a_{1}, ..., a_{n}) satisfies ( 4). Then
Since h (a_{1}, ..., a_{n}, y) is a polynomial of degree d, and r (a_{1}, ..., a_{n}, y) is a nonzero polynomial of degree less than d, there is a root b of h (a_{1}, ..., a_{n}, y) such that (yb)^{m} divides h (a_{1}, ..., a_{n}, y) but not r (a_{1}, ..., a_{n}, y) for some 1≤m≤d. If g (a_{1}, ..., a_{n}, b) was zero, then (yb)^{m} would divide g (a_{1}, ..., a_{n}, y)^{d}, which is impossible because it would imply that (yb)^{m} divides r (a_{1}, ..., a_{n}, y). Therefore g (a_{1}, ..., a_{n}, b)≠0. Property 4 shows that p (a_{1}, ..., a_{n}, b)= 0 for any polynomial pG. Since G is a Gröbner basis of the ideal generated by {f_{1}, ..., f_{k}},
which completes the proof of correctness of the quantifier elimination algorithm.
This eliminates the quantifier from . Here g=1, h=y+x_{1}+x_{2}, and c=1. Since c is a nonzero constant, ( 2) is False and the equivalent quantifierfree system is given by ( 4). Since g is a nonzero constant, ( 4) becomes .
Out[14]=  

This resets the system option to its default value. 
Arbitrary Complex Polynomial Systems
FindInstance
FindInstance can handle arbitrary complex polynomial systems giving instances of complex solutions, or an empty list for systems that have no solutions. If the number of instances requested is more than one, the instances are randomly generated from the full solution of the system given by Reduce. If one instance is requested, a faster algorithm that produces one instance is used. Here is a description of the algorithm used to find a single instance, or prove that a system has no solutions.
If the system contains general quantifiers ( ), the quantifier elimination algorithm is used to eliminate the innermost quantifiers until the system contains only existential quantifiers ( ) or is quantifierfree. Note that
has solutions if and only if (x_{1}, ..., x_{n}, y_{1}, ..., y_{m}) has solutions, and if (a_{1}, ..., a_{n}, b_{1}, ..., b_{m}) is a solution of (x_{1}, ..., x_{n}, y_{1}, ..., y_{m}), then (b_{1}, ..., b_{m}) is a solution of ( 1). Hence to find instances of solutions of systems containing only existential quantifiers it is enough to be able to find instances of quantifierfree systems. Moreover, (a_{1}, ..., a_{n}) is a solution of
if and only if it is a solution of one of the _{i} (x_{1}, ..., x_{n}), with 1≤i≤m, so it is enough to show how to find instances of solutions of
First compute the GroebnerBasis G of {f_{1}, ..., f_{k}, 1g z} with MonomialOrder>EliminationOrder, eliminating the polynomials that depend on z (if there is no inequation condition, G is the GroebnerBasis of {f_{1}, ..., f_{k}} with MonomialOrder>DegreeReverseLexicographic). If G contains 1, there are no solutions. Otherwise, compute a subset S of {x_{1}, ..., x_{n}} of the highest cardinality among subsets strongly independent modulo the ideal generated by G with respect to the degree reverse lexicographic order ([ 1], Section 9.3). Reorder {x_{1}, ..., x_{n}} so that S={x_{nd+1}, ..., x_{n}}, and compute the lexicographic order GroebnerBasis H of the ideal generated by G. To compute H, Mathematica uses the Gröbner walk algorithm.
For each of the variables x_{i}, 1≤i≤nd, select the polynomial h_{i}H with the smallest leading monomial among elements of H that depend on x_{i} and not on {x_{1}, ..., x_{i1}}. Let c_{i} be the leading coefficient of h_{i} as a polynomial in x_{i}. If c_{i} depends on a variable that is not in S, replace H with the lexicographic order Gröbner basis of the ideal generated by H and c_{i}. The following shows that this operation keeps S strongly independent modulo the ideal generated by H. Hence, possibly after a finite (by the Noetherian property of polynomial rings) number of extensions of H, the leading coefficient c_{i} of h_{i} depends only on {x_{nd+1}, ..., x_{n}}, for all 1≤i≤nd. For the set of polynomials P, let Z (P) be the set of common zeros of elements of P. Both Z (G) and Z (H) have dimension d, and Z (H)Z (G), hence any ddimensional irreducible component of Z (H) is also a component of Z (G). Since g does not vanish on any irreducible component of Z (G), it does not vanish on any ddimensional irreducible component of Z (H). Therefore, the Gröbner basis of H and g contains a polynomial t depending only on {x_{nd+1}, ..., x_{n}}. Let p=t c_{1}...c_{nd}. To find a solution of ( 2), pick its last d coordinates {a_{nd+1}, ..., a_{n}} so that p (a_{nd+1}, ..., a_{n})≠0. For all 1≤i≤nd, c_{i} (a_{nd+1}, ..., a_{n})≠0, and so by Property 4 if a_{i}, for i=nd, ..., 1, is chosen to be the first root of h_{i} (x_{i}, a_{i+1}, ..., a_{n}), then (a_{1}, ..., a_{n})Z (H)Z (G). Moreover, g (a_{1}, ..., a_{n})≠0, because otherwise (a_{1}, ..., a_{n}) would belong to Z (H{g}), which would imply that t (a_{nd+1}, ..., a_{n})= 0, which is impossible since t divides p.
To prove the correctness of the aforementioned algorithm, it must be shown that extending H by c_{i} that depend on a variable not in S preserves strong independence of S modulo the ideal generated by H. Suppose for some 1≤i≤nd, c_{i} depends on a variable, which is not in S. Let I_{i+1}[x_{i+1}, ..., x_{n}] denote the ideal generated by H[x_{i+1}, ..., x_{n}], and let J_{i+1}[x_{i+1}, ..., x_{n}] denote the ideal generated by I_{i+1} and c_{i}. Then J_{i+1} does not contain nonzero elements of [x_{nd+1}, ..., x_{n}]. To prove this, suppose that r=p c_{i}+qJ_{i+1}[x_{nd+1}, ..., x_{n}]\{0} where p[x_{i+1}, ..., x_{n}] and qI_{i+1}. Then h_{i}= c_{i}x_{i}^{k}+t, with deg_{xi} (t)<k, and
belongs to the ideal generated by H, and so does g_{i}= r x_{i}^{k}+p t. This contradicts the choice of h_{i} since the leading monomial of g_{i} depends on x_{i} and is strictly smaller than the leading monomial of h_{i}. Therefore, the projection of Z (J_{i+1}) on A_{d}= (^{d})_{{xnd+1, ..., xn}} is dense in A_{d}, and so, since Z (I_{i+1}) has dimension d, c_{i} must be zero on some irreducible component C_{i+1} of Z (I_{i+1}) whose projection on A_{d} is dense in A_{d}. Since Z (I_{i+1}) is the Zariski closure of the projection of the ddimensional set Z (H), C_{i+1} is contained in the Zariski closure of the projection of an irreducible component C of Z (H). Z (c_{i})C has dimension d, hence c_{i} is zero on C, and the projection of C on A_{d} is dense in A_{d}, which proves that S is strongly independent modulo the ideal generated by H and c_{i}.
Here is an example in which H needs to be extended. Here S={x_{3}}, h_{1}= (x_{2}x_{3}) x_{1}, c_{1}=x_{2}x_{3}, and I_{2}=< (x_{2}x_{3})^{2} (x_{2}2 x_{3})>. c_{1} is zero on one of the two onedimensional components of I_{2}.
Out[16]=  

Extending H by c_{1} results in all c_{i} depending on x_{3} only (in fact even constant) while preserving the strong independence of {x_{3}}.
Out[17]=  

Reduce
Reduce can solve arbitrary complex polynomial systems. As the first step, Reduce uses the quantifier elimination algorithm to eliminate the quantifiers. If the obtained quantifierfree system is a disjunction, each term of the disjunction is solved separately, and the solution is given as a disjunction of the solutions of the terms. Thus, the problem is reduced to solving quantifierfree systems of the form
First compute the GroebnerBasis G of {f_{1}, ..., f_{k}, 1g z} with variable order {z, x_{n}, ..., x_{1}} and MonomialOrder>Lexicographic, and select the polynomials that do not depend on z. Then the solution set of G=0 g (x_{1}, ..., x_{n})≠0 is equal to the solution set of ( 3) and g does not vanish on any component of the zero set Z (G) of G. If G contains 1, ( 3) has no solutions. Otherwise for each 1≤i≤n, such that the set G_{i} of elements of G depending on x_{i} and not on any x_{j} with j>i is not empty, select an element h_{i} of G_{i} with the lowest positive degree in x_{i}. If one of the leading coefficients c_{i} of h_{i} is zero on Z (G), that is, it belongs to the radical of the ideal generated by G, replace G by the lexicographic Gröbner basis of the ideal generated by G and c_{i}. Now split the system into
and call the solving procedure recursively on all but the last term of the disjunction ( 4). Note that the algebraic set c_{ij}=0G=0 is strictly contained in G=0, so the recursion is finite. If the product of all the c_{i} and g belongs to the radical of the ideal generated by G, the last term has no solutions. Otherwise, by Property 4, the solution set of the last term is equal to
The conditions c_{ij}≠0 guarantee that all the solutions (represented as radicals or Root objects) given by Roots[h_{ij}=0, x_{ij}] are well defined. Reduce performs several operations in order to simplify the inequation conditions returned, like removing multiple factors, removing factors common with earlier inequation conditions, reducing modulo the h_{ij}, and removing factors that are nonzero on Z (G).
Options
Options for Reduce, Resolve, and FindInstance
The Mathematica functions for solving complex polynomial systems have a number of options that control the way they operate. This section gives a summary of these options.
  
Backsubstitution  False  whether the solutions given by Reduce and Resolve with specified variables should be unwound by backsubstitution 
Cubics  False  whether the Cardano formulas should be used to express solutions of cubics 
Quartics  False  whether the Cardano formulas should be used to express solutions of quartics 
Options of Reduce and Resolve affecting the behavior of complex polynomial systems.
  
WorkingPrecision   the working precision to be used in computations, with the default settings of system options; the value of working precision affects only calls to Roots 
Options of Reduce, Resolve, and FindInstance affecting the behavior of complex polynomial systems.
Backsubstitution
By default, Reduce may use variables appearing earlier in the variable list to express solutions for variables appearing later in the variable list.
Out[18]=  

With Backsubstitution>True, Reduce uses backsubstitution to eliminate variables from the righthand sides of the equations.
Out[19]=  

Cubics and Quartics
By default Reduce does not use the Cardano formulas for solving cubics or quartics.
Out[20]=  

WorkingPrecision
The ReduceOptions Group of System Options
Here are the system options from the ReduceOptions group that may affect the behavior of Reduce, Resolve, and FindInstance for complex polynomial systems. The options can be set with
This sets the option FinitePrecisionGB to True. 
This checks the value of FinitePrecisionGB.
Out[24]=  

This sets the option FinitePrecisionGB back to the default value False. 
  
"FinitePrecisionGB"  False  whether finite values of working precision should be used in calls to GroebnerBasis 
"ReorderVariables"  False  whether Reduce and Resolve are allowed to reorder the specified variables 
ReduceOptions group options that affect the behavior of Reduce, Resolve, and FindInstance for complex polynomial systems.
FinitePrecisionGB
Using finite precision may significantly improve the speed of GroebnerBasis computations. However, the numeric computations may fail due to loss of precision, or give incorrect answers. They usually give less precise results than exact GroebnerBasis computations followed by numeric root finding.
Out[31]=  

This shows that the results are equal up to their precision.
Out[32]=  

ReorderVariables
By default, Reduce is not allowed to reorder the specified variables. Variables appearing earlier in the variable list may be used to express solutions for variables appearing later in the variable list, but not vice versa.
Out[34]=  

Setting the system option "ReorderVariables">True allows Reduce to pick a variable order that makes the equations easier to solve.
Out[35]=  

References
[1] Becker T. and V. Weispfenning. Gröbner Bases. SpringerVerlag (1993)
[2] Cox D., J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. SpringerVerlag (1996)
[3] Łojasiewicz S. Introduction to Complex Analytic Geometry. SpringerVerlag (1991)






