Methods for evaluating the Jones representations of braids and the Jones polynomials of the closure

[fuglede....@gmail.com]

Hey sage-devel

In work with Egsgaard, I ended up needing an implementation of the Jones representations of braid groups and figured it made sense to do it in sage. While interesting in their own right, they also allow for direct calculation of the Jones polynomials of the trace closures of the braids, and I figured that since sage is currently rather low on quantum topology (and knot theory in general), that adding this to the base could be useful in general.

The development guide suggests suggesting changes here before on trac, so here you go. The source code is currently available here:
    https://github.com/fuglede/jones-representation/blob/master/curverep.sage

- Søren

[Amit Jamadagni]

Hello Soren,
        Thanks for sharing the work. But we do have been working on Knot Theory and here is the ticket
Ticket : http://trac.sagemath.org/ticket/17030, which is currently under review. It would be helpful if you compare the missing features as the work on calculations of Jones polynomial has been included. Also from the source, as far as I understand the representations are mainly Braid Group, but we do have supported other representations such as oriented gauss code and also planar diagram. I guess you could directly contribute to the ticket, if something is missing. 

Thanks,
Amit.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[fuglede....@gmail.com]

Hi Amit

Thanks for the reference; good to know that stuff is happening in that regard.

And yes, everything here is related to the braid group. Even though this would create some overlap, perhaps it could be of use to have both algorithms: using braid group representations, for a fixed number of strands, the evaluation of the Jones polynomial of the trace closures becomes polynomial in the number of crossings (as only matrix multiplication is involved). From a quick look at ticket #17030, that's not the case for the existing implementation which appears to implement Kauffman's O(2^{O(#crossings)}) algorithm (please correct me if I'm wrong).

- Søren

[Amit Jamadagni]

Hello Soren,
        Yeah, we have used the Kauffman's bracket decomposition for the construction of Jones polynomial. I am not sure (may also be not the right person to comment) on whether we could include this in the current ticket. I guess may be we could have it in the groups/braid.py as we have an implementation of Alexander polynomial which is also implemented in the ticket #17030.

Thanks,
Amit.

[fuglede....@gmail.com]

Ah, right, with the Alexander polynomial redundancy, I don't need to argue that having two implementations of the Jones polynomial makes sense.

And yeah, this particular implementation was written with Braid.py in mind specifically (following the conventions that are already in place in there).

- Søren

[fuglede....@gmail.com]

In fact, when matching the return values of Link.jones_polynomial() with the one I posted, I ran into some problems for sufficiently trivial links:

sage: B = BraidGroup(2)
sage: b = B([])
sage: L = Link(b)
sage: L.jones_polynomial()
...
IndexError: list index out of range

Likewise, it does not appear to give the expected results when it does give results:

sage: B = BraidGroup(8)
sage: b = B([1])
sage: L = Link(b)
sage: L.jones_polynomial()
1
sage: b.jones_polynomial()
A^12 + 6*A^8 + 15*A^4 + 15/A^4 + 6/A^8 + 1/A^12 + 20

This was obtained using the version of link.py in 04facf8.

- Søren

[mmarco]

I wouldsay that the problems in your  examples has to do with the existence of completely isolated trivial components. Since we make the computation with the lists of crossings, all components with no crossings involved are ignored. Besides, the first example has no crossings at all (which makes the method to fail).

So maybe we should try to take care of these cases in our data structures. 

If you are interested in knot theory in Sage, please help us review the ticket. There are some people already looking at the code, but they would like someone that knows the theory behind it to review the mathematical correctness.

Btw, in the long run, i would like to include a library[1] to compute the homfly polynomial. It is much faster than our actual methods for Alexander and Jones polynomials. But in the meantime, i think we should focus on having the basics merged.

[1]http://trac.sagemath.org/ticket/18047

[mmarco]

Oh, i forgot to say: please open a ticket with your code added to the braid class. It is definitely a nice addition. I would be happy to review it. write your methods inside the class definition, and consider which ones should be public and which ones should be hidden to the user.

[fuglede....@gmail.com]

