# Software for deciding ideal membership

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.

-
The best plan would be to fix the installation problem! I would be surprised if Macaulay2 is packaged for Debian. –  Mariano Suárez-Alvarez Dec 13 '12 at 5:51
@MarianoSuárez-Alvarez Do you know where I can get help for installation of Macaulay2? –  user38268 Dec 13 '12 at 5:54
There is a Macaulay2 googlegroup; it is linked to from Macaulay2's homepage. There you should find help —they are the nicest people! –  Mariano Suárez-Alvarez Dec 13 '12 at 5:56
@MarianoSuárez-Alvarez Is there an algorithm that I can do by hand to decide if my element above is in the ideal or not? –  user38268 Dec 13 '12 at 6:03
This is one application of groebner basis. Sympy has a groebner basis implementation! Don't bother with the sympy ubuntu package though (unless you are also using LaTex on your ubuntu system), but install directly from source (in python that's 'python setup.py install' in the unzipped/untared dir). –  Peter Sheldrick Dec 13 '12 at 6:25

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 :

-
See my answer below :D :D :D :D :D :D :D :D :D –  user38268 Dec 13 '12 at 6:36

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

-
If you want, I can add some details later. –  Hans Giebenrath Dec 13 '12 at 7:09
Can you add some details please? I have never heard of the hermite normal form, perhaps an example to illustrate this? Thanks. –  user38268 Dec 13 '12 at 7:34
@BenjaLim: I added the stuff about $\mathbb Z$-modules. If you want I can give more details for your application. But this will take some time. –  Hans Giebenrath Dec 13 '12 at 9:29
Dear Hans, I have found the expression of $(23)(\alpha - 3)$ in terms of members of the ideal. Please see my answer below. –  user38268 Dec 13 '12 at 10:51
I basically guessed that a solution could be found with only the 5 generators of the ideal (exlucing $23^2$) with integer coefficients $x_1,\ldots,x_5$. I set up a linear system and row reduced it to get expressions for $x_1,\ldots,x_5$ in fractions. Of course these had free variables in there, I found the smallest integer (and entered it into the free variable) for which each $x_i$ was an integer and checked the answer. If you plug that expression below into wolframalpha you'll see it's correct :D –  user38268 Dec 13 '12 at 12:20

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.

-