System of polynomial equations


A system of polynomial equations is a set of simultaneous equations where the are polynomials in several variables, say, over some field.
A solution of a polynomial system is a set of values for the s which belong to some algebraically closed field extension of, and make all equations true. When is the field of rational numbers, is generally assumed to be the field of complex numbers, because each solution belongs to a field extension of, which is isomorphic to a subfield of the complex numbers.
This article is about the methods for solving, that is, finding all solutions or describing them. As these methods are designed for being implemented in a computer, emphasis is given on fields in which computation is easy and efficient, that is the field of rational numbers and finite fields.
Searching for solutions that belong to a specific set is a problem which is generally much more difficult, and is outside the scope of this article, except for the case of the solutions in a given finite field. For the case of solutions of which all components are integers or rational numbers, see Diophantine equation.

Definition

A simple example of a system of polynomial equations is
Its solutions are the four pairs. These solutions can easily be checked by substitution, but more work is needed for proving that there are no other solutions.
The subject of this article is the study of generalizations of such an examples, and the description of the methods that are used for computing the solutions.
A system of polynomial equations, or polynomial system is a collection of equations
where each is a polynomial in the indeterminates, with integer coefficients, or coefficients in some fixed field, often the field of rational numbers or a finite field. Other fields of coefficients, such as the real numbers, are less often used, as their elements cannot be represented in a computer.
A solution of a polynomial system is a tuple of values of that satisfies all equations of the polynomial system. The solutions are sought in the complex numbers, or more generally in an algebraically closed field containing the coefficients. In particular, in characteristic zero, all complex solutions are sought. Searching for the real or rational solutions are much more difficult problems that are not considered in this article.
The set of solutions is not always finite; for example, the solutions of the system
are a point and a line. Even when the solution set is finite, there is, in general, no closed-form expression of the solutions.
The Barth surface, shown in the figure is the geometric representation of the solutions of a polynomial system reduced to a single equation of degree 6 in 3 variables. Some of its numerous singular points are visible on the image. They are the solutions of a system of 4 equations of degree 5 in 3 variables. Such an overdetermined system has no solution in general. If it has a finite number of solutions, this number is at most, by Bézout's theorem. However, it has been shown that, for the case of the singular points of a surface of degree 6, the maximum number of solutions is 65, and is reached by the Barth surface.

Basic properties and definitions

A system is overdetermined if the number of equations is higher than the number of variables. A system is inconsistent if it has no complex solution. By Hilbert's Nullstellensatz this means that 1 is a linear combination of the first members of the equations. Most but not all overdetermined systems, when constructed with random coefficients, are inconsistent. For example, the system is overdetermined, but it is not inconsistent since it has the solution.
A system is underdetermined if the number of equations is lower than the number of the variables. An underdetermined system is either inconsistent or has infinitely many complex solutions. This is a non-trivial result of commutative algebra that involves, in particular, Hilbert's Nullstellensatz and Krull's principal ideal theorem.
A system is zero-dimensional if it has a finite number of complex solutions. This terminology comes from the fact that the algebraic variety of the solutions has dimension zero. A system with infinitely many solutions is said to be positive-dimensional.
A zero-dimensional system with as many equations as variables is sometimes said to be well-behaved.
Bézout's theorem asserts that a well-behaved system whose equations have degrees has at most solutions. This bound is sharp. If all the degrees are equal to, this bound becomes and is exponential in the number of variables.
This exponential behavior makes solving polynomial systems difficult and explains why there are few solvers that are able to automatically solve systems with Bézout's bound higher than, say, 25.

What is solving?

