Exemples d'anneaux effectifs

Description

CHAPITRE XII Exemples d'anneaux effectifs The mathematician is entirely free, within the limits of his imagination, to construct what worlds he pleases. John W. N. Sullivan Objectifs ? Expliciter ce qu'il faut pour rendre un anneau effectif. ? Implementer les nombres rationnels comme un exemple de base. ? Plus generalement, implementer le corps des fractions ou un anneau quotient. Un anneau est effectif s'il existe une maniere de representer chacun de ses elements sur ordinateur et des algorithmes pour effectuer chacune des operations de l'anneau dans la representation choisie. L'ap- proche effective est une vraie restriction quant aux anneaux en question et un important defi quant a l'ingeniosite algorithmique. Ce chapitre precise ce que l'on exige d'un anneau effectif, discute quelques exemples typiques, et presente des implementations possibles. Notre exemple phare est, bien sur, l'anneau Z. La representation des entiers et les algorithmes de base ont ete discutes aux chapitres II, IX, et XI. On discute dans le present chapitre son corps des fractions Q et on reconsidere les quotients Zn, constructions que l'on generalise a d'autres anneaux. Le projet a la fin traite de l'anneau Z[i] des entiers de Gauss. Voici trois exemples importants et assez representatifs pour illustrer l'etendue du concept : Exemple 0.1. L'anneau Q[ √ 2] est effectif : c'est un Q-espace vectoriel a base (1, √ 2).

• classe rationnel


• anneau


• homomorphisme d'anneaux injectif


• construction du corps des fractions


• operations de l'anneau dans la representation choisie


• affectation par copie


• rationnel


• a?


• corps de fractions


• representation

Sujets

• multiplication
• exercice
• mathe
• cours
• exercices
• cours de

Informations

• Publié par: pefav
• Nombre de lectures: 32
• Langue: Français

Extrait

CHAPITRE XII

The mathematician is entirely free, within the limits of his imagination, to construct what worlds he pleases. John W. N. Sullivan

Exemples d'anneaux effectifs

