Editing Elimination theory

{{short description|Part of algebraic geometry devoted to the elimination of variables between polynomials}}
In [[commutative algebra]] and [[algebraic geometry]], '''elimination theory''' is the classical name for algorithmic approaches to eliminating some variables between [[polynomial]]s of several variables, in order to solve [[systems of polynomial equations]].

Classical elimination theory culminated with the work of [[Francis Sowerby Macaulay|Francis Macaulay]] on [[multivariate resultant]]s, as described in the chapter on ''Elimination theory'' in the first editions (1930) of [[Bartel Leendert van der Waerden|Bartel 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 (in the case of two polynomials in two variables at Bézout time).

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. In the 19th century, this was extended to linear [[Diophantine equation]]s and [[abelian group]] with [[Hermite normal form]] and [[Smith normal form]].

Before the 20th century, different types of ''eliminants'' were introduced, including ''[[resultant]]s'', and various kinds of ''[[discriminant]]s''. In general, these eliminants are also [[invariant theory|invariant]] under various changes of variables, and are also fundamental in [[invariant theory]].

All these concepts are effective, in the sense that their definitions 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 the 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 if one may eliminate all unknowns to obtain the constant equation 1 = 0.

Elimination theory culminated with the work of [[Leopold Kronecker]], and finally  [[Francis Sowerby Macaulay|Macaulay]], who introduced [[multivariate resultant]]s and [[Resultant#U-resultant|U-resultants]], providing complete elimination methods for systems of polynomial equations, which are described in the chapter on ''Elimination theory'' in the first editions (1930) of [[Bartel Leendert van der Waerden|van der Waerden's]] ''[[Moderne Algebra]]''.

Later, elimination theory was considered old-fashioned and removed from subsequent editions of ''Moderne Algebra''. It was generally ignored until the introduction of [[computer]]s, and more specifically of [[computer algebra]], which again made relevant the design of efficient elimination algorithms, rather than merely existence and structural results. The main methods for this renewal of elimination theory are [[Gröbner bases]] and [[cylindrical algebraic decomposition]], 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 [[polynomial]]s over an [[algebraically closed field]], where elimination theory may be viewed as the theory of the methods to make quantifier elimination algorithmically effective. [[Tarski–Seidenberg theorem|Quantifier elimination over the reals]] is another example, which is fundamental in [[algebraic geometry#Computational algebraic geometry|computational algebraic geometry]].

== See also ==
* [[Buchberger's algorithm]]
* [[Faugère's F4 and F5 algorithms]]
* [[Resultant]]
* [[Triangular decomposition]]
* [[Main theorem of elimination theory]]

== References ==
* [[Israel Gelfand]], Mikhail Kapranov, [[Andrey Zelevinsky]], ''Discriminants, resultants, and multidimensional determinants''. Mathematics: Theory & Applications. Birkhäuser Boston, Inc., Boston, MA, 1994. x+523 pp. {{ISBN|0-8176-3660-9}} 
* {{Lang Algebra}}
* David Cox, John  Little, Donal O'Shea, ''Using Algebraic Geometry''. Revised second edition. [[Graduate Texts in Mathematics]], vol. 185. [[Springer-Verlag]], 2005, xii+558 pp., {{ISBN|978-0-387-20733-9}}

[[Category:Algebraic geometry]]
[[Category:Computer algebra]]