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

Added 13.11.09 - By controlled I mean that the coefficients of the terms $a_i f_i$ are bounded in a non-exponential manner by the coefficients of $h$. There is no problem with degree of the $a_i$'s.

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?

• I might be confused about your question, but isn't that exactly what <a href="en.wikipedia.org/wiki/… algorithm</a> does? Oct 29 '09 at 19:22
• Hello Kirill, I didn't get your link. Oct 30 '09 at 2:06
• Sorry about that. I thought I could write HTML in comments. Apparently not. The link is just the Wikipedia page for Buchberger's algorithm: en.wikipedia.org/wiki/Buchberger%27s_algorithm It is used for computing a Gröbner basis, but if I understand your question correctly, it does exactly what you are asking for in the process. Oct 30 '09 at 3:01
• The question is whether we can control the size of the coefficients of the polynomials introduced in the process. Oct 30 '09 at 16:16
• Yes, that's the question. Oct 31 '09 at 3:02

• No, it isn't. There is no problem with the degree of the $a_i$'s, when the $f_i$'s are a Groebner basis (with respect to a grlex for instance) the degree of the $a_i$'s will be less than the degree of $h$ (the point of 3.1 is that the generating polynomials there are not assumed to be a basis). The bad thing that can happen, see the link below (Example 2.5), is that h can be a polynomial with very small coefficients, while when the division algorithm is run naively, one gets the the coefficients of the polynomials $a_i f_i$ are huge. Nov 13 '09 at 11:36