Opened 4 months ago
Closed 4 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 4 months ago by tscrim
- Branch set to public/groups/cartesian_product_category-16718
- Commit set to 6664adb7da87177ef6ae877c10dcf0a49fece50e
- Status changed from new to needs_review
comment:2 Changed 4 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 4 months ago by ncohen
- Status changed from needs_review to needs_info
comment:4 follow-up: ↓ 5 Changed 4 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: ↓ 6 Changed 4 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 4 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 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 follow-up: ↓ 11 Changed 4 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 4 months ago by git
- Commit changed from 6664adb7da87177ef6ae877c10dcf0a49fece50e to 32737e190871917e340683b9467b0cfcc18a72e3
comment:9 Changed 4 months ago by git
- Commit changed from 32737e190871917e340683b9467b0cfcc18a72e3 to 156fe1ded7e1a8bfa184c4ea51a65952ec7f85ad
Branch pushed to git repo; I updated commit sha1. New commits:
156fe1d | Changed finiteness test. |
comment:10 Changed 4 months ago by git
- 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 ; follow-up: ↓ 12 Changed 4 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: ↓ 16 Changed 4 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 4 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 4 months ago by git
- 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 4 months ago by git
- Commit changed from 79db91ea092db9fd2143e5812fc490a5bb01e581 to 8db0f5138914ddd7a9da9e2a57d26c8f45091c93
Branch pushed to git repo; I updated commit sha1. New commits:
8db0f51 | Micro-optimizations to the *_generators. |
comment:16 in reply to: ↑ 12 ; follow-up: ↓ 17 Changed 4 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 4 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 4 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
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: