Sharp Estimates for Triangular Sets
A result of Xavier Dahan and Erich Schost, ISSAC '04
Presented by Michael Monagan
Let I be a zero-dimensional ideal in Q[x1,x2,...,xn]. Let N denote the number of solutions of the corresponding system. The authors study two triangular representations for I, the lex Grobner basis representation and the rational univariate (Kronecker) representation. They prove that size of the integer coefficients in the lex GB representation is QUADRATIC in N and for the Kronecker representation is LINEAR in N. Previous bounds were EXPONENTIAL in N. In this talk we explain the result and show examples.