Sage: Ticket #14234: Restructuring Diagram/Partition Algebras to match category structure
https://trac.sagemath.org/ticket/14234
<p>
Currently, the <a class="missing wiki">Partition/Diagram?</a> Algebra implementations in Sage need to be redone. This problem was identified at Sage Days 38. The documentation is not very clear on how it should be used, and although it is supposed to be an algebra, it does not follow the standard form for algebras in Sage (most likely because these algebras have not been modified since 2007.) <br /><br />This attached program seeks to provide an alternate implementation for, and eventually replace once dependencies are resolved, the existing PartionAlgebra package. More detail about these specific algebras can be found in a 2005 paper by Halverson and Ram titled "Partition Algebras." This new implementation restructures the <a class="missing wiki">Partition/Diagram?</a> Algebras to use the category structure in Sage, so that they are actually implemented as Algebras_with_basis. The new implementation also provides much more detailed documentation on how to use the Partition Algebras, what they actually are, and provides an easier and more standard usage pattern (inherited from CombinatorialFreeModule.)
</p>
<hr />
<p>
Apply:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14234/trac_14234-folded-ts.patch" title="Attachment 'trac_14234-folded-ts.patch' in Ticket #14234">trac_14234-folded-ts.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14234/trac_14234-folded-ts.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14234
Trac 1.1.6ghseeliWed, 06 Mar 2013 05:10:58 GMTattachment set
https://trac.sagemath.org/ticket/14234
https://trac.sagemath.org/ticket/14234
<ul>
<li><strong>attachment</strong>
set to <em>17710.patch</em>
</li>
</ul>
TicketghseeliWed, 06 Mar 2013 05:14:38 GMTkeywords changed
https://trac.sagemath.org/ticket/14234#comment:1
https://trac.sagemath.org/ticket/14234#comment:1
<ul>
<li><strong>keywords</strong>
<em>days38</em> <em>days40</em> added
</li>
</ul>
TickettscrimTue, 30 Apr 2013 16:55:15 GMT
https://trac.sagemath.org/ticket/14234#comment:2
https://trac.sagemath.org/ticket/14234#comment:2
<p>
This patch has been useful to some of my colleagues, and I would like to see it get into sage.
</p>
<p>
Currently I couldn't see how we could display the diagrams pictorially in latex, and I think it would be really cool if we could have the latex version of the elements as sums of the pictorial diagrams. There seemed to be a few functions missing some doctests. Let me know when this gets ready for a formal review. Thanks.
</p>
TicketghseeliTue, 30 Apr 2013 17:00:37 GMT
https://trac.sagemath.org/ticket/14234#comment:3
https://trac.sagemath.org/ticket/14234#comment:3
<p>
I have a second revision on my computer that I am adding the finishing touches to. I will try to upload it in the following week. I have some ideas for pictorial representations using tikz, but the standard networkx and other drawing libraries are not powerful enough to make meaningful diagrams the same way sage does with other graphs. I wrote some code at one point in networkx to display them, but this ended up with issues when trying to create edges along the rows of diagrams, such as an edge between vertex 1 and vertex 3 (it looked the same as having edges {1,2},{2,3}). I will be sure to let you know when I need some formal review and I am glad your colleagues have found this patch useful. Thank you!
</p>
TickettscrimThu, 02 May 2013 14:43:27 GMT
https://trac.sagemath.org/ticket/14234#comment:4
https://trac.sagemath.org/ticket/14234#comment:4
<p>
Even if the diagrams are not too clean pictorially in tikz, as long as the output is moderately easily parseable and the connectivity is there, I think that will be good. Anyways, just let me know when it's ready. Thanks.
</p>
TicketghseeliThu, 30 May 2013 02:38:46 GMTattachment set
https://trac.sagemath.org/ticket/14234
https://trac.sagemath.org/ticket/14234
<ul>
<li><strong>attachment</strong>
set to <em>trac_14232_latexDrawing.patch</em>
</li>
</ul>
TicketghseeliThu, 30 May 2013 02:41:50 GMT
https://trac.sagemath.org/ticket/14234#comment:5
https://trac.sagemath.org/ticket/14234#comment:5
<p>
I have added a new patch that I believe may need to be applied after the previous one has been. However, this patch *should* now allow for the generation of LaTeX code using TikZ to create diagrams for individual, basis diagrams. I have not changed any of the tests, however, so any tests that failed before will probably still fail.
</p>
TickettscrimSun, 21 Jul 2013 10:32:15 GMT
https://trac.sagemath.org/ticket/14234#comment:6
https://trac.sagemath.org/ticket/14234#comment:6
<p>
How close is this to being ready review? Thanks.
</p>
TicketghseeliTue, 23 Jul 2013 02:26:50 GMT
https://trac.sagemath.org/ticket/14234#comment:7
https://trac.sagemath.org/ticket/14234#comment:7
<p>
I think the patch is ready for review. I'm sorry it took so long! Please let me know if more changes need to be made.
</p>
TickettscrimTue, 23 Jul 2013 03:48:56 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/14234#comment:8
https://trac.sagemath.org/ticket/14234#comment:8
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Travis Scrimshaw</em>
</li>
</ul>
<p>
I've set the ticket to needs_review and I'll write a review patch. I would like to know if there is a better name than <code>IdealAlgebra</code> since that will likely cause some confusion (perhaps something that does not begin with <code>Ideal</code> such as <code>PartitionIdealAlgebra</code>)? I'll take care of this in the review patch as well. Also, you'll need to fill in your real names as the authors.
</p>
<p>
Thank you,<br />
Travis
</p>
<p>
PS - No need to worry about the time delay. Thanks for getting this done.
</p>
TickettscrimWed, 24 Jul 2013 13:50:27 GMTauthor changed
https://trac.sagemath.org/ticket/14234#comment:9
https://trac.sagemath.org/ticket/14234#comment:9
<ul>
<li><strong>author</strong>
changed from <em>ghseeli, s.r.doty, alauve</em> to <em>Stephen Doty, Aaron Lauve, George H. Seelinger</em>
</li>
</ul>
<p>
Okay, here's my review patch. I changed <code>IdealAlgebra</code> to <code>IdealPartitionAlgebra</code>, which is (much) better but I'm not perfectly happy with. If you can think of a better name, then I'll change it. I've also reorganized the class structure to better use base classes and implemented a coercion up to the ambient space for the subalgebras. After that it's mostly docstring/doctest additions and corrections.
</p>
<p>
If you agree with my changes (and can't think of a better name), you can go ahead and set this to positive review. Thanks.
</p>
TickettscrimWed, 24 Jul 2013 13:51:45 GMTdescription changed
https://trac.sagemath.org/ticket/14234#comment:10
https://trac.sagemath.org/ticket/14234#comment:10
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14234?action=diff&version=10">diff</a>)
</li>
</ul>
<p>
For patchbot:
</p>
<p>
Apply: trac_14234_revision_for_5.10_compatibility.patch trac_14234-review-ts.patch
</p>
TicketghseeliThu, 25 Jul 2013 02:00:43 GMT
https://trac.sagemath.org/ticket/14234#comment:11
https://trac.sagemath.org/ticket/14234#comment:11
<p>
I talked to my co-authors and we seem to agree that "<a class="missing wiki">PropagatingIdeal?</a>" might be a better name for a few reasons:
</p>
<p>
1) There are actually many ideals in the <a class="missing wiki">PartitionAlgebra?</a>.<br />
2) It is defined based on the propagating number of the diagrams.<br />
3) It is technically a non-unital algebra, which makes calling it an algebra debatable amongst some circles.
</p>
<p>
Once this is done, I think this enhancement is good to go.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14234#comment:9" title="Comment 9">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Okay, here's my review patch. I changed <code>IdealAlgebra</code> to <code>IdealPartitionAlgebra</code>, which is (much) better but I'm not perfectly happy with. If you can think of a better name, then I'll change it. I've also reorganized the class structure to better use base classes and implemented a coercion up to the ambient space for the subalgebras. After that it's mostly docstring/doctest additions and corrections.
</p>
<p>
If you agree with my changes (and can't think of a better name), you can go ahead and set this to positive review. Thanks.
</p>
</blockquote>
TickettscrimThu, 25 Jul 2013 04:28:21 GMT
https://trac.sagemath.org/ticket/14234#comment:12
https://trac.sagemath.org/ticket/14234#comment:12
<p>
Alright, the name has been changed (I like this one). Just needs one last lookover from you and you can set it to positive review. Thank you.
</p>
<p>
For patchbot:
</p>
<p>
Apply: trac_14234_revision_for_5.10_compatibility.patch trac_14234-review-ts.patch
</p>
TicketghseeliFri, 26 Jul 2013 00:37:28 GMTstatus changed
https://trac.sagemath.org/ticket/14234#comment:13
https://trac.sagemath.org/ticket/14234#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketjdemeyerFri, 26 Jul 2013 06:15:17 GMTmilestone changed
https://trac.sagemath.org/ticket/14234#comment:14
https://trac.sagemath.org/ticket/14234#comment:14
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketdarijFri, 09 Aug 2013 22:02:34 GMT
https://trac.sagemath.org/ticket/14234#comment:15
https://trac.sagemath.org/ticket/14234#comment:15
<p>
Adding a dependency needed for this to apply.
</p>
TicketdarijFri, 09 Aug 2013 22:06:11 GMTdependencies set
https://trac.sagemath.org/ticket/14234#comment:16
https://trac.sagemath.org/ticket/14234#comment:16
<ul>
<li><strong>dependencies</strong>
set to <em>#10630</em>
</li>
</ul>
TickettscrimFri, 09 Aug 2013 22:09:18 GMT
https://trac.sagemath.org/ticket/14234#comment:17
https://trac.sagemath.org/ticket/14234#comment:17
<p>
Sorry that wasn't listed Darij. Thanks for updating this.
</p>
TicketdarijSat, 10 Aug 2013 02:38:08 GMT
https://trac.sagemath.org/ticket/14234#comment:18
https://trac.sagemath.org/ticket/14234#comment:18
<p>
This is a very promising patch! Some errors I found:
</p>
<pre class="wiki"> An propogating ideal.
A propogating ideal of rank `k` is a non-unital algebra with basis indexed
by the collection of ideal set partitions of `\{1, \ldots, k, -1, \ldots,
-k\}`. We say a set partition is ideal if its has propogating number is
less than `k`.
This algebra is thus a subalgebra of the partition algebra.
For more information, see :class:`PartitionAlgebra`
</pre><p>
I don't like this. First of all, it should be "propagating", not "propogating" (fortunately the method name is correct). Second, this should be "The", not "A", propagating ideal. Otherwise it sounds like <strong>some</strong> ideal generated by ideal partitions -- and there are many of those.
</p>
<p>
Actually I see the "propogating" typo elsewhere too. Also, a "with with" in the definition of <code>ideal_diagrams</code>.
</p>
<p>
Also, typo: "ommitted".
</p>
<p>
I'm not very happy with the use of floats (as in "2.5") for the "intermediate" partition algebras. Is it safe to assume that, say, <code>range(1,int(k+0.5))</code> always ends at k-0.5, or can it happen that k-0.5 is a tad smaller than an integer due to a rounding error and k-0.5 no longer falls in the interval?
</p>
<p>
There is a more serious issue with the intermediate algebras, and it's this (from your doctest):
</p>
<pre class="wiki"> sage: da.partition_diagrams(1.5)
[{{2, -2}, {1, -1}}, {{-1}, {2, -2}, {1}}]
</pre><p>
If I am to follow the Halverson-Ram conventions, this should contain three more partition diagrams, e. g., {{1, -1, 2, -2}}. Generally, they define a (k+1/2)-partition diagram, for k being an integer, to be any (k+1)-partition diagram in which k+1 and -k-1 lie in the same block (but don't need to be alone there). These are in bijections with set partitions of a fixed (2k+1)-element set. What you define, instead, bijects with set partitions of a 2k-element set, which is boring since these are already the k-partition diagrams.
</p>
<p>
Moreover, <code>da.partition_diagrams(2)</code> returns a combinatorial class whereas <code>da.partition_diagrams(1.5)</code> returns a list. I am a bit puzzled because this hardly intended behaviour is doctested for...
</p>
TicketdarijSat, 10 Aug 2013 02:38:22 GMTstatus changed
https://trac.sagemath.org/ticket/14234#comment:19
https://trac.sagemath.org/ticket/14234#comment:19
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
TicketdarijSat, 10 Aug 2013 12:29:12 GMT
https://trac.sagemath.org/ticket/14234#comment:20
https://trac.sagemath.org/ticket/14234#comment:20
<p>
Another reason why floats are a bad thing:
</p>
<pre class="wiki">sage: da.PartitionAlgebra(3+1/2, 1, QQ, 'part') == da.PartitionAlgebra(3+1/2, 1, QQ, 'part')
True
sage: da.PartitionAlgebra(3+1/2, 1, QQ, 'part') == da.PartitionAlgebra(3.5, 1, QQ, 'part')
False
</pre><p>
I think the code should use rationals, and floats in the input should be normalized to the nearest semi-integer.
</p>
<p>
Remove the word "with" from <code>with propogating number less than</code>, since there is already a "with" on the preceding line.
</p>
<p>
There is a typo ("usualy") here:
</p>
<pre class="wiki"> Returns the product of two basis diagrams. Usually it is not called
directly, but indirectly through usualy arithmetic operators.
</pre><p>
but actually the word can be removed.
</p>
<p>
I think the docstrings should mention the fact that the partition-to-diagram correspondence is not 1-to-1, and diagrams are usually seen just as intuitive representations of set partitions, with several different diagrams corresponding to the same set partition.
</p>
<p>
Put "k" in backticks in <code>The Brauer algebra of rank k</code>.
</p>
<p>
The docstring <code> ambient returns the partition algebra the Brauer algebra is a sub-algebra of.</code> should be adjusted as it is defined not just for a Brauer algebra but for any subalgebra.
</p>
<p>
It seems to me that the <code>SubPartitionAlgebra</code> docstring should say that the subalgebra is spanned by a subset of the basis of the partition algebra. Otherwise the code of the <code>retract</code> method makes no sense.
</p>
TickettscrimSat, 10 Aug 2013 20:14:52 GMT
https://trac.sagemath.org/ticket/14234#comment:21
https://trac.sagemath.org/ticket/14234#comment:21
<p>
There are two reasons why I left it as <code>0.5</code> instead of <code>1/2</code>, the first is that <code>floor</code> is being called and it seemed somewhat troublesome to covert it to an integer, and the second is this what the old partition algebras used (which is why I didn't look too hard to getting around the first problem). Also IMO you're abusing the input with your <code>==</code> example, so it's an unfair test.
</p>
<p>
I think that <code>da.partition_diagrams</code> is okay since its more of an internal helper function, but I'll change the output to be a list in both cases to match the output of the other such functions.
</p>
<p>
For the <code>0.5 +/- 0.5</code>, since there is no division being performed and they are specified floating points, their bit representations are the same and it's a power of two, so +/- are both okay (here). If it was say <code>0.1</code> added 10 times, then it's slightly more worrisome (but I think it's still okay...)
</p>
<p>
In any case, I'll look more deeply into seeing if I can convert this to using rationals, make sure the 1/2's are correct (and fix it if it's not), and fix those typos (including my spelling of propagate <code>:P</code>).
</p>
<p>
Thanks for your comments Darij.
</p>
<p>
Best,<br />
Travis
</p>
TickettscrimSat, 10 Aug 2013 23:58:49 GMTattachment set
https://trac.sagemath.org/ticket/14234
https://trac.sagemath.org/ticket/14234
<ul>
<li><strong>attachment</strong>
set to <em>trac_14234-review-ts.patch</em>
</li>
</ul>
TickettscrimSun, 11 Aug 2013 00:04:12 GMTstatus changed
https://trac.sagemath.org/ticket/14234#comment:22
https://trac.sagemath.org/ticket/14234#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hey Darij,
</p>
<p>
Here's the new version of the review patch with all of the changes. I wasn't very explicit/detailed with the docstring for <code>SubPartitionAlgebra</code> since it's an internal (abstract) class. If you happy with my changes, go ahead and set this to positive review.
</p>
<p>
Best,<br />
Travis
</p>
<p>
For patchbot:
</p>
<p>
Apply: trac_14234_revision_for_5.10_compatibility.patch, trac_14234-review-ts.patch
</p>
TicketdarijSun, 11 Aug 2013 00:35:47 GMTattachment set
https://trac.sagemath.org/ticket/14234
https://trac.sagemath.org/ticket/14234
<ul>
<li><strong>attachment</strong>
set to <em>trac_14234-microchange-dg.2.patch</em>
</li>
</ul>
TicketdarijSun, 11 Aug 2013 00:35:48 GMTattachment set
https://trac.sagemath.org/ticket/14234
https://trac.sagemath.org/ticket/14234
<ul>
<li><strong>attachment</strong>
set to <em>trac_14234-microchange-dg.patch</em>
</li>
</ul>
TicketdarijSun, 11 Aug 2013 00:37:27 GMT
https://trac.sagemath.org/ticket/14234#comment:23
https://trac.sagemath.org/ticket/14234#comment:23
<p>
Hi Travis,
</p>
<p>
thanks, the issues are fixed. I've suggested a little improvement on the propagating ideal docstring in <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14234/trac_14234-microchange-dg.patch" title="Attachment 'trac_14234-microchange-dg.patch' in Ticket #14234">trac_14234-microchange-dg.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14234/trac_14234-microchange-dg.patch" title="Download"></a> which you're free to use or ignore. Basically I think it makes a lot more sense to think of it as an ideal than as a non-unital algebra.
</p>
<p>
Greets,<br />
Darij
</p>
TicketdarijSun, 11 Aug 2013 00:38:12 GMTstatus changed
https://trac.sagemath.org/ticket/14234#comment:24
https://trac.sagemath.org/ticket/14234#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TickettscrimSun, 11 Aug 2013 04:06:43 GMTreviewer changed
https://trac.sagemath.org/ticket/14234#comment:25
https://trac.sagemath.org/ticket/14234#comment:25
<ul>
<li><strong>reviewer</strong>
changed from <em>Travis Scrimshaw</em> to <em>Travis Scrimshaw, Darij Grinberg</em>
</li>
</ul>
<p>
Thanks Darij.
</p>
TicketjdemeyerThu, 15 Aug 2013 15:06:36 GMTattachment set
https://trac.sagemath.org/ticket/14234
https://trac.sagemath.org/ticket/14234
<ul>
<li><strong>attachment</strong>
set to <em>trac_14234_revision_for_5.10_compatibility.patch</em>
</li>
</ul>
TicketjdemeyerThu, 15 Aug 2013 15:07:55 GMTdescription changed
https://trac.sagemath.org/ticket/14234#comment:26
https://trac.sagemath.org/ticket/14234#comment:26
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14234?action=diff&version=26">diff</a>)
</li>
</ul>
<p>
Folded both patches since the folded patch is smaller than the original patch and smaller than the reviewer patch! Also added <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14234/trac_14234-microchange-dg.patch" title="Attachment 'trac_14234-microchange-dg.patch' in Ticket #14234">trac_14234-microchange-dg.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14234/trac_14234-microchange-dg.patch" title="Download"></a> which wasn't mentioned in the "Apply" block but I guess was meant to be merged anyway.
</p>
TicketjdemeyerThu, 15 Aug 2013 15:11:31 GMTstatus changed
https://trac.sagemath.org/ticket/14234#comment:27
https://trac.sagemath.org/ticket/14234#comment:27
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
This <code>AssertionError</code> should be fixed (you probably want to raise a <code>ValueError</code> instead):
</p>
<pre class="wiki">sage: sage.combinat.diagram_algebras.to_Brauer_partition([[1,2,3],[-1,-2]])
---------------------------------------------------------------------------
AssertionError Traceback (most recent call last)
<ipython-input-1-8bfe84be2a91> in <module>()
----> 1 sage.combinat.diagram_algebras.to_Brauer_partition([[Integer(1),Integer(2),Integer(3)],[-Integer(1),-Integer(2)]])
/mazur/release/merger/sage-5.12.beta1/local/lib/python2.7/site-packages/sage/combinat/diagram_algebras.pyc in to_Brauer_partition(l, k)
1419 L2.append(list(i))
1420 for i in L2:
-> 1421 assert len(i) < 3
1422 if (len(i) == 2):
1423 paired.append(i)
AssertionError:
</pre>
TickettscrimThu, 15 Aug 2013 17:02:17 GMTattachment set
https://trac.sagemath.org/ticket/14234
https://trac.sagemath.org/ticket/14234
<ul>
<li><strong>attachment</strong>
set to <em>trac_14234-folded-ts.patch</em>
</li>
</ul>
TickettscrimThu, 15 Aug 2013 17:04:22 GMTstatus, description changed
https://trac.sagemath.org/ticket/14234#comment:28
https://trac.sagemath.org/ticket/14234#comment:28
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/14234?action=diff&version=28">diff</a>)
</li>
</ul>
<p>
Here's the folded patch which replaces asserts with raising <code>ValueError</code>s.
</p>
<p>
Sorry for not noticing that the microchange patch was not listed in the apply section.
</p>
<p>
For patchbot:
</p>
<p>
Apply: trac_14234-folded-ts.patch
</p>
TicketjdemeyerTue, 20 Aug 2013 12:55:50 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/14234#comment:29
https://trac.sagemath.org/ticket/14234#comment:29
<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>merged</strong>
set to <em>sage-5.12.beta3</em>
</li>
</ul>
Ticket