A sparse effective Nullstellensatz. (English) Zbl 0933.14001
Let \(k\) be a field, \(\overline k\) its algebraic closure, \(\mathbb{A}^n\) the affine \(n\)-space over \(\overline k\). Let \(f_1,\dots, f_s\in k[X_1, \dots, X_n,X_1^{-1}, \dots,X_n^{-1}]\) be Laurent polynomials. The support of the set \(f_1, \dots, f_s\) is the set of exponents of all non-zero monomials of all the \(f_i\). The Newton polytope \(N(f_1, \dots, f_s)\) is the convex hull of the support and the unmixed volume \(U(f_1, \dots, f_s)\) is \(\rho\)! times the volume of \(N(f_1,\dots,f_s)\), where \(\rho\) is the dimension of the polytope. The main result of the paper shows that if \(f_1, \dots, f_s\in k[X_1, \dots, X_n]\) without common zeroes in \(\mathbb{A}^n\), there are \(g_1, \dots, g_s\in k[X_1, \dots, X_n]\) such that \(\sum^s_{i=1} g_if_i=1\) and \(N(g_if_i) \subseteq (n^{n+3} U)N\), \(i=1, \dots,s\). An analogous result is obtained for the case of Laurent polynomials. Several applications are given.
Reviewer: Christodor-Paul Ionescu (Bucureşti)
MSC:
| 14A05 | Relevant commutative algebra |
| 13F20 | Polynomial rings and ideals; rings of integer-valued polynomials |
References:
| [1] | Almeida, M. S., Función de Hilbert de álgebras graduadas y Nullstellensatz afı́n efectivo. Función de Hilbert de álgebras graduadas y Nullstellensatz afı́n efectivo, Tesis de Licenciatura (1995), Univ. Buenos Aires |
| [2] | Amoroso, F., On a conjecture of C. Berenstein and A. Yger, Algorithms in Algebraic Geometry and Applications, Proceedings MEGA’94. Algorithms in Algebraic Geometry and Applications, Proceedings MEGA’94, Birkhäuser Progress in Math., 143 (1996), Birkhäuser: Birkhäuser Basel, p. 17-28 · Zbl 0866.13008 |
| [3] | Berenstein, C. A.; Struppa, D. C., Recent improvements in the complexity of the effective Nullstellensatz, Linear Alg. Appl., 157, 203-215 (1991) · Zbl 0759.13012 |
| [4] | Berenstein, C. A.; Yger, A., Effective Bézout identities in \(Q[x_1 x_n ]\), Acta Math., 166, 69-120 (1991) · Zbl 0724.32002 |
| [5] | Bernshtein, D. N., The number of roots of a system of equations, Functional Anal. Appl., 9, 183-185 (1975) · Zbl 0328.32001 |
| [6] | Brownawell, W. D., Bounds for the degrees in the Nullstellensatz, Ann. Math., 126, 577-591 (1987) · Zbl 0641.14001 |
| [7] | Brownawell, W. D.; Masser, D. W., Multiplicity estimates for analytic functions II, Duke J. Math., 47, 273-295 (1980) · Zbl 0461.10027 |
| [8] | Caniglia, L.; Galligo, A.; Heintz, J., Some new effectivity bounds in computational geometry, (Mora, T., Proceedings AAECC-6. Proceedings AAECC-6, Lecture Notes in Computer Science, 357 (1989), Springer: Springer Berlin), 131-151 · Zbl 0685.68044 |
| [9] | J. Canny, I. Emiris, A subdivision-based algorithm for the sparse resultant, 1996; J. Canny, I. Emiris, A subdivision-based algorithm for the sparse resultant, 1996 |
| [10] | Danilov, V. I., The geometry of toric varieties, Russian Math. Surveys, 33, 97-154 (1978) · Zbl 0425.14013 |
| [11] | Dubé, T. W., A combinatorial proof of the effective Nullstellensatz, J. Symb. Comp., 15, 277-296 (1993) · Zbl 0783.13023 |
| [12] | Ewald, G.; Wessels, U., On the ampleness of invertible sheaves in complete toric varieties, Results Math., 25, 275-278 (1991) · Zbl 0739.14031 |
| [13] | Fitchas, N.; Galligo, A., Nullstellensatz effectif et conjecture de Sèrre (théorème de Quillen-Suslin) pour le Calcul Formel, Math. Nachr., 149, 231-253 (1990) · Zbl 0729.14001 |
| [14] | Fulton, W., Introduction to Toric Varieties. Introduction to Toric Varieties, Ann. Math. Studies, 131 (1993), Princeton Univ. Press: Princeton Univ. Press Princeton · Zbl 0813.14039 |
| [15] | Giusti, M.; Hägele, K.; Heintz, J.; Montaña, J. L.; Morais, J. E.; Pardo, L. M., Lower bounds for diophantine approximation, J. Pure Appl. Algebra, 117 & 118, 277-317 (1997) · Zbl 0871.68101 |
| [16] | Giusti, M.; Heintz, J.; Morais, J. E.; Morgenstern, J.; Pardo, L. M., Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124, 101-146 (1998) · Zbl 0944.12004 |
| [17] | K. Hägele, J. E. Morais, L. M. Pardo, M. Sombra, On the intrinsic complexity of the arithmetic Nullstellensatz, J. Pure Appl. Algebra; K. Hägele, J. E. Morais, L. M. Pardo, M. Sombra, On the intrinsic complexity of the arithmetic Nullstellensatz, J. Pure Appl. Algebra · Zbl 0971.14042 |
| [18] | Harris, J., Algebraic Geometry: A First Course. Algebraic Geometry: A First Course, Graduate Texts in Math., 133 (1992), Springer: Springer Berlin · Zbl 0779.14001 |
| [19] | Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., 24, 239-277 (1983) · Zbl 0546.03017 |
| [20] | Huber, B.; Sturmfels, B., A polyhedral method for solving sparse polynomial systems, Math. Comp., 64, 1541-1555 (1995) · Zbl 0849.65030 |
| [21] | Kollár, J., Sharp effective Nullstellensatz, J. Amer. Math. Soc., 1, 963-975 (1988) · Zbl 0682.14001 |
| [22] | Krick, T.; Pardo, L. M., A computational method for diophantine approximation, (González-Vega, L.; Recio, T., Algorithms in Algebraic Geometry and Applications, Proceedings MEGA’94. Algorithms in Algebraic Geometry and Applications, Proceedings MEGA’94, Birkhäuser Progress in Math., 143 (1996), Birkhäuser: Birkhäuser Basel), 193-253 · Zbl 0878.11043 |
| [23] | Krick, T.; Sabia, J.; Solernó, P., On intrinsic bounds in the Nullstellensatz, AAECC J., 8, 125-134 (1997) · Zbl 0897.13021 |
| [24] | Kushnirenko, A. G., Newton polytopes and the Bézout theorem, Functional Anal. Appl., 10, 82-83 (1976) · Zbl 0328.32002 |
| [25] | Matsumura, H., Commutative Ring Theory (1986), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0603.13001 |
| [26] | Pardo, L. M., How upper and lower bounds meet in elimination theory, (Cohen, G.; Giusti, M.; Mora, T., Proceedings AAECC-11. Proceedings AAECC-11, Lecture Notes in Computer Science, 948 (1995), Springer: Springer Berlin), 33-69 · Zbl 0899.68054 |
| [27] | Philippon, P., Dénominateurs dans le théorème des zeros de Hilbert, Acta Arith., 58, 1-25 (1990) · Zbl 0679.13010 |
| [28] | J. M. Rojas, Toric generalized characteristic polynomials, 1997; J. M. Rojas, Toric generalized characteristic polynomials, 1997 · Zbl 0911.13012 |
| [29] | Rojas, J. M., Toric laminations, sparse generalized characteristic polynomials, and a refinement of Hilbert’s tenth problem, (Cucker, F.; Shub, M., Foundations of Computational Mathematics (1997), Springer: Springer Berlin), 369-381 · Zbl 0911.13012 |
| [30] | Sabia, J.; Solernó, P., Bounds for traces in complete intersections and degrees in the Nullstellensatz, AAECC J., 6, 353-376 (1995) · Zbl 0844.14018 |
| [31] | Shiffman, B., Degree bounds for the division problem in polynomial ideals, Michigan Math. J., 36, 163-171 (1989) · Zbl 0691.12010 |
| [32] | F. Smietanski, Quelques bornes effectives pour le théorème des zéros avec paramètres, Univ. Nice-Sophia Antipolis, 1994; F. Smietanski, Quelques bornes effectives pour le théorème des zéros avec paramètres, Univ. Nice-Sophia Antipolis, 1994 |
| [33] | Sombra, M., Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz, J. Pure Appl. Algebra, 117 & 118, 565-599 (1997) · Zbl 0928.14002 |
| [34] | Sturmfels, B., Sparse elimination theory, (Eisenbud, D.; Robbiano, L., Proceedings of the Cortona conference on computational algebraic geometry and commutative algebra. Proceedings of the Cortona conference on computational algebraic geometry and commutative algebra, Symposia Matematica XXXIV, Ist. Naz. di Alta Matematica (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 377-396 |
| [35] | Sturmfels, B., Gröbner bases and convex polytopes, Amer. Math. Soc., 8 (1996) · Zbl 0856.13020 |
| [36] | Teissier, B., Résultats récents d’algèbre commutative effective (1991), Soc. Math. France, p. 107-131 · Zbl 0743.13017 |
| [37] | Verschelde, J.; Verlinden, P.; Cools, R., Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal., 31, 915-930 (1994) · Zbl 0809.65048 |
| [38] | Vogel, W., Lectures on results on Bézout theorem. Lectures on results on Bézout theorem, Tata Lecture Notes, 74 (1984), Springer: Springer Berlin · Zbl 0553.14022 |
| [39] | Zariski, O.; Samuel, P., Commutative Algebra (1958, 1960), Van Nostrand: Van Nostrand New York · Zbl 0081.26501 |
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.
