Opened 5 years ago
Closed 5 years ago
#16718 closed enhancement (fixed)
Create a category for Cartesian products of groups
Reported by:  tscrim  Owned by:  tscrim 

Priority:  major  Milestone:  sage6.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/sagedevel/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 5 years ago by
 Branch set to public/groups/cartesian_product_category16718
 Commit set to 6664adb7da87177ef6ae877c10dcf0a49fece50e
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
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 5 years ago by
 Status changed from needs_review to needs_info
comment:4 followup: ↓ 5 Changed 5 years ago by
 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 ; followup: ↓ 6 Changed 5 years ago by
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 callmonoid_generators
and not all groups have amonoid_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 5 years ago by
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 callmonoid_generators
and not all groups have amonoid_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 C_{n} (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 followup: ↓ 11 Changed 5 years ago by
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 5 years ago by
 Commit changed from 6664adb7da87177ef6ae877c10dcf0a49fece50e to 32737e190871917e340683b9467b0cfcc18a72e3
comment:9 Changed 5 years ago by
 Commit changed from 32737e190871917e340683b9467b0cfcc18a72e3 to 156fe1ded7e1a8bfa184c4ea51a65952ec7f85ad
Branch pushed to git repo; I updated commit sha1. New commits:
156fe1d  Changed finiteness test.

comment:10 Changed 5 years ago by
 Commit changed from 156fe1ded7e1a8bfa184c4ea51a65952ec7f85ad to f8539f428dfa3c770b35969c1a7668a89ddfe892
Branch pushed to git repo; I updated commit sha1. New commits:
f8539f4  Added test for lists/tuples for finitely generated.

comment:11 in reply to: ↑ 7 ; followup: ↓ 12 Changed 5 years ago by
Replying to ncohen:
Could you add doctests for the infinite case ?
Done.
Also, why
M.monoid_generators().cardinality() != float('inf')
instead ofM.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 ; followup: ↓ 16 Changed 5 years ago by
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 precomputed 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 inFiniteEnumeratedSets()
?).
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 5 years ago by
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 5 years ago by
 Commit changed from f8539f428dfa3c770b35969c1a7668a89ddfe892 to 79db91ea092db9fd2143e5812fc490a5bb01e581
Branch pushed to git repo; I updated commit sha1. New commits:
79db91e  Fixed trivial failing doctests.

comment:15 Changed 5 years ago by
 Commit changed from 79db91ea092db9fd2143e5812fc490a5bb01e581 to 8db0f5138914ddd7a9da9e2a57d26c8f45091c93
Branch pushed to git repo; I updated commit sha1. New commits:
8db0f51  Microoptimizations to the *_generators.

comment:16 in reply to: ↑ 12 ; followup: ↓ 17 Changed 5 years ago by
 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 precomputed generators if necessary,FiniteEnumeratedSets()
is also created at each turn and because it is aUniqueRepresentation
of something there is a lookup going on there too....
I changed it to create FiniteEnumeratedSets()
outside of the loop (its a microoptimization: the result is cached and the number of factors is small). However *_generators
is very rarely to be called twice and not shortcircuit 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 5 years ago by
Yoooooooo !
I changed it to create
FiniteEnumeratedSets()
outside of the loop (its a microoptimization: the result is cached and the number of factors is small).
Thanks for that :)
Nathann
comment:18 Changed 5 years ago by
 Branch changed from public/groups/cartesian_product_category16718 to 8db0f5138914ddd7a9da9e2a57d26c8f45091c93
 Resolution set to fixed
 Status changed from positive_review to closed
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:
Added a CartesianProduct category for groups.
Changes and copied over to monoids as well.
Added a TODO message.
Fixed doctests in groups.py.