# 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? –  SJR 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

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.