Knot Theory as a part of GSoC 2014.

[amitjamadagni]

We provide a basic implementation of knots and links such as the Seifert matrix, Jones and Alexander polynomials.

CC: @miguelmarco @jhpalmieri @tscrim @fuglede

Component: algebraic topology

Author: Amit Jamadagni, Miguel Marco

Branch: 207d033

Reviewer: Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw, Søren Fuglede Jørgensen, John Palmieri

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

[amitjamadagni]

Branch: u/amitjamadagni/knots

[amitjamadagni]

Commit: 50abd99

[amitjamadagni]

Author: amitjamadagni, mmarco

[amitjamadagni]

comment:5

Things to do:

1. Plot method needs to be added.
2. ncomponents needs to be worked upon.

[amitjamadagni]

Reviewer: mmarco

[miguelmarco]

comment:8

I am not sure if it is a good idea that i would be the reviewer, since i have been involved in tge coding too. Besides, there is some polishing needed still and it would go faster if i directly work on it.

jhpamieri, do you feel able to do the revieweing? If yes, i will start working in the corrections. Otherwise, i will stay away from changing the code and just act as reviewer.

[miguelmarco]

comment:9

I get the following wrror when compiling:

running install_lib
byte-compiling /home/mmarco/sage/local/lib/python2.7/site-packages/sage/all.py to all.pyc
File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/all.py", line 174
<<<<<<< HEAD
^

Is it a problem with the commit? Over which branch is it based?

[amitjamadagni]

comment:10

Replying to @miguelmarco:

I get the following wrror when compiling:

running install_lib
byte-compiling /home/mmarco/sage/local/lib/python2.7/site-packages/sage/all.py to all.pyc
File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/all.py", line 174
<<<<<<< HEAD
^

Is it a problem with the commit? Over which branch is it based?

I pushed the branch from github (the branch week15) onto the trac ticket. Let me try adding all.py and commit once again.

[sagetrac-git]

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

e6e17c4

Removed the messages in all.py

[sagetrac-git]

Changed commit from 50abd99 to e6e17c4

[tscrim]

Changed reviewer from mmarco to Miguel Marco

[tscrim]

Changed author from amitjamadagni, mmarco to Amit Jamadagni, Miguel Marco

[tscrim]

comment:12

It looks like a bad resolution to a merge, but it's a simple enough fix. Also on a quick look through:

• Doc formatting should follow:

INPUT:

- ``name`` -- some description that is very long and
  note the alignment

OUTPUT:

- these are not usually complete sentences but short descriptions

• Move the nice documentation from the __init__ into the class-level doc so people can actually see it.
• All methods must have doctests.
• It's my pythonic to use isinstance(input_, list) instead of type(input_) == list.
• input_ is a bad variable name (according to python standards), just use input (or perhaps the slightly more descriptive data)
• Don't raise Exception, instead raise ValueError or TypeError (after killing with fire and holy water :P).
• Change

pd_error = _pd_check_(input_)
if pd_error == True:
    pass
elif pd_error == False:
    pass

into (the pythonic)

if _pd_check_(input_):
    pass
else:
    pass

• Use is not None instead of != None.
• Make _dt_internal_ a proper method of the class.
• Remove the trailing underscore of _pd_check_, ,_dt_internal_ etc. as methods with a leading and trailing underscore are usually Sage special functions (and naming conventions of python).
• Is "dowker" a proper name (and hence, should be capitalized in the documentation)?
• The method name Seifert_Matrix should be seifert_matrix (naming conventions again).
• Could you change the name of ncomponents to number_of_components (although you can keep it as a shorthand alias)?
• This needs to be added to the documentation (probably as a new component).

I'll make a more detailed pass through the code after these are addressed. I also don't know how much of the math I'll be able to review as I've studied a little knot theory, but possibly not enough to check everything. Although Miguel could count as the reviewer on that front.

I think this will be a great addition to Sage, all it needs a little polish.

Best,

Travis

[jdemeyer]

comment:13

Also please respect http://www.sagemath.org/doc/developer/coding_basics.html#headings-of-sage-library-code-files and add your new files to the reference manual (have a look at the files in src/doc/en/reference to see how that is done).

Even better, change

pd_error = _pd_check_(input_)
if pd_error == True:
    raise Exception("...")
elif pd_error == False:
    foo

to

if not _pd_check(input):
    raise ValueError("...")

foo

and change the last line of def _pd_check_(pd): to return not pd_error, since I would expect a "check" function to return True if the checking was successful. Also drop the trailing underscores.

[jdemeyer]

comment:14

Instead of returning a string in _vogel_move_(), you should return None in case of failure. That would be more efficient and one wouldn't need to remember a magic string (which is by the way wrong in the doc of that method, further proving my point).

[amitjamadagni]

comment:15

Replying to @jdemeyer:

Instead of returning a string in _vogel_move_(), you should return None in case of failure. That would be more efficient and one wouldn't need to remember a magic string (which is by the way wrong in the doc of that method, further proving my point).

