Ideal with large Grobner basis with respect to one monomial order What is an example of a set of at most four polynomials $f_1,\ldots,f_n$ (in any number of variables) such that $\{f_i\}$ is a Grobner basis of $I=\langle f_i\rangle$ with respect to one monomial order, but any Grobner basis for $I$ with respect to another monomial order has at least $1000$ elements?
I don't know how to start finding this set of polynomials. What should be the idea?

I know this is not what the OP has asked for, but I can offer the following start by sketching the solution to an easier problem:
I am going to give you $f,g$ in 2 variables and a monomial ordering such that the Buchberger algorithm - in the process of creating the Grobner basis - gives at least 1000 elements; while under a different monomial ordering, $f,g$ is itself a Grobner basis for the ideal it generates. I know the OP asked for that ALL Grobner basis has at least a 1000 elements, while I only show here an instance of the Buchberger's algorithm taking ridiculously long to terminate.
Take Lex ordering, with $x>y$, and  $f(x,y)=x^{1000}$ and $g(x,y)=x^{999}y^{999}+x^{998}y^{998}+...+xy$. If you compute the $S$-polynomial, you multiply $g$ by $x$ and deleting the leading term, getting $x^{999}y^{998}+x^{998}y^{997}+...+x^2y$. None of the terms are divisible by $LT(f), LT(g)$. So you throw this new $f_3$ into your basis. If you now compute $S(f,f_3)$, you again multiply $f_3$ by $x$ and throw away the leading term, getting $x^{999}y^{997}+x^{998}y^{996}+...+x^3y$. Hopefully the pattern is clear, and why the Buchberger algorithm will give at least 1000 elements.
Now, I claim that you can modify $g$ slightly so that this above process still gives at least 1000 elements, and so that under the monomial ordering Lex with $y>x$, $f,g$ is now a Grobner basis for the ideal it generates. I will let you figure this part out, so that you can still have some fun doing the problem! =]
