Zeros of simultaneous polynomials

Sphere and slanted circle

In classical algebraic geometry, the main objects of interest are the vanishing sets of collections of polynomials, meaning the set of all points that simultaneously satisfy one or more polynomial equations. For instance, the two-dimensional sphere of radius 1 in three-dimensional Euclidean space R³ could be defined as the set of all points (x,y,z) with

${\displaystyle x^{2}+y^{2}+z^{2}-1=0.\,}$

A "slanted" circle in R³ can be defined as the set of all points (x,y,z) which satisfy the two polynomial equations

${\displaystyle x^{2}+y^{2}+z^{2}-1=0,\,}$

${\displaystyle x+y+z=0.\,}$

Affine varieties

First we start with a field k. In classical algebraic geometry, this field was always the complex numbers C, but many of the same results are true if we assume only that k is algebraically closed. We consider the affine space of dimension n over k, denoted Aⁿ(k) (or more simply Aⁿ, when k is clear from the context). When one fixes a coordinate system, one may identify Aⁿ(k) with kⁿ. The purpose of not working with kⁿ is to emphasize that one "forgets" the vector space structure that kⁿ carries.

A function f : Aⁿ → A¹ is said to be polynomial (or regular) if it can be written as a polynomial, that is, if there is a polynomial p in k[x₁,...,x_n] such that f(M) = p(t₁,...,t_n) for every point M with coordinates (t₁,...,t_n) in Aⁿ. The property of a function to be polynomial (or regular) does not depend on the choice of a coordinate system in Aⁿ.

When a coordinate system is chosen, the regular functions on the affine n-space may be identified with the ring of polynomial functions in n variables over k. Therefore, the set of the regular functions on Aⁿ is a ring, which is denoted k[Aⁿ].

We say that a polynomial vanishes at a point if evaluating it at that point gives zero. Let S be a set of polynomials in k[Aⁿ]. The vanishing set of S (or vanishing locus or zero set) is the set V(S) of all points in Aⁿ where every polynomial in S vanishes. Symbolically,

${\displaystyle V(S)=\{(t_{1},\dots ,t_{n})\mid p(t_{1},\dots ,t_{n})=0{\text{ for all }}p\in S\}.\,}$

A subset of Aⁿ which is V(S), for some S, is called an algebraic set. The V stands for variety (a specific type of algebraic set to be defined below).

Given a subset U of Aⁿ, can one recover the set of polynomials which generate it? If U is any subset of Aⁿ, define I(U) to be the set of all polynomials whose vanishing set contains U. The I stands for ideal: if two polynomials f and g both vanish on U, then f+g vanishes on U, and if h is any polynomial, then hf vanishes on U, so I(U) is always an ideal of the polynomial ring k[Aⁿ].

Two natural questions to ask are:

• Given a subset U of Aⁿ, when is U = V(I(U))?
• Given a set S of polynomials, when is S = I(V(S))?

The answer to the first question is provided by introducing the Zariski topology, a topology on Aⁿ whose closed sets are the algebraic sets, and which directly reflects the algebraic structure of k[Aⁿ]. Then U = V(I(U)) if and only if U is an algebraic set or equivalently a Zariski-closed set. The answer to the second question is given by Hilbert's Nullstellensatz. In one of its forms, it says that I(V(S)) is the radical of the ideal generated by S. In more abstract language, there is a Galois connection, giving rise to two closure operators; they can be identified, and naturally play a basic role in the theory; the example is elaborated at Galois connection.

For various reasons we may not always want to work with the entire ideal corresponding to an algebraic set U. Hilbert's basis theorem implies that ideals in k[Aⁿ] are always finitely generated.

An algebraic set is called irreducible if it cannot be written as the union of two smaller algebraic sets. Any algebraic set is a finite union of irreducible algebraic sets and this decomposition is unique. Thus its elements are called the irreducible components of the algebraic set. An irreducible algebraic set is also called a variety. It turns out that an algebraic set is a variety if and only if it may be defined as the vanishing set of a prime ideal of the polynomial ring.

Some authors do not make a clear distinction between algebraic sets and varieties and use irreducible variety to make the distinction when needed.

Regular functions

Just as continuous functions are the natural maps on topological spaces and smooth functions are the natural maps on differentiable manifolds, there is a natural class of functions on an algebraic set, called regular functions or polynomial functions. A regular function on an algebraic set V contained in Aⁿ is the restriction to V of a regular function on Aⁿ. For an algebraic set defined on the field of the complex numbers, the regular functions are smooth and even analytic.

It may seem unnaturally restrictive to require that a regular function always extend to the ambient space, but it is very similar to the situation in a normal topological space, where the Tietze extension theorem guarantees that a continuous function on a closed subset always extends to the ambient topological space.

Just as with the regular functions on affine space, the regular functions on V form a ring, which we denote by k[V]. This ring is called the coordinate ring of V.

Since regular functions on V come from regular functions on Aⁿ, there is a relationship between the coordinate rings. Specifically, if a regular function on V is the restriction of two functions f and g in k[Aⁿ], then f − g is a polynomial function which is null on V and thus belongs to I(V). Thus k[V] may be identified with k[Aⁿ]/I(V).

Morphism of affine varieties

Using regular functions from an affine variety to A¹, we can define regular maps from one affine variety to another. First we will define a regular map from a variety into affine space: Let V be a variety contained in Aⁿ. Choose m regular functions on V, and call them f₁, ..., f_m. We define a regular map f from V to A^m by letting f = (f₁, ..., f_m). In other words, each f_i determines one coordinate of the range of f.

If V′ is a variety contained in A^m, we say that f is a regular map from V to V′ if the range of f is contained in V′.

The definition of the regular maps apply also to algebraic sets. The regular maps are also called morphisms, as they make the collection of all affine algebraic sets into a category, where the objects are the affine algebraic sets and the morphisms are the regular maps. The affine varieties is a subcategory of the category of the algebraic sets.

Given a regular map g from V to V′ and a regular function f of k[V′], then f ∘ g ∈ k[V]. The map f → f ∘ g is a ring homomorphism from k[V′] to k[V]. Conversely, every ring homomorphism from k[V′] to k[V] defines a regular map from V to V′. This defines an equivalence of categories between the category of algebraic sets and the opposite category of the finitely generated reduced k-algebras. This equivalence is one of the starting points of scheme theory.

Rational function and birational equivalence

In contrast to the preceding sections, this section concerns only varieties and not algebraic sets. On the other hand, the definitions extend naturally to projective varieties (next section), as an affine variety and its projective completion have the same field of functions.

If V is an affine variety, its coordinate ring is an integral domain and has thus a field of fractions which is denoted k(V) and called the field of the rational functions on V or, shortly, the function field of V. Its elements are the restrictions to V of the rational functions over the affine space containing V. The domain of a rational function f is not V but the complement of the subvariety (a hypersurface) where the denominator of f vanishes.

