300000
29177
14053
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский
14053
Knot Colouring
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
Two of the following three diagrams
can be deformed into each other without cutting the knotline.
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.
N-colourability
unknot
Tuzun-Sikora
8_19
can be deformed into each other without cutting the knotline.
Which do you think they are?
You learn below how to use colourability to tell whether two diagrams belong to different knots. By investigating tri-colourability one could see which diagrams can definitely not be deformed into each other.
Otherwise, the following sequence shows how to simplify the Tuzun-Sikora diagram to a circle.
Proof that the Tuzun-Sikora diagram is the unknot.
The unknotting diagram and Tuzun-Sikora together with infinitely many other deformations belong to the same mathematical knot, in this case, the unknot. How could one decide whether two diagrams could never be deformed into each other, no matter how large they grow inbetween? A property which does not change when the diagram is deformed is called 'invariant' (non-varying).Otherwise, the following sequence shows how to simplify the Tuzun-Sikora diagram to a circle.
Proof that the Tuzun-Sikora diagram is the unknot.
Initial projection
A Reidemeister 3 move
After the move and a stretch
A crossing reducing pass move
After the move and a stretch
A crossing reducing pass move
After the move and a stretch
A crossing reducing pass move
After the move and a stretch
A crossing reducing pass move
After the move and a stretch
A crossing reducing pass move
After the move
A crossing reducing pass move
After the move
A Reidemeister 2 move
After the move
A Reidemeister 1 move
After the move
A Reidemeister 1 move
After the move
A Reidemeister 1 move
After the move
A Reidemeister 1 move
After the move
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.
To explain it, we use strands which are parts of the knotline that can be drawn without lifting the pen. At each crossing meet 3 strands, one is the over-pass and one from each side. A knot diagram is tri-colourable if each strand can be given one of 3 colours so that at each crossing we have either 1 or 3 colours, not 2 colours. Colouring all with one colour is always possible and does not count. At least 2 colours need to be used somewhere.
Which of the 3 diagrams is tri-colourable?
The unknot has only one strand and is therefore not tri-colourable. The 2nd knot is deformable to the unknot and therefore also not colourable. We will prove that later. The other knot is tri-colourable and therefore can never be deformed to the unknot as shown above.
Tri-colourability is a weak invariant because it contains only the smallest possible amount of information, just a yes/no. This invariant is only able to put all knots into two groups, knots which are tri-colourable and those which are not.
N-colourability
A stronger invariant is N-Colourability where N colours are available and each colour represents one of the numbers 0,1,2,3,...,N-1. The condition to be satisfied at each crossing is that the sum of colours of the 2 under-strands minus 2 times the colour of the over-strand is a multiple of N. In other words, if the colours are a,b,c then there must be a multiplier k such that a+b-2c = kN. The mathematically equivalent but more common formulation is a + b ≡ 2c mod N. This means that both sides of the ≡ sign leave the same remainder in the division through N. Working modulo (mod) some number is called Modular Arithmetic and has a lot of interesting and useful rules.
Many questions come up.
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
The modular equation a ≡ b mod N says that a and b differ only by a multiple of p.
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
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
(a ≡ b mod N) → (∃ integer k: a = b + kN)
After multiplication with m we get
ma = mb + mkN
→ 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.
a ≡ b mod (PQ)
→ ∃ integer k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
What about the opposite direction?
Why is it plausible that the inverse is not true?
→ ∃ integer k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
What about the opposite direction?
Here is a counter example:
6 ≡ 1 mod 5 but
6 ≢ 1 mod 15 because 6 and 1 do not differ by a multiple of 15.
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
a and a mod N differ by a multiple of N: a = (a mod N) + pN
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
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
a and a mod N differ by a multiple of N: a = (a mod N) + pN
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
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
Each polynomial can be written as a sum of products, so applying the above two rules repeatedly proves the statement.
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?
We saw that from a ≡ b mod N follows ma ≡ mb mod N. We have equivalence if we can multiply with an integer k ≡ 1/m mod N. This means that after multipliction with m there exist an integer l such that mk = 1 + lN which Bézout's identity with 1 = GCD(m,N) (Greated Common Divisor of m,N), so m and N must be co-prime for equivalenve of ma ≡ mb mod N and a ≡ b mod N.
The Chinese Remainder Theorem.
We talked earlier about information content in a modular equation mod N to depend on N. Should it not be possible to combine two modular equations with smaller modular numbers to one with a larger number?
This is what the Chinese reminder theorem states.
If for the two equations
x ≡ a1 mod N1
x ≡ a2 mod N2
the divisors N1,N2 are co-prime, then there exists exactly one value for x up to multiples of p1p2 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 m1N1 + m2N2 = 1 by computing m1,m2 and then to use the formula
x = a1m2N2 + a2m1M1
= a1(1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
which shows x ≡ a1 mod N1 and equivalently x = a2 + (a1 - a2)m2N2 which shows x ≡ a2 mod N2.
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.
This is what the Chinese reminder theorem states.
If for the two equations
x ≡ a1 mod N1
x ≡ a2 mod N2
the divisors N1,N2 are co-prime, then there exists exactly one value for x up to multiples of p1p2 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 m1N1 + m2N2 = 1 by computing m1,m2 and then to use the formula
x = a1m2N2 + a2m1M1
= a1(1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
which shows x ≡ a1 mod N1 and equivalently x = a2 + (a1 - a2)m2N2 which shows x ≡ a2 mod N2.
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?
As explained earlier in the Unknotting Some Food for Thought > Introduction with Definitions > Reidemeister moves, the 3 Reidemeister moves are enough to perform any deformation of a knot diagram. Therefore, to be an invariant, one only needs to show that the property does not change under these 3 moves.
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.
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?
Each one of the colouring conditions has the form A + B ≡ 2C mod N. Let us write it as A - C ≡ C - B mod N.
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.
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?
No, for N=2 the colouring is trivial.
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.
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?
We saw above that either all colours are even or odd. If they are even then we can divide all of them by 2 and have without loss of information a colouring mod N. If they are all odd then we can add 1 to all colours and get an equivalent colouring where now all colours are even so we can drop a factor 2 and have an equivalent colouring mod N.
As a consequence, each colouring mod (2N) is equivalent to a coulouring mod N.
As a consequence, each colouring mod (2N) is equivalent to a coulouring mod N.
For which N is N-colourability useful and not trivial?
For odd N>1 colourability mod N is meaningful.
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)?
If N is a composite number, i.e. a product with both factors not being 1, then one can write it as N=PQ with P and Q being co-prime. Having a solution of the colouring conditions mod N gives us a colouring mod P by computing all colour values mod P and it gives us a colouring mod Q by computing all colour values mod Q. But what about the other direction? If a system of colouring conditions for a knot diagram has a solution mod P and another solution mod Q, where P and Q are co-prime, does this system of conditions then have a solution mod PQ?
Answer: Yes.
Proof:
Let a1, a2 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 ≡ a1 mod P
A ≡ a2 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 = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 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.
Answer: Yes.
Proof:
Let a1, a2 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 ≡ a1 mod P
A ≡ a2 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 = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 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?
Which letter should be given a value?
- 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 NC 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?
Yes. Knots with less than 12 crossings that have no colouring are 10124, 10153, 11n34, 11n42, 11n49, 11n116 and, of course, the unknot. The figure shows a diagram of knot 10124.
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.
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?
Yes, these additional invariants are the multiplicities of solutions, one multiplicity for each number of available colours. To understand the following comments some knowledge of linear algebra is useful.
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 12a801.
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.
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 12a801.
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?
The text file
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?
The following table shows how using more colouring invariants increases the number of invariant classes of knots and thus decreases the average number of knots per class. The right column shows how the (#cr - 3)'th root of the number of colouring invariant classes stays roughly constant, where #cr is the number of crossings of the knots.
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)
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?
If one takes all knots with crossing number C (<16) and finds from these knots the one with the highest colouring number Nmax then the following table shows that Nmax grows roughly by a factor of 1.7 when increasing C by 1.
Table 2: Table of B(C) = Nmax1/(C−1)
Table 2: Table of B(C) = Nmax1/(C−1)
| C | Nmax | knot | B(C) |
|---|---|---|---|
| 3 | 3 | 31 | 1.732 |
| 4 | 5 | 41 | 1.710 |
| 5 | 7 | 52 | 1.627 |
| 6 | 13 | 63 | 1.670 |
| 7 | 19 | 76 | 1.634 |
| 8 | 37 | 817 | 1.675 |
| 9 | 61 | 933 | 1.672 |
| 10 | 109 | 10115 | 1.684 |
| 11 | 199 | 11a301 | 1.698 |
| 12 | 353 | 12a1188 | 1.705 |
| 13 | 593 | 13a4620 | 1.703 |
| 14 | 1103 | 14a16476 | 1.714 |
| 15 | 1823 | 15a65606 | 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
[1] R. H. Fox, Metacyclic invariants of knots and links, Canadian Journal of Mathematics 22 (1970) 193−201.
[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
[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: