The Canny-Emiris conjecture for the sparse resultant

Solving polynomial systems; resultants (13P15) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Abstract: We present a product formula for the initial parts of the sparse resultant associated to an arbitrary family of supports, generalising a previous result by Sturmfels. This allows to compute the homogeneities and degrees of the sparse resultant, and its evaluation at systems of Laurent polynomials with smaller supports. We obtain a similar product formula for some of the initial parts of the principal minors of the Sylvester-type square matrix associated to a mixed subdivision of a polytope. Applying these results, we prove that the sparse resultant can be computed as the quotient of the determinant of such a square matrix by a certain principal minor, under suitable hypothesis. This generalises the classical Macaulay formula for the homogeneous resultant, and confirms a conjecture of Canny and Emiris.

Review text

Let \(M\simeq \mathbb{Z}^n\) be a lattice of rank \(n\) and \(\mathcal{A}_i \subset M\) a nonempty finite subset for \(i=0,\ldots ,n\). Let \(\mathrm{Res}_\mathcal{A}\) be the sparse resultant associated with this family of supports. The first contribution of this paper is that for a vector \(\omega \in \mathbb{R}^{n+1}\), \(\mathrm{init}_{\omega}(\mathrm{Res}_\mathcal{A})\) can be factorized as the product of some sparse resultants. Here the initial stands for the sum of the monomial terms whose exponents have minimal weight with respect to \(\omega\). This result generalizes a previous one by \textit{B. Sturmfels} [J. Algebr. Comb. 3, No. 2, 207--236 (1994; Zbl 0798.05074)]. Note that this representation facilitates the computation not only of the homogeneities and degrees of \(\mathrm{Res}_\mathcal{A}\) but also its evaluation at systems of Laurent polynomials with smaller supports. Moreover, the authors present similar result for some of the initial parts of the principal minors of the Sylvester-type square matrix associated with a mixed subdivision of a polytope. Finally, it is shown that these arguments proves that under suitable hypothesis, the sparse resultant can be computed as the quotient of the determinant of a matrix by one of its principal minors; confirming a conjecture due [\textit{J. F. Canny} and \textit{I. Z. Emiris}, J. ACM 47, No. 3, 417--451 (2000; Zbl 1094.65508)] stated in 2000.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: The Canny-Emiris conjecture for the sparse resultant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6101263)