Sparse trace tests

Brysiewicz, Taylor; Burr, Michael

doi:10.1090/mcom/3849

Sparse trace tests
HTML articles powered by AMS MathViewer

by Taylor Brysiewicz and Michael Burr

Math. Comp. 92 (2023), 2893-2922

DOI: https://doi.org/10.1090/mcom/3849

Published electronically: May 8, 2023

HTML | PDF | Request permission

Abstract:

We establish how the coefficients of a sparse polynomial system influence the sum (or the trace) of its zeros. As an application, we develop numerical tests for verifying whether a set of solutions to a sparse system is complete. These algorithms extend the classical trace test in numerical algebraic geometry. Our results rely on both the analysis of the structure of sparse resultants as well as an extension of Esterov’s results on monodromy groups of sparse systems.

References

D. N. Bernstein, The number of roots of a system of equations, Funkcional. Anal. i Priložen. 9 (1975), no. 3, 1–4 (Russian). MR 435072
Taylor Brysiewicz, Jose Israel Rodriguez, Frank Sottile, and Thomas Yahl, Solving decomposable sparse systems, Numer. Algorithms 88 (2021), no. 1, 453–474. MR 4297926, DOI 10.1007/s11075-020-01045-x
David A. Cox, John B. Little, and Henry K. Schenck, Toric varieties, Graduate Studies in Mathematics, vol. 124, American Mathematical Society, Providence, RI, 2011. MR 2810322, DOI 10.1090/gsm/124
Carlos D’Andrea and Gabriela Jeronimo, Rational formulas for traces in zero-dimensional algebras, Appl. Algebra Engrg. Comm. Comput. 19 (2008), no. 6, 495–508. MR 2566145, DOI 10.1007/s00200-008-0085-x
Carlos D’Andrea and Martín Sombra, A Poisson formula for the sparse resultant, Proc. Lond. Math. Soc. (3) 110 (2015), no. 4, 932–964. MR 3335291, DOI 10.1112/plms/pdu069
A. Esterov, Galois theory for general systems of polynomial equations, Compos. Math. 155 (2019), no. 2, 229–245. MR 3896565, DOI 10.1112/s0010437x18007868
A. Esterov and L. Lang, Sparse polynomial equations and other enumerative problems whose Galois groups are wreath products, Selecta Math. (N.S.) 28 (2022), no. 2, Paper No. 22, 35. MR 4357477, DOI 10.1007/s00029-021-00741-3
Günter Ewald, Combinatorial convexity and algebraic geometry, Graduate Texts in Mathematics, vol. 168, Springer-Verlag, New York, 1996. MR 1418400, DOI 10.1007/978-1-4612-4044-0
D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
Joe Harris, Galois groups of enumerative problems, Duke Math. J. 46 (1979), no. 4, 685–724. MR 552521
Jonathan D. Hauenstein and Jose Israel Rodriguez, Multiprojective witness sets and a trace test, Adv. Geom. 20 (2020), no. 3, 297–318. MR 4121336, DOI 10.1515/advgeom-2020-0006
A. G. Khovanskiĭ, Newton polyhedra and irreducible components of complete intersections, Izv. Ross. Akad. Nauk Ser. Mat. 80 (2016), no. 1, 281–304 (Russian, with Russian summary); English transl., Izv. Math. 80 (2016), no. 1, 263–284. MR 3462682, DOI 10.4213/im8307
A. G. Kušnirenko, Newton polyhedra and Bezout’s theorem, Funkcional. Anal. i Priložen. 10 (1976), no. 3, 82–83 (Russian). MR 422272
Anton Leykin, Jose Israel Rodriguez, and Frank Sottile, Trace test, Arnold Math. J. 4 (2018), no. 1, 113–125. MR 3810571, DOI 10.1007/s40598-018-0084-3
Gregorio Malajovich, Computing mixed volume and all mixed cells in quermassintegral time, Found. Comput. Math. 17 (2017), no. 5, 1293–1334. MR 3709333, DOI 10.1007/s10208-016-9320-1
Manfred Minimair, Sparse resultant under vanishing coefficients, J. Algebraic Combin. 18 (2003), no. 1, 53–73. MR 2002220, DOI 10.1023/A:1025169426299
J. Maurice Rojas, A convex geometric approach to counting the roots of a polynomial system, Theoret. Comput. Sci. 133 (1994), no. 1, 105–140. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294429, DOI 10.1016/0304-3975(93)00062-A
Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, Symmetric functions applied to decomposing solution sets of polynomial systems, SIAM J. Numer. Anal. 40 (2002), no. 6, 2026–2046 (2003). MR 1974173, DOI 10.1137/S0036142901397101
Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, Introduction to numerical algebraic geometry, Solving polynomial equations, Algorithms Comput. Math., vol. 14, Springer, Berlin, 2005, pp. 301–335. MR 2161992, DOI 10.1007/3-540-27357-3_{8}
Andrew J. Sommese and Charles W. Wampler, Numerical algebraic geometry, The mathematics of numerical analysis (Park City, UT, 1995) Lectures in Appl. Math., vol. 32, Amer. Math. Soc., Providence, RI, 1996, pp. 749–763. MR 1421365
Frank Sottile, General witness sets for numerical algebraic geometry, ISSAC’20—Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, ACM, New York, [2020] ©2020, pp. 418–425. MR 4144068, DOI 10.1145/3373207.3403995
F. Sottile and T. Yahl, Galois groups in enumerative geometry and applications, 2021. arXiv:2108.07905.
G. Staglianò, SparseResultants: computations with sparse resultants. Version 1.1. A Macaulay2 package available at https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages.
Bernd Sturmfels, On the Newton polytope of the resultant, J. Algebraic Combin. 3 (1994), no. 2, 207–236. MR 1268576, DOI 10.1023/A:1022497624378
Oscar Zariski, A theorem on the Poincaré group of an algebraic hypersurface, Ann. of Math. (2) 38 (1937), no. 1, 131–141. MR 1503330, DOI 10.2307/1968515