On the complexity of the real Nullstellensatz in the 0-dimensional case
type: Item
instance of: scholarly article
title: On the complexity of the real Nullstellensatz in the 0-dimensional case
zbMATH Open document ID: 1013.14002
DOI: 10.1016/S0022-4049(99)00077-8
author: Joachim Schmid
published in: Journal of Pure and Applied Algebra
publication date: 2001-02-06T00:00:00Z
review text: 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\).
reviewed by: Joos Heintz
Mathematics Subject Classification ID: 14A05
Mathematics Subject Classification ID: 13J30
Mathematics Subject Classification ID: 14Q20
Mathematics Subject Classification ID: 14P05
zbMATH DE Number: 1523644
zbMATH Keywords: real algebra
zbMATH Keywords: effective Nullstellensatz
MaRDI profile type: Publication
cites work: Q3135197
cites work: Q4295701
cites work: Q3770650
cites work: Equations for the projective closure and effective Nullstellensatz
cites work: The membership problem for unmixed polynomial ideals is solvable in single exponential time
cites work: Sharp Effective Nullstellensatz
cites work: Q3663392
cites work: An introduction to real algebra
cites work: Q4037362
cites work: Sur la représentation en somme de carrés des polynômes à une indéterminée sur un corps de nombres algébriques
cites work: Q3708857
description: scientific article; zbMATH DE number 1523644