Knot Colouring ©

គំនូសតាងពីរក្នុងចំណោមបីខាងក្រោម

មិនដឹង

ទូហ្សុន-ស៊ីកូរ៉ា

8_19

អាចត្រូវបានខូចទ្រង់ទ្រាយគ្នាទៅវិញទៅមកដោយមិនចាំបាច់កាត់ ខ្សែរចំណង ។

តើអ្នកគិតថាពួកគេជាអ្វី?

អ្នករៀនខាងក្រោមពីរបៀបប្រើពណ៌ដើម្បីប្រាប់ថាតើដ្យាក្រាមពីរជារបស់ ចំណង ផ្សេងគ្នា។ ដោយការសិក្សាលើពណ៌បី គេអាចមើលឃើញថាដ្យាក្រាមមួយណាដែលមិនអាចខូចទ្រង់ទ្រាយគ្នាទៅវិញទៅមក។
បើមិនដូច្នោះទេ លំដាប់ខាងក្រោមបង្ហាញពីរបៀបធ្វើឱ្យដ្យាក្រាម ទូហ្សុន-ស៊ីកូរ៉ាសាមញ្ញទៅជារង្វង់មួយ។

ភ័ស្តុតាងដែលថាដ្យាក្រាម ទូហ្សុន-ស៊ីកូរ៉ា គឺជាចំណុចមិនច្បាស់លាស់។

ដ្យាក្រាមដែលមិនចេះអក្សរ និង Tuzun-Sikora រួមជាមួយនឹងការខូចទ្រង់ទ្រាយផ្សេងទៀតជាច្រើនដែលគ្មានកំណត់ ជាកម្មសិទ្ធិរបស់គណិតសាស្ត្រដូចគ្នា ក្នុងករណីនេះ unknot ។ តើគេអាចសម្រេចចិត្តដោយរបៀបណាថាតើដ្យាក្រាមពីរមិនអាចខូចទ្រង់ទ្រាយគ្នាទៅវិញទៅមកបានទេ ទោះបីវាធំប៉ុណ្ណាក៏ដោយ? ទ្រព្យសម្បត្តិដែលមិនផ្លាស់ប្តូរនៅពេលដែលដ្យាក្រាមត្រូវបានខូច ត្រូវបានគេហៅថា 'invariant' (មិនប្រែប្រួល)។

ឧទាហរណ៏នៃ invariant គឺជាចំនួនតិចតួចបំផុតនៃការឆ្លងកាត់ដែលណាមួយនៃដ្យាក្រាមសមមូលជាច្រើនដែលគ្មានកំណត់អាចមាន។ វិចារណញាណនេះពិបាករកណាស់ ព្រោះគេមិនអាចពិនិត្យមើលដ្យាក្រាមច្រើនគ្មានកំណត់។

ប៉ុន្តែអ្វីដែលអាចជាអថេរដែលអាចគណនាបានសម្រាប់ដ្យាក្រាមដែលបានផ្តល់ឱ្យ? វាពិបាកក្នុងការស្រមៃមើលថាតើទ្រព្យសម្បត្តិណាដែលមិនផ្លាស់ប្តូរនៅក្នុងការខូចទ្រង់ទ្រាយនៅពេលដែលមនុស្សម្នាក់អាចខូចទ្រង់ទ្រាយដ្យាក្រាមតាមវិធីណាមួយដែលមនុស្សម្នាក់ចង់បាន។

ភាពមានពណ៌បីគឺជាអថេរ។

ដើម្បីពន្យល់វា យើងប្រើ strands ដែលជាផ្នែកនៃ knotline ដែលអាចគូរដោយមិនចាំបាច់លើកប៊ិច។ នៅច្រកឆ្លងកាត់នីមួយៗជួប 3 ខ្សែ មួយគឺឆ្លងកាត់និងមួយទៀតពីចំហៀង។ ដ្យាក្រាម knot មានបីពណ៌ ប្រសិនបើខ្សែនីមួយៗអាចត្រូវបានផ្តល់ពណ៌មួយក្នុងចំណោម 3 ពណ៌ ដូច្នេះនៅពេលឆ្លងកាត់នីមួយៗយើងមានពណ៌ 1 ឬ 3 មិនមែន 2 ពណ៌ទេ។ ការដាក់ពណ៌ទាំងអស់ជាមួយនឹងពណ៌តែមួយគឺតែងតែអាចធ្វើទៅបាន និងមិនរាប់បញ្ចូល។ យ៉ាងហោចណាស់ 2 ពណ៌ត្រូវប្រើនៅកន្លែងណាមួយ។

តើគំនូសតាងទាំង ៣ មួយណាអាចមានពណ៌បី?

Tri-colourability គឺជាវិចារណញាណខ្សោយ ព្រោះវាមានចំនួនព័ត៌មានតិចបំផុតដែលអាចធ្វើទៅបាន គ្រាន់តែបាទ/ចាស។ បំរែបំរួលនេះគ្រាន់តែអាចដាក់ knots ទាំងអស់ជាពីរក្រុម គឺ knots ដែលមានបីពណ៌ និង knots ដែលមិនមាន។

N - ភាពធន់នឹងពណ៌

