5
$\begingroup$

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}$ ?

References:

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Crossposted from math.SE: math.stackexchange.com/q/1907770/264 $\endgroup$
    – Zev Chonoles
    Commented Aug 29, 2016 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
    Commented Aug 29, 2016 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
    Commented Aug 30, 2016 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
    Commented Aug 30, 2016 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
    Commented Aug 31, 2016 at 2:21

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\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
    Commented Aug 31, 2016 at 11:41
  • 2
    $\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
    Commented Aug 31, 2016 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
    Commented Aug 31, 2016 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
    Commented Aug 31, 2016 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
    Commented Sep 2, 2016 at 2:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .