Code de Gauss

Un code de Gauss, du nom du mathématicien Carl Friedrich Gauss est une liste de nombres codant une courbe plane fermée présentant des croisements. Il a été étendu au codage d'un nœud, et même d'un entrelacs.

Historique

Dans un article de 1823^[1], Gauss se proposait de démontrer qu’une courbe plane fermée de nombre d'enroulement $N$ (nombre de tours sur lui-même effectué par un observateur parcourant la courbe) possède au moins $N-1$ croisements ( $N\geqslant 1$ ).

À l'occasion de cette démonstration, il a introduit le code qui porte son nom, défini dans le paragraphe suivant.

Comme visualisé ci-contre, une courbe circulaire à $n(=3)$ boucles internes a un nombre d'enroulement égal à $N=n 1(=4)$ ; elle possède le nombre minimal de croisements à $N$ donné.

Définition

Par courbe, on entend ici une courbe fermée, ayant une tangente en tous points, et dont les points multiples, en nombre fini, sont tous doubles et transverses (tangentes non confondues), qui seront ici dénommés croisements. Cela équivaut topologiquement à un graphe planaire 4-régulier (4 arêtes partant de chaque sommet), les croisements correspondant aux sommets du graphe (par graphe, on entend graphe non orienté et acceptant les arêtes multiples). Notons que s'il y a $n$ croisements, il y a alors $2n$ arêtes, donc par la relation d'Euler, $n 2$ faces (en comptant la face externe).

Deux courbes sont dites équivalentes, si elles sont images l'une de l'autre par un difféomorphisme du plan.

Ayant numéroté arbitrairement de 1 à $n$ ces croisements, et ayant choisi arbitrairement un point de départ sur la courbe, et un sens de parcours, le code de Gauss de la courbe est alors la liste des $2n$ numéros des croisements que l'on obtient successivement lorsqu’on effectue un parcours complet sur la courbe.

On trouvera dans la première figure ci-dessous les codes de Gauss des courbes correspondant aux projections des nœud de trèfle et nœud de huit. On peut noter que les deux courbes du haut ont le même code de Gauss, mais ne sont pas équivalentes dans le plan (elles le sont par contre sur la sphère).

Un code de Gauss est toujours une liste de 2 $n$ nombres entre 1 et $n$ , chacun étant répété deux fois, que nous désignerons par mot de Gauss. Notons que le nombre de mots de Gauss est le coefficient multinomial ${\binom {2n}{2,2,...,2}}=(2n)!/2^{n}$ .

En pratique, pour coder une courbe, on choisit un point de départ entre deux croisements, un sens de parcours et on numérote successivement les croisements 1, 2, 3, ..., $n$ en sautant les croisements déjà numérotés. On obtient alors un code de Gauss où les premières occurrences de chaque nombre sont classées en croissant. Il y a alors ${\frac {\binom {2n}{2,2,...,2}}{n!}}=1\times 3\times 5\times \cdots \times (2n-1)$ codes de ce type.

Codes de Gauss de courbes à 3 ou 4 croisements.
Courbe à 7 croisements avec son code et son diagramme de Gauss.
Les 3, 5,15 courbes à respectivement 3, 4, 5 croisements répertoriées par Nagy .

Diagramme de Gauss

Les 5 diagrammes de Gauss à 3 cordes, à rotations près. Seuls le premier, le troisième et le dernier sont réalisables.

On peut visualiser un code de Gauss en traçant un cercle, marquant des points successifs numérotés par les nombres du code, et reliant par une corde les points de même numéro, le dessin obtenu étant dénommé diagramme de Gauss (ou diagramme de cordes). L’intérêt étant qu'à une rotation près ou une symétrie près, le diagramme ne dépend plus de la numérotation des croisements ni du sens de parcours.

Nota : le nombre de diagrammes de Gauss à rotation près est donné par suite A007769 de l'OEIS, et à rotation et symétrie près par la suite A054499 de l'OEIS.

Problème et condition de Gauss

Les 1, 1, 3 et 5 diagrammes de Gauss réalisables pour ' **$n$ '** = 1, 2, 3 et 4 avec des courbes correspondantes ; pour ' **$n$ '** = 4, les 5 courbes tracées sont de la main de Gauss.

Un mot (ou diagramme) de Gauss est dit réalisable s'il provient d'une courbe au sens ci-dessus. Gauss s'est posé le problème de caractériser cette réalisabilité, et a trouvé la condition nécessaire très simple suivante :

Dans un mot de Gauss réalisable, deux nombres égaux sont séparés par un nombre pair de nombres.

Par exemple, le mot (1, 2, 1, 3, 3, 2) n'est pas réalisable car les deux 1 sont séparés par un seul nombre.

Pour un diagramme de Gauss, la condition se traduit par le fait que de part et d'autre d'une corde, il y a un nombre pair de points marqués sur le cercle.

Cette condition a été démontrée par Julius Nagy en 1927^[2].

Démonstration succincte de ce fait.

Si les nombres situés entre deux nombres répétés n'ont pas de répétition, la portion de courbe correspondant aux deux occurrences du même nombre forme une courbe fermée sans point double, ou courbe de Jordan, séparant le plan en deux parties connexes. Lorsque la courbe entre dans la partie interne, elle doit forcément en ressortir, d'où le fait que le nombre de points de croisements différents du point de départ est pair. Dans le cas de répétitions imbriquées, on applique ce qui précède aux répétitions les plus imbriquées, puis aux autres, successivement.

Une démonstration détaillée, en anglais, se trouve dans^[3].

On notera l'utilisation du théorème de Jordan dans la démonstration : sur un tore par exemple, on peut trouver une courbe qui aurait pour code (1,2,1,2).

Malheureusement, Gauss avait déjà remarqué (^[1] page 284) qu'à partir de $n$ = 5, cette condition de parité n'est pas suffisante ; par exemple le mot (1,2,3,4,5,3,4,1,2,5) vérifie la condition de parité mais ne correspond à aucune courbe à 5 croisements.

Plusieurs mathématiciens ont donné et démontré des conditions nécessaires et suffisantes de réalisabilité : Nagy en 1927^[2], Dehn en 1936^[4], Treybig en 1968^[5], Marx en 1969^[6], Bouchet en 1972^[7], Lovasz en 1976^[8], Rosenstiehl en 1976^[9], Chaves et Weber en 1994^[10], Burckel dans les années 1990^[11], et Grindblat-Lopatkin en 2017^[12].

Rosenstiehl, par exemple, définit le graphe d'entrelacements $G$ associé au mot de Gauss, dont les sommets sont les nombres de 1 à $n$ , deux nombres $a$ et b étant reliés par une arête s'ils sont entrelacés dans le mot : entre les deux occurrences de $a$ , le nombre $b$ apparaît une fois et une seule (et donc entre les deux occurrences de $b$ , $a$ apparaît une fois et une seule). Il démontre que le mot de Gauss est réalisable si et seulement si :

1) Les sommets de $G$ sont de degré pair (condition de Gauss).

2) Si $a$ , $b$ } n'est pas une arête de $G$ , les sommets à la fois reliés à $a$ et $b$ sont en nombre pair.

3) Les arêtes $a$ , $b$ } de $G$ pour lesquelles les sommets à la fois reliés à $a$ et $b$ sont en nombre pair forment l'ensemble des arêtes incidentes à un même sommet (ou cocycle).

Reconstitution d'une courbe à partir du code de Gauss.

Courbe à 6 croisements de code de Gauss : (1,2,4,6,5,4,2,1,3,5,6,3)
Courbe reconstituée à partir du code de Gauss précédent.
Réalisation de la courbe de code Gauss (1,2,1,2) sur le tore.
Tentative de reconstitution dans le plan du code de Gauss (1,2,3,4,5,3,4,1,2,5) faisant apparaitre 3 croisements supplémentaires.
Réalisation de la courbe de code de Gauss (1,2,3,4,5,3,4,1,2,5) sur le tore et le plan projectif.

Il s'agit en fait d'un problème similaire à celui de tracer un graphe planaire connaissant les sommets et les arêtes. En effet, si le code de Gauss est $(x_{1},x_{2},...,x_{2n})$ , les 2 $n$ arêtes du graphe associé à la courbe sont les $\left\{x_{i-1},x_{i}\right\}$ , plus $\left\{x_{2n},x_{1}\right\}$ . On place donc $n$ croix représentant les croisements numérotés de 1 à $n$ , que l'on relie par des arêtes qui ne doivent pas se croiser. La contrainte est, lorsqu'on arrive à une croix, de repartir sur la même branche de la croix. Cette contrainte est importante, car par exemple le mot (1,2,1,2) n'est pas réalisable, bien qu'il existe un graphe planaire ayant pour arêtes {1,2}, {2,1}, {1,2} et {2,1} !

Le site knotilus possède une application permettant de reconstituer automatiquement la courbe (ou plutôt, le nœud alterné) à partir du code de Gauss.

Ci-dessus, on verra une tentative de reconstituer une courbe associée au mot (1,2,3,4,5,3,4,1,2,5) , ce qui est impossible sans croisement dans le plan. À droite, réalisation de ce même code sur le tore et le plan projectif.

Notation de Dowker

La notation de Dowker^[13]^,^[14] constitue une autre manière de coder une courbe, plus concise : ayant de nouveau choisi arbitrairement un point de départ sur la courbe et un sens de parcours, on numérote successivement les $n$ croisements par les nombres de 1 à 2 $n$ ; chaque croisement reçoit donc une paire de nombres entre 1 et 2 $n$ , et la propriété de parité de Gauss indique que chaque paire est formée d'un nombre pair et d'un nombre impair. La notation de Dowker est alors la liste des nombres pairs associés aux nombre impairs 1, 3, ..., 2 $n$ - 1, dans cet ordre. Par exemple les croisements de la courbe ci-contre, reçoivent les paires successives {1,2}, {3,6}, {4,7}, et {5,8} ; la liste des impairs (1,3,5,7) est donc associée à la liste des pairs (2,6,8,4) qui constitue une notation de Dowker de la courbe. On récupère un code de Gauss de la courbe en mettant deux 1 aux places 1 et 2, deux 2 aux places 3 et 6, deux 3 aux places 5 et 8, et deux 4 aux places 7 et 4 : (1,1,2,3,4,2,3,4).

Notons que Gauss avait déjà introduit cette notation, en numérotant de 0 à 2 $n$ -1 au lieu de 1 à 2 $n$ (^[1] page 284).

Pour une courbe à $n$ croisements donnée, il y a au plus 4 $n$ notations de Dowker possibles (dues aux 2 $n$ points de départ situés sur les 2 $n$ arêtes et aux deux sens de parcours), éventuellement confondues. La notation qui a l'ordre lexicographique minimal est dite standard.

Notations de Dowker standards des courbes associées aux quatre premiers nœuds premiers.

Extension aux nœuds et entrelacs.

Un diagramme d'un nœud est une projection plane du nœud ayant les propriétés des courbes définies ci-dessus, avec en sus l'indication des passages dessus, ou dessous. Le code de Gauss du nœud (ou plutôt de son diagramme) est alors le code de Gauss de cette courbe, les nombres étant affectés du signe plus en cas de passage au-dessus, et du signe moins en cas de passage en dessous. Le code de Gauss est donc formé des 2 $n$ nombres de 1 à $n$ et de $-n$ à $-1$ . Pour un entrelacs, on effectue ceci pour chaque brin ; mais attention : pour chaque brin, les croisements avec les autres brins interviennent !

Notons que la condition de parité de Gauss permet de justifier que toute courbe est le diagramme d'un nœud dit "alterné" (où les passages dessus et dessous se suivent de façon alternée) : si dans un croisement donné on a un "pont", lorsqu'on reviendra à ce même croisement, on aura forcément un "souterrain". Par contre, il existe des nœuds dont aucune projection n'est alternée, comme le nœud premier 8.19.

Voir aussi

Lien entre notation de Dowker et problème des ménages.

Lien externe

Cours sur le sujet par Jeff Erickson.

Références