I am currently having few issues with pushing commits onto trac, once I am done with the setup I will be sending in the commits. Thanks for guiding me and sorry for missing on the rules.

[kcrisman]

comment:16

I'll make a more detailed pass through the code after these are addressed. I also don't know how much of the math I'll be able to review as I've studied a little knot theory, but possibly not enough to check everything. Although Miguel could count as the reviewer on that front.

Yeah, I think it would be really wise for such a new component and with a lot of technicalities for determining e.g. whether a given link is a knot to have a couple actual knot theorists review it, at least by checking the output in lots of cases. That may take some cold-calling, though perhaps a sage-devel email will turn up some all by itself, and there are Sage-friendly knot folks out there - though I don't know if they know how to review a branch.

[miguelmarco]

comment:17

I was planning on making a package with the database from the knot atlas, and use it to run automated tests, computing the invariants for the knots and links there.

The problem with that approach is that a) It needs some nontrivial work to be implemented, and b) it restricts to knots and links presented im spcially "nice" ways, so we could miss some bugs if they show up only when some strange representations are used.

Anyways, it would be a nice addition by itself, so i will try to work on it in the following weeks.

In the meantime, and since there are several other reviewers in the coding style part, i will just focus on checking the mathematical correctness of the methods.

[miguelmarco]

comment:18

There is something working wrong in the following case:

sage: L=Link([[1, 4, 2, 5], [7, 10, 8, 11], [3, 9, 4, 8], [9, 3, 10, 2], [5, 12, 6, 1], [11, 6, 12, 7]])
sage: L
<repr(<sage.knots.link.Link at 0x7f41771c8a28>) failed: Exception: Invalid Input>

It gets an error when trying to get the connected components, which in turn tries to convert it to braid (which is probably not a good idea, it would be wiser to compute the components directly from the PD_code, since we might me loosing something in the conversion PD<->braid).

In any case, this example fails in the conversion to braid:

sage: L.braid()
...
Exception: Invalid Input

Please go through it and debug.
}}}

[kcrisman]

comment:19

I was planning on making a package with the database from the knot atlas, and use it to run automated tests, computing the invariants for the knots and links there.

The problem with that approach is that a) It needs some nontrivial work to be implemented, and b) it restricts to knots and links presented im spcially "nice" ways, so we could miss some bugs if they show up only when some strange representations are used.

Anyways, it would be a nice addition by itself, so i will try to work on it in the following weeks.

That's a really excellent idea. It's always good to have two ways to check information anyway. Ideally one could have a prototype of that available in time to help test this ticket as well.

[jhpalmieri]

comment:190

Should we set this back to "positive review"? I don't plan to make any more changes.

[tscrim]

Changed reviewer from Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw, Søren Fuglede Jørgensen to Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw, Søren Fuglede Jørgensen, John Palmieri

[vbraun]

Changed branch from public/ticket/17030 to 207d033

[jhpalmieri]

comment:193

See #20315 for a followup.

[jhpalmieri]

Changed commit from 207d033 to none

[jhpalmieri]

comment:194

Replying to @jhpalmieri:

See #20315 for a followup.

In more detail, whoever is familiar with the plotting code should review the changes there.

[slel]

comment:195

Follow-up ticket at #25050: allow braid computation for more links.

[soehms]

comment:24

Replying to @miguelmarco:

I was planning on making a package with the database from the knot atlas, and use it to run automated tests, computing the invariants for the knots and links there.
The problem with that approach is that a) It needs some nontrivial work to be implemented, and b) it restricts to knots and links presented im spcially "nice" ways, so we could miss some bugs if they show up only when some strange representations are used.
Anyways, it would be a nice addition by itself, so i will try to work on it in the following weeks.
In the meantime, and since there are several other reviewers in the coding style part, i will just focus on checking the mathematical correctness of the methods.

Just to mention knot altas has other kind of representation of PD Code, they start on the under crossing and move in the anti clockwise direction around the cross while we move in the clockwise direction in the construction of the PD code.

Who can remember ... ?

I'm interested in the background of a decision about the PD -code. In many well-known places as Bar Natan's original work, Snappy, KnotInfo, Szabo's HF package .... the convention used to read PD code is in counter clockwise direction. Contrary Sage's convention is clockwise. Neither I can't find the source of this convention nor something about the reason for the choice (which is at least mentioned in the quoted comment 24 from 25th of September 2014).

[soehms]

@amitjamadagni , @miguelmarco , @tscrim , @kcrisman , @jhpalmieri , @fchapoton , @fuglede

I wonder if notification works for migrated participants of a migrated Trac ticket. Did you see my #17030 (comment) above from last Tuesday?

[kcrisman]

I wonder if notification works for migrated participants of a migrated Trac ticket. Did you see my #17030 (comment) above from last Tuesday?

I don't see it on my GH notifications, just this one. I guess you have to "subscribe" to the ticket (whether universally or in particular), and that doesn't seem to have happened. Could be worth talking about on sage-devel if it hasn't already shown up as one of the tickets on the trac-to-github repo (and I'm not sure what the default should be, if any).

