I.2 Calcul de bases de Gröbner

I.2.1 Un calcul formel sur les polynômes

a. Étapes d'une résolution par bases de Gröbner

La donnée est une famille finie de polynômes engendrant un idéal I de K[X]. On commence par calculer une base de Gröbner de cet idéal. C'est une autre famille génératrice, permettant de tester facilement l'appartenance à l'idéal I.

Ensuite, il est possible d'en déduire quelques informations sur la structure de la variété solution.

b. Valeur des résultats obtenus

Des algorithmes tels celui de Buchberger [10] construisent une base de Gröbner engendrant l'idéal I. Le calcul de la base de Gröbner puis la résolution du système se font avec des opérations exactes, sur les polynômes, leurs résultats sont donc utilisables directement.

Malheureusement, la puissance de calcul et la mémoire nécessaires empêchent souvent le recours à cette méthode. La principale raison de cette lenteur est qu'il est nécessaire de manipuler des polynômes à plusieurs variables, à coefficients dans K. Même des implantations très performantes comme le logiciel GB [19], qui fait aussi des calculs modulo p pour limiter la taille des données, atteignent vite leurs limites lors du calcul de dessins d'enfants.

c. Affine ou projectif

Nous ne décrirons que le cas affine, mais la théorie du calcul de variétés algébriques et d'idéaux de polynômes est plus simple dans le cas homogène (projectif). Cependant, les principes restent les mêmes.

I.2.2 Réduction dans K[X]

a. Terme dominant d'un polynôme

Soit un polynôme f = f X dans K[X]. Nous appellerons monôme le produit de puissances X et terme un élément non nul f X. Pour comparer les polynômes, nous choisissons un ordre total sur les monômes. Nous notons max(f) le monôme dominant du polynôme f, qui est l'élément maximal de son support, et nous notons  maxt(f) le terme correspondant.

b. Principe

Étant donnés deux polynômes f et g, la réduction de f modulo g est une opération qui calcule un certain polynôme h = f - kg où k est choisi dans K[X] de telle sorte que max(g) ne divise aucun élément du support de h. Un tel k est unique, si l'ordre sur les monômes vérifie certaines propriétés de compatibilité (cf. § f.). On a bien sûr l'égalité des idéaux engendrés <h, g> = <f, g>. Lorsque max(g) ne divise aucun élément du support de f, on dit que f ne peut pas être réduit par g.

La réduction peut se noter comme une règle de réécriture f _g h. Soit une famille de polynômes G, on dit que f se réduit en h par rapport à G s'il existe une suite non vide de réductions de f par des éléments de G qui aboutit à h. Cela se note f ⁺_G h. Cette opération permet de transformer une famille génératrice d'un idéal en une autre plus simple.

On dit que r est un reste de la réduction de f par G si f ⁺_G r et si r est nul ou ne peut être réduit par aucun élément de G.

c. Le cas des polynômes à une variable

Les monômes sont bien sûr ordonnés par leur degré. La division euclidienne nous donne la réduction dans K[X] : le polynôme k est le quotient de la division de f par g et le polynôme h en est le reste.

d. Le cas linéaire

Nous devons choisir un ordre sur les indéterminées, par exemple X_i < X_j si i < j. La réduction du pivot de Gauss est un exemple de l'opération de réduction décrite plus haut.

Soient f et g deux polynômes linéaires non nuls, avec X_i = max(g). Si le coefficient f_i est non nul, alors la réduction de Gauss calcule h = f - (f_i/g_i) g qui ne fait plus intervenir la variable X_i.

e. Généralisation

Voici un algorithme de réduction. Si max(g) divise un terme non nul X de f, nous calculons h = f - X/maxt(g) g, que nous notons f mod_X g. Si l'ordre sur les monômes est compatible, cette opération diminue le nombre de termes divisibles par max(g), le polynôme f mod g est obtenu après avoir effectué toutes les réductions par g possibles.

f. Ordre sur les monômes

Pour que la réduction ait les propriétés ci-dessus, l'ordre sur les X doit vérifier les trois conditions ci-dessous :

• ce doit être un ordre total,
• le monôme 1 est strictement inférieur à tous les autres,
• si X < X alors X⁺ < X⁺.

Les ordres habituellement choisis par les programmes de calcul formel sont les quatre ci-dessous. Ils présupposent un ordre sur les indéterminées, donné par leurs indices. Les ordres du degré sont une transposition au cas affine des ordres sur les monômes homogènes. Il ont ainsi de meilleures propriétés théoriques.

L'ordre lexicographique :

où X <_lex X s'il existe un indice i tel que : ₀ = ₀ , ... , _i-1 = _i-1 , _i < _i .

L'ordre lexicographique réverse :

où X <_revlex X s'il existe un indice i tel que : _i > _i , _i+1 = _i+1 , ... , _m = _m .

L'ordre du degré, lexicographique :

nous avons X <_deglex X si le degré total de X est strictement inférieur à celui de X, ou bien s'ils ont même degré total et sont dans l'ordre lexicographique.

L'ordre du degré, lexicographique réverse :

X <_degrevlex X si le degré total de X est strictement inférieur à celui de X, ou bien s'ils ont même degré total et sont dans l'ordre lexicographique réverse. Il diffère de l'ordre du degré lexicographique dès qu'il y a au moins trois variables.

g. Calcul du reste

