I would like to know what Bernstein's bound is on multivariate polynomial systems where there are more equations than unknowns. I have a "generic" zero-dimensional multivariable polynomial system with a set of sparse real coefficients: $$ \begin{pmatrix} p_1(x_1,\ldots,x_d)\\ \vdots \\ p_m(x_1,\ldots,x_d) \end{pmatrix} = 0, $$ where $m>d$. When $m=d$, one can definitely bound the number of zeros by the mixed volume BKK-bound but I am not confident that the bound continues to hold in the $m>d$ (and if it does what the bound looks like).

My motivating polynomial system comes from the analysis of a truss/graph (with adjacency matrix $A = (a_{ij})$), and after some trigonometric identities I end up with the polynomial system:
$$ \begin{aligned} \sum_{j=2}^d a_{1j} x_j &= 0 \\ a_{i1}x_i + \sum_{j=2}^d a_{ij}x_iy_j - \sum_{j=2}^d a_{ij}x_jy_i & =0, \quad 2\leq i\leq d, \\ x_i^2+y_i^2 - 1 &=0, \quad 2\leq i\leq d. \end{aligned} $$ Here, I have $2d-1$ equations and $2d-2$ variables. In a given truss problem, most of the $a_{ij}$'s are zero. Under the assumption that the graph is connected, then I imagine that it could be valid to drop one of the middle equations above. However, ideally, I could just apply a bound directly. In practice, I am interested in a bound on the number of real solutions, but happy to have a bound on the number of solutions in $(\mathbb{C}^*)^{2d-2}$ or $\mathbb{C}^{2d-2}$ to begin with.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.