On the efficiency of effective Nullstellensätze. (English) Zbl 0824.68051

Summary: Let \(k\) be an infinite and perfect field, \(x_ 1, \dots, x_ n\) indeterminates over \(k\) and let \(f_ 1, \dots, f_ s\) be polynomials in \(k[x_ 1, \dots, x_ n]\) of degree bounded by a given number \(d\), which satisfies \(d \geq n\). We prove an effective affine Nullstellensatz of the following particular form: For arbitrary given parameters \(d,s,n\) there exists a probabilistic (randomized) arithmetic network over \(k\) of size \(s^{O (1)}\) \(d^{O (n)}\) and depth \(O(n^ 4 \log^ 2 sd)\) solving the following task: It decides whether the ideal generated by \(f_ 1, \dots, f_ s\) in \(k[x_ 1, \dots, x_ n]\) is trivial and, if this is the case, it produces a straight-line program of size \(s^{O (1)}\) \(d^{O (n)}\) and depth \(O (n^ 4 \log^ 2 sd)\) in the function field \(k(x_ 1, \dots, x_ n)\) which computes polynomials \(p_ 1, \dots, p_ s\) of \(k[x_ 1, \dots, x_ n]\) of degree \(d^{O (n^ 2)}\) satisfying \(1 = \sum_{1 \leq j \leq s} p_ j f_ j\).


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] J. L. Balcázar, J. Díaz, and J. Gabarró,Structural Complexity I, EATCS Monographs on Theoretical Computer Science11, Springer, 1988.
[2] S. J. Berkowitz, On computing the determinant in small parallel time using a small number of processors,Inform. Process. Lett. 18 (1984), 147-150. · Zbl 0541.68019 · doi:10.1016/0020-0190(84)90018-8
[3] W. S. Brown, On Euclid’s algorithm and the computation of polynomial greatest common divisors,J. Assoc. Comput. Mach. 18 (1971), 478-504. · Zbl 0226.65040
[4] D. Brownawell, Bounds for the degrees in the Nullstellensatz,Ann. of Math. (Second Series)126 (1987), 577-591. · Zbl 0641.14001 · doi:10.2307/1971361
[5] L. Caniglia,Complejidad de algoritmos en geometría computacional, Doctoral Thesis, Universidad de Buennos Aires, 1989.
[6] L. Caniglia, A. Galligo, andJ. Heintz, Borne simple 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 (1988), 255-258. · Zbl 0686.14001
[7] L. Caniglia, A. Galligo, and J. Heintz, Some new effectivity bounds in computational geometry, inApplied Algebra, Algebraic Algorithms andError-Correcting Codes, Proc. 6th Intern. Conf. AAECC-6, Rome 1988, T. Mora, ed., Springer LN Comput. Sci.357 (1989), 131-151.
[8] L. Caniglia, J.A. Guccione, and J.J. Guccione, Local membership problems for polynomial ideals, inEffective Methods in Algebraic Geometry, Proc. Intern. Conf. MEGA 90, Castiglioncello 1990, T. Mora and C. Traverso, eds., Progress in Mathematics94, Birkhäuser (1991), 31-45. · Zbl 0709.15007
[9] A. Dickenstein, N. Fitchas, M. Giusti, andC. Sessa, The membership problem for unmixed polynomial ideals is solvable in single exponential time,Discrete Appl. Math. 33 (1991), 73-94,Special issue 7th Intern. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-7, Toulouse 1989. · Zbl 0747.13018 · doi:10.1016/0166-218X(91)90109-A
[10] N. Fitchas andA. Galligo, Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel,Math. Nachr. 149 (1990), 231-253. · Zbl 0729.14001 · doi:10.1002/mana.19901490118
[11] J. von zur Gathen, Parallel arithmetic computations: a survey, inProc. 13th Symp. MFCS 1986, Springer LN Comput. Sci. 233 (1986), 93-112.
[12] M. Giusti and J. Heintz, Algorithmes?disons rapides?pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionelles, inEffective Methods in Algebraic Geometry, Proc. Intern. Conf. MEGA 90, Castiglioncello 1990, T. Mora and C. Traverso, eds., Progress in Mathematics94, Birkhäuser (1991a), 169-193.
[13] M. Giusti and J. Heintz,La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, Manuscript, Centre de Mathématiques, École Polytechnique, Palaiseau (1991b). To appear inProc. Intern. Meeting on Commutative Algebra, Cortona, Cambridge University Press, 1991.
[14] J. Heintz, Definability and fast quantifier elimination over algebraically closed fields,Theoret. Comput. Sci. 24 (1983), 239-277; Russian translation in:Kyberneti?eskij Sbornik, Novaja Serija, Vyp. 22, Mir Moskva (1985), 113-158. · Zbl 0546.03017 · doi:10.1016/0304-3975(83)90002-6
[15] J. Heintz, On the computational complexity of polynomials and bilinear mappings. A survey, inApplied Algebra, Algebraic Algorithms and Error-Correcting Codes, 5th Intern. Conf. AAECC-5, Menorca 1987, L. Huguet and A. Poli, eds., Springer LN Comput. Sci.356 (1989), 269-300.
[16] J. Heintz and C.P. Schnorr, Testing polynomials which are easy to compute, inLogic and Algorithmic. An International Symposium held in Honour of Ernst Specker, Monographie de l’Enseignement Mathématique, Genève 1982, 237-254; also published in12th Annual ACM Symp. Theory of Computing (1980), 262-268.
[17] J.P. Jouanolou,Théorèmes de Bertini et applications, Progress in Mathematics42, Birkhäuser 1983. · Zbl 0519.14002
[18] H. Kobayashi, S. Moritsugu and R.W. Hogan, On solving systems of algebraic equations, inProc. Intern. Symp. on Symbolic and Algebraic Computation, ISSAC 88, Rome 1988, P. Gianni, ed., Springer LN Comp. Sci.358 (1989).
[19] J. Kollár, Sharp effective Nullstellensatz,J. Amer. Math. Soc. 1 (1988), 963-975. · doi:10.1090/S0894-0347-1988-0944576-7
[20] T.Y. Lam,Serre’s Conjecture, Springer LN Math.635 (1978). · Zbl 0373.13004
[21] H. Matsumura,Commutative ring theory, Cambridge Studies in Advanced Mathematics8, Cambridge University Press, Cambridge 1989.
[22] K. Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field,Combinatorica 7 (1987), 101-104. · Zbl 0635.65040 · doi:10.1007/BF02579205
[23] F. Rossi and W. Spangher, Some effective methods in the openness of loci for Cohen-Macaulay and Gorenstein properties, inEffective Methods in Algebraic Geometry, Proc. Intern. Conf. MEGA 90, Castiglioncello 1990, T. Mora and C. Traverso, eds., Progress in Mathematics94, Birkhäuser (1990), 441-455. · Zbl 0742.14040
[24] H.-J. Stoss, On the representation of rational functions of bounded complexity,Theoret. Comput. Sci. 64 (1989), 1-13. · Zbl 0679.68099 · doi:10.1016/0304-3975(89)90093-5
[25] V. Strassen, Berechnung und Programm I,Acta Inform. 1 (1972), 320-334. · Zbl 0252.68018 · doi:10.1007/BF00289512
[26] B. Teissier, Résultats récents d’algèbre commutative effective, inSéminaire Bourbaki, Volume 1989/90, Exposé 718, novembre 1989, Astérisque189-190 (1991), 107-131.
[27] L.G. Valiant, S. Skyum, S. Berkowitz andC. Rackoff, Fast parallel computation of polynomials using few processors,SIAM J. Comput. 12 (1983), 641-644. · Zbl 0524.68028 · doi:10.1137/0212043
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.