↑ ^{a b et c} (de) Carl Friedrich GAUSS, Werke,VIII,1823 et 1844, Leipzig, Teubner, 1900, p. 272 et 284
↑ ^{a et b} (de) Julius V. Sz. NAGY, Mathematische Zeitschrift, 26, Uber ein toplogisches Problem von Gauss, 1927, 579-592 p.
↑ (en) Hans Rademacher, The Enjoyment of Math, Princeton, Princeton Science Library, 1994, p. 61-65
↑ (de) Max DEHN, « Über kombinatorische Topologie », Acta mathematica, 67,‎ 1936, p. 123-168
↑ (en) L. B. TREYBIG, « A characterization of the double point structure of the projection of a polygonal knot in regular position », Transactions of the American Mathematical Society, 130,‎ 1968, p. 223-247
↑ (en) Morris L. MARX, « The Gauss realizability problem », Proceedings of the American Mathematical Society, 22,‎ 1969, p. 610-613
↑ André BOUCHET, « Caractérisation des symboles croisés de genre nul », Comptes rendus de l'Académie des sciences,‎ 1972, p. 724
↑ (en) Laszlo LOVASZ, « A forbidden substructure characterization of Gauss codes », Bull. Amer. Math. Soc. , 82, n°1,‎ 1976, p. 121-122
↑ Pierre ROSENSTIEHL, « Solution algébrique du problème de Gauss sur la permutation des points d'intersection d'une ou plusieurs courbes fermées du plan », Comptes-rendus de l'Académie de Sciences, tome 283,‎ 11 octobre 1976, p. 551,553
↑ Nathalie CHAVES et Claude WEBER, « Plombages de rubans et problème des mots de Gauss », Expositiones Mathematicae,‎ 1994, p. 53-77
↑ (en) Serge Burckel, « A Game for the Characterization of Realizable Gauss Words » [ps], 13 mars 2001, p. 1-10
↑ (en) Andrey GRINBLAT and Viktor LOPATKIN, « On realizability of Gauss diagrams », arXiv:1610.01440,‎ 4 décembre 2017 (lire en ligne)
↑ (en) Colin C. ADAMS, THE KNOT BOOK, USA, American Mathematical Society, 2004, p. 35-40
↑ (en) C.H. DOWKER and Morwen B. THISTLETHWAITE, « CLASSIFICATION OF KNOT PROJECTIONS », Topology and its Applications 16,‎ 1983, p. 19-31 (lire en ligne)

Portail des mathématiques

[:2-1] {a b et c} (de) Carl Friedrich GAUSS, Werke,VIII,1823 et 1844, Leipzig, Teubner, 1900, p. 272 et 284

[:0-2] {a et b} (de) Julius V. Sz. NAGY, Mathematische Zeitschrift, 26, Uber ein toplogisches Problem von Gauss, 1927, 579-592 p.

[3] (en) Hans Rademacher, The Enjoyment of Math, Princeton, Princeton Science Library, 1994, p. 61-65

[4] (de) Max DEHN, « Über kombinatorische Topologie », Acta mathematica, 67,‎ 1936, p. 123-168

[5] (en) L. B. TREYBIG, « A characterization of the double point structure of the projection of a polygonal knot in regular position », Transactions of the American Mathematical Society, 130,‎ 1968, p. 223-247

[6] (en) Morris L. MARX, « The Gauss realizability problem », Proceedings of the American Mathematical Society, 22,‎ 1969, p. 610-613

[7] André BOUCHET, « Caractérisation des symboles croisés de genre nul », Comptes rendus de l'Académie des sciences,‎ 1972, p. 724

[8] (en) Laszlo LOVASZ, « A forbidden substructure characterization of Gauss codes », Bull. Amer. Math. Soc. , 82, n°1,‎ 1976, p. 121-122

[:1-9] Pierre ROSENSTIEHL, « Solution algébrique du problème de Gauss sur la permutation des points d'intersection d'une ou plusieurs courbes fermées du plan », Comptes-rendus de l'Académie de Sciences, tome 283,‎ 11 octobre 1976, p. 551,553

[10] Nathalie CHAVES et Claude WEBER, « Plombages de rubans et problème des mots de Gauss », Expositiones Mathematicae,‎ 1994, p. 53-77

[11] (en) Serge Burckel, « A Game for the Characterization of Realizable Gauss Words » [ps], 13 mars 2001, p. 1-10

[12] (en) Andrey GRINBLAT and Viktor LOPATKIN, « On realizability of Gauss diagrams », arXiv:1610.01440,‎ 4 décembre 2017 (lire en ligne)

[13] (en) Colin C. ADAMS, THE KNOT BOOK, USA, American Mathematical Society, 2004, p. 35-40

[14] (en) C.H. DOWKER and Morwen B. THISTLETHWAITE, « CLASSIFICATION OF KNOT PROJECTIONS », Topology and its Applications 16,‎ 1983, p. 19-31 (lire en ligne)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]