Effective Methods in Algebraic Geometry

It is a fact and a motivation of this meeting, that many interesting constructions in semi-algebraic geometry can be effectively done, that is, roughly speaking, by means of algorithms with computably bounded complexity. It is also a fact that semi-algebraic objects have some effective finiteness properties. Hence the interest in finding reasonably ”fast” algorithms or “sharp” bounds. Neverthless, on the other side of the mainstream, one can be interested in essential lack of effectiveness or finiteness. We are going to see some examples and to discuss shortly some possible basic sources of such a lack.

In these notes, we describe some of the main features of an explicit proof of canonical desingularization (of algebraic varieties or analytic spaces X) in characteristic zero. Full details will appear in [7]. The proof is a variation on our proof of local desingularization (“uniformization”) [4], [5], and justifies the philosophy that “a sufficiently good local choice [of centre of blowing-up] should globalize automatically” [5, p. 901]. The final version is surprisingly elementary; these notes, for example, include an essentially self-contained presentation of the hypersurface case. The general case involves a “reduction to the hypersurface case” result from [5].

Let K be a field, R:= K[X] the ring of polynomials in the indeterminates X₁,…, X _n over K and J an ideal of R. In this work we consider the following Localization Problem (LP): Given f, f₁, …, f _t ∈ R,

We here give a method to calculate the resultant of three polynomials in terms of a square-free decomposition and resultants of two polynomials. After that, we show how the subresultant algorithm enables us to avoid many calculations.In the last part, we study the possible extension to the general case of n homogeneous polynomials in n variables.

During the last years several researchers have considered the problem of finding polynomial-time sequential algorithms for the computation of the topology of a real algebraic plane curve. Up till now, we can divide these algorithms into two main groups: those coding real algebraic numbers by means of isolating intervals (see for instance [3] and [7]) and those coding them à la Thom (see [9]). The aim of this note is to survey the state of the art as far as the second group is concerned. In particular we introduce two new such algorithms, one of which is, to our knowledge, the algorithm computing the topology of a real algebraic plane curve with the lowest running time, while the other one has been successfully implemented.

The classical problem of deciding membership to arbitrary polynomial ideals is EXPSPACE complete. Moreover, the problem of finding a representation of a polynomial by generators of a given ideal may involve doubly exponential (in the number of variables) degrees ([16]). The same difficulty arises when computing Gröebner bases of arbitrary polynomial ideals ([11]). This means that all known techniques to decide membership and to find representations of polynomials with respect to a given ideal lead to doubly exponential (sequential time) worst case complexities. However, if the geometry of the underlying algebraic variety is particularly simple, e.g. if the given ideal is zero dimensional or complete intersection, algorithms of considerably lower complexity can be found (see e.g. [7], [9]). The improvements are due to recent progress concerning affine versions of the effective Nullstellensatz (compare [18] and the references given there).

Un ensemble E de n points d’un espace affine, dont les équations forment un idéal de polynômes de colongueur n, est en position uniforme si pour tout sous-ensemble de n′ points E′ de E la fonction de Hilbert de E′ ne dépend que de n′.

The concept of a characteristic set of an ideal was originally introduced by J.F. Ritt, in the late forties, and later, independently rediscovered by Wu Wen-Tsiin, in the late seventies. Since then Wu-Ritt Characteristic Sets have found wide applications in Symbolic Computational Algebra, Automated Theorem Proving in Elementary Geometries and Computer Vision. The original algorithm of Ritt, and subsequent modifications by Wu, has a non-elementary worst-case time complexity, and could be used for computing only an extended characteristic set. In this paper, we present optimal algorithms for computing a characteristic set with simple-exponential sequential and polynomial parallel time complexities. These algorithms are derived, via linear algebra, from simple-exponential degree bounds for a characteristic set. The degree bounds are obtained by using the recent effective version of Hilbert’s Nullstellensatz, due to D. Brownawell and J. Kollár, and a version of Bezout’s Inequality, due to J. Heintz.

We consider finitely generated associative algebras over a fixed K of arbitrary characteristic. For such an algebra A we impose some structural restrictions (we call A strictly ordered). We are interested in the implication of strict order on A for its noetherian properties and type of growth. In particular, we prove that if A is a graded standard finitely presented strictly ordered algebra, then A is right (left) noetherian if and only if A has polynomial growth. In this case A is almost commutative. It follows from this that the conjecture we made in [9] is true.

