Skip to main content



Computation of Real Radicals of Polynomial Ideals

We describe an algorithm for the computation of the τ-radicals of ideals in polynomial rings over rational function fields k(T 1,…,T m) where (k, τ) is a preordered field satisfying certain computational conditions.
E. Becker, R. Neuhaus

Semialgebraic geometry of polynomial control problems

We prove some new facts concerning metric properties of semi algebraic sets and on this base establish some geometric properties of nearcritical trajectories in polynomial control problems.
M. Briskin, Y. Yomdin

The Resultant via a Koszul Complex

As noticed by Jouanolou, Hurwitz proved in 1913 ([Hu]) that, in the generic case, the Koszul complex is acyclic in positive degrees if the number of (homogeneous) polynomials is less than or equal to the number of variables. It was known around 1930 that resultants may be calculated as a Mc Rae invariant of this complex. This expresses the resultant as an alternate product of determinants coming from the differentials of this complex. Demazure explained in a preprint ([De]), how to recover this formula from an easy particular case of deep results of Buchsbaum and Eisenbud on finite free resolutions. He noticed that one only needs to add one new variable in order to do the calculation in a non generic situation.
I have never seen any mention of this technique of calculation in recent reports on the subject (except the quite confidential one of Demazure and in an extensive work of Jouanolou, however from a rather different point of view). So, I will give here elementary and short proofs of the theorems needed—except the well-known acyclicity of the Koszul complex and the “Principal Theorem of Elimination”—and present some useful remarks leading to the subsequent algorithm. In fact, no genericity is needed (it is not the case for all the other techniques). Furthermore, when the resultant vanishes, some information can be given about the dimension of the associated variety.
As an illustration of this technique, we give an arithmetical consequence on the resultant: if the polynomials have integral coefficients and their reductions modulo a prime p defines a variety of projective dimension zero and degree d, then p d divides the resultant.
Marc Chardin

Gröbner Bases and Standard Monomial Theory

For rings of polynomials on varieties corresponding to minuscule weight representations of Lie groups, we show how the standard monomial theory of Seshadri et al. can be used to compute Gröbner bases. This generalizes results of Sturmfels and White in which straightening has been interpreted as a normal form computation with respect to a Gröbner basis.
Arjeh M. Cohen, Richard H. Cushman

A continuous and rational solution to Hilbert’s 17th problem and several cases of the Positivstellensatz

From the Positivstellensatz we construct a continuous and rational solution for Hilbert’s 17th problem and for several cases of the Positivstellensatz. The solutions are obtained using an especially simple method.
Charles N. Delzell, Laureano González-Vega, Henri Lombardi

The analytic spread of the ideal of a monomial curve in projective 3-space

Let k be an algebraically closed field and let C ⊂ An stand for a quasi homogeneous surface admitting a rational parametrization given by monomials. Consider the blowing-up A ñ of A n with center C and look at the fibre of the structural morphism
$$ \widetilde{{{\mathbb{A}^{2}}}} \to {\mathbb{A}^{n}} $$
over the origin 0 (the special fibre of the blowing-up).
Philippe Gimenez, Marcel Morales, Aron Simis

Computational Complexity of Sparse Real Algebraic Function Interpolation

We analyze the computational complexity of the problem of interpolating real algebraic functions given by a black box for their evaluations, extending the results of [GKS 90b, GKS 91b] on interpolation of sparse rational functions.
Dima Grigoriev, Marek Karpinski, Michael Singer

Shade, Shadow and Shape

We shall motivate the use of geometric cues in intelligent vision, then explain how mathematics can be used to define and unify treatment of these cues.1 2
Jean-Pierre Henry, Michel Merle

Arrangements of singularities and proper partitions of Dynkin diagrams

We associate to every isolated singularity of an analytic function and to every tame polynomial a bilinear form, namely the intersection form (.,.) in the vanishing homology group H.
Piotr Jaworski

Versal deformations of powers of volume forms

Deformations of powers of volume forms of the kind
$$ F\left( {x,\lambda } \right){{\left( {dx} \right)}^{\alpha }},x \in {{C}^{n}},F\left( {x,0} \right) = f\left( x \right),dx = d{{x}_{1}} \wedge ... \wedge d{{x}_{n}},\alpha \in C $$
are investigated. If f has an isolated singularity of multiplicity μ at the origin, then the form f(x)(dx) α has a μ-parameter versal deformation for almost every value of α. Exceptional values of α form a discrete set of negative rational numbers. Given f, the versal deformation can be obtained algorithmically. For non-exceptional values of α it is the same as the versal deformation of the germ of a function f.
V. P. Kostov, S. K. Lando

Computing subfields: Reverse of the primitive element problem

We describe an algorithm which computes all subfields of an effectively given finite algebraic extension. Although the base field can be arbitrary, we focus our attention on the rationals.
This appears to be a fundamental tool for the simplification of algebraic numbers.
D. Lazard, A. Valibouze

Applications of the Eisenbud-Levine’s theorem to real algebraic geometry

Let f: (R n,0) → (R p,0) be the germ of an analytic mapping. The fibre f - 1(0) is locally homeomorphic to a cone, with vertex 0. The base L of the cone is the intersection of f 1(0) with a small sphere S centred at 0. Investigation of topology of L is one of the most crucial aims of singularity theory.
Andrzej Łȩcki, Zbigniew Szafraniec

Applications of Algebraic Geometry to Computer Vision

There is an increasing interest in applications of algebraic geometry to computer vision. There are at least three possible reasons for this: i) certain vision problems naturally involve polynomial equations; ii) with the increase in available computing power it is easier to implement algorithms which stay close to the geometry underlying vision; and iii) algebraic geometry may in future provide methods for assessing the stability of algorithms against small perturbations in the data.
S. J. Maybank

