From polynomial ideal over $\mathbb{Q}$ to polynomial ideal over $\mathbb{Z}$

Question

Is there an algorithm to compute, given a polynomial ideal $I\subset \mathbb{Q}[x_1,\dotsc,x_n]$, the ideal $I\cap \mathbb{Z}[x_1,\dotsc,x_n]$ in $\mathbb{Z}[x_1,\dotsc,x_n]$?

The input and output can be given via a finite set of generators. From chapter 10 of book "Gröbner bases" by Becker and Weispfenning, I am familiar with Gröbner bases over PID, and in particular understand how to compute the intersection of polynomial ideals over PID (though it is not explicitly mentioned in the book, as far as I can see). However, $\mathbb{Z}[x_1,\dotsc,x_n]$ is not an ideal in $\mathbb{Q}[x_1,\dotsc,x_n]$. It is tempting to work in the ring $\frac{1}{D}\mathbb{Z}[x_1,\dotsc,x_n]$ for large very composite integer $D$, but how large is large enough?

Answer 1

I am aware that I am replying to an old question that has been satisfactorily answered, but I think it might be worth while pointing out, for the completeness of MathOverflow, that the question is discussed (in slightly greater generality, and with an example) as corollary 4.4.5 in the book An Introduction to Gröbner Bases by William Adams and Philippe Loustaunau (AMS 1994, Graduate Studies in Mathematics 3). The method is the same as in the approved answer, but formulated in a slightly different way. Their statements (very slightly reworded) are:

Proposition 4.4.1 [computation of the saturation]: Let $R$ be an integral domain and $I$ a non-zero ideal of $A = R[x_1,\ldots,x_n]$. Let $g\in A$, $g\neq 0$. Let $w$ be a new variable. Consider the ideal $\langle I,wg-1\rangle$ of $A[w]$. Then $I A_g \cap A = \langle I, wg-1\rangle \cap A$ where $A_g = A[\frac{1}{g}]$.

(Note that the intersection $\langle I, wg-1\rangle \cap A$ in $A[w]$ can be computed using an elimination order on the variables: it is theorem 4.3.6 in that book.)

Proposition 4.4.4: Let $R$ be an integral domain with $k$ its quotient field. Let $I$ be a non-zero ideal of $A = R[x_1,\ldots,x_n]$ and let $G = \{g_1,\ldots,g_t\}$ be a Gröbner basis for $I$ with respect to some term ordering. Let $s$ be the product of the leading coefficients of $g_1,\ldots,g_t$. Then $$I k[x_1,\ldots,x_n] \cap R[x_1,\ldots,x_n] = IR_s[x_1,\ldots,x_n] \cap R[x_1,\ldots,x_n]$$

(This is essentially what the approved answer to this question explains.)

Corollary 4.4.5: Let $R$ be an integral domain in which linear equations are algorithmically solvable and let $k$ be its quotient field. Let $I$ be an ideal of $A = R[x_1,\ldots,x_n]$. Then we can compute generators for the ideal $I k[x_1,\ldots,x_n] \cap R[x_1,\ldots,x_n]$.

(This follows immediately from the above results.)

Answer 2

Let J be a finitely generated ideal in $A = \mathbf{Z}[x_1,\dotsc,x_n]$. (Take your ideal $I$ and scale its generators to clear denominators.) The ideal you want is then $$ J' = \{f\in A: \exists n\in\mathbf{Z}. n\neq 0 \text{ and } nf\in J\}. $$ To find a finite list of generators for $J'$ we do the following.

1. Compute a Groebner basis for $J$, and let $N$ be the product of the leading coefficients of the elements of the Groebner basis.

2. Compute a finite list of generators for the saturation $(J:N^\infty)$ of $J$ with respect to $N$. One can compute such generators using Groebner bases in several ways, which you can probably look up easily.

We have $J' = (J:N^\infty)$, and so we have the desired generators for $J'$.

Here is why it works: it is clear that $(J:N^\infty)$ is contained in $J'$. To see the reverse inclusion we argue as follows. Note that the ring $(A/J)_N$ (invert $N$) is free over $\mathbf{Z}[1/N]$, since when we invert $N$ the Groebner basis for $J$ becomes monic, and the division algorithm allows us to reduce elements of $A$ uniquely to sums standard monomials modulo $J$. Consequently, for any non-zero $d\in\mathbf{Z}[1/N]$ and any $f\in (A/J)_N$, if we have $df = 0$, then we may conclude that $f=0$.

Now let $f\in J'$: we have $f\in A$ and $nf\in J$ for some $n\in\mathbf{Z}$ with $n\neq 0$. We then have $nf = 0$ in $(A/J)_N$, and so we may conclude that $f=0$ in $(A/J)_N$. The kernel of $A/J\to (A/J)_N$ is the image modulo $J$ of the saturation $(J:N^\infty)$; we thus have $f\in (J:N^\infty)$, as desired.