In this paper we discuss recent results ([1], [2], [3], [4], [5], [9]) on codes and algebraic curves. We are not concerned with algebraic geometric Goppa codes but rather with another link between coding theory and algebraic geometry. In our case the codes correspond to families of algebraic curves over a finite field, whereas Goppa codes come from a fixed algebraic curve. We use algebraic geometry to determine the weight distributions of certain codes but also we show that results from coding theory may be used to obtain results about the variation of the number of points in families of algebraic curves over a finite field. We do not assume that the reader has a knowledge of coding theory.

Résumé. Nous décrivons dans cet article deux algorithmes qui construisent les décompositions irréductible et équidimensionnelle d’une variété algébrique affine (ou projective), définie par un ensemble fini de polynômes. Le premier calcule les composantes irréductibles, donc dépend d’un algorithme de factorisation, et en conséquence ne peut se paralléliser que partiellement, du moins à notre connaissance. Le second correspond aux composantes équidimensionelles, et est susceptible d’une parallélisation totale. Comme applications, le lecteur trouvera en appendice un calcul de la forme de Chow d’une variété projective quelconque, dû à T. Krick et P. Solerno, et un calcul du degré d’une variété affine.Ces algorithmes sont décrits par des réseaux arithmétiques, ce qui permet un déroulement séquentiel ou parallèle (avec la restriction concernant la factorisation). En séquentiel, leurs complexités admettent une borne supérieure simplement exponentielle en la taille des polynômes d’entrée (quantité, degré, nombre de variables et éventuellement taille arithmétique). En parallèle, la complexité du deuxième algorithme devient polynomiale en cette taille.

Denote by A _n = A _n (F) = F[X₁,…, X _n , D₁,…, D _n ] the Weyl algebra over a field F([2]) determined by the relations X _i X _j = X _j X _i , D _i D _j = D _j D _i , X _i D _i = D _i X _i − 1, X _i D _j = D _j X _i for i ≠ j, and by the algebra of differential operators.

In this paper we consider membership problem, representation problem and also the computation of the radical for one-dimensional ideals in the polynomial ring k[X₁,…, X _n ] from a complexity point of view. Our aim is to give bounds for the complexity of the above problems which are simply exponential in the number n of variables in the one-dimensional case. Moreover we show that in the general case the first two problems are doubly exponential only in the dimension of the ideal, and parallelizable. Many authors considered membership problem (i.e. given polynomials F, F₁,…, F, ∈ k[X₁,…, X _n ], decide whether F belongs to I:= (F1…, F,)) and representation problem (compute a representation A _i ∈ k[X₁,…, X _n ]) from this effective approach. In particular [18] gives a lower bound, doubly exponential in (a fraction of) the numbers of variables n. On the other hand, [4] shows that in “good” cases, for instance for unmixed ideals, the membership problem is simply exponential in n.

A probabilistic algorithm is given which, a zero-dimensional system of polynomials being given, computes Gröbner base for any ordering of its radical and/or all of its irreducible components in time dO(n) where d is the maximal degree of the polynomials and n the number of variables. With probability nearly 1, no component is lost.This algorithm can decide zero-dimensionality with the same complexity and the same probability of success.These complexities remain valid even if the system is not zero-dimensional at infinity.This algorithm is a pratical one; it is probably slower than the computation of the Gröbner base for a degree ordering but faster than the same computation with a variable more.

Let R = ℚ[x₁, x ₂ , …, x _n ] denote the ring of polynomials in n variables over the rational numbers ℚ. Let f₁, f₂,…, f _r ∈ R, r ≥ n with deg(f _i ) = d _i and let d = max(d _i ).

We give fast algorithms for computing product and inverse in a multiple algebraic extension of the rational numbers. The algorithms are almost linear in terms of the output length, i.e. they work in time O(d1+δ), for all δ > 0, where d is an a priori bound on the length of the output. Since we require time Ω(d) just to write down the output the algorithms are close to optimal. The algorithm for inverse uses a technique referred to as dynamic evaluation for computing in algebraic extensions defined by reducible polynomials.

The classical theory of ordered fields (Artin-Schreier theory) makes intensive use of non-constructive methods, in particular of the axiom of choice. However since Tarski (and even since Sturm and Sylvester) one knows how to compute in the real closure of an ordered field K solely by computations in K. This apparent contradiction is solved in this paper.

