×

A computational method for diophantine approximation. (English) Zbl 0878.11043

González-Vega, Laureano (ed.) et al., Algorithms in algebraic geometry and applications. Proceedings of the MEGA-94 conference, Santander, Spain, April 5-9, 1994. Basel: Birkhäuser. Prog. Math. 143, 193-253 (1996).
An important improvement to the algorithmic resolution of the effective Nullstellensatz was achieved by M. Giusti and J. Heintz [Proc. Int. Meet. Commut. Algebra, Cortona, Symp. Math. 34, 216-256 (1993; Zbl 0829.14029)] and by M. Giusti, J. Heintz and J. Sabia [Comput. Complexity 3, No. 1, 56-95 (1993; Zbl 0824.68051)] by means of encoding polynomials by straight-line programs. The paper under review presents important results, based on the use of division free non-scalar straight-line programs, to some of the problems appearing, in these approaches, when a Turing machine has to simulate the procedures.
In this context, they prove the existence of non-scalar straight-line programs of size \(sd^{O(n)}\), depth \(O(n\log_2d)\) and integer parameters of absolute height \(\max\{d^{O(n)},\eta\}\) for the effective Nullstellensatz (where \(s\) is the number of input polynomials, \(n\) the number of variables, \(d\geq n\) and \(\eta\) bound the degree and absolute height, respectively), and the existence of non-scalar straight-line programs of size \(d^{O(n)}\), depth \(O(r\log_2 d)\) and integer parameters of height \(\max\{d^{O(n)},\eta\}\) for the membership problem in a complete intersection (where \(n\) is the number of variables, \(r\leq n\) is the number of input ideal generators, \(d\geq n\) and \(\eta\) bound the degree and height of the input polynomials, respectively). Furthermore, as a consequence, they show that the effective Nullstellensatz and the membership problem in a complete intersection are in the BPP-class.
For the entire collection see [Zbl 0841.00016].

MSC:

11Y16 Number-theoretic algorithms; complexity
11J99 Diophantine approximation, transcendental number theory
68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
14A05 Relevant commutative algebra
PDF BibTeX XML Cite