Complexity of Groebner bases

Question

Let $I$ be an ideal in the polynomial ring $R=\mathbb{Z}[x_1,...,x_k]$. Let $F$ be a (reduced) Groebner basis of $I$. For every polynomial $f$ in $R$ let the size of $f$ be the sum of absolute values of coefficients of $f$ plus the degree of $f$ (so there are only finitely many polynomials of size $\le n$). If $f=\sum g_ip_i $ where $p_i\in F, g_i\in R$ is the decomposition of $f$, we call the sum of sizes of $g_i$ the size of the decomposition. For every $n$ let $D(n)$ be the maximal size of decomposition of a polynomial of size $\le n$. It is not difficult to show that $D(n)$ is at most $\exp n^l$ for some constant $l$.

Question Is there am example of $I$ with $D(n)$ super-exponential?

Update 1. Mayr and Meyer in The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. in Math. 46 (1982), no. 3, 305–329. Proved that the uniform word problem in finitely generated commutative semigroups and the uniform membership problem in polynomial ideals is exponential space complete. The ideals constructed in that paper may help in answering my question (see also the comment by Gwyn Whieldon below).

Update 2. Perhaps a paper Aschenbrenner, Matthias Ideal membership in polynomial rings over the integers. J. Amer. Math. Soc. 17 (2004), no. 2, 407–441 is more relevant than the paper by Mayr and Meyer (see a comment below).

As for the motivation: the problem is related to Dehn functions of certain solvable groups.

Answer 1

This is not a complete answer, just some related thoughts. I don't really know about the size that you define; the following (and the Mayr-Meyer paper) are about the degree of the $g_i$ with coefficients in a field. In 1926 Grete Hermann showed an upper bound that is doubly-exponential in the number of variables $k$. The Mayr-Meyer example, a binomial ideal, shows that her bound is sharp.

The Castelnuovo-Mumford regularity of an ideal is probably the most important invariant in this context. In "What can be computed in algebraic geometry" Bayer and Mumford explain that bounding the regularity in terms of the degrees of the generators allows to measure how complicated an ideal is. The regularity is nice because it is connected to free resolutions (degrees of relations) and vanishing of local cohomology (making it computable in some cases). There are examples where the regularity is doubly-exponential in the generating degree, but in many 'geometrically nice' situations one gets better bounds.

For one example: In "Gröbner bases of toric varieites" Sturmfels shows that there is an exponential bound for the regularity of toric ideals (which are essentially binomial prime ideals).

In general it is a different and more complicated story to bound the regularity in terms of the degrees in a Gröbner basis as those are usually higher than in a generating set.

Another interesting result is due to Kollar ("Sharp effective Nullstellensatz") which shows that writing 1 as a member of an ideal with empty variety can be done with coefficients of exponentially bounded degree.

Answer 2

Just an idle thought: could involutive bases be relevant to this area? See for example papers by Gerdt available on the arXiv.