presentee a l'Universite de Limoges pour l'obtention du

138

pages

Français

Documents

1992

Écrit par
Jean - Franc¸Ois Ragot

Publié par
profil-zyak-2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

138

pages

Français

Ebook

1992

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-zyak-2012

Publié le

01 mars 1992

Nombre de lectures

Langue

Français

Poids de l'ouvrage

1 Mo

Niveau: Supérieur, Doctorat, Bac+8
THESE presentee a l'Universite de Limoges pour l'obtention du Doctorat de l'Universite de Limoges en Mathematiques Specialite : Calcul formel (arrete du 30 Mars 1992 ) par Jean-Franc¸ois Ragot Sur la factorisation absolue des polynomes Soutenue le 4 Decembre 1997 devant le jury compose de Guy Robin President Dominique Le Brigand Carlo Traverso Gilles Villard Rapporteurs Dominique Duval Andre Galligo Marc Rybowicz Paul Zimmermann

factorisation absolue

instar des systemes de calcul formel

doctorat de l'universite de limoges en mathematiques

Voir

Publié par

profil-zyak-2012

Publié le

01 mars 1992

Nombre de lectures

Langue

Français

Poids de l'ouvrage

1 Mo

THÈSE

présentée à l’Université de Limoges pour l’obtention du

Doctorat de l’Université de Limoges en Mathématiques Spécialité : Calcul formel (arrêté du 30 Mars 1992)

par JeanFran¸coisRagot

Sur la factorisation absolue des polynômes

Soutenue le 4 Décembre 1997 devant le jury composé de

Guy Robin

Dominique Le Brigand Carlo Traverso Gilles Villard

Dominique Duval André Galligo Marc Rybowicz Paul Zimmermann

Président

Rapporteurs

Une thèse est une entreprise délicate. Tous ceux qui ont suivi ce long cheminement savent à quel point les errances qui l’émaillent pourraient être fatales sans le concours déterminant de quelques personnes, et la rencontre de beaucoup d’autres. Je tiens en premier lieu à remercier chaleureusement Dominique Duval : ce projet n’aurait pas abouti sans sa compétence, sa disponibilité, sa patience, et son optimisme. Marc Rybowicz a, depuis les balbutiements de cette thèse, toujours répondu à mes innom brables pourquoi et comment avec patience, et ce même à plusieurs milliers de kilomètres de distance : qu’il en soit vivement remercié. Merci à Dominique Le Brigand, Carlo Traverso et Gilles Villard d’avoir bien voulu rap porter sur cette thèse. Merci à André Galligo, Guy Robin et Paul Zimmermann de m’avoir fait le plaisir et l’honneur de faire partie du jury. Je tiens à remercier tous les membres du jury, qui se sont intéressés à ce travail et m’ont fait proﬁter de leurs diverses compétences à travers leurs critiques. Merci à JacquesArthur Weil et Gaëtan Haché : nos discussions mathématiques véspérales feront partie des bons souvenirs. Merci à tous ceux qui ont contribué à ma formation pédagogique, en particulier mes étudiants; j’éspère que celleci aura favorablement inﬂué sur la clarté de ce mémoire. Merci à Martine Guerletin, Véronique Merigoux et Nadine Tchefranoﬀ qui ont assuré l’indispensable “soutien logistique” avec patience et gentillesse. J’ai partagé avec plaisir mon bureau et mes soucis avec Christophe Durousseau, Pierre Dusart, Rachid Haﬁd et Gérard Juin. Je tiens enﬁn à remercier aﬀectueusement mes parents, mes soeurs et Guilène qui m’ont supporté, dans tous les sens du terme, durant toutes ces années.

Introduction