[kcrisman]

And for what it's worth, I do not remember the story behind the clock/counter (non?)decision 😄

[miguelmarco]

I didn't see it on my notifications either, just this one.

About the decission, IIRC we followed snappy convention.

[soehms]

And for what it's worth, I do not remember the story behind the clock/counter (non?)decision smile

About the decission, IIRC we followed snappy convention.

@kcrisman , @miguelmarco

Thank you both.

Miguel,

currently SnapPy follows the counter clockwise convention, too:

sage: Ksage = Knot([[1,5,2,4],[3,1,4,6],[5,3,6,2]])
sage: import snappy
sage: Ksnappy = snappy.Link([[1,5,2,4],[3,1,4,6],[5,3,6,2]])
sage:
sage: Ksnappy.sage_link().pd_code()
[[1, 4, 2, 5], [3, 6, 4, 1], [5, 2, 6, 3]]
sage: Ksage.pd_code()
[[1, 5, 2, 4], [3, 1, 4, 6], [5, 3, 6, 2]]
sage:
sage: KnotInfo.K3_1.pd_notation()
[[1, 5, 2, 4], [3, 1, 4, 6], [5, 3, 6, 2]]
sage: KnotInfo.K3_1.link().pd_code()
[[1, 4, 2, 5], [3, 6, 4, 1], [5, 2, 6, 3]]
sage:
sage:  KnotInfo.K3_1.link().is_isotopic(Ksnappy.sage_link())
True
sage:  KnotInfo.K3_1.link().is_isotopic(Ksage.mirror_image())
True

This is compensated by the transition method sage_link. A similarly compensation I've implemented in the KnotInfo interface link method. In the SnapPy release notes I found a change in conventions concerning the braids (version 3.0) but nothing concerning PD code.

The question about the convention has been arisen by Chuck Livingston. He has been very confused by it, as I was when I implemented the KnotInfo interface. But besides this, he is very impressed with Sage Knot Theory and hopeful that it will become the standard platform for knot theory researchers.

Maybe, we should think about a change of the PD convention if there is no strong reason for the choice made in 2014. What do you think?

[miguelmarco]

I see, I guess the origin comes from that difference in the braid representation: I must have assumed that snappy uses the same convention for braids, and inferred from there the clockwise convention for links.

Since there is no real reason to keep that convention (aside from not breaking existing code that relies on it), i have no objection to change it... being very careful with the issue of not breaking things.

[tscrim]

The doctests should (in principle) be sufficient to catch if anything breaks. Although there will be no way to ensure a transition period where downstream code using this convention explicitly would not break. I think we just have to take our medicine here and switch the conventions with a big warning in our release notes about it, possibly also in the PD code documentation itself.

[soehms]

I guess the origin comes from that difference in the braid representation

I had the backward confusion when I implemented the KnotInfo interface. First I thought the reflection of knots was due to a difference in the braid convention since the referenced paper on KnotInfo had the inverse convention. But than I realized, that the braid convention in KnotInfo is the same as ours despite of the reference.

[soehms]

The doctests should (in principle) be sufficient to catch if anything breaks. Although there will be no way to ensure a transition period where downstream code using this convention explicitly would not break. I think we just have to take our medicine here and switch the conventions with a big warning in our release notes about it, possibly also in the PD code documentation itself.

I completely agree. But, we should try to do the switch simultaneously with an adaption in the SnapPy sage_link method, explicitly these lines o code:

        # Sage's PD_code lists strands *clockwise* not our *anticlockwise*.
        code = [[x[0], x[3], x[2], x[1]] for x in self.PD_code(min_strand_index=1)]

@NathanDunfield will this be possible? I know, this does not prevent users to have incompatible versions of Sage and SnapPy. But if in both there is an note about the switch of convention and which versions are compatible it would be acceptable.

[NathanDunfield]

@miguelmarco For what it's worth, SnapPy changed its convention for braids with the 3.0 release. Positive braid generators now give positive crossings (we used to follow the convention in Birman's classic book, which is the reverse).

@soehms I think the best solution would be for SnapPy to test for the version of Sage and then convert appropriately. There's no way to avoid the problem of (old SnapPy, new Sage) but the other three combinations would all work correctly.

[tscrim]

@NathanDunfield Of course, the version() command... :P

[soehms]

@soehms I think the best solution would be for SnapPy to test for the version of Sage and then convert appropriately. There's no way to avoid the problem of (old SnapPy, new Sage) but the other three combinations would all work correctly.

That would be great. But an additional note in the docstring would be nice for the surprise when the user notices the change for the first time.

[soehms]

Since there are no objections against the change here, I ask on sage-devel for opinions. If there will be no other objections, I will open an issue / PR in one of the next weeks.

[soehms]

Since there are no objections against the change here, I ask on sage-devel for opinions. If there will be no other objections, I will open an issue / PR in one of the next weeks.

Now, there is PR #35665 implementing the switch of convention being ready for review.