#7545 closed enhancement (fixed)
Gaussian and Eisenstein integers
Reported by:  wuthrich  Owned by:  davidloeffler 

Priority:  minor  Milestone:  sage7.1 
Component:  number fields  Keywords:  gaussian integers, Z[i], quadratic number ring 
Cc:  kcrisman, vdelecroix, katestange  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  Frédéric Chapoton, Vincent Delecroix, Katherine Stange, KarlDieter Crisman 
Report Upstream:  N/A  Work issues:  
Branch:  daee4f2 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
Define GaussianIntegers()
and EisensteinIntegers()
as orders in the appropriate number field.
Attachments (1)
Change History (46)
Changed 13 years ago by
comment:1 Changed 13 years ago by
 Status changed from new to needs_info
The added patch will add a file 'gaussian_integer.py' which adds GaussianIntegers
and GaussianNumberField
to sage. The elements of the GaussianIntegers
are elements in a quadratic Order, but they have a few more functions. Like factor
, gcd
, is_prime
, quo_rem
,... Also they are printed as a + b*i
not as b*i + a
. Also the coefficients of integers are in ZZ
, not in QQ
as for general quadratic orders.
I am not sure if I should propose this ticket for review and inclusion in sage. It maybe against the more general framework in number fields and will create silly exceptions. Also I still have not learned to do this in cython, so it is nowhere as efficient as it should be.
One might also want to change further things, like the function gcd
. Also QuadarticField(1)
should give back GaussianNumberFields
etc.
A futher issue is 'i'. By default i is a symbol expression. If someone types GaussianInteger()
he will probably assume that 'i' is in it afterwards. But changing this would probably not be a good idea.
Anyway, the patch is here to be looked at as it may inspire some further work in this direction.
comment:2 Changed 13 years ago by
I think this could be very useful to have. (In fact, it would be cool if the default i was in ZZ[i], and coerced down to the symbolics...) If an embedding into CC is specified then it would probably play better with symbolics.
comment:3 Changed 13 years ago by
The default I
is currently just a wrapper around the QQ[I] one.
comment:4 Changed 12 years ago by
 Cc kcrisman added
comment:5 Changed 12 years ago by
The Pynac/symbolic one is, yes. In fact, it looks a lot like the one in this patch already:
K = QuadraticField(1, 'I', embedding=CC.gen(), latex_name='i') pynac_I = K.gen()
which by the way appears to be a bug of sorts; embedding
should be True
or False
in this case, which then passes things to NumberField
, where embedding
should be the image of the generator in an ambient field. I don't know if should be considered a bug in QuadraticField
or in the Pynac implementation, though. What's actually passed to NumberField
is CLF(1).sqrt()
.
(Parenthetical: sage.rings.all says
# i = I = QuadraticField(1, 'I').gen() I = CC.gen()
So I wonder if there is any conflict between these that would need to get sorted out. Apparently it just gets overwritten during the import process when Sage starts up.)
Anyway, in sage.symbolic.pynac we have further that
I = new_Expression_from_GEx(ring.SR, g_I)
So is it possible to make I
no longer be this Pynacwrapped generator of the appropriate quadratic field, but instead stay an element of the number field 'coerced' as robertwb says when appropriate (such as with 2.*I
)?
I would be very happy to take Chris' excellent start and turn it into that, because I could definitely use it this spring in my own class. But I'd need help because I don't know how the coercion stuff works at all.
comment:6 Changed 9 years ago by
#13213 seems to be nearly ready, which I think might make dealing with these things more tractable  ?
comment:7 followup: ↓ 9 Changed 9 years ago by
Actually #13213 is not complete enough to start implementing this, we need #13256 as well !
GaussianIntegers
should definitely inherit from sage.rings.number_field.order.Order
and its elements from sage.rings.number_field.number_field_element_quadratic.OrderElement_quadratic
. By the way, the Gaussian integers is not the only integer ring which is a euclidean ring ! This is True for negative discriminants 1 (Gaussian integers), 2, 3, 7 and 11. Moreover, some of the quadratic fields with positive discriminant are also normeuclidean (see the related page on wikipedia).
comment:8 Changed 9 years ago by
 Cc vdelecroix added
comment:9 in reply to: ↑ 7 Changed 9 years ago by
Actually #13213 is not complete enough to start implementing this, we need #13256 as well !
Thanks for pointing this out.
By the way, the Gaussian integers is not the only integer ring which is a euclidean ring ! This is True for negative discriminants 1 (Gaussian integers), 2, 3, 7 and 11. Moreover, some of the quadratic fields with positive discriminant are also normeuclidean (see the related page on wikipedia).
Of course! I am thinking of these primarily for pedagogical purposes  my druthers would be to have these and the Eisenstein integers, that's as much as I'll ever use at the undergraduate level.
If you'd like to start this (as I believe you understand technical details of Sage coercion, which I do not really) by rebasing the current patch to those tickets in the way you indicate, I should have some time this summer and some motivation to help out.
comment:10 Changed 9 years ago by
 Cc katestange added