Un polynôme à coeﬃcients dans un corpsKest ditabsolument irréductibles’il est ir réductible sur toute extension algébrique deKurenetusruelctô,cooundéefa¸alenquiv algébrique deK. La factorisation absolue d’un polynôme est sa décomposition en facteurs absolument irréductibles. Ainsi déﬁnie, la factorisation absolue d’un polynômeFenrvariables est la traduction algébrique du problème géométrique suivant : soitVl’ensemble des zéros deFdans une r clôture algébrique deK; l’ensembleVdéﬁnit unehypersurfacede l’espace aﬃneK, et la décomposition deFen facteurs absolument irréductibles correspond à celle deVen composantes irréductibles. 2 2 Considérons par exemple le polynômeF=y−2xL’hyperlC . à coeﬃcients dans 2 surfaceVdes points (a, btels que) appartenant à Cl F(a, b) = 0 est unecourbe plane. √ √ Le polynômeFlefasodeocpmeséde:ntvauinscoa¸F= (y−2x) (y+ 2x) , les deux facteurs étant absolument irréductibles (clairement car de degré 1). Autrement dit, la √ √ courbeVse décompose en deux composantes d’équationsF1=y−2xetF2=y+ 2x, composantes qui sont elles mêmes irréductibles. Sur cet exemple, la “séparation” des composantes se “voit” sur la représentation graphique deV∩IR . Si l’on entre une commande du typef actor(F) en Maple par exemple, la réponse est 2 2 y−2xdit Maple considère. Autrement FPourtant, nous l’avonscomme irréductible. √ √ vu cidessus,F= (y−2x) (y+ 2x) . La commandef actor(F) renvoie la factorisation deFsur le plus petit corps contenant ses coeﬃcientslQ . , ici Ainsi Maple, à l’instar des systèmes de calcul formel les plus sophistiqués, sait faire de lafactorisation rationnelle, que nous déﬁnirons commefactorisation sur un corps donné(contenant les coeﬃcients du polynôme à factoriser). Ce corps peutêtre explicitement ou implicitement spéciﬁé. Pour notre exemple, le corps sousentendu est lQ . Il est déﬁni à la fois explicitement par les coeﬃcients deF, et implicitement puisque aucune référence à la caractéristique n’est faite dans la commandef actor(FOn peut alors entrer successivement les commandes) . 2 2 α=RootOf(T−2) , qui déﬁnitαcomme étant une racine deT−2 dans Cl , puis f actor(F ,{α}demande la factorisation de) qui Fsur le plus petit corps contenant ses coeﬃcients etα, et qui renvoie (y−α x) (y+α xOn sait factoriser entre autres sur) . lQ , sur les corps ﬁnis et sur les extensions algébriques de degré ﬁni des précédents. D’après cette déﬁnition, la factorisation rationnelle d’un polynôme peut être déﬁnie sur un corps quelconque. La factorisation absolue est ainsi un cas particulier de factorisation

rationnelle. Si l’on prend un point de vue plus “algorithmique”, on est amené à se poser la question : qu’estce que sedonnerun corps ? La factorisation rationnelle pourrait être alors considérée comme la factorisation sur un corps que l’on peut représenter à partird’unnombreﬁnideconstantesetdesymbolesopératoires;parexemplelQ(et son arithmétique), que l’on peut déﬁnir à partir de l’ensemble{0,1,+,−,×, /,=}, où =représenteletestd’égalité.UneextensionﬁniedelQrentreaussiclairementdansce cadre, si l’on sait se donner les éléments qui l’engendrent. On serait tenté de penser qu’une clôturealgébriquedelQnepeutpasêtrereprésentéedemanièreﬁnie.Maispuisquel’on dispose d’un algorithme de factorisation sur les extensions algébriques ﬁnies de lQ , on peutreprésenterlQparunensembledutype{0,1,+,−,×, /,=, RootOf}, oùRootOf est une instruction permettant de représenter un élément algébrique comme racine d’un polynômeirréductibleà coeﬃcients dans une extension de Notons que les corpslQ . K sur lesquels on sait factoriser sontcalculables: c’estàdire que l’on peut tester l’égalité de deux éléments deKet eﬀectuer les opérations arithmétiques dansKle(i.e. donner résultat d’une opération entre deux éléments deKsous forme d’un représentant deK). La réciproque est fausse : on ne dispose pas d’algorithme de factorisation sur tous les corps calculables.LareprésentationquenousendonnonscidessusfaitdelQuncorpscalculable; cependant, les travaux de Claire Dicrescenzo et Dominique Duval [DD] prouvent que la factorisation n’est pas nécessaire pour cela (voir le début de la section 1 de [Duv2] pour un développement de ces concepts).

La méthode de factorisation absolue dûe à Barry Trager [Tra2] et Carlo Traverso [Trav] se ramène à une factorisation rationnelle sur une extension ﬁnie après détermination de celleci. Elle cumule ainsi deux problèmes : trouver une extension convenable, ce qui débouche en général sur une extension trop grande, et factoriser sur cette extension par des méthodes classiques de factorisation, processus qui deviennent très vite ineﬃcaces quandledegrédel’extensioncroıˆt.LaméthodedeDominiqueDuval[Duv2]quenous étudions dans la première partie de cette thèse est radicalement diﬀérente, et en particulier ne nécessite aucun procédé de factorisation. La contrepartie est qu’elle passe par le calcul de structures complexes. Ainsi, si le cas de la factorisation absolue entre dans le cadre de la déﬁnition de la factorisation rationnelle, son mécanisme semble bien atypique, ce qui est sans doute une des raisons pour laquelle la factorisation absolue reste aujourd’hui considérée comme une factorisation particulière. En réalité, la raison fondamentale n’est pas là, car ces problèmes de représentation et de rationalité sont des préoccupations récentes, directement liés au développement du calcul symbolique. Ils ne traduisent pas le caractère de “quasiuniversalité” de la factorisation absolue, mis en évidence par les géomètres algébristes du début du siècle, et que nous tenterons d’exprimer comme suit : Soitfun polynôme,x1, . . . , xrses indéterminées, etSl’ensemble de ses coeﬃcients; la factorisation absolue defestla même quel que soit le corpsdontSest vu comme sousensemble et sur lequelx1, . . . , xrsont transcendants,à quelques exceptions près. 2 2 Considérons le polynômeG=y+ 3x+ 5 . On a alorsX={x , y}etS={1,3,5}. L’ensembleSpêtuevertucommepartiedelQd,le(Qtde IF) , p, pour toutppremier,

évidemment de toute extension algébrique de ces corps, etc. . .. Le polynômeGest absolument irréductible quels que soit ce corps, sauf en caractéristique 2 pour laquelle c’est un carré, 3 pour laquelle il se décompose sur IF3, et 5 pour laquelle il se décompose sur IF5. 2 2 2 Reprenons l’exempleF=y−2Xx , ={x , y}etS={1,−2}factorisation. La absolue deFest (y−α x) (y+α x) quel que soit le corps de baseK, oùαest une 2 racine deT−2 dansK, sauf pourKde caractéristique 2 – remarquons d’ailleurs qu’en caractéristique 2, F=y∙y, et que cette factorisation est dans un sens la même que les autres – . Ce fait peut être déduit d’un théorème fondamental d’Emmy Noether (voir section 4.2). Ce théorème exprime le fait qu’un polynôme ennvariables, de degré au plusd, et à coeﬃcients dans un corpsK, est réductible surKsi et seulement si ses coeﬃcients sont solutions d’un système d’équations à coeﬃcients entiers rationnels, ces équations ne dépendant pas du corpsK(les coeﬃcients du système devant être interprétés dans la caractéristique deKreviendrons sur ce théorème et ses conséquences lors de). Nous l’étude de notre test d’irréductibilité absolue qui constitue la deuxième partie de cette thèse. Dans la pratique, on est bien loin de disposer d’un algorithme qui donnerait la factorisation absolue d’un polynôme au sens où nous venons de la déﬁnir, c’estàdire une décomposition symboliqueen produit de facteurs absolument irréductibles, et la liste ﬁnie des corps sur lesquels cette décomposition n’est pas valable (en fait une liste d’entiers représentant la caractéristique de ces corps). Si la factorisation, dite “rationnelle”, sur les corps non algébriquement clos a été beaucoup étudiée et a donné lieu à diverses implantations (tout “bon” système de calcul formel possèdesonfactoriseurdepolynômessurlesextensionsﬁniesdelQousurlescorpsﬁnis), on est très loin de pouvoir en dire autant de la factorisation absolue. Seul Maple oﬀre à ce jour une procédure de factorisation absolue, basée sur le principe de Barry Trager et Carlo Traverso, et implantée par Marc Rybowicz. La factorisation absolue a connu un regain d’intérêt de la part des chercheurs dans les années 80, justement suite au développement du calcul formel et à l’implantation d’algorithmes de factorisation sur les corps usuels. Une caractéristique majeure de la fac torisation des polynômes multivariés est que l’on peut se ramener du cas général au cas de deux indéterminées qui concentre l’essentiel des diﬃcultés. Divers algorithmes permettent de se ramener à cette situation, ce que font la plupart des auteurs dont nous citons les travaux ciaprès. Heintz et Sieveking [HS] ont proposé en 1981 un test d’irréductibilité absolue. Chistov [Chi] et Grigoryev [Gri] semblent être à l’origine du premier algorithme de factorisation 2 n surlCpolynomialenddonné un polynôme(1984). Etant F(x, y) à coeﬃcients dansK, Kaltofen [Kal1] donne en 1985 un algorithme consistant à rechercher le polynôme minimal d’une racine deF, vu comme polynôme eny, dansK[x, y] . Ce polynôme est un facteur absolument irréductible deFavons mentionné cidessus la méthode de Trager et. Nous

