[PDF] Calcul de résolvantes avec les modules de Cauchy

View - Download Calcul de résolvantes avec les modules de Cauchy

Previous PDF

Next PDF

Calcul de résolvantes avec les modules de CauchyNicolas Rennert et Annick ValibouzeTABLE DES MATIÈRES1. Introduction2. Notations et définitions3. Polynômes caractéristiques et résolvantes4. Calcul du polynôme caractéristique dans l"algèbre de

décomposition universelle

6. Calcul de la résolvante absolue

7. Généralisation aux multi-résolvantes

8. Implantation

9. Temps de calculs et comparaisons avec SYM

10. Conclusions

Disponibilité electronique

Bibliographie

Lesauteursremercientlepro jetGALOISduGDRdeCalculFormelMEDICIS? Cet article décrit un algorithme nouveau et efficace pour cal- culer des polynômes caractéristiques d"endomorphismes dans un algèbre quotient en utilisant les modules de Cauchy. Cet al- gorithme est ensuite utilisé pour calculer des résolvanteset des multi-résolvantes absolues, outilsde base de la théorie des corps et donc aussi de la théorie de Galois constructive. We give a new and efficient algorithm to compute some char- acteristic polynomials using Cauchy modules. This algorithm is used for the computation of absolute resolvents and multi- resolvents which are essential tools in constructive Galois the- ory.

1. INTRODUCTION

Lar?solvanteestl?outildebasedelath?oriedeGaloise?ectivedontlecalcul?lamains?av?reviteimp ossible?Ainsi?chercher?diminuerletempscon?sacr??soncalculam?lioreceluiducalculdugroup edeGaloisd?unp olyn?me?Historiquementlespre?miers?r?aliserdetelscalculs?l?aidedel?outilinformatique?furentR?P?Stauduhar?1973?etK?Girstmair?1983?utilisantp ourlepremierunem??tho debas?esurdescalculsnum?riques?Bienqueler?sultatnesoitpascerti???cettem?tho des?av?re?trelaplusrapidedanslecasg?n?ral?LelogicielGALP?EichenlaubetOlivier1996?bas?esurlali?brairiePARI?GP?utilisecestechniquesp ourd?ter?minerlegroup edeGaloisdep olyn?mes?Lesm?tho desalg?briquesontenrevanchel?avan?taged??treexactes?Parmielles?lesm?tho desbas?essurlesfonctionssym?triquess?av?rente?cacesp ourdesinvariantsparticuliers ;voir?Valib ouze1989?? Cetarticles?int?resseauxalgorithmesquicalculentdesr?solvantesp ouruninvariantquelconqueetquisontbas?ssurl?op ?rationder?sultant?Ler?sultantestunoutilparticuli?rementpuissantp ourmanipuleralg?briquementlesracinesdep oly?n?mesquidepuisLagrangeaservip ourlecalculdelar?solvante ;voir?Lagrange1770??Lepremierqui

c ?A K Peters, Ltd.

1058-6458/1999 $0.50 per page

Experimental Mathematics8:4, page 351

352Experimental Mathematics, Vol. 8 (1999), No. 4

