Opened 3 months ago

Closed 3 months ago

#16718 closed enhancement (fixed)

Create a category for Cartesian products of groups

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-6.3
Component: group theory Keywords: cartesian product, generators, categories
Cc: ncohen, nthiery Merged in:
Authors: Travis Scrimshaw Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 8db0f51 (Commits) Commit: 8db0f5138914ddd7a9da9e2a57d26c8f45091c93
Dependencies: Stopgaps:

Description

We can define generators of a Cartesian (direct) product of groups as a Cartesian product of the generators with the identity elements. This will fix the issue noted in https://groups.google.com/forum/#!topic/sage-devel/nlRGZpr_Je8.

sage: AG=cartesian_product([CyclicPermutationGroup(5),CyclicPermutationGroup(4),CyclicPermutationGroup(4)])
sage: AG.group_generators()
...
AttributeError: 'CartesianProduct_with_category' object has no attribute 'gens'
sage: AG.j_classes()
...
AttributeError: 'CartesianProduct_with_category' object has no attribute 'gens'

We will do so by defining a general method in the appropriate category.

Change History (18)

comment:1 Changed 3 months ago by tscrim

  • Branch set to public/groups/cartesian_product_category-16718
  • Commit set to 6664adb7da87177ef6ae877c10dcf0a49fece50e
  • Status changed from new to needs_review

This also works for infinitely generated groups, but it's a hack and is work very well. I've also copied this over to monoids as well. A note for the future, these functions should be split if we implement an axiom FinitelyGenerated.


New commits:

95ebfa2Added a CartesianProduct category for groups.
a96ee13Changes and copied over to monoids as well.
9e91a51Added a TODO message.
6664adbFixed doctests in groups.py.

comment:2 Changed 3 months ago by ncohen

Helloooooooooooooooooo !!

Why do you need to implement the same function twice ? Isn't there a way to say that group_generators = monoid_generators ?

Nathann

comment:3 Changed 3 months ago by ncohen

  • Status changed from needs_review to needs_info

comment:4 follow-up: Changed 3 months ago by tscrim

  • Status changed from needs_info to needs_review

It's better to have two separate functions because the number of generators as group is often smaller the number of generators as a monoid (usually by a factor of 2 since the inverses need to be included as generators of the monoid for torsion free generators) -- albeit Sage currently does not make a distinction, nor has the functionality I believe. Plus group_generators currently does not call monoid_generators and not all groups have a monoid_generators method.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 3 months ago by ncohen

Hello !

It's better to have two separate functions because the number of generators as group is often smaller the number of generators as a monoid (usually by a factor of 2 since the inverses need to be included as generators of the monoid for torsion free generators) -- albeit Sage currently does not make a distinction, nor has the functionality I believe.

The code that only exists in your head again ....

Plus group_generators currently does not call monoid_generators and not all groups have a monoid_generators method.

Why don't all groups have a monoid_generators method ? They are monoids, aren't they ?

Nathann

comment:6 in reply to: ↑ 5 Changed 3 months ago by tscrim

Replying to ncohen:

The code that only exists in your head again ....

There's thousands of lines by hundreds of people. :p

Plus group_generators currently does not call monoid_generators and not all groups have a monoid_generators method.

Why don't all groups have a monoid_generators method ? They are monoids, aren't they ?

Yes, but as I stated above, there are often more generators as a monoid than as a group. For example, take ZZ under addition, there is 1 generator as a group (+1) but 2 generators as a monoid (+/-1). However for Cn (cyclic group), the generators as a group and as a monoid are the same. I guess we could define the monoid generators as the group generators and their inverses as a general method for general groups and for finite groups, the generators as a group also generate as a monoid. This is now #16725.

As for why this is not there for many groups is that they were implemented before monoids were considered in Sage (I believe).

comment:7 follow-up: Changed 3 months ago by ncohen

Hello !!

Could you add doctests for the infinite case ?

Also, why M.monoid_generators().cardinality() != float('inf') instead of M.monoid_generators().is_finite() ?

Nathann

comment:8 Changed 3 months ago by git

  • Commit changed from 6664adb7da87177ef6ae877c10dcf0a49fece50e to 32737e190871917e340683b9467b0cfcc18a72e3

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

3c1c896Merge branch 'develop' into public/groups/cartesian_product_category-16718
32737e1Added test for infinitely generated groups.

comment:9 Changed 3 months ago by git

  • Commit changed from 32737e190871917e340683b9467b0cfcc18a72e3 to 156fe1ded7e1a8bfa184c4ea51a65952ec7f85ad

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

156fe1dChanged finiteness test.

