Return to 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.

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.

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

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.

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?

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