Coloration de Cartes et Bases de Gröbner

Cette image est la propriété de mathscareers.org.uk, qui a aimablement autorisé son utilisation pour cet article.

Vignette écrite par Escudeiro Hernandes.
D’après le célèbre “théorème des quatre couleurs”, seulement quatre couleurs sont nécessaires pour colorier une carte sans que deux régions adjacentes aient la même couleur. En utilisant des équations polynomiales et les bases de Gröbner, nous pouvons déterminer si trois couleurs sont suffisantes pour colorier une carte donnée.

1. Coloration de carte
Le théorème des quatre couleurs (1) établit que n’importe quelle carte, qu’elle soit plane ou sphérique, peut être coloriée avec quatre couleurs sans que deux régions adjacentes soient de la même couleur. Il est facile de produire des exemples de cartes ne pouvant être coloriées avec seulement trois couleurs, et d’autre pouvant être coloriées avec trois couleurs. Une façon de déterminer si trois couleurs sont suffisantes pour colorier une carte consiste à analyser un système d’équations polynomiales associé à la carte. Chaque couleur est associée à une racine cubique (complexe) de l’unité et chaque région est symbolisée par une variable x_i de sorte qu’elle ne peut qu’admettre l’une des trois valeurs, c’est-à-dire une des trois couleurs. Ainsi nous avons {x_i}^3 - 1 = 0 pour chaque région.

Pour des régions x_j et x_k, nous avons 0= x_j ^3 -x_k ^3 =(x_j -x_k)(x_j ^2 +x_j x_k + x_k ^2). Si x_j et x_k sont des régions adjacentes, et puisque de telles régions ne peuvent pas être de la même couleur, alors x_j \neq x_k, c’est-à-dire, x_j ^2+ x_j x_k + x_k ^2=0. De cette façon, une carte avec n régions peut être coloriée avec trois couleurs si et seulement si le système d’équations polynomiales

(1)   \begin{eqnarray*} \left\{ \begin{array}{l}  x_i ^3-1=0 ~,\\ x_j ^2+ x_j x_k + x_k ^2=0 ~, \end{array}\right. \end{eqnarray*}

i= 1 , ... , n et x_j et x_k représentent des régions adjacentes, admet au moins une solution.

Exemple 1.

On considère la carte:

Figure 1.

Peut-elle être coloriée avec trois couleurs?

Pour répondre à cette question on doit vérifier que le système polynomial 1 avec i = 1, ..., 9 et


Rendered by QuickLaTeX.com

peut être résolu.

2. Systèmes d’équations polynomiales

La réponse à de nombreux problèmes de mathématiques réside dans la résolution de systèmes d’équations polynomiales, ce qui n’est pas toujours aisé. Si le système est donné par des équations linéaires, on peut, par la méthode du pivot de Gauss par exemple, substituer un système par un système équivalent dont la solution est plus facile à trouver. Dans le cas des systèmes polynomiaux, il existe une méthode analogue que nous présentons ci-dessous.

On notera P(n) l’ensemble des polynômes à coefficients complexes et à variables x_1 , ... , x_n. Etant donné un ensemble de polynômes f_1, ... , f_r dans P(n), on définit l’idéal qu’ils engendrent par

    \[I = \langle f_1, ... , f_r \rangle = \{ h_1 f_1 + ... + h_r f_r \mid h_1 , ... , h_r \in P(n) \}.\]

Un théorème du mathématicien David Hilbert: (2), appelé théorème des zéros de Hilbert, établit que le système f_1 = ... = f_r = 0 admet une solution (complexe) si et seulement si 1 \notin \langle f_1 , ... , f_r \rangle. Comment peut-on vérifier la dernière condition?

Il est facile de vérifier que deux systèmes d’équations f_1 = ... = f_r = 0 et g_1 = ... = g_s = 0, où f_i, g_j \in P (n), vérifiant la condition

(2)   \begin{eqnarray*} \langle f_1 , ... , f_r \rangle = \langle g_1 , ... , g_r \rangle , \end{eqnarray*}

ont la même solution.

Par conséquent, la stratégie pour résoudre un système f_1 = ... = f_r = 0 consiste à trouver des polynômes g_1, ... , g_s satisfaisant la condition 2 et avec lesquels il est possible de vérifier si un élément f \in P (n) appartient ou non à l’idéal \langle f_1, ... , f_r \rangle et dont la solution commune est plus facile à calculer qu’avec le système d’origine.

L’existence théorique d’un tel ensemble G = \{ g_1 , ... , g_s \} a été découverte durant la première moitié du siècle dernier par le mathématicien Wolfgang Gröbner. Des années plus tard, son étudiant Bruno Buchberger créa un algorithme pour le calculer. Ces ensembles sont appelés bases de Gröbner et l’algorithme de Buchberger pour les calculer est un des outils de calcul algébrique les plus importants.

Si l’idéal est de la forme I = \langle f_1 \rangle, on a f \in I si et seulement si f = h_1 f_1, c’est-à-dire f est divisible par f_1. De même, f \in \langle f_1 , ... , f_r \rangle si et seulement si f = h_1 f_1 + ... + h_r f_r, ce qui suggère quelque chose de similaire pour la division de f par f_1 , ... , f_r. En fait, on peut diviser un polynôme à plusieurs variables par un ensemble fini de polynômes, à condition que les monômes soient ordonnés d’une certaine façon.

3. Les Bases de Gröbner

Un monôme m de P (n) est un élément de la forme x_1 ^{a_1} ... x_n ^{a_n}, où a_1 , ... , a_n sont des entiers positifs ou nuls. Le monôme x_1 ^0 ... x_n ^0 sera noté 1. Parmi les ordres \preceq sur les monômes de P (n), ceux qui satisfont 1 \preceq m and m_1 .m \preceq m_2 .m lorsque m_1 \preceq m_2 sont ceux qui rendent possible la mise en pratique de l’algorithme de division.

Un exemple est l’ordre lexicographique \preceq_{Lex}, où x_1 ^{a_1} ... x_n ^{a_n} \preceq_{Lex} x_1 ^{b_1} ... x_n ^{b_n}, s’il existe 1 \leqslant i \leqslant n de sorte que a_i < b_i et a_j = b_j pour tous j < i.

Etant donné un ordre sur les monômes, le plus grand monôme d’un polynôme f est appelé terme dominant de f et noté lt (f) (pour “leading term”).

Une base de Gröbner d’un idéal I = \langle f_1 , ... , f_r\rangle relativement à un ordre sur les monômes, est, par définition, un ensemble G = \{ g_1 , ... , g_s \} d’éléments de I de sorte que le terme dominant de chaque élément de I soit divisible par le terme dominant d’un élément de G. On peut montrer que chaque base de Gröbner G de I est un ensemble qui vérifie la condition 2.

Par conséquent, 1 \in I si et seulement si il existe une base de Gröbner de I contenant une constante non nulle, puisque 1 \preceq m, pour chaque monôme m de P (n).

Par exemple, G = \{ f_1 \} est une base de Gröbner de \langle f_1 \rangle, pour tout ordre sur les monômes, alors que G = \{ x+y+z-6, x-y+1, x+y-z \} n’est pas une base de Gröbner de I = \langle x+y+z-6, x-y+1, x+y-z \rangle pour l’ordre lexicographique, puisque lt(x+y+z-6-(x-y+1)) = lt(2y+z-7) = 2y n’est pas divisible par x = lt(x + y + z - 6) = lt(x - y + 1) = lt(x + y - z).

Pour obtenir une base de Gröbner d’un idéal, pour un ordre sur les monômes donné, on peut utiliser l’algorithme de Buchberger (3). On trouve des algorithmes permettant de calculer des bases de Gröbner dans la majorité des systèmes de calcul algébrique.

En l’occurence, une base de Gröbner de l’idéal I = \langle x+y+z-6, x-y+1, x+y-z \rangle, pour l’ordre lexicographique, est G = \{ x+y +z -6, 2y +z -7, 2z -6 \}.

4. Solution du problème et autres applications

Le système de l’exemple 1, a au plus un nombre fini de solutions (neuf variables, chacune pouvant prendre une valeur parmi trois). Le problème est de déterminer si le système admet une solution, et dans ce cas de la déterminer.

En appliquant l’algorithme de Buchberger au système de l’exemple 1, on obtient la base de Gröbner G suivante, pour l’ordre lexicographique:


Rendered by QuickLaTeX.com

Ainsi, 1 \notin I et par conséquent le système admet des solutions. Les équations

    \[\left\{ \begin{array}{l}  x_1 ^3 - 1 = 0 ~,\\ x_2 ^2 + x_2 x_1 + x_1 ^2 = 0 ~,\\ x_5 - x_2 = 0 ~,\\ x_7 - x_2 = 0 ~,\\  x_9 -x_3 = 0 ~, \end{array}\right.\]

traduisent le fait suivant: on peut utiliser n’importe quelle couleur pour x_1, x_2 \neq x_1, x_2 = x_5 = x_7 et x_3 = x_9.

Puisque les couleurs sont représentées par des racines cubiques complexes de l’unité, la seule solution pour x_4 + x_3 + x_2 = 0, x_6 + x_3 + x_2 = 0 et x_8 + x_3 + x_2 = 0 est d’attribuer des valeurs (couleurs) distinctes pour x_2, x_3 et x_4, et donc x_4 = x_6 = x_8. Enfin, 0 = x_3 ^2 + x_3 x_2 -x_2 x_1 -x_1 ^2 = (x_3 + x_2 + x_1 )(x_3 - x_1 ) qui nous donne deux possibilités: x_3 +x_2 +x_1 = 0 ou x_3 -x_1 = 0, c’est-à-dire x_1, x_2 et x_3 ont des couleurs distinctes ou x_1 = x_3. Ainsi, on trouve, à une permutation des couleurs près, toutes les solutions possibles:

Figure 2.

Les bases de Gröbner peuvent aussi être utilisées pour déterminer des idéaux, en convertisssant des équations paramétriques en équations cartésiennes (pour des surfaces et des courbes par exemples), pour calculer des polynômes minimaux de nombres algébriques, pour vérifier des théorèmes de géométrie Euclidienne, pour valider des constructions en origami et résoudre des grilles de sudoku (voir (4), (5) et (6)).

Références

(1) http://www.ipv.pt/millenium/Millenium24/12.pdf

(2) http://www.mat.uniroma1.it/people/manetti/dispense/nullstellen.pdf

(3) https://www.risc.jku.at/people/buchberg/papers/1970-00-00-A.english.pdf

(4) Adams, W. and Loustaunau, P., An Introduction to Gröbner Basis, AMS, Providence RI (1994).

(5) Cox, D; Little, J. and O’Shea, D., Ideals, Varieties and Algorithms, 2nd edition, Springer-Verlag, New York, (1996).

(6) Hernandes, M. E., Um Primeiro Contato com Bases de Gröbner, 28°. Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, (2011).

Ce post est disponible en: Anglais, Allemand, Italien, Arabe, Khmère

This entry was posted in Vignettes. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *