most recent 30 from http://mathoverflow.net 2013-05-19T13:52:38Z http://mathoverflow.net/feeds/question/3249 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/3249/is-there-a-stable-algorithm-for-polynomial-division-in-several-variables Orr Shalit 2009-10-29T12:09:30Z 2010-06-25T04:27:20Z

<p>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 </p> <p>$$h = a_1 f_1 + ... + a_k f_k $$</p> <p>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?</p> <p><strong>Added 13.11.09 -</strong> By <em>controlled</em> I mean that the <strong>coefficients</strong> of the terms $a_i f_i$ are bounded in a non-exponential manner by the coefficients of $h$. There is no problem with <strong>degree</strong> of the $a_i$'s.</p> <p>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.</p> <p>Note: My question begins <strong>after</strong> a basis has been found, I am <em>not</em> concerned here with the terrible complexity of actually computing a Groebner basis.</p> <p><strong>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?</strong> </p>

http://mathoverflow.net/questions/3249/is-there-a-stable-algorithm-for-polynomial-division-in-several-variables/3449#3449 JP May 2009-10-30T16:07:55Z 2009-10-30T16:07:55Z

<p>You might have luck looking into the matrix based reduction used in the F4 algorithm. The simple description in the PDF linked from "An introduction to the F4 algorithm" at the bottom of the Wikipedia page suggests it might be useful in this context.</p>

http://mathoverflow.net/questions/3249/is-there-a-stable-algorithm-for-polynomial-division-in-several-variables/5170#5170 David Lehavi 2009-11-12T08:08:42Z 2009-11-12T08:08:42Z

<p>In Bayer and Mumford's <a href="http://arxiv.org/pdf/alg-geom/9304003v1" rel="nofollow">What Can Be Computed in Algebraic Geometry?</a> section 3, you can find a 17 years old survey of known results. The bottom line is that without controlling the Castelnuovo Mumford regularity of the variety in question, there is very little you can do (you follow Buchberger's algorithm step by step and get some doubly exponential bound on the coefficients). The situation when imposing geometric conditions is a mater of current research.</p>

http://mathoverflow.net/questions/3249/is-there-a-stable-algorithm-for-polynomial-division-in-several-variables/5223#5223 Orr Shalit 2009-11-12T18:46:40Z 2010-06-25T04:27:20Z

<p><strong>Revised June 25, 2010: I feel I need to close this circle. Thanks for the answers given but they have all been quite off the mark. My partial results on this problem (there is much room for improvement) as well as an application to operator theory can be found in this link:</strong> <a href="http://arxiv.org/abs/1003.0502" rel="nofollow">http://arxiv.org/abs/1003.0502</a></p>