I.3 Méthode numérique 

I.3.1 Un calcul approché dans un corps de nombres

a. Méthode en trois étapes

La donnée est une famille finie de polynômes engendrant un idéal I de K[X₁,..., X_m], où K est un corps de nombres, habituellement Q. Nous construisons une approximation de la solution, c'est à dire un ou plusieurs points très proches de V(I), et nous en déduisons la structure algébrique de cette variété.

Pour cela, nous commençons par fabriquer une approximation grossière d'un point solution. Nous faisons ensuite converger numériquement cette valeur vers une meilleure approximation, suffisamment précise. Cela nous permettra de retrouver la valeur exacte du point solution, et ensuite d'en déduire (une partie au moins) de la structure de la variété solution.

Chacune de ces étapes doit être adaptée au type de système étudié, si nous voulons que cette méthode puisse être compétitive avec la recherche d'une base de Gröbner. C'est envisageable si le système n'est pas quelconque mais s'il est construit pour représenter un objet plus riche, tel un dessin d'enfant.

b. Valeur des résultats obtenus

Il est toujours possible de vérifier par des calculs exacts (dans K[X₁,..., X_m]) le résultat de nos calculs. Cette méthode permet donc de trouver une solution du système, ou bien une famille de solutions.

Il est parfois possible d'en déduire une description de l'ensemble solution mais, en général, si notre méthode ne trouve pas de solution, cela ne prouve pas que le système n'en a pas. De plus, si la variété se décompose en variétés irréductibles de dimensions différentes, il est très probable que la méthode numérique n'aboutisse qu'à des points des composantes de dimension maximale.

I.3.2 Convergence

a. Algorithme de Newton

À partir d'une valeur = (₁ , ... , _m) proche d'une solution y du système, nous allons construire des approximations de y aussi précises que nécessaire.

La formule de Taylor, valable pour toute norme, nous donne :

||F( + ) - ( F() + DF()[])|| = O(||||²).

Si nous cherchons l'écart = - y, nous savons que |||| est petit puisque par hypothèse est proche de y. Or y est solution du système donc ||F(y)|| = 0. La formule de Taylor devient
||F() + DF()[]|| = O(||||²).

Si DF() est inversible (et donc carrée), nous avons donc un moyen d'obtenir une approximation de , et chaque étape de l'algorithme de Newton remplace par + où

= - DF()^-1[F()].

Il faut inverser DF(), ce qui n'est pas toujours stable numériquement, et il s'agit d'un développement au premier degré, qui ne permet pas toujours de se rapprocher de la solution.

b. Choix de la norme

Lorsqu'on affirme que est proche de y, cela signifie que nous utilisons une certaine norme sur K^m, donc une valeur absolue sur K. Si deux normes sont équivalentes, la résolution du système se fera de la même façon. C'est donc le choix de la valeur absolue qui importe.

Le choix le plus intuitif est la valeur absolue usuelle (dans C), ce que nous conseillons.

c. Dans Q_p

Lorsqu'on connaît un premier p tel que K Q_p , ce qui n'est pas évident puisqu'habituellement on ne connaît pas K, une approximation p-adique d'une solution y avec une précision k est une solution du système modulo p^k. Comme la valeur absolue p-adique est ultramétrique, l'algorithme de Newton (qui s'appelle alors lemme de Hensel) restera dans la boule de rayon ^k autour de y.

Pour pouvoir inverser la matrice DF() il faut que son déterminant soit non nul modulo p^k. Ce qui signifie que l'algorithme (de Newton) ne convergera vers y que si l'approximation initiale est une solution du système modulo p^k où k est supérieur à la valuation p-adique de DF(y).

Sauf pour les petits p, on peut espérer que k=1 suffit, mais la recherche d'une solution modulo p n'est pas facile. On peut l'obtenir par calcul d'une base de Gröbner modulo p, mais si cette recherche aboutit, un logiciel comme GB [19] arrivera vraisemblablement à calculer une base de Gröbner dans Z.

Malle [29] a utilisé la métrique 23-adique pour le groupe Aut(M₂₂) des automorphismes du groupe de Mathieu M₂₂ , mais cette approche ne paraît pas prometteuse dans le cas général : il avait une connaissance a priori du corps K, et nous montrons au paragraphe IV.5.2 qu'on peut arriver au même résultat à l'aide d'approximations dans C.

d. Dans C