comment:11 Changed 9 years ago by
The patches discussed seem to be ready.
comment:12 followup: ↓ 18 Changed 8 years ago by
Looking at this ticket, I fail to see the need for a whole new implementation of Z[i]
. If NumberField(x^2+1, 'I').ring_of_integers()
doesn't suit you, we should fix the latter such that it does.
I do agree with just defining the name GaussianIntegers
to be a synonym of NumberField(x^2+1, 'I').ring_of_integers()
.
comment:13 followups: ↓ 14 ↓ 15 Changed 8 years ago by
I do agree with just defining the name GaussianIntegers? to be a synonym of NumberField?(x^{2+1, 'I').ring_of_integers(). }
Some stuff already works with this. However, it is definitely insufficient.
 I can't figure out how to get something prime (I can get the factorization and whether it's a unit, but that's not the same thing).
 What is this?
sage: GaussianIntegers([199,0]).quo_rem(GaussianIntegers([100,0])) (199/100, 0)
 There is no
gcd
implemented either.
So I don't think it could just be a synonym, but would it be possible to only slightly extend the class, maybe? I would be, as mentioned before, very motivated to review something like this, not sure if just adapting the current patch (well, the stuff that is missing) to just extend the current thing is possible or the way to go.
comment:14 in reply to: ↑ 13 Changed 8 years ago by
comment:15 in reply to: ↑ 13 Changed 8 years ago by
Replying to kcrisman:
 I can't figure out how to get something prime
Do you mean that you're missing an is_prime()
method?
comment:16 Changed 8 years ago by
I created #17538 for is_prime()
.
comment:17 Changed 8 years ago by
And does the Euclidean algorithm work as intended here? I would definitely say that those two tickets would be very useful.
comment:18 in reply to: ↑ 12 Changed 7 years ago by
I do agree with just defining the name
GaussianIntegers
to be a synonym ofNumberField(x^2+1, 'I').ring_of_integers()
.
Finally returning to this as I'm teaching it again... Would it be better to have it be a synonym of NumberField(x^2+1, 'I', embedding=CC.gen()).ring_of_integers()
so that one can do numerical approximation? (Or would that cause other problems?)
comment:19 followups: ↓ 20 ↓ 21 Changed 7 years ago by
Alternately, should we use QuadraticField
?
Also, what about the questions in the original post  would these nowadays be fixed by just doing the 'obvious'? I think that for pedagogical purposes at least, and hopefully general purposes, these would both be useful.
Also they are printed as a + b*i not as b*i + a.
Also the coefficients of integers are in ZZ, not in QQ as for general quadratic orders.
comment:20 in reply to: ↑ 19 Changed 7 years ago by
Replying to kcrisman:
Alternately, should we use
QuadraticField
?
The best choice would be
ZI = QuadraticField(1, 'I').ring_of_integers()
Also they are printed as a + b*i not as b*i + a.
This is an indeed an "issue". However, it certainly does not justify adding a whole new class just to print things differently. One should add some kind of option to NumberField
to _repr_()
things in a different order.
comment:21 in reply to: ↑ 19 Changed 7 years ago by
Replying to kcrisman:
Also the coefficients of integers are in ZZ, not in QQ as for general quadratic orders.
The coefficients of the ring_of_integers()
are in ZZ, so this is not a problem.
comment:22 followups: ↓ 23 ↓ 25 Changed 7 years ago by
Maybe I should clarify the original aim of this ticket and the preliminary code: It was for educational purpose. The code there was in no way optimized, but it illustrated what I taught at the time. I don't think that code should go in. Some of the comments above relate to outdated things. After all this ticket is now 5 years old.
Regardless of that. I believe we should have that the standard I
in sage is an element in the ring of integers of the QuadraticField
. It may be worth to have this particular field and its ring as a class for the following reason:
 I would really want the printing to change and I am not sure I want to fight for a change for arbitrary number fields.
 I think the global name
GaussianIntegers
could be worth having for educational purposes.  Maybe there are things from pari's
I
that one can use to increase the speed. Presumably pari'sI
is not just a wrap aroundMod(x,x^2+1)
but I don't know about this.  It is also one of two in the intersection of
CyclotomicFields
andQuadraticField
.  It could interact with the symbolic
I
and other instances of it.
In any case, this should not be more than a wrapper around optimized code in other places.
What I consider a bug is
sage: K = QuadraticField(1) sage: I in K False
comment:23 in reply to: ↑ 22 Changed 7 years ago by
Replying to wuthrich:
 I think the global name
GaussianIntegers
could be worth having for educational purposes.
I agree. That change could be done now even without this ticket.
 Maybe there are things from pari's
