Category for IntegerModRing(n)

41 views
Skip to first unread message

Nicolas M. Thiery

unread,
Mar 20, 2010, 11:07:12 AM3/20/10
to sage-...@googlegroups.com
Hi!

In order to let Rob use IntegerModRing(n) as example of finite
additive group for his cool Cayley graph feature (#7555), I just wrote
a patch (#8562) letting IntegerModRing(n) use the category
framework. That was essentially a one liner, plus minor updates here
and there, and all test pass.

There is just a single issue for which I would like feedback.
Namely, what shall be the result of:

sage: IntegerModRing(5).category()

It used to be "CommutativeRings()", which feels a bit disappointing.
So the current patch whether n is prime, and if yes sets the category
to Fields(). This sounds natural, but there is one drawback: the
category needs to be set at construction time, and the primality test
can possibly be costly. And indeed, the Sage tests contain one use
case where this is not acceptable (sage/tests/book_stein_ent.py, l.122):

sage: def is_prime_lucas_lehmer(p):
... s = Mod(4, 2^p - 1)
... for i in range(3, p+1):
... s = s^2 - 2
... return s == 0
sage: # Check primality of 2^9941 - 1
sage: is_prime_lucas_lehmer(9941)
True

The Mod call constructs IntegerModRing(2^9941) and the primality test
triggers a timeout or pari overflow.

What strategy would you recommend?

(1) We don't care about the usecase above (hmm)

(2) IntegerModRing(n) is always in CommutativeRings()

(3) Same thing, unless the user specifies the category:

IntegerModRing(5, Fields())

Although in that case, he might as well call GF(5).

(4) IntegerModRing(n) always do a primality test, unless the user
specifies himself the category.

(5) When n is not too big, IntegerModRing(n) checks the primality of
n, and sets the category accordingly. Otherwise it always uses
CommutativeRings().

(6) When n is not too big, IntegerModRing(n) checks the primality of
n, and returns GF(n) or a plain IntegerModRing(n) accordingly.

(7) Something else?

I vote for (6), but only with a very light preference.

Thanks!
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

Florent Hivert

unread,
Mar 20, 2010, 11:35:01 AM3/20/10
to sage-...@googlegroups.com
Hi There,

> In order to let Rob use IntegerModRing(n) as example of finite
> additive group for his cool Cayley graph feature (#7555), I just wrote
> a patch (#8562) letting IntegerModRing(n) use the category
> framework. That was essentially a one liner, plus minor updates here
> and there, and all test pass.

[...]


> The Mod call constructs IntegerModRing(2^9941) and the primality test
> triggers a timeout or pari overflow.
>
> What strategy would you recommend?
>
> (1) We don't care about the usecase above (hmm)
>
> (2) IntegerModRing(n) is always in CommutativeRings()
>
> (3) Same thing, unless the user specifies the category:
>
> IntegerModRing(5, Fields())

You probably mean
IntegerModRing(5, category=Fields())
which is consitent with was we do in sevaral other places.

> Although in that case, he might as well call GF(5).
>
> (4) IntegerModRing(n) always do a primality test, unless the user
> specifies himself the category.
>
> (5) When n is not too big, IntegerModRing(n) checks the primality of
> n, and sets the category accordingly. Otherwise it always uses
> CommutativeRings().
>
> (6) When n is not too big, IntegerModRing(n) checks the primality of
> n, and returns GF(n) or a plain IntegerModRing(n) accordingly.

What about:

(6') if the user specifies a category with
IntegerModRing(5, category=Fields())
then trust him and do no check otherwise (6). But maybe it is what you meant.

Cheers,

Florent

John Cremona

unread,
Mar 20, 2010, 11:50:43 AM3/20/10
to sage-...@googlegroups.com
I would say that you should never test for primality unless
specifically required, e.g. if the user asks is_field() (after which
the category could be upgraded? I don't know if that is possible).

I would always use GF(p) rather than IntegerMod(p) for when I know p
is prime. it is is vital in teaching primality tests and the like
that one can form IntegerModRing(n) without knowing (or automatically
testing behind the scenes) whether or not n is prime.

There are surely many other similar situations, for example when
constructing a commutative ring it might be expensive to determine
whether or not it is an Integral Domain.

John

PS This would be a suitable discussion for the newly-formed sage-algebra list!

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
> To unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words "REMOVE ME" as the subject.
>

Rob Beezer

unread,
Mar 20, 2010, 11:52:54 AM3/20/10
to sage-devel
On Mar 20, 8:07 am, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
> Cayley graph feature (#7555)

Cayley TABLES (and other "operation tables"). Cayley GRAPHS are due
to Moretti/Miller/Thiery. ;-)

> That was essentially a one liner

I can testify to that. If you haven't been following the Categories
work, now might be the time to tune in. Highly recommended.

> What strategy would you recommend?

None of this matters to my work on #7555, just my 2 cents worth while
I'm here. I'm negative on (2) (always CommutativeRing). I'd love to
see the field structure exploited when available. Whether or not an
integer-ring or a GF comes back is less of an issue for me.

I'm also not wild about the "not too big" part of (6) and (7). I'd
rather not see behavior change based on some (arbitrary) cut-off.
Implementation based on cut-offs is great (such as for finite fields),
so long as the interface maintains some consistency. I'm sure there
are counterexamples in Sage, and maybe this has been hashed out before
- I don't know what the consensus/history is.

I'd like an approach where there is always a primality check unless a
second argument, say a category, is present

IntegerModRing( n, CommutativeRings()|Fields() )

So the default is a primality check, but the power user can turn it
off by indicating they know what they want, and what they will get.
With the usual stern warnings in the documentation about specifying a
composite order as a Field and then all h*ll will break loose.

I recall something similar (and more subtle) in some work with
Sebastian Pancratz [1]. IIRC, there were rings that were sometimes
know to be integral domains, or not. I suspect this will come up over
and over again as the categories get fleshed out. So this relatively
straightforward/simple case might be a good place to set precedent.

Thanks to Nicolas (and others) for their work on this.

Rob

[1] http://groups.google.com/group/sage-devel/browse_thread/thread/dc104b7cb64d39e3/

Nick Alexander

unread,
Mar 20, 2010, 1:07:58 PM3/20/10
to sage-...@googlegroups.com

On 20-Mar-10, at 8:50 AM, John Cremona wrote:

> I would say that you should never test for primality unless
> specifically required, e.g. if the user asks is_field() (after which
> the category could be upgraded? I don't know if that is possible).
>
> I would always use GF(p) rather than IntegerMod(p) for when I know p
> is prime. it is is vital in teaching primality tests and the like
> that one can form IntegerModRing(n) without knowing (or automatically
> testing behind the scenes) whether or not n is prime.
>
> There are surely many other similar situations, for example when
> constructing a commutative ring it might be expensive to determine
> whether or not it is an Integral Domain.

+1, I agree with John: no primality testing unless I ask for it, and
even then I would like to be able to specify the category and override
it.

Nick

Rob Beezer

unread,
Mar 20, 2010, 1:38:15 PM3/20/10
to sage-devel
I wonder if the category infrastructure would support a pervasive
command like

R=IntegerModRing(7)
R.promote(Fields(), with_check=True)
R.category()
Category of fields

with the construction doing no extra work, and the promote method
having defaults and exceptions consistent with John and Nick's
"explicit is better" philosophy?

I had though about is_field doing the upgrade, but I think these sort
of side-effects are confusing.

Rob

Florent Hivert

unread,
Mar 20, 2010, 1:55:00 PM3/20/10
to sage-...@googlegroups.com
Hi Rob,

On Sat, Mar 20, 2010 at 10:38:15AM -0700, Rob Beezer wrote:
> I wonder if the category infrastructure would support a pervasive
> command like
>
> R=IntegerModRing(7)
> R.promote(Fields(), with_check=True)
> R.category()
> Category of fields
>
> with the construction doing no extra work, and the promote method
> having defaults and exceptions consistent with John and Nick's
> "explicit is better" philosophy?
>
> I had though about is_field doing the upgrade, but I think these sort
> of side-effects are confusing.

I already discussed about such thing with Nicolas, but as far as I remember
this could be a hard thing to do. Indeed, doing this you not only need to
upgrade the class of R but also of any of its elements in the
memory. Otherwise, older elements won't get new methods which are provided by
the Field() category (eg: division)... I don't think you can achieve
something robust with coercion...

The only solution I can think about (we is even much more hazardeous), is not
only to accept classes which are bynamically created in python, but also to
have classes which are dynamically *modified*. You have to change the mro() of
a class. I'm not sure that we really want it...

Nicolas: can you confirm this ?

Cheers,

Florent

Robert Bradshaw

unread,
Mar 20, 2010, 2:04:34 PM3/20/10
to sage-...@googlegroups.com
On Mar 20, 2010, at 10:38 AM, Rob Beezer wrote:

> I wonder if the category infrastructure would support a pervasive
> command like
>
> R=IntegerModRing(7)
> R.promote(Fields(), with_check=True)
> R.category()
> Category of fields
>
> with the construction doing no extra work, and the promote method
> having defaults and exceptions consistent with John and Nick's
> "explicit is better" philosophy?
>
> I had though about is_field doing the upgrade, but I think these sort
> of side-effects are confusing.

Side effects are confusing in general, especially with cached parents.
I would rather have a change_category method that returns a new object
with the updated category, like

sage: R=IntegerModRing(7)
sage: R.change_category(Fields()).is_field()
True

For the record, I'm also -1 to automatic primality checking
(especially inconsistently depending on n), but like the idea of being
able to specify a category.

- Robert


> On Mar 20, 10:07 am, Nick Alexander <ncalexan...@gmail.com> wrote:
>> On 20-Mar-10, at 8:50 AM, John Cremona wrote:
>>
>>> I would say that you should never test for primality unless
>>> specifically required, e.g. if the user asks is_field() (after which
>>> the category could be upgraded? I don't know if that is possible).
>>
>>> I would always use GF(p) rather than IntegerMod(p) for when I know p
>>> is prime. it is is vital in teaching primality tests and the like
>>> that one can form IntegerModRing(n) without knowing (or
>>> automatically
>>> testing behind the scenes) whether or not n is prime.
>>
>>> There are surely many other similar situations, for example when
>>> constructing a commutative ring it might be expensive to determine
>>> whether or not it is an Integral Domain.
>>
>> +1, I agree with John: no primality testing unless I ask for it, and
>> even then I would like to be able to specify the category and
>> override
>> it.
>>
>> Nick
>

Rob Beezer

unread,
Mar 20, 2010, 2:08:56 PM3/20/10
to sage-devel
Thanks, Florent. That's what I suspected, given my nascent
understanding of how categories work.

So an irrevocable decision needs to be made at construction time, it
would seem.

Rob

On Mar 20, 10:55 am, Florent Hivert <florent.hiv...@univ-rouen.fr>
wrote:

Florent Hivert

unread,
Mar 20, 2010, 2:22:33 PM3/20/10
to sage-...@googlegroups.com
Hi Robert,

>> I wonder if the category infrastructure would support a pervasive
>> command like
>>
>> R=IntegerModRing(7)
>> R.promote(Fields(), with_check=True)
>> R.category()
>> Category of fields
>>
>> with the construction doing no extra work, and the promote method
>> having defaults and exceptions consistent with John and Nick's
>> "explicit is better" philosophy?
>>
>> I had though about is_field doing the upgrade, but I think these sort
>> of side-effects are confusing.
>
> Side effects are confusing in general, especially with cached parents. I
> would rather have a change_category method that returns a new object with
> the updated category, like
>
> sage: R=IntegerModRing(7)
> sage: R.change_category(Fields()).is_field()
> True

This is perfectly doable, except that, all the element created before will
still be ring element. More precisely if you write:
> sage: R = IntegerModRing(7)
> sage: R1 = change_category(Fields())
then you have a brand new parent with no connection to the former one. You can
set up a coercion R -> R1 but this is very likely to leads to very unexpected
behavior.

Cheers,

Florent

Alec Mihailovs

unread,
Mar 20, 2010, 3:40:36 PM3/20/10
to sage-devel
From the user point of view, without reading the documentation, I
would expect IntegerModRing(n) be a ring, IntegerModField(p) be a
field, and Integer ModAbelianGroup(n) be an Abelian group.

So I would go with option (2).

It would be rather confusing to define something that you think is a
ring, and then find out that it is a field.

The situation would be different for IntegerMod(n), in which case the
category can be specified using a keyword category, which could be
CommutativeRings by default, but may be changed as category=Fields, as
in option 3, or category=AbelianGroups, if desirable.

Alec Mihailovs

Robert Bradshaw

unread,
Mar 20, 2010, 4:48:01 PM3/20/10
to sage-...@googlegroups.com

I was imagining this would be set up automatically.

> but this is very likely to leads to very unexpected behavior.

Like?

- Robert

Nicolas M. Thiery

unread,
Mar 21, 2010, 3:12:11 AM3/21/10
to sage-...@googlegroups.com
On Sat, Mar 20, 2010 at 04:35:01PM +0100, Florent hivert wrote:
> Hi There,
>
> > In order to let Rob use IntegerModRing(n) as example of finite
> > additive group for his cool Cayley graph feature (#7555), I just wrote
> > a patch (#8562) letting IntegerModRing(n) use the category
> > framework. That was essentially a one liner, plus minor updates here
> > and there, and all test pass.
>
> [...]
>
>
> > The Mod call constructs IntegerModRing(2^9941) and the primality test
> > triggers a timeout or pari overflow.
> >
> > What strategy would you recommend?
> >
> > (1) We don't care about the usecase above (hmm)
> >
> > (2) IntegerModRing(n) is always in CommutativeRings()
> >
> > (3) Same thing, unless the user specifies the category:
> >
> > IntegerModRing(5, Fields())
>
> You probably mean
> IntegerModRing(5, category=Fields())
> which is consitent with was we do in sevaral other places.

Yes.

> > Although in that case, he might as well call GF(5).
> >
> > (4) IntegerModRing(n) always do a primality test, unless the user
> > specifies himself the category.
> >
> > (5) When n is not too big, IntegerModRing(n) checks the primality of
> > n, and sets the category accordingly. Otherwise it always uses
> > CommutativeRings().
> >
> > (6) When n is not too big, IntegerModRing(n) checks the primality of
> > n, and returns GF(n) or a plain IntegerModRing(n) accordingly.
>
> What about:
>
> (6') if the user specifies a category with
> IntegerModRing(5, category=Fields())
> then trust him and do no check otherwise (6). But maybe it is what you meant.

That would be a 5', but yes indeed.

Cheers,

Gonzalo Tornaria

unread,
Mar 21, 2010, 3:25:18 AM3/21/10
to sage-...@googlegroups.com
On Sat, Mar 20, 2010 at 11:52 AM, Rob Beezer <goo...@beezer.cotse.net> wrote:
>> (2) IntegerModRing(n) is always in CommutativeRings()

IMO this is the one that makes sense, by the same reasons why:

sage: parent(2/1)
Rational Field

IOW, IntegerModRing should be a map from ZZ to CommutativeRings()

This is the only "natural" definition, as the only possible "generic"
property you know about IntegerModRing(n) is that it is commutative.

This seems to lead to IntegerModRing(0) returning a ZZ in category
CommutativeRings(). I don't know if that's right or even possible.

You would have the same issue for R.quotient(I) where R is a ring and
I is an R-ideal... You wouldn't want having to check properties of I
and make inconsistent definitions for different R, etc.


>> (3) Same thing, unless the user specifies the category:
>>
>>     IntegerModRing(5, Fields())
>>
>>     Although in that case, he might as well call GF(5).

I think it's ok to add a category=other argument, again for
consistency with the case:

R.quotient(I, category=blah)

where you may not have an alternate notation as the GF(p) one.


>>
>> (4) IntegerModRing(n) always do a primality test, unless the user
>>     specifies himself the category.

No way as already explained by others in this thread.

>> (5) When n is not too big, IntegerModRing(n) checks the primality of
>>     n, and sets the category accordingly. Otherwise it always uses
>>     CommutativeRings().
>>
>> (6) When n is not too big, IntegerModRing(n) checks the primality of
>>     n, and returns GF(n) or a plain IntegerModRing(n) accordingly.

Making things depend on "when n is not too big" is as far away as I
can possibly imagine from a "categorical approach" :-)

Gonzalo

Nicolas M. Thiery

unread,
Mar 21, 2010, 3:30:48 AM3/21/10
to sage-...@googlegroups.com
On Sat, Mar 20, 2010 at 03:50:43PM +0000, John Cremona wrote:
> There are surely many other similar situations, for example when
> constructing a commutative ring it might be expensive to determine
> whether or not it is an Integral Domain.

Yup.

> I would always use GF(p) rather than IntegerMod(p) for when I know p
> is prime. it is is vital in teaching primality tests and the like
> that one can form IntegerModRing(n) without knowing (or automatically
> testing behind the scenes) whether or not n is prime.

Here is a typical situation where this feature could be desirable:

Imagine that, in some deep construction, you construct internally a
Z/nZ, without knowing in advance whether n is prime or not; then later
on, you build some module M over it, and do some intensive linear
algebra over it. Then you would want the linear algebra to
automatically make use of the fact that M is a vector space for faster
calculations.

The first option is for the caller to do the primality test himself;
but I find this a bit invasive (I need to know something about Z/nZ to
do this); there might be similar situations where the test to be used
could be less trivial.

Another option is something like:

IntegerModRing(n, category="best_possible")

Alternatively, since it was pointed out that, given the name, it could
be surprising for IntegerModRing to return a field (unless asked for
explicitly), an option would be to leave IntegerModRing as is, and on
the other hand, to have the current:

Integers(5)

return GF(5) automatically.

(which exploits the optimized Givaro implementation)

Best,

Nicolas M. Thiery

unread,
Mar 21, 2010, 3:40:35 AM3/21/10
to sage-...@googlegroups.com
On Sat, Mar 20, 2010 at 03:50:43PM +0000, John Cremona wrote:
> PS This would be a suitable discussion for the newly-formed sage-algebra list!

Oops, right!

Speaking of that: the primary purpose of sage-algebra is to allow
people to follow algebra related discussions without having to follow
all of sage-devel; it is not to reduce traffic on sage-devel, right?

Therefore, shouldn't all mail to sage-algebra be automatically
forwarded to sage-devel? Then, other sage developers could still keep
an eye on what's going on. And for those that could be bothered, it is
easy to setup a filter since the subject will always contain
"Sage-algebra".

At least, that could be a good intermediate measure, until most people
have registered to sage-algebra.

The same question applies to sage-combinat-devel; there has been
people on sage-devel regretting not to be aware of some discussions
going on there. And I find myself very often CC'ing to both lists.

Cheers,

Nicolas M. Thiery

unread,
Mar 21, 2010, 4:22:04 AM3/21/10
to sage-...@googlegroups.com
On Sat, Mar 20, 2010 at 08:52:54AM -0700, Rob Beezer wrote:
> On Mar 20, 8:07�am, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
> wrote:
> > Cayley graph feature (#7555)
>
> Cayley TABLES (and other "operation tables"). Cayley GRAPHS are due
> to Moretti/Miller/Thiery. ;-)

Oops :-)

> I can testify to that. If you haven't been following the Categories
> work, now might be the time to tune in. Highly recommended.

Thanks for your testimony :-)

It is my impression that people around got a bit scared of
categories. And I can't blame them after all the technical discussions
that went in about the *implementation* of categories. But using them
is (supposed to) be easy. Recall the main entry point:

sage: sage.categories?

Thanks you (and all others!) for your feedback,

Cheers,

Nicolas M. Thiery

unread,
Mar 22, 2010, 6:06:46 PM3/22/10
to sage-...@googlegroups.com
Hi!

By lack of decision for the moment, I postponed the change to a later
ticket, I just uploaded on trac a minimal version of my patch which
just lets IntegerModRing use its categories, without upgrading its
category to Fields(): see

http://trac.sagemath.org/sage_trac/ticket/8562

which needs review.

Cheers,

Reply all
Reply to author
Forward
0 new messages