Software for deciding ideal membership

Question

Let $\alpha$ be such that $\alpha^3 + \alpha + 1 = 0$ and consider $\Bbb{Z}[\alpha]$. Suppose I have an ideal in $\Bbb{Z}[\alpha]$ that is given by

$$ I = \Bigg(23^3, 23^2(\alpha - 3), 23(\alpha - 10)^2, -23\left( (\alpha-3)^2 - (\alpha - 3) + 1 \right), 23^2(\alpha - 10),23(\alpha - 10)(\alpha - 3)\Bigg).$$

How can I use a computer algebra system to decide if $23$ or $23(\alpha - 3)$ is in my ideal $I$? I have tried for some time now to do this by hand but have failed. I have been unable to install Macaulay2 on my computer (I am using ubuntu 12.04 LTS).

Otherwise, is there a systematic algorithm that can be done by hand to decide such problems?

Thanks.

Answer 1

Here is the computation from Macaulay2:

On the other hand, I have also found that

$$\begin{eqnarray*} 15(23^2)(\alpha - 3) + 3(23^2)(\alpha - 10)+ 45(23)(\alpha-3)(\alpha-10) + \hspace{1in} \\ 11(23)(\alpha - 10)^2 + 56(\alpha-3)(\alpha- 10)^2 &=& 23(\alpha - 3) \end{eqnarray*}$$

which verifies the calculation of Macaulay2.

Answer 2

Using M2:

i1 : R = ZZ[a]

o1 = R

o1 : PolynomialRing

i2 : I = ideal (a^3-a-1)

            3
o2 = ideal(a  - a - 1)

o2 : Ideal of R

i3 : S = R / I

o3 = S

o3 : QuotientRing

i4 : J = ideal (23^3, 23^2*(a-3), 23*(a-10)^2, -23*((a-3)^2-(a-3)+1),23^2*(a-10), 23*(a-10)*(a-3))

                                   2                     2                   
o4 = ideal (12167, 529a - 1587, 23a  - 460a + 2300, - 23a  + 161a - 299, 529a
     -------------------------------------------------------------------------
                2
     - 5290, 23a  - 299a + 690)

o4 : Ideal of S

i5 : (23*(a-3)) % J == 0

o5 = true

i6 : 23 % J == 0

o6 = true

i7 : 

Answer 3

Since you also asked for an algorithm to do it by hand. Your ring $\mathbb Z[\alpha]$ is a free $\mathbb Z$-module of rank $3$ with basis $B = (1,\alpha,\alpha^2)$. Moreover any ideal $I$ of $\mathbb Z[\alpha]$ is also a free $\mathbb Z$-module of rank 3. Therefore you can compute a basis matrix of $I$ with respect to $B$. Now you can check easily if a given element is contained in $I$. (Hermite normal form etc.)

(I think this is the way its done in some of the algorithmic number theory packages. Ideal membership for ideals of orders is reduced to $\mathbb Z$-module algorithms.)

And ofcourse it avoids groebner basis.

Details:

Let me first show how to use the Hermite normal form to check for membership. Consider the free $\mathbb Z$-module $M \subseteq \mathbb R ^2$ given by the generators $(2,6), (4,3), (6,9)$. Writing this in a matrix we have $$ A = \begin{pmatrix} 2 & 6 \\ 4 & 3 \\ 6 & 9 \end{pmatrix}. $$ ($M$ is generated by the rows of $A$). Now we want to determine if the element $(20,87) \in \mathbb R^2$ is contained $M$. This means we want to know if there exists $v \in \mathbb Z^3$ such that $v M = (20,87)$. If we would allow $v$ to have real coefficients, this could easily answered by computing the row echelon form. But this uses division, so we cannot use this algorithm. But since $\mathbb Z$ is a principal ideal domain, there exists the Hermite normal form, which enjoys similar properties as the row echelon form over fields. More precisely there exists a transformation $U \in \operatorname{GL}_3(\mathbb Z)$ such that $UA = H$ is in is an upper triangular matrix. Since $U$ is invertible, the rows of $H$ also give an generating system of $M$. Using the upper triangular form, one also knows that they are linearly independent. Thus the rows of $H$ are a basis of $M$. In our case, the Hermite normal form $H$ of $A$ is given by $$ H = \begin{pmatrix} 2 & 6 \\ 0 & 9 \\ 0 & 0 \end{pmatrix} $$ and we easily deduce $$ (20, 87) = 10 (2,6) + 3 (0,9) \in M.$$ This means $(20,87) = (10,3,0) H = (10,3,0)U A$. Therefore the coefficients of $(20,87)$ in our generating system $A$ are given by $(10,3,0)U$.

(There are is no standard definition for the Hermite normal form regarding upper or lower triangular form. So don't be confused if you read about it. Also, some people think of modules generated by columns instead of rows. This is just a matter of taste. )