Tropical Varieties for Exponential Sums

Abstract

We study the complexity of approximating complex zero sets of certain $n$-variate exponential sums. We show that the real part, $R$, of such a zero set can be approximated by the $(n-1)$-dimensional skeleton, $T$, of a polyhedral subdivision of ${\mathbb{R}}^n$. In particular, we give an explicit upper bound on the Hausdorff distance: $\Delta (R,T)=O\left(t^{3.5}/\delta \right)$, where $t$ and $\delta$ are respectively the number of terms and the minimal spacing of the frequencies of $g$. On the side of computational complexity, we show that even the $n=2$ case of the membership problem for $R$ is undecidable in the Blum-Shub-Smale model over $\mathbb{R}$, whereas membership and distance queries for our polyhedral approximation $T$ can be decided in polynomial-time for any fixed $n$.

18 pages, 3 figures. This version corrects an erroneous proof of Theorem 1.1, and a small typo in Assertion (3) of Theorem 1.5, in the published version

Cited by in corpus (1)

• On the multivariate Fujiwara bound for exponential sums