Objectifs ◮ Expliciter ce qu'il faut pour rendre un anneau effectif. ◮ Imple´menter les nombres rationnels comme un exemple de base. ◮ Plusg´ene´ralement,imple´menterlecorpsdesfractionsouunanneauquotient. Un anneau est effectif s'il existe une maniere de repre´senter chacundeses´ele´mentssurordinateuret des algorithmes pour effectuer chacune des ope´rations de l'anneau dans la repre´sentatio n choisie. L'ap- procheeffectiveestunevraierestrictionquantauxanneauxenquestionetunimportantd´equanta l'ing´eniosit´ealgorithmique.Cechapitrepre´cisecequel'onexiged'unanneaueffectif,discutequelques exemplestypiques,etpre´sentedesimpl´ementationspossibles. Notre exemple phare est, bien s ˆur, l'anneau Z . La repre´sentation des entiers et les algorithmes de base ont´ete´discute´sauxchapitresII,IX,etXI.Ondiscutedanslepre´sentchapitresoncorpsdesfractions Q et on reconsidere les quotients Z n ,constructionsquel'onge´n´eralisead'autresanneaux.Leprojetalan traite de l'anneau Z [ i ] des entiers de Gauss. Voici trois exemples importants et assez representatifs pour illustrer l'e´tendue du concept : ´ Exemple 0.1. L'anneau Q [ 2 ] est effectif : c'est un Q -espace vectoriel a base ( 1  2 ) . On peut donc travailler avec des couples ( a  b ) ∈ Q 2 pourrepr´esentertout´ele´ment a + b 2 de maniere unique. Exercice. — Exprimer les ope´rations de l'anneau Q [ 2 ] sous cette forme. Exemple 0.2. Si A est effectif, alors l'anneau A [ X ] des polyn ˆomes sur A est effectif. Exercice. — L'id´ee ´evidentemarchera:onrepr´esentetoutpolynˆome P ∈ A [ X ] par la suite nie de ses coefcients dans A . D´etaillercetterepre´sentationetlesope´rationsdel'anneau A [ X ] . Exemple 0.3. Le corps R des nombres ´ ls ar contre, n'est pas effectif. Ceci sur prend beaucoup les ree , p ´ de´butants, mais la vie est ainsi faite. Evidemment le corps R est de grande importance ; toute l'analyse s'appuie sur lui, et dans des applications il est souvent ind ispensable d'effectuer des calculs « r´eels » sur ordinateur.Lesdifcult´es d'approcher des calculs dans R surordinateurfontl'objetducalculnum´erique. Attention. — Les types float et double nemod ´ elisentpas lecorpsdesnombresr´eels!Loindecela,ils ne representent qu'un sous-ensemble ni de nombres rationnels, ce qui n'a rien a voir avec R . ´ Remarque 0.4 . Voici un argument intuitif mais faux que R n'est pas effectif : « il est impossible de stocker une suite innieded´ecimalespourrepr´esenterunnombreirrationneldemaniereexacte. » Certes, mais nul ne nous oblige derepr´esenternosnombresparund´eveloppementde´cimal!Lessous-anneaux Q [ 2 ] et Q [ ϑ ] de R , par exemple, contiennentdesnombresirrationnels,maisonpeuttresbeinlesrepr´esentersurordinateur!(Comment?) Sil'argumentintuitifestfaux,ilnousmettoutdemˆemesurlabonnepiste.Apresr´eexion,onenextraitune re´ponseplussolide:larepr´esentationd'unnombre x sur ordinateur doit se faire par un objet ni (arbitrairement grand, mais toujours ni pour chaque x individuellement).Onpeutainsirepr´esenterseulementunnombre d´enombrable d'´el´ements,maislecorps R est non de´nombrable . Sommaire 1. De l'anneau Z au corps Q . 1.1. Qu'est-ce qu'un corps de fractions ? 1.2. Imple´mentat ion du corps Q .1.3.Leprincipedebase:encapsulerdonn´eesetm´ethodes! 2. Anneaux effectifs. 2.1. Que faut-il pour imple´menter un anneau ? 2.2. Vers une formulation math´ematique.2.3.Anneauxeuclidiens.2.4.Anneauxprincipaux.2.5.Anneauxfactoriels. 2.6. Corps des fractions. 2.7. Anneaux quotients. 215

216

ChapitreXII—Exemplesd'anneauxeffectifs

1. De l'anneau Z au corps Q Oncommenceparunexempleconcretetpratique,quel'ong´ene´raliseradanslasuite:lepassagede l'anneau Z des nombres entiers au corps Q desnombresrationnels.Onr´eviserad'abordlaconstructiondu corpsdesfractions,puisonpasseraal'impl´ementationenC++.