Having a libhomfly wrapper would certainly be nice. More generally, the Mathematica KnotTheory` package allows, iirc, for the input of a general R-matrix and spits out braid group representations. Or maybe it's just for the ones that come from quantum groups of simple Lie algebras. It would be great to have that ported to sage as well.

Nonetheless, I think there could still be some value in having a Kauffman bracket implementation of the Jones polynomial such as yours: while the braid group representation algorithm is certainly more effective in particular cases, it is not clear to me that it always is. In particular, what I wrote tends to be rather slow for closures of long words in 10 or more strands. I actually noticed the incorrect outputs in #17030 when I was about to benchmark the algorithm.

Also on my wish list is a wrapper for Toby Hall's implementation of Bestvina–Handel for braids, but that's a different issue entirely.

[fuglede....@gmail.com]

Alright, I'll do that soon. The code is set up to be copy-pasted more or less directly; in particular I think all of the functions could be useful as methods but that's a matter of opinion.

[mmarco]

I also spent some time trying to figure out how to implement Bestvina -Handel algorithm. But i am not really an expert on that, so i desisted after some time. If you want to work on that, i would definitely try to help.

I am so happy to have a braid/knot theory specialist on board.

[fuglede....@gmail.com]

There could of course be some point to cooking up a new implementation from scratch, but if I were to do it, I'd probably just wrap this library (note that main() in train.cpp needs a few changes to be run ad hoc, but I've had some good use out of it already).

[mmarco]

Cool, i didn't know about it. I just knew about Toby Hall program (which, for several reasons, cannot be included in sage). It would be nice to produce a picture of the train track of a braid ;)

[fuglede....@gmail.com]

Note: I copied these remarks to the trac ticket.

[Vincent Delecroix]

Hello,

Let me tell you that T. Coulbois already implemented Bestvina-Handel
algorithm (for general automorphisms of the free group):

https://github.com/coulbois/sage-train-track

There are a lot of possible optimization and improvement in the
documentation. But it works well (and has been intensively tested).

Vincent

On 09/08/15 13:02, mmarco wrote:
> I also spent some time trying to figure out how to implement Bestvina
> -Handel algorithm. But i am not really an expert on that, so i desisted
> after some time. If you want to work on that, i would definitely try to
> help.
>
> I am so happy to have a braid/knot theory specialist on board.
>
> El domingo, 9 de agosto de 2015, 12:55:21 (UTC+2), fuglede....@gmail.com
> escribió:
>>
>> Having a libhomfly wrapper would certainly be nice. More generally, the
>> Mathematica KnotTheory`

>> <http://katlas.org/wiki/The_Mathematica_Package_KnotTheory%60> package

>> allows, iirc, for the input of a general R-matrix and spits out braid group
>> representations. Or maybe it's just for the ones that come from quantum
>> groups of simple Lie algebras. It would be great to have that ported to
>> sage as well.
>>
>> Nonetheless, I think there could still be some value in having a Kauffman
>> bracket implementation of the Jones polynomial such as yours: while the
>> braid group representation algorithm is certainly more effective in

>> particular cases, it is not clear to me that it *always* is. In

>>>>>>> <http://www.google.com/url?q=http%3A%2F%2Ftrac.sagemath.org%2Fticket%2F17030&sa=D&sntz=1&usg=AFQjCNHtremMXOZeAA7pqdSLRqPr2yNIIg>,

[fuglede....@gmail.com]

Nifty! Any plans to include this in the code base?

- Søren

[Vincent Delecroix]

Not short term plans as far as I know. The best would be to ask Thierry
Coulbois himself. One thing which should be relatively easy would be to
polish the doctests and make it an optional package.

Vincent

[Travis Scrimshaw]

From a quick lookover, it looks like it is easy enough to actually port the methods directly into Sage, which would make it easier to maintain and use than an optional spkg.

Best,
Travis

[Vincent Delecroix]

It is technically feasible and certainly easy. But will the current
programmers will one day contribute to Sage? If the answer is no, it
would be bad to include it in Sage source code as it will diverge from
upstream. This is why I asked to ask before moving on.

On 11/08/15 02:44, Travis Scrimshaw wrote:
>>From a quick lookover, it looks like it is easy enough to actually port the
> methods directly into Sage, which would make it easier to maintain and use
> than an optional spkg.
>
> Best,
> Travis
>
>
> On Monday, August 10, 2015 at 8:26:36 AM UTC-7, vdelecroix wrote:
>>
>> Not short term plans as far as I know. The best would be to ask Thierry
>> Coulbois himself. One thing which should be relatively easy would be to
>> polish the doctests and make it an optional package.
>>
>> Vincent
>>

[fuglede....@gmail.com]

The methods have been include in [http://trac.sagemath.org/ticket/19011 trac ticket #19011].

At the end of the day, it would be nice to have some kind of mechanism for deciding which algorithm to use as they really are rather different. I made a simply benchmark to highlight their strengths and weaknesses:

sage: benchmark()

Test 1: A very long braid on very few strands
Braid: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Braid rep: 0.03 seconds, Kauffman bracket: 10.33 seconds

Test 2: A very simple braid on quite a few strands
Braid: (1, 2, 3, 4, 5, 6, 7, 8)
Braid rep: 6.56 seconds, Kauffman bracket: 0.00 seconds

Code:

import time

def benchmark():
    def test(b):
        L = Link(b)
        print "Braid: " + str(b.Tietze())
        result_string = "Braid rep: {0:.2f} seconds, Kauffman bracket: {1:.2f} seconds"

        start_time = time.time()
        jones = b.jones_polynomial()
        testb = time.time() - start_time
   
        start_time = time.time()
        jones = L.jones_polynomial()
        testl = time.time() - start_time

        print result_string.format(testb, testl)

    print "\nTest 1: A very long braid on very few strands"
    l = 60
    B = BraidGroup(2)
    test(B([1]*l))
   
    print "\nTest 2: A very simple braid on quite a few strands"
    n = 9
    B = BraidGroup(n)
    test(B(range(1,n)))

-Søren

[mmarco]

Out of my head, the bracket method is exponential in the number of crossings, and pretty much independent on the number of strands. The TL representation involves the product of a nuumber of matrices that is linear on the number of crossings, and the complexity of such a matrix is also polynomial on the number of strands (around fourth power maybe?). So one could expect the bracket method to be better only if the number of crossings is really small.

In the future we could have even a thirthd option, which is to compute the HOMFLY polyonimal using Jenkins method. I have ported his program to be used as a shared library, and written sage package with a cython interface. When the knot code gets merged, i will open another ticket to include it. His method is also exponential in the worst case, but quite fast in practice. Its problem is that it consumes a lot of memory.

[fuglede....@gmail.com]

Den onsdag den 12. august 2015 kl. 15.26.09 UTC+2 skrev mmarco:

The TL representation involves the product of a nuumber of matrices that is linear on the number of crossings, and the complexity of such a matrix is also polynomial on the number of strands (around fourth power maybe?).

In the code in #19011, the representation for n strands is actually a direct sum of roughly n/2 representations. I'm not sure what you mean exactly by the 'complexity' of the matrix representations but the sums of the squares of the dimensions of the relevant spaces are exactly the Catalan numbers which grow asymptotically like something like 4^n / n^(3/2).

It just occurred to me though, that the problematic cases could probably become a lot less problematic by imposing sparsity. That should probably be the default assumption:

sage: benchmark()

Test 1: A very long braid with very few strands

Braid: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Braid rep: 0.06 seconds, Kauffman bracket: 9.99 seconds

Test 2: A very simple braid on quite a few strands
Braid: (1, 2, 3, 4, 5, 6, 7, 8)

Braid rep: 0.04 seconds, Kauffman bracket: 0.00 seconds

- Søren

[mmarco]

I see, i got the wrong idea about the representation. Thanks for the clarification. In that casde, it would be really interesting to run your benchmark on a lot of different cases. Maybe the sparcity advantage gets reduced after a big number of crossings, when we get a lot of non-zero entries in the matrix.

[fuglede....@gmail.com]

Den onsdag den 12. august 2015 kl. 16.07.15 UTC+2 skrev mmarco:

I see, i got the wrong idea about the representation. Thanks for the clarification. In that casde, it would be really interesting to run your benchmark on a lot of different cases. Maybe the sparcity advantage gets reduced after a big number of crossings, when we get a lot of non-zero entries in the matrix.

Yep, it could be fun to see how they perform on the katlas database (which I believe you've already mounted on sage) to see how they fare in 'practice'. I would imagine that sparsity correlates very strongly with the Nielsen-Thurston type of the braid (without wanting to make too precise a statement in that direction).