Sage: Ticket #9773: Abelian groups
https://trac.sagemath.org/ticket/9773
<p>
This patch will implement abelian groups, both additive and multiplicative, finite and infinite, under a common abstract class, using machinery for quotients of modules over <code>ZZ</code>. This will make subgroups, intersections of subgroups, isomorphism classes, and quotient groups possible. Generators may be of any type, so long as they support the minimal operations required.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/9773
Trac 1.1.6rbeezerFri, 20 Aug 2010 23:10:06 GMTattachment set
https://trac.sagemath.org/ticket/9773
https://trac.sagemath.org/ticket/9773
<ul>
<li><strong>attachment</strong>
set to <em>trac_9773-abelian-groups-draft-1.patch</em>
</li>
</ul>
TicketrbeezerFri, 20 Aug 2010 23:14:32 GMTstatus, type changed; cc, author set
https://trac.sagemath.org/ticket/9773#comment:1
https://trac.sagemath.org/ticket/9773#comment:1
<ul>
<li><strong>cc</strong>
<em>davidloeffler</em> <em>cremona</em> <em>was</em> <em>nthiery</em> <em>boothby</em> <em>jason</em> <em>kcrisman</em> added
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_info</em>
</li>
<li><strong>type</strong>
changed from <em>defect</em> to <em>enhancement</em>
</li>
<li><strong>author</strong>
set to <em>Rob Beezer</em>
</li>
</ul>
<p>
AAG is the class of additive abelian groups. This is an infinite group with a subgroup and a quotient. (Typically quotients lose the generators and are "generic" but not in this example.)
</p>
<pre class="wiki">sage: A=AAG([3,4,0])
sage: A.gens()
((2, 3, 0), (0, 0, 1))
sage: A.0.order()
12
sage: A.1.order()
+Infinity
sage: B=A.subgroup([A.1])
sage: B
Infinite additive abelian group isomorphic to Z with generator(s): (0, 0, 1)
sage: C=A/B
sage: C
Finite additive abelian group isomorphic to Z_12 with generator(s): (2, 3, 0)
</pre><p>
GUN is a constructor of Groups of Units Mod n. It employs MAG, the class of multiplicative abelian groups. This is an intersection of two subgroups, and then a Cayley table is free (in the category of multiplicative groups).
</p>
<pre class="wiki">sage: G=GUN(72)
sage: G.list()
[1, 65, 49, 17, 25, 41, 55, 47, 31, 71, 7, 23, 37, 29, 13, 53, 61, 5, 19, 11, 67, 35, 43, 59]
sage: G.subgroup([71,7])
Finite multiplicative abelian group isomorphic to Z_2 + Z_6 with generator(s): 55, 65
sage: K=G.subgroup([71,7])
sage: K.list()
[1, 65, 49, 17, 25, 41, 55, 47, 31, 71, 7, 23]
sage: L=G.subgroup([13,7])
sage: L
Finite multiplicative abelian group isomorphic to Z_2 + Z_6 with generator(s): 55, 61
sage: L.list()
[1, 61, 49, 37, 25, 13, 55, 43, 31, 19, 7, 67]
sage: M=K.intersection(L)
sage: M.list()
[1, 7, 49, 55, 25, 31]
sage: M
Finite multiplicative abelian group isomorphic to Z_6 with generator(s): 7
sage: M.cayley_table()
* a b c d e f
+------------
a| a b c d e f
b| b c d e f a
c| c d e f a b
d| d e f a b c
e| e f a b c d
f| f a b c d e
</pre><p>
This is an example from the current additive abelian wrapper class. It shows the generators keyword allowing arbitrary elements to form the group, so long as they know how to add. GUN above is similar, but with multiplication.
</p>
<pre class="wiki">sage: E = EllipticCurve('30a2')
sage: pts = [E(4,-7,1), E(7/4, -11/8, 1), E(3, -2, 1)]
sage: M=AAG([3,2,2], generators=pts)
sage: M.list()
[(0 : 1 : 0), (13 : -52 : 1), (4 : -7 : 1), (3 : -2 : 1), (4 : 2 : 1), (13 : 38 : 1), (7/4 : -11/8 : 1), (1 : -4 : 1), (-2 : -7 : 1), (-5 : 2 : 1), (-2 : 8 : 1), (1 : 2 : 1)]
sage: M.gens()
((7/4 : -11/8 : 1), (13 : -52 : 1))
sage: N=M.subgroup([M.1])
sage: N
Finite additive abelian group isomorphic to Z_6 with generator(s): (13 : -52 : 1)
sage: N.list()
[(0 : 1 : 0), (13 : -52 : 1), (4 : -7 : 1), (3 : -2 : 1), (4 : 2 : 1), (13 : 38 : 1)]
</pre><p>
There is lots to do here still: different filenames, different class names, error-checking, doctests, comparisons, and so on. But the code seems to be working. I'm not 100% confident on the <code>__call__</code> method of the main abstract class and I don't know if I need some things to support coercion better. Any advice or comments at this stage would be appreciated before I begin to clean this all up.
</p>
TicketjhpalmieriSat, 21 Aug 2010 00:39:07 GMT
https://trac.sagemath.org/ticket/9773#comment:2
https://trac.sagemath.org/ticket/9773#comment:2
<p>
Will this interact at all with the class <code>CombinatorialFreeModule</code>? I don't know what the long term plans are, or even if there are any, for connecting this with <code>FreeModule</code>, but the combinatorial version has some nice features.
</p>
<p>
Also, how do you define <strong>R</strong> or <strong>Q</strong> as additive abelian groups with this setup?
</p>
TicketrbeezerSat, 21 Aug 2010 01:35:26 GMT
https://trac.sagemath.org/ticket/9773#comment:3
https://trac.sagemath.org/ticket/9773#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9773#comment:2" title="Comment 2">jhpalmieri</a>:
</p>
<p>
Hi John,
</p>
<p>
Thanks for the good questions. I began this when I tried to implement a multiplicative group in concert with the work at <a class="closed ticket" href="https://trac.sagemath.org/ticket/6449" title="defect: Additive abelian groups (closed: fixed)">#6449</a>. So I really didn't even have groups like <strong>R</strong> and <strong>Q</strong> in mind. Truth-in-advertising would suggest I sprinkle in some "finitely generated" qualifiers in class names and filenames.
</p>
<p>
I've plugged this into the categories framework as groups, but hadn't thought about modules. I'll go take a look at all that to see how this might fit in. Maybe Nicolas Thiery will have some ideas as well.
</p>
<p>
Thanks again,
Rob
</p>
TicketmhansenSat, 21 Aug 2010 05:33:20 GMTcc changed
https://trac.sagemath.org/ticket/9773#comment:4
https://trac.sagemath.org/ticket/9773#comment:4
<ul>
<li><strong>cc</strong>
<em>mhansen</em> added
</li>
</ul>
TicketrbeezerMon, 23 Aug 2010 07:01:26 GMT
https://trac.sagemath.org/ticket/9773#comment:5
https://trac.sagemath.org/ticket/9773#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9773#comment:2" title="Comment 2">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
Will this interact at all with the class <code>CombinatorialFreeModule</code>? I don't know what the long term plans are, or even if there are any, for connecting this with <code>FreeModule</code>, but the combinatorial version has some nice features.
</p>
</blockquote>
<p>
I looked at these two classes. Generally they seem to require the same ring in each "component", whereas the FGP_Module class allows for diffferent rings in each component, such as in creating something like Z_3 x Z_4. So I don't see an abvious way to leverage these, but maybe I'm missing something.
</p>
<p>
Rob
</p>
TicketmpatelMon, 23 Aug 2010 09:58:13 GMT
https://trac.sagemath.org/ticket/9773#comment:6
https://trac.sagemath.org/ticket/9773#comment:6
<h1 id="Tothereleasemanager">To the release manager</h1>
<p>
Please close <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/9694" title="enhancement: Implement direct product of cyclic groups (needs_work)">#9694</a> when this ticket is merged.
</p>
TicketrbeezerThu, 02 Sep 2010 04:18:10 GMTattachment set
https://trac.sagemath.org/ticket/9773
https://trac.sagemath.org/ticket/9773
<ul>
<li><strong>attachment</strong>
set to <em>trac_9773-abelian-groups-draft-2.patch</em>
</li>
</ul>
TicketrbeezerThu, 02 Sep 2010 04:23:21 GMT
https://trac.sagemath.org/ticket/9773#comment:7
https://trac.sagemath.org/ticket/9773#comment:7
<p>
Code is stablizing in draft 2 patch, and I'm starting to write the doctests. Still uncertain about <code>__call__</code> and now its interactions with <code>__contains__</code>.
</p>
<p>
There are liberal comments in the code and the <code>units_modn</code> module has a rather complete demo of functionality.
</p>
TicketzimmermaThu, 28 Oct 2010 09:29:33 GMT
https://trac.sagemath.org/ticket/9773#comment:8
https://trac.sagemath.org/ticket/9773#comment:8
<p>
Question: does this patch solve <a class="new ticket" href="https://trac.sagemath.org/ticket/10181" title="enhancement: speed up AbelianGroup().subgroups() (new)">#10181</a>?
</p>
<p>
Paul Zimmermann
</p>
TicketjhpalmieriThu, 28 Oct 2010 19:31:38 GMT
https://trac.sagemath.org/ticket/9773#comment:9
https://trac.sagemath.org/ticket/9773#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9773#comment:8" title="Comment 8">zimmerma</a>:
</p>
<blockquote class="citation">
<p>
Question: does this patch solve <a class="new ticket" href="https://trac.sagemath.org/ticket/10181" title="enhancement: speed up AbelianGroup().subgroups() (new)">#10181</a>?
</p>
</blockquote>
<p>
While we're at it, how about <a class="closed ticket" href="https://trac.sagemath.org/ticket/9940" title="defect: Fix equality/inequality for AdditiveAbelianGroup (closed: fixed)">#9940</a>?
</p>
TicketrbeezerSun, 31 Oct 2010 17:41:16 GMT
https://trac.sagemath.org/ticket/9773#comment:10
https://trac.sagemath.org/ticket/9773#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9773#comment:8" title="Comment 8">zimmerma</a>:
</p>
<blockquote class="citation">
<p>
Question: does this patch solve <a class="new ticket" href="https://trac.sagemath.org/ticket/10181" title="enhancement: speed up AbelianGroup().subgroups() (new)">#10181</a>?
</p>
</blockquote>
<p>
Short answer: this could speed up <code>subgroups()</code> by a factor of 8, if my experiments are right. We won't beat Magma, but we won't be embarassed on really small examples. This patch does not have a <code>subgroups()</code> method yet, but could be easy to add.
</p>
<p>
Full details at <a class="new ticket" href="https://trac.sagemath.org/ticket/10181" title="enhancement: speed up AbelianGroup().subgroups() (new)">#10181</a>. Thanks for asking.
</p>
<p>
Rob
</p>
TicketrbeezerSun, 31 Oct 2010 17:43:29 GMT
https://trac.sagemath.org/ticket/9773#comment:11
https://trac.sagemath.org/ticket/9773#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9773#comment:9" title="Comment 9">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
While we're at it, how about <a class="closed ticket" href="https://trac.sagemath.org/ticket/9940" title="defect: Fix equality/inequality for AdditiveAbelianGroup (closed: fixed)">#9940</a>?
</p>
</blockquote>
<p>
This patch has code that is in pretty good shape (IMHO). It still needs doctests, plus things like an equality method. So it could fix <a class="closed ticket" href="https://trac.sagemath.org/ticket/9440" title="enhancement: document more environment variables (closed: fixed)">#9440</a> if the equality method is done right?
</p>
TicketrbeezerWed, 23 Mar 2011 20:55:31 GMTcc changed
https://trac.sagemath.org/ticket/9773#comment:12
https://trac.sagemath.org/ticket/9773#comment:12
<ul>
<li><strong>cc</strong>
<em>justin</em> added
</li>
</ul>
<p>
Justin - no documentation to speak of, but look at the derived classes to get a feel for how this might work.
</p>
<p>
Any insights or ideas you might have would be helpful before I try to finish this off later this spring.
</p>
<p>
Rob
</p>
TicketrbeezerThu, 17 May 2012 22:45:11 GMTattachment set
https://trac.sagemath.org/ticket/9773
https://trac.sagemath.org/ticket/9773
<ul>
<li><strong>attachment</strong>
set to <em>trac_9773-abelian-groups-draft-3.patch</em>
</li>
</ul>
TicketrbeezerThu, 17 May 2012 22:49:10 GMT
https://trac.sagemath.org/ticket/9773#comment:13
https://trac.sagemath.org/ticket/9773#comment:13
<p>
Draft 3 patch is actually about a year old at time of posting (for safe-keeping). Category code changed out from under me, so I had to start over last summer. This applies on 5.0.rc0, builds, and simple testing of the abstract classes seems to be successful.
</p>
<p>
Needs documentation, some changes, and practical derived classes, like totally abstract cyclic groups, the multiplicative subgroup of units mod n, etc. IIRC, there are examples of these in the previous drafts. I fully intend to work on this over the summer.
</p>
TicketrbeezerMon, 16 Jul 2012 03:05:37 GMT
https://trac.sagemath.org/ticket/9773#comment:14
https://trac.sagemath.org/ticket/9773#comment:14
<p>
I keep plugging away at this. Some improvement by exploiting category code. Totally reworked, so most of my comments above are obsolete.
</p>
<p>
Draft 4 patch is very functional, with the following caveats that I cannot figure out. Assistance greatly appreciated if you can provide advice or specific pointers. There is quite a bit of functionality demonstrated in the module-level doctests. Little or no error-checking yet.
</p>
<ol><li> <code>_element_constructor()</code> works fine with module elements, which is to be expected, since it is copied verbatim from there. I cannot seem to make it accept reasonable elements of the parent of the generators for subsequent processing without totally breaking extensive doctests.
</li><li> The multiplicative version does not pass the <code>TestSuite</code> framework. Likely the implementation of multiplicative operators on top of an additive class (FGP modules) is to blame?
</li></ol><p>
I've tried to add copious comments to make it easier to navigate the code. More specific problem areas are flagged with <code>*PROBLEM*</code>.
</p>
TicketrbeezerMon, 16 Jul 2012 04:01:34 GMTattachment set
https://trac.sagemath.org/ticket/9773
https://trac.sagemath.org/ticket/9773
<ul>
<li><strong>attachment</strong>
set to <em>trac_9773-abelian-groups-draft-4.patch</em>
</li>
</ul>
TicketrbeezerMon, 16 Jul 2012 04:05:21 GMT
https://trac.sagemath.org/ticket/9773#comment:15
https://trac.sagemath.org/ticket/9773#comment:15
<p>
Just replaced the patch. Realized the <code>_user_to_optimized()</code> method needed to be in the parent class, not the element class. Then had some partial success getting <code>_element_constructor()</code> to work, but it still fails on subgroups - <code>.smith_form_gens()</code> for FGP modules is the suspect.
</p>
<p>
Test suite on the elliptic curve example was testing the wrong instance - as corrected one test fails, so it is commented out, but should be experimented with to determine root cause.
</p>
TicketrbeezerTue, 31 Jul 2012 02:54:58 GMTattachment set
https://trac.sagemath.org/ticket/9773
https://trac.sagemath.org/ticket/9773
<ul>
<li><strong>attachment</strong>
set to <em>trac_9773-abelian-groups-draft-5.patch</em>
</li>
</ul>
TicketrbeezerTue, 31 Jul 2012 02:58:56 GMT
https://trac.sagemath.org/ticket/9773#comment:16
https://trac.sagemath.org/ticket/9773#comment:16
<p>
draft-4 failed to include "<span class="underline">init</span>.py" in the patch - that has been corrected in draft-5.
</p>
<p>
David Roe helped me rework the initialization of the module class, so now the test suite is not doing additive tests on the multiplicative classes. And I also believe I understand the problems with the element constructor (again with David's help). So I think I'm over the hump on this one now.
</p>
<p>
Long list of tests at module level are all passing, except one test suite (which I think I understand and can correct). A few other test suites commented-out, but I think they are correctable also.
</p>
TicketrbeezerWed, 08 Aug 2012 03:53:32 GMTattachment set
https://trac.sagemath.org/ticket/9773
https://trac.sagemath.org/ticket/9773
<ul>
<li><strong>attachment</strong>
set to <em>trac_9773-abelian-groups-draft-6.patch</em>
</li>
</ul>
TicketrbeezerWed, 08 Aug 2012 03:56:25 GMT
https://trac.sagemath.org/ticket/9773#comment:17
https://trac.sagemath.org/ticket/9773#comment:17
<p>
draft-6 patch is darn close to functional. Lots of doctests, all passing. Lots of code pushed up to abstract class. Much more to do on docstrings.
</p>
<p>
One <strong>real</strong> edit in <code>FGP_Module</code> code. Remainder are stray print statements to be cleaned up.
</p>
TicketAlexGhitzaThu, 30 Aug 2012 05:47:05 GMTcc changed
https://trac.sagemath.org/ticket/9773#comment:18
https://trac.sagemath.org/ticket/9773#comment:18
<ul>
<li><strong>cc</strong>
<em>AlexGhitza</em> added
</li>
</ul>
<p>
Hi Rob,
</p>
<p>
Just a quick note to say that I've played with draft-6 a bit (mainly with the <code>UnitsModmGroup</code>), and I very much like it. Thanks for all the work you've put into this (and the patience!).
</p>
TicketrbeezerThu, 30 Aug 2012 21:20:56 GMT
https://trac.sagemath.org/ticket/9773#comment:19
https://trac.sagemath.org/ticket/9773#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9773#comment:18" title="Comment 18">AlexGhitza</a>:
</p>
<blockquote class="citation">
<p>
Just a quick note to say that I've played with draft-6 a bit (mainly with the <code>UnitsModmGroup</code>), and I very much like it. Thanks for all the work you've put into this (and the patience!).
</p>
</blockquote>
<p>
Thanks very much, Alex, for the encouragement. Still lots of docstrings to work on, but making (slow) progress, since classes started recently. Soon. ;-)
</p>
TicketzimmermaTue, 08 Jan 2013 08:27:39 GMT
https://trac.sagemath.org/ticket/9773#comment:20
https://trac.sagemath.org/ticket/9773#comment:20
<p>
any progress on this? Which info is needed?
</p>
<p>
Paul
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/9773#comment:21
https://trac.sagemath.org/ticket/9773#comment:21
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketrbeezerSat, 09 Nov 2013 05:51:08 GMT
https://trac.sagemath.org/ticket/9773#comment:22
https://trac.sagemath.org/ticket/9773#comment:22
<p>
Update: v6 patch will compain about one hunk not applying - just ignore it, it is no longer needed.
</p>
<p>
On 5.12: compiles and passes all tests.
</p>
<p>
Basically I think the code is solid on this one, but it needs extensive work to fully document and doctest. And then it would be a big effort to slowly integrate in.
</p>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/9773#comment:23
https://trac.sagemath.org/ticket/9773#comment:23
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/9773#comment:24
https://trac.sagemath.org/ticket/9773#comment:24
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/9773#comment:25
https://trac.sagemath.org/ticket/9773#comment:25
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketkcrismanThu, 12 Feb 2015 15:03:00 GMT
https://trac.sagemath.org/ticket/9773#comment:26
https://trac.sagemath.org/ticket/9773#comment:26
<p>
Hey Rob, what's the status here? If one (say, me) were to have a student who knows some algebra and is a solid programmer, could they finish up what is remaining? Could be really useful stuff.
</p>
TicketmcognettaThu, 19 Feb 2015 03:50:37 GMT
https://trac.sagemath.org/ticket/9773#comment:27
https://trac.sagemath.org/ticket/9773#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9773#comment:26" title="Comment 26">kcrisman</a>:
</p>
<blockquote class="citation">
<p>
Hey Rob, what's the status here? If one (say, me) were to have a student who knows some algebra and is a solid programmer, could they finish up what is remaining? Could be really useful stuff.
</p>
</blockquote>
<p>
I am also interested in this. I am a student as well with algebra coursework under my belt. If there is still a need for this and you would like to work together, I am down.
</p>
Ticket