surmachineautilis?ler?sultantp ourlecalculder?solvantes?absolues?estL?H?Soicher?1984?p ourdesinvariantslin?aires?Jusqu??pr?sentlesm?tho desbas?essurler?sul?tantp ourcalculerlar?solvante?absolue?seheur?taient?deuxd?fauts :apparitiondefacteursetdepuissances?parasites?quiaugmententconsid?rable?mentlatailledesp olyn?mesn?cessairesetr?duisentdoncl?e?cacit??Cetarticlepr?senteunalgorithmesimpleetrapide?voirth?or?me4?7?quicalcule?sansformationdefacteursparasites?lep olyn?mecarac?t?ristiqued?unendomorphismemultiplicatifasso ci??uninvariantquelconquedonn??Lep olyn?meca?ract?ristiqueestunepuissancedelar?solvantep ourcem?meinvariant?Ainsileprobl?medesfacteurs?parasites?estr?solu?resteencoreceluidelapuis?sance?parasite??L?algorithmeprop os?utilisees?sentiellementler?sultantetlesmo dulesdeCau?chyquiformentunebasedeGr?bnerr?duitedel?id?aldesrelationssym?triques?p ourl?ordrelexico?graphique??Silescalculsduth?or?me4?7sontr?a?lis?smo dulol?id?aldesrelationssym?triquesalorslapuissances?laquellenousobtenonslar?solvanteestr?duiteetlescalculsinterm?diairesacc?l?r?s?Silescalculsmo dulairesn?ab outissentpas?lar?sol?vantesmais?unepuissancestrictementp ositive?cequiestpr?visibleapriorialorsnousutilisonsalorsler?sultatdeF?Lehob ey?1997?p our?liminercespuissancesencoursdecalcul?cetravailfaitr?f??renceauxr?sultatsdearticle??Ainsileprobl?medelapuissanceparasiteest?galementr?solu?voiralgo6?10??Dansleparagraphe7l?algorithmedecalculdesr?solvantesestnaturellementg?n?ralis?aucasdesmulti?r?solvantes ? c?est???direlesr?solvantesrela?tives?unpro duitdegroup essym?triques?Lesder?niersparagraphessontconsacr?s?l?implantationdecettem?tho de?lacomparaisonavecd?autresalgo?rithmesalg?briquesainsiquedesam?liorations?

2. NOTATIONS ET DÉFINITIONS

?Kd?signeuncorpsdecaract?ristique0 ;?xestunevariableind?termin?esurK;?festunp olyn?meunitairedeK?x?dedegr?n;?x1

? ? ? ?? xn sontdesvariablesind?termin?essurK;?K?x1 ? ? ? ?? xn ?d?signel?anneaudesp olyn?mesenlesvariablesx1 ? ? ? ? ? xn et?co e?cientsdansK; ?K?x1 ? ? ? ?? xn ?d?signelecorpsdesfractionsdeK?x1 ? ? ? ? ? xn ?;??estunp olyn?meappartenant?K?x1 ? ? ? ?? xn ?;?????1 ? ? ? ? ? ?n ?estuneliste?ordonn?e?form?edesnracinesdup olyn?mefdansunecl?turealg?brique ? ? ? ?? ?n ?;?Sn d?signelegroup esym?triquededegr?n? Definition 2.1.Lep olyn?me?estditd?arit?msimestleplusp etitentierjtelqu?ilexistejentiersdistinctsi1 ? ? ? ? ? ij v?ri?ant?2K?xi 1 ? ? ? ?? xi j Definition 2.2.Si?????0alors?estapp el?eune??relation?

Definition 2.3.L?actiondugroup esym?triqueSn

sur?estd??niepar :? ?????x??1? ? ? ? ?? x??n? ?p ourtout?2Sn

Definition 2.4.L?actiondugroup esym?triqueSn

sur? K nestd??nie?p ourtout?2Sn ettout????1 ? ? ? ?? ?n ?2 ?K n?par?? ?????1? ? ???2? ? ? ? ? ? ???n? Definition 2.5.L?orbitede?sousl?actiond?unsous?groupeLdeSn ?not?eL???estd??niepar :L???f? ??j?2Lg

Definition 2.6.SoientLetHdeuxsous?group esdeS

n telsqueLcontienneH?Lep olyn?me?estditL?primitifH?invariantsiHestlestabilisateurde?dansL:H?StabL ????f?2Lj? ????g?LorsqueL?Sn

Exemple 2.7.SoitH?S2

?Sn?2 ?Lep olyn?me??x 1 ?x2 estunSn ?primitifH?invariant? Definition 2.8.Soientdeuxsous?group esLetHdugroup esym?triqueSn telsqueLcontienneH?Onapp eleral?ensemblef?1 ? ? ? ?? ?e gunetransversale?gauchedeLmo dHsi?1

