Welcome to MathOverflow

Question

13

3

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:

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

edited May 3 2010 at 19:16

asked May 3 2010 at 15:05

SJR
3,082●1●6●16

Your ring Z[f_1,...,f_n] contains 1 by definition. Did you mean something else? – Felipe Voloch May 3 2010 at 15:27

4

But 1 is a constant polynomial. Am I missing something? – SJR May 3 2010 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 2010 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 2010 at 17:37

1

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 2010 at 11:17

show 6 more comments

Guntram · Answer 1 · 2010-05-04 15:17:51Z UTC

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.

A decision problem concerning polynomial rings

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.