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
    The best plan would be to fix the installation problem! I would be surprised if Macaulay2 is packaged for Debian.2012-12-13
  • 0
    @MarianoSuárez-Alvarez Do you know where I can get help for installation of Macaulay2?2012-12-13
  • 0
    There is a Macaulay2 googlegroup; it is linked to from Macaulay2's homepage. There you should find help —they are the nicest people!2012-12-13
  • 0
    @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?2012-12-13
  • 0
    I would use Magma or Pari/gp, since this is kind of a algorithmic number theory thingy (equation order etc.)2012-12-13
  • 0
    @PeterSheldrick I have installed Macaulay2 and indeed I can arrive at the result that I want. However can Macaulay2 give explicit expressions for why certain elements are in an ideal? I.e. in my example above can it give an expression for $23$ in terms of the generators of $I$?2012-12-13
  • 0
    @PeterSheldrick That is ok. Could you recommend me some references for Groebner bases computations by hand? I would certainly like to understand what's happening behind the scenes in Macaulay2.2012-12-13
  • 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. )

  • 0
    If you want, I can add some details later.2012-12-13
  • 0
    Can you add some details please? I have never heard of the hermite normal form, perhaps an example to illustrate this? Thanks.2012-12-13
  • 1
    @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.2012-12-13
  • 0
    Dear Hans, I have found the expression of $(23)(\alpha - 3)$ in terms of members of the ideal. Please see my answer below.2012-12-13
  • 0
    @BenjaLim How did you find it?2012-12-13
  • 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