Nous pouvons imaginer un algorithme élémentaire pour calculer un reste de la réduction de f par rapport à G : Nous commençons par poser h = 0. S'il existe un g_i tel que max(g_i) divise max(f), nous réduisons f modulo g_i. Sinon, nous remplaçons f par f - maxt(f) et h par h + maxt(f). Cet algorithme s'arrête. La valeur finale de h est un reste de la réduction de f par G.

L'exemple de la réduction de f = X₁ par G = {X₁ + X₂, X₁ - X₂} nous montre que le reste de la réduction de f par un ensemble G n'est pas unique, il dépend des choix de g_i à chaque étape.

Dans le cas ou G est un idéal, le reste de la réduction par G est unique. C'est le théorème de division d'Hironaka [25].

h. Notion de base de Gröbner

Une partie finie G d'un idéal I de K[X] est une base de Gröbner (terminologie de Buchberger) ou base standard (terminologie d'Hironaka) si et seulement si, pour tout f non nul de I, il existe g dans G tel que max(g) divise max(f). Cela s'écrit aussi, avec les notations de réécriture : f élément non nul de I si, et seulement si, f ⁺_G 0.

Nous pouvons remarquer que si on ajoute un polynôme de l'idéal à une base de Gröbner, la propriété est conservée. Une base de Gröbner est minimale si ce n'est plus une base lorsqu'on enlève un polynôme. Dans une telle base, les max(g) sont distincts. La résolution du système utilise le calcul d'une base de Gröbner minimale.

I.2.3 Réduction de S-polynômes

a. Les S-polynômes

Si g₁ et g₂ sont deux polynômes non nuls, nous pouvons définir L le PPCM formel des monômes max(g₁) et max(g₂). Le S-polynôme (qu'on appelle aussi polynôme de syzygie dans le cas homogène) de g₁ et g₂ est par définition :

S(g₁, g₂) =   L / maxt(g₁)   g₁   -   L / maxt(g₂)   g₂.

C'est une généralisation du PGCD qui permet de mesurer l'ambiguité introduite par le choix d'une réduction modulo g₁ ou g₂. En effet, si h₁ = f mod_X g₁ et h₂ = f mod_X g₂, alors h₂ - h₁ = (X / L) S(g₁, g₂).

L'idée fondamentale de Buchberger limite la définition d'une base de Gröbner à l'étude des S-polynômes : G est une base de Gröbner de l'idéal qu'elle engendre si et seulement si pour tous g_i et g_j dans G, on a S(g_i, g_j) ⁺_G 0.

b. Calcul d'une base de Gröbner

Ceci permet de concevoir un algorithme pour calculer une base de Gröbner, en calculant les restes de la réduction par G des S(g_i, g_j).

L'algorithme de Buchberger ajoute progressivement et récursivement au système G = {g_i} tous les restes non nuls de la réduction par G de tous les S(g_i, g_j). Les stratégies de sélection des S(g_i, g_j) ont fait l'objet de nombreuses recherches, la stratégie dite du sucre est habituellement considérée comme la plus performante [22].

Le logiciel GB, pour les systèmes à coefficients entiers calcule simultanément une base modulo p.

c. Choix de l'ordre des monômes

Pour l'ordre lexicographique, la manipulation de polynômes de degré élevé handicape le calcul d'une base de Gröbner. On prouve que si les polynômes du système de départ sont de degré au plus d avec m variables, la complexité du calcul est d^O(m³) si le système est de dimension 0.

En revanche, l'ordre du degré réverse limite le degré des polynômes manipulés et obtient une bien meilleure efficacité avec une complexité de d^m² (qui descend à d^m si le système homogène correspondant est de dimension 0).

Il est bien plus facile de déduire la géométrie de la solution à partir d'une base lexicographique, dont les premiers éléments font intervenir un petit nombre de variables.

Faugère, Gianni, Lazard et Mora [20] ont donc proposé une méthode efficace pour changer d'ordre, en dimension 0. Cet algorithme a été implanté dans GB et Axiom. L'efficacité de cette méthode est telle qu'on a souvent intérêt à calculer une base pour l'ordre du degré puis à la transformer en une base pour l'ordre lexicographique, plutôt qu'un calcul entièrement selon l'ordre lexicographique.

d. Dimension 0 et systèmes triangulaires

La description d'une variété d'une façon intelligible n'est pas facile lorsqu'elle est de dimension positive. Une variété de dimension 0 peut être décrite par la liste (finie) de ses points, dans leur corps de définition. On représente ceci sous la forme d'une collection de systèmes triangulaires, chacun correspondant à quelques orbites sous l'action de Galois.

Sur K[X₁,..., X_m] avec les variables ordonnées dans cet ordre, un ensemble de m polynômes est dit triangulaire si le i-ième polynôme est un polynôme unitaire de K[X₁,..., X_i-1][X_i]. Tout idéal maximal admet une base triangulaire, ce qui permet de prouver que toute variété de dimension 0 est réunion d'un nombre fini de variétés issues de systèmes triangulaires.

D. Lazard [27] propose des méthodes pour rendre cette représentation effective, à partir d'une base de Gröbner de l'idéal. Ceci est nettement plus efficace à partir d'une base de Gröbner pour l'ordre lexicographique, ce qui confirme la remarque du paragraphe précédent.

On peut remarquer qu'il est facile de tester si une variété est de dimension 0 lorsqu'on en connaît une base de Gröbner (pour n'importe quel ordre). C'est le cas si, et seulement si, l'ensemble des monômes dominant des éléments de la base contient une puissance de chacun des X_i.