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.

Depends on #24323
Depends on #25146

CC: @darijgr @alauve @tscrim @ghseeli @srdoty @mantepse @zabrocki

Component: combinatorics

Keywords: IMA coding sprint, CHAs, set partitions, diagram algebras

Author: Aaron Lauve, Mike Zabrocki, Travis Scrimshaw

Branch/Commit: 8481a77

Reviewer: Travis Scrimshaw

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

[alauve]

Branch: public/combinat/implement_orbit_basis-25162

[sagetrac-git]

Commit: 9d1b0b4

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

[sagetrac-git]

Changed commit from 9d1b0b4 to 8b9dd14

[sagetrac-git]

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

8b9dd14

Implemented new "orbit basis" for partition algebras.

[alauve]

comment:5

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]

comment:6

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.

[sagetrac-git]

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

3e71dac

moved one_basis from DiagramAlgebra, one -> id in one

[sagetrac-git]

Changed commit from 8b9dd14 to 3e71dac

[zabrocki]

comment:8

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]

comment:9

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]

comment:10

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]

comment:11

ah. that's more sensible.

[tscrim]

comment:12

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

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

[sagetrac-git]

Changed commit from 3e71dac to f64c871

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:14

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]

Changed author from Aaron Lauve, Mike Zabrocki to Aaron Lauve, Mike Zabrocki, Travis Scrimshaw

[tscrim]

comment:15

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]

comment:16

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]

comment:17

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]

comment:18

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]

comment:19

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]

comment:20

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]

comment:21

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

[alauve]

comment:71

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

[sagetrac-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

[sagetrac-git]

Changed commit from 564f36b to 136244a

[sagetrac-git]

Changed commit from 136244a to cb89aa3

[sagetrac-git]

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

cb89aa3

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

[tscrim]

comment:75

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

[vbraun]

comment:76

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

[sagetrac-git]

Changed commit from cb89aa3 to 91996a1

[sagetrac-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__.

[sagetrac-git]

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

8481a77

Adding custom `__hash__` to AbstractPartitionDiagram.

[sagetrac-git]

Changed commit from 91996a1 to 8481a77

[tscrim]

comment:79

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]

comment:81

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]

comment:82

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

[vbraun]

Changed branch from public/combinat/implement_orbit_basis-25162 to 8481a77