13
$\begingroup$

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)

Improve this question
$\endgroup$
11
  • $\begingroup$ Your ring Z[f_1,...,f_n] contains 1 by definition. Did you mean something else? $\endgroup$
    – Felipe Voloch
    May 3, 2010 at 15:27
  • 4
    $\begingroup$ But 1 is a constant polynomial. Am I missing something? $\endgroup$
    – Sidney Raffer
    May 3, 2010 at 15:28
  • $\begingroup$ 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. $\endgroup$
    – Cam McLeman
    May 3, 2010 at 17:24
  • $\begingroup$ 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. $\endgroup$
    – Cam McLeman
    May 3, 2010 at 17:37
  • 1
    $\begingroup$ 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]$. $\endgroup$
    – Wadim Zudilin
    May 4, 2010 at 11:17

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Guntram, Thank you for the reference to SAGBI bases. I'll check this out. $\endgroup$
    – Sidney Raffer
    May 4, 2010 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.