2
$\begingroup$

It's known that finding a Gröbner basis of a polynomial ideal has a worst-case space complexity of $O(2^{2^{c\cdot n}})$, where c is constant and n is the number of variables $k[x_1,\ldots,x_n]$.

However, in practice it seems that most ideals have a simple Gröbner basis.

Can anyone give some concrete examples of small generators whose ideal has a large Gröbner basis? How would I go about searching for such examples (besides a brute-force approach of trying random ideals)?

  • 0
    Point of interest: As f$a$r as I've heard, the $b$$a$d examples people used to show the worst-case complexity are not very $g$eometrical in nature.2012-12-09

2 Answers 2

1

I just found the following example, from this paper:

GroebnerBasis[{x^5 + y^5 + z^5 - 1, x^3 + y^3 + z^2 - 1}, {x, y, z}] (* Is long *)

-1

$ (x5+y5+z5−1x3+y3+z2−1)(xyz) =(x5+y5+z5+−x3+y3+z2+−1)(xyz) =(x5)(xyz)+(y5)(xyz)+(z5)(xyz)+(−x3)(xyz)+(y3)(xyz)+(z2)(xyz)+(−1)(xyz) =x6yz+xy6z+xyz6−x4yz+xy4z+xyz3−xyz =x6yz+xy6z+xyz6−x4yz+xy4z+xyz3−xyz $

  • 0
    See [math notation guide](http://math.stackexchange.com/help/notation). You can [edit] your post to improve its appearance.2014-09-09