Metric Estimates and Membership Complexity for Archimedean Amoebae and Tropical Hypersurfaces

Given any complex Laurent polynomial $f$, $\mathrm{A}\mathrm{m}\mathrm{o}\mathrm{e}\mathrm{b}\mathrm{a}(f)$ is the image of its complex zero set under the coordinate-wise log absolute value map. We give an efficiently constructible polyhedral approximation, $\mathrm{A}\mathrm{r}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{T}\mathrm{r}\mathrm{o}\mathrm{p}(f)$, of $\mathrm{A}\mathrm{m}\mathrm{o}\mathrm{e}\mathrm{b}\mathrm{a}(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 $\mathrm{A}\mathrm{r}\mathrm{c}\mathrm{h}\mathrm{T}\mathrm{r}\mathrm{o}\mathrm{p}(f)$ is doable in polynomial-time, for any fixed dimension, unlike the corresponding problem for $\mathrm{A}\mathrm{m}\mathrm{o}\mathrm{e}\mathrm{b}\mathrm{a}(f)$, which is $\mathbf{N}\mathbf{P}$-hard already in one variable. $\mathrm{A}\mathrm{r}\mathrm{c}\mathrm{h}\mathrm{T}\mathrm{r}\mathrm{o}\mathrm{p}(f)$ can thus serve as a canonical low order approximation to start any higher order iterative polynomial system solving algorithm, such as homotopy continuation. $\mathrm{A}\mathrm{r}\mathrm{c}\mathrm{h}\mathrm{T}\mathrm{r}\mathrm{o}\mathrm{p}(f)$ also provides an Archimedean analogue of Kapranov’s Non-Archimedean Amoeba Theorem and a higher-dimensional extension of earlier estimates of Mikhalkin and Ostrowski.