យើងអាចបញ្ជាក់សេចក្តីថ្លែងការណ៍ទាំងអស់នៃនព្វន្ធម៉ូឌុលដោយការណែនាំមេគុណ k និងបង្កើតសមីការ ≡ ឡើងវិញជាសមីការធម្មតា។ ដើម្បីបង្រួមកំណត់ចំណាំ យើងប្រើ
'ចំនួនគត់' សម្រាប់ 'លេខទាំងមូល',
'pq' សម្រាប់ 'p ដង q',
'∃' សម្រាប់ 'មាន',
' : ' សម្រាប់ 'ជាមួយទ្រព្យសម្បត្តិ' និង
'A → B' សម្រាប់ 'ពី A តាម B' ។

បញ្ជាក់៖ ប្រសិនបើ ≡ b mod N និង c ≡ d mod N បន្ទាប់មក (a+c) ≡ (b+d) mod N

បញ្ជាក់៖ ប្រសិនបើ a ≡ b mod N បន្ទាប់មកសម្រាប់ចំនួនគត់ m យើងមាន ma ≡ mb mod N

បញ្ជាក់៖ ប្រសិនបើ ≡ b mod (PQ) បន្ទាប់មក ≡ b mod P ។

a ≡ b mod (PQ)
→ ∃ integer k: a = b + k(PQ)
→ ∃ ចំនួនគត់ k: a = b + k(PQ)
→ a ≡ b mod P

ចុះទិសដៅផ្ទុយវិញ?

ហេតុអ្វីបានជាអាចជឿបានថាការបញ្ច្រាសមិនពិត?

នៅក្នុងសមីការ mod N ភាគីទាំងពីរនៃ ≡ អាចមានតម្លៃ N ផ្សេងគ្នា។ នៅក្នុងម៉ូឌុលសមីការ (NM) ភាគីទាំងពីរនៃ ≡ អាចមានតម្លៃខុសគ្នា NM ។ ដូច្នេះ relation mod (NM) ផ្ទុកពត៌មានច្រើនជាង relation mod N ។ ការបោះព័ត៌មានទៅឆ្ងាយដោយចេញពី mod (NM) ទៅ mod N គឺងាយស្រួល ប៉ុន្តែការបញ្ច្រាសនៃការបង្កើតព័ត៌មានចេញពីគ្មានអ្វីគឺមិនអាចទៅរួចទេ។ និយាយដោយប្រយោល ក្នុងន័យនេះ សមភាពធម្មតាដោយប្រើ = គឺស្មើនឹង ≡ mod ∞(គ្មានកំណត់)។

ក្នុងនាមជាមតិយោបល់ចំហៀង នេះបើកលទ្ធភាពដែលថានៅក្នុងកម្មវិធីដែលដំណោះស្រាយពាក់ព័ន្ធនឹងចំនួនគត់ និងកន្លែងដែលមនុស្សម្នាក់កំពុងស្វែងរកដំណោះស្រាយក្នុងទម្រង់សមីការដោយប្រើ '=' និងកន្លែងដែលមនុស្សម្នាក់ដឹងថាមានព្រំដែនខាងលើសម្រាប់តម្លៃដាច់ខាត។ នៃលេខនៅក្នុងដំណោះស្រាយនោះ យុទ្ធសាស្ត្រមួយអាចចាប់ផ្តើមជាមួយនឹងការស្វែងរកដំណោះស្រាយ mod N សម្រាប់ចំនួនបឋមតូចៗ N ហើយបន្ទាប់មកដើម្បីគណនាអត្តសញ្ញាណ mod N^2 បន្ទាប់មក mod N^4 និងបន្តរហូតដល់ថាមពលរបស់ N គឺ ធំជាងព្រំដែនខាងលើ គេដឹងសម្រាប់ដំណោះស្រាយ ហើយបន្ទាប់មកគេអាចទម្លាក់ mod ហើយមានដំណោះស្រាយពិតប្រាកដដោយប្រើ = .

វិធីសាស្រ្តបែបនេះដែលហៅថា ការលើករបស់ Hensel អាចត្រូវបានប្រើដើម្បីបង្វែរពហុនាមឯកវចនៈជាមុនសិនដោយគោរពតាមចំនួនបឋមតូចៗមួយចំនួន ហើយចុងក្រោយគឺលើសចំនួនគត់។

បញ្ជាក់៖ a + b ≡ ((a mod N) + (b mod N)) mod 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.

When is ma ≡ mb mod N equivalent to a ≡ b mod N?

The Chinese Remainder Theorem.

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?

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

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

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

Is colourability mod 2 meaningful?

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

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)?

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.

Which value should one assign?

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.

Yes. Knots with less than 12 crossings that have no colouring are 10₁₂₄, 10₁₅₃, 11n₃₄, 11n₄₂, 11n₄₉, 11n₁₁₆ and, of course, the unknot. The figure shows a diagram of knot 10₁₂₄.

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.

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 12a₈₀₁.

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.

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.

# 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 strong is N-colouring as an invariant?

C	N_max	knot	B(C)
3	3	3₁	1.732
4	5	4₁	1.710
5	7	5₂	1.627
6	13	6₃	1.670
7	19	7₆	1.634
8	37	8₁₇	1.675
9	61	9₃₃	1.672
10	109	10₁₁₅	1.684
11	199	11a₃₀₁	1.698
12	353	12a₁₁₈₈	1.705
13	593	13a₄₆₂₀	1.703
14	1103	14a₁₆₄₇₆	1.714
15	1823	15a₆₅₆₀₆	1.710

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

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'

[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