Newton polytopes and witness sets (Q475408)

Let \(\mathcal{H}\) be a hypersurface in \(\mathbb{C}^{n}\) defined by the vanishing of a polynomial \(f \in \mathbb{C}[x_{1},\ldots,x_{n}]\), where \(\mathbb{C}[x_{1},\ldots,x_{n}]\) is the polynomial ring over the field \(\mathbb{C}\) of complex numbers. The set of monomials in \(f\), or more simply the convex hull of their exponent vectors (the Newton polytope of \(f\)), is an important combinatorial invariant of \(\mathcal{H}\). The Newton polytope encodes asymptotic information about \(\mathcal{H}\) and determining it from \(\mathcal{H}\) is a step towards determining the polynomial \(f\). The authors propose numerical methods to compute the Newton polytope of \(f\) in two cases when \(f\) is not known explicitly. They first show how to compute the Newton polytope when we are able to evaluate \(f\). This occurs, for example, if \(f\) is represented as a straight-line program, as a determinant, or as an oracle. For the other case, they suppose that \(f\) defines a hypersurface \(\mathcal{H}\) that is represented numerically as a witness set. The authors use numerical algebraic geometry to study the asymptotic behavior of \(\mathcal{H}\) in \((\mathbb{C}^{\star})^{n}\) and use this to recover the Newton polytope of a defining equation of \(\mathcal{H}\).