On the intrinsic complexity of the arithmetic Nullstellensatz (Q1969498)

Let \(X_1,\ldots,X_n\) be indeterminates and let \(f_1,\ldots,f_t,f\in{\mathbb Z}[X_1,\ldots,X_n]\) be polynomials of degree at most \(d\) with \(t\leq n+1\). Suppose that for \(1\leq i<t\) the polynomials \(f_1,\ldots,f_i\) form a regular sequence and generate a radical ideal in \({\mathbb Q}[X_1,\ldots,X_n]\). Denote by \(V(f_1,\ldots,f_i)\) the closed subvariety of \({\mathbb C}^n\) defined by \(f_1,\ldots, f_i\) and by \(\deg V(f_1,\ldots,f_i)\) its geometric degree (disregarding possible components at infinity). Let \(\delta:= \max\{\deg V(f_1,\ldots,f_i);1\leq i\leq t\}\) and observe that \(\delta\leq d^{t-1}\) holds by Bezout's theorem. Suppose that \(f_t\) is not a zero divisor in the residue ring \({\mathbb Q}[X_1,\ldots,X_n]/(f_1,\ldots, f_{t-1})\) and that \(f\) belongs to the ideal generated by \(f_1,\ldots,f_t\) in \({\mathbb Q}[X_1,\ldots,X_n]\). Finally suppose that the polynomials \(f_1,\ldots,f_t, f\) are represented by a division-free straight-line program \(\Gamma\) in \({\mathbb Z}[X_1,\ldots,X_n]\) of size \(L\) and non-scalar depth \(\ell\) and that \(\Gamma\) contains only parameters belonging to a given finite set \(F\subset {\mathbb Z}\). The main results of the paper are the following intrinsic effective Nullstellensätze of algebraic, arithmetic and computational nature (theorem 1 and 2 of the paper): (i) There exists a division-free straight-line program \(\Gamma_1\) in \({\mathbb Z}[X_1,\ldots,X_n]\) representing a nonzero element \(a\in{\mathbb Z}\) and polynomials \(g_1,\ldots, g_t\in {\mathbb Z}[X_1,\ldots,X_n]\) such that the following conditions are satisfied: \(af=g_1f_1+\cdots+g_tf_t\), \(\max\{\deg g_i;1\leq i\leq t\}\leq 3t^2d\delta\leq 3t^2 d^t\). The size and the nonscalar depth of \(\Gamma_1\) are of order \((tdL\delta)^{c_1}=d^{O(n)}\) and \(O((n+\ell)^2\log_2\delta)=O(n^3\log_2^2d)\) respectively and the parameters of \(\Gamma_1\) belong to the set \(F\cup \{z\in{\mathbb Z};|z|\leq (tdL\delta)^{c_1}\}\), where \(c_1\) is a suitable universal constant. (ii) There exists a division-free straight-line program \(\Gamma_2\) in \(\mathbb Z[X_1,\ldots,X_n]\) of size \(((td)^t+L\delta)^{c_2}=d^{O(n)}\) and nonscalar depth \(O(\log t+\log d+\log L+\log \delta)=O(n\log d)\) with parameters in the set \(F\cup \{z\in{\mathbb Z};|z|\leq (tdL\delta)^{c_2}\}\) representing another nonzero element \(a\in {\mathbb Z}\) and polynomials \(g_1,\ldots,g_t\in{\mathbb Z}[X_1,\ldots,X_n]\) satifying the same conditions as in statement (i) with \(c_2>0\) being a suitable universal constant. Statement (i) optimizes the size of the straight-line program \(\Gamma_1\) representing the output data \(a,g_1,\ldots,g_t\), whereas statement (ii) optimizes the nonscalar depth of the straight--line program \(\Gamma_2\), introducing an extra factor of \((td)^t\) in the size of \(\Gamma_2\). Note that the size of \(\Gamma\) is polynomial in the extrinsic input parameters \(t\), \(d\), \(L\) and in the intrinsic geometric invariant \(\delta\). Statement (i) represents an almost optimal solution to a well--known complexity problem in computer algebra. It generalizes and improves a similar result announced by \textit{M. Giusti, J. Heintz, J. E. Mordis, J. Morgenstern} and \textit{J.-M. Pardo} [J. Pure Appl. Algebra 124, 101-146 (1998; Zbl 0944.12004)]. The present paper contains the first rigorous proof of such an intrinsic computational Nullstellensatz. Statement (ii) implies the following arithmetic result (corollary 4): For \(1\leq i\leq t\) denote by \(\text{ht}(V(f_1,\ldots,f_i))\) the suitably defined logarithmic height of the algebraic varieties \(V(f_1,\ldots,f_i)\). Let \(\eta:=\max\{\text{ht}(V(f_1,\ldots,f_i))\); \(1\leq i\leq t\}\). Then the output data \(a,g_1,\ldots,g_t\) of statement (ii) satisfy the following height estimate: \[ \max\{\text{ht}(a),\text{ht}(g_1),\ldots, \text{ht}(g_t)\}=(\text{nd }L \delta)^{O(1)}(\eta t \text{ ht}(F)) \] (here \(\text{ht}(a)\), \(\text{ht}(g_1),\ldots, \text{ht}(g_t)\), \(\text{ht}(F)\) denotes the suitably defined logarithmic height of the corresponding polynomial or the set of integers). Although improved in the meantime by the authors, this height estimate represents the first example of an intrinsic arithmetic Nullstellensatz. The authors derive then different effective Nullstellensätze from their main result, statements (i) and (ii). The paper finishes with a number of asymptotically tight estimates for the number of primes \(p\) for which an inconsistent polynomial equation system over \({\mathbb C}\) becomes consistent modulo \(p\) (corollary 7, 8, 9 and Theorem 10).