The intrinsic complexity of the arithmetic Nullstellensatz

We show several arithmetic estimates for Hilbert's Nullstellensatz, This in cludes an algorithmic procedure computing the polynomials and constants occ urring in a Bezout identity, whose complexity is polynomial in the geometri c degree of the system. Moreover, we show for the first time height estimat es of intrinsic type for the polynomials and constants appearing, again pol ynomial in the geometric degree and linear in the height of the system. The se results are based on a suitable representation of polynomials by straigh t-line programs and duality techniques using the Trace Formula For Gorenste in algebras. As an application we show more precise upper bounds for the fu nction pi(S)(x) counting the number of primes yielding an inconsistent modu lar polynomial equation system. We also give a computationally interesting lower bound for the density of small prime numbers of controlled bit length for the reduction to positive characteristic of inconsistent systems. Agai n, this bound is given in terms of intrinsic parameters, (C) 2000 Elsevier Science B.V. All rights reserved.