Sage: Ticket #16718: Create a category for Cartesian products of groups
https://trac.sagemath.org/ticket/16718
<p>
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 <a class="ext-link" href="https://groups.google.com/forum/#!topic/sage-devel/nlRGZpr_Je8"><span class="icon"></span>https://groups.google.com/forum/#!topic/sage-devel/nlRGZpr_Je8</a>.
</p>
<pre class="wiki">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'
</pre><p>
We will do so by defining a general method in the appropriate category.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/16718
Trac 1.1.6tscrimSun, 27 Jul 2014 05:50:41 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/16718#comment:1
https://trac.sagemath.org/ticket/16718#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>6664adb7da87177ef6ae877c10dcf0a49fece50e</em>
</li>
<li><strong>branch</strong>
set to <em>public/groups/cartesian_product_category-16718</em>
</li>
</ul>
<p>
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 <code>FinitelyGenerated</code>.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=95ebfa24c927ef1f88ba4fc27dd85c34a8469415"><span class="icon"></span>95ebfa2</a></td><td><code>Added a CartesianProduct category for groups.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a96ee13078718f8f63988491d02a52a65adc95b9"><span class="icon"></span>a96ee13</a></td><td><code>Changes and copied over to monoids as well.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9e91a51da57872f00f93f064289426eb8c4e9721"><span class="icon"></span>9e91a51</a></td><td><code>Added a TODO message.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6664adb7da87177ef6ae877c10dcf0a49fece50e"><span class="icon"></span>6664adb</a></td><td><code>Fixed doctests in groups.py.</code>
</td></tr></table>
TicketncohenSun, 27 Jul 2014 08:56:53 GMT
https://trac.sagemath.org/ticket/16718#comment:2
https://trac.sagemath.org/ticket/16718#comment:2
<p>
Helloooooooooooooooooo !!
</p>
<p>
Why do you need to implement the same function twice ? Isn't there a way to say that <code>group_generators = monoid_generators</code> ?
</p>
<p>
Nathann
</p>
TicketncohenSun, 27 Jul 2014 20:59:46 GMTstatus changed
https://trac.sagemath.org/ticket/16718#comment:3
https://trac.sagemath.org/ticket/16718#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
TickettscrimSun, 27 Jul 2014 21:54:01 GMTstatus changed
https://trac.sagemath.org/ticket/16718#comment:4
https://trac.sagemath.org/ticket/16718#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
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 <code>group_generators</code> currently does not call <code>monoid_generators</code> and not all groups have a <code>monoid_generators</code> method.
</p>
TicketncohenMon, 28 Jul 2014 09:24:41 GMT
https://trac.sagemath.org/ticket/16718#comment:5
https://trac.sagemath.org/ticket/16718#comment:5
<p>
Hello !
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
The code that only exists in your head again ....
</p>
<blockquote class="citation">
<p>
Plus <code>group_generators</code> currently does not call <code>monoid_generators</code> and not all groups have a <code>monoid_generators</code> method.
</p>
</blockquote>
<p>
Why don't all groups have a <code>monoid_generators</code> method ? They are monoids, aren't they ?
</p>
<p>
Nathann
</p>
TickettscrimMon, 28 Jul 2014 17:25:04 GMT
https://trac.sagemath.org/ticket/16718#comment:6
https://trac.sagemath.org/ticket/16718#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16718#comment:5" title="Comment 5">ncohen</a>:
</p>
<blockquote class="citation">
<p>
The code that only exists in your head again ....
</p>
</blockquote>
<p>
There's thousands of lines by hundreds of people. <code>:p</code>
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Plus <code>group_generators</code> currently does not call <code>monoid_generators</code> and not all groups have a <code>monoid_generators</code> method.
</p>
</blockquote>
<p>
Why don't all groups have a <code>monoid_generators</code> method ? They are monoids, aren't they ?
</p>
</blockquote>
<p>
Yes, but as I stated above, there are often more generators as a monoid than as a group. For example, take <code>ZZ</code> under addition, there is 1 generator as a group (<code>+1</code>) but 2 generators as a monoid (<code>+/-1</code>). However for C<sub>n</sub> (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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/16725" title="enhancement: Implement a general monoid_generators for groups (closed: fixed)">#16725</a>.
</p>
<p>
As for why this is not there for many groups is that they were implemented before monoids were considered in Sage (I believe).
</p>
TicketncohenMon, 28 Jul 2014 19:35:38 GMT
https://trac.sagemath.org/ticket/16718#comment:7
https://trac.sagemath.org/ticket/16718#comment:7
<p>
Hello !!
</p>
<p>
Could you add doctests for the infinite case ?
</p>
<p>
Also, why <code>M.monoid_generators().cardinality() != float('inf')</code> instead of <code>M.monoid_generators().is_finite()</code> ?
</p>
<p>
Nathann
</p>
TicketgitTue, 29 Jul 2014 21:06:31 GMTcommit changed
https://trac.sagemath.org/ticket/16718#comment:8
https://trac.sagemath.org/ticket/16718#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>6664adb7da87177ef6ae877c10dcf0a49fece50e</em> to <em>32737e190871917e340683b9467b0cfcc18a72e3</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3c1c896cf83b42b98101b883b2d9a23108a786f5"><span class="icon"></span>3c1c896</a></td><td><code>Merge branch 'develop' into public/groups/cartesian_product_category-16718</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=32737e190871917e340683b9467b0cfcc18a72e3"><span class="icon"></span>32737e1</a></td><td><code>Added test for infinitely generated groups.</code>
</td></tr></table>
TicketgitTue, 29 Jul 2014 21:15:44 GMTcommit changed
https://trac.sagemath.org/ticket/16718#comment:9
https://trac.sagemath.org/ticket/16718#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>32737e190871917e340683b9467b0cfcc18a72e3</em> to <em>156fe1ded7e1a8bfa184c4ea51a65952ec7f85ad</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=156fe1ded7e1a8bfa184c4ea51a65952ec7f85ad"><span class="icon"></span>156fe1d</a></td><td><code>Changed finiteness test.</code>
</td></tr></table>
TicketgitTue, 29 Jul 2014 21:19:52 GMTcommit changed
https://trac.sagemath.org/ticket/16718#comment:10
https://trac.sagemath.org/ticket/16718#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>156fe1ded7e1a8bfa184c4ea51a65952ec7f85ad</em> to <em>f8539f428dfa3c770b35969c1a7668a89ddfe892</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f8539f428dfa3c770b35969c1a7668a89ddfe892"><span class="icon"></span>f8539f4</a></td><td><code>Added test for lists/tuples for finitely generated.</code>
</td></tr></table>
TickettscrimTue, 29 Jul 2014 21:21:15 GMT
https://trac.sagemath.org/ticket/16718#comment:11
https://trac.sagemath.org/ticket/16718#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16718#comment:7" title="Comment 7">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Could you add doctests for the infinite case ?
</p>
</blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<p>
Also, why <code>M.monoid_generators().cardinality() != float('inf')</code> instead of <code>M.monoid_generators().is_finite()</code> ?
</p>
</blockquote>
<p>
I've changed this to <code>in FiniteEnumeratedSets()</code> which is more restrictive, but it is safer. I've also added a second safety check in case <code>*_generators()</code> returns a tuple or a list (it shouldn't and maybe tuple/list should be considered as a objects in <code>FiniteEnumeratedSets()</code>?).
</p>
TicketncohenTue, 29 Jul 2014 21:39:55 GMT
https://trac.sagemath.org/ticket/16718#comment:12
https://trac.sagemath.org/ticket/16718#comment:12
<p>
Yo.
</p>
<blockquote class="citation">
<p>
I've changed this to <code>in FiniteEnumeratedSets()</code> which is more restrictive, but it is safer.
</p>
</blockquote>
<p>
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
</p>
<pre class="wiki">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()]
</pre><p>
is executed and it really is awful... <code>monoid_generators()</code> is called once or twice per factor, the caching mechanism does its job to return the pre-computed generators if necessary, <code>FiniteEnumeratedSets()</code> is also created at each turn and because it is a <code>UniqueRepresentation</code> of something there is a lookup going on there too....
</p>
<blockquote class="citation">
<p>
I've also added a second safety check in case <code>*_generators()</code> returns a tuple or a list (it shouldn't and maybe tuple/list should be considered as a objects in <code>FiniteEnumeratedSets()</code>?).
</p>
</blockquote>
<p>
Don't know ... Then you would have stuff which is detected as <code>FiniteEnumeratedSet</code> but does not inherit the methods... Well...
</p>
<p>
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 <code>positive_review</code> afterwards.
</p>
<p>
Nathann
</p>
TicketncohenTue, 29 Jul 2014 21:40:48 GMT
https://trac.sagemath.org/ticket/16718#comment:13
https://trac.sagemath.org/ticket/16718#comment:13
<p>
Sorry, I forgot to give you the files
</p>
<pre class="wiki">----------------------------------------------------------------------
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
----------------------------------------------------------------------
</pre>
TicketgitTue, 29 Jul 2014 22:00:55 GMTcommit changed
https://trac.sagemath.org/ticket/16718#comment:14
https://trac.sagemath.org/ticket/16718#comment:14
<ul>
<li><strong>commit</strong>
changed from <em>f8539f428dfa3c770b35969c1a7668a89ddfe892</em> to <em>79db91ea092db9fd2143e5812fc490a5bb01e581</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=79db91ea092db9fd2143e5812fc490a5bb01e581"><span class="icon"></span>79db91e</a></td><td><code>Fixed trivial failing doctests.</code>
</td></tr></table>
TicketgitTue, 29 Jul 2014 22:10:41 GMTcommit changed
https://trac.sagemath.org/ticket/16718#comment:15
https://trac.sagemath.org/ticket/16718#comment:15
<ul>
<li><strong>commit</strong>
changed from <em>79db91ea092db9fd2143e5812fc490a5bb01e581</em> to <em>8db0f5138914ddd7a9da9e2a57d26c8f45091c93</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8db0f5138914ddd7a9da9e2a57d26c8f45091c93"><span class="icon"></span>8db0f51</a></td><td><code>Micro-optimizations to the *_generators.</code>
</td></tr></table>
TickettscrimTue, 29 Jul 2014 22:12:05 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/16718#comment:16
https://trac.sagemath.org/ticket/16718#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16718#comment:12" title="Comment 12">ncohen</a>:
</p>
<blockquote class="citation">
<p>
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
</p>
<pre class="wiki">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()]
</pre><p>
is executed and it really is awful... <code>monoid_generators()</code> is called once or twice per factor, the caching mechanism does its job to return the pre-computed generators if necessary, <code>FiniteEnumeratedSets()</code> is also created at each turn and because it is a <code>UniqueRepresentation</code> of something there is a lookup going on there too....
</p>
</blockquote>
<p>
I changed it to create <code>FiniteEnumeratedSets()</code> outside of the loop (its a micro-optimization: the result is cached and the number of factors is small). However <code>*_generators</code> is very rarely to be called twice and not short-circuit the <code>all</code> (because <code>*_generators</code> should return a <code>Family</code>), and it should be cached.
</p>
<blockquote class="citation">
<p>
Don't know ... Then you would have stuff which is detected as <code>FiniteEnumeratedSet</code> but does not inherit the methods... Well...
</p>
</blockquote>
<p>
Another question for me to ask Nicolas next time I see him.
</p>
<blockquote class="citation">
<p>
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 <code>positive_review</code> afterwards.
</p>
</blockquote>
<p>
Thanks Nathann!
</p>
TicketncohenWed, 30 Jul 2014 06:39:04 GMT
https://trac.sagemath.org/ticket/16718#comment:17
https://trac.sagemath.org/ticket/16718#comment:17
<p>
Yoooooooo !
</p>
<blockquote class="citation">
<p>
I changed it to create <code>FiniteEnumeratedSets()</code> outside of the loop (its a micro-optimization: the result is cached and the number of factors is small).
</p>
</blockquote>
<p>
Thanks for that <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketvbraunThu, 31 Jul 2014 00:44:28 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/16718#comment:18
https://trac.sagemath.org/ticket/16718#comment:18
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/groups/cartesian_product_category-16718</em> to <em>8db0f5138914ddd7a9da9e2a57d26c8f45091c93</em>
</li>
</ul>
Ticket