Calcul de développements de Puiseux et application au

Calcul de développements de Puiseux etapplication au calcul du groupe de monodromie

d'une courbe algébrique plane

Poteaux Adrien

XLIM-DMI, UMR-CNRS 6172Université de Limoges

Soutenance de thèse15 octobre 2008

Adrien Poteaux Puiseux & monodromie

Stratégie employée

Situation

Entrée : exacte.

Sortie : approchée.

Approche

1 Trouver la structure du problème modulo p.

2 Utiliser la structure pour faire des calculs numériques.



Plan

1 Calcul des développements de Puiseux : un nouvel algorithmesymbolique-numérique

1 Calculs modulo un bon premier p → informations exactes.

2 Calcul numérique des séries de Puiseux à l'aide de cesinformations.

2 Calcul du groupe de monodromie

1 Chemins optimisés

2 Développements en des points critiques

3 Stratégie nombre de pas / ordre de troncation

3 Exemples, conclusion et perspectives


Notations

K = Q(α) un corps de nombres

F (X ,Y ) ∈ K [X ,Y ]

C = {(x , y) ∈ C2 |F (x , y) = 0}

Soit x0 ∈ C :

Fibre en x0 :F(x0) = {racines de F (x0,Y ) = 0}.

Point régulier : #F(x0) = dY .

Point critique : #F(x0) < dY .


Calcul de développements de Puiseux


Développements de Puiseux

Théorème (Puiseux)

Il existe e1, . . . , es des entiers positifs véri�ant∑s

i=1 ei = dY tel

que F (vu comme un polynôme univarié en y) possède dY racines

distinctes dans K ((X )), qui s'écrivent de la manière suivante :

Yij(X ) =∞∑

k=ni

αik ζ jkei Xkei

où 1 ≤ i ≤ s, 0 ≤ j ≤ ei − 1, ni ∈ Z et αini 6= 0. De plus,

l'ensemble des coe�cients {αik} est inclus dans une extension �nie

de K.


Partie singulière

Yij(X ) =∞∑

k=ni

αik ζ jkei Xkei

=

rij∑k=ni

αik ζ jkei Xkei + termes suivants

rij est l'indice de régularité ; ri = rij pour 1 ≤ j ≤ ei

Termes suivants : calculés par exemple via Newton quadratiqueKung & Traub 1978, All Algebraic Functions Can Be Computed Fast


Polygones de Newton génériques

F (X ,Y ) =∑i ,j

aijXjY i

× Supp(F)= {(i , j) ∈ N2 | aij 6= 0}

� N (F ) : partie inférieure del'enveloppe convexe de Supp(F).

- - GN (F ) : pentes de N (F ) ≥ −1.

Polynôme caractéristique :

φ∆(T ) =∑

(i ,j)∈∆

aijTi−i0q


Algorithme de Newton-Puiseux rationnel

D. Duval 89, Rational Puiseux Expansions

Pour chaque arête ∆ de GN (F )

• φ∆ =s∏

k=1

φMk

k

• Pour chaque φk

F (X ,Y )←F (ξukX

q,Xm(ξvk + Y ))

X l

avec · ξk t.q. φk(ξk) = 0,

avec · (u, v) tel que uq − vm = 1.


Arbre des polygones


Algorithme symbolique

Calcul dans des extensions de degré potentiellement élevé.

Croissance des coe�cients.

Exemple : F = (Y 3 − X ) ((Y − 1)2 − X ) (Y − 2− X 2) + X 2 Y 5

a pour discriminant X 3 P(X ) avec degX (P) = 23.

Les coe�cients des développement de Puiseux au-dessus desracines de P à l'ordre 1 ont une taille de 136 chi�res !

Complexité binaire O (̃dY32dX

4) Walsh 2000


Une approche modulaire-numérique

1 Calculer la partie singulière des séries de Puiseux modulo unbon premier p.

Cela nous donne l'arbre des polygones T (F ), i.e. :Les polygones de Newton génériques,Les structures de multiplicité des φ∆.

2 Calculer numériquement les séries de Puiseux en suivant T (F ).


Contributions

Notion de polygone de Newton générique.

