Complex Polynomial Systems
| Introduction | Arbitrary Complex Polynomial Systems |
| Gröbner Bases | Options |
| Decision Problems | References |
| Quantifier Elimination |
Introduction
The Wolfram Language 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 
inside 
or 
is called a bound occurrence, and any other occurrence of 
is called a free occurrence. A variable 
is called a free variable of a complex polynomial system if the system contains a free occurrence of 
. A complex polynomial system is quantifier-free if it contains no quantifiers.
Here is an example of a complex polynomial system with free variables 
, 
, and 
.
In the Wolfram Language, quantifiers are represented using the functions Exists (
) and ForAll (
).
Any complex polynomial system can be transformed to the prenex normal form
where each 
is a quantifier 
or 
, and 
is quantifier-free.
Any quantifier-free complex polynomial system can be transformed to the disjunctive normal form
where each 
is a polynomial equation or inequation.
Reduce, Resolve, and FindInstance always put complex polynomial systems in the prenex normal form, with quantifier-free 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 
are the free variables of the system, each 
is a polynomial, each 
is an algebraic function expressed using radicals or Root objects, and any terms of the conjunction (2) may be absent. Each 
is well defined, that is, no denominators or leading terms of Root objects in 
become zero for any 
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 
and 
are polynomials, and each 
is a free variable of the system. With variables specified in the input, Resolve gives the same answer as Reduce.
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.
The main tool used in solving complex polynomial systems is the Gröbner basis algorithm [1], which is available in the Wolfram Language 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 the Wolfram Language 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 
is an expression of the form 
with non‐negative integers 
.
Let 
be the set of all monomials in 
. A monomial order is a linear order 
on 
, such that 
for all 
, and 
implies 
for all 
.
Let 
be a field, the domain of integers, or the domain of univariate polynomials over a field. Let 
and 
be functions 
defined as follows. If 
is a field, 
, and 
. If 
is the domain of integers, 
and 
are the integer quotient and remainder functions, with 
. If 
is the domain of univariate polynomials over a field, 
and 
are the polynomial quotient and remainder functions.
A product 
, where 
is a nonzero element of 
and 
is a monomial, is called a term.
Let 
be a monomial order on 
, and let 
. The leading monomial 
of 
is the 
-largest monomial appearing in 
, the leading coefficient 
of 
is the coefficient at 
in 
, and the leading term 
of 
is the product 
.
A Gröbner basis of an ideal 
in 
, with respect to a monomial order 
, is a finite set 
of polynomials, such that for each 
, there exists 
, such that 
divides 
. Every ideal 
has a Gröbner basis (see [1] for a proof).
Let 
, and let 
be a monomial. A term 
is reducible modulo 
, if 
divides 
, and 
. If 
is reducible modulo 
, the reduction of 
modulo 
is the polynomial
Note that if 
, then 
; otherwise, 
.
Let 
, and let 
be an ordered finite subset of 
. 
is reducible modulo 
if 
contains a term reducible modulo an element of 
. The reduction 
of 
modulo 
is defined by the following procedure. While the set 
of terms of 
reducible modulo an element of 
is not empty, take the term 
with the 
-largest monomial, take the first 
, such that 
is reducible modulo 
, and replace the term 
in 
with 
. Note that the monomials of terms 
chosen in subsequent steps of the procedure form a 
-descending chain, and each monomial can appear at most 
times, where 
is the number of elements of 
, hence the procedure terminates.
A Gröbner basis 
is semi-reduced if for all 
, 
is not reducible modulo 
, and if 
is the domain of integers, 
.
The Wolfram Language function GroebnerBasis returns semi-reduced Gröbner bases. In the following discussion, all Gröbner bases are assumed to be semi-reduced. 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. Semi-reduced Gröbner bases defined here are only unique up to multiplication by invertible elements of 
(see Property 2).
Property 1: Let 
be a Gröbner basis of an ideal 
in 
, and let 
. Then 
iff 
.
This is a simple consequence of the definitions.
Property 2: Let 
and 
be two Gröbner bases of an ideal 
with respect to the same monomial order 
, and suppose that elements of 
and 
are ordered by their leading monomials. Then 
, and for all 
, if 
is the domain of integers, 
; otherwise, 
for some invertible element 
of 
.
Proof: If 
, then 
is reducible modulo 
or 
is reducible modulo 
. Hence the leading monomials of the elements of a Gröbner basis are all different. Without loss of generality, assume 
. For induction, fix 
and suppose that for all 
, 
for some invertible element 
of 
. If 
is the domain of integers, 
. Without loss of generality, assume 
. Since 
belongs to 
, there exists 
such that 
divides 
. Then 
, and so 
. If 
, then 
would be reducible modulo 
and also modulo 
, which is impossible, since 
is semi-reduced. Hence 
, and 
, and 
divides 
. Similarly, 
divides 
. Therefore, there exists an invertible element 
of 
, such that 
. If 
is the domain of integers, 
and 
are positive, and so 
. Let 
. Suppose 
. Since 
belongs to 
, 
must be divisible by 
, for some 
. Let 
and 
be the coefficients at 
in 
and 
. If 
is a field, the term 
of 
is reducible modulo 
, which contradicts the assumption that 
is semi-reduced. If 
is the domain of univariate polynomials over a field,
and so either 
is reducible modulo 
, or 
is reducible modulo 
, which contradicts the assumption that 
and 
are semi-reduced. Finally, let 
be the domain of integers. Since neither 
is reducible modulo 
nor 
is reducible modulo 
, 
and 
. Hence 
, which is impossible, since 
is divisible by 
. Therefore 
, and so 
. By induction on 
, for all 
, 
. If 
, then 
would be reducible modulo some 
, with 
, and hence 
would be reducible modulo 
. Therefore 
, which completes the proof of Property 2.
Property 3: Let 
be an ideal in 
, let 
, and let 
be a Gröbner basis of the ideal 
in 
. Then 
belongs to the radical of 
iff 
for an invertible element 
of 
.
If an ideal contains invertible elements of 
, GroebnerBasis always returns 
.
belongs to the ideal 
for any non‐negative integer 
. Hence, if 
belongs to the radical of 
, then 1 belongs to 
. Since 
is a Gröbner basis of 
, it must contain an element 
whose leading coefficient divides 1. Hence 
is an invertible element of 
. Since 
is semi-reduced and 
divides any term, 
. Now suppose that 
for an invertible element 
of 
. Then 1 belongs to 
, and so
where each 
belongs to 
, and each 
belongs to 
. Hence comparing coefficients at powers of 
leads to the following equations modulo 
: 
, 
, for 
, and 
. Then, 
, for 
, and 
modulo 
. Therefore, 
belongs to the radical of 
, which completes the proof of Property 3.
The following more technical property is important for solving complex polynomial systems.
Property 4: Let 
be a Gröbner basis of an ideal 
in 
with a monomial order that makes monomials containing 
greater than monomials not containing 
, let 
be the element of 
with the lowest positive degree 
in 
, let 
be the leading coefficient of 
in 
, and let 
be all elements of 
that do not depend on 
. Then for any polynomial 
and any point 
if 
, 
, for 
, and 
, then 
.
Proof: Consider the pseudoremainder 
of the division of 
by 
as polynomials in 
.
Since 
and 
belong to 
, so does 
. By Property 1, reduction of 
by 
must yield zero. Since the degree of 
in 
is less than 
, 
cannot be reduced by any of the elements of 
that depend on 
. Hence
and so 
. Since 
, (1) implies that 
, which completes the proof of Property 4.
Wolfram Language Function GroebnerBasis
The Wolfram Language function GroebnerBasis finds semi-reduced Gröbner bases. This section describes GroebnerBasis options used in the solving of complex polynomial systems.
option name | default value | |
| 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.
This option specifies the domain 
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  |
| 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 
also depends on the setting of the Modulus option of GroebnerBasis. With Modulus->p, for a prime number 
, the coefficient domain is the field 
, or the field of rational functions over 
if CoefficientDomain->RationalFunctions.
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"->order1},MonomialOrder->order2] | |
| find a Gröbner basis in order1 and use the Gröbner walk algorithm to transform it to a Gröbner basis in order2 | |
Transforming Gröbner bases using the Gröbner walk algorithm.
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 
.
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 
denotes total degree, 
denotes free variables, 
denotes quantifier variables, 
and 
are monomials, and 
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 
from the result, returning only basis polynomials in 
. To get all basis polynomials, the value of the system option EliminateFromGroebnerBasis from the GroebnerBasisOptions group must be changed. (The Wolfram Language changes the option locally in the quantifier elimination algorithm.) The option value can be changed with
SetSystemOptions["GroebnerBasisOptions"->{"EliminateFromGroebnerBasis"->False}].
option name | default value | |
| "EliminateFromGroebnerBasis" | True | whether GroebnerBasis with MonomialOrder->EliminationOrder should remove polynomials containing elimination variables |
System option EliminateFromGroebnerBasis.
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 
plane:
plane depends on all basis polynomials. Note that the second basis polynomial cannot be zero if 
or 
is zero:
Decision Problems
A decision problem is a system with all variables existentially quantified, that is, a system of the form
where 
are all variables in 
. Solving a decision problem means deciding whether it is equivalent to True or to False, that is, deciding whether the quantifier-free system of polynomial equations and inequations 
has solutions.
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
with an arbitrary monomial order, is different than {1}.
When the Wolfram Language 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 the Wolfram Language uses MonomialOrder->DegreeReverseLexicographic.
Quantifier Elimination
For any complex polynomial system there exists an equivalent quantifier-free complex polynomial system. This follows from Chevalley's theorem, which states that a projection of a quasi-algebraically constructible set (a solution set of a quantifier-free system of polynomial equations and inequations) is a quasi-algebraically constructible set [3]. Quantifier elimination is the procedure of finding a quantifier-free complex polynomial system equivalent to a given complex polynomial system. In the Wolfram Language, 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.
For complex polynomial systems the Wolfram Language 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), the Wolfram Language first computes the Gröbner basis of equations
with a monomial order that makes monomials containing 
greater than monomials not containing 
.
The monomial order used is EliminationOrder, with 
specified as the elimination variable list and all basis polynomials kept.
If 
contains no polynomials that depend on 
, then a quantifier-free system equivalent to (1) can be obtained by equating all elements of 
to zero, and asserting that at least one coefficient of 
as a polynomial in 
is not equal to zero. Otherwise let 
be the element of 
with the lowest positive degree 
in 
, let 
be the leading coefficient of 
in 
, and let 
be all elements of 
that do not depend on 
. 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 
strictly contains the ideal generated by 
, the Noetherian property of polynomial rings guarantees finiteness of the recursion.
If 
belongs to the radical of the ideal generated by 
, which is exactly when 1 belongs to
(3) is equivalent to False. Otherwise let
be the pseudoremainder of the division of 
by 
as polynomials in 
. Then (3) is equivalent to the quantifier-free system
To show that (3) implies (4), suppose that 
satisfies (3). Then 
and there exists 
, such that
Since 
and 
belong to the ideal generated by 
,
To show that (4) implies (3), suppose that 
satisfies (4). Then
Since 
is a polynomial of degree 
, and 
is a nonzero polynomial of degree less than 
, there is a root 
of 
such that 
divides 
but not 
for some 
. If 
were zero, then 
would divide 
, which is impossible because it would imply that 
divides 
. Therefore 
. Property 4 shows that 
for any polynomial 
. Since 
is a Gröbner basis of the ideal generated by 
,
which completes the proof of correctness of the quantifier elimination algorithm.
. Here 
, 
, and 
. Since 
is a nonzero constant, (2) is False and the equivalent quantifier-free system is given by (4). Since 
is a nonzero constant, (4) becomes 
: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 quantifier-free. Note that
has solutions if and only if 
has solutions, and if 
is a solution of 
, then 
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 quantifier-free systems. Moreover, 
is a solution of
if and only if it is a solution of one of the 
, with 
, so it is enough to show how to find instances of solutions of
First compute the GroebnerBasis 
of 
with MonomialOrder->EliminationOrder, eliminating the polynomials that depend on 
(if there is no inequation condition, 
is the GroebnerBasis of 
with MonomialOrder->DegreeReverseLexicographic). If 
contains 1, there are no solutions. Otherwise, compute a subset 
of 
of the highest cardinality among subsets strongly independent modulo the ideal generated by 
with respect to the degree reverse lexicographic order ([1], Section 9.3). Reorder 
so that 
, and compute the lexicographic order GroebnerBasis 
of the ideal generated by 
. To compute 
, the Wolfram Language uses the Gröbner walk algorithm.
For each of the variables 
, 
, select the polynomial 
with the smallest leading monomial among elements of 
that depend on 
and not on 
. Let 
be the leading coefficient of 
as a polynomial in 
. If 
depends on a variable that is not in 
, replace 
with the lexicographic order Gröbner basis of the ideal generated by 
and 
. The following shows that this operation keeps 
strongly independent modulo the ideal generated by 
. Hence, possibly after a finite (by the Noetherian property of polynomial rings) number of extensions of 
, the leading coefficient 
of 
depends only on 
, for all 
. For the set of polynomials 
, let 
be the set of common zeros of elements of 
. Both 
and 
have dimension 
, and 
, hence any 
-dimensional irreducible component of 
is also a component of 
. Since 
does not vanish on any irreducible component of 
, it does not vanish on any 
-dimensional irreducible component of 
. Therefore, the Gröbner basis of 
and 
contains a polynomial 
depending only on 
. Let 
. To find a solution of (2), pick its last 
coordinates 
so that 
. For all 
, 
, and so by Property 4 if 
, for 
, is chosen to be the first root of 
, then 
. Moreover, 
, because otherwise 
would belong to 
, which would imply that 
, which is impossible since 
divides 
.
To prove the correctness of the aforementioned algorithm, it must be shown that extending 
by 
that depend on a variable not in 
preserves strong independence of 
modulo the ideal generated by 
. Suppose for some 
, 
depends on a variable, which is not in 
. Let 
denote the ideal generated by 
, and let 
denote the ideal generated by 
and 
. Then 
does not contain nonzero elements of 
. To prove this, suppose that 
where 
and 
. Then 
, with 
, and
belongs to the ideal generated by 
, and so does 
. This contradicts the choice of 
since the leading monomial of 
depends on 
and is strictly smaller than the leading monomial of 
. Therefore, the projection of 
on 
is dense in 
, and so, since 
has dimension 
, 
must be zero on some irreducible component 
of 
whose projection on 
is dense in 
. Since 
is the Zariski closure of the projection of the 
-dimensional set 
, 
is contained in the Zariski closure of the projection of an irreducible component 
of 
. 
has dimension 
, hence 
is zero on 
, and the projection of 
on 
is dense in 
, which proves that 
is strongly independent modulo the ideal generated by 
and 
.
needs to be extended. Here 
, 
, 
, and 
. 
is zero on one of the two one-dimensional components of 
:
by 
results in all 
depending on 
only (in fact even constant) while preserving the strong independence of 
: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 quantifier-free 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 quantifier-free systems of the form
First compute the GroebnerBasis 
of 
with variable order 
and MonomialOrder->Lexicographic, and select the polynomials that do not depend on 
. Then the solution set of 
is equal to the solution set of (3) and 
does not vanish on any component of the zero set 
of 
. If 
contains 1, (3) has no solutions. Otherwise for each 
, such that the set 
of elements of 
depending on 
and not on any 
with 
is not empty, select an element 
of 
with the lowest positive degree in 
. If one of the leading coefficients 
of 
is zero on 
, that is, it belongs to the radical of the ideal generated by 
, replace 
by the lexicographic Gröbner basis of the ideal generated by 
and 
. 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 
is strictly contained in 
, so the recursion is finite. If the product of all the 
and 
belongs to the radical of the ideal generated by 
, the last term has no solutions. Otherwise, by Property 4, the solution set of the last term is equal to
The conditions 
guarantee that all the solutions (represented as radicals or Root objects) given by Roots[hij0,xij] 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 
, and removing factors that are nonzero on 
.
Options
Options for Reduce, Resolve, and FindInstance
The Wolfram Language 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.
option name | default value | |
| 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.
option name | default value | |
| 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.
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
SetSystemOptions["ReduceOptions"->{"option name"->value}].
option name | default value | |
| "AlgebraicNumberOutput" | True | whether Reduce should output AlgebraicNumber objects instead of polynomials in one Root object |
| "FinitePrecisionGB" | False | whether finite values of working precision should be used in calls to GroebnerBasis |
| "ReorderVariables" | Automatic | whether Reduce, Resolve, and Solve are allowed to reorder the specified variables |
| "UseNestedRoots" | Automatic | whether Root objects representing algebraic numbers defined by triangular systems of equations can be used in the output |
ReduceOptions group options that affect the behavior of Reduce, Resolve, and FindInstance for complex polynomial systems.
For systems with equational constraints generating a zero-dimensional ideal 
, the Wolfram Language uses a variant of the CAD algorithm that finds projection polynomials using Gröbner basis methods. If the lexicographic order Gröbner basis of 
contains linear polynomials with constant coefficients in every variable but the last one (which is true "generically"), then all coordinates of a solution are polynomials in one algebraic number, namely the last coordinate. The setting of AlgebraicNumberOutput determines whether Reduce represents the solution coordinates as AlgebraicNumber objects in the field generated by the last coordinate.
, if the input is exact GroebnerBasis uses exact computations:
first and express 
in terms of the solution for 
: