300000
24414
12216
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский
12216
Coloriage de Nœuds
Si vous vous intéressez seulement à comment résoudre ce défi et non par la théorie sous-jacente, veuillez vous dirigez vers la section « Quels sont les indices pour trouver une coloration par tâtonnements ? »
À propos des Invariants
Deux parmi les trois diagrammes suivants
peuvent être déformés les uns en les autres sans couper la ligne de nœud.
Un exemple d’invariant est le nombre minimal de croisements que n’importe lequel des diagrammes équivalents (d'un même noeud) infiniment nombreux peut avoir. Cet invariant est difficile à trouver car on ne peut pas vérifier une infinité de diagrammes.
Mais quel pourrait être un invariant qui peut être calculé pour tout diagramme donné? Il est difficile d’imaginer quelle propriété reste inchangé dans une déformation étant donné qu'on peut déformer un diagramme comme on veut.
La tricolorabilité est un invariant.
N-colorabilité
non-noeud
Tuzun-Sikora
8_19
peuvent être déformés les uns en les autres sans couper la ligne de nœud.
Que pensez-vous qu’ils sont?
Vous apprendrez ci-dessous comment utiliser la colorabilité pour savoir si deux diagrammes appartiennent à des nœuds différents. En étudiant la tricolorabilité, on pourrait voir quels diagrammes ne peuvent certainement pas être déformés les uns en les autres.
Sinon, la séquence suivante montre comment simplifier le diagramme de Tuzun-Sikora en un cercle.
Preuve que le diagramme de Tuzun-Sikora est le non-noeud.
Le diagramme du non-noeud et celui de Tuzun-Sikora ainsi qu’un nombre infini d’autres déformations appartiennent au même nœud mathématique, dans ce cas, le non-noeud. Comment pourrait-on décider si deux diagrammes ne pourraient jamais être déformés l’un en l’autre, quelle que soit leur taille et complexité? Une propriété qui ne change pas lorsque le diagramme est déformé est appelée 'invariant' (qui ne varie pas).Sinon, la séquence suivante montre comment simplifier le diagramme de Tuzun-Sikora en un cercle.
Preuve que le diagramme de Tuzun-Sikora est le non-noeud.
Projection initiale
Un mouvement Reidemeister 3
Après le mouvement et un élargissement
Un mouvement de passage qui réduit le nombre de croisements
Après le mouvement et un élargissement
Un mouvement de passage qui réduit le nombre de croisements
Après le mouvement et un élargissement
Un mouvement de passage qui réduit le nombre de croisements
Après le mouvement et un élargissement
Un mouvement de passage qui réduit le nombre de croisements
Après le mouvement et un élargissement
Un mouvement de passage qui réduit le nombre de croisements
Après le mouvement
Un mouvement de passage qui réduit le nombre de croisements
Après le mouvement
Un mouvement Reidemeister 2
Après le mouvement
Un mouvement Reidemeister 1
Après le mouvement
Un mouvement Reidemeister 1
Après le mouvement
Un mouvement Reidemeister 1
Après le mouvement
Un mouvement Reidemeister 1
Après le mouvement
Un exemple d’invariant est le nombre minimal de croisements que n’importe lequel des diagrammes équivalents (d'un même noeud) infiniment nombreux peut avoir. Cet invariant est difficile à trouver car on ne peut pas vérifier une infinité de diagrammes.
Mais quel pourrait être un invariant qui peut être calculé pour tout diagramme donné? Il est difficile d’imaginer quelle propriété reste inchangé dans une déformation étant donné qu'on peut déformer un diagramme comme on veut.
La tricolorabilité est un invariant.
Pour l’expliquer, on peut utiliser des brins qui font partie de la ligne de nœud qui peuvent être dessinées sans soulever son stylo. À chaque croisement se rencontrent 3 brins, un brin par-dessus et les deux autres de chaque côté. Un diagramme de nœuds est tricolore si chaque brin peut recevoir l’une parmi 3 couleurs de sorte qu’à chaque croisement, on a 1 ou 3 couleurs, et non 2 couleurs. La coloration avec une seule couleur est toujours possible et ne compte donc pas. Au moins 2 couleurs doivent être utilisées quelque part.
Lequel des 3 diagrammes est tricolorable ?
Le non-noeud n’a qu’un seul brin et n’est donc pas tricolorable. Le 2ème nœud est déformable au non-nœud et donc non plus colorable. On le prouvera plus tard. L’autre nœud est tricolore et ne peut donc jamais être déformé au non-nœud comme indiqué ci-dessus.
La tricolorabilité est un invariant faible parce qu’il ne contient que la plus petite quantité possible d’informations, juste un oui/non. Cet invariant permet de repartir les noeuds en deux groupes uniquement, les nœuds tricolorables et ceux qui ne le sont pas.
N-colorabilité
Un invariant plus fort est la N-Colorabilité où N couleurs sont disponibles et chaque couleur représente l’un des nombres 0,1,2,3,...,N-1. La condition à remplir à chaque croisement est que la somme des couleurs des 2 brins par-dessous moins 2 fois la couleur du brin par-dessus soit un multiple de N. Autrement dit, si les couleurs sont a,b,c alors il doit y avoir un multiplicateur k tel que a+b-2c = kN. La formulation mathématiquement équivalente mais la plus courante est a + b ≡ 2c mod N. Cela signifie que les deux côtés du signe ≡ laissent le même reste dans la division à travers N. Le fait d'effectuer modulo (mod) un certain nombre est appelé l'arithmétique modulaire et a beaucoup de règles intéressantes et utiles.
Du coup, de nombreuses questions se posent.
Du coup, de nombreuses questions se posent.
Introduction à l’arithmétique modulaire
On peut prouver toutes les assertions de l’arithmétique modulaire en introduisant un multiplicateur k et en reformulant l’équation ≡ comme une équation normale. Pour raccourcir la notation, on utilisera
« entier » pour « nombre entier »,
« pq » pour « p fois q »,
« ∃ » pour « Il existe »,
« : » pour « avec la propriété », et
« A → B » pour « de A suit B ».
Démonstration : si a ≡ b mod N et c ≡ d mod N alors (a+c) ≡ (b+d) mod N
L’équation modulaire a ≡ b mod N dit que a et b ne diffèrent que par un multiple de p.
c’est-à-dire qu’il doit exister un multiplicateur m avec la propriété a = b + mp. En bref, c’est
(a ≡ b mod N) → (∃ entier m : a = b + mp)
(c ≡ d mod N) → (∃ entier n: c = d + np)
En additionnant les deux équations, on obtient a + c = b + mp + d + np = b + d + (m + n)p
→ a + c ≡ (b + d) mod N
c’est-à-dire qu’il doit exister un multiplicateur m avec la propriété a = b + mp. En bref, c’est
(a ≡ b mod N) → (∃ entier m : a = b + mp)
(c ≡ d mod N) → (∃ entier n: c = d + np)
En additionnant les deux équations, on obtient a + c = b + mp + d + np = b + d + (m + n)p
→ a + c ≡ (b + d) mod N
Démonstration : si a ≡ b mod N alors pour tout entier m on a ma ≡ mb mod N
(a ≡ b mod N) → (∃ entier k : a = b + kN)
Après multiplication avec m, on obtient
ma = mb + mkN
→ ma ≡ mb mod N
Après multiplication avec m, on obtient
ma = mb + mkN
→ ma ≡ mb mod N
Démonstration : si un mod ≡ b (PQ) alors a mod ≡ b P.
a ≡ b mod (PQ)
→ ∃ entier k : a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
Qu’en est-il du sens inverse ?
Pourquoi est-il plausible que l’inverse ne soit pas vrai ?
→ ∃ entier k : a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
Qu’en est-il du sens inverse ?
Voici un contre-exemple :
6 ≡ 1 mod 5 mais
6 ≢ 1 mod 15 car 6 et 1 ne diffèrent pas d’un multiple de 15.
6 ≡ 1 mod 5 mais
6 ≢ 1 mod 15 car 6 et 1 ne diffèrent pas d’un multiple de 15.
Pourquoi est-il plausible que l’inverse ne soit pas vrai ?
Dans une équation mod N les deux côtés de ≡ peuvent avoir N valeurs différentes. Dans un mod d’équation (NM), les deux côtés de ≡ peuvent avoir des valeurs NM différentes. Par conséquent, un mod de relation (NM) contient plus d’informations qu’une relation mod N. Le fait de perdre des informations en passant de mod (NM) vers mod N est facile, mais l’inverse, le fait de créer des informations à partir de rien, est impossible. En gros, dans ce sens, une égalité normale utilisant = équivaut à ≡ mod ∞(infini).
En passant, cela ouvre la possibilité que dans les applications où la solution implique des nombres entiers et où l’on cherche une solution sous la forme d’une équation utilisant un '=' et où l’on sait qu’il existe une limite supérieure pour la valeur absolue des nombres dans la solution, alors une stratégie peut être de commencer par trouver une solution mod N pour un petit nombre premier N, puis de calculer l’identité mod N^2, puis mod N^4 et ainsi de suite jusqu’à ce que la puissance de N soit plus grande que la limite supérieure que l’on connaît pour la solution et alors on peut laisser tomber le mod et avoir la solution exacte en utilisant = .
Une telle méthode, appelée le lemme de Hensel, peut être utilisée pour factoriser des polynômes univariés d’abord par rapport à un petit nombre premier, puis finalement précisément sur les entiers.
Démonstration : a + b ≡ ((a mod N) + (b mod N)) mod N
a et a mod N diffèrent par un multiple de N: a = (un mod N) + pN
b et b mod N diffèrent par un multiple de 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 et b mod N diffèrent par un multiple de 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
Démonstration : ab ≡ ((a mod N)(b mod N)) mod N
a et a mod N diffèrent par un multiple de N: a = (un mod N) + pN
b et b mod N diffèrent par un multiple de 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 et b mod N diffèrent par un multiple de 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
Démonstration : si P(x,y,...) est un polynôme dans les variables x,y,... alors P(x,y,...) ≡ P((x mod N),(y mod N),...) mod N
Chaque polynôme peut être écrit comme une somme de produits, donc l’application des deux règles ci-dessus à plusieurs reprises prouve l’assertion.
Démonstration : En arithmétique modulaire modulo un nombre premier, les divisions par les entiers donnent à nouveau des entiers.
On commence par démontrer que pour un nombre premier p et tout entier a ≢ 0 mod N, l’inverse 1/a mod N est aussi un entier. On a besoin d’un ≢ 0 mod N car aussi en arithmétique modulaire, la division par zéro n’est pas possible.
Soit u ≡ 1/a mod N. Pour que u soit l’inverse de a mod N signifie que
ua ≡ 1 mod N
→ ∃ entier k : ua = 1 + kp
Ceci a la forme de l’identité de Bézout : ua + vp = GCD(a,p) où GCD(a,p) est le plus grand commun diviseur de a,p et où v=-k. Parce que p est un nombre premier et que a n’est pas un multiple de p donc GCD(a,p)=1.
Les multiplicateurs u,v dans l’identité de Bézout peuvent être calculés par l’algorithme euclidien étendu et u,v, sont tous les deux entiers.
Si u = 1 / a est un mod entier N alors b / a = bu est aussi un entier mod N qui sera montré.
Exemple : 1/3 ≡ 5 mod 7 car 1 = 3(1/3) ≡ 3(5) = 15 = 2(7) + 1 ≡ 1 mod 7.
Quand ma ≡ mb mod N est-il équivalent à un ≡ b mod N ?
Nous avons vu que d’un ≡ b mod N suit ma ≡ mb mod N. Nous avons équivalence si nous pouvons multiplier par un entier k ≡ 1/m mod N. Cela signifie qu’après multiplication avec m il existe un entier l tel que mk = 1 + lN dont l’identité de Bézout avec 1 = GCD(m,N) (Diviseur commun cupidé de m,N), donc m et N doivent être co-premiers pour l’équivalence de ma ≡ mb mod N et a ≡ b mod N.
Le théorème du reste chinois.
Plus tôt, on parlé des informations contenues dans une équation modulaire mod N dépendant de N. Ne devrait-il pas être possible de combiner deux équations modulaires avec des nombres modulaires plus petits en une seule équation modulaire avec un nombre plus grand?
C’est ce que dit le Théorème des Restes chinois.
Si pour les deux équations
x ≡ a 1 mod N1
x ≡ unmod 2 N2
les diviseursN1,N2 sont co-premiers, alors il existe exactement une valeur pour x jusqu’à des multiples de p1p2 qui satisfait les deux équations modulaires.
Une façon d’obtenir la solution est d’utiliser l’algorithme euclidien étendu pour résoudre l’identité de Bézout m 1 N 1 + m 2 N 2 = 1 en calculant m 1,m2puis d’utiliser la formule
x = a 1 m 2N2 + a2m 1 M1
= a 1(1 - m 1 N 1) + a2m 1 N 1
= a 1 + (a2 - a 1)m 1 N 1
qui montre x ≡ un 1 mod N1 et de manière équivalente x = a 2 + (a1 - a 2)m 2 N 2 qui montre x ≡ unmod 2 N 2.
Si l’on a plus de deux équations modulaires, on peut en remplacer deux par une jusqu’à ce que l’on ait la solution sous la forme d’une équation modulaire. Dans chaque remplacement, le nouveau nombre diviseur croît en devenant le produit des deux diviseurs des équations fusionnées.
C’est ce que dit le Théorème des Restes chinois.
Si pour les deux équations
x ≡ a 1 mod N1
x ≡ unmod 2 N2
les diviseursN1,N2 sont co-premiers, alors il existe exactement une valeur pour x jusqu’à des multiples de p1p2 qui satisfait les deux équations modulaires.
Une façon d’obtenir la solution est d’utiliser l’algorithme euclidien étendu pour résoudre l’identité de Bézout m 1 N 1 + m 2 N 2 = 1 en calculant m 1,m2puis d’utiliser la formule
x = a 1 m 2N2 + a2m 1 M1
= a 1(1 - m 1 N 1) + a2m 1 N 1
= a 1 + (a2 - a 1)m 1 N 1
qui montre x ≡ un 1 mod N1 et de manière équivalente x = a 2 + (a1 - a 2)m 2 N 2 qui montre x ≡ unmod 2 N 2.
Si l’on a plus de deux équations modulaires, on peut en remplacer deux par une jusqu’à ce que l’on ait la solution sous la forme d’une équation modulaire. Dans chaque remplacement, le nouveau nombre diviseur croît en devenant le produit des deux diviseurs des équations fusionnées.
Comment prouver que la N-colorabilité est un invariant ?
Comme nous l’avons expliqué précédemment dans Défaire le Noeud > De la Matière à Réflexion > Introduction et définitions > Mouvements de Reidemeister, les 3 mouvements de Reidemeister sont suffisants pour effectuer n’importe quelle déformation d’un diagramme de nœud. Par conséquent, pour être un invariant, il suffit de montrer que la propriété ne change pas sous ces 3 mouvements.
Comment peut-on montrer qu’un mouvement Reidemeister 1 ne change pas la colorabilité ?
Si les couleurs des brins sont A et B comme indiqué, alors la condition de coloration nécessite dans la figure de gauche A + B ≡ 2B mod N et dans la figure droite B + A ≡ 2A mod N. Dans les deux cas, B = A est une solution :
Cela signifie que l’exécution d’un mouvement Reidemeister 1 ne change pas la colorabilité.
Comment peut-on montrer qu’un mouvement Reidemeister 2 ne change pas la colorabilité ?
Si les couleurs des brins sont A, B et C comme indiqué, alors C est déterminé de manière unique à partir de la condition B + C ≡ 2A mod N dans la figure de gauche donc C ≡ (2A - B mod N) et dans la figure de droite A + C ≡ 2B mod N donc C ≡ (2B - A mod N). Cela détermine la couleur du nouveau brin lors de l’exécution d’un mouvement Reidemeister 2. La colorabilité n’est pas affectée.
Comment peut-on montrer qu’un mouvement Reidemeister 3 ne change pas la colorabilité ?
Si les couleurs des brins sont A, B, C, D, E, F et G comme indiqué, les trois conditions à gauche sont
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
En éliminant le brin interne F, la condition sur les brins externes est
2D - E ≡ 2C - B mod N qui, en utilisant A + D ≡ 2C mod N ce qui se réduit en
2D - E ≡ A + D - B mod N et donc A - B - D + E ≡ 0 mod N.
Les 3 conditions à droite sont
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
En éliminant le brin interne G, la condition sur les brins externes est
2C - E ≡ 2A - B mod N ce qui, en utilisant 2C ≡ A + D mod N se réduit en
A + D - E ≡ 2A - B mod N et donc 0 ≡ A - B - D + E mod N.
F et G sont calculés à partir de l’une des relations dans lesquelles ils apparaissent.
Nous concluons que pour les deux diagrammes les conditions sur les couleurs des brins extérieurs sont les mêmes: A + D ≡ 2C mod N et A - B - D + E ≡ 0 mod N.
Par conséquent, soit les deux diagrammes ont ou aucun d’entre eux n’a de coloration et donc la colorabilité est invariante sous les mouvements Reidemeister 3.
Comment peut-on montrer qu’un mouvement Reidemeister 1 ne change pas la colorabilité ?
Si les couleurs des brins sont A et B comme indiqué, alors la condition de coloration nécessite dans la figure de gauche A + B ≡ 2B mod N et dans la figure droite B + A ≡ 2A mod N. Dans les deux cas, B = A est une solution :
Cela signifie que l’exécution d’un mouvement Reidemeister 1 ne change pas la colorabilité.
Comment peut-on montrer qu’un mouvement Reidemeister 2 ne change pas la colorabilité ?
Si les couleurs des brins sont A, B et C comme indiqué, alors C est déterminé de manière unique à partir de la condition B + C ≡ 2A mod N dans la figure de gauche donc C ≡ (2A - B mod N) et dans la figure de droite A + C ≡ 2B mod N donc C ≡ (2B - A mod N). Cela détermine la couleur du nouveau brin lors de l’exécution d’un mouvement Reidemeister 2. La colorabilité n’est pas affectée.
Comment peut-on montrer qu’un mouvement Reidemeister 3 ne change pas la colorabilité ?
Si les couleurs des brins sont A, B, C, D, E, F et G comme indiqué, les trois conditions à gauche sont
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
En éliminant le brin interne F, la condition sur les brins externes est
2D - E ≡ 2C - B mod N qui, en utilisant A + D ≡ 2C mod N ce qui se réduit en
2D - E ≡ A + D - B mod N et donc A - B - D + E ≡ 0 mod N.
Les 3 conditions à droite sont
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
En éliminant le brin interne G, la condition sur les brins externes est
2C - E ≡ 2A - B mod N ce qui, en utilisant 2C ≡ A + D mod N se réduit en
A + D - E ≡ 2A - B mod N et donc 0 ≡ A - B - D + E mod N.
F et G sont calculés à partir de l’une des relations dans lesquelles ils apparaissent.
Nous concluons que pour les deux diagrammes les conditions sur les couleurs des brins extérieurs sont les mêmes: A + D ≡ 2C mod N et A - B - D + E ≡ 0 mod N.
Par conséquent, soit les deux diagrammes ont ou aucun d’entre eux n’a de coloration et donc la colorabilité est invariante sous les mouvements Reidemeister 3.
La trivialité, l'équivalence et l'indépendance de la coloration
Si l’on a une coloration, quelles autres colorations peut-on en obtenir pour n’importe quel diagramme de nœuds?
Chacune des conditions de coloration a la forme A + B ≡ 2C mod N. On peut l'écrire sous la forme A - C ≡ C - B mod N.
1) En ajoutant la même constante, disons S, à chaque couleur, les différences ne changent pas:
(A+S) - (C+S) = A - C+S - S = A - C et
(C+S) - (B+S) = C - B+S - S = C - B et
Les conditions sont donc toujours remplies.
2) Nous avons vu plus haut comme règle de l’arithmétique modulaire que nous pouvons multiplier les deux côtés de ≡ avec un nombre co-premier à N et obtenir une solution équivalente du système d’équations et donc une coloration équivalente.
1) En ajoutant la même constante, disons S, à chaque couleur, les différences ne changent pas:
(A+S) - (C+S) = A - C+S - S = A - C et
(C+S) - (B+S) = C - B+S - S = C - B et
Les conditions sont donc toujours remplies.
2) Nous avons vu plus haut comme règle de l’arithmétique modulaire que nous pouvons multiplier les deux côtés de ≡ avec un nombre co-premier à N et obtenir une solution équivalente du système d’équations et donc une coloration équivalente.
La colorabilité mod 2 a-t-elle un sens ?
Non, pour N=2, la coloration est triviale.
Commençons par un brin de couleur A qui continue comme brin B après avoir traversé sous le premier brin par-dessus de couleur C. Ensuite, A, B, C sont liés par A + B ≡ 2C mod 2 et après avoir ajouté B des deux côtés A ≡ B mod 2 parce que 2B ≡ 2C ≡ 0 mod 2. Si l’on poursuit ce raisonnement à tous les croisements, il s’ensuit que tous les brins ont soit une couleur paire (0), soit une couleur impaire (1). Cela donne une coloration triviale.
Commençons par un brin de couleur A qui continue comme brin B après avoir traversé sous le premier brin par-dessus de couleur C. Ensuite, A, B, C sont liés par A + B ≡ 2C mod 2 et après avoir ajouté B des deux côtés A ≡ B mod 2 parce que 2B ≡ 2C ≡ 0 mod 2. Si l’on poursuit ce raisonnement à tous les croisements, il s’ensuit que tous les brins ont soit une couleur paire (0), soit une couleur impaire (1). Cela donne une coloration triviale.
Qu’en est-il du mod de colorabilité (2N), c’est-à-dire modulo un nombre pair?
Nous avons vu plus haut que toutes les couleurs sont paires ou impaires. S’ils sont pairs, nous pouvons les diviser tous par 2 et sans perte d’information obtenir un mod de coloration N. Si elles sont toutes impaires, nous pouvons ajouter 1 à toutes les couleurs et obtenir une coloration équivalente où maintenant toutes les couleurs sont égales afin que nous puissions laisser tomber un facteur 2 et avoir un mod de coloration équivalent N.
En conséquence, chaque coloration mod (2N) est équivalente à une coloration mod N.
En conséquence, chaque coloration mod (2N) est équivalente à une coloration mod N.
Pour quel N la colorabilité N est-elle utile et non triviale ?
Pour les impairs N>1 colorabilité mod N est significatif.
Est-il suffisant de connaître toutes les colorations mod P et mod Q où P et Q sont co-premiers pour connaître toutes les colorations mod (PQ)?
Si N est un nombre composé, c’est-à-dire un produit dont les deux facteurs ne sont pas 1, alors on peut l’écrire comme N=PQ avec P et Q étant co-premiers. Avoir une solution des conditions de coloration mod N nous donne un mod de coloration P en calculant toutes les valeurs de couleur mod P et cela nous donne une coloration mod Q en calculant toutes les valeurs de couleur mod Q. Mais qu’en est-il de l’autre sens? Si un système de conditions de coloration pour un diagramme de nœuds a une solution mod P et une autre solution mod Q, où P et Q sont co-premiers, ce système de conditions a-t-il alors une solution mod PQ?
Réponse : Oui.
Démonstration :
Soit a1, a2 les couleurs d’un brin dans les colorations mod P et mod Q.
Le théorème des restes chinois garantit alors l’existence et l’unicité d’un entier A mod PQ qui satisfait aux deux conditions
A ≡ amod 1 P
A ≡ amod 2 Q.
Ceci peut être répété pour chaque brin en donnant les valeurs de couleur A, B, C,... mod PQ.
A chaque croisement, les deux conditions de coloration
(A + B - 2C) mod P = a 1 + b 1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a 2 + b 2 - 2c2 ≡ 0 mod Q
sont satisfaites. La seule valeur de (A + B - 2C) mod PQ qui est zéro mod P et est zéro mod Q est A + B - 2C ≡ 0 mod PQ. Cela montre que les valeurs de couleur A, B, C,... fournissent une coloration mod PQ.
Parce que tous les entiers positifs ont une factorisation première, ils peuvent être écrits comme des produits de puissances de nombres premiers. On peut donc trouver tous les nombres de coloration en n’étudiant que toutes les puissances de tous les nombres premiers impairs comme nombre de coloration. Nous avons vu plus haut que le nombre premier 2 et les puissances de 2 ne sont pas des nombres de coloration possibles.
On commencerait à vérifier l’existence d’une coloration modulo un nombre premier et, en cas de succès, on répéterait la vérification avec des puissances de plus en plus élevées de ce nombre premier jusqu’à ce qu’il n’y ait plus de coloration possible.
Réponse : Oui.
Démonstration :
Soit a1, a2 les couleurs d’un brin dans les colorations mod P et mod Q.
Le théorème des restes chinois garantit alors l’existence et l’unicité d’un entier A mod PQ qui satisfait aux deux conditions
A ≡ amod 1 P
A ≡ amod 2 Q.
Ceci peut être répété pour chaque brin en donnant les valeurs de couleur A, B, C,... mod PQ.
A chaque croisement, les deux conditions de coloration
(A + B - 2C) mod P = a 1 + b 1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a 2 + b 2 - 2c2 ≡ 0 mod Q
sont satisfaites. La seule valeur de (A + B - 2C) mod PQ qui est zéro mod P et est zéro mod Q est A + B - 2C ≡ 0 mod PQ. Cela montre que les valeurs de couleur A, B, C,... fournissent une coloration mod PQ.
Parce que tous les entiers positifs ont une factorisation première, ils peuvent être écrits comme des produits de puissances de nombres premiers. On peut donc trouver tous les nombres de coloration en n’étudiant que toutes les puissances de tous les nombres premiers impairs comme nombre de coloration. Nous avons vu plus haut que le nombre premier 2 et les puissances de 2 ne sont pas des nombres de coloration possibles.
On commencerait à vérifier l’existence d’une coloration modulo un nombre premier et, en cas de succès, on répéterait la vérification avec des puissances de plus en plus élevées de ce nombre premier jusqu’à ce qu’il n’y ait plus de coloration possible.
Quels sont les indices pour trouver une coloration par tâtonnements ?
À quelle lettre faut-il attribuer une valeur?
- Pour décider quel brin colorer ensuite, appuyez sur Entrée pour trier les équations en fonction de leur nombre de lettres, c’est-à-dire par urgence.
- Si une équation comporte plusieurs lettres, choisissez-en une qui se produit dans la plupart des autres équations afin que plus d’équations simplifient l’attribution d’un nombre. De manière équivalente, déplacez la souris sur l’équation, voyez le croisement encerclé et à ce croisement, cliquez sur le brin non coloré qui a le plus de passages par-dessus.
- Les lettres sur le côté droit de ≡ sont plus rapides à calculer que les lettres sur le côté gauche. Pour calculer une lettre à gauche, il faut diviser par 2, ce qui peut nécessiter d’ajouter N à droite pour qu'il devienne pair. Ce n’est pas difficile, mais dans un concours, le temps est précieux. Pour la même raison, lorsque l’on devine la valeur d’une lettre, on peut prendre une lettre à gauche d’un ≡.
- Pour gagner du temps, ne vous souciez pas de calculer des valeurs dans l’intervalle 0..N−1. Les valeurs peuvent être négatives ou arbitrairement grandes. S’ils sont corrects, une équation violette devient verte et c’est tout ce qui compte.
- Si une équation n’a plus qu’une lettre restante, l’arrière-plan est violet et il n’y a pas de choix, la valeur doit être calculée pour rendre l’équation verte. Voir les exemples dans les instructions.
- Comme indiqué ci-dessus dans Cette section > « Si l’on a une coloration... » , les valeurs de toutes les lettres peuvent être décalées de la même valeur constante. Par conséquent, la toute première lettre que l’on veut attribuer peut recevoir la valeur 0 sans perte de généralité. On n’essaiera aucune autre valeur pour cette lettre parce qu’on pourrait toujours décaler cette valeur à zéro.
- Pour que la 2ème lettre soit colorée, il suffit de considérer deux cas: 1) elle a la même valeur que la première lettre, c’est-à-dire 0, et 2) elle a une valeur différente. Dans ce cas, il suffit de considérer 1 car nous avons vu que tous les nombres pouvaient être multipliés par 2...(N-1) (où N est le nombre premier de couleurs disponibles) et ont toujours une solution équivalente. Pour plus d'informations veuillez revisiter Cette section > « Si l’on a une coloration... ». Par exemple, si N = 5 et que l’on aurait essayé une valeur différente pour la 2ème lettre assignée, disons 3 et que l’on aurait obtenu une solution, alors multiplier cette valeur (et toutes les autres valeurs) par 2 rendra le 3 à 3×2 = 6 ≡ 1 mod 5 donc à un 1. Par conséquent, il ne reste qu'à essayer 0 et 1 pour la 2ème.
- Les tests sont aussi une question de temps. On peut gagner du temps en saississant des nombres négatifs lorsqu’ils sont plus rapides à calculer que les nombres positifs. L’interface n’a pas besoin de nombres compris entre 0..N-1.
- Lorsqu’une équation devient rouge, la condition ≡ n’est pas satisfaite et au moins un nombre doit être modifié. Ensuite, essayez un autre nombre. Afin de ne pas manquer de nombres, on peut essayer des nombres de l’ordre 0,1,...,N-1 et s’arrêter lorsqu’une coloration est trouvée.
- Lorsque vous revenez en arrière en cliquant sur le bouton d’annulation, si l’on voit une équation violette, on peut cliquer à nouveau sur le bouton d’annulation sans réfléchir. La raison en est que l’équation violette n’a qu’une seule lettre et pour cette lettre, il n’y a qu’une seule valeur possible (mod N), donc aucune autre valeur ne doit être essayée pour cette lettre dans cette situation.
- Pour effectuer une recherche systématique et ne manquer aucune possibilité de coloration, on pourrait commencer par attribuer à chaque variable la valeur 0 qui donne la solution triviale et ensuite commencer à revenir en arrière pour obtenir une solution non triviale.
- Les diagrammes de nœuds utilisés dans ce jeu ont déjà un nombre minimal de croisements. Mais si les diagrammes ne sont pas minimeisés, il serait avantageux de les simplifier d’abord. Sans les techniques d’accélération ci-dessus, il faudrait essayer les colorations NC où N est le nombre de couleurs et C est le nombre de croisements = nombre de brins. Réduire le nombre de croisements de seulement 1 diminue l’effort d’un FACTEUR de N.
Y a-t-il des nœuds qui ne peuvent pas être colorés?
Oui. Les nœuds avec moins de 12 croisements qui n’ont pas de coloration sont 10124, 10153, 11n34, 11n42, 11n49, 11n116 et, bien sûr, le non-noeud. La figure montre un diagramme du nœud 10124.
Le diagramme intitulé « Tuzun-Sikora » en haut de la page n’est qu’un des nombreux diagrammes du nœud noué et n’est donc pas non plus colorable.
Le diagramme intitulé « Tuzun-Sikora » en haut de la page n’est qu’un des nombreux diagrammes du nœud noué et n’est donc pas non plus colorable.
Y a-t-il encore plus d’invariants de couleur et comment peuvent-ils être calculés ?
Oui, ces invariants supplémentaires sont les multiplicités des solutions, une multiplicité pour chaque nombre de couleurs disponibles. Pour comprendre les commentaires suivants, une certaine connaissance de l’algèbre linéaire est utile.
Si un diagramme de nœuds a C croisements, alors il a aussi des C brins et donc le système de conditions a une matrice de coefficients C×C où chaque ligne représente un croisement et se compose soit de deux -1 et un 2, soit d’un +1 et d’un -1 (croisement en boucle Reidemeister 1). Chaque colonne correspond à un brin et a autant de 2s que le brin a de passages par-dessus et a soit deux -1 soit un -1 et un +1.
Les conditions forment un système linéaire homogène (le côté droit ne contient que des 0) et la question consiste à trouver des nombres de coloration modulo pour lesquelles des solutions linéaires indépendantes non triviales (colorations) existent.
Comme en algèbre linéaire, la matrice est mise en diagonale en permutant des lignes et en ajoutant des multiples de lignes à d’autres lignes. De plus, ces étapes sont également effectuées avec des colonnes. Ce qui n’est pas permis ici, c’est de multiplier les lignes et les colonnes par un nombre parce que cela ajouterait un nombre de couleur modulo dont le déterminant de la matrice serait zéro et qui ajouterait une coloration supplémentaire. Ce qui est fait à la place est de choisir à plusieurs reprises 2 composantes non nulles d’une colonne / ligne, disons A, B, pour utiliser l’algorithme d’Euclide étendu pour trouver p, q, satisfaisant pA + qB = GCD (A, B). Les nombres p,q sont les multiplicateurs des deux rangées/colonnes. Après l’inversion des rangées/colonnes, le GCD(A,B) devient l’élément diagonal. Le résultat est une matrice diagonale appelée Smith Normal Form où généralement le coin supérieur gauche commence par des 1s suivis de nombres qui sont chacun le facteur du nombre suivant dans la diagonale. Le dernier élément diagonal est nul car chaque diagramme de nœud permet la coloration triviale en utilisant une seule couleur. Par conséquent, il suffit de calculer la Smith Normal Form après avoir laissé tomber une colonne et une rangée.
Le calcul du déterminant de la matrice des coefficients C×C donne zéro parce que les colonnes s’additionnent à zéro. Le calcul du déterminant après avoir perdu une rangée et une colonne donne un nombre qui est le produit des nombres sur la diagonale de la Smith Normal Form. Ainsi, la Smith Normal Form donne plus d’informations pour à peu près le même effort.
Exemple : Pour ce diagramme avec 83 croisements, la matrice des coefficients a une taille de 83×83.
La Smith Normal Form a une diagonale commençant dans le coin supérieur gauche avec 79 fois a 1 suivis de 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Cela signifie qu’il existe trois colorations indépendantes à 3 couleurs et une coloration 85837301265, ce qui implique qu’il y a également une coloration 5, une coloration 15, et des colorations 3x5722486751 et 5x5722486751.
Si un diagramme n’a pas de coloration, tous les nombres diagonaux sont 1 sauf le 0 en dernière position.
Le diagramme suivant appartient au nœud 12a801.
La Smith Normal Form (SNF) a dans la diagonale neuf 1s, suivis de 3,45,0. Dans cette forme, chaque nombre est un facteur du nombre diagonal suivant. Et la multiplicité d’une coloration est le nombre d’éléments diagonaux dans lesquels elle se produit en tant que facteur. Par conséquent, chaque diagramme de ce nœud a deux 3 colorations indépendantes et une seule coloration 45, ce qui implique qu’il a également une seule coloration 5, 9 et 15.
Si un diagramme de nœuds a C croisements, alors il a aussi des C brins et donc le système de conditions a une matrice de coefficients C×C où chaque ligne représente un croisement et se compose soit de deux -1 et un 2, soit d’un +1 et d’un -1 (croisement en boucle Reidemeister 1). Chaque colonne correspond à un brin et a autant de 2s que le brin a de passages par-dessus et a soit deux -1 soit un -1 et un +1.
Les conditions forment un système linéaire homogène (le côté droit ne contient que des 0) et la question consiste à trouver des nombres de coloration modulo pour lesquelles des solutions linéaires indépendantes non triviales (colorations) existent.
Comme en algèbre linéaire, la matrice est mise en diagonale en permutant des lignes et en ajoutant des multiples de lignes à d’autres lignes. De plus, ces étapes sont également effectuées avec des colonnes. Ce qui n’est pas permis ici, c’est de multiplier les lignes et les colonnes par un nombre parce que cela ajouterait un nombre de couleur modulo dont le déterminant de la matrice serait zéro et qui ajouterait une coloration supplémentaire. Ce qui est fait à la place est de choisir à plusieurs reprises 2 composantes non nulles d’une colonne / ligne, disons A, B, pour utiliser l’algorithme d’Euclide étendu pour trouver p, q, satisfaisant pA + qB = GCD (A, B). Les nombres p,q sont les multiplicateurs des deux rangées/colonnes. Après l’inversion des rangées/colonnes, le GCD(A,B) devient l’élément diagonal. Le résultat est une matrice diagonale appelée Smith Normal Form où généralement le coin supérieur gauche commence par des 1s suivis de nombres qui sont chacun le facteur du nombre suivant dans la diagonale. Le dernier élément diagonal est nul car chaque diagramme de nœud permet la coloration triviale en utilisant une seule couleur. Par conséquent, il suffit de calculer la Smith Normal Form après avoir laissé tomber une colonne et une rangée.
Le calcul du déterminant de la matrice des coefficients C×C donne zéro parce que les colonnes s’additionnent à zéro. Le calcul du déterminant après avoir perdu une rangée et une colonne donne un nombre qui est le produit des nombres sur la diagonale de la Smith Normal Form. Ainsi, la Smith Normal Form donne plus d’informations pour à peu près le même effort.
Exemple : Pour ce diagramme avec 83 croisements, la matrice des coefficients a une taille de 83×83.
La Smith Normal Form a une diagonale commençant dans le coin supérieur gauche avec 79 fois a 1 suivis de 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Cela signifie qu’il existe trois colorations indépendantes à 3 couleurs et une coloration 85837301265, ce qui implique qu’il y a également une coloration 5, une coloration 15, et des colorations 3x5722486751 et 5x5722486751.
Si un diagramme n’a pas de coloration, tous les nombres diagonaux sont 1 sauf le 0 en dernière position.
Le diagramme suivant appartient au nœud 12a801.
La Smith Normal Form (SNF) a dans la diagonale neuf 1s, suivis de 3,45,0. Dans cette forme, chaque nombre est un facteur du nombre diagonal suivant. Et la multiplicité d’une coloration est le nombre d’éléments diagonaux dans lesquels elle se produit en tant que facteur. Par conséquent, chaque diagramme de ce nœud a deux 3 colorations indépendantes et une seule coloration 45, ce qui implique qu’il a également une seule coloration 5, 9 et 15.
Statistiques des colorations de nœuds
Y a-t-il un aperçu des colorations possibles des nœuds primaires jusqu’à une certaine taille?
Le fichier texte
https://cariboutests.com/qi/knots/colour3-15-N.txt répertorie pour chaque nœud avec le numéro de croisement ≦ 15 toutes les entrées de la Smith Normal Form qui ne sont pas 0 ou 1. Ces nombres ont été calculés à partir d’un diagramme, mais ils sont invariants et donc les mêmes lorsqu’ils sont calculés à partir de n’importe quel diagramme de ce nœud. Si vous aimez les images de nœuds colorés, vous pouvez télécharger une affiche de notre collection d’affiches en cliquant sur la page d’accueil 'Accueil' > 'Affiches' menant à https://cariboutests.com/images/posters/knot_colouring_portrait.pdf.
Quelle est la force de la coloration N en tant qu’invariant?
Le tableau suivant montre comment l’utilisation d’un plus grand nombre d’invariants colorants augmente le nombre de classes invariantes de nœuds et diminue ainsi le nombre moyen de nœuds par classe. La colonne de droite montre comment la (#cr - 3)ème racine du nombre de classes invariantes colorantes reste à peu près constante, où #cr est le nombre de croisements des nœuds.
Tableau 1 : Statistiques sur les invariants de couleur
# de cr: # de croisements
# de kn: # de nœuds
# de cl1: # de classes en considérant uniquement la liste des nombres premiers de coloration
# de cl2: # de classes en considérant uniquement la liste des multiplicités des nombres premiers de coloration
# de cl3: # de classes lors de l’examen de la liste des entrées de Smith Normal Form <> 1
ABS : exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)ème racine de (# de cl3)
Tableau 1 : Statistiques sur les invariants de couleur
# de cr: # de croisements
# de kn: # de nœuds
# de cl1: # de classes en considérant uniquement la liste des nombres premiers de coloration
# de cl2: # de classes en considérant uniquement la liste des multiplicités des nombres premiers de coloration
# de cl3: # de classes lors de l’examen de la liste des entrées de Smith Normal Form <> 1
ABS : exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)ème racine de (# de cl3)
| # de cr | # de kn | # de cl1 | kn/cl1 | # de cl2 | kn/cl2 | # de 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 |
Comment le plus grand nombre de coloration pour les nœuds avec C croisement dépend-il de C?
Si l’on prend tous les nœuds avec le nombre croisé C (<16) et que l’on trouve à partir de ces nœuds celui qui a le plus grand nombre de coloration Nmax, alors le tableau suivant montre que Nmax croît approximativement d’un facteur de 1,7 en augmentant C de 1.
Tableau 2 : Tableau de B(C) = Nmax1/(C−1)
Tableau 2 : Tableau de B(C) = Nmax1/(C−1)
| C | Nmax | noeud | 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 |
Existe-t-il un programme informatique capable de calculer les colorations?
AsciiKnots est un programme informatique permettant de calculer pour un diagramme de nœuds donné tous les nombres de coloration en calculant la Smith Normal Form de la matrice de coefficients. Si le diagramme de nœuds n’a pas trop de croisements, il calcule également par recherche optimisée par tâtonnements pour un nombre de coloration donné toutes les couleurs ou tous les nombres de coloration, y compris leurs colorations.Outre les colorations, le programme peut calculer beaucoup plus. Il peut être téléchargé à partir de
https://cariboutests.com/games/knots/AsciiKnots.tar.gz. AsciiKnots fonctionne sous linux. Les utilisateurs de Windows peuvent installer Ubuntu Linux gratuitement en tant qu’application sous Windows 10. Les commandes Linux pour supprimer les anciennes versions téléchargées, pour télécharger la dernière version, pour la décompresser et la démarrer sont
rm AsciiKnots.tar.gz
wget https://cariboutests.com/games/knots/AsciiKnots.tar.gz
tar xfz AsciiKnots.tar.gz
./AsciiKnots
Une fonctionnalité de coloration limitée est également disponible sur https://cariboutests.com/games/knots/knoteditor/ après avoir sélectionné 'Tools' > 'Colour Knot'
Références
[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
Suivez ou abonnez-vous à l'Infolettre