We give a constructive proof of the real Nullstellensatz. So we obtain, for every ordered field K, a uniformly primitive recursive algorithm that computes, for the input “a system of generalized signs conditions (gsc) on polynomials of K[X₁, X₂, …, X _n ] impossible to satisfy in the real closure of K, an algebraic identity that makes this impossibility evident. The main idea is to give an “algebraic identity version” of universal and existential axioms of the theory of real closed fields, and of the simplest deduction rules of this theory (as Modus Ponens). We apply this idea to the Hörmander algorithm, which is the conceptually simplest test for the impossibility of a gsc system in the real closure of an ordered field.

Solution methods for linear equation systems in a commutative ring are discussed. Four methods are compared, in the setting of several different rings: Dodgson’s method [1], Bareiss’s method [2] and two methods of the author — method by forward and back-up procedures [3] and a one-pass method [4].We show that for the number of coefficient operations, or for the number of operations in the finite rings, or for modular computation in the polynomial rings the one-pass method [4] is the best. The method of forward and back-up procedures [3] is the best for the polynomial rings when we make use of classical algorithms for polynomial operations.

Dans son article Torsion in cohomology of compact Lie groups Victor Kac écrivait: “Remark: … A(G, Z) for G = Spin _n , SO _n , G₂ and F₄ was computed by R. Marlin. His thesis was very helpful for finding the general pattern.”

Soient A la variété des modules des courbes de genre 2, R la surface de A correspondant aux courbes ayant une involution autre que l’involution hyperelliptique, et P un point de A — R défini sur un corps k de caractéristique 0.

Let U be a submodule of P8, P a ring of multivariate polynomials, let G₁, …, G _r generate U, and let F₁:= Σb_1j G _j ,…, F _m := Σb _ij G _j with b _mj ∈ P. If a set of generators for the module of syzygies w. r. t. (G₁,…, G _r ) is given, then one problem is to compute a set of generators for the module of syzygies w. r. t. (F₁,…, F _m ) and to decide whether F₁, …, F _m also generate U. For this purpose an algorithm is presented which is similar to the Gauß-Jordan algorithm in linear algebra. It uses Gröbner bases techniques for modules and allows to solve some constructive problems in connection with modules.

An outline on the relation between algebraic complexity theories and semialgebraic sets is presented. First we discuss the concepts of total and non-scalar complexities both for polynomials and semialgebraic sets observing that they are ”geometric complexities” verifying the ”semialgebraic” version of the Benedetti-Risler conjecture [4]. Moreover, we remark that total and non-scalar complexities of semialgebraic sets are decidable theories. Finally, using non-scalar complexity and intersection numbers of semialgebraic sets we get new lower bounds for several problems in computational geometry, generalizing the results obtained by M. Ben-Or using total complexity and number of connected components. An expanded version of the ideas sketched here is [10]

The aim of this paper is to treat geometric configurations of points in a way which is as “invariant” as possible, in order to be able to interpret calculus for instance when one want to prove geometric properties of a figure. The algebraic background of this problem consists in selecting good irreducible components of the variety defined by the hypotheses and in reducing the conclusion on these sets. Instead of dealing directly with polynomials as in Ritt-Wu method, we look for geometric objects and limite ourself to relations of colinearity. A natural space where such objects can be treated easily is ΛE (the exterior algebra of E). Extending it to ΛE⊗S(ΛE) (symmetric algebra of ΛE) allows us to transform two conditions on a vector to a single one, equivalent to the first. We translate this method in the case of “formal” vectors and show that an irreducible component of the corresponding variety plays a special part for the geometric configurations. It is called the generic component. This leads to an algorithm which reduces an element of the “formal” space ΛF ⊗ S(ΛF) to zero if and only if the corresponding geometric property is true on the generic component.

