Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I've spent some time recently looking at some Groebner bases for some specific ideals coming from problems in computer vision. The generators are not sparse, and they all have the same degree (specifically, degree 2). I'm actually surprised by the relatively small number of basis elements needed in my examples. So it's got me thinking of some general questions about the number of elements in any reduced Groebner basis.

For concreteness, let's say that we've got an ideal $I$ generated by $m$ polynomials, each of degree $d$, in a polynomial ring in $n$ indeterminates over a field $k$, with a deglex term order. If it matters, my ideals will not be zero-dimensional.

  1. If the generators of $I$ are "sufficiently general", what can we say about the expected number of elements in a reduced Groebner basis?
  2. Can we say anything about bounds on the number of elements in such a reduced Groebner basis, in terms of $m$ and $d$? In general, I've heard that the bound is "doubly-exponential", but in what?
  3. For my needs, the polynomials are not very sparse. But if we did have many of the coefficients in our generators being $0$, can we use that to get some different bounds?
share|improve this question
    
I think this kind of phenomena happens quite often -- in most examples you see, things turn out to be quite straight-forward and efficient but there are always examples that are extremely complicated. There's a sense in which "most" finitely-presented groups are either trivial, hyperbolic or free, but some hard-to-find groups have unsolvable word problem. Similarly, the simplex method is usually fast but in some rare instances it is exponential run-time. I do not know if people have done probabilistic estimates on sizes of Groebner basis, but it would be interesting. –  Ryan Budney Aug 5 '10 at 17:29

4 Answers 4

The double exponential bound is indeed frighteningly easy to obtain. This ought to make Grobner bases prohibitively costly, and indeed there has been some effort put into non-Grobner methods to solve polynomial equations (e.g. Gregoire Lecerf's Kronecker package for Magma).

In practice, Grobner bases remain competitive, and users of Grobner methods note that the double-exponential bound, though easily obtained through construction, does not occur often in the systems that people are actually interested in. In particular, if you're working with a 0-dimensional ideal, it is possible to construct the Grobner basis of the system (wrt any admissible ordering) in single-exponential time , which certainly implies that the basis itself is single exponential in size. [Y.N. Lakshman, A single exponential bound on the complexity of computing Gröbner bases of zero-dimensional ideals. In: Effective methods in algebraic geometry (Castiglioncello, 1990).]

Sparsity does not help. As I recall, Mayr and Meyer-type examples are extremely sparse.

I've never heard of any serious probabilistic study of the number of elements, probably because this would be excessively hard and not very rewarding, given that there is no natural way to put a probability measure on your system. (Note that for a somewhat related problem, the average number of real roots of a real polynomial, the answers you obtain do depend noticeably on the measure used.)

share|improve this answer

On the "doubly-exponential" bound, from papers 18--21 on Irena Swanson's web page:

Grete Hermann proved in [H] that for any ideal $I$ in an $n$-dimensional polynomial ring over the field of rational numbers, if $I$ is generated by polynomials $f_1 , \dots , f_k$ of degree at most d, then it is possible to write $f = \sum r_i f_i$, where each $r_i$ has degree at most $\mathrm{deg}\ f + (kd)^{(2^n)}$. Mayr and Meyer in [MM] found ideals $J(n, d)$ for which a doubly exponential bound in $n$ is indeed achieved. Bayer and Stillman [BS] showed that for these same ideals also any minimal generating set of syzygies has elements of degree which is doubly exponential in $n$. Koh [K] modified the original ideal to obtain homogeneous quadric ideals with doubly exponential degrees of syzygies and ideal membership coefficients.

share|improve this answer

As far as I know, recent work on the complexity of Groebner bases has concentrated on linking it to the volume of the Newton polygon associated to the ideal. The main thought here is to generalize the Bezout bound.

Note that even the double-exponential bound has been recently sharpened. And for $0$-dimensional ideas a lot more is known.

[Links are given instead of trying to transcribe the results here. This is both the simplest way to cite the proper sources, as well as to ensure that no errors slip in as the results are all extremely technical and require quite a number of preliminary definitions to be stated.]

share|improve this answer
    
Great! I'm glad you could provide more up to date references on the state of the art. The first link you provided deals with mixed volume and Kushnirenko-Bernstein theorem, but unless I missed something, does not address size of the corresponding bases. Is there work being done in that direction? –  Thierry Zell Aug 9 '10 at 14:37
    
The first link was for 'general information' rather than specific results about the size of bases. Yes, people are working on it, but I don't know the details. The authors of the 2 papers I linked to would be in a much better position to answer this. –  Jacques Carette Aug 9 '10 at 15:02

There is a long strand of research attempting to show that the worst-case doubly-exponential bounds don't apply to "interesting" problems - dating back to Bayer and Stillman's work on Castelnuovo-Mumford regularity in the eighties to very recent work of Mayr on sharpened bounds for low-dimensional ideals. The obvious keyword searches, e.g. Grobner exponential, should quickly locate the pertinent literature.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.