Create a category for Cartesian products of groups

[tscrim]

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.

CC: @nathanncohen @nthiery

Component: group theory

Keywords: cartesian product, generators

Author: Travis Scrimshaw

Branch/Commit: 8db0f51

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/16718

[tscrim]

Branch: public/groups/cartesian_product_category-16718

[tscrim]

comment:1

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:

95ebfa2	Added a CartesianProduct category for groups.
a96ee13	Changes and copied over to monoids as well.
9e91a51	Added a TODO message.
6664adb	Fixed doctests in groups.py.

[tscrim]

Commit: 6664adb

[nathanncohen]

comment:2

Helloooooooooooooooooo !!

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

Nathann

[tscrim]

comment:4

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.

[nathanncohen]

comment:5

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

[tscrim]

comment:6

Replying to @nathanncohen:

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).

[nathanncohen]

comment:7

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

[sagetrac-git]

Changed commit from 6664adb to 32737e1

[sagetrac-git]

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

3c1c896	Merge branch 'develop' into public/groups/cartesian_product_category-16718
32737e1	Added test for infinitely generated groups.

[sagetrac-git]

Changed commit from 32737e1 to 156fe1d

[sagetrac-git]

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

156fe1d

Changed finiteness test.

[sagetrac-git]

Changed commit from 156fe1d to f8539f4

[sagetrac-git]

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

f8539f4

Added test for lists/tuples for finitely generated.

[tscrim]

comment:11

Replying to @nathanncohen:

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()?).

[nathanncohen]

comment:12

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

[nathanncohen]

comment:13

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
----------------------------------------------------------------------

[sagetrac-git]

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

79db91e

Fixed trivial failing doctests.

[sagetrac-git]

Changed commit from f8539f4 to 79db91e

[sagetrac-git]

Changed commit from 79db91e to 8db0f51

[sagetrac-git]

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

8db0f51

Micro-optimizations to the *_generators.

[tscrim]

Reviewer: Nathann Cohen

[tscrim]

comment:16

Replying to @nathanncohen:

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!

[nathanncohen]

comment:17

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

[vbraun]

Changed branch from public/groups/cartesian_product_category-16718 to 8db0f51