×

Lower bounds for diophantine approximations. (English) Zbl 0871.68101

Summary: We introduce a subexponential algorithm for geometric solving of multivariate polynomial equation systems whose bit complexity depends mainly on intrinsic geometric invariants of the solution set. From this algorithm, we derive a new procedure for the decision of consistency of polynomial equation systems whose bit complexity is subexponential, too. As a byproduct, we analyze the division of a polynomial modulo a reduced complete intersection ideal and from this, we obtain an intrinsic lower bound for the logarithmic height of diophantine approximations to a given solution of a zero-dimensional polynomial equation system. This result represents a multivariate version of Liouville’s classical theorem on approximation of algebraic numbers by rationals. A special feature of our procedures is their polynomial character with respect to the mentioned geometric invariants when instead of bit operations only arithmetic operations are counted at unit cost. Technically our paper relies on the use of straight-line programs as a data structure for the encoding of polynomials, on a new symbolic application of Newton’s algorithm to the implicit function theorem and on a special, basis independent trace formula for affine Gorenstein algebras.

MSC:

68Q25 Analysis of algorithms and problem complexity
14Q15 Computational aspects of higher-dimensional varieties
11J68 Approximation to algebraic numbers

Software:

TERA
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Alonso, M. E.; Becker, E.; Roy, M.-F.; Wörmann, T., Zeroes, multiplicities and idempotents for zerodimensional systems, (González, L.; Recio, T., Algorithms in Algebraic Geometry and Applications. Algorithms in Algebraic Geometry and Applications, Progress in Mathematics, Vol. 142 (1996), Birkhäuser: Birkhäuser Basel), 1-15
[2] Becker, E.; Cardinal, J. P.; Roy, M.-F.; Szafraniec, Z., Multivariate Bezoutians, Kronecker symbol and Eisenbud-Levine formula, (González, L.; Recio, T., Algorithms in Algebraic Geometry and Applications. Algorithms in Algebraic Geometry and Applications, Progress in Mathematics, Vol. 142 (1996), Birkhauser: Birkhauser Basel), 79-104 · Zbl 0873.13013
[3] Berenstein, C.; Yger, A., Effective Bezout identities in \(Q[X1,…,Xn]\), Acta Math., 166, 69-120 (1991) · Zbl 0724.32002
[4] Berenstein, C.; Yger, A., Une formule de Jacobi et ses conséquences, Ann Sci. E.N.S., 4ième série, 24, 363-377 (1991) · Zbl 0742.32004
[5] Berenstein, C.; Yger, A., Green currents and analytic continuation (1995), Univ. of Maryland, preprint · Zbl 0910.14009
[6] Berkowitz, S. J., On computing the determinant in small parallel time using a small number of processors, (Inf. Proc. Lett., 18 (1984)), 147-150 · Zbl 0541.68019
[7] Borodin, A.; von zur Gathen, J.; Hopcroft, J., Fast parallel matrix and GCD computations, Inform. and Control, 52, 241-256 (1982) · Zbl 0507.68020
[8] Bost, J.-B.; Gillet, H.; Soulé, C., Un analogue arithmétique du théorème de Bézout, C.R. Acad. Sci. Paris, Série I, Math., 312, 845-848 (1991) · Zbl 0756.14012
[9] Bost, J.-B.; Gillet, H.; Soulé, C., Heights of projective varieties and positive Green forms (1993), IHES, manuscript · Zbl 0973.14013
[10] Brownawell, D. W., Bounds for the degree in the Nullstellensatz, Ann. Math., 126, 577-591 (1987) · Zbl 0641.14001
[11] Canny, J. F.; Emiris, I. Z., Efficient incremental algorithms for the sparse resultant and the mixed volume (1995), preprint · Zbl 0843.68036
[12] Caniglia, L.; Galligo, A.; Heintz, J., Borne simplement exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque, C.R. Acad. Sci. Paris, Série I, Math., 307, 255-258 (1988) · Zbl 0686.14001
[13] Caniglia, L.; Galligo, A.; Heintz, J., Some new eflfectivity bounds in computational geometry, (Mora, T., Proc. AAECC-6. Proc. AAECC-6, Lecture Notes in Computer Science, Vol. 357 (1989)), 131-152
[14] Cardinal, J. P., Dualité et algorithmes itératives pour la solution des systèmes polynomiaux, (Thèse (1993), U. de Rennes I)
[15] Chistov, A. L.; Grigor’ev, D. J., Subexponential time solving systems of algebraic equations, LOMI preprints E-9-83, E-10-83 (1983), Leningrad
[16] Csanky, L., Fast parallel matrix inversion algorithms, SIAM J. Comp., 5, 618-623 (1976) · Zbl 0353.68063
[17] Dedieu, J.-P., Estimations for the separation number of a polynomial system (1995), Univ. Paul Sabatier: Univ. Paul Sabatier Toulouse, preprint
[18] Dedieu, J.-P., Approximate solutions of numerical problems, condition number analysis and condition number theorems (1995), Univ. Paul Sabatier: Univ. Paul Sabatier Toulouse, preprint
[19] Elkadi, M., Bornes pour le degré et les hauteurs dans le problème de division, Michigan Math. J., 40, 609-618 (1993) · Zbl 0810.32001
[20] Emiris, I. Z., On the complexity of sparse elimination, (Report No. UCB/CSD-94/840 (1994), Univ. of California) · Zbl 0935.12008
[21] Fallings, G., Diophantine approximation on abelian varieties, Ann. Math., 133, 549-576 (1991) · Zbl 0734.14007
[22] Fitchas, N.; Giusti, M.; Smietanski, F., Sur la complexité du théorème des zéros, (Florenzano, M.; etal., Approximation and Optimization in the Caribbean II, Proc. 2nd Internat. Conf. on Approximation and Optimization. Approximation and Optimization in the Caribbean II, Proc. 2nd Internat. Conf. on Approximation and Optimization, La Habana, 1993. Approximation and Optimization in the Caribbean II, Proc. 2nd Internat. Conf. on Approximation and Optimization. Approximation and Optimization in the Caribbean II, Proc. 2nd Internat. Conf. on Approximation and Optimization, La Habana, 1993, Approximation and Optimization (1995), Peter Lang Verlag: Peter Lang Verlag Frankfurt), 274-329 · Zbl 0868.12008
[23] Gianni, P.; Mora, T., Algebraic solution of systems of polynomial equations using Gröbner bases, (Proc. AAECC-5, LNCS, Vol. 356 (1989), Springer: Springer Berlin), 247-257
[24] Giusti, M.; Heintz, J., La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, (Eisenbud, D.; Robbiano, L., Computational Algebraic Geometry and Commutative Algebra. Computational Algebraic Geometry and Commutative Algebra, Proc. Cortona Conf. on Computational Algebraic Geometry and Commutative Algebra, Symposia Matematica, vol. XXXIV (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), Istituto Nazionale di Alta Matematica · Zbl 0829.14029
[26] Giusti, M.; Heintz, J.; Morais, J. E.; Pardo, L. M., When polynomial equation systems can be “solved” fast?, (Cohen, G.; Giusti, M.; Mora, T., Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris 1995. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris 1995, Lecture Notes in Computer Science, Vol. 948 (1995), Springer: Springer Berlin), 205-231 · Zbl 0902.12005
[27] Giusti, M.; Heintz, J.; Sabia, J., On the efficiency of effective Nullstellensätze, Comput. Complexity, 3, 56-95 (1993) · Zbl 0824.68051
[28] Heintz, J., Fast quantifier elimination over algebraically closed fields, Theoret. Comput. Sci., 24, 239-277 (1983) · Zbl 0546.03017
[29] Heintz, J.; Krick, T.; Slissenko, A.; Solernó, P., Searching for a shortest path surrounding semi-algebraic obstacles in the plane, (Teorija složnosti vyčislenij, 5. Teorija složnosti vyčislenij, 5, Zapiski nauc̆nyh seminarov LOMI (Leningrad branch of the Mathematical Institute Steklov), Vol. 192 (1991), Nauka: Nauka Leningrad), 163-173, (in russian) · Zbl 0761.14019
[30] Heintz, J.; Krick, T.; Slissenko, A.; Solernó, P., Une borne inférieure pour la construction des chemins polygonaux dans \(R^n (1992)\), Univ. de Limoges, preprint
[31] Heintz, J.; Morgenstern, J., On the intrinsic complexity of elimination theory, J. Complexity, 9, 471-498 (1993) · Zbl 0835.68054
[32] Heintz, J.; Schnorr, C. P., Logic and Algorithmic, (An Internat. Symp. held in Honour of Ernst Specker. An Internat. Symp. held in Honour of Ernst Specker, Monographie No. 30 (1982), de l’Enseignement de Mathématiques: de l’Enseignement de Mathématiques Genève), 237-254, also in
[33] Kollár, J., Sharp Effective Nullstellensatz, J. Amer. Math. Soc., 1, 963-975 (1988) · Zbl 0682.14001
[34] Krick, T.; Pardo, L. M., A computational method for diophantine approximation, (González, L.; Recio, T., Algorithms in Algebraic Geometry and Applications. Algorithms in Algebraic Geometry and Applications, Progress in Mathematics, Vol. 142 (1996), Birkhäuser: Birkhäuser Basel), 193-254 · Zbl 0878.11043
[35] Krick, T.; Pardo, L. M., Une approche informatique pour l’approximation diophantienne, C.R. Acad. Sci. Paris, t. 318, Série I, 5, 407-412 (1994) · Zbl 0814.14050
[36] Krick, T.; Sabia, J.; Solernó, P., On intrinsic bounds in the Nullstellensatz, Appl. Algebra Eng. Commun. Comput. (AAECC J.), 8, 125-134 (1997) · Zbl 0897.13021
[37] Kunz, E., Kahler Differentials, (Advanced Lectures in Mathematics (1986), Vieweg Verlag: Vieweg Verlag Braunschweig/Wiesbaden) · Zbl 0587.13014
[38] Iversen, B., Generic Local Structure of the Morphisms in Commutative Algebra, (Lecture Notes in Computer Science, Vol. 310 (1973), Springer: Springer Berlin) · Zbl 0247.13001
[39] Mignotte, M., Mathématiques pour le Calcul Formel (1989), Presses Universitaires de France · Zbl 0679.12001
[40] Montaña, J. L.; Morais, J. E.; Pardo, L. M., Lower bounds for arithmetic networks II: sum of Betti numbers, Appl. Algebra Eng. Commun. Comput. (AAECC J.), 7, 1, 41-51 (1996) · Zbl 0844.68069
[41] Montaña, J. L.; Pardo, L. M., Lower bounds for arithmetic networks, Appl. Algebra Eng. Commun. Comput. (AAECC J.), 4, 1-24 (1993) · Zbl 0769.68055
[42] Nesterenko, Yu. V., Estimates for the order of zero o functions of a certain class and applications in the theory of transcendental numbers, Math. USSR Izvestija, 11, 2, 239-270 (1977) · Zbl 0378.10022
[43] Nesterenko, Yu. V., On a measure of the algebraic independence of the values of certain functions, Math. USSR Sbornik, 56, 545-567 (1987) · Zbl 0608.10034
[44] Pardo, L. M., How lower and upper complexity bounds meet in elimination theory, (Cohen, G.; Giusti, M.; Mora, T., Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris 1995. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris 1995, Lecture Notes in Computer Science, Vol. 948 (1995), Springer: Springer Berlin), 33-69 · Zbl 0899.68054
[45] Philippen, P., Critères pour l’indépendence algébrique, Pub. Math, de l’IHFS, 64, 5-52 (1987)
[46] Philippen, P., Sur des hauteurs alternatives, I, Math. Ann., 289, 255-283 (1991)
[47] Philippen, P., Sur des hauteurs alternatives, II, Ann. Inst. Fourier, Grenoble, 44, 2, 1043-1065 (1994) · Zbl 0878.11024
[48] Philippen, P., Sur des hauteurs alternatives, III, J. Math. Pures Appl., 74, 345-365 (1995)
[49] Sabia, J.; Solernó, P., Bounds for traces in complete intersections and degrees in the Nullstellensatz, Appl. Algebra in Eng. Commun. Comput. (AAECC J.), 6, 353-376 (1996) · Zbl 0844.14018
[50] Schneider, T., Einführung in die Theorie der transzendenten Funktionen (1957), Springer: Springer Berlin
[51] Shub, M.; Smale, S., Complexity of Bezout’s theorem I: Geometric aspects, J. Amer. Math. Soc., 6, 459-501 (1993) · Zbl 0821.65035
[52] Shub, M.; Smale, S., Complexity of Bezout’s theorem II: Volumes and probabilities, (Eyssette, F.; Galligo, A., Computational Algebraic Geometry. Computational Algebraic Geometry, Progress in Mathematics, Vol. 109 (1993), Birkhäuser: Birkhäuser Basel), 267-285 · Zbl 0851.65031
[53] Shub, M.; Smale, S., Complexity of Bezout’s theorem III: condition number and packing, J. Complexity, 9, 4-14 (1993) · Zbl 0846.65018
[54] Shub, M.; Smale, S., Complexity of Bezout’s theorem V: polynomial time, Theoret. Comput. Sci., 133 (1994) · Zbl 0846.65022
[55] Shub, M.; Smale, S., On the intractability of Hubert’s Nullstellensatz and an algebraic version of NP ≠ P?, IBM Research Report (1994), Yorktown Heights
[58] Strassen, V., Vermeidung von Divisionen, Grelle J. Reine Angew. Math., 264, 184-202 (1973) · Zbl 0294.65021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.