Canonical bases for k-subalgeras of k[x₁, …, x _n ] are analogs of standard bases for ideals. They form a set of generators, which allows to answer the membership problem by a reduction process. Unfortunately, they may be infinite even for finitely generated subalgeras. We redefine canonical bases, and for that we recall some properties of monoids, k-algebras of monoids and “binomial” ideals, which play an essential role in our presentation and the implementation we made in the IBM computer algebra system Scratchpad II. We complete the already known relations between standard bases and canonical bases by generalizing the notion of standard bases for ideals of any k-subalgebra admitting a finite canonical basis. We also have a way of finding a set of generators of the ideal of relations between elements of a canonical basis, which is a standard basis for some ordering.We then turn to finiteness conditions, and investigate the case of integrally closed subalgebras. We show that if some integral extension B of a subalgebra A admits a finite canonical basis, we have an algorithm to solve the membership problem for A, by computing the generalized standard basis of a B-ideal. We conjecture that any integrally closed subalgebra admits a finite canonical basis, and provide partial results.There is a simple case, but of special interest, where the complexity of computing a canonical basis is known: the case where k[f₁, …, f _n ] = k[x₁, …, x _n ]. We show that the canonical bases procedure give more information than previously known methods and may provide a tool for the tame generators conjecture.

Our interest to use computers to investigate problems of algebraic geometry started because we couldn’t solve two conjectures we have been interested for a long time.

As a matter of fact, despite the fast progress of computer algebra during the last ten years, only a few steps have been done towards the use of symbolic computers for studying systems of partial differential equations (PDE) ([2], [13]). In particular, one must notice a few modern tentatives for dealing with algebraic PDE through differential algebraic techniques [19] or differential elimination techniques [16], [18] or exterior calculus ([1], Novosibirsk school), but these methods, being absolutely dependent on the coordinate system as they rely on old works ([6], [14], [18]), do not seem to go far inside the intrinsic structure of the system. Despite this point, these methods have been applied with success to control theory during the last five years ([3], [12]).

A method is given for approximating solutions of f (x) = 0, for f in a certain class F of real valued analytic functions of one real variable. The method depends on being able to decide the sign of f (r) for given f in F and rational r. That is, approximation of roots is Turing reduced to the constant problem. The last root problem is evaded: essentially solutions are only found in given finite intervals.The class of functions F contains x, exp(x), log(x) for x > 0, sin(x) for x in (—π/2, π/2), and is closed under field operations, differentiation and integration. F is built up by successively adding solutions g of first order differential equations q(x, g, g′) = 0, where q is a polynomial whose coefficients may involve previously defined functions.The main technique used is construction of a false derivative. A false derivative of f (x) is a function f *(x) which is continuous and has the same sign as f′(x) whenever f(x) = 0.

In this paper we present some effective methods in order to compute the P-locus of a quotient A of a polynomial ring S = k[X], where P is any of the following properties: “Cohen-Macaulay (C. M.)”, “Gorenstein”, “C. M. type ≤ r”, “Complete intersection (C. I.)”. It is well known that the previous loci are open being A an excellent ring (see, for instance, [GM]).

The aim of this paper is to study the following problem: • Let f₁, f₂, …, f _n , be n polynomials with integer coefficients such that: 1.for 1 ≤ i ≤n, f _i - is a polynomial of the variables (X₁, …, X _i ), monic in X _i , of degree d _i in X _i ; 2.for 1 ≤ i ≤n, for 1 ≤ j ≤i, f _i is of degree δ _j ≤ d _j in X _j .

Monomial algebras are finitely presented algebras defined by monomials. This notion is considered the most fundamental of “standard” finitely presented algebras, in the sense that they have finite non-commutative Gröbner bases as defining relations.This paper classifies and constructs finite-dimensional monomial algebras modulo an algebra isomorphism by means of trees of nonzero monomials. These trees are deeply related to partially ordered sets called LSGOP. As a corollary, it is shown that every finite-dimensional monomial algebra has a unique irredundant presentation up to a permutation of generators. This result will serve as an effective method for solving the isomorphism problem in this area.

A classical problem of projective geometry is the determination of methods for the computation of the number of figures which satisfy certain properties. In the case of subspaces, a method which has been largely developed and is well known is the study of the Grassmann varieties and their Chow ring. In the case of quadrics, pairs of spaces and more in general in the case of a symmetric variety G/H, where G is a semisingle adjoint group, H = Gσ, σ an order two automorphism of G, a general method has been introduced, defining a suitable intersection ring for G/H. Such ring is difficult to calculate being the direct limit of the Chow ring of all the equivariant regular compactifications of G/H. For a given compactification, one can give a general combinatorial method for the computation of the Chow ring, using root systems, fans and sheaves over fans, which can be treated in a purely algebraic way [BDP].

Let h ∈ Z[X₁,…, X _n ] be an arbitrary polynomial.