Exemples d'anneaux effectifs
20
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
20
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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).
Voir
- 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
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 mani ere 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´equant a 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 reconsid ere les quotients Z n ,constructionsquel'onge´n´eralise ad'autresanneaux.Leprojet alan 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 mani ere 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´esenterunnombreirrationneldemani ereexacte. » Certes, mais nul ne nous oblige derepr´esenternosnombresparund´eveloppementde´cimal!Lessous-anneaux Q [ 2 ] et Q [ ϑ ] de R , par exemple, contiennentdesnombresirrationnels,maisonpeuttr esbeinlesrepr´esentersurordinateur!(Comment?) Sil'argumentintuitifestfaux,ilnousmettoutdemˆemesurlabonnepiste.Apr esr´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
ChapitreXIIExemplesd'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,puisonpassera al'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 tr es utile de disposer d'une solution ! Pour l'anneau Z vousconnaissezbiensˆurlasolutiondeceprobl eme:oncosntruit le corps des fractions Q .Onetablitainsiunethe´oriepluslargemaistoujourscoh´erente,danslaquellele ´ probl emeinitialseretrouveetsere´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 r egles suivantes : ba + dc = adb + dbc et ba cd = abcd .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 Ε ) o u 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 estunique aisomorphismepr es.Formulezpre´cis´ementecquecela veut dire, p is prouvez votre ´ ´ u enonce. Exercice/M 1.5 . Contrairement al'unicit´e,l'existencen'estpastoujoursdonne´e:montrerqu'unanneaunonint egre n'admet pas de corps de fractions. Heureusement pour nous, c 'est le seul obstacle : The´ore me 1.6. Tout anneau inte gre admet un corps de fractions. Exercice/M 1.7. O ucherchercecorps?Commentprouversonexistence?Iln'yaqu'uneseulepossibilit´e: ilfautleconstruire!D´emontrerlethe´or emeende´tailalntlaconstructionsuivante. E SQUISSE DE PREUVE . Supposons que A est un anneau int egre. Notre but est de donner un sens aux quotients ba dansuncorpsencore aconstruire.Ens'inspirantdesproprie´t´essouhaite´es,onconsid ere 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!O uutilise-t-onl'int´egrit´edel'anneau A ´ dansceraisonnement?)Laclassed'´equivalencede ( a b ) est note´e ab . 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 int egre, comme Z 6 par exemple ? MAE 22 juin 2009
