Caribou in Covid: Contests are running online as usual. Check out the FAQ for further questions.

300000

1069

__If you are just interested in how to solve this challenge and not the theory behind, then advance to 'What are hints for finding a colouring by trial and error?'__**About invariants**

can be deformed into each other without cutting the knotline.

Otherwise, the following sequence shows how to simplify the Tuzun-Sikora diagram to a circle.

**Proof that the Tuzun-Sikora diagram is the unknot.**

An example of an invariant is the minimal number of crossings that any one of the infinitely many equivalent diagrams may have. This invariant is hard to find because one can not check infinitely many diagrams.

But what could be an invariant that can be computed for a given diagram? It is difficult to imagine which property does not change in a deformation when one can deform a diagram in any way one wants.

**Tri-colourability is an invariant.**

**Which of the 3 diagrams is tri-colourable?**

**N-colourability**

Many questions come up.

**Introduction to modular arithmetic**

We can prove all statements of modular arithmetic by introducing a multiplier k and re-formulating the ≡ equation as a normal equation. To shorten notation we use

'integer' for 'whole number',

'pq' for 'p times q',

'∃' for 'There exist',

':' for 'with the property', and

'A → B' for 'from A follows B'.

**Prove: if a ≡ b mod N and c ≡ d mod N then (a+c) ≡ (b+d) mod N**

i.e. there must exists a multiplier m with the property that a = b + mp. In short notation this is

(a ≡ b mod N) → (∃ integer m: a = b + mp)

(c ≡ d mod N) → (∃ integer n: c = d + np)

By adding up both equations we get a + c = b + mp + d + np = b + d + (m+n)p

→ a + c ≡ (b + d) mod N

**Prove: if a ≡ b mod N then for any integer m we have ma ≡ mb mod N**

After multiplication with m we get

ma = mb + mkN

→ ma ≡ mb mod N

**Prove: if a ≡ b mod (PQ) then a ≡ b mod P.**

→ ∃ integer k: a = b + k(PQ)

→ a = b + (kQ)P

→ a ≡ b mod P

**What about the opposite direction?**

6 ≡ 1 mod 5 but

6 ≢ 1 mod 15 because 6 and 1 do not differ by a multiple of 15.

**Why is it plausible that the inverse is not true?**

In an equation mod N both sides of ≡ can have N different values. In an equation mod (NM) both sides of ≡ can have NM different values. Therefore a relation mod (NM) carries more information than a relation mod N. Throwing information away by going from mod (NM) to mod N is easy but the inverse of creating information out of nothing is impossible. Roughly speaking, in this sense a normal equality using = is equivalent to ≡ mod ∞(infinity).

As a side comment, this opens the possibility that in applications where the solution involves integer numbers and where one is looking for a solution in form of an equation using an '=' and where one knows that there is an upper bound for the absolute value of the numbers in the solution then a strategy may be to start with finding a solution mod N for some small prime number N and then to compute the identity mod N^2, then mod N^4 and so on until the power of N is larger than the upper bound one knows for the solution and then one can drop the mod and has the exact solution using = .

Such a method called *Hensel lifting* can be used to factorize univariate polynomials first with respect to some small prime number and then finally exactly over the integers.

**Prove: a + b ≡ ((a mod N) + (b mod N)) mod N**

b and b mod N differ by a multiple of N: b = (b mod N) + qN

→ a + b = (a mod N) + (b mod N) + (p + q)N

→ a + b ≡ ((a mod N) + (b mod N)) mod N

**Prove: ab ≡ ((a mod N)(b mod N)) mod N**

b and b mod N differ by a multiple of N: b = (b mod N) + qN

→ ab = ((a mod N) + pN)((b mod N) + qN)

= (a mod N)(b mod N) + [(a mod N)q + (b mod N)p + pqN]N

→ ab ≡ (a mod N)(b mod N) mod N

**Prove: if P(x,y,...) is a polynomial in variables x,y,... then P(x,y,...) ≡ P((x mod N),(y mod N),...) mod N**

**Prove: In modular arithmetic modulo a prime number, divisions by integers give again integers.**

We start by showing that for a prime number p and any integer a ≢ 0 mod N, the inverse 1/a mod N is also an integer. We require a ≢ 0 mod N because also in modular arithmetic, division by zero is not possible.

Let u be u ≡ 1/a mod N. For u to be the inverse of a mod N it means

ua ≡ 1 mod N

→ ∃ integer k: ua = 1 + kp

