Bounding the Number of Roots of Multi-Homogeneous Systems

What is it about?

Polynomial systems model a large variety of problems in all branches of sciences and technology. A major question in studying as well as solving such systems is an estimate on the number of solutions. Determining the number of solutions of a multi-homogeneous polynomial system is a fundamental problem in algebraic geometry. The multi-homogeneous Bézout number bounds from above the number of non-singular solutions of a multi-homogeneous system, but its computation is a #P-hard problem. Here, we prove that every multi-homogeneous system can be modeled by hypergraphs and the computation of its multi-homogeneous Bézout number is related to constrained hypergraph orientations. Thus, we convert the algebraic problem of bounding the number of roots of a polynomial system to a purely combinatorial problem of analyzing the structure of a hypergraph. We also provide a formulation of the orientation problem as a constraint satisfaction problem (CSP), hence leading to an algorithm that computes the multi-homogeneous bound by finding constrained hypergraph orientations.

Featured Image

Photo by Alina Grubnyak on Unsplash

Photo by Alina Grubnyak on Unsplash