comment:10 Changed 3 months ago by git

  • Commit changed from 156fe1ded7e1a8bfa184c4ea51a65952ec7f85ad to f8539f428dfa3c770b35969c1a7668a89ddfe892

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

f8539f4Added test for lists/tuples for finitely generated.

comment:11 in reply to: ↑ 7 ; follow-up: Changed 3 months ago by tscrim

Replying to ncohen:

Could you add doctests for the infinite case ?

Done.

Also, why M.monoid_generators().cardinality() != float('inf') instead of M.monoid_generators().is_finite() ?

I've changed this to in FiniteEnumeratedSets() which is more restrictive, but it is safer. I've also added a second safety check in case *_generators() returns a tuple or a list (it shouldn't and maybe tuple/list should be considered as a objects in FiniteEnumeratedSets()?).

comment:12 in reply to: ↑ 11 ; follow-up: Changed 3 months ago by ncohen

Yo.

I've changed this to in FiniteEnumeratedSets() which is more restrictive, but it is safer.

It is also more costly. Really it would all be okay if this was compiled code, but I keep thinking of what happens when a line like

if all(M.monoid_generators() in FiniteEnumeratedSets()
  or isinstance(M.monoid_generators(), (tuple, list)) for M in F):
  ret = [lift(i, gen) for i,M in enumerate(F) for gen in M.monoid_generators()]

is executed and it really is awful... monoid_generators() is called once or twice per factor, the caching mechanism does its job to return the pre-computed generators if necessary, FiniteEnumeratedSets() is also created at each turn and because it is a UniqueRepresentation of something there is a lookup going on there too....

I've also added a second safety check in case *_generators() returns a tuple or a list (it shouldn't and maybe tuple/list should be considered as a objects in FiniteEnumeratedSets()?).

Don't know ... Then you would have stuff which is detected as FiniteEnumeratedSet but does not inherit the methods... Well...

Okay. Despite the fact that I really do not like categories and probably never will, thank you for fixing that, your patch does the job. Can you fix the broken doctests ? It can be set to positive_review afterwards.

Nathann

comment:13 Changed 3 months ago by ncohen

Sorry, I forgot to give you the files

----------------------------------------------------------------------
sage -t --long algebras.py  # 1 doctest failed
sage -t --long covariant_functorial_construction.py  # 2 doctests failed
sage -t --long cartesian_product.py  # 3 doctests failed
----------------------------------------------------------------------

comment:14 Changed 3 months ago by git

  • Commit changed from f8539f428dfa3c770b35969c1a7668a89ddfe892 to 79db91ea092db9fd2143e5812fc490a5bb01e581

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

79db91eFixed trivial failing doctests.

comment:15 Changed 3 months ago by git

  • Commit changed from 79db91ea092db9fd2143e5812fc490a5bb01e581 to 8db0f5138914ddd7a9da9e2a57d26c8f45091c93

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

8db0f51Micro-optimizations to the *_generators.

comment:16 in reply to: ↑ 12 ; follow-up: Changed 3 months ago by tscrim

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Replying to ncohen:

It is also more costly. Really it would all be okay if this was compiled code, but I keep thinking of what happens when a line like

if all(M.monoid_generators() in FiniteEnumeratedSets()
  or isinstance(M.monoid_generators(), (tuple, list)) for M in F):
  ret = [lift(i, gen) for i,M in enumerate(F) for gen in M.monoid_generators()]

is executed and it really is awful... monoid_generators() is called once or twice per factor, the caching mechanism does its job to return the pre-computed generators if necessary, FiniteEnumeratedSets() is also created at each turn and because it is a UniqueRepresentation of something there is a lookup going on there too....

I changed it to create FiniteEnumeratedSets() outside of the loop (its a micro-optimization: the result is cached and the number of factors is small). However *_generators is very rarely to be called twice and not short-circuit the all (because *_generators should return a Family), and it should be cached.

Don't know ... Then you would have stuff which is detected as FiniteEnumeratedSet but does not inherit the methods... Well...

Another question for me to ask Nicolas next time I see him.

Okay. Despite the fact that I really do not like categories and probably never will, thank you for fixing that, your patch does the job. Can you fix the broken doctests ? It can be set to positive_review afterwards.

Thanks Nathann!

comment:17 in reply to: ↑ 16 Changed 3 months ago by ncohen

Yoooooooo !

I changed it to create FiniteEnumeratedSets() outside of the loop (its a micro-optimization: the result is cached and the number of factors is small).

Thanks for that :-)

Nathann

comment:18 Changed 3 months ago by vbraun

  • Branch changed from public/groups/cartesian_product_category-16718 to 8db0f5138914ddd7a9da9e2a57d26c8f45091c93
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.