This has the form of Bézout's identity: ua + vp = GCD(a,p) where GCD(a,p) is the Greatest Common Divisor of a,p and where v=-k. Because p is a prime number and a is not a multiple of p therefore GCD(a,p)=1.

The multipliers u,v in Bézout's identity can be computed through the extended Euclidean algorithm and both, u,v, are integers.

If u=1/a is an integer mod N then b/a = bu is also an integer mod N which was to be shown.

Example: 1/3 ≡ 5 mod 7 because 1 = 3(1/3) ≡ 3(5) = 15 = 2(7) + 1 ≡ 1 mod 7.**When is ma ≡ mb mod N equivalent to a ≡ b mod N?**

**The Chinese Remainder Theorem.**

This is what the Chinese reminder theorem states.

If for the two equations

x ≡ a

_{1}mod N

_{1}

x ≡ a

_{2}mod N

_{2}

the divisors N

_{1},N

_{2}are co-prime, then there exists exactly one value for x up to multiples of p

_{1}p

_{2}which satisfies both modular equations.

One way to get the solution is to use the extended Euclidean algorithm to solve the Bézout's identity m

_{1}N

_{1}+ m

_{2}N

_{2}= 1 by computing m

_{1},m

_{2}and then to use the formula

x = a

_{1}m

_{2}N

_{2}+ a

_{2}m

_{1}M

_{1}

= a

_{1}(1 - m

_{1}N

_{1}) + a

_{2}m

_{1}N

_{1}

= a

_{1}+ (a

_{2}- a

_{1})m

_{1}N

_{1}

which shows x ≡ a

_{1}mod N

_{1}and equivalently x = a

_{2}+ (a

_{1}- a

_{2})m

_{2}N

_{2}which shows x ≡ a

_{2}mod N

_{2}.

If one has more than two modular equations then one can repeatedly replace two of them by one until one has the solution in form of one modular equation. In each replacement the new divisor number grows by becoming the product of the two divisors of the merged equations.

**How can one prove that N-colourability is an invariant?**

**How can one show that a Reidemeister I move does not change colourability?**

If the colours of the strands are A and B as indicated then the colouring condition requires in the left figure A + B ≡ 2B mod N and in the right figure B + A ≡ 2A mod N. In both cases B = A is a solution:

That means, performing a Reidemeister I move does not change colourability.

**How can one show that a Reidemeister II move does not change colourability?**

If the colours of the strands are A,B and C as indicated then C is uniquely determined from the condition B + C ≡ 2A mod N in the left figure so C ≡ (2A - B mod N) and in the right figure A + C ≡ 2B mod N so C ≡ (2B - A mod N). This determines the colour of the new strand when performing a Reidemeister II move. Colourability is not affected.

**How can one show that a Reidemeister III move does not change colourability?**

If the colours of the strands are A,B,C,D,E,F and G as indicated then the three conditions on the left are

A + D ≡ 2C mod N

E + F ≡ 2D mod N

F + B ≡ 2C mod N .

By eliminating the internal strand F the condition on the external strands is

2D - E ≡ 2C - B mod N which by using A + D ≡ 2C mod N simplifies to

2D - E ≡ A + D - B mod N and thus A - B - D + E ≡ 0 mod N.

The 3 conditions on the right are

E + G ≡ 2C mod N

G + B ≡ 2A mod N

A + D ≡ 2C mod N

By eliminating the internal strand G the condition on the external strands is

2C - E ≡ 2A - B mod N which by using 2C ≡ A + D mod N simplifies to

A + D - E ≡ 2A - B mod N and thus 0 ≡ A - B - D + E mod N.

F and G are calculated from any one of the relations they appear in.

We conclude that for both diagrams the conditions on the colours of external strands are the same: A + D ≡ 2C mod N and A - B - D + E ≡ 0 mod N.

Therefore either both diagrams have or none of them has a colouring and hence colourability is invariant under Reidemeister III moves.

**Triviality, equivalence and independence of colouring**

**If one has one colouring, what other colourings can be obtained from it for any knot diagram?**

1) When adding the same constant, say S, to each colour then differences do not change:

(A+S) - (C+S) = A - C + S - S = A - C and

(C+S) - (B+S) = C - B + S - S = C - B and

the conditions are therefore still satisfied.

2) We saw earlier as a rule of modular arithmetic that we can multiply both sides of ≡ with a number co-prime to N and obtain an equivalent solution of the system of equations and thus an equivalent colouring.

