Sharp Estimates for Triangular Sets

A result of Xavier Dahan and Erich Schost, ISSAC '04

Presented by Michael Monagan

July 19th, 2004.

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.