Opened 10 years ago

Closed 4 years ago

Last modified 4 years ago

#7545 closed enhancement (fixed)

Gaussian and Eisenstein integers

Reported by: wuthrich Owned by: davidloeffler
Priority: minor Milestone: sage-7.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, Karl-Dieter Crisman
Report Upstream: N/A Work issues:
Branch: daee4f2 (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

Define GaussianIntegers() and EisensteinIntegers() as orders in the appropriate number field.

Attachments (1)

trac_7545_zi.patch (16.3 KB) - added by wuthrich 10 years ago.
patch exported in 4.3.alpha0.

Download all attachments as: .zip

Change History (46)

Changed 10 years ago by wuthrich

patch exported in 4.3.alpha0.

comment:1 Changed 10 years ago by wuthrich

  • 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 10 years ago by robertwb

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 10 years ago by mhansen

The default I is currently just a wrapper around the QQ[I] one.

comment:4 Changed 9 years ago by kcrisman

  • Cc kcrisman added

comment:5 Changed 9 years ago by kcrisman

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 Pynac-wrapped 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 7 years ago by kcrisman

#13213 seems to be nearly ready, which I think might make dealing with these things more tractable - ?

comment:7 follow-up: Changed 7 years ago by vdelecroix

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 norm-euclidean (see the related page on wikipedia).

comment:8 Changed 7 years ago by vdelecroix

  • Cc vdelecroix added

comment:9 in reply to: ↑ 7 Changed 7 years ago by kcrisman

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 norm-euclidean (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 6 years ago by katestange

  • Cc katestange added

comment:11 Changed 6 years ago by katestange

The patches discussed seem to be ready.

comment:12 follow-up: Changed 5 years ago by jdemeyer

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 follow-ups: Changed 5 years ago by kcrisman

I do agree with just defining the name GaussianIntegers? to be a synonym of NumberField?(x2+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 5 years ago by jdemeyer

Replying to kcrisman:

  • There is no gcd implemented either.

There is if somebody reviews #17294.

comment:15 in reply to: ↑ 13 Changed 5 years ago by jdemeyer

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 5 years ago by jdemeyer

I created #17538 for is_prime().

comment:17 Changed 5 years ago by kcrisman

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 5 years ago by kcrisman

I do agree with just defining the name GaussianIntegers to be a synonym of NumberField(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 follow-ups: Changed 5 years ago by kcrisman

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 5 years ago by jdemeyer

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 5 years ago by jdemeyer

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 follow-ups: Changed 5 years ago by wuthrich

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's I is not just a wrap around Mod(x,x^2+1) but I don't know about this.
  • It is also one of two in the intersection of CyclotomicFields and QuadraticField.
  • 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 5 years ago by jdemeyer

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 5 years ago by jdemeyer

I still think that GaussianIntegers should be exactly the same as QuadraticField(-1).ring_of_integers().

comment:25 in reply to: ↑ 22 ; follow-up: Changed 5 years ago by jdemeyer

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 sage-nt. 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 5 years ago by wuthrich

Don't fight, just ask... I did just that on sage-nt. 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 follow-up: Changed 5 years ago by wuthrich

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 5 years ago by kcrisman

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

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 5 years ago by kcrisman

(Also separate ticket: Eisenstein Integers!)

comment:30 follow-up: Changed 5 years ago by wuthrich

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 5 years ago by vdelecroix

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. That I^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 follow-up: Changed 5 years ago by jdemeyer

Please open a different ticket for the issue of I.

comment:33 in reply to: ↑ 32 Changed 5 years ago by vdelecroix

Replying to jdemeyer:

Please open a different ticket for the issue of I.

#18036

comment:34 Changed 4 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Dependencies set to #15348
  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-7.0
  • Summary changed from Gaussian Integers to Gaussian and Eisenstein integers

comment:35 Changed 4 years ago by jdemeyer

  • Branch set to u/jdemeyer/gaussian_integers

comment:36 Changed 4 years ago by jdemeyer

  • Commit set to c81e460f4e6a52da209b37c5effcd8ca88ca1cf8
  • Status changed from needs_info to needs_review

New commits:

dac0a4cLet "R.<x> =" syntax use ring_generators if possible
c81e460Add Gaussian and Eisenstein integers

comment:37 Changed 4 years ago by git

  • Commit changed from c81e460f4e6a52da209b37c5effcd8ca88ca1cf8 to d4bab146a23b9696ca10f4a73a743b7fe99c6f0f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d4bab14Add Gaussian and Eisenstein integers

comment:38 Changed 4 years ago by jdemeyer

  • Dependencies #15348 deleted

comment:39 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-7.0 to sage-7.1
  • Status changed from needs_review to needs_work

comment:40 Changed 4 years ago by git

  • Commit changed from d4bab146a23b9696ca10f4a73a743b7fe99c6f0f to daee4f27848d4de6c4a3f49b3c11f7e0af0e95cd

Branch pushed to git repo; I updated commit sha1. New commits:

daee4f2Merge tag '7.1.beta0' into t/7545/gaussian_integers

comment:41 Changed 4 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:42 Changed 4 years ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, looks good to me.

comment:43 Changed 4 years ago by kcrisman

  • Reviewers changed from Frédéric Chapoton to Frédéric Chapoton, Vincent Delecroix, Kate Stange, Karl-Dieter Crisman

Thank you!!!

comment:44 Changed 4 years ago by vbraun

  • Branch changed from u/jdemeyer/gaussian_integers to daee4f27848d4de6c4a3f49b3c11f7e0af0e95cd
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:45 Changed 4 years ago by jdemeyer

  • Commit daee4f27848d4de6c4a3f49b3c11f7e0af0e95cd deleted
  • Reviewers changed from Frédéric Chapoton, Vincent Delecroix, Kate Stange, Karl-Dieter Crisman to Frédéric Chapoton, Vincent Delecroix, Katherine Stange, Karl-Dieter Crisman
Note: See TracTickets for help on using tickets.