Counting solutions to binomial systems

A. DICKENSTEIN

Stuttgart, Alemania

Conferencia; Colloquium; 2006

Binomial ideals are quite ubiquitous in very different contexts particularly those involving toric geometry and its applications in the study of semigroup algebras, and in the modern versions of hypergeometric systems of differential equations. In this talk  we consider ideals generated by n binomials in a polynomial ring in n variables with coefficients in a field k. We are interested in determining when  the number of affine solutions over the algebraic closure of k  is finite and non zero (i.e. when the given binomials  define a complete intersection) and, in this case, to count the number of solutions, with or without multiplicity, directly in terms of the given data: the  2n exponents and the 2n coefficients. We use commutative algebra tools to reduce the study of these solutions to a combinatorial problem on a graph associated to the exponents occurring in the given binomials. It follows that for generic exponents the problem of counting the number of solutions (with or without multiplicity) can be solved in polynomial time, but that the general problem is #P-complete, i.e. at least as hard as an NP-complete problem. If time permits, we will outline some applications to differential equations and to the computation of sparse discriminants. This is joint work with Eduardo Cattani.