Bases de Gröbner-Shirshov sur les anneaux de valuation et Caractérisation de certaines bases de Gröbner non commutatives finies

Bases de Gröbner-Shirshov sur les anneaux de valuation et Caractérisation de certaines bases de Gröbner non commutatives finies

Rappels sur les bases de Gröbner

Ce chapitre est consacré aux rappels sur les bases de Gröbner. Il est composé de trois sections. Dans la première section, on reviendra sur les bases de Gröbner commutatives sur un corps, dans la deuxième et la troisième sections intitulées respectivemnt Bases de Gröbner non commutatives sur un corps et Bases de Gröbner sur un anneau, on taitera les généralisations des bases de Gröbner. Pour chacune de ces sections, on introduira les concepts de base et les notations que nous utilisons. Le lecteur peut se réfèrer aux documents [20, 34] pour les détails concernant les notions élémentaires essentielles que sont anneaux, corps, idéaux, anneaux de polynômes à plusieurs indéterminées. I Bases de Gröbner commutatives sur un corps Il est connu que l’anneau KrXs des polynômes en une seule indéterminée est principal et euclidien. Ainsi, le test d’appartenance d’un polynôme g à un idéal I de KrXs se réalise facilement par la division euclidienne de g par un polynôme f engendrant I. Par contre, l’anneau KrX1, X2, …, Xns des polynômes à plusieurs indéterminées n’est ni principal ni euclidien. Néanmoins, le théorème de la base de Hilbert affirme que tout idéal I de KrX1, X2, …, Xns admet au moins une partie génératrice finie. Faisant le parallèle avec l’anneau des polynômes en une seule indéterminée, on développe dans KrX1, X2, …, Xns un analogue de la division euclidienne afin de faire le test  d’appartenance. Puis, on verra que pour un idéal I donné, il peut exister des parties génératrices qui ne garantissent pas nécessairement l’unicité du reste de la division d’un polynôme f. Ces parties génératrices ne sont donc pas efficaces dans la résolution de l’IMP. Certaines parties génératrices ayant des propriétés particulières garantissent l’unicité du reste de la division d’un polynôme f. Ces dernières que nous appelerons plus tard bases de Gröbner permettent donc de résoudre l’IMP de façon efficace. Les bases de Gröbner commutatives sur un corps sont le cas classique des bases de Gröbner. Elles ont été développées par B. Buchberger dans sa thèse de doctorat alors qu’il cherchait à résoudre le problème de l’appartenance d’un polynôme à un idéal [13]. I – 1 Notations Etant donnés un corps commutatif K et un alphabet fini X “ tX1, X2, …, Xnu, — l’anneau KrX1, X2, …, Xns des polynômes commutatifs à coefficients dans K et à indéterminées dans X est noté KrXs; — pour tout α “ pα1, α2, …, αnq P N n , le monôme X1 α1X2 α2 …Xn αn est noté Xα ; — L’ensemble tXα |α P N n u des monômes est noté M ; — l’idéal engendré par un sous-ensemble G de KrXs est noté xGy. — Le nombre d’éléments d’un ensemble fini G est appelé cardinal de G et noté cardpGq. I – 2 Concepts de base I – 2 – a Support d’un polynôme Définition I – 2.1. Tout polynôme f P KrXs s’exprime de façon unique à une permutation près sous la forme f “ ÿ iPΛ aiX αi , ai P Kzt0u, αi P N n , Λ est fini et αi ‰ αj si i ‰ j L’ensemble des monômes intervenant dans cette expression forme le support de f noté Supppfq.

Degré d’un monôme et degré d’un polynôme

