8
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ I might be confused about your question, but isn't that exactly what <a href="en.wikipedia.org/wiki/… algorithm</a> does? $\endgroup$
    – Kirill Levin
    Commented Oct 29, 2009 at 19:22
  • $\begingroup$ Hello Kirill, I didn't get your link. $\endgroup$
    – Orr Shalit
    Commented Oct 30, 2009 at 2:06
  • $\begingroup$ 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. $\endgroup$
    – Kirill Levin
    Commented Oct 30, 2009 at 3:01
  • 1
    $\begingroup$ The question is whether we can control the size of the coefficients of the polynomials introduced in the process. $\endgroup$
    – David E Speyer
    Commented Oct 30, 2009 at 16:16
  • $\begingroup$ Yes, that's the question. $\endgroup$
    – Orr Shalit
    Commented Oct 31, 2009 at 3:02

3 Answers 3

Reset to default
2
$\begingroup$

In Bayer and Mumford's What Can Be Computed in Algebraic Geometry? 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, that is nice reference, but if I am not mistaken, it does not address the problem. $\endgroup$
    – Orr Shalit
    Commented Nov 12, 2009 at 23:30
  • $\begingroup$ isn't 3.1 what you looked for ? $\endgroup$
    – David Lehavi
    Commented Nov 13, 2009 at 6:07
  • $\begingroup$ 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. $\endgroup$
    – Orr Shalit
    Commented Nov 13, 2009 at 11:36
3
$\begingroup$

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: http://arxiv.org/abs/1003.0502

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. It will take some time to see if that's what I need, but it looks interesting. $\endgroup$
    – Orr Shalit
    Commented Oct 31, 2009 at 3:03
  • $\begingroup$ No, this doesn't help. Thanks anyway. $\endgroup$
    – Orr Shalit
    Commented Nov 4, 2009 at 14:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .