Toric intersection theory for affine root counting. (English) Zbl 0943.14027
Consider a system of \(n\) polynomial equations in \(n\) variables over an algebraically closed field \(K\), where the occurring monomials are fixed and the coefficients are “generic”. In this paper formulae for the number of roots of such a system in any \(K^*\)-stable subset of the affine space \(K^n\) are given. There are two main results, a recursion over “shifted” and lower-dimensional systems (main theorem I), and an expression for a special situation in terms of mixed volumes (affine point theorem II). The paper also contains a characterization of “genericity” of the coefficients in terms of sparse resultants (main theorem II). Moreover, for the case of affine space minus an arbitrary union of coordinate hyperplanes, the formulae yield upper bounds on the number of possible isolated roots. With some examples, the author illustrates that those bounds are sharper than the ones obtained from previously known results. There are two main new ideas, one is to construct from the Newton-polytopes of the given system a suitable projective toric compactification for \(K^n\), and the other is to consider “shifts” of the modified polytopes to take into account roots in certain coordinate subspaces.
Reviewer: Annette A’Campo-Neuen (Konstanz)
MSC:
| 14N10 | Enumerative problems (combinatorial problems) in algebraic geometry |
| 52A39 | Mixed volumes and related topics in convex geometry |
| 14M25 | Toric varieties, Newton polyhedra, Okounkov bodies |
| 52B20 | Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) |
| 65H10 | Numerical computation of solutions to systems of equations |
References:
| [1] | Bernshtein, D. N., The number of roots of a system of equations, Funct. Anal. Appl., 9, 2, 183-185 (1975), (translated from Russian) · Zbl 0328.32001 |
| [2] | Burago, Yu. D.; Zalgaller, V. A., Geometric Inequalities, (Grundlehren der Mathematischen Wissenschaften, vol. 285 (1988), Springer: Springer Berlin) · Zbl 0436.52009 |
| [3] | Canny, J. F.; Emiris, I. Z., An efficient algorithm for the sparse mixed resultant, (Proc. AAECC. Proc. AAECC, Puerto Rico, May. Proc. AAECC. Proc. AAECC, Puerto Rico, May, Lecture Notes in Computer Science, vol. 263 (1993), Springer: Springer Berlin), 89-104 · Zbl 0789.65034 |
| [4] | Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms, (Undergraduate Texts in Mathematics (1992), Springer: Springer Berlin) · Zbl 0756.13017 |
| [5] | Danilov, V. I., The geometry of Toric varieties, Russian Math. Surveys, 33, 2, 97-154 (1978) · Zbl 0425.14013 |
| [6] | Danilov, V. I.; Khovanskii, A., Newton polyhedra and an algorithm for computing Hodge-Deligne numbers, Math. USSR Ivzestiya, 29, 2, 279-298 (1987) · Zbl 0669.14012 |
| [7] | Dyer, M.; Gritzmann, P.; Hufnagel, A., On the complexity of computing mixed volumes, SIAM J. Comput., 27, 356-400 (1998) · Zbl 0909.68193 |
| [8] | Emiris, I. Z.; Canny, J. F., Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Comput., 20, 117-149 (1995) · Zbl 0843.68036 |
| [9] | Eisenbud, D., Commutative Algebra with a View Toward Algebraic Geometry, (Graduate Texts in Mathematics, vol. 150 (1995), Springer: Springer Berlin) · Zbl 0819.13001 |
| [10] | Emiris, I. Z., sparse elimination and applications in kinematics, (Ph.D. Dissertation (December, 1994), Computer Science Division, U.C. Berkeley), available on-line at |
| [11] | Fulton, W., Introduction to Intersection Theory in Algebraic Geometry, (Regional Conference Series in Mathematics, no. 54 (1984), Amer. Math. Soc: Amer. Math. Soc Providence, RI) |
| [12] | Fulton, W., Intersection Theory (1984), Springer: Springer Berlin · Zbl 0541.14005 |
| [13] | Fulton, W., Introduction to Toric Varieties, (Annals of Mathematics Studies (1993), Princeton University Press: Princeton University Press Princeton, NJ), no. 131 · Zbl 1083.14065 |
| [14] | Gel’fand, I. M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants of polynomials in several variables and triangulations of Newton polytopes, Algebra and Analysis, 2, 1-62 (1990), (translated from Russian) · Zbl 0719.15003 |
| [15] | Gel’fand, I. M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants, Resultants and Multidimensional Determinants (1994), Birkhauser: Birkhauser Boston · Zbl 0827.14036 |
| [16] | Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics: A Foundation for Computer Science (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0836.00001 |
| [17] | Hafner, J. L.; McCurley, K. S., Asymptotically fast triangularization of matrices over rings, SIAM J. Comput., 20, 6, 1068-1083 (1991) · Zbl 0738.68050 |
| [18] | Hartshorne, R., Algebraic Geometry (1977), Springer: Springer Berlin · Zbl 0367.14001 |
| [19] | Huber, B.; Sturmfels, B., A polyhedral method for solving sparse polynomial systems, Math. Comput., 64, 1541-1555 (1995) · Zbl 0849.65030 |
| [20] | Huber, B.; Sturmfels, B., Bernshtein’s theorem in affine space, Discrete Comput. Geom., 17, 137-141 (1998) · Zbl 0891.65055 |
| [21] | Iliopoulos, C. S., Worst case complexity bounds on algorithms for computing the canonical structure of finiter Abelian groups and the Hermite and Smith normal forms of an integer matrix, SIAM J. Comput., 18, 4, 658-669 (1989) · Zbl 0689.68059 |
| [22] | Jacobson, N., Basic Algebra 1 (1985), Freeman: Freeman San Francisco, CA · Zbl 0557.16001 |
| [23] | Kapranov, M. M.; Sturmfels, B.; Zelevinsky, A. V., Chow polytope and general resultants, Duke Math. J., 67, 1, 189-218 (1992) · Zbl 0780.14027 |
| [24] | Kempf, G.; Knudsen, F.; Mumford, D.; Saint-Donat, B., Toroidal Embeddings I, (Lecture Notes in Mathematics, vol. 339 (1973), Springer: Springer Berlin) · Zbl 0271.14017 |
| [25] | Khovanskii, A. G., Newton polyhedra and toroical varieties, Funct. Anal. Appl., 11, 289-296 (1977) · Zbl 0445.14019 |
| [26] | Khovanskii, A. G., Newton polyhedra and the genus of complete intersections, Funct. Anal., 12, 1, 51-61 (1978), (translated from Russian) · Zbl 0387.14012 |
| [27] | Kushnirenko, A. G., A Newton polytope and the number of solutions of a system of \(k\) equations in \(k\) unknowns, Usp. Matem. Nauk., 30, 2, 266-267 (1975) |
| [28] | Kushnirenko, A. G., Newton polytopes and the Bézout theorem, Funct. Anal. Appl., 10, 3, 82-83 (1976), (translated from Russian) · Zbl 0328.32002 |
| [29] | Li, T. Y.; Wang, X., The BKK root count in \(C^n\), Math. Comput., 65, 1477-1484 (1996) · Zbl 0855.65053 |
| [30] | Morgan, A. P.; Sommese, A. J.; Wampler, C. W., A product-decomposition theorem for bounding Bézout numbers, SIAM J. Numer. Anal., 32, 4, 1308-1325 (1995) · Zbl 0854.65038 |
| [31] | Mumford, D., Algebraic Geometry I: Complex Algebraic Varieties (1976), Springer: Springer Berlin · Zbl 0356.14002 |
| [32] | Oda, T., Convex Bodies and Algebraic Geometry: an Introduction to the Theory of Toric Varieties (1988), Springer: Springer Berlin · Zbl 0628.52002 |
| [33] | Parsons, D.; Canny, J. F., Geometric problems in molecular biology and robotics, (Proc. 2nd Int. Conf. on Intelligent Systems for Molecular Biology. Proc. 2nd Int. Conf. on Intelligent Systems for Molecular Biology, Palo Alto, CA (August, 1994)) |
| [34] | Pedersen, P.; Sturmfels, B., Product formulas for sparse resultants and Chow forms, Math. Z., 214, 377-396 (1993) · Zbl 0792.13006 |
| [35] | Rojas, J. M., When can one easily find the number of roots of a nonhomogeneous polynomial system?, (extended abstract presented at the 40th Annual Meeting of the Society for Industrial and Applied Mathematics. extended abstract presented at the 40th Annual Meeting of the Society for Industrial and Applied Mathematics, Los Angeles (July 15-19, 1992)) |
| [36] | Rojas, J. M., A convex geometric approach to counting the roots of a polynomial system, Theoret. Comput. Sci., 133, 1, 105-140 (1994), Additional notes and corrections available on-line at · Zbl 0812.65040 |
| [37] | Rojas, J. M., On the average number of real roots of certain random sparse polynomial systems, (Renegar, J.; Shub, M.; Smale, S. (1996), Amer. Math. Soc: Amer. Math. Soc Providence, RI), 689-699 · Zbl 0857.65055 |
| [38] | Rojas, J. M., Toric Laminations, Sparse Generalized Characteristic Polynomials, and a Refinement of Hilbert’s Tenth Problem, (Foundations of Computational Mathematics, selected papers of a conference, held at IMPA in Rio de Janeiro. Foundations of Computational Mathematics, selected papers of a conference, held at IMPA in Rio de Janeiro, January 1997 (1997), Springer: Springer Berlin) · Zbl 0911.13012 |
| [39] | J.M. Rojas, The geometry of elimination I: degree formulae and the vanishing of resultants, preprint.; J.M. Rojas, The geometry of elimination I: degree formulae and the vanishing of resultants, preprint. |
| [40] | Rojas, J. M., Affine elimination theory, (Proc. Conf. in Honor of the 60th Birthday of David A. Buchsbaum (October 1997), Northeastern University), (extended abstract) · Zbl 0943.14027 |
| [41] | Rojas, J. M.; Wang, X., Counting affine roots of polynomial systems via pointed Newton polytopes, J. Complexity, 12, 116-133 (1996) · Zbl 0885.12007 |
| [42] | Schneider, R., Convex Bodies: The Brunn-Minkowski Theory, (Encyclopedia of Mathematics and its Applications, vol. 44 (1994), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 1287.52001 |
| [43] | Shafarevich, I. N., Basic Algebraic Geometry (1980), Springer: Springer Berlin |
| [44] | Shub, M., Some remarks on Bézout’s theorem and complexity theory, (From Topology to Computation: Proc. Smalefest (1993), Springer: Springer Berlin), 443-455 · Zbl 0811.13021 |
| [45] | Silverman, J., The Arithmetic of Elliptic Curves, (Springer Graduate Texts in Mathematics, vol. 106 (1986), Springer: Springer Berlin) · Zbl 0585.14026 |
| [46] | Sturmfels, B., More examples of Å-resultants (1992), letter to Misha Kapranov |
| [47] | Sturmfels, B., Sparse elimination theory, (Eisenbud, D.; Robbiano, L., Proc. Computat. Algebraic Geom. and Commut. Algebra. Proc. Computat. Algebraic Geom. and Commut. Algebra, 1991, Cortona, Italy (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 377-396 |
| [48] | Sturmfels, B., On the Newton polytope of the resultant, J. Algebraic Combinatorics, 3, 207-236 (1994) · Zbl 0798.05074 |
| [49] | Sturmfels, B., Gröbner bases and convex polytopes, (Lectures presented at the Holiday Symposium at New Mexico State University (27-31 December 1994)) · Zbl 0856.13020 |
| [50] | Sturmfels, B.; Zelevinsky, A., Multigradd resultants of Sylvester type, J. Algebra, 163, 1, 115-127 (1994) · Zbl 0813.13018 |
| [51] | Verschelde, J., Homotopy continuation methods for solving polynomial systems, (Doctoral Dissertation (May 1996), Katholieke Universiteit Leuven: Katholieke Universiteit Leuven Leuven, Belgium) |
| [52] | Verschelde, J.; Gatermann, K.; Cools, R., Mixed volume computation by dynamic lifting applied to polynomial system solving, Discrete Comput. Geom., 16, 1, 69-112 (1996) · Zbl 0854.68111 |
| [53] | Wampler, C. W., Bezout number calculations for multi-homogeneous polynomial systems, Appl. Math. Comput., 51, 143-157 (1992) · Zbl 0759.65023 |
| [54] | Warren, A bound on the implicit degree of polygonal Bézier surfaces, in: C.L. Bajaj (Ed.), Algebraic Geometry and its Applications, pp. 513-525.; Warren, A bound on the implicit degree of polygonal Bézier surfaces, in: C.L. Bajaj (Ed.), Algebraic Geometry and its Applications, pp. 513-525. · Zbl 0806.68112 |
| [55] | Emiris, I. Z.; Verschelde, J., How to count efficiently all affine roots of a polynomial system, INRIA Rapport de Recherche no. 3212 (1997) |
| [56] | T. Gao, T.Y. Li, X. Wang, Finding isolated zeroes of polynomial systems in \(C^n\); T. Gao, T.Y. Li, X. Wang, Finding isolated zeroes of polynomial systems in \(C^n\) |
| [57] | Huber, B.; Verschelde, J., Polyhedral end games for polynomial continuation, (Report TW254 (1997), Dept. of Computer Science, K.U. Leuven) · Zbl 0933.65057 |
| [58] | Rojas, J. M., Intrinsic near quadratic complexity bounds for real multivariate root counting, (Proc. 6th Annual European Symp. on Algorithms. Proc. 6th Annual European Symp. on Algorithms, Lecture Notes in Computer Science, vol. 1461 (1998), Springer: Springer Berlin) · Zbl 0929.65028 |
| [59] | J.M. Rojas, Solving degenerate sparse polynomial systems faster, J. Symbolic Comput., special issue on Elimination Theory, to appear.; J.M. Rojas, Solving degenerate sparse polynomial systems faster, J. Symbolic Comput., special issue on Elimination Theory, to appear. · Zbl 0943.65060 |
| [60] | Sturmfels, B., An introduction to resultants, (Applications of Computational Algebraic Geometry. Applications of Computational Algebraic Geometry, Proc. Symp. Appl. Math., vol. 53 (1998), Amer. Math. Soc: Amer. Math. Soc Providence, RI), 25-39, San Diego, CA · Zbl 0916.13008 |
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.
