Question

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?

Answer 1

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.

Answer 2

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.)

Answer 3

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.]

Answer 4

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.