Software for deciding ideal membership
$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, -23left( (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.
ring-theory algorithms ideals math-software computational-algebra
$endgroup$
|
show 3 more comments
$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, -23left( (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.
ring-theory algorithms ideals math-software computational-algebra
$endgroup$
$begingroup$
The best plan would be to fix the installation problem! I would be surprised if Macaulay2 is packaged for Debian.
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:51
$begingroup$
@MarianoSuárez-Alvarez Do you know where I can get help for installation of Macaulay2?
$endgroup$
– user38268
Dec 13 '12 at 5:54
$begingroup$
There is a Macaulay2 googlegroup; it is linked to from Macaulay2's homepage. There you should find help —they are the nicest people!
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:56
$begingroup$
@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?
$endgroup$
– user38268
Dec 13 '12 at 6:03
$begingroup$
I would use Magma or Pari/gp, since this is kind of a algorithmic number theory thingy (equation order etc.)
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 6:15
|
show 3 more comments
$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, -23left( (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.
ring-theory algorithms ideals math-software computational-algebra
$endgroup$
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, -23left( (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.
ring-theory algorithms ideals math-software computational-algebra
ring-theory algorithms ideals math-software computational-algebra
edited Dec 8 '18 at 14:44
Rodrigo de Azevedo
13k41958
13k41958
asked Dec 13 '12 at 5:48
user38268
$begingroup$
The best plan would be to fix the installation problem! I would be surprised if Macaulay2 is packaged for Debian.
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:51
$begingroup$
@MarianoSuárez-Alvarez Do you know where I can get help for installation of Macaulay2?
$endgroup$
– user38268
Dec 13 '12 at 5:54
$begingroup$
There is a Macaulay2 googlegroup; it is linked to from Macaulay2's homepage. There you should find help —they are the nicest people!
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:56
$begingroup$
@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?
$endgroup$
– user38268
Dec 13 '12 at 6:03
$begingroup$
I would use Magma or Pari/gp, since this is kind of a algorithmic number theory thingy (equation order etc.)
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 6:15
|
show 3 more comments
$begingroup$
The best plan would be to fix the installation problem! I would be surprised if Macaulay2 is packaged for Debian.
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:51
$begingroup$
@MarianoSuárez-Alvarez Do you know where I can get help for installation of Macaulay2?
$endgroup$
– user38268
Dec 13 '12 at 5:54
$begingroup$
There is a Macaulay2 googlegroup; it is linked to from Macaulay2's homepage. There you should find help —they are the nicest people!
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:56
$begingroup$
@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?
$endgroup$
– user38268
Dec 13 '12 at 6:03
$begingroup$
I would use Magma or Pari/gp, since this is kind of a algorithmic number theory thingy (equation order etc.)
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 6:15
$begingroup$
The best plan would be to fix the installation problem! I would be surprised if Macaulay2 is packaged for Debian.
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:51
$begingroup$
The best plan would be to fix the installation problem! I would be surprised if Macaulay2 is packaged for Debian.
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:51
$begingroup$
@MarianoSuárez-Alvarez Do you know where I can get help for installation of Macaulay2?
$endgroup$
– user38268
Dec 13 '12 at 5:54
$begingroup$
@MarianoSuárez-Alvarez Do you know where I can get help for installation of Macaulay2?
$endgroup$
– user38268
Dec 13 '12 at 5:54
$begingroup$
There is a Macaulay2 googlegroup; it is linked to from Macaulay2's homepage. There you should find help —they are the nicest people!
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:56
$begingroup$
There is a Macaulay2 googlegroup; it is linked to from Macaulay2's homepage. There you should find help —they are the nicest people!
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:56
$begingroup$
@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?
$endgroup$
– user38268
Dec 13 '12 at 6:03
$begingroup$
@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?
$endgroup$
– user38268
Dec 13 '12 at 6:03
$begingroup$
I would use Magma or Pari/gp, since this is kind of a algorithmic number theory thingy (equation order etc.)
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 6:15
$begingroup$
I would use Magma or Pari/gp, since this is kind of a algorithmic number theory thingy (equation order etc.)
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 6:15
|
show 3 more comments
3 Answers
3
active
oldest
votes
$begingroup$
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 :
$endgroup$
$begingroup$
See my answer below :D :D :D :D :D :D :D :D :D
$endgroup$
– user38268
Dec 13 '12 at 6:36
add a comment |
$begingroup$
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. )
$endgroup$
$begingroup$
If you want, I can add some details later.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 7:09
$begingroup$
Can you add some details please? I have never heard of the hermite normal form, perhaps an example to illustrate this? Thanks.
$endgroup$
– user38268
Dec 13 '12 at 7:34
1
$begingroup$
@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.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 9:29
$begingroup$
Dear Hans, I have found the expression of $(23)(alpha - 3)$ in terms of members of the ideal. Please see my answer below.
$endgroup$
– user38268
Dec 13 '12 at 10:51
1
$begingroup$
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
$endgroup$
– user38268
Dec 13 '12 at 12:20
|
show 1 more comment
$begingroup$
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.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f257698%2fsoftware-for-deciding-ideal-membership%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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 :
$endgroup$
$begingroup$
See my answer below :D :D :D :D :D :D :D :D :D
$endgroup$
– user38268
Dec 13 '12 at 6:36
add a comment |
$begingroup$
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 :
$endgroup$
$begingroup$
See my answer below :D :D :D :D :D :D :D :D :D
$endgroup$
– user38268
Dec 13 '12 at 6:36
add a comment |
$begingroup$
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 :
$endgroup$
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 :
answered Dec 13 '12 at 6:16
Mariano Suárez-ÁlvarezMariano Suárez-Álvarez
111k7155284
111k7155284
$begingroup$
See my answer below :D :D :D :D :D :D :D :D :D
$endgroup$
– user38268
Dec 13 '12 at 6:36
add a comment |
$begingroup$
See my answer below :D :D :D :D :D :D :D :D :D
$endgroup$
– user38268
Dec 13 '12 at 6:36
$begingroup$
See my answer below :D :D :D :D :D :D :D :D :D
$endgroup$
– user38268
Dec 13 '12 at 6:36
$begingroup$
See my answer below :D :D :D :D :D :D :D :D :D
$endgroup$
– user38268
Dec 13 '12 at 6:36
add a comment |
$begingroup$
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. )
$endgroup$
$begingroup$
If you want, I can add some details later.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 7:09
$begingroup$
Can you add some details please? I have never heard of the hermite normal form, perhaps an example to illustrate this? Thanks.
$endgroup$
– user38268
Dec 13 '12 at 7:34
1
$begingroup$
@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.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 9:29
$begingroup$
Dear Hans, I have found the expression of $(23)(alpha - 3)$ in terms of members of the ideal. Please see my answer below.
$endgroup$
– user38268
Dec 13 '12 at 10:51
1
$begingroup$
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
$endgroup$
– user38268
Dec 13 '12 at 12:20
|
show 1 more comment
$begingroup$
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. )
$endgroup$
$begingroup$
If you want, I can add some details later.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 7:09
$begingroup$
Can you add some details please? I have never heard of the hermite normal form, perhaps an example to illustrate this? Thanks.
$endgroup$
– user38268
Dec 13 '12 at 7:34
1
$begingroup$
@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.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 9:29
$begingroup$
Dear Hans, I have found the expression of $(23)(alpha - 3)$ in terms of members of the ideal. Please see my answer below.
$endgroup$
– user38268
Dec 13 '12 at 10:51
1
$begingroup$
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
$endgroup$
– user38268
Dec 13 '12 at 12:20
|
show 1 more comment
$begingroup$
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. )
$endgroup$
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. )
edited Dec 13 '12 at 9:35
answered Dec 13 '12 at 6:20
Hans GiebenrathHans Giebenrath
799613
799613
$begingroup$
If you want, I can add some details later.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 7:09
$begingroup$
Can you add some details please? I have never heard of the hermite normal form, perhaps an example to illustrate this? Thanks.
$endgroup$
– user38268
Dec 13 '12 at 7:34
1
$begingroup$
@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.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 9:29
$begingroup$
Dear Hans, I have found the expression of $(23)(alpha - 3)$ in terms of members of the ideal. Please see my answer below.
$endgroup$
– user38268
Dec 13 '12 at 10:51
1
$begingroup$
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
$endgroup$
– user38268
Dec 13 '12 at 12:20
|
show 1 more comment
$begingroup$
If you want, I can add some details later.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 7:09
$begingroup$
Can you add some details please? I have never heard of the hermite normal form, perhaps an example to illustrate this? Thanks.
$endgroup$
– user38268
Dec 13 '12 at 7:34
1
$begingroup$
@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.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 9:29
$begingroup$
Dear Hans, I have found the expression of $(23)(alpha - 3)$ in terms of members of the ideal. Please see my answer below.
$endgroup$
– user38268
Dec 13 '12 at 10:51
1
$begingroup$
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
$endgroup$
– user38268
Dec 13 '12 at 12:20
$begingroup$
If you want, I can add some details later.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 7:09
$begingroup$
If you want, I can add some details later.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 7:09
$begingroup$
Can you add some details please? I have never heard of the hermite normal form, perhaps an example to illustrate this? Thanks.
$endgroup$
– user38268
Dec 13 '12 at 7:34
$begingroup$
Can you add some details please? I have never heard of the hermite normal form, perhaps an example to illustrate this? Thanks.
$endgroup$
– user38268
Dec 13 '12 at 7:34
1
1
$begingroup$
@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.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 9:29
$begingroup$
@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.
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 9:29
$begingroup$
Dear Hans, I have found the expression of $(23)(alpha - 3)$ in terms of members of the ideal. Please see my answer below.
$endgroup$
– user38268
Dec 13 '12 at 10:51
$begingroup$
Dear Hans, I have found the expression of $(23)(alpha - 3)$ in terms of members of the ideal. Please see my answer below.
$endgroup$
– user38268
Dec 13 '12 at 10:51
1
1
$begingroup$
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
$endgroup$
– user38268
Dec 13 '12 at 12:20
$begingroup$
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
$endgroup$
– user38268
Dec 13 '12 at 12:20
|
show 1 more comment
$begingroup$
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.
$endgroup$
add a comment |
$begingroup$
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.
$endgroup$
add a comment |
$begingroup$
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.
$endgroup$
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.
edited Dec 13 '12 at 10:50
answered Dec 13 '12 at 6:35
user38268
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f257698%2fsoftware-for-deciding-ideal-membership%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
The best plan would be to fix the installation problem! I would be surprised if Macaulay2 is packaged for Debian.
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:51
$begingroup$
@MarianoSuárez-Alvarez Do you know where I can get help for installation of Macaulay2?
$endgroup$
– user38268
Dec 13 '12 at 5:54
$begingroup$
There is a Macaulay2 googlegroup; it is linked to from Macaulay2's homepage. There you should find help —they are the nicest people!
$endgroup$
– Mariano Suárez-Álvarez
Dec 13 '12 at 5:56
$begingroup$
@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?
$endgroup$
– user38268
Dec 13 '12 at 6:03
$begingroup$
I would use Magma or Pari/gp, since this is kind of a algorithmic number theory thingy (equation order etc.)
$endgroup$
– Hans Giebenrath
Dec 13 '12 at 6:15