Nullstellensätze for zero-dimensional Gröbner bases (Q626612)

Let \(I=\langle f_1,\dots,f_k\rangle\) be an ideal of the polynomial ring \(R=K[x_1,\dots,x_n]\) over a field \(K\). Let \(d_i\) denote the total degree of \(f_i\) and suppose w.l.o.g. that \(d_2\geq \dots\geq d_k\geq d_1\). Set \(d=\max\{d_1,\dots,d_k\}\). Denote by \(D(k,n)\) the minimum integer \(D\) such that for any polynomial \(f\) in \(I\) there exists a representation of \(f\) as \(f=g_1f_1+\dots +g_kf_k\), such that the degree of \(g_if_i\) be at most \(\deg(f)+D\). The first part of this paper gives new bounds for \(D(k,n)\) in the case that \(f_1,\dots,f_k\) is a regular sequence and \(d_1\geq 2\) (Theorem 2.4) and in the case that \(I\) is a zero-dimensional ideal and \(d_1\geq 2\) (Theorem 2.5). The second part of the paper uses the previous results to show that, with the above notation, if \(I\) is a zero dimensional ideal and \(d_1\geq 0\) then the reduced Gröbner basis, with respect to any monomial ordering, of \(I\) may be computed within a bit complexity which is polynomial in \(\max\{S,D^{n^2}\}\) where \(D=(d_1+\dots+d_n)/n\) and \(S\) is the total size of the input polynomials, defined as the sum of their sizes in the dense representation (Theorem 2.6).