**Is colourability mod 2 meaningful?**

Let us start at a strand with colour A which continues as strand B after crossing underneath the first overpass with colour C. Then A,B,C are related through A + B ≡ 2C mod 2 and after adding B to both sides A ≡ B mod 2 because 2B ≡ 2C ≡ 0 mod 2. Continuing that reasoning at all crossings it follows that all strands have either an even colour (0) or an odd colour (1). This gives a trivial colouring.

**What about colourability mod (2N), i.e. modulo an even number?**

As a consequence, each colouring mod (2N) is equivalent to a coulouring mod N.

**For which N is N-colourability useful and not trivial?**

**Is it sufficient to know all colourings mod P and mod Q where P and Q are co-prime to know all colourings mod (PQ)?**

Answer: Yes.

Proof:

Let a

_{1}, a

_{2}be the colours of one strand in colourings mod P and mod Q.

The Chinese Remainder Theorem then guarantees the existence and uniqueness of one integer A mod PQ that satisfies both conditions

A ≡ a

_{1}mod P

A ≡ a

_{2}mod Q.

This can be repeated for each strand giving colour values A,B,C,... mod PQ.

At each crossing the two colouring conditions

(A + B - 2C) mod P = a

_{1}+ b

_{1}- 2c

_{1}≡ 0 mod P

(A + B - 2C) mod Q = a

_{2}+ b

_{2}- 2c

_{2}≡ 0 mod Q

are satisfied. The only value of (A + B - 2C) mod PQ that is zero mod P and is zero mod Q is A + B - 2C ≡ 0 mod PQ. This shows that colour values A,B,C,... provide a colouring mod PQ.

Because all positive integers have a prime factorization, they can be written as products of powers of prime numbers. One can therefore find all colouring numbers by investigating only all powers of all odd prime numbers as colouring number. We saw earlier that the prime number 2 and powers of 2 are not possible colouring numbers.

One would start checking the existence of a colouring modulo some prime number and if successful then to repeat the check with inccreasingly higher powers of that prime number until there does not exist a coulouring anymore.

**What are hints for finding a colouring by trial and error?**

- To decide which strand to colour next, press Enter to sort equations by their number of letters, i.e. by urgency.
- If an equation has several letters then pick one that occurs in the most other equations so that more equations simplify when a number is assigned. Equivalently, move the mouse over the equation, see the circled crossing and at this crossing click that uncoloured strand which has the most over-passes.
- Letters on the right side of ≡ are faster to compute than letters on the left. To compute a letter on the left one needs to divide by 2 which may require to add N to the right to become even. This is not difficult but in a contest time is prescious. For the same reason, when guessing the value of a letter one might take a letter on the left of a ≡.
- To save time do not worry to compute values in the interval 0..N−1. Values can be negative or arbitrarily large. If they are correct then a purple equation turns green and that is all that matters.

- If an equation has only one letter left then the background is purple and then there is no choice, the value needs to be calculated to make the equation green. See the examples in the instructions.
- As shown above in this section > 'If one has one colouring ...' section, the values of all letters can be shifted by the same constant value. Therefore the very first letter that one wants to assign can be given the value 0 without loss of generality. One will not try any other value for that letter because one could always shift that value to zero.
- For the 2nd letter to colour one needs to consider only two cases: 1) It has the same value as the first letter, i.e. 0, and 2) it has a different value. In that case one only needs to consider 1 because we saw that all numbers could be multiplied with 2..(N-1) (where N is the prime number of available colours) and still have an equivalent solution. Please reference this section > 'If one has one colouring ...'. For example, if N=5 and one would have tried a different value for the 2nd assigned letter, like 3 and have obtained a solution then multiplying this value (and all other values) with 2 would make the 3 to 3×2 = 6 ≡ 1 mod 5 so to a 1. Therefore the 2nd letter needs only to be tried as 0 and 1.
- Tests are also a question of time. One can save time by inputing negative numbers when they are faster to compute than positive numbers. The interface does not need numbers in the range 0..N-1.
- When an equation turns red then the ≡ condition is not satisfied and at least one number must be changed. Then try a different number. In order not to miss numbers one could try numbers in the order 0,1,...,N-1 and stop when a colouring was found.
- When backtracking by clicking the undo button, if one sees a purple equation then one can click the undo button again without thinking. The reason is that the purple equation has only one letter and for this letter there is only one possible value (mod N) so no other value needs to be tried for this letter in this situation.
- To search systematically and not to miss any colouring possibility one could start by assigning each variable the value 0 which gives the trivial solution and then to start backtracking to get a non-trivial solution.
- Knot diagrams used in this game have already a minimal number of crossings. But if diagrams would not be minimal then it would be advantageous to simplify them first. Without the above techniques for speedup one would have to try N
^{C}colourings where N is the number of colours and C is the number of crossings = number of strands. Reducing the number of crossings by only 1 lowers the effort by a FACTOR of N.

