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 '19 at 22:39

The problem here is the system is overdetermined: One more equations than unknowns, and the system is far from generic (specially the last group of equations).

It is probably impossible to answer without knowing more about the question, but this does reminds me of the root counting problem for the Kuramoto equations, which can be adapted to the BKK framework via...

  1. Find symmetry and eliminate one of the equations (in the Kuramoto case, the sum of the equation happens to be 0, which allows the elimination of one equation).
  2. Use different algebraic formulations for equations involving trig functions (don't use $x_i = \sin(\theta_i)$ and $y_i = \cos(\theta_i)$).

With these changes, the BKK bound may provide a sharp bound, at least for Kuramoto equations. Hopefully it applies to your problem here.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.