Amoebas and coamoebas are the logarithmic images of algebraic varieties and the images of algebraic varieties under the arg-map, respectively. We present new techniques for computational problems on amoebas and coamoebas, thus establishing new connections between (co-)amoebas, semialgebraic and convex algebraic geometry and semidefinite programming.<\/p>\n
Our approach is based on formulating the membership problem in amoebas (respectively coamoebas) as a suitable real algebraic feasibility problem. Using the real Nullstellensatz, this allows us to tackle the problem by sums of squares techniques and semidefinite programming. Our method yields polynomial identities as certificates of non-containment of a point in an amoeba or coamoeba. As the main theoretical result, we establish some degree bounds on the polynomial certificates. Moreover, we provide some actual computations of amoebas based on the sums of squares approach.<\/p>","DOI":"10.1090\/s0025-5718-2014-02828-7","type":"journal-article","created":{"date-parts":[[2014,3,6]],"date-time":"2014-03-06T14:11:58Z","timestamp":1394115118000},"page":"455-473","source":"Crossref","is-referenced-by-count":12,"title":["Approximating amoebas and coamoebas by sums of squares"],"prefix":"10.1090","volume":"84","author":[{"given":"Thorsten","family":"Theobald","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timo","family":"de Wolff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2014,3,6]]},"reference":[{"key":"1","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03718-8","volume-title":"Real algebraic geometry","volume":"36","author":"Bochnak, Jacek","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540646639"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1006\/aima.1999.1856","article-title":"Laurent determinants and arrangements of hyperplane amoebas","volume":"151","author":"Forsberg, Mikael","year":"2000","journal-title":"Adv. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-8708","issn-type":"print"},{"key":"3","series-title":"Mathematics: Theory \\& Applications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4771-1","volume-title":"Discriminants, resultants, and multidimensional determinants","author":"Gel\u2032fand, I. M.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0817636609"},{"issue":"3","key":"4","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","article-title":"Global optimization with polynomials and the problem of moments","volume":"11","author":"Lasserre, Jean B.","year":"2000","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-0-387-09686-5_7","article-title":"Sums of squares, moment matrices and optimization over polynomials","author":"Laurent, Monique","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387096858"},{"key":"6","doi-asserted-by":"crossref","unstructured":"J.A. De Loera, J. Lee, P.N. Malkin, and S. Margulies, Hilbert\u2019s Nullstellensatz and an algorithm for proving combinatorial infeasibility, Proc. ISSAC 2008, ACM, New York, 2008, pp. 197\u2013206.","DOI":"10.1145\/1390768.1390797"},{"key":"7","doi-asserted-by":"crossref","unstructured":"J. L\u00f6fberg and P. Parrilo, From coefficients to samples: a new approach to SOS optimization, 43rd IEEE Conference on Decision and Control, Atlantis, vol. 3, 2004, pp. 3154\u20133159.","DOI":"10.1109\/CDC.2004.1428957"},{"key":"8","unstructured":"D. Maclagan and B. Sturmfels, Introduction to Tropical Geometry, Manuscript, 2010."},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/0-306-48658-X_6","article-title":"Amoebas of algebraic varieties and tropical geometry","author":"Mikhalkin, Grigory","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0306486571"},{"issue":"5-6","key":"10","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.crma.2010.11.018","article-title":"A toric Positivstellensatz with applications to delay systems","volume":"349","author":"Niculescu, Silviu-Iulian","year":"2011","journal-title":"C. R. Math. Acad. Sci. Paris","ISSN":"https:\/\/id.crossref.org\/issn\/1631-073X","issn-type":"print"},{"key":"11","unstructured":"L. Nilsson, Amoebas, discriminants, and hypergeometric functions, Ph.D. thesis, Stockholm University, 2009."},{"issue":"4","key":"12","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1216\/JCA-2010-2-4-447","article-title":"Discriminant coamoebas in dimension two","volume":"2","author":"Nilsson, Lisa","year":"2010","journal-title":"J. Commut. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/1939-0807","issn-type":"print"},{"issue":"1","key":"13","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s12220-011-9235-7","article-title":"Mellin transforms of multivariate rational functions","volume":"23","author":"Nilsson, Lisa","year":"2013","journal-title":"J. Geom. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1050-6926","issn-type":"print"},{"key":"14","unstructured":"M. Nisse, Geometric and combinatorial structure of hypersurface coamoebas, Preprint, arXiv:0906.2729, 2009."},{"issue":"2","key":"15","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","article-title":"Semidefinite programming relaxations for semialgebraic problems","volume":"96","author":"Parrilo, Pablo A.","year":"2003","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"16","isbn-type":"print","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/10997703_11","article-title":"Exploiting algebraic structure in sum of squares programs","author":"Parrilo, Pablo A.","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/3540239480"},{"key":"17","isbn-type":"print","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/conm\/377\/06997","article-title":"Amoebas: their spines and their contours","author":"Passare, Mikael","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/0821835386"},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/10997703_14","article-title":"SOSTOOLS and its control applications","author":"Prajna, Stephen","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/3540239480"},{"key":"19","series-title":"Springer Monographs in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04648-7","volume-title":"Positive polynomials","author":"Prestel, Alexander","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/3540412158"},{"issue":"3","key":"20","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1215\/00127094-2007-001","article-title":"A Nullstellensatz for amoebas","volume":"141","author":"Purbhoo, Kevin","year":"2008","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"issue":"3","key":"21","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","article-title":"Positive polynomials on compact semi-algebraic sets","volume":"42","author":"Putinar, Mihai","year":"1993","journal-title":"Indiana Univ. Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-2518","issn-type":"print"},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1090\/conm\/377\/06998","article-title":"First steps in tropical geometry","author":"Richter-Gebert, J\u00fcrgen","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/0821835386"},{"issue":"1-4","key":"23","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1080\/10556789908805766","article-title":"Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones","volume":"11\/12","author":"Sturm, Jos F.","year":"1999","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"key":"24","series-title":"CBMS Regional Conference Series in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/097","volume-title":"Solving systems of polynomial equations","volume":"97","author":"Sturmfels, Bernd","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/0821832514"},{"key":"25","unstructured":"J.L. Sun, Low rank decompositions for sum of squares optimization, M.Sc. thesis, M.I.T., 2006."},{"issue":"4","key":"26","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1080\/10586458.2002.10504703","article-title":"Computing amoebas","volume":"11","author":"Theobald, Thorsten","year":"2002","journal-title":"Experiment. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1058-6458","issn-type":"print"},{"key":"27","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.aim.2013.03.001","article-title":"Amoebas of genus at most one","volume":"239","author":"Theobald, Thorsten","year":"2013","journal-title":"Adv. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-8708","issn-type":"print"},{"key":"28","series-title":"International Series in Operations Research \\& Management Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4381-7","volume-title":"Handbook of semidefinite programming","volume":"27","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0792377710"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2015-84-291\/S0025-5718-2014-02828-7\/S0025-5718-2014-02828-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-291\/S0025-5718-2014-02828-7\/S0025-5718-2014-02828-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:12:57Z","timestamp":1776795177000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-291\/S0025-5718-2014-02828-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,6]]},"references-count":28,"journal-issue":{"issue":"291","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["S0025-5718-2014-02828-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2014-02828-7","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2014,3,6]]}}}