H ? ? ? ? ? ?e

Hsontlesdi???rentesclasses?gauchesdeLmo dH?

Definition 2.9.Pouri?0? ? ? ?? n?lai?i?mefonctionsym?trique?l?mentaireenx1 ? ? ? ?? xn ?not?eei ?estd??niepare0 ?1ete i Xm2Sn ??x1 ???xi mp ouri?1? Rennert et Valibouze: Calcul de résolvantes avec les modules de Cauchy353

Remarque 2.10.

Rapp elonsquef?x??x

n?e1 ???x n?1?e2 ???x n?2?? ? ????1? ne n Definition 2.11.Lesnfonctionsinterpolairesintro?duitesparAmp ?re?1826?v?ri?ent :f i

2K?xi?1

? ? ? ? ? xn ??x?etdegx ?fi ??ietsontd??niesparfn ?x??f?x?etf i ?x??fi ?x? xi?1 ? ? ? ?? xn f i?1 ?x??fi?1 ?xi?1 x?xi?1p ourn?1?i?1?

Definition 2.12.Lesp olyn?mesf1

?x1 ??f2 ?x2 ??? ? ? ?f n ?xn ?sontapp el?slesmodulesdeCauchyasso ci?saup olyn?mef? Definition 2.13.SoitLunsous?group edugroup esy?m?triqueSn ?L?id?alI L? ?fr2K?x1 ? ? ? ? ? xn ?j?8?2L??? ?r?????0gestunid?alradicalapp el?id?aldes??relationsin?variantesparL?

Definition 2.14.L?id?alI

S n?

Definition 2.15.SoitIn

legroup eidentit?dansSn ?L?id?alI I n? ?not?I? ?estconnusouslenomd?id?aldes??relations?

Remarque 2.16.LequotientK?x1

? ? ? ?? xn ??Iestap?p el?alg?breded?compositionuniversel le?

Definition 2.17.Lesous?group eG?

dugroup esym??triqueSn d??niparG ?f?2Sn j?8r2I? ??? ?r?????0gestconnuabusivementsouslenomdegroupedeGaloisdef?Onlenommeragroup edeGaloisde??

Notation 2.18.SoitIunid?aldeK?x1

? ? ? ?? xn ??Pour?2K?x1 ? ? ? ?? xn ?notons ? ? ? ?? xn ? ? ? ?? xn ??I ?Lep olyn?mecaract?ristiquedel?endomorphisme ??seranot????I ?SiI?Ialorsilseranot?simplement? Definition 2.19.SoitLunsous?group edugroup esy?m?triqueSn telqueLcontiennelegroup edeGaloisG dup olyn?mef?LaL?relativer?solvantedefpar??asso ci?e?lanum?rotation???not?eL??L?? ?estlep olyn?medeK?T?d??nicommesuit :L ??L?? ?T??

Y?2L??

?T???????SiL?Sn ?lar?solvanteestnot?eL??f etapp el?er?solvante?absolue?defpar??Commelegroup eLcontientlegroup edeGaloisG

3. POLYNÔMES CARACTÉRISTIQUES ET RÉSOLVANTES

Dansceparagraphe?lep olyn?mefestsupp os?s?parable?sesracinessontdistinctesdeux?deux?etLd?signeunsous?group edeSn

quicontientlegroup edeGaloisG?

Proposition 3.1.Lavari?t?del?id?alI

L? dansunecl??turealg?briquesdeK?not?eV?I L? L? ??f??

Démonstration.Lapreuveestsimple?Voir?Valib ouze1999???Pourunid?alIradical?leth?or?medeStickel?b ergerdonnecetteexpressionexplicitedup olyn?mecaract?ristiquedel?endomorphisme

??asso ci??unid?alI?voirnotation2?18? :? ??I ?T??

Y?2V?I?

