Opened 5 years ago

Closed 5 years ago

#17317 closed enhancement (fixed)

Add unit_group() method to IntegerModRing

Reported by: pbruin Owned by:
Priority: major Milestone: sage-6.4
Component: number theory Keywords: unit group
Cc: rbeezer, fwclarke, kcrisman, wuthrich, jpflori Merged in:
Authors: Peter Bruin Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: a861303 (Commits) Commit: a8613031ce7f122a91d2ca6257ee50d7bebc3f32
Dependencies: #17315 Stopgaps:

Description (last modified by pbruin)

This ticket implements a unit_group() method for Z/nZ. Example:

sage: A = Zmod(24)
sage: G = A.unit_group(); G
Multiplicative Abelian group isomorphic to C2 x C2 x C2
sage: G.gens_orders()
(2, 2, 2)
sage: G.gens_values()
(7, 13, 17)

At the moment, there is no new class for such groups; it uses AbelianGroupWithValues. However, this could easily be changed in the future if required.

The unit_group() method admits an optional algorithm argument (default: 'sage'). This can be set to 'pari' to use PARI's znstar() function (see #17315). This gives different generators in general.

See also:

Change History (17)

comment:1 Changed 5 years ago by pbruin

  • Branch set to u/pbruin/17317-IntegerModRing_unit_group
  • Commit set to 7f38953bdbc38709a218533934d759abc5325f76
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by wuthrich

  • Cc wuthrich added

comment:3 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

First impressions:

  1. I find the examples in the doctest all rather simple. It doesn't really show how different the algorithm="sage" and algorithm="pari" can be. I would add Zmod(319) as example. Also a larger example, say Zmod(lcm([1..40])) or so...
  1. I would add a **kwds argument to unit_gens():
    def unit_gens(self, **kwds):
        return self.unit_group(**kwds).gens_values()
    
  1. And a nitpick: I prefer to see repr(algorithm) in the error message, something like:
    raise ValueError('unknown algorithm %r for computing the unit group' % algorithm)
    

This error should also be doctested in a TESTS:: block.

Last edited 5 years ago by jdemeyer (previous) (diff)

comment:4 Changed 5 years ago by jdemeyer

I would also add doctests for the special cases Zmod(1) and Zmod(2)

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

If possible, I would like to see the changes to the Dirichlet character stuff in a different ticket (to make reviewing easier).

comment:6 Changed 5 years ago by jdemeyer

Why not

from sage.rings.arith import primitive_root

def _unit_gens_primecase(p):
    return primitive_root(p, check=False)

def _unit_gens_primepowercase(p, r):
    return primitive_root(p**r, check=False)
Last edited 5 years ago by jdemeyer (previous) (diff)

comment:7 follow-up: Changed 5 years ago by fwclarke

For number fields, we have

sage: QuadraticField(5).unit_group(5)
Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 5
sage: QuadraticField(5).unit_group(5).number_field()
Number Field in a with defining polynomial x^2 - 5

But in the current case:

sage: Zmod(1000).unit_group()
Multiplicative Abelian group isomorphic to C2 x C2 x C100

Though we can see which ring we're working with via

sage: Zmod(1000).unit_group().values_group()
Ring of integers modulo 1000

this terminology is very non-intuitive. I think it would be worth having a class for these groups, with a ring method and a more complete _repr_.

comment:8 Changed 5 years ago by pbruin

  • Description modified (diff)

comment:9 Changed 5 years ago by git

  • Commit changed from 7f38953bdbc38709a218533934d759abc5325f76 to a6e38c686b028bbbbd112fdeb569e09dd932e2a5

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

3597314Trac 17317: revert some of the changes in the previous commit
758798eTrac 17317: rewrite _unit_gens_primepowercase() using primitive_root()
7f45af0Trac 17317: slightly change error message and add doctests
a6e38c6Trac 17317: temporary special case n = 1 to avoid having to fix many doctests

comment:10 Changed 5 years ago by git

  • Commit changed from a6e38c686b028bbbbd112fdeb569e09dd932e2a5 to 7e046ddd5ddf66209daf7dd4755e76e4dbbedf56

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

7e046ddTrac 17317: add optional keywords to unit_gens() and update related documentation

comment:11 in reply to: ↑ 5 ; follow-up: Changed 5 years ago by pbruin

  • Status changed from needs_work to needs_review

Replying to jdemeyer:

If possible, I would like to see the changes to the Dirichlet character stuff in a different ticket (to make reviewing easier).

See #17337 and #17338.

I think the new commits address your other comments, back to needs_review.

comment:12 in reply to: ↑ 7 Changed 5 years ago by pbruin

Replying to fwclarke:

For number fields, we have

sage: QuadraticField(5).unit_group(5)
Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 5
sage: QuadraticField(5).unit_group(5).number_field()
Number Field in a with defining polynomial x^2 - 5

But in the current case:

sage: Zmod(1000).unit_group()
Multiplicative Abelian group isomorphic to C2 x C2 x C100

Though we can see which ring we're working with via

sage: Zmod(1000).unit_group().values_group()
Ring of integers modulo 1000

this terminology is very non-intuitive. I think it would be worth having a class for these groups, with a ring method and a more complete _repr_.

I agree, but this should probably be done on a different ticket. I think it won't cause problems if we change the precise type of group output by unit_group() in the future. (Maybe we could just make it a subclass of AbelianGroupWithValues.)

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

  • Reviewers set to Jeroen Demeyer

Replying to pbruin:

I think the new commits address your other comments, back to needs_review.

From a quick look through the diffs, this is indeed the case. I'll make a deeper review later.

comment:14 Changed 5 years ago by jpflori

  • Cc jpflori added

comment:15 Changed 5 years ago by jdemeyer

  • Branch changed from u/pbruin/17317-IntegerModRing_unit_group to u/jdemeyer/ticket/17317
  • Created changed from 11/12/14 00:16:58 to 11/12/14 00:16:58
  • Modified changed from 11/17/14 09:32:58 to 11/17/14 09:32:58

comment:16 Changed 5 years ago by jdemeyer

  • Commit changed from 7e046ddd5ddf66209daf7dd4755e76e4dbbedf56 to a8613031ce7f122a91d2ca6257ee50d7bebc3f32
  • Status changed from needs_review to positive_review

I added a trivial patch, looks good!


New commits:

a861303Trac 17317: Factor out computation of p**r

comment:17 Changed 5 years ago by vbraun

  • Branch changed from u/jdemeyer/ticket/17317 to a8613031ce7f122a91d2ca6257ee50d7bebc3f32
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.