Small Resultant Systems via Linear Combinations

Abstract

For a system of $s$ homogeneous polynomials of degree $d$ in $n$ variables, say $\mathbf{f}=0$, we consider the problem of constructing resultant systems. A resultant system is a finite set of polynomials in the coefficients of the input polynomials, the vanishing of which characterizes the systems $\mathbf{f}$ with a common non-zero solution. The classical approaches for constructing resultant systems rely either on maximal minors of large coefficient matrices or on the coefficients of a resultant of generic linear combinations of the input polynomials. Typically, they produce resultant systems containing a very large number of polynomials. We develop new constructions based on taking resultants of linear combinations of the input polynomials; this results in resultant systems of small cardinality. Our main results are: 1) We prove that a resultant system with $\left(\genfrac{}{}{0ex}{}{d+n-1}{n-1}\right)s-n^2+1$ polynomials exists; each polynomial is the resultant of $n$ linear combinations of the input polynomials. This improves the previously known upper bounds, even for systems of bivariate homogeneous polynomials. 2) Under the assumption that the input polynomials are non-zero, we construct explicit resultant systems with cardinality $\mathrm{poly}(s,d)$, when $n$ is fixed.