Skip to content

Implement the Birman-Murakami-Wenzl algebra#41513

Open
soehms wants to merge 17 commits intosagemath:developfrom
soehms:birman_murakami_wenzl
Open

Implement the Birman-Murakami-Wenzl algebra#41513
soehms wants to merge 17 commits intosagemath:developfrom
soehms:birman_murakami_wenzl

Conversation

@soehms
Copy link
Copy Markdown
Member

@soehms soehms commented Jan 25, 2026

This pull request introduces a new class that implements the Birman-Murakami-Wenzl algebra. As a tool, another new class is needed for tangles.

Additionally, I am making the following changes to the existing code:

  • Class Link: Add a new method kauffman_polynomial to obtain the Kauffman polynomial which can be directly derived from the algebra.
  • Class KnotInfo: Add a doctest that compares the result of kauffman_polynomial with that of KnotInfo.
  • Class Braid: Redirect the plot method to a refactored and enhanced version for tangles to keep maintenance centralized.
  • Class CubicHeckeAlgebra: Improved the formal_markov_trace method to support specializations of the base ring.
  • Class CubicHeckeBaseRing: Fix a bug.

Still to do (not neccessarily within this PR):

  • add representation theory using chapter 6 of EG2017 together with the CellularBasis class.
  • improve perfomance maybe by adding multiprocessing or converting the tangle module to cython code. Currently, calculating the image of a 5-strand braid takes more than a minute and for a 6-strand braid about 20 minutes. Most of the time is consumed by the method find_unlayered_crossing (because of a high number of invocations). Furthermore, these lengthy calculations are very memory-intensive. I observed a memory overflow that went uncaught. However, since there is no explicit memory allocation in the code of the branch, I assume it is an independent problem.

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.
  • I have linked a relevant issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation and checked the documentation preview.

⌛ Dependencies

@github-actions
Copy link
Copy Markdown

github-actions bot commented Jan 25, 2026