Une variante (classique) de l'algorithme de Newton permet (presque) toujours de se rapprocher d'une solution : on remplace par + k avec k dans ] 0, 1] de telle sorte que ||F( + k )|| < ||F()||. En réalité, on se rapproche ainsi d'un minimum local de ||F||. Le système et l'approximation initiale doivent être étudiés pour que ce soit un zéro.

Une fois que est dans la zone de convergence, l'algorithme de Newton aboutit rapidement à la précision demandée. Le nombre de chiffres significatifs gagnés double à chaque étape, ce qui permet de connaître la précision de l'approximation que nous avons calculée.

Il est possible de converger plus vite, par exemple en calculant la différentielle seconde de F.

I.3.3 Choix de l'approximation initiale

a. Problématique

Dans le cas des dessins d'enfants, toutes les solutions du système ne sont pas intéressantes. En particulier, il faut éviter les solutions triviales, qui correspondent à la collision de plusieurs points. Ceci peut être obtenu en utilisant une formulation du système qui élimine la plupart des solutions parasites (cf. section III.1.2).

Il faut aussi choisir l'approximation initiale de telle sorte que nous puissions maîtriser la solution vers laquelle convergera le système. C'est ainsi que nous pouvons calculer suffisamment de points pour obtenir la description d'une solution de dimension 1 ou plus.

b. Difficulté du cas général

Dans le cas général, une valeur de départ quelconque risque de ne pas permettre de convergence. En particulier si la variété solution est de dimension 1 ou plus, il y a le risque de se rapprocher de la variété sans se rapprocher d'un point particulier de celle-ci. On voit alors par exemple une fuite vers l'infini.

c. Résolution successives de problèmes proches

Après une étude spécifique, il peut être possible de trouver un système algébrique plus simple, dont les solutions sont proches de celles du système étudié.

