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

Jean - Franc¸Ois Ragot

Description

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

Sujets

• Dusart
• Villard
• Zimmermann
• Western concert flute

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 mars 1992
• Nombre de lectures: 74
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

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 profiter 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 influé sur la clarté de ce mémoire. Merci à Martine Guerletin, Véronique Merigoux et Nadine Tchefranoff 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 Hafid et Gérard Juin. Je tiens enfin à remercier affectueusement 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 à coefficients 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éfinie, 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éfinit unehypersurfacede l’espace affineK, 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 . à coefficients 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’équationsF 1 =y−2xetF 2 =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 coefficientslQ . , ici Ainsi Maple, à l’instar des systèmes de calcul formel les plus sophistiqués, sait faire de lafactorisation rationnelle, que nous définirons commefactorisation sur un corps donné(contenant les coefficients du polynôme à factoriser). Ce corps peutêtre explicitement ou implicitement spécifié. Pour notre exemple, le corps sousentendu est lQ . Il est défini à la fois explicitement par les coefficients 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éfinitαcomme étant une racine deT−2 dans Cl , puis f actor(F ,{α}demande la factorisation de) qui Fsur le plus petit corps contenant ses coefficients etα, et qui renvoie (y−α x) (y+α xOn sait factoriser entre autres sur) . lQ , sur les corps finis et sur les extensions algébriques de degré fini des précédents. D’après cette définition, la factorisation rationnelle d’un polynôme peut être définie sur un corps quelconque. La factorisation absolue est ainsi un cas particulier de factorisation

1

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’unnombrefinideconstantesetdesymbolesopératoires;parexemplelQ(et son arithmétique), que l’on peut définir à partir de l’ensemble{0,1,+,−,×, /,=}, où =représenteletestd’égalité.UneextensionfiniedelQrentreaussiclairementdansce 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èrefinie.Maispuisquel’on dispose d’un algorithme de factorisation sur les extensions algébriques finies 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à coefficients 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 effectuer 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 finie 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 inefficaces quandledegrédel’extensioncroıˆt.LaméthodedeDominiqueDuval[Duv2]quenous étudions dans la première partie de cette thèse est radicalement diffé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éfinition 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,x 1 , . . . , x r ses indéterminées, etSl’ensemble de ses coefficients; la factorisation absolue defestla même quel que soit le corpsdontSest vu comme sousensemble et sur lequelx 1 , . . . , x r sont 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,

2

é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 IF 3 , et 5 pour laquelle il se décompose sur IF 5 . 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 à coefficients dans un corpsK, est réductible surKsi et seulement si ses coefficients sont solutions d’un système d’équations à coefficients entiers rationnels, ces équations ne dépendant pas du corpsK(les coefficients 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éfinir, c’estàdire une décomposition symboliqueen produit de facteurs absolument irréductibles, et la liste finie 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ômessurlesextensionsfiniesdelQousurlescorpsfinis), on est très loin de pouvoir en dire autant de la factorisation absolue. Seul Maple offre à 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 difficulté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) à coefficients 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

3

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. Enfin 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 difficulté majeure sur les corps finis). Mais, nous l’avons dit, même dans ce cas on ne dispose pas d’un algorithme de factorisation efficace, 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 à coefficients dans lQ . Etant donné un polynômeFlQ , le test consistà coefficients dans arechercherdesconditionssuffisantessurs è 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érifié 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 IF p avons effectué une implantation de ce test, qui s’avère très efficace.. 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.

4

Table

I

des

Introduction

matières

Factorisation Absolue

1 Première méthode (Trager/Traverso) 1.1 Algorithme de Trager et Traverso. . . . . . . . . . . . . . . . . . . . . . . 1.2 Définitions 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 ramification. . . . 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 effectif. . . . . . . . . . . . . . 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.

5

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

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

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

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

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

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

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

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

1

9

13 14 16 19 19 21 23

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

3

II

4

5

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’infini. . . . . . . . . . . . 2.4.2.1 Bases normales. . . . . . . . . . . . . . . . . . . . . . . . 2.4.2.2 Normalisation à l’infini 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éfinitions 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 IF q [X] d . . . . . . . 5.4 Dénombrement des polynômes de IF q [X] d ayant des solutions rationnelles simples dans IF q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Ensembles algébriques – Idéaux. . . . . . . . . . . . . . . . . . . .

6

34 35 37 40 40 41 49 53 56

57 57 62

65

69 69 73 75 76 76 78 81

83 83 86 91

97 97 98