Opened 8 years ago

Closed 7 years ago

#14234 closed enhancement (fixed)

Restructuring Diagram/Partition Algebras to match category structure

Reported by: ghseeli Owned by: AlexGhitza
Priority: minor Milestone: sage-5.12
Component: algebra Keywords: Partition algebra, diagram algebra, days38, days40
Cc: alauve, s.r.doty, saliola Merged in: sage-5.12.beta3
Authors: Stephen Doty, Aaron Lauve, George H. Seelinger Reviewers: Travis Scrimshaw, Darij Grinberg
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #10630 Stopgaps:

Description (last modified by tscrim)

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:

Attachments (7)

17710.patch (61.0 KB) - added by ghseeli 8 years ago.
trac_14232_latexDrawing.patch (36.1 KB) - added by ghseeli 8 years ago.
trac_14234-review-ts.patch (90.0 KB) - added by tscrim 7 years ago.
trac_14234-microchange-dg.2.patch (781 bytes) - added by darij 7 years ago.
trac_14234-microchange-dg.patch (781 bytes) - added by darij 7 years ago.
trac_14234_revision_for_5.10_compatibility.patch (53.7 KB) - added by jdemeyer 7 years ago.
trac_14234-folded-ts.patch (53.9 KB) - added by tscrim 7 years ago.

Download all attachments as: .zip

Change History (36)

Changed 8 years ago by ghseeli

comment:1 Changed 8 years ago by ghseeli

  • Keywords days38 days40 added

comment:2 Changed 8 years ago by tscrim

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.

comment:3 Changed 8 years ago by ghseeli

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!

comment:4 Changed 8 years ago by tscrim

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.

Changed 8 years ago by ghseeli

comment:5 Changed 8 years ago by ghseeli

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.

comment:6 Changed 8 years ago by tscrim

How close is this to being ready review? Thanks.

comment:7 Changed 8 years ago by ghseeli

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.

comment:8 Changed 8 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from new to needs_review

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.

Last edited 8 years ago by tscrim (previous) (diff)

comment:9 follow-up: Changed 8 years ago by tscrim

  • Authors changed from ghseeli, s.r.doty, alauve to Stephen Doty, Aaron Lauve, George H. Seelinger

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.

comment:10 Changed 8 years ago by tscrim

  • Description modified (diff)

For patchbot:

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

comment:11 in reply to: ↑ 9 Changed 8 years ago by ghseeli

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.

Last edited 8 years ago by ghseeli (previous) (diff)

comment:12 Changed 8 years ago by tscrim

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

comment:13 Changed 8 years ago by ghseeli

  • Status changed from needs_review to positive_review

comment:14 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:15 Changed 7 years ago by darij

Adding a dependency needed for this to apply.

Last edited 7 years ago by darij (previous) (diff)

comment:16 Changed 7 years ago by darij

  • Dependencies set to #10630

comment:17 Changed 7 years ago by tscrim

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

comment:18 Changed 7 years ago by darij

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

comment:19 Changed 7 years ago by darij

  • Status changed from positive_review to needs_work

comment:20 Changed 7 years ago by darij

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.

comment:21 Changed 7 years ago by tscrim

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

Changed 7 years ago by tscrim

comment:22 Changed 7 years ago by tscrim

  • Status changed from needs_work to needs_review

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​

Changed 7 years ago by darij

Changed 7 years ago by darij

comment:23 Changed 7 years ago by darij

Hi Travis,

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

comment:24 Changed 7 years ago by darij

  • Status changed from needs_review to positive_review

comment:25 Changed 7 years ago by tscrim

  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Darij Grinberg

Thanks Darij.

comment:26 Changed 7 years ago by jdemeyer

  • Description modified (diff)

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

comment:27 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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: 

Changed 7 years ago by tscrim

comment:28 Changed 7 years ago by tscrim

  • Description modified (diff)
  • Status changed from needs_work to positive_review

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

Last edited 7 years ago by tscrim (previous) (diff)

comment:29 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.12.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.