Dans le cas de revêtements (dessins d'enfants), le choix naturel est un dessin dont la structure topologique est proche de notre problème. Sa géométrie est alors assez proche de la solution cherchée (cf. III.3.1 et III.3.3).

I.3.4 Algébrisation

a. Conditions

Nous devons connaître a priori la dimension de la variété et avoir suffisamment de points très proches de cette variété.

Le nombre de points et la précision nécessaires ne sont pas toujours faciles à estimer. Nous pouvons contourner cet obstacle en vérifiant formellement nos résultats et en calculant de nouveaux points ou avec une précision plus grande si besoin.

b. Dépendance algébrique, pour une solution de dimension 0

La variété solution est un ensemble fini de points de ^m. Pour chaque point y = (y₁,..., y_m) de la solution nous sommes intéressés par le calcul de son corps de définition L qui nous permettra d'exprimer ses coordonnées en termes exacts.

Si nous connaissons une borne supérieure d [L : K] et si P le polynôme minimal de = y_i est de degré supérieur à d/2, on en déduit que L = K[X] / (P). Nous devons donc trouver le polynôme minimal d'un nombre algébrique dont on connaît une approximation proche de .

Le calcul de P se fait en remarquant que P() est proche de 0. Il s'agit donc de trouver une relation de dépendance linéaire entre 1, , ², ..., ^d telle que _j=0..d p_j ^j soit proche de 0.

Supposons que K = Q, nous devons alors chercher des p_j dans Z tels que |_j=0..d p_j ^j| soit minimal. Comme suggéré par Lenstra, Lenstra et Lovász [28], ceci peut être réalisé par la recherche d'un vecteur court dans le réseau décrit au paragraphe suivant.

Il importe que soit suffisamment proche de , pour que ces p_j soient les coefficients de P. Le paragraphe d'après étudie cette question.

c. Utilisation de l'algorithme LLL

Soit (V_j)_j=1...p une famille libre de vecteurs de Qⁿ. L'ensemble des combinaisons linéaires _j q_jV_j (avec q_j dans Z) forme un réseau dont (V_j) est une base. Le déterminant du réseau est l'aire p-dimensionnelle du parallélépipède engendré par les (V_j ; il ne dépend pas du choix de la base. La notion de base réduite d'un réseau peut être définie de plusieurs façons qui ne sont pas équivalentes. Les vecteurs d'une base réduite ont une norme assez petite et sont presque orthogonaux les uns aux autres. Les algorithmes de réduction de réseau, dont LLL, calculent une base réduite, donc un vecteur non nul de norme assez petite. On peut considérer qu'en pratique cette norme est inférieure à la racine p-ième du déterminant du réseau. Il est possible de prouver que pour LLL elle est inférieure à 2^{p(p-1)/2 1/p}.

À tout polynôme Q(X) = _j p_j X^j on associe le vecteur du réseau V_Q = _j p_j V_j. Nous construirons un réseau tel que V_p soit très probablement son vecteur le plus court.

Nous avons le choix de l'algorithme de réduction de réseau : l'algorithme LLL est le plus rapide, il s'exécute en temps polynomial. L'algorithme Korkine-Zolotarev donne une base beaucoup plus réduite, mais en temps exponentiel. Les variantes intermédiaires Block-KZ (avec ou sans élagage de l'arbre de recherche) sont polynomiales mais bien plus lentes que LLL.

Si un algorithme de réduction plus puissant que LLL trouve V_p dans la base réduite du réseau, il est toujours possible, en augmentant légèrement la précision avec laquelle approche , de construire un autre réseau tel que LLL trouve V_p. L'expérimentation confirme que cette augmentation de précision n'est pas pénalisante et que nous avons intérêt à utiliser LLL, bien plus rapide que les autres algorithmes de réduction.

d. Précision nécessaire 

Nous plongeons dans C, donc est élément de C, et nous supposons que est un nombre complexe quelconque, proche de . Il faut trouver une valeur N dans R_>0 suffisante pour qu'on puisse calculer P dès que | - | < 1/N.

Si nous avons un tel N, nous notons R_j et I_j les parties entières des parties réelles et imaginaires de N^j. Les d+1 vecteurs V_j = (0, ... , 1, ..., 0, R_j , I_j) pour j=0...d (avec un 1 en j-ième position) sont libres dans Q^d+3 et engendrent donc un réseau. Lorsque  max |q_j| = K, sa norme est environ :

||V_Q|| max(Kd, |N Q()|).

L'ensemble Z_K,d[X] des polynômes de Z[X] de degré au plus d et de coefficients majorés par K a un nombre fini d'éléments. Si est racine d'un de ces polynômes, alors il existe une borne minimale _K,d telle que pour tout Q dans Z_K,d[X], soit Q() = 0, soit |Q()| _K,d.

Supposons que nous avons une borne K sur les coefficients de P le polynôme minimal que nous cherchons. Si N > K d / _K,d , alors ||V_Q|| < Kd si, et seulement si, Q = P. Si de plus N > K^d+1, alors le vecteur calculé par LLL est très probablement V_p.

Malheureusement, la borne _K,d est difficile à calculer. Expérimentalement, on remarque que ce n'est pas nécessaire pour les dessins d'enfants. Nous avons mesuré des valeurs comprises entre 0,53 et 1,18 pour 1/(d+1) (log N / log K), pour d valant jusqu'à 60. On a aussi remarqué que pour les corps de définition des dessins calculés, K < 10^2d, ce qui nous donne en première estimation N = 10^2d².

e. Solution de dimension 1 

Nous devons calculer des approximations numériques d'un grand nombre de points de la courbe V, pour trouver ensuite un paramétrage naturel. Ceci se fait donc en deux étapes.

Pour avoir suffisamment de valeurs sur V, nous devons faire varier un paramètre du système, par exemple en changeant l'approximation initiale à partir de laquelle nous allons faire converger vers une solution. Il existe une variable y_i du système telle que la projection de V sur le i-ième axe de coordonnées ne soit pas réduite à un point. Nous cherchons par exemple des points de V ayant leur i-ième coordonnée fixée a priori.

Nous avons ainsi un grand nombre de valeurs = (₁ , ... , _m) que nous supposerons suffisamment proches de la courbe solution du système, définie sur K. Nous cherchons alors un paramètre rationnel de cette courbe.

Nous devons trouver un nombre suffisant de fonctions _i, fractions rationnelles en les variables du système, pour en extraire un paramètre naturel. Nous faisons ceci par étapes : si nous trouvons une équation polynomiale P₁(₀, ₁) = 0, nous construisons un paramètre t₂ de la courbe définie par P₁, en désingularisant cette équation. Puis nous cherchons une équation P₂(t₂, ₂) = 0, d'où un paramètre t₃, jusqu'à avoir un paramètre de V. C'est ce que nous avons mis en oeuvre pour le calcul d'un polynôme de groupe de Galois M₂₄ (voir § IV.5.4.d.).