Implement orbit basis for partition algebras

[alauve]

Aside from the natural diagram basis for the Partition Algebra, there is an "orbit basis" which carries representation-theoretic meaning. At present, the Partition Algebra (indeed all diagram algebras) have only the diagram basis implemented. This ticket will implement the orbit basis following the model of PBWBasisOfFreeAlgebra in sage.algebras.free_algebra.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​179ce29	Fixing options for Brauer diagrams and algebra.
​64901e3	additions to the documentation to explain the compact notation
​1d651d5	added element classes specfic to subclasses, methods to element classes, factor set partition methods
​bcad2c4	cleanup advice from Travis, added missing doctests, restored previous partition algebra iterator
​737d383	doc test +1/2 iterators, move max_block_size, remove unused import statement
​783bca5	max takes an iterator
​d0c9fbd	move (restore) is_planar as a standalone function
​15aa908	added diagram algebras to the list of Subsets and set partitions doc, moved is_planar
​9d1b0b4	Began implementation of orbit basis for partition algebra.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8b9dd14

Implemented new "orbit basis" for partition algebras.

[alauve]

I should mention that I did quite a bit more than implement the orbit basis. I also worked towards implmenting coercion between different instances of SubPartitionAlgebra? classes.

e.g., one would like the following code to work, and it seems like now it does:

sage: R.<q> = QQ[]
sage: S2 = SymmetricGroupAlgebra(ZZ, 2)
sage: B2 = BrauerAlgebra(2, q, R)
sage: P = PartitionAlgebra(4, q, R)
sage: P(S2.an_element())
3*P{{-4, 4}, {-3, 3}, {-2, 1}, {-1, 2}} + P{{-4, 4}, {-3, 3}, {-2, 2}, {-1, 1}}
sage: P(B2.an_element())
3*P{{-4, 4}, {-3, 3}, {-2, -1}, {1, 2}} + 2*P{{-4, 4}, {-3, 3}, {-2, 1}, {-1, 2}} + 2*P{{-4, 4}, {-3, 3}, {-2, 2}, {-1, 1}}

However, I don't understand why coercion from the base ring doesn't work:

sage: R.<q> = QQ[]
sage: O2 = PartitionAlgebra(2, q, R).orbit_basis()
sage: P2 = PartitionAlgebra(2, q, R)
sage: O2(P2(13))
13*OP{{-2, -1, 1, 2}} + 13*OP{{-2, 2}, {-1, 1}}
sage: O2(13)  # this is wrong!!
13*OP{{-2, 2}, {-1, 1}}

(Mike should also check that multiplication in the Orbit basis performs as expected.)

[tscrim]

My guess is because DiagramAlgebra.one_basis() is defined for the orbit basis. IIRC, the conversion (technically, what you are doing is conversion) for scalars first tries to see if one_basis() is defined, and if so, then constructs an element as the term (self.one_basis(), scalar). This is done for speed reasons (it is faster than acting by multiplication). You probably need to add another ABC for the diagram algebra bases where 1 is not a basis element.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3e71dac

moved one_basis from DiagramAlgebra, one -> id in one

[zabrocki]

The problem was that one_basis was defined in DiagramAlgebra and you didn't want that method to exist in the orbit basis. I don't think it is right for unital_algebra to insist that the one of the basis is a single monomial.

[alauve]

Great, thanks! (and I agree that unital_algebra should not assume that the unit is a single monomial.)

Will you be making other changes soon? I can tackle the doctest failures, but I think it's best to wait for zabrocki/tscrim/other to take a deeper look under the hood first.

[tscrim]

Replying to zabrocki:

I don't think it is right for unital_algebra to insist that the one of the basis is a single monomial.

That is incorrect, unital algebras does not force you to implement one_basis. If you have implemented one_basis, then it has every right to assume 1 is a basis element. Otherwise you should just implement one().

[alauve]

ah. that's more sensible.

[tscrim]

