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.

  • $\begingroup$ For $d=3$ and generic $A,$ there are no $(\mathbb{C}^*)^4$-solutions to the entire system. "Generic" means $a_{1, 2}*a_{2, 3}*a_{3, 1}-a_{1, 3}*a_{2, 1}*a_{3, 2}\ne 0.$ So any BK-type bound is far from sharp, unless you know something special about your matrix! $\endgroup$ – tim Aug 13 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.