4
$\begingroup$

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.

  • 0
    I think you crack a nut with a sledge hammer. Attacking this problem with groebner bases makes it more complicated then it actual is. In my opinion the approach with $\mathbb Z$-modules is more elementary since it is just linear algebra over $\mathbb Z$. Moreover its faster then groebner bases computations and its output is not exponential.2012-12-13

3 Answers 3

2

Here is the computation from Macaulay2:

enter image description here

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.

5

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 :  
  • 0
    See my answer below :D :D :D :D :D :D :D :D :D2012-12-13
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. )

  • 1
    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 :D2012-12-13