Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry

Mohab Safey El Din 1 Philippe Trebuchet 1
1 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Let f1, ..., fs be a polynomial family in Q[X1,..., Xn] (with s less than n) of degree bounded by D. Suppose that f1, ..., fs generates a radical ideal, and defines a smooth algebraic variety V. Consider a projection P. We prove that the degree of the critical locus of P restricted to V is bounded by D^s(D-1)^(n-s) times binomial of n and n-s. This result is obtained in two steps. First the critical points of P restricted to V are characterized as projections of the solutions of Lagrange's system for which a bi-homogeneous structure is exhibited. Secondly we prove a bi-homogeneous Bézout Theorem, which bounds the sum of the degrees of the equidimensional components of the radical of an ideal generated by a bi-homogeneous polynomial family. This result is improved when f1,..., fs is a regular sequence. Moreover, we use Lagrange's system to design an algorithm computing at least one point in each connected component of a smooth real algebraic set. This algorithm generalizes, to the non equidimensional case, the one of Safey El Din and Schost. The evaluation of the output size of this algorithm gives new upper bounds on the first Betti number of a smooth real algebraic set. Finally, we estimate its arithmetic complexity and prove that in the worst cases it is polynomial in n, s, D^s(D-1)^(n-s) and the binomial of n and n-s, and the complexity of evaluation of f1,..., fs.
Type de document :
[Research Report] RR-6001, INRIA. 2006, pp.46
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 23 octobre 2006 - 10:03:21
Dernière modification le : jeudi 11 janvier 2018 - 06:20:06
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 10:39:39





Mohab Safey El Din, Philippe Trebuchet. Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry. [Research Report] RR-6001, INRIA. 2006, pp.46. 〈inria-00105204v4〉



Consultations de la notice


Téléchargements de fichiers