Skip to main content

Über dieses Buch

The symposium "MEGA-90 - Effective Methods in Algebraic Geome­ try" was held in Castiglioncello (Livorno, Italy) in April 17-211990. The themes - we quote from the "Call for papers" - were the fol­ lowing: - Effective methods and complexity issues in commutative algebra, pro­ jective geometry, real geometry, algebraic number theory - Algebraic geometric methods in algebraic computing Contributions in related fields (computational aspects of group theory, differential algebra and geometry, algebraic and differential topology, etc.) were also welcome. The origin and the motivation of such a meeting, that is supposed to be the first of a series, deserves to be explained. The subject - the theory and the practice of computation in alge­ braic geometry and related domains from the mathematical viewpoin- has been one of the themes of the symposia organized by SIGSAM (the Special Interest Group for Symbolic and Algebraic Manipulation of the Association for Computing Machinery), SAME (Symbolic and Algebraic Manipulation in Europe), and AAECC (the semantics of the name is vary­ ing; an average meaning is "Applied Algebra and Error Correcting Codes").



On Lack of Effectiveness in Semi-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.

Riccardo Benedetti

A simple constructive proof of Canonical Resolution of Singularities

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].

Edward Bierstone, Pierre D. Milman

Local Membership Problems for Polynomial Ideals

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

Leandro Caniglia, Jorge A. Guccione, Juan J. Guccione

Un Algorithme pour le Calcul des Résultants

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.

Marc Chardin

On algorithms for real algebraic plane curves

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.

Felipe Cucker, Laureano González Vega, Francesc Rossello

Duality methods for the membership problem

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).

Alicia Dickenstein, Carmen Sessa

Exemples d’ensembles de Points en Position Uniforme

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′.

André Galligo

Efficient Algorithms and Bounds for Wu-Ritt Characteristic Sets

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.

Giovanni Gallo, Bhubaneswar Mishra

Noetherian Properties and Growth of some Associative Algebras

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.

Tatiana Gateva-Ivanova

Codes and Elliptic Curves

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.

Gerard van der Geer

Algorithmes – disons rapides – pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionnelles

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.

Marc Giusti, Joos Heintz

Complexity of Solving Systems of Linear Equations over the Rings of Differential Operators

Denote by A n = A n (F) = F[X1,…, X n , D1,…, 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.

Dimitri Yu. Grigor’ev

Membership problem, Representation problem and the Computation of the Radical for one-dimensional Ideals

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[X1,…, 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, F1,…, F, ∈ k[X1,…, X n ], decide whether F belongs to I:= (F1…, F,)) and representation problem (compute a representation A i ∈ k[X1,…, 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.

Teresa Krick, Alessandro Logar

On the Complexity of Zero-dimensional Algebraic Systems

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.

Y. N. Lakshman, Daniel Lazard

A Single Exponential Bound on the Complexity of Computing Gröbner Bases of Zero Dimensional Ideals

Let R = ℚ[x1, x 2 , …, x n ] denote the ring of polynomials in n variables over the rational numbers ℚ. Let f1, f2,…, f r ∈ R, r ≥ n with deg(f i ) = d i and let d = max(d i ).

Y. N. Lakshman

Algorithms for a Multiple Algebraic Extension

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.

Lars Langemyr

Elementary constructive theory of ordered fields

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.

Henri Lombardi, Marie-Françoise Roy

Effective real Nullstellensatz and variants

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[X1, X2, …, 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.

Henri Lombardi

Algorithms for the Solution of Systems of Linear Equations in Commutative Rings

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.

Gennadi I. Malashonok

Une conjecture sur les anneaux de Chow A(G, Z) renforcée par un calcul formel

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

Roger Marlin

Construction de courbes de genre 2 à partir de leurs modules

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.

Jean-François Mestre

Computing Syzygies à la Gauß-Jordan

Let U be a submodule of P8, P a ring of multivariate polynomials, let G1, …, G r generate U, and let F1:= Σb1j 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. (G1,…, G r ) is given, then one problem is to compute a set of generators for the module of syzygies w. r. t. (F1,…, F m ) and to decide whether F1, …, 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.

H. Michael Möller

The non-scalar Model of Complexity in Computational Geometry

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]

José L. Montaña, Luis M. Pardo, Tomas Recio

Géométrie et Interpretations Génériques un Algorithme

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.

Bernard Mourrain

Canonical Bases: Relations with Standard Bases, Finiteness Conditions and Application to Tame Automorphisms

Canonical bases for k-subalgeras of k[x1, …, 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[f1, …, f n ] = k[x1, …, 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.

François Ollivier

The tangent cone algorithm and some applications to local algebraic geometry

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.

Gerhard Pfister

Effective Methods for Systems of Algebraic Partial Differential Equations

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]).

Jean-François Pommaret, Akli Haddak

Finding roots of equations involving functions defined by first order algebraic differential equations

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.

Daniel Richardson

Some Effective Methods in the Openness of Loci for Cohen-Macaulay and Gorenstein Properties

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]).

Fabio Rossi, Walter Spangher

Sign determination on zero dimensional sets

The aim of this paper is to study the following problem: • Let f1, f2, …, f n , be n polynomials with integer coefficients such that: 1.for 1 ≤ i ≤n, f i - is a polynomial of the variables (X1, …, 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 .

Marie-Françoise Roy, Aviva Szpirglas

A Classification of Finite-dimensional Monomial Algebras

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.

Kiyoshi Shirayanagi

An Algorithm related to Compactifications of adjoint Groups

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].

Elisabetta Strickland

Deciding Consistency of Systems of Polynomial in Exponent Inequalities in Subexponential Time

Let h ∈ Z[X1,…, X n ] be an arbitrary polynomial.

Nikolaj N. Vorobjov
Weitere Informationen