Sharp estimates for triangular sets

ABSTRACT

We study the triangular representation of zero-dimensional varieties defined over the rational field (resp. a rational function field). We prove polynomial bounds in terms of intrinsic quantities for the height (resp. degree) of the coefficients of such triangular sets, whereas previous bounds were exponential. We also introduce a rational form of triangular representation, for which our estimates become linear. Experiments show the practical interest of this new representation.

REFERENCES

• 1: M. E. Alonso , E. Becker , M.-F. Roy , T. Wörmann, Zeros, multiplicities, and idempotents for zero-dimensional systems, Algorithms in algebraic geometry and applications, Birkhauser Verlag, Basel, Switzerland, 1996
• 2: Philippe Aubry , Daniel Lazard , Marc Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation, v.28 n.1-2, p.105-124, July/Aug. 1999 [doi>10.1006/jsco.1999.0269]
• 3: Philippe Aubry , Annick Valibouze, Using Galois ideals for computing relative resolvents, Journal of Symbolic Computation, v.30 n.6, p.635-651, Dec. 2000 [doi>10.1006/jsco.2000.0376]
• 4: J.-B. Bost, H. Gillet, and C. Soulé. Heights of projective varieties and positive Green forms. J. Amer. Math. Soc., 7(4):903--1027, 1994.
• 5: X. Dahan. Bornes de hauteur pour la représentation triangulaire de variétés présentant des symétries. www.stix.polytechnique.fr/~dahan, 2003.
• 6: G. Gallo and B. Mishra. Efficient algorithms and bounds for Wu-Ritt characteristic sets. In MEGA'90, volume~94 of Prog. in Math., pages 119--142. Birkhäuser, 1990.
• 7: P. Gaudry and É. Schost. Construction of secure random curves of genus 2 over prime fields. 2003.
• 8: M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower bounds for Diophantine approximations. J. Pure Appl. Algebra, 117--118:277--317, 1997.
• 9: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 10: K. Hägele, J.-E. Morais, L.-M. Pardo, and M. Sombra. On the intrinsic complexity of the arithmetic Nullstellensatz. J. Pure. Appl. Alg., 146:103--183, 2000.
• 11: J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theoret. Comput. Sci., 24(3):239--277, 1983.
• 12: É. Hubert. Notes on triangular sets and triangulation decomposition algorithms I: Polynomial systems. In Symbolic and Numerical Scientific Computations, volume 2630 of LNCS. Springer, 2003.
• 13: T. Krick, L.-M. Pardo, and M. Sombra. Sharp estimates for the arithmetic Nullstellensatz. Duke Math. J., 109(3):521--598, 2001.
• 14: S. Lang. Diophantine geometry. Tracts in Pure and Applied Mathematics, No. 11. Interscience, 1962.
• 15: D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, v.13 n.2, p.117-131, Feb. 1992 [doi>10.1016/S0747-7171(08)80086-7]
• 16: P. J. McCarthy. Algebraic extensions of fields. Dover Publications Inc., New York, 1991.
• 17: P. Philippon. Sur des hauteurs alternatives. III. J. Math. Pures Appl. (9), 74(4):345--365, 1995.
• 18: F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. Appl. Algebra Engrg. Comm. Comput., 9(5):433--461, 1999.
• 19: É. Schost. Sur la résolution des systèmes polynomiaux à paramètres. PhD thesis, École polytechnique, 2000.
• 20: Éric Schost, Complexity results for triangular sets, Journal of Symbolic Computation, v.36 n.3-4, p.555-594, September 2003 [doi>10.1016/S0747-7171(03)00095-6]
• 21: ÉE. Schost. Computing parametric geometric resolutions. Appl. Algebra Engrg. Comm. Comput., 13(4):349--393, 2003.
• 22: M. Sombra. Estimaciones para el teorema de ceros de Hilbert. PhD thesis, U. de Buenos Aires, 1998.
• 23: Agnes Szanto , Dexter Kozen, Computation with polynomial systems, 1999
• 24: D. Wang. Elimination Methods, volume XIII of Texts and monographs in symbolic computation. Springer-Verlag, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Experimentation, Theory

Keywords:
intrinsic bounds, polynomial systems, triangular sets