Restructuring Diagram/Partition Algebras to match category structure

[ghseeli]

Currently, the Partition/Diagram 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.)

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 Partition/Diagram 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.)

---

Apply:

• attachment: trac_14234-folded-ts.patch

Depends on #10630

CC: @alauve @srdoty @saliola

Component: algebra

Keywords: Partition algebra, diagram algebra, days38, days40

Author: Stephen Doty, Aaron Lauve, George H. Seelinger

Reviewer: Travis Scrimshaw, Darij Grinberg

Merged: sage-5.12.beta3

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

[ghseeli]

Changed keywords from Partition algebra, diagram algebra to Partition algebra, diagram algebra, days38, days40

[ghseeli]

comment:1

Attachment: 17710.patch.gz

[tscrim]

comment:2

This patch has been useful to some of my colleagues, and I would like to see it get into sage.

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.

[ghseeli]

comment:3

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!

[tscrim]

comment:4

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.

[ghseeli]

comment:5

Attachment: trac_14232_latexDrawing.patch.gz

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.

[tscrim]

comment:6

How close is this to being ready review? Thanks.

[ghseeli]

comment:7

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.

[tscrim]

comment:8

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 IdealAlgebra since that will likely cause some confusion (perhaps something that does not begin with Ideal such as PartitionIdealAlgebra)? 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.

Thank you,

Travis

PS - No need to worry about the time delay. Thanks for getting this done.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:9

Okay, here's my review patch. I changed IdealAlgebra to IdealPartitionAlgebra, 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.

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.

[tscrim]

Changed author from ghseeli, s.r.doty, alauve to Stephen Doty, Aaron Lauve, George H. Seelinger

[tscrim]

comment:10

For patchbot:

Apply: trac_14234_revision_for_5.10_compatibility.patch trac_14234-review-ts.patch

[ghseeli]

comment:11

I talked to my co-authors and we seem to agree that "PropagatingIdeal" might be a better name for a few reasons:

1. There are actually many ideals in the PartitionAlgebra.

2. It is defined based on the propagating number of the diagrams.

3. It is technically a non-unital algebra, which makes calling it an algebra debatable amongst some circles.

Once this is done, I think this enhancement is good to go.

Replying to @tscrim:

Okay, here's my review patch. I changed IdealAlgebra to IdealPartitionAlgebra, 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.

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.

[tscrim]

comment:12

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.

For patchbot:

Apply: trac_14234_revision_for_5.10_compatibility.patch trac_14234-review-ts.patch

[darijgr]

comment:15

Adding a dependency needed for this to apply.

[darijgr]

Dependencies: #10630

[tscrim]

comment:17

Sorry that wasn't listed Darij. Thanks for updating this.

[darijgr]

comment:18

This is a very promising patch! Some errors I found:

    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`

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 some ideal generated by ideal partitions -- and there are many of those.

Actually I see the "propogating" typo elsewhere too. Also, a "with with" in the definition of ideal_diagrams.

Also, typo: "ommitted".

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, range(1,int(k+0.5)) 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?

There is a more serious issue with the intermediate algebras, and it's this (from your doctest):

        sage: da.partition_diagrams(1.5)
        [{{2, -2}, {1, -1}}, {{-1}, {2, -2}, {1}}]

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.

Moreover, da.partition_diagrams(2) returns a combinatorial class whereas da.partition_diagrams(1.5) returns a list. I am a bit puzzled because this hardly intended behaviour is doctested for...

[darijgr]

comment:20

Another reason why floats are a bad thing:

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

I think the code should use rationals, and floats in the input should be normalized to the nearest semi-integer.

Remove the word "with" from with propogating number less than, since there is already a "with" on the preceding line.

There is a typo ("usualy") here:

        Returns the product of two basis diagrams. Usually it is not called
        directly, but indirectly through usualy arithmetic operators.

but actually the word can be removed.

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.

Put "k" in backticks in The Brauer algebra of rank k.

The docstring ambient returns the partition algebra the Brauer algebra is a sub-algebra of. should be adjusted as it is defined not just for a Brauer algebra but for any subalgebra.

It seems to me that the SubPartitionAlgebra docstring should say that the subalgebra is spanned by a subset of the basis of the partition algebra. Otherwise the code of the retract method makes no sense.

[tscrim]

comment:21

There are two reasons why I left it as 0.5 instead of 1/2, the first is that floor 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 == example, so it's an unfair test.

I think that da.partition_diagrams 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.

For the 0.5 +/- 0.5, 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 0.1 added 10 times, then it's slightly more worrisome (but I think it's still okay...)

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

Thanks for your comments Darij.

Best,

Travis

[tscrim]

Attachment: trac_14234-review-ts.patch.gz

[tscrim]

comment:22

Hey Darij,

Here's the new version of the review patch with all of the changes. I wasn't very explicit/detailed with the docstring for SubPartitionAlgebra since it's an internal (abstract) class. If you happy with my changes, go ahead and set this to positive review.

Best,

Travis

For patchbot:

Apply: trac_14234_revision_for_5.10_compatibility.patch​, trac_14234-review-ts.patch​

[darijgr]

Attachment: trac_14234-microchange-dg.2.patch.gz

[darijgr]

comment:23

Attachment: trac_14234-microchange-dg.patch.gz

Hi Travis,

thanks, the issues are fixed. I've suggested a little improvement on the propagating ideal docstring in attachment: trac_14234-microchange-dg.patch 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.

Greets,

Darij

[tscrim]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Darij Grinberg

[tscrim]

comment:25

Thanks Darij.

[jdemeyer]

Attachment: trac_14234_revision_for_5.10_compatibility.patch.gz

[jdemeyer]

comment:26

Folded both patches since the folded patch is smaller than the original patch and smaller than the reviewer patch! Also added attachment: trac_14234-microchange-dg.patch which wasn't mentioned in the "Apply" block but I guess was meant to be merged anyway.

[jdemeyer]

comment:27

This AssertionError should be fixed (you probably want to raise a ValueError instead):

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: 

[tscrim]

comment:28

Attachment: trac_14234-folded-ts.patch.gz

Here's the folded patch which replaces asserts with raising ValueErrors.

Sorry for not noticing that the microchange patch was not listed in the apply section.

For patchbot:

Apply: trac_14234-folded-ts.patch

[jdemeyer]

Merged: sage-5.12.beta3