On the complexity of the real Nullstellensatz in the 0-dimensional case (Q1584040)

The author proves a real effective Nullstellensatz of the following form: Let \(k\) be an ordered field, \(d\geq 3\) a given natural number and \(f, f_1,\dots f_m\) be elements of the polynomial ring \(k[X_1,\dots ,X_n]\) with \(\deg f_j \leq d\) for \(1\leq j\leq m\). Suppose that the following two conditions are satisfied: (I) The solutions of the system of polynomial equations \(f_1=0,\dots f_m=0\), defined over the algebraic closure of \(k\), form an algebraic variety of dimension zero (i.e. a nonempty, finite set). (II) The polynomial \(f\) vanishes on all solutions of the above polynomial equation system which are defined over the \textit{real} closure of \(k\). Then there exist natural numbers \(r,t\) and polynomials \(h_1,\dots ,h_r,q_1,\dots ,q_m\in k[X_1,\dots ,X_m]\) with \(f^{2t}+\sum_{i=1}^r h_i^2=\sum_{j=1}^m q_jf_j\) satisfying the following estimates: (i) \(2t\leq d^{2n+1}\), (ii) \(r\) is bounded by the second Pythagorean number of the univariate rational function field over \(k\), (iii) \({\text{deg}} {h_i}^2 \leq d^{2n+1}\) for any \(1\leq i\leq r\), (iv) \(\deg {q_jf_j}\leq d^{2n+1}(1+\deg f)\) for any \(1\leq j\leq m\). The proof of this result combines two well known variants of effective Nullstellensätze for algebraically closed fields with techniques coming from real commutative algebra. The argumentation makes substantial use of assumption (I). Although this assumption seems to be very restrictive from a theoretical point of view, the formulation of this real effective Nullstellensatz (the first one with really single exponential degree bounds), indicates what could be expected in more general situations. An algorithmic version of this result would have many important applications in real polynomial equation solving, but, as the author observes, such a version would require a previous general elimination theory for systems of quadratic equations over \(k\).