These - Resolution effective d’equations diophantiennes

Informations

• Publié par: Thuwyer
• Nombre de lectures: 40
• Langue: Français

Extrait

oN d’ordre : 1693.
THESE
presentee a
L’UNIVERSITE BORDEAUX I
ECOLE DOCTORALE DE MATHEMATIQUES ET INFORMATIQUE
Par Guillaume HANROT
POUR OBTENIR LE GRADE DE
DOCTEUR
SPECIALITE : MATHEMATIQUES PURES
Resolution e ective d’equations diophantiennes :
algorithmes et applications.
Soutenue le 28 avril 1997.
Apres avis de :
M. WALDSCHMIDT, Professeur Universite Pierre et Marie Curie – Paris 6
B.M.M. DE WEGER, Professeur Rijksuniversiteit Leiden et
Erasmus Universiteit Rotterdam
Devant la commission d’examen formee de :
P. FLAJOLET, Directeur de Recherche INRIA Rocquencourt President
L. HABSIEGER, Charge de Recherche A2X (UMR CNRS 9936) Rapporteur
J-M. DESHOUILLERS, Professeur Universite Victor Segalen Bordeaux 2 Examinateurs
H. IWANIEC, Professeur Rutgers University et ETH Zur ich
J. MARTINET, Professeur Universite Bordeaux I
M. WALDSCHMIDT, Professeur Universite Pierre et Marie Curie – Paris 6
B.M.M. DE WEGER, Professeur Rijksuniversiteit Leiden et
Erasmus Universiteit Rotterdam
– 1997 –Remerciements 3
Remerciements
Mes remerciements vont en premier lieu a Jean-Marc Deshouillers, mon di-
recteur de these. Il a su faire preuve d’une grande ouverture d’esprit dans les
recherches vers lesquelles il m’a oriente, et me suggerer des themes en accord
avec mes interˆets. J’ai largement mis a pro t sa disponibilite et sa vaste culture
mathematique; pendant ces annees j’ai enormemement appris a son contact et a
son instigation.
Yuri Bilu a ete le compagnon de travail quotidien durant une grande partie
de cette these; compagnon souvent electronique mais non moins indefectible,
toujours patient et disponible. Merci a lui pour ces annees de collaboration; je
ne peux que souhaiter la perennite de notre association.
Michel Waldschmidt et Benne de Weger ont bien voulu se charger du lourd
travail de rapporteur, qu’ils ont accompli scrupuleusement. Je les remercie l’un
et l’autre pour leurs remarques constructives, ainsi que pour l’interˆet qu’ils ont
manifeste pour ce travail. Merci aussi d’avoir bien voulu faire partie du jury.
Je suis reconnaissant a Laurent Habsieger et a Jacques Martinet d’avoir ac-
cepte de participer a ce jury, et pour l’interˆet que l’un et l’autre ont toujours
montre pour ces algorithmes. Je pro te de l’occasion pour remercier Jacques
Martinet de contribuer, en assumant la direction de l’a2x, charge riche en travail
mais souvent pauvre en reconnaissance, a en faire un lieu eminemment sympa-
thique et propice a faire des mathematiques et de l’algorithmique.
Merci a Henryk Iwaniec d’avoir bien voulu se deplacer pour participer a ce
jury. Je lui suis egalement redevable d’un fort agreable sejour a Rutgers l’annee
derniere, qui m’a beaucoup apporte dans la perspective de nouvelles directions
de recherche.
Je remercie Philippe Flajolet d’avoir accepte de participer au jury, malgre un
emploi du temps charge; c’est pour moi l’indication que ces travaux, qui sont de
l’algorithmique a objectif mathematique peuvent avoir de l’interˆet aussi pour les
informaticiens.
Merci a Henri Cohen et Michel Olivier qui ont repondu avec patience a mes
(nombreuses) questions sur pari et sur le calcul des systemes d’unites. Merci4 Remerciements
aussi a eux et a leurs acolytes pour avoir mis a disposition de tous le systeme
pari, sans lequel la majorite des calculs presentes dans cette these n’existeraient
qu’ a l’etat de vaine speculation.
Merci plus generalement a tout l’a2x, ou il regne une excellente ambiance
de travail qui est le fait de tous. Je tiens a remercier en particulier Francine
Delmer,Fran coisHennecartetBernardLandreaudontj’aipuapprecierl’humour,
la gentillesse et l’hospitalite.
J’ai e ectue la plus grande partie de ce travail a l’Universite Bordeaux 2;
la bonne humeur et la cordialite que j’y ai rencontrees ont rendu ce travail fort
agreable.
Et en n, last but not least, je tiens a remercier les amis qui m’ont soutenu
pendant cette these et grˆace auxquels la vie de tous les jours est apparue moins
quotidienne. Je pense en particulier a K.B, Laurent, Nicolas, Gilles, David, Ri-
chard, Putu et les autres.5
J’ai ainsi eu, au cours de ma vie, des tas de contacts avec des tas de gens
serieux. J’ai beaucoup vecu chez les grandes personnes. Je les ai vues de tres pres.
Ca n’a pas beaucoup ameliore mon opinion.
Quandj’enrencontraisunequimeparaissaitunpeulucide,jefaisaisl’experience
osur elle de mon dessin n 1 que j’ai toujours conserve. Je voulais savoir si elle
etait vraiment comprehensive. Mais toujours elle me repondait « c’est un cha-
peau». Alors je ne lui parlais ni de serpents boas, ni de forˆets vierges, ni d’etoiles.
Je me mettais a sa portee. Je lui parlais de bridge, de golf, de politique et de cra-
vates. Et la grande personne etait bien contente de connaˆ tre un homme aussi
raisonnable.
Antoine de Saint-Exupery, Le Petit Prince.
A mes parents et grand-parents.6 Table des matieresTable des matieres
Table des matieres 6
Introduction 11
1 L’equation de Thue 21
1.1 Preambule et prerequis algorithmiques . . . . . . . . . . . . . . . 21
1.1.1 Problemes d’algorithmique . . . . . . . . . . . . . . . . . . 21
1.1.1.1 Les unites . . . . . . . . . . . . . . . . . . . . . . 22
1.1.1.2 L’equation aux normes . . . . . . . . . . . . . . . 24
1.2 Formes lineaires en logarithmes . . . . . . . . . . . . . . . . . . . 25
1.2.1 Preliminaires . . . . . . . . . . . . . . . . . . . . . . . . . 25
(i)1.2.2 L’approximation de y x . . . . . . . . . . . . . . . . 26
1.2.3 Unites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.3 La borne de Baker . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.3.1 Bornes inferieures pour les formes lineaires en logarithmes 30
1.3.2 B et log|x| . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.3.2.1 b . . . . . . . . . . . . . . . . . . . . . . . . . . 320
1.3.2.2 |b| et log|x|, 1ir . . . . . . . . . . . . . . . 33i
1.3.2.3 |b | et log|x| . . . . . . . . . . . . . . . . . . . 35r+1
001.3.3 Une borne superieure pour B . . . . . . . . . . . . . . . . 35
1.4 La reduction de la borne . . . . . . . . . . . . . . . . . . . . . . . 37
1.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.4.1.1 L’algorithme LLL . . . . . . . . . . . . . . . . . . 37
1.4.1.2 L’algo de Fincke et Pohst . . . . . . . . . . 39
1.4.2 Mise en uvre de la reduction . . . . . . . . . . . . . . . . 39
1.4.2.1 La methode de Tzanakis et de Weger . . . . . . . 40
1.4.2.2 La methode de Mignotte et de Weger . . . . . . . 43
1.4.2.3 Reduction au cas de la dimension 2 ou 3. . . . . . 44
1.4.2.4 La methode de Bennett et de Weger . . . . . . . 47
1.4.3 Mauvaise reduction . . . . . . . . . . . . . . . . . . . . . . 48
1.4.3.1 Mauvaisereduction,dimension 3,casinhomogene 48
1.4.3.2 Mauvaise reduction, 3 . . . . . . . . 49
1.4.3.3 Mauvaise r dimension 2 . . . . . . . . . 498 Table des matieres
1.5 L’enumeration nale . . . . . . . . . . . . . . . . . . . . . . . . . 51
1.5.1 Enumerer les b . . . . . . . . . . . . . . . . . . . . . . . . 51
1.5.1.1 Enumeration systematique . . . . . . . . . . . . . 51
1.5.1.2 Petits vecteurs de . . . . . . . . . . . . . . . . 52
1.5.1.3 Cribler les b . . . . . . . . . . . . . . . . . . . . . 53
1.5.2 Des b a x . . . . . . . . . . . . . . . . . . . . . . . . . . . 53i
1.5.3 Enumerer x . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.5.3.1 La borne pour|x| est grande . . . . . . . . . . . 54
1.5.3.2 La borne pour|x| est petite . . . . . . . . . . . . 54
1.6 L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.7 Un detail numerique . . . . . . . . . . . . . . . . . . . . . . . . . 56
2 L’equation de Thue : cas d’un corps compose 59
2.1 Preliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.1.2 Prerequis algorithmiques . . . . . . . . . . . . . . . . . . . 60
2.2 Reduction aux formes lineaires en logarithmes . . . . . . . . . . . 60
(i)2.2.1 L’approximation de ϕ . . . . . . . . . . . . . . . . . . . . 60
2.2.2 De x aux b . . . . . . . . . . . . . . . . . . . . . . . . . . 62i
2.2.2.1 Une unite . . . . . . . . . . . . . . . . . . . . . . 62
2.2.2.2 Une borne pour max|b| . . . . . . . . . . . . . . 63i i
2.2.3 Des b a x . . . . . . . . . . . . . . . . . . . . . . . . . . . 65i
2.3 L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3 Exemples et applications 67
3.1 Remarques generales . . . . . . . . . . . . . . . . . . . . . . . . . 67
19 193.2 x +2y =1,2. . . . . . . . . . . . . . . . . . . . . . . . . . 67
4 3 2 2 3 43.3 y +xy 1500x y +23756x y 81536x =1. . . . . . . . . . 68
3.4 Diviseurs primitifs des suites de Lucas et Lehmer . . . . . . . . . 69
3.4.1 Le cas 31p 67 . . . . . . . . . . . . . . . . . . . . . 71
3.4.2 Le cas 67p 1000, p = 5011. . . . . . . . . . . . . . . . 72
3.4.3 p = 83. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4.4 p = 4001. . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4 Equations superelliptiques 77
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3 Une famille de corps de nombres . . . . . . . . . . . . . . . . . .