Critère de bonne réduction (choix d'un bon p).

Bornes sur le premier p.

Complexité améliorée de la partie modulaire de notrealgorithme.

Calculs numériques suivant T (F ).

Prototype d'implémentation en Maple


Calcul de développements de Puiseux :partie symbolique

Poteaux & Rybowicz, On the good reduction of Puiseux series and

complexity of the Newton-Puiseux algorithm over �nite �elds, ISSAC'08


Bonne p-réduction

On note :

o l'anneau des entiers algébriques de K ,

p un nombre premier,

p un idéal premier de o divisant p.

Dé�nition

F a une bonne p-réduction locale (en x = 0) si :

F ∈ op[X ,Y ],

p > dY ,

tc(RF ) 6≡ 0 mod p.

où RF = ResultantY (F ,FY )


Réduction des séries de Puiseux

L une extension �nie de K engendrée par les coe�cients desséries de Puiseux,

O l'anneau des entiers algébriques de L,

P un idéal premier de OP divisant p,

OP = {α ∈ L | vP(α) ≥ 0}.

Théorème

Si F a une bonne p-réduction locale, alors les coe�cients des séries

de Puiseux de F au-dessus de 0 sont dans OP.

Preuve : Utilise un théorème de Dwork & Robba 79On Natural Radii of p-adic Convergence


Réduction de T (F )

Théorème

Si F a une bonne p-réduction locale, alors T (F ) = T (F ).

Faux avec les polygones classiques :

Exemple

F (X ,Y ) = (Y − pX )(Y 2 − X ) + X 3 ⇒ tc(RF ) = 4


Choix du nombre premier p

K = Q(γ), w = [K : Q], Mγ le polynôme minimal de γ

ht(Q) = log ‖Q‖∞ où Q est un polynôme multivarié.

ht(p) appartient à

Stratégie déterministe

O(wdY (wht(Mγ) + ht(F ) + log(wdXdY )))

Stratégie de type Monte-Carlo, probabilité d'erreur ≤ ε

O(log(dYw log dX ) + log(ht(F )) + log(ht(Mγ)) + log(ε−1))

Stratégie de type Las-Vegas, 2 itérations en moyenne

O(log(dYw log dX ) + log(ht(F )) + log(ht(Mγ)))


Complexité de l'algorithme rationnel au-dessus de L = Fpt0

Substitutions → O˜(δ2FdY )

Factorisations → O˜(δF [d2Y + dY t0 log p])

Total → O˜(δFdY [δF + dY + t0 log p])

Lemme

δF ≤ vX (∆F ) ≤ dX (2dY − 2)

Théorème (Nombre d'opérations dans L)

→ T (F ) au-dessus de 0 : O˜(d3Y d2X + d2Y dX t0 log p)

→ T (F ) au-dessus de l'ensemble des points critiques :

O˜(d3Y d2X t0 log p)

D. Duval 89 Rational Puiseux Expansions : O(d6Y d2X )


Complexité binaire du calcul de T (F )

F ∈ K [X ,Y ]

K = Q(γ)

w = [K : Q]

Mγ le polynôme minimal de γ

Théorème

Il existe un algorithme de type Monte-Carlo qui calcule T (F ) en

O˜(d3Y d2Xw

2 log2 ε−1[ht(Mγ) + ht(F )])

opérations binaires avec une probabilité d'erreur ≤ ε.


Calcul de développements de Puiseux :partie numérique


Suivre T (F ) numériquement : un exemple

Développements de Puiseux de F :

S1(X ) = X + · · ·S2(X ) = 4X

12 + X

78 + · · ·

S3(X ) = 2X12 + 2X + · · ·

S4(X ) = 2X12 + X + X

76 + · · ·

S5(X ) = X12 + 2X + X

54 + · · ·

S6(X ) = X12 + X + · · ·

S7(X ) = X12 + 4X + · · ·

dY = 25, dX = 26 ; 1 ≤ coe�cients ≤ 1013 ; Digits = 20.


Premier polygone de Newton


Premier polygone de Newton


Tri selon les polygones

Gi (X ,Y )←F (X 2,X (Y + ξ

1/2i ))

X, ξ1 = 1. ξ2 = 4. ξ3 = 16.

polynôme coe�cient en X 3

G1 0.G2 0.G3 −17199267840000.0


Tri selon les polygones


Tri selon les multiplicités

Structures de multiplicité :

(2, 1, 1)⇒ deg(pgcd(φ, φ′)) = 1

(3, 1)⇒ deg(pgcd(φ, φ′)) = 2

Polynômes caractéristiques :φ1 = 1049760000.0− 2361960000.0T + 1837080000.0T2 − 590490000.0T3 + 65610000.0T4

φ2 = 1719926784.0− 6019743744.0T + 7739670528.0T2 − 4299816960.0T3 + 859963392.0T4

1 Si ← Syl(φi , φ′i )

2 Calcul des valeurs singulières des Si


Tri selon les multiplicités

Valeurs singulières associées à φ1 :[710694508.4327095884, 5827385163.0346368216, 3038236185.2953794346, 1140210769.8445335036,

40759543.641844042087, 1882790.0681572535369, 3.8263754075532025314 ·10−11 ]

Valeurs singulières associées à φ2 :[ 37445022322.189717034, 24644791488.066781055, 12101920587.793187214,

3915075466.8959244453, 31534726.725839766232, 0.00000000074101187358617089031 ,

0.00000000027761147770454585021 ]


Calcul du groupe de monodromie

Poteaux, Computing monodromy groups de�ned by plane algebraic curves,SNC'07


Groupe de monodromie

On note c1, . . . , cn les points critiques.

On �xe un point de base régulier a.

On cherche les n permutationsσ1, . . . , σn correspondant à c1, . . . , cn.

Ces permutations engendrent le groupe de monodromie.


Méthodes �Relier les �bres�

1 Choix des chemins.

2 Choix des points de connexion.

a





3 Calcul des �bres

aAdrien Poteaux Puiseux & monodromie




3 Calcul des �bres

4 Méthode de connexion.

a


Monodromie : état de l'art (sketch)

1 Relier les �bres3 van Hoeij & Deconinck 99

Fonction monodromy de Maple.Fibres reliées à l'aide des dérivées premières.Critère de connexion et contrôle de l'erreur heuristiques.

3 van Hoeij & Rybowicz (com. perso.)Théorème de Smith + arithmétique numérique/intervalles.Algorithme certi�é mais trop lent

2 Equation di�érentielle


Monodromie : état de l'art (sketch)

1 Relier les �bres2 Equation di�érentielle

Intérêt : calcul rapide des développements à ordre élevé.Chudnovsky & Chudnovsky 86, 90 ; van der Hoeven 00 ;

Cormier-Singer-Trager-Ulmer 02 ; Bostan & all 07 ...

Calcul de l'équation di�érentielle potentiellement coûteux.

Taille de l'équation di�érentielle importante.

On utilise des développements à ordre petit.


Contributions

1 Choix des chemins : arbre de recouvrement minimal.

2 Méthode de connexion : développements en série tronqués etdéveloppements de Puiseux au-dessus des points critiques.

Bornes sur les ordres de troncation.

Donne la monodromie locale.

Utile pour l'application d'Abel (Deconinck and Patterson 07).

3 Choix des points intermédiaires :Compromis entre les ordres de troncation et le nombre depoints.Borne sur le nombre de points intermédiaires.


Arbre de recouvrement minimum


Connexions le long de l'arbre


Nombre de points intermédiaires

⇒ À ce stade, on a besoin de O(n) = O(d2) points intermédiaires.


Ordres de troncation

Cauchy → ordres de troncation

F (X ,Y ) = Y 3 − X 5 + 2(10X − 1)2 → n ≥ 102309

Ajouts de points intermédiaires


Bornes sur le nombre d'étapes

Théorème

Nombre total de points : O(n log LMLm

+ g + dY ) et donc

O(d2 log LMLm

).

Corollaire

Si F ∈ Z[X ,Y ], on a O(d6 + d5 log ||F ||∞) points intermédiaires.

⇒ borne cubique en la sortie.


Exemples


Exemple 1

Ma,d = xd − 2(ax − 1)2, F1(x , y) = y3 −M10,5(x)

coe�cient en x16/3 :

Digits évaluation numérique algorithme numérique-modulaire10 0 740 0 3650 6 47

Algorithme de monodromie :

version symbolique/numérique : 0.950 secondes. Précision de40 chi�res nécessaires pour avoir un résultat correct.

version numérique/modulaire : 0.839 secondes. Digits 10.


Exemple 2

F2(x , y) = (y3 −M10,6(x))(y3 −M10,3(x)) + y2x5

coe�cient en x1/2

Digits évaluation numérique algorithme numérique-modulaire10 0 420 0 1530 5 29


Exemple 3

Gn(x , y) =(yd

n2e − Pd n2e(x)

)Gb n2c(x , y)

où

Pn0(x) =1

n03!x

(xn0 + (n0 − 1) x − 1

n0!

).

Polynôme algorithme symbolique algorithme numérique-modulaireconsidéré temps en seconde temps en secondes précision

G8 0.031 0.029 9G12 0.041 0.099 9G16 2.3 0.221 9G20 0.751 0.550 9G24 2.889 0.920 9G28 8.509 1.719 9G32 30.820 5.040 9


Résumé des contributions et perspectives


Résumé (Puiseux)

Critère de réduction :Permet de calculer T (F )Algorithmes probabilistes → petit p

Utilisation de T (F ) pour le calcul numérique :Filtre à deux étagesUtilisation de la SVD

Bornes de complexité améliorées

Complexité binaire pour le calcul de T (F )


Résumé (monodromie)

Chemins optimisés.

Stratégie nombre de pas / ordre de troncation : borne sur lenombres d'étapes.

Développements en des points critiques : utilisation del'algorithme numérique-modulaire.


Perspectives

Développements de Puiseux :

Extensions : complexité (calcul du genre)

Contrôle des erreurs numériques (implémentation certi�ée)

Groupe de monodromie :

Contrôle numérique des erreurs (implémentation certi�ée)

Complexité

Autres utilisations de la stratégie modulaire-numérique.


Documents

Calcul de développements de Puiseux et application au