I
that one can use to increase the speed.
I don't think so. PARI's I
is really meant for complex numbers, not for doing number theory. PARI's I
is a very different thing than Mod(x, x^2+1)
.
comment:24 Changed 7 years ago by
I still think that GaussianIntegers
should be exactly the same as QuadraticField(1).ring_of_integers()
.
comment:25 in reply to: ↑ 22 ; followup: ↓ 26 Changed 7 years ago by
Replying to wuthrich:
I am not sure I want to fight for a change for arbitrary number fields.
Don't fight, just ask... I did just that on sagent
. Note that changing the print order will probably break a huge amounts of doctests, so it won't be fun.
comment:26 in reply to: ↑ 25 Changed 7 years ago by
Don't fight, just ask... I did just that on
sagent
. Note that changing the print order will probably break a huge amounts of doctests, so it won't be fun.
For cyclotomic fields it would make sense to change too. I guess. Thanks for asking :)
Good to know about pari's I. How do you feel about the interaction in sage with the symbolic I. As a student I would be very confused if I was not in GaussianIntegers?.
comment:27 followup: ↓ 28 Changed 7 years ago by
Just noticed now that the pun were better had I written
"As a student I would be very confused if I were not in
GaussianIntegers
."
comment:28 in reply to: ↑ 27 Changed 7 years ago by
So I think that we have a few separate issues.
 Add prime elements, not just ideals (done)
 Add gcd (ticket #17294)
 Add alias for
GaussianIntegers
(this ticket)  Worry about printing order
 Figure out how to get
I in GaussianIntegers
to work, if at all possible, or document the heck out of it if not
Can anyone think of anything else that would be needed for pedagogical purposes? I can only think of
 Plotting Gaussian integers, especially primes, like http://www.jasondavies.com/gaussianprimes/ (though I have some nice interacts of my own for this)
Just noticed now that the pun were better had I written
"As a student I would be very confused if I were not in
GaussianIntegers
."
Very nice indeed.
comment:29 Changed 7 years ago by
(Also separate ticket: Eisenstein Integers!)
comment:30 followup: ↓ 31 Changed 7 years ago by
Alias or its own class is still a question, I believe. Do we want CyclotomicField(4)
and QuadraticField(1)
to return the same thing ? We agree that in either case it should be minimal.
Why I
is a symbolic expression in sage now is a mystery to me. Surely it should be in Z[i], just like 2 is in Z. That I^2
is a symbolic expression and not an integer seems particularly inconvenient.
Eisenstein integer could be dealt with on this same ticket. We only have to decide if the generator is a 3rd or a 6th root of unity.
comment:31 in reply to: ↑ 30 Changed 7 years ago by
Replying to wuthrich:
Why
I
is a symbolic expression in sage now is a mystery to me. Surely it should be in Z[i], just like 2 is in Z. ThatI^2
is a symbolic expression and not an integer seems particularly inconvenient.
Agreed: this is very annoying. And actually, defining I
as the generator of ZZ[I]
might work out of the box
sage: good_I = QuadraticField(1,'I').gen() sage: (good_I + 1.0).parent() Complex Field with 53 bits of precision sage: (good_I + 1/2).parent() Number Field in I with defining polynomial x^2 + 1 sage: good_I == I # not perfect I == I sage: bool(good_I == I) # but not that bad True
comment:32 followup: ↓ 33 Changed 7 years ago by
Please open a different ticket for the issue of I
.
comment:33 in reply to: ↑ 32 Changed 7 years ago by
comment:34 Changed 7 years ago by
 Dependencies set to #15348
 Description modified (diff)
 Milestone changed from sagewishlist to sage7.0
 Summary changed from Gaussian Integers to Gaussian and Eisenstein integers
comment:35 Changed 7 years ago by
 Branch set to u/jdemeyer/gaussian_integers
comment:36 Changed 7 years ago by
 Commit set to c81e460f4e6a52da209b37c5effcd8ca88ca1cf8
 Status changed from needs_info to needs_review
comment:37 Changed 7 years ago by
 Commit changed from c81e460f4e6a52da209b37c5effcd8ca88ca1cf8 to d4bab146a23b9696ca10f4a73a743b7fe99c6f0f
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
d4bab14  Add Gaussian and Eisenstein integers

comment:38 Changed 7 years ago by
 Dependencies #15348 deleted
comment:39 Changed 7 years ago by
 Milestone changed from sage7.0 to sage7.1
 Status changed from needs_review to needs_work
comment:40 Changed 7 years ago by
 Commit changed from d4bab146a23b9696ca10f4a73a743b7fe99c6f0f to daee4f27848d4de6c4a3f49b3c11f7e0af0e95cd
Branch pushed to git repo; I updated commit sha1. New commits:
daee4f2  Merge tag '7.1.beta0' into t/7545/gaussian_integers

comment:41 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:42 Changed 6 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, looks good to me.
comment:43 Changed 6 years ago by
 Reviewers changed from Frédéric Chapoton to Frédéric Chapoton, Vincent Delecroix, Kate Stange, KarlDieter Crisman
Thank you!!!
comment:44 Changed 6 years ago by
 Branch changed from u/jdemeyer/gaussian_integers to daee4f27848d4de6c4a3f49b3c11f7e0af0e95cd
 Resolution set to fixed
 Status changed from positive_review to closed
comment:45 Changed 6 years ago by
 Commit daee4f27848d4de6c4a3f49b3c11f7e0af0e95cd deleted
 Reviewers changed from Frédéric Chapoton, Vincent Delecroix, Kate Stange, KarlDieter Crisman to Frédéric Chapoton, Vincent Delecroix, Katherine Stange, KarlDieter Crisman
patch exported in 4.3.alpha0.