Disproving Hibi’s Conjecture with CoCoA or Projective Curves with bad Hilbert Functions

In this paper we show how to combine different techniques from Commutative Algebra and a systematic use of a Computer Algebra System (in our case mainly CoCoA (see [G-N] and [A-G-N])) in order to explicitly construct Cohen-Macaulay domains, which are standard k-algebras and whose Hilbert function is “bad”. In particular we disprove a well-known conjecture by Hibi.
Gianfranco Niesi, Lorenzo Robbiano

Counting real zeros in the multivariate case

In this paper we show, by generalizing Hermite’s theorem to the multivariate setting, how to count the number of real or complex points of a discrete algebraic set which lie within some algebraic constraint region. We introduce a family of quadratic forms determined by the algebraic constraints and defined in terms of the trace from the coordinate ring of the variety to the ground field, and we show that the rank and signature of these forms are sufficient to determine the number of real points lying within a constraint region. In all cases we count geometric points, which is to say, we count points without multiplicity. The theoretical results on these quadratic forms are more or less classical, but forgotten too, and can be found also in [3].
We insist on effectivity of the computation and complexity analysis: we show how to calculate the trace and signature using Gröbner bases, and we show how the information provided by the individual quadratic forms may be combined to determine the number of real points satisfying a conjunction of constraints. The complexity of the computation is polynomial in the dimension as a vector space of the quotient ring associated to the defining equations. In terms of the number of variables, the complexity of the computation is singly exponential. The algorithm is well parallelizable.
We conclude the paper by applying our machinery to the problem of effectively calculating the Euler characteristic of a smooth hypersurface.
P. Pedersen, Marie-Françoise Roy, Aviva Szpirglas

Finding the number of distinct real roots of sparse polynomials of the form p(x,x n)

Cylindrical decomposition and false derivatives are used to find the number of distinct real solutions of a polynomial with integral coefficients p(x, x n ), where n is large. The computation time depends only poly normally on the size of the problem, where this is defined to be the maximum of d, log(n) and log(C), where d is the total degree of p(x, y), assumed to be small relative to n, and C is the maximum of the absolute values of the coefficients.
Daniel Richardson

Locally effective objects and algebraic topology

Algebraic topology consists of associating invariants are of an algebraic nature, describing certain topological properties. For example, since Poincaré, it is known how to associate the group π1(X,x 0 to a topological space X and to one of its points x 0; this group is called the Poincaré group or the first homotopy group of the space X based on x 0. This group is null if and only if the space X is simply connected at x 0; in another case, the group measures the lack of simple connectivity. Many other groups can be associated to a topological space, evaluating certain properties of this space: homology groups,K-theory groups,etc.
Julio Rubio, Francis Sergeraert

Decision of Algebra Isomorphisms Using Gröbner Bases

Given two finite-dimensional non-commutative finitely presented algebras A and B over a field k, this paper presents two algorithms for deciding whether or not they are isomorphic as k-algebras. We reduce this problem to a radical ideal membership problem in a commutative ring, by Hilbert’s zero point theorem. That is, A and B are isomorphic if and only if the determinant f of a k-linear mapping: AB does not lie in the radical of an ideal I derived from the relations of A and B. Moreover an efficient technique for computing f is provided.
We propose two Gröbner basis methods for solving our problem. One is to compute the radical of I directly and then to rewrite the above determinant f modulo this radical. The other method is to judge solvability of a certain system of algebraic equations: the union of I and a new polynomial. As a result, it is shown that the isomorphism problem for finitely presented algebras is decidable.
Kiyoshi Shirayanagi

Complexity of Bezout’s Theorem II Volumes and Probabilities

In this paper we study volume estimates in the space of systems of n homegeneous polynomial equations of fixed degrees d i with respect to a natural Hermitian structure on the space of such systems invariant under the action of the unitary group. We show that the average number of real roots of real systems is D 1/2 where D = Π d i is the Be zout number. We estimate the volume of the subspace of badly conditioned problems and show that volume is bounded by a small degree polynomial in n, N and D times the reciprocal of the condition number to the fourth power. Here N is the dimension of the space of systems.
Michael Shub, Steve Smale

A Parametrized Nullstellensatz

Let k be a field and f, F1,…,F3k[X 1,…,X n], with deg(Fi) = d i and maxd 1,…, d 3d. When there exist some polynomials A 1,…, A 3 and power N such that we have a representation 1 = A 1 F 1 + … + A 3F3 or f N = A 1 F 1 + … + A3F3, the question arises how to bound optimally a = sup deg {A i} and N.
Frédéric Smietanski

An Elimination Method Based on Seidenberg’s Theory and Its Applications

In this paper we present an elimination method for algebraically closed fields based on Seidenberg’s theory. The method produces, for any pair [PS, QS] of sets of multivariate polynomials, a sequence of triangular forms TF 1,…, TF e and polynomial sets US 1,…, US e such that the difference set of common zeros of PS and QS is the same as the union of the difference sets of common zeros of TF i and US i. Moreover, the triangular forms TF i and polynomial sets US i can be so computed as to give a necessary and sufficient condition for the given system to have algebraic zeros for some prescribed variables. This method has a number of applications such as to solving systems of polynomial equations and inequalities, mechanical theorem proving in geometry, irreducible decomposition of algebraic varieties and constructive proof of Hilbert’s Nullstellensatz which are partially discussed in the paper. Preliminary experiments show that the efficiency of this method is at least comparable with that of the well-known methods of characteristic sets and Gröbner bases for some applications. A few illustrative yet encouraging examples performed by a draft implementation of the method are given.
Dongming Wang


Weitere Informationen