Définition I – 2.2. — Pour tout α “ pα1, α2, …, αnq P N n , l’entier naturel |α| “ α1 ` α2 ` … ` αn est appelé degré du monôme Xα . On le note degpXα q. — Le degré d’un polynôme f est le maximum des degrés des éléments de son support. I – 2 – c Relation de divisibilité entre monômes Définition I – 2.3. On dit qu’un monôme Xα divise un monôme Xβ s’il existe un monôme Xγ tel que Xβ “ XαXγ “ Xα`γ où α ` γ “ pα1 ` γ1, α2 ` γ2, …, αn ` γnq. Exemple I – 2.1. Le monôme X2Z divise X2Y3Z mais il n’y a aucune relation de divisibilité entre XY et XZ dans l’anneau à trois indéterminées KrX, Y, Zs. I – 2 – d Ordre monomial Dans l’écriture d’un polynôme en une seule indéterminée, les monômes sont très souvent rangés suivant leur degré. Le monôme de plus haut degré étant souvent désigné sous l’expression « monôme de tête ». On peut vérifier que cet ordre défini à partir du degré est total, un bon ordre et compatible avec la multiplication des monômes. On l’étend à l’anneau commuatif des polynômes à plusieurs indéterminées. Plus précisément, on a la définition suivante. Définition I – 2.4. Un ordre ă sur M est appelé ordre monomial si : — ă est total ; — ă est un bon ordre ; — ă est compatible avec la multiplication des monômes. Exemple I – 2.2. Les ordres définis ci-après sont des ordres monomiaux. — L’ordre lexicographique ălex défini par Xα ălex Xβ si et seulement si la première composante non nulle de α ´ β est négative. YATMA DIOP 3 UCAD-EDMI CHAPITRE 1. RAPPELS SUR LES BASES DE GRÖBNER — L’ordre lexicographique gradué ăgrlex défini par X α ăgrlex X β ô $ ’& ’% |α| ă |β| ou |α| “ |β| et Xα ălex Xβ En considérant l’alphabet tX, Y, Zu avec Z ă Y ă X, on a Z 4 ălex XYZ ălex X2Z et XYZ ăgrlex X2Z ăgrlex Z 4 . Remarque I.1. Sur l’anneau des polynômes en une seule indéterminée, tous les ordres monomiaux sont identiques. Ainsi, on ne parle que de l’ordre du degré. Définition I – 2.5. Soient f P KrXs, G Ă KrXs et ă un ordre monomial fixé. 1. Le maximum du support de f relativement à ă est appelé monôme dominant de f et noté LMăpfq. L’ensemble des monômes dominants de G est LMăpGq “ tLMăpfq|f P Gu. 2. Le coefficient de LMăpfq est appelé coefficient dominant de f et noté LCăpfq. L’ensemble des coefficients dominants de G est LMăpGq “ tLMăpfq|f P Gu. 3. Le produit LCăpfqLMăpfq est appelé terme dominant de f et noté LTăpfq. L’ensemble des termes dominants de G est LTăpGq “ tLTăpfq|f P Gu. S’il n’y a aucun risque de confusion alors on notera uniquement LM, LC et LT au lieu de LMă, LCă et LTă. Exemple I – 2.3. Soit f “ 2X2Z ` XYZ ´ Z 4 . Alors 1. LMălex pfq “ X2Z, LCălex pfq “ 2, LTălex pfq “ 2X2Z. 2. LMăgrlexpfq “ Z 4 , LCăgrlexpfq “ ´1, LTăgrlexpfq “ ´Z 4 . Définition I – 2.6. Etant donnés un ordre monomial et des monômes Xα et Xβ . On note par CMpXα , Xβ q l’ensemble des multiples communs à Xα et Xβ . Le plus petit élément de CMpXα , Xβ q est appelé plus petit commun multiple de Xα et Xβ . Il est noté LCMpXα , Xβ q.

Bases de Gröbner commutatives sur un corps 

 Généraliés sur les bases de Gröbner commutatives sur un corps Définition I – 3.1. Un idéal est dit monomial s’il peut être engendré par des monômes. Exemple I – 3.1. L’idéal I “ xX2Y, Y2 , XZYy est un idéal monomial de RrX, Y, Zs. Définition I – 3.2. Soit G Ă KrXs, I “ xGy et ă un ordre monomial. On dit que G est une base de Gröbner de I relativement à ă si xLMpGqy “ xLMpIqy. Une fois la définition établie, la question est de savoir comment les bases de Gröbner résolvent-elles toujours le problème posé. La réponse se trouve dans le théorème suivant. Théorème I.3. Si G est une base de Gröbner alors pour tout polynôme f il existe un unique couple pg,rq P xGy ˆ Gr tel que f “ g ` r. Démonstration. Soit f un polynôme et G une base de Gröbner. On applique à f l’algorithme de réduction modulo G empruntant deux chemins différents. Ainsi, on a : f “ g1 ` r1 “ g2 ` r2, g1, g2 P xGy, r1,r2 P Gr. g1 ` r1 “ g2 ` r2 ñ g1 ´ g2 “ r2 ´ r1 P xGy. Or G est une base de Gröbner. Si r2 ´ r1 ‰ 0 alors LMpr2 ´ r1q P xLMpGqy ; ie rSupppr1q Ť Supppr2qs Ş xLMpGqy ‰ H ; ce qui est absurde. D’où r2 ´ r1 “ 0 ; ie r1 “ r2. ˝ Définition I – 3.3. Soient f un polynôme, G une base de Gröbner et pg,rq l’unique élément de xGy ˆ Gr tel que f “ g ` r. Alors, le polynôme r est appelé forme normale de f modulo G. On note r “ NFpf, G, ăq ou r “ NFpf, Gq ou r “ NFpfq s’il n’y aucune ambiguité sur l’ensemble G et l’ordre monomial ă. L’unicité du reste est très importante et le théorème suivant en résulte. Théorème I.4. Soit G une base de Gröbner d’un idéal I relativement à un ordre monomial ă et f un polynôme. Alors f P I si et seulement si NFpf, G, ăq “ 0. Ainsi, les bases de Gröbner résolvent donc efficacement le problème de l’appartenance d’un polynôme à un idéal donné et se distinguent des parties génératrices quelconques. Ceci conduit à la question de savoir comment se caractérisent les bases de Gröbner. Tout d’abord, on a la définition suivante. Définition I – 3.4. Soient f et g deux polynômes et Xγ “ LCMrLMpfq, LMpgqs. On appelle S-polynôme de f et g le polynôme noté S-polpf, gq défini par Calculé en fonction des monômes dominants, le S-Polynôme dépend de l’ordre monomial choisi. Cependant, on peut remarquer que pour toute paire pf, gq de polynômes et tout ordre monomial ă fixé, LMrS-Polpf, gqs ă LCMrLMpfq, LMpgqs. Le théorème suivant est le résultat fondamental des bases de Gröbner. Il donne une caractérisation complète de ces dernières à partir des S-polynômes. Le lecteur peut se réfèrer à [20, page 74] pour la preuve. Théorème I.5 (Critère de Buchberger). Soient G Ă KrXs et ă un ordre monomial. Les assertions suivantes sont équivalentes. 1. G est une base de Gröbner. 2. Pour toute paire pf, gq P G2 , S-Polpf, gq GÝÑ 0 Ce théorème est l’outil principal utilisé pour vérifier si un ensemble donné est une base de Gröbner ou non relativement à un ordre monomial fixé. Exemple I – 3.3. L’efficacité des bases de Gröbner dans la résolution du test d’appartenance conduit également à la question de savoir si tout idéal admet une telle base. La réponse est donnée par l’algorithme de Buchberger. Cet algorithme construit une base de Gröbner à partir d’une partie génératrice quelconque dont l’existence est garantie par le théorème de la base de Hilbert. Théorème I.6 (Théorème de la base de Hilbert). Tout idéal I de KrXs admet une partie génératrice finie. L’algorithme de Buchberger suivant découle du Théorème I.5. Il permet de construire une base de Gröbner d’un idéal I à partir d’une partie génératrice G par des ajouts successifs des réduits non nuls des S-Polynômes. Il est évident que les S-polynômes définis dans l’ensemble G pretournéq seront tous réduits à zéro.