Documentation preview for this PR (built with commit 604c9a7; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

@soehms soehms force-pushed the birman_murakami_wenzl branch from 870ea0e to bef0478 Compare January 26, 2026 16:58
@soehms soehms marked this pull request as ready for review January 26, 2026 17:53
@soehms soehms requested a review from tscrim January 26, 2026 17:56
Copy link
Copy Markdown
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I will probably have more comments on the next round.

You also have some real doctest failures.

Copy link
Copy Markdown
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I will probably have more comments on the next round.

You also have some real doctest failures.

Sugg

Co-authored-by: Travis Scrimshaw <clfrngrown@aol.com>
Copy link
Copy Markdown
Member Author

@soehms soehms left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Many thanks, Travis! I will continue on your comments later!

soehms and others added 2 commits January 28, 2026 18:56
Co-authored-by: Travis Scrimshaw <clfrngrown@aol.com>
@soehms
Copy link
Copy Markdown
Member Author

soehms commented Jan 29, 2026

I will probably have more comments on the next round.

@tscrim I worked through all of your first comments, now!

You also have some real doctest failures.

These should also be fixed with one of the previous commits. Current CI failures seem to be unrelated (after the previous commit there is just one failing job).

@soehms soehms requested a review from tscrim February 25, 2026 06:31
Copy link
Copy Markdown
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I still need to go back over tangles.py, but here's some additional comments.

b = self.braid_group_algebra_preimage()

if b is None or len(b.support()) > 1:
raise NotImplementedError('Only braid images can be inverted')
Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
raise NotImplementedError('Only braid images can be inverted')
raise NotImplementedError('only braid images can be inverted')

There is also a general method for computing inverses in a finite algebra, which calling super().__invert__() should go to. (Although it is computationally intensive.)

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I will take that into account. Once we have integrated representation theory (via the cellular algebra structure) into the class, it will make sense to add this as a fallback option. Currently, however, we do not have a working to_matrix method:

File ~/devel/sage/src/sage/categories/finite_dimensional_algebras_with_basis.py:1389, in FiniteDimensionalAlgebrasWithBasis.ElementMethods.__invert__(self)
   1386             raise ValueError("cannot invert self (= %s)" % self)
   1388 e = alg.one().to_vector()
-> 1389 A = self.to_matrix()
...
File ~/devel/sage/src/sage/monoids/tangles.py:898, in KauffmanTangles.morton_wasserman_tangle(self, bd, top_bottom)
    895 from sage.misc.flatten import flatten
    897 n = self.strands()
--> 898 nb = max(bd.base_set())
    899 if n != nb:
    900     raise ValueError('Base set of Brauer diagram is incompatible with the number of strands %s' % n)

File sage/structure/element.pyx:494, in sage.structure.element.Element.__getattr__()

File sage/structure/element.pyx:507, in sage.structure.element.Element.getattr_from_category()

File sage/cpython/getattr.pyx:357, in sage.cpython.getattr.getattr_from_other_class()

AttributeError: 'KauffmanTangles_with_category.element_class' object has no attribute 'base_set'

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The to_matrix() method should be returning the result of the algebra acting on itself (i.e., as the regular representation). So this should work because multiplication of the algebra on itself must be well-defined (and you don't seem to override it). This seems like it's exposing a genuine bug.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The to_matrix() method should be returning the result of the algebra acting on itself (i.e., as the regular representation). So this should work because multiplication of the algebra on itself must be well-defined (and you don't seem to override it). This seems like it's exposing a genuine bug.

The cause likely lies in my specific basic construction. This is based on an iterated, lazy family that, in a first step, maps the Brauer diagrams to Morton-Wassermann tangles and then the tangles to the monomials of the BMW algebra:

       brauer_basis = self._brauer_algebra.basis().keys()
       basis = Family(brauer_basis, function=KT.morton_wasserman_tangle, lazy=True, name='Morton-Wasserman-Tangle')
sage: algebras.BirmanMurakamiWenzl(3).basis()
Lazy family (Term map from Lazy family (Morton-Wasserman-Tangle(i))_{i in Brauer diagrams of order 3} to Birman-Murakami-Wenzl algebra on 3 strands over Multivariate Laurent Polynomial Ring in l, m over Integer Ring(i))_{i in Lazy family (Cached version of <function KauffmanTangles.morton_wasserman_tangle at 0x7faefbc87420>(i))_{i in Brauer diagrams of order 3}}

Perhaps this is a bit too complicated. My intention was to display the basis elements as tangles, not Brauer diagrams. I would appreciate it if you could suggest a better solution.

@soehms
Copy link
Copy Markdown
Member Author

soehms commented Feb 26, 2026

@tscrim, thanks again for reviewing!

BTW: I couldn't use your suggestions this time because they weren't displayed in the Files changed tab. I don't know why. This never happened before.

@soehms soehms requested a review from tscrim February 26, 2026 21:54
@tscrim
Copy link
Copy Markdown
Collaborator

tscrim commented Feb 27, 2026

@tscrim, thanks again for reviewing!

BTW: I couldn't use your suggestions this time because they weren't displayed in the Files changed tab. I don't know why. This never happened before.

I gave too many comments for GH to decide to display them all. So it is hiding many of them.

For me at least, GH it telling me on the "files changed" tab

To view the remaining comments, open the comments side panel

which is located next to the "submit review" button.

Copy link
Copy Markdown
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This might be the last batch hopefully.

I'm still confused about the necessity of the cardinality for the Kauffmann tangles (I could see the list, but even still, that seems strange). I should investigate this properly and fix it...

Comment on lines +159 to +162
from sage.combinat.diagram_algebras import BrauerAlgebra
from sage.rings.polynomial.polynomial_ring import polygen
from sage.rings.integer_ring import ZZ
BA = BrauerAlgebra(P._nstrands, polygen(ZZ))
Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think it would be better to store this in the parent as a @lazy_attribute.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done!

self._mwt_names = {} # support for the names of the BMW-algebra basis
self._shared_memory = {} # shared cache for sign independent results of methods

def __repr__(self):
Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
def __repr__(self):
def _repr_(self):

Do you also want a _latex_ method? Not necessary though.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It is difficult to find a consistent convention in the literature. In the reference by Morton and Wasserman, the set of n-m tangles is denoted as {\cal U}_n^m. Elsewhere, the monoidal category of tangles is denoted as {\cal T}, so these monoids would be denoted as Hom_{\cal T}(n, n). Which convention would you prefer?

Comment on lines +996 to +999
- start -- integer, position on the top or bottom line
(for bottom inline pairs) of the connector
- end -- integer, position on the bottom or top line
(for top inline pairs) of the connector
Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
- start -- integer, position on the top or bottom line
(for bottom inline pairs) of the connector
- end -- integer, position on the bottom or top line
(for top inline pairs) of the connector
- ``start`` -- integer, position on the top or bottom line
(for bottom inline pairs) of the connector
- ``end`` -- integer, position on the bottom or top line
(for top inline pairs) of the connector

but perhaps better at the class level docstring?

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done!

Co-authored-by: Travis Scrimshaw <clfrngrown@aol.com>
@soehms
Copy link
Copy Markdown
Member Author

soehms commented Mar 3, 2026

which is located next to the "submit review" button.

Yes, I tried that too. But I could only find older comments. It was probably due to a poor internet connection on the bus. However, this time it worked again.

@soehms soehms requested a review from tscrim March 3, 2026 18:11
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants