Let $f(x)$, $g(x)$ be two univariate, coprime, integer polynomials and let $I=\big(f(x),g(x)\big)$ the ideal of $\mathbb{Z}[x]$ generated by $f, g$. Let $I \cap \mathbb{Z}$, that is, the elements of $\mathbb{Z}$ which can be expressed as linear combinations of $f(x), g(x)$ with coefficients in $\mathbb{Z}[x]$. $I \cap \mathbb{Z}$ is clearly an ideal in $\mathbb{Z}$. The following argument shows that, given two coprime integer polynomials $f,g$, the ideal $I \cap \mathbb{Z}$ of $\mathbb{Z}$ has always non zero elements:

If $f,g$ are considered as elements of $\mathbb{Q}[x]$, Bezout's identity tells us that there exists a pair of unique rational polynomials $U(x)$, $V(x)$ with $\deg U<\deg g$, $\deg V<\deg f$ such that $$ U(x)f(x)+V(x)g(x)=1 $$ Thus, clearing denominators in the above identity, we get that there exists a pair of unique integer polynomials $u(x)$, $v(x)$ with $\deg u<\deg g$, $\deg v<\deg f$ such that $$ u(x)f(x)+v(x)g(x)=c $$ where $c$ is the $lcm$ of the denominators of $U,V$ and: $u=cU$, $v=cV$. Thus: $0 \neq c\in I \cap \mathbb{Z}$.

Question $1$: Can we determine a sufficient and necessary condition such that: $\mathbb{Z}\subset I \cap \mathbb{Z}$?

Question $2$: Is there a general method for determining the least positive generator of $I \cap \mathbb{Z}$ ?


P.S.: The second question above, is actually part of the question posted in the first of the references above. However, it is posted here rather as a problem of commutative algebra than a problem of number theory.

  • $\begingroup$ Crossposted from math.SE: math.stackexchange.com/q/1907770/264 $\endgroup$ – Zev Chonoles Aug 29 '16 at 20:31
  • 2
    $\begingroup$ The answer to question 2 is yes, there is a general method. First, find $c$ as in your post. After passing to the quotient ring, where we mod out by the ideal $(c)$, you are working in a finite ring $(\mathbb{Z}/c\mathbb{Z})[x]/(\overline{f}(x),\overline{g}(x))$. It is then a finite computation to figure out the additive order of $1$ in that ring. $\endgroup$ – Pace Nielsen Aug 29 '16 at 20:48
  • $\begingroup$ @Pace Nielsen: thank you for the idea. So, I guess in the example cited in the first reference, $f(x)=2x+1$, $g(x)=2x+17$, it would have been: $\mathbb{Z}_{16}[x]/\big(2x+1\big)$, right? $\endgroup$ – Konstantinos Kanakoglou Aug 30 '16 at 14:32
  • $\begingroup$ @KonKan Yes, and then in that ring we get $1=-2x$, and so $1=(1)^4=(-2x)^4=16x^4=0$ modulo 16. Thus $1$ belongs to your ideal. $\endgroup$ – Pace Nielsen Aug 30 '16 at 14:39
  • $\begingroup$ yes I see. But, you mean $1=0$ modulo $16(2x+1)$ right? Thus, the ring $\mathbb{Z}_{16}[x]/\big(2x+1\big)$ is zero, so $(2x+1)=\mathbb{Z}_{16}[x]$. But in the general case, I mean for higher degree polynomials, we should resort to the use of Gröbner basis techniques, shouldn't we? $\endgroup$ – Konstantinos Kanakoglou Aug 31 '16 at 2:21

For question 2, compute a Gröbner basis over $\mathbb{Z}$ for the ideal generated by $f(x)$ and $g(x)$, which gives the required generator. You can do this easily in SageMathCloud (available free to use). The algorithm behind this computation is exactly what you would be doing by hand to find the generator. This also answers question 1, if you allow an algorithm to provide a necessary and sufficient condition.

  • $\begingroup$ thank you very much for the idea. I had this somewhere in the back of my mind but I was hoping to .. avoid it ;) I am not very familiar with Gröbner bases and as far as I remember, the initiall algorithm of Buchberger deals with polynomials over a field. Where can I find smt on how it works in $\mathbb{Z}[x]$? P.S.: thanks for mentioning SageMathCloud. I did not knew it. $\endgroup$ – Konstantinos Kanakoglou Aug 31 '16 at 11:41
  • 1
    $\begingroup$ Chapter 4 of An Introduction to Gröbner Bases by Adams and Loustaunau contains complete details for polynomials with coefficients in a ring where you can compute GCDs. This is implemented in Sage if you apply the groebner_basis method to an ideal generated by polynomials with integer coefficients. A slight caution: the default in Sage is to use the algorithm from Singular, but apparently this has a bug in the integer implementation, so just use Macauley2, as in I.groebner_basis(algorithm = 'macaulay2:gb'), where I is the ideal. Of course this works for polynomials in several variables too. $\endgroup$ – Douglas Lind Aug 31 '16 at 13:00
  • $\begingroup$ SageMathCloud is a new way to access Sage from any web browser, with no hassles about installing anything. It's amazing, however there's a fairly steep learning curve to use it effectively, but worth the effort if you're going to be using mathematical software. $\endgroup$ – Douglas Lind Aug 31 '16 at 13:05
  • 1
    $\begingroup$ It is a property of Gröbner bases that the contraction of an ideal $I$ to $\mathbb{Z}$ is generated by those elements in the Gröbner basis which are in $\mathbb{Z}$, and this is one of the main features. This becomes clearer in several variables. If you have an ideal $J\subset\mathbb{Z}[x,y,z]$ and you want to compute the contraction ideal $K = J\cap\mathbb{Z}[x,y]$, all you do is compute a Gröbner basis for $J$ using the lex ordering $x<y<z$, and then $K$ is generated by the elements in the Gröbner basis that are polynomials in just $x$ and $y$. See the book by Cox, Little, and O'Shea. $\endgroup$ – Douglas Lind Aug 31 '16 at 22:02
  • 1
    $\begingroup$ No, they only consider coefficients in a field, since their main focus is algebraic geometry. In fact, they generally consider algebraically close fields, although the Gröbner basis algorithms don't use this. It's relatively straightforward to adapt these ideas to $\mathbb{Z}$ coefficients, you just have to replace the division algorithm with cancelling leading terms up to the GCD of the leading coefficients. Roughly speaking, $\mathbb{Z}$ and $k[x]$ are UFDs of dimension 1 (both are PIDs), and so $\mathbb{Z}[x]$ and $k[x,y]=k[x][y]$ work roughly the same. [CLO] is an amazing book! $\endgroup$ – Douglas Lind Sep 2 '16 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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