Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Implement colorings of knots and links #21863

Closed
miguelmarco opened this issue Nov 11, 2016 · 34 comments
Closed

Implement colorings of knots and links #21863

miguelmarco opened this issue Nov 11, 2016 · 34 comments
Labels
c: algebraic topology p: major / 3 t: enhancement
Milestone
sage-8.8

Comments

@miguelmarco
Copy link
Contributor

This ticket implements methods to check n-colorability of knots and links (1) and adapts the plot method to allow to plot the link with the corresponding coloring.

It deppends on the .arcs() method, implemented in #21815

CC: @kcrisman @amitjamadagni @sagetrac-fugelde @tscrim @jdemeyer

Component: algebraic topology

Keywords: knot, link

Author: Miguel Marco, Frédéric Chapoton

Branch/Commit: bc9412a

Reviewer: Miguel Marco, Frédéric Chapoton, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/21863
@miguelmarco miguelmarco added this to the sage-7.5 milestone Nov 11, 2016
@miguelmarco
Copy link
Contributor Author

Dependencies: #21815

@miguelmarco

This comment has been minimized.

Sign in to view
@miguelmarco
Copy link
Contributor Author

Branch: u/mmarco/knot-colorings

@fchapoton
Copy link
Contributor

Commit: f6483a5

@fchapoton
Copy link
Contributor

comment:3

rebased and refreshed, this seems to be good to go

New commits:

ea0358dImplement knot collorings
f6483a5Merge branch 'u/mmarco/knot-colorings' in 8.7.b7

@fchapoton
Copy link
Contributor

Changed dependencies from #21815 to none

@fchapoton
Copy link
Contributor

Changed branch from u/mmarco/knot-colorings to public/ticket/21863

@fchapoton fchapoton modified the milestones: sage-7.5, sage-8.8 Mar 15, 2019
@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 16, 2019

Changed commit from f6483a5 to caaac73

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 16, 2019

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

caaac73trac 21863 fix some details in colored knots

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 16, 2019

Changed commit from caaac73 to 015455e

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 16, 2019

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

015455etrac 21863 some fix of doctest for py3 compatibility

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 16, 2019

Changed commit from 015455e to 7b5a69b

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 16, 2019

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

7b5a69btrac 21863 fix mistake

@miguelmarco
Copy link
Contributor Author

comment:7

Thanks for the revival. If all test pass, would you agree on a positive review?

@fchapoton
Copy link
Contributor

comment:8

Well, almost.

  • I am not fully happy with the test for type "str" to check if the color is a color or a coloring. Maybe we should rather check for type "dict" to recognize colorings ?

  • I would still like to add a reference to [Livi1993] (which gives a nice presentation of knots colorings)

@miguelmarco
Copy link
Contributor Author

comment:9

Fine. I will try to work on it during the weekend.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 16, 2019

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

3cfb2d6trac 21863 last minute fixes

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 16, 2019

Changed commit from 7b5a69b to 3cfb2d6

@fchapoton
Copy link
Contributor

comment:11

I have made the changes that I wanted to do. I will now launch my bot. If it comes back green, it will be ready for your approval.

@fchapoton
Copy link
Contributor

comment:12

Bot is green. I am ok with the code. If you too, please set to positive.

@fchapoton
Copy link
Contributor

Changed author from Miguel Marco to Miguel Marco, Frédéric Chapoton

@fchapoton
Copy link
Contributor

Reviewer: Miguel Marco, Frédéric Chapoton

@miguelmarco
Copy link
Contributor Author

comment:13

Now that I look at it, I am not completely sure that the result of is_colorable is mathematically correct in general: it relies on coloring_matrix, which takes the next prime of the passed number. So in the case of prime numbers, that is correct, but for non-prime, we are actually saying if it is p-colorable for the next prime p.

Maybe it is ok if we just calrify this in the documentation? Or should we write more complete code to check that there actually exist solutions over the integers mod n for non prime n?

@tscrim
Copy link
Collaborator

tscrim commented Mar 16, 2019

comment:14

I also have one doc nitpick: n should be in code formatting.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 17, 2019

Changed commit from 3cfb2d6 to 27548b0

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 17, 2019

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

27548b0trac 21863 polishing the details

@fchapoton
Copy link
Contributor

comment:16

ok, done

@tscrim
Copy link
Collaborator

tscrim commented Mar 18, 2019

comment:17

I am happy with things as the added documentation does clarify what Sage does, but I want to wait to see if Miguel has any additional comments.