1.1. Qu'est-ce qu'un corps de fractions ? Certaines´equationsdutype a = bx avec a  b ∈ Z n'ont pas de solution x dans Z . C'est le cas, par exemple, pour l'e´quation 2 = 3 x . Il serait pourtant tres utile de disposer d'une solution ! Pour l'anneau Z vousconnaissezbiensˆurlasolutiondeceprobleme:oncosntruit le corps des fractions Q .Onetablitainsiunethe´oriepluslargemaistoujourscoh´erente,danslaquellele ´ problemeinitialseretrouveetsere´solve.Essayonsd'ende´gagerunere´ponsege´n´erale,quienglobetous les anneaux commutatif unitaires. Exercice/M 1.1 . Soit A un anneau commutatif unitaire. Optimiste que nous sommes, supposons dans un premier temps qu'il existe un homomorphisme injectif Ε : A → L dans un corps L . An de simplier la notation nous pouvons identier A avec son image Ε ( A ) , et ainsi supposer que A ⊂ L . (Pourquoi ?) Dans ce cas on peut regarder l'ensemble Frac ( A ) ⊂ L forme´des´el´ements ba = ab − 1 tels que a ∈ A et b ∈ A ∗ . Ve´rier d'abord que ba = dc si et seulement si ad = bc . ´ Etablir ensuite les regles suivantes : ba + dc = ad b + dbc et ba  c d = a b c d .End´eduirequeFrac ( A ) est un sous-corps de L , contenant A . Plus pre´cise´ment c'est le plus petit sous-corps de L qui contienne A . On l'appelle corps des fractions de A dans L . Fortsdecettev´ericationrassurante,formulons-enlade´nitionge´n´erale: De´nition 1.2. Soit A un anneau commutatif unitaire. Un corps de fractions de A est la donne´e d'un couple ( K  Ε ) ou K est un corps et Ε : A → K est un homomorphisme d'anneaux injectif, de sorte que tout ´ele´ment x ∈ K s'´ecrivecomme x = Ε ( a ) Ε ( b ) − 1 avec a ∈ A et b ∈ A ∗ . Exemple 1.3 . Q est un corps de fractions de Z via l'inclusion Ε : Z ⊂ Q . Par contre, R n'est pas un corps de fractions de Z : certains e´le´ments x ∈ R nes'´ecriventpascomme ba avec a ∈ A et b ∈ A ∗ . Soit p premier et Β : Z → Z p l'homomorphisme canonique. Tout e´le´ment x ∈ Z p s'´ecritcomme Β ( a ) Β ( 1 ) − 1 avec a ∈ Z . Le couple ( Z p  Β ) n'est cependant pas un corps de fractions, car l'homomorphisme Β n'est pas injectif. Exercice/M 1.4 . Un corps de fractions ( K  Ε ) de A ser´ejouitdelapropri´ete´universellesuivante:si Β : A → L est un homomorphisme injectif dans un corps L , alors il existe un et un seul homomorphisme 8 : K → L tel que 8 ◦ Ε = Β . Ilend´ecoulequelecorpsdesfractions ( K  Ε ) de A estuniqueaisomorphismepres.Formulezpre´cis´ementecquecela veut dire, p is prouvez votre ´ ´ u enonce. Exercice/M 1.5 . Contrairemental'unicit´e,l'existencen'estpastoujoursdonne´e:montrerqu'unanneaunonintegre n'admet pas de corps de fractions. Heureusement pour nous, c 'est le seul obstacle : The´oreme 1.6. Tout anneau integre admet un corps de fractions. Exercice/M 1.7. Oucherchercecorps?Commentprouversonexistence?Iln'yaqu'uneseulepossibilit´e: ilfautleconstruire!D´emontrerlethe´oremeende´tailalntlaconstructionsuivante. E SQUISSE DE PREUVE . Supposons que A est un anneau integre. Notre but est de donner un sens aux quotients b a dansuncorpsencoreaconstruire.Ens'inspirantdesproprie´t´essouhaite´es,onconsidere l'ensemble F = A × A ∗ avec les ope´rations ( a  b ) + ( c  d ) : = ( ad + bc  bd ) et ( a  b )  ( c  d ) : = ( ac  bd ) . On constate que ( F  +   ) n'est pas un anneau, encore moins un corps. (Pourquoi ? Il y a une exception : laquelle ?) An de sortir de cette impasse, on de´nit la relation ( a  b ) ∼ ( c  d ) si ad = bc .Onv´eried'abord qu'ils'agitd'unerelationd'´equivalence,ensuitequelesope´rations + et  sontbiend´eniessurlequotient K = F  ∼ , et nalement que ( K  +   ) estuncorps.(Lede´tailler!Ouutilise-t-onl'int´egrit´edel'anneau A ´ dansceraisonnement?)Laclassed'´equivalencede ( a  b ) est note´e a b . L'application Ε : A → K donnee par a 7→ a 1 est un homomorphisme d'anneaux injectif. On peut ainsi iden tier l'anneau A avec son image Ε ( A ) . Cecifait,onconstatequetout´ele´ment x ∈ K s'e´crit comme x = ab − 1 avec a ∈ A et b ∈ A ∗ .  Exercice/M 1.8 . Ve´rier que cette construction applique´e a Z donne le corps Q comme vous le connaissez. Tout corps de caracte´ristique 0 contient donc Q comme un sous-corps. Exercice/M 1.9 . Qu'obtient-on si l'on l'applique a R [ X ] ? Plus ge´ne´ralement a K [ X ] sur un corps K ? Que se passe-t-il lorsqu'on l'applique a un anneau non integre, comme Z 6 par exemple ? MAE 22 juin 2009