## 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

### Citations:

Zbl 0829.14029; Zbl 0824.68051