@tscrim
Copy link
Collaborator

tscrim commented Mar 18, 2019

Changed reviewer from Miguel Marco, Frédéric Chapoton to Miguel Marco, Frédéric Chapoton, Travis Scrimshaw

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 18, 2019

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

bc9412aUse next_prime also in colorings

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Mar 18, 2019

Changed commit from 27548b0 to bc9412a

@miguelmarco
Copy link
Contributor Author

comment:19

I added a check for next prime also in colorings, so it is now totally clear that we only cover the case of prime number of colors. Maybe we should support also non prime number of colors, but that requires slightly more sophisticated algorithms, so it should be better done in another ticket.

If you are ok with these last changes, positive review.

@fchapoton
Copy link
Contributor

comment:20

ok, good to go.

@vbraun
Copy link
Member

vbraun commented Mar 25, 2019

Changed branch from public/ticket/21863 to bc9412a

@vbraun vbraun closed this as completed in c9edc89 Mar 25, 2019
@jhpalmieri jhpalmieri mentioned this issue Mar 30, 2019
Closed
@soehms soehms mentioned this issue Sep 25, 2023
Merged
5 tasks
vbraun pushed a commit to vbraun/sage that referenced this issue Oct 19, 2023
731be1c 
sagemathgh-36333: Revision of the knot theory colorings method
    
<!-- ^^^^^
Please provide a concise, informative and self-explanatory title.
Don't put issue numbers in there, do this in the PR body below.
For example, instead of "Fixes sagemath#1234" use "Introduce new method to
calculate 1+1"
-->
<!-- Describe your changes here in detail -->

<!-- Why is this change required? What problem does it solve? -->
<!-- If this PR resolves an open issue, please link to it here. For
example "Fixes sagemath#12345". -->
<!-- If your change requires a documentation PR, please link it
appropriately. -->

The following issue has been reported by Chuck Livingston to me:

```
sage: K9_15 = Knots().from_table(9, 15)
sage: K9_15.colorings(13)
[]
sage: K9_15.determinant()
39
```


Since 13 divides the determinant of the knot 156 colorings are expected.
While analyzing this issue, I found that the implementation (done in
sagemath#21863) does not match the
definition of [Fox `n`-colorings](https://en.wikipedia.org/wiki/Fox_n-
coloring) given in the listed references on Wikipedia and in Chuck's
book.

The name coloring maybe misleading here: The number `n` does not refer
to the number of (arbitrary) colors to be used. It can be interpreted as
the size of a fixed color palette. Mathematically, the colors correspond
to elements of the `n`-th dihedral group `D_n` whose rotations
(multiplied with the generating transvection) form the color palette. A
coloring corresponds to a group homomorphism from the fundamental group
`F` of the knot to `D_n`. If one interprets the arcs of the knot as the
generators of `F`, their colors correspond to their images in `D_n`.

Here are some lines in the current code that do not meet this
definition:

1. Changing `n` to the next prime number:

```
        p = next_prime(n - 1)
```

2. Restriction of `n` to the number of different colors used:

```
            if len(colors) == p:
```

3. Change color values:


```
                colors = {b: a for a, b in enumerate(colors)}
                res.add(tuple(colors[c] for c in coloring))
```

This PR fixes these issues. Furthermore, a new method `coloring_maps` is
added to calculate the group homomorphisms explicitly. This can also be
used to verify the results of the method `colorings`. Finally, the
`plot` method is adapted to the changes.

Note that the definition does not restrict `n` to be a prime number.
However, if this is not the case, we cannot just take the next prime
number to work more comfortably over a field. It is still necessary to
work over the residue class ring modulo `n`. Although the method
`right_kernel_matrix` works well in this context the method
`right_kernel` does not work due to a failure in the `span` method of
the `FreeModule` class. Since I didn't find an easy fix for this I
worked around this issue.




### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->
<!-- If your change requires a documentation PR, please link it
appropriately -->
<!-- If you're unsure about any of these, don't hesitate to ask. We're
here to help! -->
<!-- Feel free to remove irrelevant items. -->

- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on
- sagemath#12345: short description why this is a dependency
- sagemath#34567: ...
-->

<!-- If you're unsure about any of these, don't hesitate to ask. We're
here to help! -->
    
URL: sagemath#36333
Reported by: Sebastian Oehms
Reviewer(s): miguelmarco, Sebastian Oehms
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: algebraic topology p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-8.8
Development

No branches or pull requests
4 participants
@vbraun @tscrim @miguelmarco @fchapoton