**Are there knots that can not be coloured?**

_{124}, 10

_{153}, 11n

_{34}, 11n

_{42}, 11n

_{49}, 11n

_{116}and, of course, the unknot. The figure shows a diagram of knot 10

_{124}.

The diagram labeled 'Tuzun-Sikora' at the top of the page is just one of infinitely many diagrams of the unknot and is therefore also not colourable.

**Are there even more colour invariants and how can they be computed?**

If a knot diagram has C crossings then it also has C strands and thus the system of conditions has a C×C coefficient matrix where each row represents a crossing and consists either of two -1 and one 2 or of a +1 and a -1 (Reidemeister I loop crossing). Each column corresponds to a strand and has as many 2's as the strand has over-passes and either two -1's or one -1 and one +1.

The conditions form a homogeneous linear system (the right hand side contains only 0s) and the question is to find colouring numbers modulo which nontrivial linear independent solutions (colourings) exist.

Like in linear algebra the matrix is brought into diagonal form by swapping rows and adding multiples of rows to other rows. In addition, these steps are also performed with columns. What is not allowed here is to multiply rows and columns by a number because that would add a colour number modulo which the determinant of the matrix would be zero and that would add an additional colouring. What is done instead is to pick repeatedly 2 non-zero components of a column/row, say A,B, to use the extended Euclid's algorithm to find p,q, satisfying pA + qB = GCD(A,B). p,q are the multipliers of the two rows/columns. After swapping rows/columns the GCD(A,B) becomes the diagonal element. The result is a diagonal matrix called Smith Normal Form where usually the top left corner starts with 1's followed by numbers that are each factor of the next number in the diagonal. The last diagonal element is zero as each knot diagram allows the trivial colouring using just one colour. Therefore it is enough to compute the Smith Normal Form after dropping any one column and any one row.

Calculating the determinant of the C×C coefficient matrix gives zero because the columns add to zero. Computing the determinant after dropping one row and one column gives one number which is the product of the numbers on the diagonal of the Smith normal form. So the Smith Normal Form gives more information for about the same effort.

Example: For this diagram with 83 crossings the coefficient matrix has size 83×83.

The Smith Normal Form has a diagonal starting in the top left corner with 79 times a 1 followed by 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. That means there are three independent 3-colourings and one 85837301265-colouring which implies it also has a 5-colouring, 15-colouring, 3x5722486751-colouring and 5x5722486751-colouring.

If a diagram has no colouring then all diagonal numbers are 1 except the 0 in the last position.

The following diagram belongs to knot 12a

_{801}.

The Smith Normal Form (SNF) has in the diagonal nine 1s, followed by 3,45,0. In this form each number is a factor of the next diagonal number. And the multiplicity of a colouring is the number of diagonal elements in which it occures as a factor. Therefore each diagram of this knot has two independent 3-colourings and a single 45-colouring which implies it also has a single 5-,9-,15-colouring.

**Statistics of knot colourings**

**Is there an overview of possible colourings of prime knots up to some size?**

`https://cariboutests.com/qi/knots/colour3-15-N.txt`

lists for each knot with crossing number ≦ 15 all entries of the Smith Normal Form that are not 0 or 1. These numbers have been computed from one diagram but they are invariant and therefore the same when being computed from any diagram of that knot. If you like pictures of coloured knots then you could download a poster from our poster collection by clicking on the home page 'Home' > 'Posters' leading to `https://cariboutests.com/images/posters/knot_colouring_portrait.pdf`

. **How strong is N-colouring as an invariant?**

Table 1: Statistics arount colour invariants

# of cr: # of crossings

# of kn: # of knots

# of cl1: # of classes when considering only list of prime colouring numbers

# of cl2: # of classes when considering only list of multiplicities of prime colouring numbers

# of cl3: # of classes when considering list of Smith Normal Form Entries <> 1

abs: exp(ln(noofcl3[cr])/(cr-3))

