×

Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces. (English) Zbl 1420.14135

Summary: Given any complex Laurent polynomial \(f\), \(\text{Amoeba}(f)\) is the image of its complex zero set under the coordinate-wise log absolute value map. We discuss an efficiently constructible polyhedral approximation, \(\text{ArchTrop}(f)\), of \(\text{Amoeba}(f)\), and derive explicit upper and lower bounds, solely as a function of the number of monomial terms of \(f\), for the Hausdorff distance between these two sets. We also show that deciding whether a given point lies in \(\text{ArchTrop}(f)\) is doable in polynomial-time, for any fixed dimension, unlike the corresponding problem for \(\text{Amoeba}(f)\), which is \(\mathbf{NP}\)-hard already in one variable. \(\text{ArchTrop}(f)\) can thus serve as a canonical low order approximation to start a higher order iterative polynomial system solving algorithm, e.g., homotopy continuation.

MSC:

14T05 Tropical geometry (MSC2010)
14Q10 Computational aspects of algebraic surfaces
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
52B11 \(n\)-dimensional polytopes
03D78 Computation over the reals, computable analysis
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Akian, Marianne; Gaubert, Stephane; Sharify, Meisam, Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots, Linear Algebra Appl., 528, 394-435 (2017) · Zbl 1428.15009
[2] Amini, Omid; Baker, Matthew; Faber, Xander, Tropical and Non-Archimedean geometry, (Proceedings of Bellairs Workshop on Tropical and Non-Archimedean Geometry (May 6-13, 2011, Barbados). Proceedings of Bellairs Workshop on Tropical and Non-Archimedean Geometry (May 6-13, 2011, Barbados), Contemp. Math., vol. 605 (2013), AMS Press) · Zbl 1281.14002
[3] Anthony, Eleanor; Grant, Sheridan; Gritzmann, Peter; Maurice Rojas, J., (Bennett, Janine; Vivodtzev, Fabien; Pascucci, Valerio, Polynomial-time Amoeba Neighborhood Membership and Faster Localized Solving. Polynomial-time Amoeba Neighborhood Membership and Faster Localized Solving, Topological and Statistical Methods for Complex Data-Tackling Large-Scale, High-Dimensional, and Multivariate Data Sets (2015), Springer-Verlag), 255-278, (chapter 15) series on Mathematics and Visualization · Zbl 1312.65080
[4] Arora, Sanjeev; Barak, Boaz, Computational Complexity. a Modern Approach (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1193.68112
[5] Bach, Eric; Shallit, Jeff, Algorithmic Number Theory, Vol. I: Efficient Algorithms (1996), MIT Press: MIT Press Cambridge, MA · Zbl 0873.11070
[6] Baker, Alan, The theory of linear forms in logarithms, (Transcendence Theory: Advances and Applications: Proceedings of a Conference Held at the University of Cambridge (1977), Academic Press: Academic Press Cambridge), Jan.-Feb., 1976
[7] Baker, Matthew; Rumely, Robert, (Potential Theory and Dynamics on the Berkovich Projective Line. Potential Theory and Dynamics on the Berkovich Projective Line, Mathematical Surveys and Monographs, vol. 159 (2010), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 1196.14002
[8] Bastani, Osbert; Hillar, Chris; Popov, Dimitar; Maurice Rojas, J., Randomization, sums of squares, and faster real root counting for tetranomials and beyond, (Randomization, Relaxation, and Complexity in Polynomial Equation Solving. Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics, vol. 556 (2011), AMS Press), 145-166 · Zbl 1239.14051
[9] Ben-Or, Michael; Kozen, Dexter; Reif, John, The complexity of elementary algebra and geometry, J. Comput. System Sci., 32, 251-264 (1986) · Zbl 0634.03031
[10] Bergman, George M., The logarithmic limit-set of an algebraic variety, Trans. Amer. Math. Soc., 157, 459-469 (1971) · Zbl 0197.17102
[11] Bernshtein, David N., The number of roots of a system of equations, Funct. Anal. Appl., 9, 2, 183-185 (1975), (translated from Russian)
[12] Daniel J. Bernstein, Computing Logarithm Intervals with the Arithmetic-Geometric Mean Iterations, available from http://cr.yp.to/papers.html; Daniel J. Bernstein, Computing Logarithm Intervals with the Arithmetic-Geometric Mean Iterations, available from http://cr.yp.to/papers.html
[13] Bihan, Frederic; Maurice Rojas, J.; Stella, Casey E., Faster real feasibility via circuit discriminants, (Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC 2009, July 28-31, Seoul, Korea) (2009), ACM Press), 39-46 · Zbl 1237.68251
[14] Canny, John F., Some algebraic and geometric computations in PSPACE, (Proc. 20th ACM Symp. Theory of Computing (1988), ACM Press: ACM Press Chicago)
[15] Cohen, Paul J., Decision procedures for real and \(p\)-adic fields, Comm. Pure Appl. Math., 22, 131-151 (1969) · Zbl 0167.01502
[16] De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco, (Triangulations, Structures for Algorithms and Applications. Triangulations, Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, vol. 25 (2010), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1207.52002
[17] Dumas, G., Sur quelques cas d’irréductibilité des polynômes à coefficients rationnels, J. Math. (6), 2, 191-258 (1906) · JFM 37.0096.01
[18] Edelsbrunner, Herbert, (Algorithms in Combinatorial Geometry. Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, vol. 10 (1987), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0634.52001
[19] Einsiedler, Manfred; Kapranov, Mikhail; Lind, Douglas, Non-archimedean amoebas and tropical varieties, J. Die Reine Angew. Math. (Crelles J.), 601, 139-157 (2006) · Zbl 1115.14051
[20] Engler, Antonio J.; Prestel, Alexander, (Valued Fields. Valued Fields, Springer Monographs in Mathematics (2005), Springer-Verlag: Springer-Verlag Berlin Heidelberg)
[21] Forsberg, Mikael, Amoebas and Laurent Series (1998), Royal Institute of Technology: Royal Institute of Technology Stockholm, Sweden, (Doctoral Thesis)
[22] Jens Forsgård, Laura Matusevich, Nathan Melhop, Timo de Wolff, Lopsided approximation of amoebas, Math. Comput., in press. http://dx.doi.org/10.1090/mcom/3323; Jens Forsgård, Laura Matusevich, Nathan Melhop, Timo de Wolff, Lopsided approximation of amoebas, Math. Comput., in press. http://dx.doi.org/10.1090/mcom/3323
[23] Fujiwara, M., Über die obere Schranke des absoluten Betrags der Wurzeln einer algebraischen Gleichung, Tôhoku Math. J., 10, 167-171 (1916) · JFM 46.0123.01
[24] Gel’fand, Israel Moseyevitch; Kapranov, Mikhail M.; Zelevinsky, Andrei V., Discriminants, Resultants and Multidimensional Determinants (1994), Birkhäuser: Birkhäuser Boston · Zbl 0827.14036
[25] Hadamard, Jacques, Étude sur les propriétés des fonctions entières et en particulier d’une fonction considérée par Riemann, J. Math. Pures Appl. 4ième Sér., 9, 171-216 (1893) · JFM 25.0698.03
[26] Hans Rullgård, Mikael Passare, Amoebas, Monge-Ampère measures, and triangulations of the Newton polytope, Duke Math. J., 121, 3, 481-507 (2004) · Zbl 1043.32001
[27] Hardy, Godrey Harold; Wright, Edward W.; Wiles, Andrew, (Heath-Brown, Roger; Silverman, Joseph, An Introduction to the Theory of Numbers (2008), Oxford University Press)
[28] Hartmanis, J.; Stearns, R. E., On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117, 285-306 (1965) · Zbl 0131.15404
[29] Itenberg, Ilia; Mikhalkin, Grigory; Shustin, Eugenii, (Tropical Algebraic Geometry. Tropical Algebraic Geometry, Oberwolfach Seminars, vol. 35 (2009), Birkhäuser Verlag: Birkhäuser Verlag Basel) · Zbl 1165.14002
[30] Litvinov, G. L.; Maslov, V. P.; Shpiz, G. B., Idempotent functional analysis, An algebraic approach, Mat. Zametki, 69, 5, 758-797 (2001) · Zbl 1017.46034
[31] Tropical and idempotent mathematics, (Litvinov, G. L.; Sergeev, S. N., International Workshop TROPICAL-07, Tropical and Idempotent Mathematics, Aug. 25-30, Independent University. International Workshop TROPICAL-07, Tropical and Idempotent Mathematics, Aug. 25-30, Independent University, Contemporary Mathematics, vol. 495 (2009))
[32] Maclagan, Diane; Sturmfels, Bernd, (Introduction To Tropical Geometry. Introduction To Tropical Geometry, Graduate Studies in Mathematics, vol. 161 (2015), AMS Press) · Zbl 1321.14048
[33] Victor P. Maslov, On a new superposition principle for optimization problem, Séminaire Équations aux dérivées partielles (Centre Mathématiques de l’École Polytechnique, Palaiseau), 1985-1986, exposé 24: pp. 1-14.; Victor P. Maslov, On a new superposition principle for optimization problem, Séminaire Équations aux dérivées partielles (Centre Mathématiques de l’École Polytechnique, Palaiseau), 1985-1986, exposé 24: pp. 1-14.
[34] Matveev, E. M., An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers, II, Izv. Ross. Akad. Nauk Ser. Mat., 64, 6, 125-180 (2000), translation in Izv. Math. 64 2000, 6, 1217-1269 · Zbl 1013.11043
[35] Mikhalkin, Grigory, Decomposition into pairs-of-pants for complex algebraic hypersurfaces, Topology, 43, 5, 1035-1065 (2004) · Zbl 1065.14056
[36] Mikhalkin, Grigory, Enumerative tropical algebraic geometry in \(R^2\), J. Amer. Math. Soc., 18, 2, 313-377 (2005) · Zbl 1092.14068
[37] Montel, Paul, Sur les modules des zéros des polnômes, Ann. Sci. l’École Norm. Sup. (3), 40, 1-34 (1923) · JFM 49.0046.01
[38] Nesterenko, Yuri, Linear forms in logarithms of rational numbers, (Diophantine Approximation. Diophantine Approximation, (Cetraro, 2000). Diophantine Approximation. Diophantine Approximation, (Cetraro, 2000), Lecture Notes in Math., vol. 1819 (2003), Springer: Springer Berlin), 53-106 · Zbl 1044.11069
[39] Newton, Isaac, Letter To Henry Oldenburg Dated 1676 Oct 24, the Correspondence of Isaac Newton, II, 126-127 (1960), Cambridge University Press
[40] Ostrowski, Alexandre, Addition Á notre mémoire: ‘Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent, Acta Math., 72, 183-186 (1940) · Zbl 0028.19901
[41] Ostrowski, Alexandre, Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent, Acta Math., 72, 99-155 (1940) · Zbl 0023.33403
[42] Papadimitriou, Christos H., Comput. Complexity (1995), Addison-Wesley
[43] Passare, Mikael; Maurice Rojas, J.; Shapiro, Boris, New multiplier sequences via discriminant amoebae, Mosc. Math. J., 11, 3, 547-560 (2011), (special issue in memory of Vladimir Igorevich Arnold), July-Sept · Zbl 1290.12001
[44] Passare, Mikael; Tsikh, August, Amoebas: their spines and their contours, (Idempotent Mathematics and Mathematical Physics. Idempotent Mathematics and Mathematical Physics, Contemporary Mathematics, vol. 377 (2005), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 275-288 · Zbl 1079.32008
[45] Pellet, M. A., Sur un mode de séparation des racines des équations et la formule de Lagrange, Bull. Sci. Math., 5, 393-395 (1881) · JFM 13.0074.01
[46] Pin, Jean-Eric, Tropical semirings, (Idempotency, Vol. 11. Idempotency, Vol. 11, (Bristol, 1994) (1998), Publ. Newton Inst.), 50-69 · Zbl 0909.16028
[47] Plaisted, David A., New NP-hard and NP-complete polynomial and integer divisibility problems, Theoret. Comput. Sci., 31, 1-2, 125-138 (1984) · Zbl 0572.68027
[48] Purbhoo, Kevin, A nullstellensatz for amoebas, Duke Math. J., 141, 3, 407-445 (2008) · Zbl 1233.14036
[49] Rahman, Q. I.; Schmeisser, G., (Analytic Theory of Polynomials. Analytic Theory of Polynomials, London Mathematical Society Monographs, vol. 26 (2002), Oxford Science Publications) · Zbl 1072.30006
[50] J.M. Robson, The complexity of Go, in: Information Processing; Proceedings of IFIP Congress, 1983, pp. 413-417.; J.M. Robson, The complexity of Go, in: Information Processing; Proceedings of IFIP Congress, 1983, pp. 413-417.
[51] Rullgård, Hans, Topics in Geometry, Analysis and Inverse Problems (2003), Department of Mathematics, Stockholm University: Department of Mathematics, Stockholm University Sweden, Downloadable from http://su.diva-portal.org/smash/record.jsf?pid=diva2:190169
[52] Franziska Schroeter, Timo de Wolff, The Boundary of Amoebas, Math ArXiV preprint 1310.7363.; Franziska Schroeter, Timo de Wolff, The Boundary of Amoebas, Math ArXiV preprint 1310.7363.
[53] Schwartz, Jacob T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 701-717 (1980) · Zbl 0452.68050
[54] Sipser, Michael, The history and status of the \(P\) versus \(NP\) question, (Proceedings STOC’92 (Twenty-Fourth Annual ACM Symposium on Theory of Computing) (1992), ACM Press), 603-618
[55] Sipser, Michael, Introduction To the Theory of Computation (2012), Cengage Learning · Zbl 1191.68311
[56] Neil Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org; Neil Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org · Zbl 1159.11327
[57] Tarski, Alfred, A Decision Method for Elementary Algebra and Geometry, Prepared for Publication By J. C. C. McKinsey (1951), University of California Press: University of California Press Berkeley and Los Angeles, California · Zbl 0035.00602
[58] Theobald, Thorsten, Computing Amoebas, Experiment. Math., 11, 4, 513-526 (2002) · Zbl 1100.14048
[59] Theobald, Thorsten; Wolff, Timo de, Amoebas of genus at most one, Adv. Math., 239, 190-213 (2013) · Zbl 1330.14090
[60] Theobald, Thorsten; Wolff, Timo de, Approximating amoebas and coamoebas by sums of squares, Math. Comp., 84, 455-473 (2015) · Zbl 1318.14054
[61] Valiron, Georges, Fonctions Analytiques (1954), Presses Universitataires de France: Presses Universitataires de France Paris
[62] Oleg Ya Viro, Dequantization of Real Algebraic Geometry on a Logarithmic Paper, Proceedings of the 3rd European Congress of Mathematicians, Birkhäuser, Progress in Math, Vol. 201, 2001, pp. 135-146.; Oleg Ya Viro, Dequantization of Real Algebraic Geometry on a Logarithmic Paper, Proceedings of the 3rd European Congress of Mathematicians, Birkhäuser, Progress in Math, Vol. 201, 2001, pp. 135-146. · Zbl 1024.14026
[63] Weiss, Edwin, Algebraic Number Theory (1963), McGraw-Hill · Zbl 0115.03601
[64] Ziegler, Gunter M., (Lectures on Polytopes. Lectures on Polytopes, Graduate Texts in Mathematics (1995), Springer Verlag) · Zbl 0823.52002
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.