8
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ I know the Mayr Meyer ideals are the standard example of doubly-exponentially complex ideals - I think that might be an example of this as well (although your definition of "size" of a polynomial isn't quite the complexity measure those're using.) $\endgroup$ Jun 8, 2012 at 17:48
  • $\begingroup$ @Gwyn: Yes, I had in mind the Mayr-Meyer's paper (about commutative semigroups and polynomial ideals). Perhaps somebody can say whether their examples satisfies "my" condition. $\endgroup$
    – user6976
    Jun 8, 2012 at 19:15

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Thomas: As far as I understand, this is all about polynomial rings over fields. I found a nice paper Aschenbrenner, Matthias Ideal membership in polynomial rings over the integers. J. Amer. Math. Soc. 17 (2004), no. 2, 407–441, which is about integer polynomials. I think it is more related to my question although the problem considered there is different. It is more like the uniform membership problem considered by Mayr and Meyer. But the "size" in that paper is similar to what I need. $\endgroup$
    – user6976
    Jun 9, 2012 at 11:05
  • $\begingroup$ Yes true, Everything I talked about is for coefficients in a field. Thanks for the reference, I'll take a look. $\endgroup$ Jun 9, 2012 at 13:47
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What is an involutive basis? $\endgroup$
    – user6976
    Jun 10, 2012 at 12:33
  • $\begingroup$ @mark-sapir I'm an amateur in this area, but heard of it through a colleague. The notions arose through work on PDEs by Thomas, Janet, Pommaret and have been transferred to commutative algebra by a number of workers, e.g. Ger. This suggested a thesis topic for Gareth Evans at Bangor, supervised by Chris Wensley, to consider the non commutative case. His thesis is available from arXiv:math/0602140v1 [math.RA] and has a nice discussion in Chapter 4 of the comparisons of commutative Grobner and involutive reductions, the latter having much tighter control of the reductions required (see p. 77). $\endgroup$ Jun 13, 2012 at 11:18
  • $\begingroup$ This might be interesting but has nothing to do with the question. $\endgroup$
    – user6976
    Jun 16, 2012 at 3:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.