= (cr-3)th root of (# of cl3)

# of cr | # of kn | # of cl1 | kn/cl1 | # of cl2 | kn/cl2 | # of cl3 | kn/cl3 | abs ↑ |
---|---|---|---|---|---|---|---|---|

3 | 1 | 1 | 1.00 | 1 | 1.00 | 1 | 1.00 | |

4 | 1 | 1 | 1.00 | 1 | 1.00 | 1 | 1.00 | 1.000 |

5 | 2 | 2 | 1.00 | 2 | 1.00 | 2 | 1.00 | 1.414 |

6 | 3 | 3 | 1.00 | 3 | 1.00 | 3 | 1.00 | 1.442 |

7 | 7 | 7 | 1.00 | 7 | 1.00 | 7 | 1.00 | 1.627 |

8 | 21 | 13 | 1.62 | 14 | 1.50 | 16 | 1.31 | 1.741 |

9 | 49 | 25 | 1.96 | 29 | 1.69 | 33 | 1.48 | 1.791 |

10 | 165 | 47 | 3.51 | 53 | 3.11 | 62 | 2.66 | 1.803 |

11 | 552 | 81 | 6.81 | 93 | 5.94 | 116 | 4.76 | 1.812 |

12 | 2176 | 136 | 16.00 | 162 | 13.43 | 203 | 10.72 | 1.805 |

13 | 9988 | 234 | 42.68 | 271 | 36.86 | 342 | 29.20 | 1.792 |

14 | 46972 | 409 | 114.85 | 488 | 96.25 | 623 | 75.40 | 1.795 |

15 | 253293 | 722 | 350.82 | 855 | 296.25 | 1100 | 230.27 | 1.792 |

**How does the largest colouring number for knots with C crossings depend on C?**

_{max}then the following table shows that N

_{max}grows roughly by a factor of 1.7 when increasing C by 1.

Table 2: Table of B(C) = N

_{max}

^{1/(C−1)}

C | N_{max} |
knot | B(C) |
---|---|---|---|

3 | 3 | 3_{1} |
1.732 |

4 | 5 | 4_{1} |
1.710 |

5 | 7 | 5_{2} |
1.627 |

6 | 13 | 6_{3} |
1.670 |

7 | 19 | 7_{6} |
1.634 |

8 | 37 | 8_{17} |
1.675 |

9 | 61 | 9_{33} |
1.672 |

10 | 109 | 10_{115} |
1.684 |

11 | 199 | 11a_{301} |
1.698 |

12 | 353 | 12a_{1188} |
1.705 |

13 | 593 | 13a_{4620} |
1.703 |

14 | 1103 | 14a_{16476} |
1.714 |

15 | 1823 | 15a_{65606} |
1.710 |

**Is there a computer program that can compute colourings?**

`AsciiKnots`

is a computer program to compute for a given knot diagram all colouring numbers by computing the Smith Normal Form of the coefficient matrix. If the knot diagram has not too many crossings then it also computes by optimized trial and error search for a given colouring number all colourings or all colouring numbers including their colourings.Apart from colourings the program can compute much more. It can be downloaded from

`https://cariboutests.com/games/knots/AsciiKnots.tar.gz`

. `AsciiKnots`

runs under linux. Strict windows users can install Ubuntu linux for free as an application under Windows 10. Linux commands to remove old downloaded versions, to download the latest version, to unpack it and to start it are```
rm AsciiKnots.tar.gz
```

wget https://cariboutests.com/games/knots/AsciiKnots.tar.gz

tar xfz AsciiKnots.tar.gz

./AsciiKnots

A limited colouring functionality is also available on https://cariboutests.com/games/knots/knoteditor/ after selecting 'Tools' > 'Colour Knot'

**References**

[2] J. H. Przytycki, 3-coloring and other elementary invariants of knots. Banach Center Publications, Vol. 42, “Knot Theory”, Warszawa, 1998, 275−295.

[3] D. Rolfsen, Table of Knots and Links. Appendix C in Knots and Links. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.

[4] J. C. Cha and C. Livingston, KnotInfo: Table of Knot Invariants, http://www. indiana.edu/~knotinfo

[5] “Colour Classification of Knots with Crossing Number up to 15”, https:// cariboutests.com/qi/knots/colour3-15.txt

[6] T. Wolf, “A Knot Workbench”, https://cariboutests.com/games/knots/AsciiKnots.tar.gz

Follow or subscribe for updates: