Skip to main content
1 of 6
Orr Shalit
  • 550
  • 4
  • 18

Is there a stable algorithm for polynomial division (in several variables)?

Suppose you have a homogeneous ideal I inside the algebra C[x_1,...,x_d] of complex polynomials in d-variables. Can one find a basis for I, say {f_1,...,f_k}, such that every h in I can be written as

h = a_1*f_1 + ... + a_k*f_k

where the coefficients appearing in each summand a_i*f_i are not much bigger then the coefficients appearing in h? More specifically, given that {f_1,...,f_k} is a Groebner basis for I, can one modify the standard division algorithm so that one gets h = a_1*f_1 + ... + a_k*f_k with controlled terms?

I will share that I found this possible in some special cases, for example when d=2, and I am now interested in the general question.

Note: My question begins after a basis has been found, I am not concerned here with the terrible complexity of actually computing a Groebner basis.

Orr Shalit
  • 550
  • 4
  • 18