Elimination theory


In commutative algebra and algebraic geometry, elimination theory is the classical name for algorithmic approaches to eliminating some variables between polynomials of several variables, in order to solve systems of polynomial equations.
The classical elimination theory culminated with the work of Macaulay on multivariate resultants, and its description in chapter Elimination theory of the first editions of van der Waerden's Moderne Algebra. After that, elimination theory was ignored by most algebraic geometers for almost thirty years, until the introduction of new methods for solving polynomial equations, such as Gröbner bases, which were needed for computer algebra.

History and connection to modern theories

The field of elimination theory was motivated by the need of methods for solving systems of polynomial equations.
One of the first results was Bézout's theorem, which bounds the number of solutions.
Except for Bézout's theorem, the general approach was to eliminate variables for reducing the problem to a single equation in one variable.
The case of linear equations was completely solved by Gaussian elimination, where the older method of Cramer's rule does not proceed by elimination, and works only when the number of equations equals the number of variables. During 19th century, this has been extended to linear Diophantine equations and abelian group with Hermite normal form and Smith normal form.
Before 20th century, different types of eliminants were introduced, including resultants, and various kinds of discriminants. In general, these eliminants are also invariant, and are also fundamental in invariant theory.
All these concepts are effective, in the sense that their definition include a method of computation. Around 1890, David Hilbert introduced non-effective methods, and this was seen as a revolution, which led most algebraic-geometers of the first half of 20th century to try to "eliminate elimination". Nevertheless Hilbert's Nullstellensatz, may be considered to belong to elimination theory, as it asserts that a system of polynomial equations does not have any solution if and only one may eliminate all unknowns for getting 1.
Elimination theory culminated with the work of Kronecker, and, finally, F.S. Macaulay, who introduced multivariate resultants and U-resultants, providing complete elimination methods for systems of polynomial equations, which have been described in chapter Elimination theory of the first editions of van der Waerden's Moderne Algebra.
After that, elimination theory has been considered as old fashioned, removed from next editions of Moderne Algebra, and generally ignored, until the introduction of computers, and more specifically of computer algebra, which set the problem of designing elimination algorithms that are sufficiently efficient for being implemented. The main methods for this renewing of elimination theory are Gröbner bases and cylindrical algebraic decomposition, which were introduced around 1970.

Connection to logic

There is also a logical facet to elimination theory, as seen in the Boolean satisfiability problem. In the worst case, it is presumably hard to eliminate variables computationally. Quantifier elimination is a term used in mathematical logic to explain that, in some theories, every formula is equivalent to a formula without quantifier. This is the case of the theory of polynomials over an algebraically closed field, where elimination theory may be viewed as the theory of the methods to make quantifier elimination algorithmically effective. Quantifier elimination over the reals is another example, which is fundamental in computational algebraic geometry.