Elimination theory and Newton polytopes (Q1039980): Difference between revisions

Consider an affine algebraic variety \(X\subseteq \mathbb C^n\) and a projection \(\pi:\mathbb C^n\to\mathbb C^m\). The general problem in elimination theory is to describe the defining equations of the projection \(\pi(X)\) in terms of the defining equations of \(X\). The authors study this problem in the framework of the theory of Newton polytopes: Suppose \(X\subset (\mathbb C\setminus 0)^n\) is given by a system of Laurent polynomial equations \(f_1=\dots=f_k=0\) with prescribed Newton polytopes and generic coefficients. Furthermore, assume that \(\pi(X)\subset (\mathbb C\setminus 0)^m\) is a hypersuface defined by a Laurent polynomial equation \(g=0\). Such \(g\) is called a \textit{composite polynomial} of the~\(f_i\). The following is a summary of the main results of the paper. (1) The authors describe the Newton polytope \(\Delta\) of \(g\) in terms of the Newton polytopes \(\Delta_i\) of the polynomials \(f_i\). They prove that \(\Delta\) coincides (up to a shift and a dilation) with the mixed fibre polytope of the~\(\Delta_i\), as defined by \textit{P. McMullen} [Discrete Comput Geom 32, 207--236 (2004; Zbl 1087.52006)], but give an independent characterization in terms of mixed volumes. To this end, they develop a version of elimination theory for convex bodies. (2) The authors give an algorithm for computing the coefficients of \(g\) corresponding to the boundary of~\(\Delta\). For every face \(\Gamma\subset\Delta\) they express the ``truncation'' of \(g\) to \(\Gamma\) as a product of composite polynomials of certain truncations of the \(f_i\), thus reducing the problem to smaller dimension. Furthermore, when the Newton polytopes of the \(f_i\) have sufficiently general mutual position (developed), their algorithms leads to explicit formulas for the vertex and edge coefficients of \(g\). This recovers previously known formulas for the product and the sum of the values of a monomial over the roots of a Laurent system with developed Newton polytopes discovered by \textit{A.~G.~Khovanskii} [in: Proceedings of a conference in honour of V. I. Arnold for his 60th birthday, Toronto, Canada, June 15-21, 1997. Providence, RI: American Mathematical Society. Fields Inst. Commun. 24, 325--364 (1999; Zbl 0965.14025); Mosc. Math. J. 2, No. 1, 99--112 (2002; Zbl 1044.14029)]. (3) The authors show how their approach can be applied to elimination theory of rational and analytic functions in the framework of Newton polyhedra. The elimination problem in the context of Newton polytopes is closely related (and in some sense equivalent) to the problem of computing the sparse resultant and the sparse implicitization problem. The authors description of \(\Delta\) in (1) above can be restated to recover the results of \textit{B. Sturmfels} [J. Algebr. Comb. 3, No. 2, 207--236)= (1994; Zbl 0798.05074)] and \textit{B.~Sturmfels, J. Tevelev} and \textit{J. Yu}, [Mosc. Math. J. 7, No. 2, 327--346 (2007; Zbl 1133.13026)].