Traverso, qui consiste à factoriserFpar un algorithme classique, sur une extension “bien choisie”. La méthode de Duval, [Duv1] en 1987 puis [Duv2] en 1991, est basée sur une approche géométrique, et consiste à calculer un certain invariant de la courbe associée au polynôme, l’espace des fonctions constantes, puis en tirer les composantes irréductibles de la courbe. Bajaj, Canny, Garrity et Warren [BCGW] proposent en 1989 une méthode basée sur la topologie de l’ensemble des zéros du polynôme. Enﬁn tout récemment (1997), Galligo et Watt [GW] ont présenté une méthode numérique. Enfait,laplupartdestravauxsurlaquestionsontconsacrésàlafactorisationsurlC, etmêmeplutôtsurlQ(certainsdesalgorithmesprécitéspeuventnéanmoinssetrans poser sans diﬃculté majeure sur les corps ﬁnis). Mais, nous l’avons dit, même dans ce cas on ne dispose pas d’un algorithme de factorisation eﬃcace, pas plus que d’un test d’irréductibilité. Ceci explique pourquoi nous nous sommes nous aussi consacrés au cas delQ,l’undesobjectifsdecettethèseétantl’obtentiondetelsalgorithmes. La première partie de nos travaux est essentiellement consacrée à l’étude, l’amélioration et l’implantation en Maple de la méthode de Dominique Duval (chapitre 2). Cette im plantation passe par l’optimisation de certaines parties de l’algorithme et en particulier, nous montrons que la factorisation absolue se déduit de l’espace des constantes par des procédures totalement rationnelles sur le corps de base (ne se déroulant pas dans des ex tensions), et performantes. Les résultats de notre implantation se comparent de manière relativement avantageuse à ceux de l’algorithme de Barry Trager et Carlo Traverso et sont présentés au chapitre 3. Avant cela, nous exposons au chapitre 1 le principe de la méthode de Trager et Traverso, et en tirons un algorithme spécialement adapté au calcul des facteurs linéaires d’un polynôme. La deuxième partie de cette thèse présente un test d’irréductibilité absolue des polynômes à coeﬃcients dans lQ . Etant donné un polynômeFlQ , le test consistà coeﬃcients dans arechercherdesconditionssuﬃsantessursèesréductionsmodulodesnombrespremiers. Ces conditions ont été remarquées par Kaltofen [Kal1], et Traverso et Dvornicich [TrDv]. Nous donnons au chapitre 4 des minorants pour les nombres premiers, à partir desquels ces conditions d’irréductibilité absolue sont aussi nécessaires. Au chapitre 5, nous montrons que la probabilité que ce critère ne soit pas vériﬁé moduloppour plusieurs nombres premierspCe calcul de probabilité passe entre autresdiminue très vite avec leur nombre. par le dénombrement des polynômes de degré majoré ayant des solutions de multiplicité donnée dans IFpavons eﬀectué une implantation de ce test, qui s’avère très eﬃcace.. Nous Chacune des deux parties comporte introduction et conclusion et peut se lire indépendam ment de l’autre. Les seuls prérequis demandés au lecteur sont des bases d’algèbre com mutative.

