# Simple generators with a complex Gröbner basis

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

-
Point of interest: As far as I've heard, the bad examples people used to show the worst-case complexity are not very geometrical in nature. –  Andrew Dec 9 '12 at 1:37

## 2 Answers

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

-

$$(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$$

-
See math notation guide. You can edit your post to improve its appearance. –  Normal Human Sep 9 '14 at 1:44