?T???????Commel?id?alI L? estradicaletquelep olyn?mefests?parable?ilvient :? ??I L? ?T?? Y?2L ?T?? Y?2Sn ?T??? ?? ?????? (3-1)

354Experimental Mathematics, Vol. 8 (1999), No. 4

SoientHunsous?group edugroup eLetTunetransversale?gauchedeLmo dH?Si?estunL?primitifH?invariantnousavonsl?identit?suivantebienconnue :L

??L?? ?T?? Y?2T ??I L? ??L??L?? card?H? (3-2)

o?ilappara?tquelep olyn?mecaract?ristiques?ex?primecomme unepuissancedelar?solvanteabsolue?Danslepro chainparagraphenousverronscom?mentsecalculelep olyn?mecaract?ristique??

li??l?alg?breded?comp ositionuniverselle?puisdanslessuivantsnouschercherons?calculerlar?solvanteabsolue?partirdelatramedel?algorithmedecalculdup olyn?mecaract?ristique?

4. CALCUL DU POLYNÔME CARACTÉRISTIQUE DANS

L"ALGÈBRE DE DÉCOMPOSITION UNIVERSELLE

Rappel 4.1.Soientuetvdeuxp olyn?mesdeK?x??avecu?x??a Q mi?1 ?x??i ?o??1 ? ? ? ?? ?m appar?tiennent?unecl?turealg?briquedeK?Ler?sultantenxdesdeuxp olyn?mesuetv?not?Resx ?u? v??p euts?exprimerainsi :Res x ?u? v??a deg?v? m Yi?1 v??i

4A. La méthode d"Arnaudiès

lam?tho deprop os?edans?Arnaudi?s1992?estbas?esurler?sultant?nvariables?Notonsxn?1 ? ? ? ?? xn ?L?homog?n?is?de??not?? ??estdonn?par :? ??x dn?1 x 1 xn?1 x nxn?1

NotonsRes?g1

? ? ? ?? gn ?ler?sultantdenp olyn?mesg 1 ? ? ? ?? gn homog?nesnonconstants?nvariables?

Théorème 4.2 (Arnaudiès).Posonssi

?ei ?ei ???pouri?1? ? ? ?? n?Alorslepolyn?mecaract?ristiqueestdonn?par:? ?T??Res?s ?1 ? ? ? ?? s ?n ? T x dn?1

???Ceth?or?med?montr?dans?Arnaudi?s1992?sed?duitdelaformuledePoisson?Perron :voir?Ar?naudi?s1989?p?243??Lecalculder?sultant?nvariabless?av?retr?sco?teux?cettem?tho den?estdoncpasutilisableenpratique?

4B. La méthode de Lagrange

Ceparagraphetraduitentermeder?sultants?lam?thodequeJ?L?Lagrange?1770?prop osaitp ourcalculerlar?solvanteabsolueL??f

etquicalculelep olyn?mecaract?ristique?Soit?Ui ?0?i?n lasuite?nied??nieinductivementparU0 ?T ? x1 ? ? ? ?? xn ??T???x1 ? ? ? ?? xn ?etU i ?T ? xi?1 ? ? ? ?? xn ??Res x i ?f?xi ? ? ? ?? xn ?? Ui?1 ?T ? xi ? ? ? ?? xn ??p our1?i?n?Alors?d?apr?slerapp el4?1etpuisquefestunitaire :U n ?T?? n Yi n ?1 n Yi n?1 ?1 n Yi 1 ?1 ?T????i 1 i n ???LesfacteurssurKdup olyn?meUn ?T?sont?lep olyn?mecaract?ristique??

;?desfacteursditsparasitesprovenantdes?galit?sdeux?deux?trois?trois?? ? ? ? n?ndesindicesapparaissantdanslespro duits?E?ectivementlesnombresalg?briquestels???1

??1 ??3 ?? ? ???n ?????1 ??1 ??1 ??3 ?? ? ???n ??? ? ? ????1 ??1 ?? ? ???1 ?sontracinesdeUn

