# A decision problem concerning polynomial rings

Let $f_1,f_2, \ldots ,f_n$ be polynomials in any number of variables with algebraic coefficients. Is there algorithm to determine whether the ring $\mathbb{Z}[f_1,f_2,\ldots ,f_n]$ contains a non-constant polynomial with integer coefficients?

To illustrate what the game is here, I'll give some examples:

1. $\mathbb{Z}[\sqrt{2}x-y]\cap \mathbb{Z}[x,y]=\mathbb{Z}$. Proof-sketch: Suppose that $H\in\mathbb{Z}[u]$ and $H(\sqrt{2}x-y)\in\mathbb{Z}[x,y]$. Choose a sequence of distinct points $(x_n,y_n)\in\mathbb{Z}^2$ such that $\sqrt{2}x_n-y_n$ converges. Then $H(\sqrt{2}x_n-y_n)$ is eventually an integer constant $c$. Thus the equation $H(u)=c$ has infinitely many solutions. It follows that $H$ is identically $c$

2. $\mathbb{Z}[\sqrt{2}x-y, 2\sqrt{2}xy-z]$ contains the polynomial $2x^2+y^2-z$. (Take the square of the first polynomial plus the second.) Note that the generators are algebraically independent.

3. $\mathbb{Z}[\sqrt{2}x-y, \sqrt{3}xy-z]\cap \mathbb{Z}[x,y,z]=\mathbb{Z}$. (I know only a rather lengthy and ad hoc proof)

• Your ring Z[f_1,...,f_n] contains 1 by definition. Did you mean something else? – Felipe Voloch May 3 '10 at 15:27
• But 1 is a constant polynomial. Am I missing something? – Sidney Raffer May 3 '10 at 15:28
• You mean Z[f_1,f_2,...f_n], not Z[f_1f_2...f_n], right? I suspect it's if and only if your f_i's contains a set of Galois conjugate polynomials up to constant multiples, or something to that effect. – Cam McLeman May 3 '10 at 17:24
• Ah, no, it's a little more complicated, since you could have products and powers forming a complete set of conjugates. And whatever theorem comes out of this line of thinking might not be easy to implement algorithmically. – Cam McLeman May 3 '10 at 17:37
• Your 3rd example: assuming that the intersection is nontrivial, pick a polynomial $\sum a_{ij}(\sqrt2x-y)^i(\sqrt3xy-z)^j=\sum b_{ijk}x^iy^kz^k$ of minimal possible degree, say $K$, in $z$. Example 1 implies $K>0$. Differentiate the polynomial w.r.t. $z$ once to get a new polynomial of degree $K-1$ in $z$. This is possible iff the new polynomial is trivial, that is, the original one has the form $bz+\mathbb Z[x,y]$ for $b\in\mathbb Z$. This implies that the right-hand side assumes the form $a(\sqrt3xy-z)+\mathbb Z[\sqrt2x-y]$, hence $a=-b\ne0$. But $a\sqrt3$ is never in $\mathbb Z[\sqrt2]$. – Wadim Zudilin May 4 '10 at 11:17

## 1 Answer

Let $\alpha \in \overline{\mathbb{Q}}$ be such that all $f_i$ have coefficients in $\mathbb{Q}(\alpha)$ and $k \in \mathbb{N}$ such that the $f_i$ are in $\mathbb{Q}(\alpha)[y_1, \ldots, y_k]$. Then the ideal the generated by the $f_i$ in this ring corresponds to an ideal $J$ in $\mathbb{Q}[x,y_1, \ldots, y_k]$ which is generated by lifts of the $f_i$ together with the minimal polynomial $f$ of $\alpha.$ Now clearly a neccessary condition for your problem is that $J \cap \mathbb{Q}[y_1 \ldots, y_k]\neq \{0\}.$ This can be checked algorithmically by computing a Groebner basis with respect to an elimination term ordering, c.f. e.g. Kreuzer/Robbiano, Computational Commutative Algebra.

For a complete solution to the original question, you are not interested in the ideal generated by the polynomials but in the subalgebra they generate. Again, sometimes it"s possible to compute the gadgets corresponding to Groebner bases for ideals; these then are called SAGBI bases, which you would need to compute with respect to an elimination term ordering. In contrast to Groebner bases, these do not neccessarily exist, though.

To summarise: SAGBI basis is the notion you're looking for, if I'm not mistaken.

• Guntram, Thank you for the reference to SAGBI bases. I'll check this out. – Sidney Raffer May 4 '10 at 17:27