I am currently doing a bunch of refactoring on this ticket (including merging in the fix on #24323).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​aefa456	Merge branch 'public/combinat/implement_orbit_basis-25162' of git://trac.sagemath.org/sage into public/combinat/implement_orbit_basis-25162
​3448e98	Merge branch 'public/combinat/fix_brauer_algebra_options-24323' of git://trac.sagemath.org/sage into public/combinat/fix_brauer_algebra_options-24323
​9f484d4	Fix failing doctest.
​52cf619	Merge branch 'public/combinat/fix_brauer_algebra_options-24323' into public/combinat/implement_orbit_basis-25162
​f64c871	Refactoring and fixing bugs and various minor issues.

[tscrim]

Okay, I have finished my refactoring and made the code as clean as I can make it. All doctests now pass and there is 100% coverage. I have also reviewed the code you wrote.

[tscrim]

Some comments:

• Never use a base except:; it catches far too much (including things like interrupts, or so I've been told).
• The module_morphism is primarily expecting something that takes a basis element as input.
• I have never really liked the (user-level) idiom of parent.to_foo(x), so I removed it. I am good with it being there to avoid reimplementation of boilerplate code, but beyond that, I think only the method at the element level should be exposed to the user.
• I fixed the category issue of PropogatingIdeal as effectively a by-product of my refactoring.

There is likely more to be done to improve this file, but this is what is sufficient for the ticket at hand.

[alauve]

Travis, Your changes look good to me. (Your comments are duly noted.)

• regarding your third comment...

You removed to_orbit_basis from parent PartitionAlgebra but left to_diagram_basis within parent OrbitBasis

• One mathematical quibble/query...

The orbit basis doesn't exist for many subalgebras of the partition algebra. Well, there could be something best known as 'orbit basis' for each subalgebra, but the formula for converting to diagram basis will not be the same as what appears around line 2339.

        PD = PartitionDiagrams(self._alg._k)
        one = self.base_ring().one()
        return self._from_dict({d: one for d in PD(diag).coarsenings()},
                               coerce=False, remove_zeros=False)

I'm not sure what's the best way to address this, but I'd be inclined to keep PartitionAlgebra in the name.

• "Basis" versus "Algebra"...

The new name also doesn't have the word 'algebra' in it, which may be more likely to lead to confusion. Likewise, implementing DiagramBasis seems like a good idea, though I'm not sure about the name.

[tscrim]

Replying to alauve:

• regarding your third comment... You removed to_orbit_basis from parent PartitionAlgebra but left to_diagram_basis within parent OrbitBasis

That was one of the first things I touched and a remnant of when I thought it could be necessary/useful. It can be removed.

• One mathematical quibble/query... The orbit basis doesn't exist for many subalgebras of the partition algebra. Well, there could be something best known as 'orbit basis' for each subalgebra, but the formula for converting to diagram basis will not be the same as what appears around line 2339.

        PD = PartitionDiagrams(self._alg._k)
        one = self.base_ring().one()
        return self._from_dict({d: one for d in PD(diag).coarsenings()},
                               coerce=False, remove_zeros=False)
  

  I'm not sure what's the best way to address this, but I'd be inclined to keep PartitionAlgebra in the name.

I don't really care since it is not anything (directly) exposed to the user. I think it is overly verbose to have it in the class name (the docstring differentiates IMO), but feel free to change it back.

(I think this file has gotten so big it is likely more manageable to be separated out into smaller pieces. In which case, sage.combinat.partition_algebra.OrbitBasis removes ambiguity, but that is a tangential.)

• "Basis" versus "Algebra"... The new name also doesn't have the word 'algebra' in it, which may be more likely to lead to confusion. Likewise, implementing DiagramBasis seems like a good idea, though I'm not sure about the name.

These are all implemented as algebras in a particular basis. so IMO, there is no distinction between an algebra and a basis. I highly doubt this will cause any serious confusion/problems once someone reads-the-code (if they are looking at these things, they should already be doing that).

[zabrocki]

It seems really slow. We might have to implement the multiplication directly on the orbit basis.

There seems to be something wrong here:

sage: O = PartitionAlgebra(2,x).orbit_basis()
sage: O[[1,-1],[2],[-2]]
OP{{-2}, {-1, 1}, {2}}
sage: O[[1,-1,2,-2]]
TypeError: 'sage.rings.integer.Integer' object is not iterable

[alauve]

Hmm. I forgot about this use. This is handled in 'get item'? I may have to give up on idea of allowing user to enter a permutation as a list

Regarding speed, would it be bad practice to make coarse bonds a cached function? (Product in orbit basis is not known, right?)

[zabrocki]

The product on the orbit basis is known. I'll have to find a reference/derivation and make sure that it is faster. We might want to cache coarsenings. It seems like if you are doing even one change of basis for a given k it will be doing repeating the same calculations.

from comment:17

I think this file has gotten so big it is likely more manageable to be separated out into smaller pieces.

+1 . Something to be done at a later date, plus improve the documentation.

[zabrocki]

By the way, the commit from comment:2 deleted the changes from #25146

[alauve]

Replying to zabrocki:

There seems to be something wrong here:

sage: O = PartitionAlgebra(2,x).orbit_basis()
sage: O[[1,-1],[2],[-2]]
OP{{-2}, {-1, 1}, {2}}
sage: O[[1,-1,2,-2]]
TypeError: 'sage.rings.integer.Integer' object is not iterable

This bug is present even in development branch for PartitionAlgebra. Should perhaps be pushed to a separate ticket?

[zabrocki]

I found a reference for the product on the orbit basis. See Lemma 4.3 in ​https://arxiv.org/pdf/1707.01410.pdf . I checked for example that Example 4.5 (2) agrees:

sage: P = PartitionAlgebra(4,x);O = P.orbit_basis()
sage: O[[1],[-1],[2,3],[4,-2],[-3,-4]]*O[[1],[2,-2],[3,4],[-1,-3],[-4]]
(x^2-11*x+30)*OP{{-4}, {-3, -1}, {-2, 4}, {1}, {2, 3}} + (x^2-9*x+20)*OP{{-4}, {-3, -1, 1}, {-2, 4}, {2, 3}} + (x^2-9*x+20)*OP{{-4}, {-3, -1, 2, 3}, {-2, 4}, {1}} + (x^2-9*x+20)*OP{{-4, 1}, {-3, -1}, {-2, 4}, {2, 3}} + (x^2-7*x+12)*OP{{-4, 1}, {-3, -1, 2, 3}, {-2, 4}} + (x^2-9*x+20)*OP{{-4, 2, 3}, {-3, -1}, {-2, 4}, {1}} + (x^2-7*x+12)*OP{{-4, 2, 3}, {-3, -1, 1}, {-2, 4}}
sage: %timeit O[[1],[-1],[2,3],[4,-2],[-3,-4]]*O[[1],[2,-2],[3,4],[-1,-3],[-4]]
1 loop, best of 3: 3.82 s per loop

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b9197b9

fix element constructor when set partition is a single part

[zabrocki]

That fix is quite easy so I don't think it should be a separate ticket and we should not be adding more bases and propagating this error. Let me point out a minor problem that perhaps should be on a separate ticket:

sage: P = PartitionAlgebra(4,x)
sage: P[[1,-1,2,-2]]
P{{-2, -1, 1, 2}}

I feel like we should element constructor for PartitionDiagrams(k) or check that the missing values are not there and raise an error. I think that the shorthand notation for blocks being left out is that they are all of size 1.

P{{-4}, {-3}, {-2, -1, 1, 2}, {3}, {4}}

[alauve]

Replying to zabrocki:

Let me point out a minor problem that perhaps should be on a separate ticket:

sage: P = PartitionAlgebra(4,x)
sage: P[[1,-1,2,-2]]
P{{-2, -1, 1, 2}}

Hmm. This is the sort of thing I've tried to address with my work. See how it works with this alternate construction:

sage: P = PartitionAlgebra(4,x)
sage: P([[1,-1,2,-2]])
P{{-4, 4}, {-3, 3}, {-2, -1, 1, 2}}

sage: P([[-1,-2],[1],[2]])
P{{-4, 4}, {-3, 3}, {-2, -1}, {1}, {2}}

So... in the __getitem__ method, perhaps one could push to ._diag_to_Blst to solve the problem?

.

I feel like we should element constructor for PartitionDiagrams(k) or check that the missing values are not there and raise an error. I think that the shorthand notation for blocks being left out is that they are all of size 1.

P{{-4}, {-3}, {-2, -1, 1, 2}, {3}, {4}}

I would prefer that missing nodes come in as pairs, if possible, instead of adding singleton blocks, because this is how smaller partition algebras would embed into larger ones. I have tried to allow for singleton blocks in ._diag_to_Blst as well: i you want to add things as singletons, you can add a stray unpaired singleton. This is not documented well:

sage: P([[1,-1,2,-2]])
P{{-4, 4}, {-3, 3}, {-2, -1, 1, 2}}

sage: P([[1,-1,2,-2],[4]])
P{{-4}, {-3}, {-2, -1, 1, 2}, {3}, {4}}

sage: P([[-1,-2],[1],[2,3]])
P{{-4}, {-3}, {-2, -1}, {1}, {2, 3}, {4}}

[zabrocki]

I'm not even sure how it is making those decisions based on your examples. I would have paired the 4 and -4 in the last one. Can you explain what it is doing?

I understand the reason for wanting to pair up for the Brauer algebra, but I don't know if that is particularly natural for the partition algebra or not. The problem arises if there are an odd number of vertices that are unpaired or if there are not the same number of positive as negative.

[alauve]

The pairing that it tries to do is of the form (+i,-i) for all omitted nodes. If the omitted nodes cannot be so paired, then it brings in everything nodes as singletons.

(So the question about an even or odd number of omitted nodes doesn't quite enter into the story.) I note that this even works for putting P_n into P_{n+1/2} story, where one insists that (n+1) and -(n+1) always appear in the same block.

Here is the code, roughly:

        nodes = flatten(map(list, d))
        assert max(nodes) <= self._k
        if all([-i in nodes for i in nodes]):
            d = to_set_partition(d, self._k, through_strands=True)
        else:
            d = to_set_partition(d, self._k)
        return self[self._base_diagrams(d)]

Where, the optional argument 'through_strands' for the function to_set_partition brings omitted nodes in as pairs (i,-i). The default value is False.

[alauve]

I have a few minutes now. Let me implement the product in the orbit basis.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0d8e723

began implementing product in orbit basis... currently as _product_on_basis. Ran into a snag, and will not get back to it before Monday. Mike or Travis should feel free to fix it before then.

[tscrim]

FYI - It is much faster to the partition algebra defined over, e.g., a polynomial ring rather than the symbolic ring.

When looking at the multiplication-by-coercion timings with %prun, about 1/3 of the time was spent constructing Set objects, 1/3 of the time (not necessarily disjoint) was spent in coarsenings, and at most 1/3 was spent in the other helper functions of diagram_algebras.py. However, the direct version takes almost no time. I will push momentarily a corrected version.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6bb56c5

Rewrote implementation of direct multiplication in orbit basis.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​cc16320

Rewrote implementation of direct multiplication in orbit basis.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​52c1fbf

Rewrote implementation of direct multiplication in orbit basis.

[alauve]

Thanks for catching my math mistake, Travis. I realized I miscoded the formula as I was walking to the train.

This wasn't the snag I hit, though. For some reason I couldn't even compose diagrams:

sage: P = PartitionAlgebra(3,x); PD = P.basis().keys()
sage: d1 = PD.random_element(); d2 = PD.random_element()
sage: d1.compose(d2)

the last line throwing some TypeError::

TypeError                                 Traceback (most recent call last)
<ipython-input-75-c92a56b0f000> in <module>()
----> 1 d1.compose(d2)

/Applications/sage/src/sage/combinat/diagram_algebras.py in compose(self, other)
    360         """
    361         (composite_diagram, loops_removed) = set_partition_composition(self._base_diagram, other._base_diagram)
--> 362         return (self.__class__(self.parent(), composite_diagram), loops_removed)
    363 
    364     def propagating_number(self):

/Applications/sage/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1672)()
    331         else:
    332             # Fast version of type.__call__(cls, *args, **kwds)
--> 333             return (<PyTypeObject*>type).tp_call(cls, args, kwds)
    334 
    335     def __get__(cls, instance, owner):

/Applications/sage/src/sage/combinat/diagram_algebras.py in __init__(self, parent, d)
    240         """
    241         self._base_diagram = tuple(sorted(tuple(sorted(i)) for i in d))
--> 242         super(AbstractPartitionDiagram, self).__init__(parent, self._base_diagram)
    243 
    244     def check(self):

TypeError: super(type, obj): obj must be an instance or subtype of type

It seems to work now, so I don't know what classes I accidentally made d1 and d2. I'll play around a bit more to see if I can reproduce the error.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5aac262

1. Modified getitem to use the same conversion scheme as element_constructor.

[zabrocki]

What do we do about #25146 ? This branch is (partially) merged, but Aaron deleted those changes in 9d1b0b4

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​937226f

Cleaned up old code and comments

[alauve]

Replying to zabrocki:

What do we do about #25146 ? This branch is (partially) merged, but Aaron deleted those changes in 9d1b0b4

Well, since I caused the problem, I guess I should try to solve it. Will take a look now to see how easy are they to merge "by hand".

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0aa6023

Merged relevant changes from 9d1b0b4 into :trac:`25162`, which were removed in commit 9d1b0b4.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​877a1b0	Merge branch 'public/cleanup_diagrams-25146' of git://trac.sagemath.org/sage into public/cleanup_diagrams-25146
​dd77d09	Better test for AbstractPartitionDiagrams.__init__ and some cleanup.
​cef9946	Merge branch 'public/cleanup_diagrams-25146' into public/combinat/implement_orbit_basis-25162
​2850224	Getting rid of duplicate code and streamlining implementation.
​f677630	Simplifying code, trivial change of iteration order.
​5e84063	Better __classcall_private__ implementations.
​9cc4e1b	Merge branch 'public/cleanup_diagrams-25146' into public/combinat/implement_orbit_basis-25162
​00dea1a	Using frozenset instead of Set for the base set; renamed to _set for consistency with SetPartitions_set.
​053aac4	A little more cleanup.

[tscrim]

Here is an updated branch with my changes from #25146, as well as fixing what should be the only docstring issue, bring to full doctest coverage, and some misc fixes.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​51b1a3a	orbit basis more appropriate than Orbit basis in doc
​3956001	add documentation for the definition of the orbit basis

[zabrocki]

I want to question the use of O+prefix for the orbit basis and propose that it be switched just to O or o. Is the double letter really necessary here? The expressions are already extremely long because the default display of set partitions has so many braces. I would prefer to have the default prefix be more compact. I computed an example the other day and I thought the OP prefix was heavy notation (but hey, the code worked as promised and has been very helpful!).

I also found it was misleading when I was looking at the to_orbit_basis in the SubPartitionAlgebra because then it generated a basis indexed by OB and I thought that this poorly indicated that this was not the orbit basis of the Brauer algebra, but instead the orbit basis of the partition algebra (I actually also find this strange behavior for ambient and lift but these are not new to this ticket).

Either way, I would just as soon have the display prefix for the basis be simply O. Are there objections to me changing it?

[alauve]

O is fine by me.

Yes, the lift functionality is strange. I don't think it should keep the same letter as prefix, after lift, as it had before. But I decided not to mess with it. We could perhaps remove this method, but I thought there could be some use for it. Shall I work on improving the surrounding documentation?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e77512d

change OP -> O, correct failing doctest

[chapoton]

pyflakes says

src/sage/combinat/diagram_algebras.py:28: 'sage.categories.algebras.Algebras' imported but unused
src/sage/combinat/diagram_algebras.py:2801: local variable 'k' is assigned to but never used

[zabrocki]

I think that things left to do here are mostly improvements in the documentation and this embedding thing we started discussing in comment:25 . Before I make any changes I just want to review what should be the right thing to do. I think that P_k -> P_{k+1/2} -> P_{k+1} should be the same as P_{k} -> P_{k+1}. In which case it is appropriate (as you say) to connect k+1 and -k-1 together.

sage: P3 = PartitionAlgebra(3,x,prefix='P3'); P4 = PartitionAlgebra(4,x,prefix='P4')
sage: P2(P[[1,-2,2,-1]])
P4{{-4, 4}, {-3, 3}, {-2, -1, 1, 2}}

but

sage: P3 = PartitionAlgebra(3,x); Px = PartitionAlgebra(7/2,x,prefix='P3.5')
sage: Px(P3[[1,-2,2,-1]])
ValueError: {{-3, 3}, {-2, -1, 1, 2}} does not represent two rows of vertices of order 7/2
sage: Px(P4[[1,-2,2,-1]])
P3.5{{-4, 4}, {-3, 3}, {-2, -1, 1, 2}}

so I think that there is something wrong (probably minor).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​10fa992

pyflakes edits

[alauve]

Replying to zabrocki:

I think that things left to do here are mostly improvements in the documentation and this embedding thing we started discussing in comment:25 . Before I make any changes I just want to review what should be the right thing to do. I think that P_k -> P_{k+1/2} -> P_{k+1} should be the same as P_{k} -> P_{k+1}. In which case it is appropriate (as you say) to connect k+1 and -k-1 together.

Yes, this.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1ccf822

change to_set_partition

[zabrocki]

See if you agree with this behavior. I didn't understand what it was doing before. There was a test pairing_is_possible which didn't always seem like the right thing to do. Before:

sage: P = PartitionAlgebra(3,x)
sage: P[[1]]
P{{-3}, {-2}, {-1}, {1}, {2}, {3}}

but I just made it pair the missing {i,-i} strands if it can. Now:

sage: P = PartitionAlgebra(3,x)
sage: P[[1]]
P{{-3, 3}, {-2, 2}, {-1}, {1}}

[alauve]

Replying to zabrocki:

See if you agree with this behavior. I didn't understand what it was doing before. There was a test pairing_is_possible which didn't always seem like the right thing to do. Before:

sage: P = PartitionAlgebra(3,x)
sage: P[[1]]
P{{-3}, {-2}, {-1}, {1}, {2}, {3}}

but I just made it pair the missing {i,-i} strands if it can. Now:

sage: P = PartitionAlgebra(3,x)
sage: P[[1]]
P{{-3, 3}, {-2, 2}, {-1}, {1}}

My idea was to preserve the ability to bring things in with singletons. Try

P[[1],[-1]]

[zabrocki]

My idea was to preserve the ability to bring things in with singletons. Try

P[[1],[-1]]

I did

sage: P = PartitionAlgebra(3,x)
sage: P[[1],[-1]]
P{{-3, 3}, {-2, 2}, {-1}, {1}}

This is what I expected. Is that not what you thought? Maybe I don't understand "bring things in with singletons."

[alauve]

It is different from

P[[1]]

which is the one that brings things in as singletons. The idea was if your excluded nodes don't pair up, then bring the rest in as singletons. If you want the excluded nodes to come in as pairs (through strands), then exclude them in pairs.

[zabrocki]

This is what I see now (and this is what I think should be):

sage: P[[1]]==P[[1],[-1]]
True

The idea was if your excluded nodes don't pair up, then bring the rest in as singletons. If you want the excluded nodes to come in as pairs (through strands), then exclude them in pairs.

The problem to me is that is not well documented and it is complex. I think it should follow a simple and consistent rule : "pair {i,-i} if they are not listed. Do this as much as possible and then fill in singletons."

What it was doing before was raising an error when I computed P[[1]] for P=PartitionAlgebra(5/2,x).

[alauve]

That's fine with me. I was trying to preserve behavior as I found it as best as possible. But improving the documentation will not improve the situation much. It is complex.

[tscrim]

Note that 3/2 == 1 in Python2 (with from __future__ import division/Python3, it becomes a floating point). IMO, if you really want to add 3/2, do it using QQ and then take the corresponding floor. Although a better approach to add 1 and then take ceil.

Also, if you want to change the "default" output, you can add the global options change to your ~/.sage/sage.init (or wherever your .sage directory is). Commands in this file are run on startup. Although for this to work, we would need a ticket to add a global option to SetPartition or to PartitionAlgebra.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f0e1a3c

additions to documentation, int(k+3/2)->ceil(k+1)

[zabrocki]

I agree that a global options is in order for SetPartition and PartitionAlgebra. A compact notation would be a nice feature. I think that there is a lot of work to do to implement the some results of Halverson-Ram (e.g. Jucys-Murphy elements, class type of a diagram, various flavors of generators, etc.). Plus reorganizing some of the code because the file has become quite huge. These are all items for followup tickets.

One of the nice features of the diagram algebra code is the latex of an expression. [BH2017] differentiates the latex of the diagram basis from the orbit basis by filled nodes so I added this for the latex of the orbit basis (although it switches BH convention in that orbit basis has filled nodes and diagram basis has not filled nodes).

Although a better approach to add 1 and then take ceil.

I went with this approach (in fact, I had it before).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a0cb892

differentiate the latex of the orbit and diagram bases

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1257b51

doctest for diagram_basis, o->O, d->D, remove TODO

[zabrocki]

I deleted the "TODO: find a better name?". elementary_symmetric is a fine name and I would not recommend deprecating it now if there was one (and one can always add an alias if a better name comes along).

I added a doctest for diagram_algebra because the ones that were there I think must have been copy-pasted.

Otherwise I think this is ready to go.

[tscrim]

I agree. Thank you.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​80a670e

deleted superfluous function; updated authors

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​564f36b

added another author

[alauve]

Travis,

• The function I deleted was one I added in an earlier revision within this branch. After Mike's changes, it's no longer needed. So I deleted it.

• Not quite sure if the work I did is worthy of mention. Please feel free to yank the new line in the header.

• It looks like all the changes from #25146 have been mixed in here. That ticket seems stable now. There are some differences, of course, but nothing that should affect a merge. Should this be double-checked before setting to positive review?

[tscrim]

All of the changes from #25146 have been merged in here.

[alauve]

Okay. If there's no objection, I shall move ticket status back to "positive review".

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​e71d82a	Merge branch 'public/25146' of git://trac.sagemath.org/sage into public/25146
​136244a	Merge branch 'public/combinat/implement_orbit_basis-25162' of git://trac.sagemath.org/sage into public/combinat/implement_orbit_basis-25162

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​cb89aa3

Marking one test as long (> 2s on my laptop).

[tscrim]

Trivial rebase and marked one test as long. I'm allowing myself to set it back to a positive review.

[vbraun]

Fails on 32-bit:

File "src/sage/combinat/diagram_algebras.py", line 2228, in sage.combinat.diagram_algebras.PartitionAlgebra._element_constructor_
Failed example:
    A(S.an_element())
Expected:
    P{{-3, 3}, {-2, 2}, {-1, 1}} + P{{-3, 1}, {-2, 3}, {-1, 2}} + 3*P{{-3, 3}, {-2, 1}, {-1, 2}}
     + 2*P{{-3, 2}, {-2, 3}, {-1, 1}}
Got:
    P{{-3, 1}, {-2, 3}, {-1, 2}} + 3*P{{-3, 3}, {-2, 1}, {-1, 2}} + P{{-3, 3}, {-2, 2}, {-1, 1}} + 2*P{{-3, 2}, {-2, 3}, {-1, 1}}
**********************************************************************
File "src/sage/combinat/diagram_algebras.py", line 2234, in sage.combinat.diagram_algebras.PartitionAlgebra._element_constructor_
Failed example:
    A(B.an_element())
Expected:
    2*P{{-3, 1}, {-2, 2}, {-1, 3}} + 2*P{{-3, 1}, {-2, 3}, {-1, 2}}
     + 3*P{{-3, 1}, {-2, -1}, {2, 3}}
Got:
    2*P{{-3, 1}, {-2, 3}, {-1, 2}} + 2*P{{-3, 1}, {-2, 2}, {-1, 3}} + 3*P{{-3, 1}, {-2, -1}, {2, 3}}
**********************************************************************
File "src/sage/combinat/diagram_algebras.py", line 2371, in sage.combinat.diagram_algebras.PartitionAlgebra._coerce_map_from_
Failed example:
    A._coerce_map_from_(O3)(elt)
Expected:
    3*P{{-4, 4}, {-3, -2, -1, 1, 3}, {2}} - 3*P{{-4, 4}, {-3, -2, -1, 1, 2, 3}}
     + 2*P{{-4, 4}, {-3, -2, -1, 2, 3}, {1}}
Got:
    -3*P{{-4, 4}, {-3, -2, -1, 1, 2, 3}} + 2*P{{-4, 4}, {-3, -2, -1, 2, 3}, {1}} + 3*P{{-4, 4}, {-3, -2, -1, 1, 3}, {2}}
**********************************************************************
File "src/sage/combinat/diagram_algebras.py", line 2776, in sage.combinat.diagram_algebras.OrbitBasis.product_on_basis
Failed example:
    O[[1,-1],[2,-2],[3],[4,-3],[-4]] * O[[1,-2],[2],[3,-1],[4],[-3],[-4]]
Expected:
    (x-6)*O{{-4}, {-3}, {-2, 1}, {-1, 4}, {2}, {3}}
     + (x-5)*O{{-4}, {-3, 3}, {-2, 1}, {-1, 4}, {2}}
     + (x-5)*O{{-4, 3}, {-3}, {-2, 1}, {-1, 4}, {2}}
Got:
    (x-6)*O{{-4}, {-3}, {-2, 1}, {-1, 4}, {2}, {3}} + (x-5)*O{{-4, 3}, {-3}, {-2, 1}, {-1, 4}, {2}} + (x-5)*O{{-4}, {-3, 3}, {-2, 1}, {-1, 4}, {2}}
**********************************************************************
3 items had failures:
   1 of  29 in sage.combinat.diagram_algebras.OrbitBasis.product_on_basis
   1 of  17 in sage.combinat.diagram_algebras.PartitionAlgebra._coerce_map_from_
   2 of  39 in sage.combinat.diagram_algebras.PartitionAlgebra._element_constructor_
    [781 tests, 4 failures, 19.54 s]
----------------------------------------------------------------------
sage -t --long src/sage/combinat/diagram_algebras.py  # 4 doctests failed
----------------------------------------------------------------------

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​fbab6bb	Merge branch 'public/combinat/implement_orbit_basis-25162' of git://trac.sagemath.org/sage into public/combinat/implement_orbit_basis-25162
​91996a1	Diagrams now do checks with __lt__.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8481a77

Adding custom __hash__ to AbstractPartitionDiagram.

[tscrim]

So it turns out AFAIK that no < comparison was returning True for the diagrams. This was because the abstract __lt__ check was checking the subclass SetPartition rather than AbstractSetPartition. However, I implemented a custom __lt__ to take advantage of the _base_diagram. To be honest, I am surprised we were not seeing (more) machine-specific output-order doctest failures.

I also implemented a custom hash to use _base_diagram for better speed and better compatibility with ==.

[zabrocki]

All tests pass on my machine, but so did the previous version. If you are confident that it fixes the problem, I'll say positive review.

[tscrim]

Yes, it is doing the comparison by the lex ordering of AbstractSetPartition.