Systems of rational polynomial equations have polynomial size approximate zeros on the average (Q1869964)

In Smale's approximate zero theory an approximate zero of a system of polynomial equations \(F\) with associated zero \(\zeta\) is a point \(z\) such that the sequences of iterates of the Newton operator of \(F\) is well defined and converges quadratically to \(\zeta\). In this paper, two of the main parameters of this theory as the total number of solutions and the size of approximate zeros, namely, the number of tape cells in a Turing machine required to write down the list of digits describings the approximate zero, are studied for input systems of multivariate polynomial equations with rational coefficients of bounded bit length. This last restriction means that computing is discrete and not continuous. Under a continuous modelling, \textit{M. Shub} and \textit{S. Smale} have shown [in: Computational algebraic geometry, Proc. Conf., MEGA'92, Prog. Math. 109, 267-285 (1993; Zbl 0851.65031)]\ that the average number or real solutions of systems of polynomial equations with real coefficientes equals the square root of the Bézout number of the system. One of the questions answered in the affirmative in this paper is whether this average can be translated to the discrete case of systems with rational coefficients of bounded input length. Another outcome of this paper is that these systems have polynomial size approximate zeros on the average. The technique used by the authors is an improvement of a sharp method due to \textit{H. Davenport} [J. Lond. Math. Soc. 26, 179-183 (1951; Zbl 0042.27504)]\ which combine induction and Fubini's theorem.