Complexity results for triangular sets

We study the representation of the solutions of a polynomial system by triangular sets, and concentrate on the positive-dimensional case. We reduce to dimension zero by placing the free variables in the base field, so the solutions can be represented by triangular sets with coefficients in a rational function field. We give intrinsic-type bounds on the degree of the coefficients in such a triangular set, and on the degree of an associated degeneracy hypersurface. Then we show how to apply lifting techniques in this context, and point out the role played by the evaluation properties of the input system. Our algorithms are implemented in Magma; we present three applications, relevant to geometry and number theory.