Skip to main content
4 of 6
another note added, emphasizing problem
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 $\mathbb{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$ or when $I$ is generated by monomials, 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.

Another note (added 12.11.09): The answers and links that I am getting suggest that this problem has not been considered before. So I re-eamphasize my note from above: assume that a Groebner basis, even a universal Groebner basis, has already been found for the ideal. What can be said about the stability of certain variants of the division algorithm now?

Orr Shalit
  • 550
  • 4
  • 18