?T?etnesontpasracinesdup olyn?mecaract?ristique?Cesfacteursparasites?taientd?j?signal?sparJ?L?Lagrange?Cesontdesp olyn?mescaract?ris?tiquesasso ci?s?desinvariantsd?arit?strictementinf?rieure?celledel?invariant??Pard?croissancestrictedel?arit??ilestdonctoujoursp ossibleded??duirelep olyn?mecaract?ristique??

?partirdup o?lyn?meUn ?Donnonsunexempleexplicite : Rennert et Valibouze: Calcul de résolvantes avec les modules de Cauchy355

Exemple 4.3.

Choisissonsl?invariant??x1

?2x2 etn?2?AlorsU 2 ?T???? ? ?3x1o??3x1 ?Resx ?f?x?? T?3x??DeplusL??f ???puisque?estunI2

?invariantprimitif?Lam?tho deprop os?eauparagraphe4C?vitelaformationdesfacteursparasitesetcalculedoncdi?rectementlep olyn?me caract?ristique?Lagrange?quicherchait?calculerlar?solvante?signalait?gale?mentlapuissanceparasiteprovenantdessym?triesdel?invariant?etquenousretrouvonsdanslafor?mule?3? 2??Ilestp ossibledediminuerlapuissanceencoursdecalcul?voirleparagraphe6consacr?aucalculdelar?solvante??

4C. Méthode des modules de Cauchy

Notonsf1

? ? ? ?? fn lesmo dulesdeCauchyasso ci?saup olyn?mef?voird??nition2?12??

Definition 4.4.Soientrunentierp ositifetsunen?tiercomprisentre1etn?Lar?i?mefonctionsym??triquecompl?te?not?ehr

?x1 ? ? ? ?? xs ??estlasommedesmon?mesdedegr?totalrenx1 ? ? ? ?? xs ?avech 0 ?x1 ? ? ? ?? xs ??1?Leth?or?mesuivantp ermetdelescalculere?ca?cementilsed?montrefacilement? Théorème 4.5 (Machì-Valibouze).Soitlepolyn?mef?x??x n?a1 x n?1?a2 x n?2?? ? ??an?coe?cientsdansK?Posonsa0 r ?xr r Xi?0 h i ?xr ? ? ? ? ? xn ?ar?i ?Enparticulierfn ?xn P ni?0 h i ?xn ?an?i ?f?xn ?etf 1 ?x1 ??h1 ?x1 ? ? ? ?? xn ??a1

Remarque 4.6.A?Cauchydonnalaformulejusqu??n?4?Uned?monstrationsimpleprop os?eparA?Lascouxp eut??trefaite?l?aidedesdi??rencesdivi?s?es ;voir?LascouxetPragacz1988??Leth?or?mesuivantdonneunem?tho deexpliciteducalculdup olyn?mecaract?ristique :

Théorème 4.7.Soitlasuite?nieR0

? R1 ? ? ? ?? Rn d???nieinductivementparR0 ?T ? x1 ? ? ? ?? xn ??T??etR i ?T ? xi?1 ? ? ? ? ? xn ??Res xquotesdbs_dbs46.pdfusesText_46

[PDF] Les calculs équations

[PDF] les calculs literaux

[PDF] Les calendriers

[PDF] Les calories joules Dm

[PDF] les calories( les valeurs énergétiques)

[PDF] Les campagnes ? l'époque des lumières

[PDF] les campagnes de prévention sont elles efficaces

[PDF] les campagnes françaises au début du XXem siècle

[PDF] Les camps de concentrations

[PDF] les cancers les plus fréquents au maroc

[PDF] Les cannibales de Montaigne

[PDF] Les capillaires et les globules rouges

[PDF] Les caprices de Marianne (Alfred de Musset)

[PDF] les caprices de marianne acte 1 scène 1 commentaire

[PDF] les caprices de marianne analyse acte 2 scene 3