Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization (Q1690788)

Let us give first some basic concepts to state the main results of the paper. Let \(X_1,\ldots ,X_m\) be a partition of the set of given variables and \(\mathbf{X}=(X_1,\ldots ,X_m)\). Let also \(\mathbf{d}=(d_1,\ldots ,d_m)\) be a sequence of positive integers. A polynomial \(f\in K[\mathbf{X}]\) is called multi-homogeneous of multi-degree \(\mathbf{d}\) if every term appearing in \(f\) is multi-homogeneous of multi-degree \(\mathbf{d}\) w.r.t. \(\mathbf{X}\). In addition, we shall need the height of a polynomial over rationals. For \(a = u/v \in {\mathbb Q}\setminus \{0\}\), the height of \(a\), denoted by \(\mathrm{ht}(a)\), is \(\max(\log(|u|), \log(v))\), with \(u\in \mathbb{Z}\) and \(v\in \mathbb{N}\) coprime. For a non-zero univariate or multivariate polynomial \(f\) with rational coefficients, let \(v\in \mathbb{N}\) be the minimal common denominator of all its non-zero coefficients. Then \(\mathrm{ht}(f)\) is defined as the maximum of the logarithms of \(v\) and of the absolute values of the coefficients of \(v f\) (which are integers). In this paper, bit complexity estimates for solving multi-homogeneous polynomial systems are presented which, up to a few extra other factors, are quadratic in the number of solutions and linear in the height of the input system, under some genericity assumptions. Furthermore, these results are applied to the problem of optimizing a linear map on the real trace of an algebraic set.