Table

des

Introduction

matières

Factorisation Absolue

1 Première méthode (Trager/Traverso) 1.1 Algorithme de Trager et Traverso. . . . . . . . . . . . . . . . . . . . . . . 1.2 Déﬁnitions et propriétés. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Une méthode de calcul des facteurs linéaires. . . . . . . . . . . . . . . . . 1.3.1 Fondements théoriques. . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Description de la méthode – Algorithme. . . . . . . . . . . . . . . 1.3.3 Généralisation aux polynômes réductibles. . . . . . . . . . . . . . .

2 Deuxième méthode (Duval) 2.1 Introduction. . . . . . . . . . . . . . . . . . . . . 2.2 Corps de fonctions algébriques. . . . . . . . . . . 2.2.1 Anneaux de valuation – Places. . . . . . . 2.2.2 Notions de valuation et ramiﬁcation. . . . 2.2.3 Notion de diviseur. . . . . . . . . . . . . 2.2.4 Eléments entiers – Constantes. . . . . . . 2.3 Factorisation absolue. . . . . . . . . . . . . . . . 2.3.1 Théorème fondamental. . . . . . . . . . . 2.3.2 Théorème eﬀectif. . . . . . . . . . . . . . 2.3.3 Schéma de l’algorithme. . . . . . . . . . . 2.4 Calcul d’une base du corps des constantes. . . . 2.4.1 Calcul d’une base de l’anneau des entiers.

. . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

13 14 16 19 19 21 23

25 25 26 26 28 28 29 31 31 32 33 33 33

2.5 2.6

2.4.1.1 Algorithme de Trager. . . . . . . . . . . . . . . . . . . . 2.4.1.2 Algorithme de van Hoeij. . . . . . . . . . . . . . . . . . . 2.4.1.3 Passage du local au global. . . . . . . . . . . . . . . . . . 2.4.2 Base de l’anneau des entiers normale à l’inﬁni. . . . . . . . . . . . 2.4.2.1 Bases normales. . . . . . . . . . . . . . . . . . . . . . . . 2.4.2.2 Normalisation à l’inﬁni d’une base de l’anneau des entiers 2.4.3 Algorithmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Calcul d’un facteur absolument irréductible. . . . . . . . . . . . . . . . . . Algorithme de factorisation absolue. . . . . . . . . . . . . . . . . . . . . .

Résultats des implantations et conclusion 3.1 Exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Irréductibilité Absolue – Test Probabiliste

Des conditions rationnelles d’irréductibilité absolue 4.1 Déﬁnitions et propriétés fondamentales. . . . . . . . . . . . . . . . . . . . 4.2 Irréductibilité absolue modulop . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Factorisation absolue et multiplicité des solutions. . . . . . . . . . . . . . 4.4 Existence de solutions rationnelles simples modulop . . . . . . . . . . . . . 4.4.1 Résultats généraux. . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.2 Résultats sur les courbes. . . . . . . . . . . . . . . . . . . . . . . . 4.5 Majorant de l’ensemble des mauvaises réductions. . . . . . . . . . . . . .

Test probabiliste 5.1 Analyse du problème – choix d’un espace probabilisé Ω. . . . . . . . . . . 5.2 Etude préliminaire des probabilités. . . . . . . . . . . . . . . . . . . . . . 5.3 Encadrement du nombre de polynômes irréductibles de IFq[X]d. . . . . . . 5.4 Dénombrement des polynômes de IFq[X]dayant des solutions rationnelles simples dans IFq. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Ensembles algébriques – Idéaux. . . . . . . . . . . . . . . . . . . .

34 35 37 40 40 41 49 53 56

57 57 62

69 69 73 75 76 76 78 81

83 83 86 91

97 97 98

Voir