The computational complexity of the Chow form (Q1879037)

The Chow form of an equidimensional quasiprojective variety is one of the basic objects of algebraic geometry and plays a central role in elimination theory. Let \({\mathcal V}\in\mathbb{P}^n\) be an equidimensional quasiprojective variety of dimension \(r\), and degree \(D\) defined over \(\mathbb{Q}\). Its Chow form \({\mathcal F}_{\mathcal V}\) is a polynomial with rational coefficients (unique up to scalar factor) which characterizes the set of overdetermined linear systems over the projective closure \(\overline{\mathcal V}\). More precisely, let \(U_i\), \(i=0,\dots,r\) denote \(r+1\) sets of \(n+1\) variables each, and let \(L_i:=U_{i0}+ \cdots+ U_{in}x_n\) be the linear form associated to the set \(U_i\), \(i=0,\dots,r\). Then, \({\mathcal F}_{\mathcal V} \in\mathbb{Q} [U_0,\dots,U_r]\) is the squarefree polynomial such that \[ {\mathcal F}_V[u_0,\dots,u_r]=0 \Leftrightarrow\overline{\mathcal V}\cap\bigl\{L_0 (u_0,x)=0,\dots,L_r(u_r,x) =0\bigr\}\neq\emptyset, \] for \(u_i\in \mathbb{C}^{n+1}\), \(i=0,\dots,r\). From \({\mathcal F}_{\mathcal V}\), we can directly read the dimension of \({\mathcal V}\). Furthermore, if \({\mathcal V}\) is closed in \(\mathbb{P}^n\), its Chow form \({\mathcal F}_{\mathcal V}\) characterizes it, and it is possible to derive a complete set of equations for \({\mathcal V}\) from \({\mathcal F}_{\mathcal V}\). In this paper, the authors present a bounded probability algorithm for the computation of Chow forms of the equidimensional components of an algebraic variety defined by means of a given set of polynomials. Thus, in particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety. Furthermore, the error probability is analyzed in detail. \textit{M. Giusti} et. al. [J. Pure Appl. Algebra 117--118, 277--317 (1997, Zbl 0871.68101); in: Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra 124, 101--146 (1998; Zbl 0944.12004)] succeeded in classifying the tractability of polynomial equations solving in the zero-dimensional case in terms of the length, and the geometric degree of the input system. The algorithm presented can be seen as a general extension of these results to arbitrary varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows to compute the Chow form from a suitable zero-dimensional fiber. The main result of this work is that the complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence, it improves the algorithms (which use dense encoding of polynomials) by \textit{L. Caniglia} [Appl. Algebra Eng. Commun. Comput. 1, 25--41 (1990; Zbl 0732.13012); \textit{M. Giusti} and \textit{J. Heintz} [in: Effective methods in algebraic geometry, Proc. Symp., Castiglioncello/Italy 1990, Prog. Math. 94, 169--194 (1991; Zbl 0755.14018)]; \textit{T. Krick} [Complejidad para Problemas de Geometría Elemental, Ph.D dissertation. Univ. Buenos Aires, Argentina (1990)]; and the algorithm (which uses the slp representation for the output) by \textit{S. Puddu} and \textit{J. Sabia} [J. Pure Appl. Algebra 129, 173--200 (1998; Zbl 0929.68132)]. The only previous algorithm whose complexity is in some cases comparable to this new algorithm is the one by \textit{G. Jeronimo, S. Puddu}, and \textit{J. Sabia} [J. Algorithms 41, 52--68 (2000; Zbl 1002.68061)], which computes an slp representation of the Chow form of the component of maximal dimension of an algebraic variety within complexity \((sd^n)^{{\mathcal O}(1)}\). In this paper, the authors do not compute the Chow forms for all the equidimensional components, but they replace the Bézout numbers \(d^n\) by \(d\delta\), where \(\delta\) denotes the geometric degree. As an application of these results, the authors obtain an algorithm to compute the subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, the authors derive an algorithm for the computation of the unique solution of a generic overdetermined polynomial equation system.