The first thing to do for solving a polynomial system is to decide whether it is inconsistent, zero-dimensional or positive dimensional. This may be done by the computation of a Gröbner basis of the left-hand sides of the equations. The system is inconsistent if this Gröbner basis is reduced to 1. The system is zero-dimensional if, for every variable there is a leading monomial of some element of the Gröbner basis which is a pure power of this variable. For this test, the best monomial order is usually the graded reverse lexicographic one.
If the system is positive-dimensional, it has infinitely many solutions. It is thus not possible to enumerate them. It follows that, in this case, solving may only mean "finding a description of the solutions from which the relevant properties of the solutions are easy to extract". There is no commonly accepted such description. In fact there are many different "relevant properties", which involve almost every subfield of algebraic geometry.
A natural example of such a question concerning positive-dimensional systems is the following: decide if a polynomial system over the rational numbers has a finite number of real solutions and compute them. A generalization of this question is find at least one solution in each connected component of the set of real solutions of a polynomial system. The classical algorithm for solving these question is cylindrical algebraic decomposition, which has a doubly exponential computational complexity and therefore cannot be used in practice, except for very small examples.
For zero-dimensional systems, solving consists of computing all the solutions. There are two different ways of outputting the solutions. The most common way is possible only for real or complex solutions, and consists of outputting numeric approximations of the solutions. Such a solution is called numeric. A solution is certified if it is provided with a bound on the error of the approximations, and if this bound separates the different solutions.
The other way of representing the solutions is said to be algebraic. It uses the fact that, for a zero-dimensional system, the solutions belong to the algebraic closure of the field k of the coefficients of the system. There are several ways to represent the solution in an algebraic closure, which are discussed below. All of them allow one to compute a numerical approximation of the solutions by solving one or several univariate equations. For this computation, it is preferable to use a representation that involves solving only one univariate polynomial per solution, because computing the roots of a polynomial which has approximate coefficients is a highly unstable problem.

Extensions

Trigonometric equations

A trigonometric equation is an equation where is a trigonometric polynomial. Such an equation may be converted into a polynomial system by expanding the sines and cosines in it, replacing and by two new variables and and adding the new equation.
For example, because of the identity
solving the equation
is equivalent to solving the polynomial system
For each solution of this system, there is a unique solution of the equation such that.
In the case of this simple example, it may be unclear whether the system is, or not, easier to solve than the equation. On more complicated examples, one lacks systematic methods for solving directly the equation, while software are available for automatically solving the corresponding system.

Solutions in a finite field

When solving a system over a finite field with elements, one is primarily interested in the solutions in. As the elements of are exactly the solutions of the equation, it suffices, for restricting the solutions to, to add the equation for each variable .

Coefficients in a number field or in a finite field with non-prime order

The elements of an algebraic number field are usually represented as polynomials in a generator of the field which satisfies some univariate polynomial equation. To work with a polynomial system whose coefficients belong to a number field, it suffices to consider this generator as a new variable and to add the equation of the generator to the equations of the system. Thus solving a polynomial system over a number field is reduced to solving another system over the rational numbers.
For example, if a system contains, a system over the rational numbers is obtained by adding the equation and replacing by in the other equations.
In the case of a finite field, the same transformation allows always supposing that the field has a prime order.

Algebraic representation of the solutions

Regular chains

The usual way of representing the solutions is through zero-dimensional regular chains. Such a chain consists of a sequence of polynomials,,..., such that, for every such that
  • is a polynomial in only, which has a degree in ;
  • the coefficient of in is a polynomial in which does not have any common zero with,...,.
To such a regular chain is associated a triangular system of equations
The solutions of this system are obtained by solving the first univariate equation, substituting the solutions in the other equations, then solving the second equation which is now univariate, and so on. The definition of regular chains implies that the univariate equation obtained from has degree and thus that the system has solutions, provided that there is no multiple root in this resolution process.
Every zero-dimensional system of polynomial equations is equivalent to a finite number of regular chains. Several regular chains may be needed, as it is the case for the following system which has three solutions.
There are several algorithms for computing a triangular decomposition of an arbitrary polynomial system into regular chains.
There is also an algorithm which is specific to the zero-dimensional case and is competitive, in this case, with the direct algorithms. It consists in computing first the Gröbner basis for the graded reverse lexicographic order, then deducing the lexicographical Gröbner basis by FGLM algorithm and finally applying the Lextriangular algorithm.
This representation of the solutions are fully convenient for coefficients in a finite field. However, for rational coefficients, two aspects have to be taken care of:
  • The output may involve huge integers which may make the computation and the use of the result problematic.
  • To deduce the numeric values of the solutions from the output, one has to solve univariate polynomials with approximate coefficients, which is a highly unstable problem.
The first issue has been solved by Dahan and Schost: Among the sets of regular chains that represent a given set of solutions, there is a set for which the coefficients are explicitly bounded in terms of the size of the input system, with a nearly optimal bound. This set, called equiprojectable decomposition, depends only on the choice of the coordinates. This allows the use of modular methods for computing efficiently the equiprojectable decomposition.
The second issue is generally solved by outputting regular chains of a special form, sometimes called shape lemma, for which all but the first one are equal to. For getting such regular chains, one may have to add a further variable, called separating variable, which is given the index. The rational univariate representation, described below, allows computing such a special regular chain, satisfying Dahan–Schost bound, by starting from either a regular chain or a Gröbner basis.