As with regular maps, one may define a rational map from a variety V to a variety V'. As with the regular maps, the rational maps from V to V' may be identified to the field homomorphisms from k(V') to k(V).

Two affine varieties are birationally equivalent if there are two rational functions between them which are inverse one to the other in the regions where both are defined. Equivalently, they are birationally equivalent if their function fields are isomorphic.

An affine variety is a rational variety if it is birationally equivalent to an affine space. This means that the variety admits a rational parameterization, that is a parametrization with rational functions. For example, the circle of equation ${\displaystyle x^{2}+y^{2}-1=0}$ is a rational curve, as it has the parametric equation

${\displaystyle x={\frac {2\,t}{1+t^{2}}}}$

${\displaystyle y={\frac {1-t^{2}}{1+t^{2}}}\,,}$

which may also be viewed as a rational map from the line to the circle.

The problem of resolution of singularities is to know if every algebraic variety is birationally equivalent to a variety whose projective completion is nonsingular (see also smooth completion). It was solved in the affirmative in characteristic 0 by Heisuke Hironaka in 1964 and is yet unsolved in finite characteristic.

Projective variety

Parabola (y = x², red) and cubic (y = x³, blue) in projective space

Just as the formulas for the roots of second, third, and fourth degree polynomials suggest extending real numbers to the more algebraically complete setting of the complex numbers, many properties of algebraic varieties suggest extending affine space to a more geometrically complete projective space. Whereas the complex numbers are obtained by adding the number i, a root of the polynomial x² + 1, projective space is obtained by adding in appropriate points "at infinity", points where parallel lines may meet.

To see how this might come about, consider the variety V(y − x²). If we draw it, we get a parabola. As x goes to positive infinity, the slope of the line from the origin to the point (x, x²) also goes to positive infinity. As x goes to negative infinity, the slope of the same line goes to negative infinity.

Compare this to the variety V(y − x³). This is a cubic curve. As x goes to positive infinity, the slope of the line from the origin to the point (x, x³) goes to positive infinity just as before. But unlike before, as x goes to negative infinity, the slope of the same line goes to positive infinity as well; the exact opposite of the parabola. So the behavior "at infinity" of V(y − x³) is different from the behavior "at infinity" of V(y − x²).

The consideration of the projective completion of the two curves, which is their prolongation "at infinity" in the projective plane, allows us to quantify this difference: the point at infinity of the parabola is a regular point, whose tangent is the line at infinity, while the point at infinity of the cubic curve is a cusp. Also, both curves are rational, as they are parameterized by x, and the Riemann-Roch theorem implies that the cubic curve must have a singularity, which must be at infinity, as all its points in the affine space are regular.

Thus many of the properties of algebraic varieties, including birational equivalence and all the topological properties, depend on the behavior "at infinity" and so it is natural to study the varieties in projective space. Furthermore, the introduction of projective techniques made many theorems in algebraic geometry simpler and sharper: For example, Bézout's theorem on the number of intersection points between two varieties can be stated in its sharpest form only in projective space. For these reasons, projective space plays a fundamental role in algebraic geometry.

Nowadays, the projective space Pⁿ of dimension n is usually defined as the set of the lines passing through a point, considered as the origin, in the affine space of dimension n + 1, or equivalently to the set of the vector lines in a vector space of dimension n + 1. When a coordinate system has been chosen in the space of dimension n + 1, all the points of a line have the same set of coordinates, up to the multiplication by an element of k. This defines the homogeneous coordinates of a point of Pⁿ as a sequence of n + 1 elements of the base field k, defined up to the multiplication by a nonzero element of k (the same for the whole sequence).

A polynomial in n + 1 variables vanishes at all points of a line passing through the origin if and only if it is homogeneous. In this case, one says that the polynomial vanishes at the corresponding point of Pⁿ. This allows us to define a projective algebraic set in Pⁿ as the set V(f₁, ..., f_k), where a finite set of homogeneous polynomials {f₁, ..., f_k} vanishes. Like for affine algebraic sets, there is a bijection between the projective algebraic sets and the reduced homogeneous ideals which define them. The projective varieties are the projective algebraic sets whose defining ideal is prime. In other words, a projective variety is a projective algebraic set, whose homogeneous coordinate ring is an integral domain, the projective coordinates ring being defined as the quotient of the graded ring or the polynomials in n + 1 variables by the homogeneous (reduced) ideal defining the variety. Every projective algebraic set may be uniquely decomposed into a finite union of projective varieties.

The only regular functions which may be defined properly on a projective variety are the constant functions. Thus this notion is not used in projective situations. On the other hand, the field of the rational functions or function field is a useful notion, which, similarly to the affine case, is defined as the set of the quotients of two homogeneous elements of the same degree in the homogeneous coordinate ring.

Gröbner basis

A Gröbner basis is a system of generators of a polynomial ideal whose computation allows the deduction of many properties of the affine algebraic variety defined by the ideal.

Given an ideal I defining an algebraic set V:

• V is empty (over an algebraically closed extension of the basis field), if and only if the Gröbner basis for any monomial ordering is reduced to {1}.
• By means of the Hilbert series one may compute the dimension and the degree of V from any Gröbner basis of I for a monomial ordering refining the total degree.
• If the dimension of V is 0, one may compute the points (finite in number) of V from any Gröbner basis of I (see Systems of polynomial equations).
• A Gröbner basis computation allows one to remove from V all irreducible components which are contained in a given hypersurface.
• A Gröbner basis computation allows one to compute the Zariski closure of the image of V by the projection on the k first coordinates, and the subset of the image where the projection is not proper.
• More generally Gröbner basis computations allow one to compute the Zariski closure of the image and the critical points of a rational function of V into another affine variety.

Gröbner basis computations do not allow one to compute directly the primary decomposition of I nor the prime ideals defining the irreducible components of V, but most algorithms for this involve Gröbner basis computation. The algorithms which are not based on Gröbner bases use regular chains but may need Gröbner bases in some exceptional situations.

Gröbner bases are deemed to be difficult to compute. In fact they may contain, in the worst case, polynomials whose degree is doubly exponential in the number of variables and a number of polynomials which is also doubly exponential. However, this is only a worst case complexity, and the complexity bound of Lazard's algorithm of 1979 may frequently apply. Faugère F5 algorithm realizes this complexity, as it may be viewed as an improvement of Lazard's 1979 algorithm. It follows that the best implementations allow one to compute almost routinely with algebraic sets of degree more than 100. This means that, presently, the difficulty of computing a Gröbner basis is strongly related to the intrinsic difficulty of the problem.

Cylindrical algebraic decomposition (CAD)

CAD is an algorithm which was introduced in 1973 by G. Collins to implement with an acceptable complexity the Tarski–Seidenberg theorem on quantifier elimination over the real numbers.

This theorem concerns the formulas of the first-order logic whose atomic formulas are polynomial equalities or inequalities between polynomials with real coefficients. These formulas are thus the formulas which may be constructed from the atomic formulas by the logical operators and (∧), or (∨), not (¬), for all (∀) and exists (∃). Tarski's theorem asserts that, from such a formula, one may compute an equivalent formula without quantifier (∀, ∃).

The complexity of CAD is doubly exponential in the number of variables. This means that CAD allows, in theory, to solve every problem of real algebraic geometry which may be expressed by such a formula, that is almost every problem concerning explicitly given varieties and semi-algebraic sets.

While Gröbner basis computation has doubly exponential complexity only in rare cases, CAD has almost always this high complexity. This implies that, unless if most polynomials appearing in the input are linear, it may not solve problems with more than four variables.

Since 1973, most of the research on this subject is devoted either to improving CAD or finding alternative algorithms in special cases of general interest.

As an example of the state of art, there are efficient algorithms to find at least a point in every connected component of a semi-algebraic set, and thus to test if a semi-algebraic set is empty. On the other hand, CAD is yet, in practice, the best algorithm to count the number of connected components.

Asymptotic complexity vs. practical efficiency

The basic general algorithms of computational geometry have a double exponential worst case complexity. More precisely, if d is the maximal degree of the input polynomials and n the number of variables, their complexity is at most ${\displaystyle d^{2^{cn}}}$ for some constant c, and, for some inputs, the complexity is at least ${\displaystyle d^{2^{c'n}}}$ for another constant c′.

During the last 20 years of the 20th century, various algorithms have been introduced to solve specific subproblems with a better complexity. Most of these algorithms have a complexity ${\displaystyle d^{O(n^{2})}}$.^[1]

Among these algorithms which solve a sub problem of the problems solved by Gröbner bases, one may cite testing if an affine variety is empty and solving nonhomogeneous polynomial systems which have a finite number of solutions. Such algorithms are rarely implemented because, on most entries Faugère's F4 and F5 algorithms have a better practical efficiency and probably a similar or better complexity (probably because the evaluation of the complexity of Gröbner basis algorithms on a particular class of entries is a difficult task which has been done only in a few special cases).

The main algorithms of real algebraic geometry which solve a problem solved by CAD are related to the topology of semi-algebraic sets. One may cite counting the number of connected components, testing if two points are in the same components or computing a Whitney stratification of a real algebraic set. They have a complexity of ${\displaystyle d^{O(n^{2})}}$, but the constant involved by O notation is so high that using them to solve any nontrivial problem effectively solved by CAD, is impossible even if one could use all the existing computing power in the world. Therefore, these algorithms have never been implemented and this is an active research area to search for algorithms with have together a good asymptotic complexity and a good practical efficiency.

Before the 16th century

Some of the roots of algebraic geometry date back to the work of the Hellenistic Greeks from the 5th century BC. The Delian problem, for instance, was to construct a length x so that the cube of side x contained the same volume as the rectangular box a²b for given sides a and b. Menaechmus (c. 350 BC) considered the problem geometrically by intersecting the pair of plane conics ay = x² and xy = ab.^[2] In the 3rd century BC, Archimedes and Apollonius systematically studied additional problems on conic sections using coordinates.^[2][3] Apollonius in the Conics further developed a method that is so similar to analytic geometry that his work is sometimes thought to have anticipated the work of Descartes by some 1800 years.^[4] His application of reference lines, a diameter and a tangent is essentially no different from our modern use of a coordinate frame, where the distances measured along the diameter from the point of tangency are the abscissas, and the segments parallel to the tangent and intercepted between the axis and the curve are the ordinates. He further developed relations between the abscissas and the corresponding coordinates using geometric methods like using parabolas and curves.^[5][6][7] Medieval mathematicians, including Omar Khayyam, Leonardo of Pisa, Gersonides and Nicole Oresme in the Medieval Period ,^[8] solved certain cubic and quadratic equations by purely algebraic means and then interpreted the results geometrically. The Persian mathematician Omar Khayyám (born 1048 AD) believed that there was a relationship between arithmetic, algebra and geometry.^[9][10][11] This was criticized by Jeffrey Oaks, who claims that the study of curves by means of equations originated with Descartes in the seventeenth century.^[12]

Renaissance

Such techniques of applying geometrical constructions to algebraic problems were also adopted by a number of Renaissance mathematicians such as Gerolamo Cardano and Niccolò Fontana "Tartaglia" on their studies of the cubic equation. The geometrical approach to construction problems, rather than the algebraic one, was favored by most 16th and 17th century mathematicians, notably Blaise Pascal who argued against the use of algebraic and analytical methods in geometry.^[13] The French mathematicians Franciscus Vieta and later René Descartes and Pierre de Fermat revolutionized the conventional way of thinking about construction problems through the introduction of coordinate geometry. They were interested primarily in the properties of algebraic curves, such as those defined by Diophantine equations (in the case of Fermat), and the algebraic reformulation of the classical Greek works on conics and cubics (in the case of Descartes).

During the same period, Blaise Pascal and Gérard Desargues approached geometry from a different perspective, developing the synthetic notions of projective geometry. Pascal and Desargues also studied curves, but from the purely geometrical point of view: the analog of the Greek ruler and compass construction. Ultimately, the analytic geometry of Descartes and Fermat won out, for it supplied the 18th century mathematicians with concrete quantitative tools needed to study physical problems using the new calculus of Newton and Leibniz. However, by the end of the 18th century, most of the algebraic character of coordinate geometry was subsumed by the calculus of infinitesimals of Lagrange and Euler.

19th and early 20th century

It took the simultaneous 19th century developments of non-Euclidean geometry and Abelian integrals in order to bring the old algebraic ideas back into the geometrical fold. The first of these new developments was seized up by Edmond Laguerre and Arthur Cayley, who attempted to ascertain the generalized metric properties of projective space. Cayley introduced the idea of homogeneous polynomial forms, and more specifically quadratic forms, on projective space. Subsequently, Felix Klein studied projective geometry (along with other types of geometry) from the viewpoint that the geometry on a space is encoded in a certain class of transformations on the space. By the end of the 19th century, projective geometers were studying more general kinds of transformations on figures in projective space. Rather than the projective linear transformations which were normally regarded as giving the fundamental Kleinian geometry on projective space, they concerned themselves also with the higher degree birational transformations. This weaker notion of congruence would later lead members of the 20th century Italian school of algebraic geometry to classify algebraic surfaces up to birational isomorphism.

The second early 19th century development, that of Abelian integrals, would lead Bernhard Riemann to the development of Riemann surfaces.

In the same period began the algebraization of the algebraic geometry through commutative algebra. The prominent results in this direction are Hilbert's basis theorem and Hilbert's Nullstellensatz, which are the basis of the connection between algebraic geometry and commutative algebra, and Macaulay's multivariate resultant, which is the basis of elimination theory. Probably because of the size of the computation which is implied by multivariate resultants, elimination theory was forgotten during the middle of the 20th century until it was renewed by singularity theory and computational algebraic geometry.^{[lower-alpha 1]}

20th century

B. L. van der Waerden, Oscar Zariski and André Weil developed a foundation for algebraic geometry based on contemporary commutative algebra, including valuation theory and the theory of ideals. One of the goals was to give a rigorous framework for proving the results of the Italian school of algebraic geometry. In particular, this school used systematically the notion of generic point without any precise definition, which was first given by these authors during the 1930s.

In the 1950s and 1960s, Jean-Pierre Serre and Alexander Grothendieck recast the foundations making use of sheaf theory. Later, from about 1960, and largely led by Grothendieck, the idea of schemes was worked out, in conjunction with a very refined apparatus of homological techniques. After a decade of rapid development the field stabilized in the 1970s, and new applications were made, both to number theory and to more classical geometric questions on algebraic varieties, singularities, moduli, and formal moduli.

An important class of varieties, not easily understood directly from their defining equations, are the abelian varieties, which are the projective varieties whose points form an abelian group. The prototypical examples are the elliptic curves, which have a rich theory. They were instrumental in the proof of Fermat's Last Theorem and are also used in elliptic-curve cryptography.

In parallel with the abstract trend of the algebraic geometry, which is concerned with general statements about varieties, methods for effective computation with concretely-given varieties have also been developed, which lead to the new area of computational algebraic geometry. One of the founding methods of this area is the theory of Gröbner bases, introduced by Bruno Buchberger in 1965. Another founding method, more specially devoted to real algebraic geometry, is the cylindrical algebraic decomposition, introduced by George E. Collins in 1973.

See also: derived algebraic geometry.

Sources

• Kline, M. (1972). Mathematical Thought from Ancient to Modern Times. Vol. 1. Oxford University Press. ISBN 0195061357.