Table des matières

Présentation générale

Ce rapport se divise en deux parties principales. Les chapitres 1, 2 et 3 concernent des travaux sur les transséries en prolongement de ma thèse. Les chapitres 4, 5 et 6 forment le départ de mon projet pour automatiser ce qui peut l'être dans l'analyse complexe, et sont au centre de mes intérêts actuels.

Le premier chapitre reprend avec plus de détails et quelques améliorations les résultats de la première partie de ma thèse. Le théorème différentiel des valeurs intermédiaires et la partie concernant les transséries complexes sont plus nouveaux. Ces travaux ont fait l'objet d'un livre [117], de deux articles [103, 105] et quelques prépublications [99, 100].

Le chapitre 2 est surtout consacré à la thèse [79] de mon étudiant M. Schmeling, soutenue avec mention très honorable. Tandis que J.P. Ressayre dirigeait cette thèse d'un point de vue administratif, je me suis occupé de l'encadrement scientifique. Le sujet de la thèse concerne la construction de corps de transséries généralisées, adaptés pour la résolution asymptotique d'équations différentielles de composition.

Le chapitre 3 concerne différentes façons d'incarner des transséries en analyse et les relations avec la théorie des modèles. On y montre notamment que le corps des transséries différentiellement algébriques sur donne lieu à un corps de Hardy. Cette partie a fait l'objet de deux articles [6, 116] et des travaux sont en cours en collaboration avec M. Aschenbrenner et L. van den Dries.

La deuxième partie commence par des résultats théoriques de décidabilité et calculabilité en analyse complexe. On y rappelle quelques théorèmes classiques sur les nombres réels calculables et poursuivons avec la formalisation des fonctions analytiques calculables. On y aborde également l'épineux problème des tests de nullité. Le chapitre 4 a donné lieu à plusieurs articles [110, 119, 120, 106, 113, 112, 114] et quelques prépublications [108, 101, 104].

Dans le chapitre 5, on étudiera des algorithmes efficaces pour évaluer différents types de fonctions analytiques. On commencera par les fonctions holonomes, qui couvrent la plupart des fonctions spéciales, et que l'on traitera de façon assez complète, y compris dans des singularités. Ces résultats ont été publiés dans [98, 102, 121]. On considérera ensuite des solutions à des équations différentielles plus générales [97, 107, 109, 122, 115].

Dans le dernier chapitre, on verra une application a priori surprenante de l'analyse complexe effective à la factorisation d'opérateurs différentiels et le calcul de leurs groupes de Galois différentiels [118].

1 – Transséries réticulées

La théorie des transséries vise à modéliser aussi explicitement que possible des comportements asymptotiques réguliers à l'infini. Pour la plupart des fonctions naturelles de l'analyse, il fut déjà remarqué par Hardy que les « fonctions » fournissent un cadre assez large et souple pour ce genre de modélisation. Ici, une fonction est construite à partir de et une indéterminée infiniment grande, par les opérations de corps, l'exponentielle, le logarithme et des fonctions algébriques.

Le corps des fonctions est totalement ordonné, valué, et stable par dérivation. Toutefois, certaines fonctions « naturelles », comme l'inverse fonctionnelle de , ne peuvent pas s'exprimer dans une échelle de fonctions [96, Section 1.7.4]. Ce problème vient essentiellement du fait que les fonctions sont données par des expressions finies : en autorisant des sommes infinies dans la définition, on obtient le corps beaucoup plus vaste et stable des transséries. En revanche, les transséries sont de nature purement formelle et leur lien avec l'analyse est un sujet en soi (voir le chapitre 3).

Les transséries sont apparues plus ou moins simultanément dans plusieurs domaines différents :

• En théorie des modèles [26, 24, 62, 63, 60], du fait que le corps des transséries forme un modèle pour plusieurs théories intéressantes.

• En analyse [37, 38], dans la démonstration de la conjecture de Dulac par Écalle, en raison de la non-oscillation des transséries.

• En calcul formel [42, 43, 93, 96], où elles fournissent un bon cadre formel pour automatiser le calcul asymptotique.

En réalité, il existe plusieurs types de transséries, dépendant de leurs types de support. Dans ce chapitre, nous allons étudier le type le plus répandu des « transséries réticulées », qui interviennent dans la résolution d'équations différentielles. Notre exposé suit le livre [117] et l'article [100]. Une partie des résultats des sections 1.1 et 1.4 se trouvent aussi (sous une forme parfois différente) dans [46, 51, 37, 62, 63, 60].

1.1.Séries réticulées

Soit un anneau de coefficients et un groupe (ou monoïde) commutatif de monômes, partiellement ordonné par une relation de dominance asymptotique . Un sous-ensemble est réticulé, s'il existe des ensemble finis et avec pour tout et . Si l'ordre est total, on peut toujours prendre . Une série réticulée est une somme formelle avec , dont le support est réticulé. On désigne par l'ensemble des séries réticulées à coefficients dans et avec des monômes dans .

Proposition 1.1. [117, Chapitre 2]

Exemple 1.2. Si est un infinitésimal formel, alors , et sont les anneaux de séries formelles, de séries de Laurent et de séries de Puiseux.

Si est totalement ordonné, alors chaque série non nulle admet un unique monôme dominant et on désigne par le coefficient dominant correspondant. Ceci permet d'étendre la relation à tout entier par . Si est un anneau totalement ordonné, alors il en est de même pour en déclarant .

Les séries étant des sommes infinies, il est naturel de chercher à définir une sommation infinie sur . Une famille est réticulée lorsque est réticulé et est fini pour tout . Dans ce cas, la somme est à nouveau une série réticulée dans .

Il est à noter que la sommation forte n'est pas de nature topologique. Par exemple, pour , la famille ( est réticulée, bien qu'elle ne donne pas lieu à une suite de Cauchy dans . En revanche, la sommation réticulée vérifie plusieurs axiomes de l'« algèbre forte » [117, Sections 2.4 et 2.5]. Cette théorie vise à généraliser l'algèbre en remplaçant l'addition par une sommation d'arité infinie. Dans la suite, on utilisera l'adjectif « fort » chaque fois que l'addition doit être repensée dans ce sens (linéarité forte, dérivation forte, etc.).

Proposition 1.3. [Extension par linéarité forte] Soit une application qui envoie tout ensemble réticulé vers une famille réticulée . Alors admet une unique extension fortement linéaire.

Exemple 1.4. Soient et (c.à.d. ). Alors la composition ) peut se définir comme la somme de la famille réticulée (. Les propriétés habituelles comme () suivent directement de la proposition 1.3.

Remarque 1.5. On obtient différents autres types intéressants de séries en considérant d'autres types de support. La condition minimale pour pouvoir multiplier est que les supports soient bel-ordonné. Par ailleurs, si est la classe des ensembles permis pour les supports, doit être stable pour l'union, le produit et l'opération pour des parties infinitésimales : si et , alors .

Remarque 1.6. Pour simplifier, supposons que soit total. Alors chaque série admet une représentation

On appelle une représentation cartésienne de . Chaque classe « intéressante » de séries (comme les séries convergentes, calculables, algébriques, etc.) induit une classe correspondante de séries réticulées, en imposant la restriction . Lorsque est en outre une communauté locale, alors un grand nombre de propriétés algébriques de se transfèrent à ; voir [117, Section 3.5] pour quelques exemples, ainsi que [96].

1.2.Méthode des polygones de Newton

Supposons maintenant que est un groupe totalement ordonné et divisible, ce qui signifie que chaque équation avec et admet une solution . En utilisant la méthode des polygones de Newton, on montre que est algébriquement clos (resp. réel clos), lorsque l'est. Dans [117, Chapitre 3] nous le faisons dans le cadre légèrement plus général des équations asymptotiques, qui permet d'exprimer la méthode des polygones de Newton d'une façon particulièrement élégante, et qui se généralisera par la suite à d'autres types d'équations.

Plus précisément, soit et et considérons l'équation asymptotique algébrique

(1.1)

La plus grande puissance de intervenant dans une arête du polygone de Newton (et qui vérifie la contrainte asymptotique) est appelée degré de Newton de (1.1). Ce degré se manipule de façon analogue au degré d'un polynôme. Par exemple, . De façon duale, on peut aussi interpréter avec ) comme la multiplicité de comme solution à modulo ).

Le méthode de Newton consiste d'abord à déterminer les termes dominants possibles pour une solution. On appelle terme débuteur un tel terme . Ensuite, on applique un raffinement

avec , ce qui conduit à une nouvelle équation asymptotique

avec . On montre que avec égalité si et seulement si est un terme débuteur de multiplicité , ce qui arrive notamment lorsque (1.1) admet une solution de multiplicité . Dans ce cas, on résout plutôt l'équation

qui est quasi-linéaire (c.à.d. ) et on prend au lieu de . Bien que l'on aura toujours , le degré de Newton ne peut que décroître strictement à l'étape suivante, puisque . Après un nombre fini d'étapes, on se ramène ainsi au cas , qui se traite avec un théorème adapté de fonctions implicites.

Théorème 1.7. [117, Chapitre 3]

1.3.Théorème des fonctions implicites

Le théorème des fonctions implicites utilisé pour démontrer la partie (a) du théorème 1.7 se généralise à des opérateurs réticulés plus généraux. Soient et des ensembles de monômes, inclus dans un groupe de monômes . Grosso modo, un opérateur réticulé est une application , telle que admet un développement en série

où

pour certains opérateurs fortement multi-linéaires .

Le support de l'opérateur est le plus petit ensemble avec

pour tous les . Les opérateurs sont par ailleurs des combinaisons linéaires fortes d'opérateurs atomiques

Un tel opérateur est dit extensif si pour tout . On dit que est extensif si tous les opérateurs intervenant dans la décomposition atomique sont extensifs.

Théorème 1.8. [117, Théorème 6.15] Considérons un opérateur réticulé

strictement extensive en , et tel que

soit réticulé avec . Alors pour tout , il existe un unique avec

et l'opérateur est réticulé.

1.4.Transséries réticulées

Les transséries sont construites en clôturant sous le logarithme et l'exponentielle. La première étape est simple : le corps des transséries logarithmiques est , où . On définit un logarithme sur par

où et .

Pour la deuxième étape de clôture par exponentiation, il faut avant tout décider quels seront les nouveaux monômes. Or, étant donnée une série où est totalement ordonné, admet une décomposition canonique , avec , et . Maintenant, l'idée consiste à imposer que pour tout monôme . Ayant construit , avec , on peut alors adjoindre un étage d'exponentielles formelles en prenant . Enfin, est le corps des transséries en . À cause de la condition de finitude pour les supports réticulés, on a avec . On montre que est un modèle de la théorie des « corps exponentiels ordonnés » [25] :

Théorème 1.9. [117, Chapitre 4] est un corps exponentiel ordonné.

Remarque 1.10. De façon équivalente, on peut construire en partant de et en clôturant d'abord par rapport à l'exponentiation et puis par rapport au logarithme. Le résultat de la première étape s'appelle le corps des transséries exponentielles. On a .

Le corps est valué, avec ou comme groupe des valeurs. Les différentes classes archimédiennes de se décrivent de façon particulièrement simple à l'aide de la relation de platitude qui est caractérisée par :

De façon plus fine, on peut chercher à développer les transséries dans des échelles asymptotiques particulièrement simples et adaptées au calcul effectif. On dit que avec dans est une transbase lorsque

TB1

pour un certain .

TB2

pour .

La démonstration du théorème suivant est très constructive et donne lieu à des algorithmes dans un contexte plus effectif [96] :

Théorème 1.11. [117, Théorème 4.15] Soit une transbase et . Alors il existe une transbase avec .

Le corps est également stable par dérivation, intégration, composition et inversion fonctionnelle et cette structure supplémentaire est compatible avec l'ordre et la sommation réticulée :

Théorème 1.12. [117, Sections 5.1 et 5.2] Il existe une unique dérivation forte sur avec et pour tout . Cette dérivation vérifie :

Par ailleurs, il existe une unique intégration forte avec et pour tout .

Théorème 1.13. [117, Sections 5.3 et 5.4] Soit . Alors il existe un unique opérateur aux différences fort avec et pour tout . Cet opérateur vérifie :

Par ailleurs :

Enfin, tout admet une inverse fonctionnelle pour .

Remarque 1.14. L'inversion fonctionnelle vérifie aussi le théorème de Translagrange [35] (voir aussi [117, Section 5.4.2]).

1.5.Équations différentielles linéaires

Considérons maintenant la résolution d'une équation différentielle linéaire , avec et . Modulo plusieurs montées (i.e. post-compositions avec ), on se ramène d'abord au cas exponentiel où et . On traite ensuite le cas homogène et inhomogène de façon séparée.

Cherchons d'abord à trouver une solution dans le cas inhomogène, ce qui commence par la recherche du terme dominant de . Pour cela on considère la trace de :

On montre qu'il existe un ensemble avec fini tel que la restriction est croissante pour et surjective. En outre, pour tout . Par la proposition 1.3, l'application s'étend en un isomorphisme fortement linéaire . Écrivant , on considère ensuite l'opérateur

Utilisant le théorème 1.8, on montre que est un opérateur fortement linéaire avec pour tout . On appelle l'inverse distinguée de , car pour toute solution non triviale à l'équation homogène .

De fait, les solutions de vérifient nécessairement . Inversement, tout monôme vérifie , ce qui conduit à une solution

de l'équation homogène avec . Par conséquent forme une base, dite canonique, pour l'espace des solutions à l'équation .

Il reste à trouver les éléments de . Pour cela, on utilise une perturbation de la méthode des polygones de Newton. D'abord on transforme l'équation en une équation différentielle algébrique en : on fait les substitutions , , etc. et on divise par . Comme on ne cherche que le monôme dominant de , il suffit de résoudre l'équation modulo . Par ailleurs, comme les coefficients de sont exponentiels, n'est en réalité qu'une perturbation de l'équation . Dans [117, Section 7.5], nous montrons comment adapter la méthode des polygones de Newton habituelle afin de trouver . Si on étend la recherche aux solutions complexes, ce qui nécessite la considération de monômes oscillants , alors on peut garantir l'existence d'une base de solutions :

Théorème 1.15. [117, Corollaires 7.37 et 7.33]

Ce théorème peut se traduire en termes de factorisations de l'opérateur :

Théorème 1.16. [117, Théorèmes 7.39 et 7.40]

Remarque 1.17. Les résultats s'étendent aisément à certaines équations différentielles aux différences linéaires, en réécrivant les opérateurs de post-composition .

1.6.Équations différentielles algébriques

Soient un polynôme différentiel et et étudions l'équation différentielle asymptotique

(1.2)

Afin de généraliser la méthode des polygones de Newton, il faut d'abord pouvoir trouver les débuts de solutions. Cela nécessite en particulier la généralisation du concept de terme débuteur. Modulo des conjugaisons multiplicatives avec , il suffit de pouvoir décider quand est un monôme débuteur. Notons par le terme dominant de en tant que série dans et par l'unique polynôme différentiel avec pour tout . On a :

Théorème 1.18. [117, Théorème 8.6] Soit . Alors il existe un et un tels que pour tout suffisamment grand.

On appelle polynôme de Newton différentiel pour la pente . Tout terme avec est appelé terme débuteur pour (1.2). On définit . En décomposant en composantes homogènes, les annulations dans (1.2) peuvent provenir de deux ou plus de termes et différents ou d'annulations internes dans un seul . Les deux cas sont traités par les propositions suivantes :

Proposition 1.19. [117, Proposition 8.14] Soit avec et pour . Alors il existe un unique tel que ne soit pas homogène.

Proposition 1.20. [117, Proposition 8.16] Soit homogène de degré et considérons le polynôme de Riccati associé avec . Alors le monôme est un débuteur pour (1.2) si et seulement si l'équation

(1.3)

admet un degré de Newton strictement positif.

La proposition 1.19 admettant une variante constructive et l'ordre de l'équation (1.3) étant un de moins que l'ordre de (1.2), ces propositions fournissent un moyen de déterminer les termes débuteurs pour (1.2). On montre à nouveau que le degré de Newton ne peut que décroître pendant le processus des raffinements [117, Section 8.3.4] et que des équations quasi-linéaires admettent toujours des solutions [117, Section 8.5]. La diminution stricte du degré de Newton en cas de solutions presque multiples pose plus de difficultés dans le cas différentiel, mais peut toujours se régler [117, Section 8.6]. En combinant le tout, on obtient donc une procédure, du moins théorique, pour résoudre (1.2) :

Théorème 1.21. [117, Section 8.7] Il existe un algorithme théorique pour trouver les solutions de (1.2).

La notion d'« algorithme théorique » étant un peu vague, on peut chercher à capturer les fruits de notre méthode dans des théorèmes de structure plus précis. Tout d'abord, on peut borner le nombre de nouveaux logarithmes et exponentielles dont on a besoin pour exprimer les solutions [117, Section 8.8]. Deuxièmement, pendant tout le processus de résolution, on conserve la propriété pour les supports d'être réticulé : lorsque l'on cherche des solutions dans des corps de transséries bien ordonnés plus grands (voir le chapitre 2), on ne trouvera pas davantage de solutions. En particulier, des séries comme ou ) sont différentiellement transcendantes sur (voir aussi [44]). Le théorème de structure le plus intéressant est le suivant :

Théorème 1.22. [117, Théorème 9.33] Soient et tels que et . Alors il existe un avec et .

Démonstration. La démonstration s'appuie sur une étude précise de la complétion de avec des coupures de Dedekind. Dans [117, Chapitre 9] on donne deux classifications des éléments de et on étudie le comportement de polynômes différentiels autour des points dans . En déroulant la méthode des polygones de Newton, cela permet en particulier de conserver la propriété de changement de signe sur des intervalles dans de plus en plus petits.

Corollaire 1.23. Tout de degré impair admet une racine dans .

1.7.Transséries complexes

Il est naturel de chercher une contre-partie complexe à la théorie des transséries. Bien que cela nous fait clairement perdre la structure de corps totalement ordonné, on peut espérer conserver l'essentiel, à savoir l'ordre asymptotique et sa compatibilité avec la dérivation. Toutefois, une telle construction n'a aucune chance d'être canonique : il faudrait par exemple décider si ou , et aucun des deux choix n'est à privilégier sur l'autre. Dans [100, Section 2] nous montrons comment généraliser la construction de la section 1.4 au cas complexe, modulo une infinité de choix du genre ou .

Plus précisément, on aura , où est un -espace vectoriel totalement ordonné pour l'action ainsi qu'un -espace vectoriel (non ordonné). Comme dans le cas réel, l'ordre sur vient d'un ordre total sur via le logarithme . Bien que l'ordre total sur ne puisse provenir d'une structure de corps totalement ordonné sur , on peut exiger que la positivité d'un élément soit décidable à partir de son coefficient dominant . L'ordre sur est donc caractérisé par le choix d'un ordre total sur pour chaque , après quoi . L'ordre vérifie pour tout et est caractérisé par un angle et une direction .

Les résultats des sections 1.5 et 1.6 se généralisent au cadre complexe et donnent lieu aux théorèmes suivants :

Théorème 1.24. [100, Théorème 9.4] Toute équation différentielle linéaire avec admet un système fondamental de solutions dans .

Théorème 1.25. [100, Théorème 9.3] Toute équation différentielle asymptotique (1.2) avec admet au moins solutions, en comptant avec multiplicités.

En particulier, le corps est Picard-Vessiot clos, ce qui le rend idéal pour la résolution récursive d'équations différentielles linéaires. En revanche, le théorème 1.25 n'implique pas que soit différentiellement clos, car l'espace des solutions d'une équation d'ordre n'a pas forcément la bonne dimension . Par exemple, l'équation elliptique

(1.4)

n'admet que les trois solutions triviales . Toutefois, le théorème 1.12 garde un certain intérêt en soi et intervient par exemple dans un nouveau test à zéro (voir le théorème 4.8).

2 – Transséries bien ordonnées

On a vu dans le chapitre précédent comment résoudre des équations différentielles à l'aide de transséries réticulées. Les solutions d'équations fonctionnelles simples admettent des solutions dont les supports ne sont pas réticulés, comme

L'élaboration d'une théorie complète pour ce genre d'équations fonctionnelles plus générales comprend les étapes suivantes :

1. Faire l'inventaire des différents types d'équations fonctionnelles que l'on aimerait pouvoir résoudre et les types de solutions en transséries correspondants.

2. Construire les corps de transséries correspondant aux différents cadres, et les munir des opérations habituelles.

3. Généraliser la méthode des polygones de Newton et le théorème 1.22 des valeurs intermédiaires.

L'inventaire donne lieu au tableau suivant :

Type d'équations	Exemple	Type de transséries
différentielles		réticulées
fonctionnelles modérées		bien ordonnées
de composition		de forces supérieures
fonctionnelles générales		imbriquées

Les deux autres étapes demandent un travail considérable, qui fut commencé dans [96] et continué en collaboration avec mon étudiant M. Schmeling [79]. À l'heure actuelle, une bonne partie de l'étape 2 a été complétée dans [79] et, dans des notes non publiées, je suis parvenu à généraliser la méthode des polygones de Newton pour la résolution d'équations différentielles aux différences algébriques modérées.

Ce chapitre correspond grosso modo à un résumé de [79]. Les résultats des sections 2.1, 2.3 et 2.2 sont surtout le fruit de mon travail en prolongement de [96, Chapitre 2], bien que rédigés avec soin dans [79, Chapitres 1–5]. Le sujet original de M. Schmeling portait davantage sur les transséries de forces supérieures ; la section 2.4 résume les résultats de [79, Chapitres 6–9], qui furent obtenus en collaboration avec lui. Il est à remarquer que le livre [37] contient de nombreux autres résultats intéressants concernant les transséries de forces supérieures.

2.1.Corps de transséries

La construction des corps de transséries adéquats pour la résolution d'équations fonctionnelles étant assez complexe, il est utile d'adopter un traitement plus axiomatique et déterminer d'abord les propriétés souhaitables d'un corps de transséries. Cette approche est également utile en théorie de modèles, si on souhaite plonger les modèles d'une théorie avec des opérations comme dans des corps de transséries.

Fondamentalement, un corps de transséries est un corps totalement ordonné de séries généralisées de la forme avec une ou quelques opérations transcendantes supplémentaires comme l'exponentielle (ou le logarithme). Le problème est donc de déterminer des axiomes raisonnables qui expriment la compatibilité entre la structure forte et les opérations transcendantes. Dans un premier temps, on se limite à l'exponentielle (ou le logarithme) comme seule opération transcendante. Pour les transséries de forces supérieures de la section 2.4, il faudra rajouter les itérateurs de l'exponentielle.

Les axiomes de compatibilité entre une fonction exponentielle partielle et la structure sérielle d'un corps de transséries s'expriment le plus facilement en fonction du logarithme :

T1

.

T2

, pour tout , où .

T3

Pour , on a .

T4

Soit une suite de monômes, avec pour tout . Alors et , pour tout suffisamment grand.

L'axiome T2 exprime le fait que le logarithme se développe par la formule de Taylor autour de . L'axiome T3 caractérise les monômes dans en fonction de l'exponentielle.

L'axiome T4 est plus subtil. Par exemple (voir aussi la section 2.3), il existe des corps de transséries qui contiennent des transséries imbriquées comme

Une telle transsérie intervient comme solution de l'équation fonctionnelle

(2.1)

En revanche, l'axiome T4 écarte des « transséries mal imbriquées » comme

Ceci est d'abord souhaitable lorsque l'on veut définir des dérivations sur des corps de transséries. Par ailleurs [96, Section 2.7.1], les solutions à l'équation fonctionnelle

s'expriment en fonction des solutions de (2.1).

Partant d'un « corps exp-log totalement ordonné » , les théorèmes suivants permettent la construction de corps de transséries de plus en plus grands :

Théorème 2.1. est un corps de transséries.

Théorème 2.2. Soit un corps de transséries. Alors il en est de même pour son extension exponentielle .

Théorème 2.3. Soit une suite croissante de corps de transséries. Alors est également un corps de transséries.

En appliquant les deux derniers théorèmes itérativement et de façon alternée sur un corps de transséries donné, on peut espérer construire sa clôture exponentielle . Malheureusement, cette procédure ne termine jamais [96, Proposition 2.2]. Toutefois, si on prend la précaution de se limiter à considérer des séries dont la cardinalité du support est bornée par un fixé, alors la procédure termine toujours [79, Proposition 3.3.1].

2.2.Opérations sur les transséries

Lorsqu'un corps de transséries est muni d'une dérivation (ou d'un opérateur de post-composition), on peut se demander comment étendre à . Bien sûr, on suppose que (resp. ) soit compatible avec la structure transsérielle de : c'est une dérivation forte, qui vérifie pour tout .

Comme la dérivée d'un transmonôme n'est pas forcément un transmonôme, il n'est pas évident a priori que le caractère bien ordonné des supports soit préservé par des extensions de . Pour montrer cela, on utilise une représentation en arbre des termes dans , dont les feuilles sont dans :

La dérivée d'un tel terme s'exprime alors comme une somme indexée par tous les chemins dans cet arbre de la racine à une feuille. Par une combinatoire fine sur ces chemins, on parvient à étendre à . De même, les post-compositions correspondent à des arbres étiquetés à l'intérieur des représentations en arbre.

Théorème 2.4. [79, Théorème 4.4.2] Soit une dérivation sur un corps de transséries . Alors il existe une unique extension de en une dérivation sur .

Théorème 2.5. [79, Théorème 5.3.2] Soit un opérateur de post-composition entre deux corps de transséries et . Alors il existe une unique extension de en un opérateur de post-composition .

2.3.Transséries imbriquées

Le corps , muni de sa dérivation et composition, est stable pour la résolution d'équations fonctionnelles modérées, où on ne compose les fonctions inconnues que par des transséries d'exponentialité zéro (c.à.d. que pour tout suffisamment grand). Toutefois, des instabilités apparaissent dès que l'on considère des équations plus générales. D'une part, il existe des équations comme

(2.2)

dont les solutions en transséries imbriquées

(2.3)

se faufilent dans des coupures au milieu de . D'autre part, il existe des équations d'itération dont les solutions dépassent tous les éléments de (voir la section suivante).

Soit un corps de transséries. Dans un premier temps, il est commode de construire des extensions de par des transséries imbriquées au cas par cas. Considérons deux suites et . On dira que est une paire diagonale si

D1

pour tout et pour tout .

D2

Pour tout et , il existe un tel que tout vérifie

Une telle paire détermine une suite de transmonômes imbriqués formels

Théorème 2.6. [79, Proposition 2.5.14] La relation sur s'étend à

et donne lieu à un corps de transséries .

Dans un deuxième temps, il sera plus utile de faire un théorème d'extension plus uniforme, par exemple en rajoutant toutes les coupures monomiales au sens de [117, Section 9.3.1] en une seule fois. En utilisant la croissance des opérateurs de post-composition, cela permettra sans doute d'obtenir un analogue imbriqué des théorèmes 2.4 et 2.5. Par ailleurs, la construction du théorème 2.6 permet de rajouter les monômes seulement une fois, alors que l'approche par des coupures permettrait l'itération du procédé.

Détaillons un peu plus cette dernière observation et cherchant la solution générale de l'équation (2.2) dans les transséries. En effet, supposons que () est la paire correspondant à la solution (2.3). On peut considérer une deuxième suite

ayant les mêmes expressions en diagonale que les , mais avec dans

On peut vérifier que porte à nouveau la structure d'un corps de transséries dans lequel (2.3) admet deux solutions et avec . En répétant le procédé, on peut obtenir d'autres solutions , , etc. dans des corps de plus en plus grands, avec , , etc. En définitive, on construit ainsi une famille croissante () de solutions de (2.2), indexée par un nombre surréel [22].

2.4.Transséries de forces supérieures

Considérons l'équation d'itération

(2.4)

Toute solution fortement monotone à cette équation croît plus vite que n'importe quelle exponentielle itérée pour . On ne peut donc pas résoudre cette équation dans des corps de transséries classiques, qui sont construits à partir de et par les opérations de corps, la sommation infinie, l'exponentielle et le logarithme.

On est donc amené à construire des corps de transséries, où, outre l'exponentielle et le logarithme, la fonction et son inverse font partie de la signature. Plus généralement, on peut considérer les itérateurs de forces supérieures, qui sont définis par récurrence :

(2.5)

Pour des ordinaux , on définit aussi

On peut même continuer la construction pour des ordinaux plus grands, en utilisant la relation

Dans [79], nous avons entrepris la construction de corps de transséries de forces finies. Il est probablement possible de généraliser la construction selon la même ligne d'idées.

Soit . Un corps de transséries de force est un corps de transséries de force , avec des fonctions partielles , qui vérifient les axiomes suivants :

T1

;

T2

Pour tout et avec , on a

T3

Soit . Alors , si pour tout , on a

T4

Soit une suite de monômes telle que

• , avec , pour tout ;

• , pour tout ordinal .

Alors et , pour tout suffisamment grand.

Les dérivées successives de sont en fait définies comme les pré-compositions à gauche par les transséries de force :

Remarque 2.7. La condition T3 n'est plus une caractérisation des monômes dans en fonction de , mais seulement une condition suffisante pour qu'une transsérie soit un monôme. En fait, les monômes qui vérifient cette condition jouent un rôle important dans la construction des corps de transséries de forces supérieures.

Par ailleurs, la condition sur est vérifiée en particulier lorsque , mais ceci n'est pas nécessaire, comme le montre l'exemple . On notera enfin que si la condition est vérifiée par un certain , elle le sera également par et , pour tout .

Remarque 2.8. Dans [79], la condition T4 est remplacée par une condition techniquement plus simple qui suffit pour les résultats ci-dessous, mais qui exclut l'existence de transséries imbriquées de forces supérieures.

Les théorèmes suivants sont les résultats principaux de [79, Chapitres 6–9]. En rajoutant une hypothèse sur la cardinalité des supports, ils permettent de clôturer un corps de transséries de force sous les opérations .

Théorème 2.9. [79, Théorème 7.6.1] Soit et corps exp-log totalement ordonné et . Alors est un corps de transséries de force .

Théorème 2.10. [79, Théorèmes 7.7.1 et 8.4.7] Soit un corps de transséries de force et . Alors il existe une extension de , telle que est défini dans , pour tout .

Théorème 2.11. Soit une suite croissante de corps de transséries de force . Alors est également un corps de transséries de force .

Remarque 2.12. Par analogie avec la fin de la section 2.3, on peut chercher la solution générale de l'équation (2.4), quitte à considérer des extensions de corps. Or cette fois-ci, la solution générale est simplement ) avec , puisque toute autre solution vérifie pour une fonction -périodique . En particulier, le corps original contient déjà toutes les solutions.

2.5.Perspectives

Afin d'aboutir à une théorie complète, plusieurs points du programme de l'introduction attendent d'être parfaits. Dans l'optique de la résolution d'équations fonctionnelles, il faudrait d'abord munir les corps de transséries imbriquées et de forces supérieures de dérivations et de compositions. Nous conjecturons que dans un corps suffisamment grand de cette nature, le théorème des fonctions intermédiaires est vérifié pour des fonctionnelles arbitraires, fabriquées à partir de la dérivation et de la composition. Pour ce projet, il suffit sans doute de considérer des transséries de forces finies pour lesquelles des paires diagonales donnent lieu à des transmonômes uniques.

Un deuxième projet intéressant s'inspire de l'analogie troublante entre les transséries et les nombres surréels [22]. Nous conjecturons qu'il existe un isomorphisme entre une définition adéquate des transséries et les nombres surréels. Cela donnerait lieu à une description ultime des ordres de croissance à l'infini par des nombres, une structure fonctionnelle sur les nombres, et une notion de simplicité pour les transséries. On peut espérer que la démonstration d'un tel théorème repose essentiellement sur une bonne définition de l'itérateur sur les nombres surréels, pour tout ordinal .

3 – Corps de Hardy et généralisations

Jusqu'à présent, nous avons exclusivement abordé la théorie des transséries sous l'angle formel. On peut faire le lien avec l'analyse d'au moins deux façons :

1. Étant donné un ensemble de transséries, issu d'un problème naturel, comment interpréter les éléments de comme des germes de fonctions réelles à l'infini ? En d'autres termes, désignant par l'anneau des germes de fonctions réelles infiniment dérivables à l'infini, comment construire un monomorphisme , qui préserve le plus de structure possible (comme l'ordre, la dérivation et la composition) ?

2. Étant donné un ensemble de germes à l'infini, comment modéliser par un ensemble de transséries ? Autrement dit, comment construire un monomorphisme qui préserve le plus de structure possible ?

Nous étudierons ces questions dans les sections 3.1, 3.2 et 3.3. Plus généralement, on peut chercher à axiomatiser les propriétés des corps de Hardy et remplacer par n'importe quel autre modèle d'une théorie obtenue ainsi. On développera brièvement ce point de vue dans la section 3.4.

3.1.Corps de Hardy transsériels

Sans doute, la meilleure méthode pour donner un sens analytique aux transséries est le procédé d'accéléro-sommation réelle d'Écalle. Cette théorie est esquissée dans ses grandes lignes dans [37, 38], mais reste à être étendue afin de s'appliquer aux solutions d'équations différentielles du chapitre 1. L'avantage de l'accéléro-sommation réside dans son caractère à la fois canonique et explicite : après sélection d'une « bonne moyenne », tout arbitraire dans la méthode disparaît et toute la structure (dérivation, composition, ordre) est naturellement préservée.

Dans sa forme la plus générale, l'accéléro-sommation fait appel à de nombreuses techniques : fonctions résurgentes, calcul accélératoire, bonnes moyennes, arborification, gestion des échelles, etc. Ayant recherché en vain quelques simplifications, il nous semble que le procédé soit intrinsèquement complexe à mettre en œuvre dans le cadre qui nous intéresse.

Si on laisse tomber l'exigence de canonicité, une autre façon de procéder consiste à unifier la théorie des transséries avec la théorie des corps de Hardy. Plus précisément, considérons le corps des transséries réticulées. Un corps de Hardy transsériel est un sous-corps différentiel de , muni d'un monomorphisme de -algèbres différentielles ordonnées, tel que

HT1

Pour tout , on a .

HT2

Pour tout , on a .

HT3

Il existe un avec pour tout .

HT4

L'ensemble est stable sous la prise de puissances réelles.

HT5

On a pour tout avec .

Il est commode d'identifier avec son image sous , qui est nécessairement un corps de Hardy au sens classique. Comme d'habitude, le jeu consiste ensuite à étendre avec de nouvelles transséries ou fonctions . Typiquement, le nouvel élément vérifie une équation différentielle à coefficients dans .

Afin de formuler le lemme central pour réaliser de telles extensions, on a besoin d'introduire quelques notions. Étant donnés et , on écrit , s'il existe un avec . On dira que et sont asymptotiquement équivalents sur , si pour tout , et différentiellement équivalents sur si pour tout . On appellera aussi coupure sérielle tout élément tel que n'admet pas d'élément -minimal et tel que toute troncature stricte est dans .

Lemme 3.1. [116, Lemme 3.10] Soient et tels que

Alors est un corps de Hardy transsériel pour l'unique morphisme différentiel sur avec .

Corollaire 3.2. La clôture réelle de admet une unique structure de corps de Hardy transsériel qui étend celle de .

Dans le langage de la théorie des modèles, le lemme 3.1 fournit un moyen pour réaliser des « extensions élémentaires », qui préservent le groupe des valeurs de . Les autres extensions différentiellement algébriques se ramènent essentiellement à rajouter des exponentielles ou des logarithmes :

Théorème 3.3. [116, Théorème 3.12] Soit tel que . Alors est un corps de Hardy transsériel pour l'unique morphisme différentiel sur avec pour tout .

Théorème 3.4. [116, Théorème 3.13] Supposons , mais . Alors est un corps de Hardy transsériel pour l'unique morphisme différentiel sur avec pour tout .

3.2.Extensions différentiellement algébriques

Étant donné un corps de Hardy , supposons maintenant que l'on veuille adjoindre une transsérie différentiellement algébrique sur . Pour cela, il faut d'abord être en mesure de fournir une contre-partie analytique de , au moins lorsque vérifie une équation sous une forme normale adéquate. Une technique simple pour construire de telles est basée sur les intégrales itérées. Par exemple, l'équation

admet une solution naturelle

qui converge quand on intègre systématiquement depuis . Dans des cas moins favorables, comme

il faut plutôt intégrer depuis un point suffisamment grand. L'inconvénient de la méthode par rapport à l'accéléro-sommation tient d'ailleurs en ceci que le choix du point n'a rien de canonique. Toutefois, pour n'importe quel choix de , on obtient bel et bien une solution.

De façon plus systématique, on montre d'abord qu'il est toujours possible de mettre l'équation pour sous forme normale

(3.1)

où est « petit » et se factorise

sur . On montre ensuite comment résoudre (3.1) dans par des intégrales itérées, en utilisant le fait que admet comme solution. On obtient ainsi une contre-partie analytique asymptotiquement équivalent à sur . La préservation de la réalité est assez technique, mais peut être assurée en faisant les différentes constructions avec soin. En supposant que vérifie une équation différentielle algébrique de complexité () minimale (où est l'ordre de , et ), on montre en outre que et vérifient les mêmes équations différentielles sur . Cela nous permet enfin d'adjoindre en appliquant le lemme 3.1.

Théorème 3.5. [116, Théorème 5.4] Soit un corps de Hardy transsériel et soit le plus petit sous-corps différentiel de tel que pour tout et . Alors la structure de corps de Hardy transsériel s'étend à .

Corollaire 3.6. Il existe un corps de Hardy qui vérifie le théorème des valeurs intermédiaires pour des polynômes différentiels.

On dit que est différentiellement hensélien lorsque toute équation différentielle quasi-linéaire à coefficients dans admet une solution dans . On peut étendre cette notion à des corps de Hardy différentiellement algébriques sur , afin de montrer un inverse partiel du théorème 3.5 :

Théorème 3.7. [116, Théorème 5.4] Soit un corps de Hardy transsériel et un corps de Hardy qui est différentiellement algébrique sur , hensélien, et stable par exponentiation. Alors on peut munir d'une structure de corps de Hardy transsériel, qui étend celle de .

Corollaire 3.8. Soit un corps de Hardy transsériel et un corps de Hardy qui est différentiellement algébrique sur et hensélien. Supposons que n'admet pas d'extensions différentiellement algébriques de corps de Hardy. Alors vérifie le théorème différentiel des valeurs intermédiaires.

Remarque 3.9. Le théorème 3.5 est classique pour les équations différentielles de premier ordre [48, 49, 12, 88], mais le passage aux ordres supérieurs semble compliqué avec les techniques classiques. Seul [10] contient quelques résultats dans cette direction. Dans ce papier, on démontre aussi que toute solution à l'équation est contenu dans un corps de Hardy, mais qu'aucune solution n'appartient à l'intersection de tous les corps de Hardy maximaux.

3.3.Équations fonctionnelles

Pour l'instant, la généralisation de la théorie des corps de Hardy transsériels aux équations fonctionnelles plus générales semble compliquée. Toutefois, pour des équations simples comme

			(3.2)
			(3.3)

on pourrait au moins vouloir s'assurer que les solutions formelles en transséries peuvent s'incarner de façon analytique.

L'équation (3.2) fut étudiée en 1943 par Kneser, à des fins industriels secrets [58]. Il démontra l'existence d'un itérateur réel analytique de . Le III^ième Reich s'en effondre une seconde fois : on peut même construire des itérateurs réels analytiques de forces supérieures . En effet, on peut toujours s'arranger pour que admette un « bon » point fixe , puisque est solution de (2.4) pour tout , si est solution. On prend ensuite une solution réelle analytique de ) autour de et on la prolonge sur ) par l'équation fonctionnelle.

Plus généralement, Écalle fournit une méthode pour trouver des solutions quasi-analytiques de l'équation [37, Proposition 8.1] : on commence par perturber de façon à exhiber un « bon » point fixe . Cette fonction perturbée admet à nouveau un itérateur naturel autour de , qui se prolonge jusqu'à . Enfin, on obtient en fonction de , par un développement asymptotique rapidement convergent. En revanche, il n'y a pas de véritable moyen pour privilégier le choix d'un itérateur spécifique sur les autres ; toute fonction , avec suffisamment petit et de période , fournit une nouvelle solution.

Afin d'obtenir des solutions quasi-analytiques de (3.3), on procède en plusieurs étapes. D'abord on perturbe la fonction logarithmique de façon qu'elle admette un point fixe. Plus précisément, en écrivant , où vérifie

(3.4)

et où pour un certain , l'équation (3.3) se transforme en

(3.5)

Les solutions quasi-analytiques de (3.4) sont de la forme , avec

(3.6)

où est l'inverse fonctionnelle de

Les solutions de (3.6) sont de la forme , avec

(3.7)

Dans un deuxième temps, il s'agit de résoudre l'équation (3.5). Pour ce faire, on considère d'abord l'équation perturbée

(3.8)

où est choisi convenablement de façon que (3.8) puisse se résoudre par un théorème d'itération autour du point fixe . En utilisant l'équation fonctionnelle (3.8), cette solution est ensuite prolongée jusqu'à l'infini. Les solutions de (3.5) s'écrivent maintenant sous la forme , où

(3.9)

Nous ignorons actuellement si l'équation (2.2) admet des solutions réelles analytiques. À nouveau, on ne voit pas non plus de façon pour privilégier une solution spécifique de (3.3) sur toute autre solution.

3.4.Corps H et corps asymptotiques

La structure particulièrement riche des corps de transséries en font des modèles naturels de nombreuses théories qui étendent l'algèbre différentielle avec une relation d'ordre, une valuation, une sommation infinie ou encore une composition. En collaboration avec Matthias Aschenbrenner et Lou van den Dries, nous essayons de généraliser la théorie des transséries à ce genre de modèles plus généraux.

Soit un corps différentiel avec comme corps de constantes. Une valuation sur détermine des relations et de domination et de prépondérance par et . La relation est compatible avec la dérivation sur si

AS

.

Un corps différentiel muni d'une telle relation est appelé corps asymptotique. De façon similaire, on dit que est un corps H, si est muni d'une relation d'ordre vérifiant

H1

.

H2

Si pour , alors il existe un avec .

En particulier, tout corps H est un corps asymptotique pour la valuation induite par la relation d'ordre.

La théorie de base des corps H a été étudiée par Aschenbrenner et van den Dries [4, 3]. Contrairement à la théorie des corps différentiels, il s'y produit un phénomène étrange de dichotomie lorsque l'on considère des extensions de corps H. Plus précisément, on dit que est Liouville clos si toute équation différentielle de type avec admet une solution dans . Une lacune dans est un élément du groupe de valuation de telle que pour tous les non nuls. Typiquement, des transséries du type

peuvent induire des lacunes. Un corps H admet au plus une lacune et jamais de lacune s'il est Liouville clos. Un corps H avec une lacune admet exactement deux clôtures de Liouville dans lesquelles on a resp. .

Afin de développer la théorie des modèles pour les corps H, il faut d'abord étudier les extensions algébrico-différentielles de corps H, et comprendre quand le phénomène de dichotomie apparaît. Une première question naturelle est de savoir si une extension algébrico-différentielle d'un corps Liouville clos peut présenter une lacune. Dans [6], nous répondons par la positive, en recourant de manière fine à de l'algèbre linéaire forte :

Théorème 3.10. [6] Il existe un corps Liouville clos de transséries, qui contient

mais pas

qui est solution de l'équation

Les transséries de types et jouent un rôle assez important dans la théorie des corps asymptotiques que nous sommes en train de développer [5]. Par exemple, la présence d'un élément de type semble être l'unique obstacle à l'existence d'un polynôme de Newton différentiel (généralisant la même notion dans le cadre des transséries). Ce résultat est intimement lié à une observation d'Écalle : étant donné un polynôme différentiel , les premiers termes de la série sont ultimement similaires à ceux de ou ceux de .

L'existence d'un polynôme de Newton différentiel est la première étape pour la généralisation de la méthode des polygones de Newton différentiels. La question suivante est la résolution d'équations quasi-linéaires (on dira qu'un corps asymptotique est différentiellement hensélien, lorsque toute équation quasi-linéaire sur admet une solution dans ). Il semble que l'absence d'éléments de type peut être préservée lors des extensions par des solutions d'équations quasi-linéaires, mais des vérifications sont encore en cours.

4 – Analyse complexe effective

Un de nos objectifs majeurs est le développement d'un système de calcul analytique, permettant de calculer de manière fiable (et donc en précision arbitraire) avec des objets de nature analytique, de la même manière que le calcul formel permet la manipulation d'objets plus algébriques. Dans ce projet, l'analyse complexe joue un rôle central, pour plusieurs raisons :

1. La plupart des problèmes explicites de l'analyse et du calcul formel (comme la résolution d'équations différentielles) admettent des solutions analytiques ou semi-analytiques.

2. L'existence d'algorithmes efficaces sur les séries formelles donne lieu à une algorithmique multi-précision efficace pour les fonctions analytiques.

3. Les fonctions analytiques sont très rigides, puisqu'entièrement déterminées par leurs développements en série en un point, modulo le procédé du prolongement analytique.

4. Les singularités des fonctions analytiques peuvent souvent être analysées de façon automatique, ce qui permet d'optimiser des algorithmes numériques.

Dans ce chapitre, nous présentons une partie de nos travaux théoriques. Dans les chapitres 5 et 6 nous nous intéresserons à la complexité algorithmique et une application. Des implantations sont en cours dans Mathemagix [123].

4.1.Nombres calculables

Un nombre réel est calculable s'il existe un algorithme d'approximation qui prend avec en entrée et qui rend une -approximation telle que . Nous notons par et les ensembles des nombres réels et complexes calculables. On désignera par l'ensemble des nombres réels digitaux.

La théorie des nombres calculables est bien développée [92, 45, 1, 7, 129]. Elle fut à l'origine de l'introduction des machines de Turing [92]. Plusieurs définitions équivalentes ou subtilement différentes existent pour les nombres calculables [129]. Les nombres réels calculables forment un corps et il existe des algorithmes pour effectuer les opérations de corps, ainsi que d'autres opérations classiques comme , , , etc. Les deux résultats fondamentaux suivants peuvent paraître plus surprenants à première vue :

Théorème 4.1. [92] Il n'existe pas d'algorithme pour décider si un nombre calculable vaut zéro.

Théorème 4.2. [45] Toute fonction calculable d'un ouvert de dans est continue.

L'absence de test à zéro (d'où l'impossibilité de calculer avec des fonctions discontinues) peut être très problématique dans certains contextes. Dans ce cas, on a plusieurs options :

1. On utilise un test heuristique (avec un niveau de « fiabilité » paramétrable).

2. On se limite à utiliser des nombres dans une classe plus petite (comme les constantes algébriques ou exp-logs).

3. On adopte une approche non déterministe [119, Section 2.5].

Dans la section 4.4, nous reviendrons de façon détaillée sur le problème du test à zéro.

Une particularité du calcul avec des nombres réels est l'existence de deux autres classes importantes et à côté de : on dit que est calculable à gauche si est la limite d'une fonction calculable croissante. Un tel nombre correspond à une « borne inférieure calculable ». Les classes et des nombres calculables à gauche et à droite vérifient et ; elles peuvent être interprétées comme le reflet de la notion d'« énumérabilité récursive » de la théorie de calculabilité. Cette subtilité intervient peu en calcul formel, mais assez systématiquement dans l'analyse effective. Nous recommandons de directement en tenir compte dans la définition des types intervenant dans les algorithmes, à l'image de l'introduction de et .

D'un point de vue pratique, le calcul avec des nombres calculables présuppose de rendre automatique le processus des estimations d'erreur. Cela peut se faire a priori, en fonction d'une tolérance en entrée, ou a posteriori, en utilisant une arithmétique d'intervalles [69, 2] ou de boules. Les deux stratégies ont l'inconvénient de potentiellement conduire à une surestimation des erreurs. En plus du développement d'algorithmes efficaces dans un modèle fixé (comme l'arithmétique d'intervalles et une algorithmique efficace pour évaluer des fonctions), il peut donc être intéressant ou nécessaire de rajouter une couche d'optimisation de plus haut niveau, afin de minimiser ces surestimations. Dans le cas le plus simple de l'évaluation d'expressions sous forme de dag (graphes acycliques orientés), il existe quelques pistes pour une telle couche [112, 114, 70].

4.2.La hiérarchie numérique

Notre présentation des nombres calculables nous a déjà permis de distinguer un certain nombres de niveaux conceptuels : un niveau abstrait (calcul avec des éléments de , , ), l'arithmétique d'intervalles, et l'algorithmique efficace sous-jacente avec des approximations (calcul dans ). Cette hiérarchie de niveaux (voir la figure 4.1) est présente d'une façon assez systématique en analyse effective et peut servir de guide pour l'élaboration et l'implantation des algorithmes. Résumons les caractéristiques principales de chaque niveau.

Niveau abstrait

Les objets analytiques de haut niveau peuvent être interprétés comme des promesses pour approximer un objet analytique abstrait avec une tolérance d'erreur fixée par l'utilisateur. La spécification d'un type haut niveau (comme ou ) présuppose la spécification d'un type pour les approximations (comme ), ainsi que pour les tolérances (comme ). Les instances des types haut niveau peuvent être manipulées formellement. Par exemple, on peut utiliser un algorithme générique pour multiplier des matrices à coefficients dans . Toutefois, il est souvent plus efficace de faire ce genre d'opérations à un niveau plus bas (ce qui correspond à une réinterprétation ). Il est donc conseillé de limiter les manipulations haut niveau à l'optimisation des opérations dans les couches d'en dessous.

Niveau fiable

Au lieu de travailler avec des promesses d'approximations, on peut développer plus directement un calcul avec des boules (ou intervalles) généralisées, c'est-à-dire des approximations (comme un centre dans ) munies d'une imprécision (comme un rayon dans ). En fournissant les entrées avec des imprécisions de plus en plus petites, on obtient en général des sorties dont les imprécisions tendent vers , ce qui permet de remonter au niveau abstrait. Pour des raisons d'efficacité et de qualité des rayons, il est souvent préférable de regrouper des ensembles de calcul avec des boules afin d'effectuer la plupart des calculs directement sur les centres, et retarder les estimations d'erreur vers la fin (par exemple, en calculant dans ) plutôt que dans )).

Niveau numérique

Modulo le travail dans les couches au-dessus, le problème initial d'analyse est ramené à un ou plusieurs problèmes de calcul numérique plus classiques. Pour de faibles précisions en nombre de chiffres après la virgule, on peut souvent utiliser des logiciels existants comme boîtes noires. Pour des précisions plus importantes, il peut être nécessaire de développer des algorithmes avec une meilleure vitesse de convergence. Par ailleurs, le problème peut souvent être réécrit en un problème de nature arithmétique, où les nombres flottants dans ont été remplacés par des entiers, après quoi on peut essayer d'appliquer un algorithme de bonne complexité asymptotique.

Niveau arithmétique

Après harmonisation des exposants et remplacement des nombres flottants dans par des entiers dans , on retombe généralement sur un problème « bas-niveau » typique du calcul formel, comme la multiplication rapide des entiers. Dans des cas plus complexes, comme la multiplication de deux polynômes ou matrices avec des coefficients dans , l'harmonisation peut-être un problème difficile en soi (voir [107, Section 6.2] pour quelques astuces typiques). En effet, une mauvaise harmonisation induit de l'instabilité numérique, alors que le renoncement à descendre au niveau arithmétique nous condamne à utiliser des algorithmes de mauvaises complexités asymptotiques.

Figure 4.1. La hiérarchie numérique.

4.3.Fonctions analytiques calculables

Considérons une équation différentielle algébrique

(4.1)

avec des conditions initiales non-singulières en :

(4.2)

Une telle équation admet une unique solution analytique en . Lorsque les coefficients de et appartiennent à un sous-corps , on dira que est une fonction algébrico-différentielle régulière sur , et que est un problème de Cauchy polynomial sur .

Étant donnée une fonction algébrico-différentielle régulière sur , ou toute fonction analytique plus générale donnée sous forme suffisamment explicite, l'analyse complexe effective vise à pouvoir faire des calculs certifiés avec . En particulier, on voudrait pouvoir déterminer la surface de Riemann de , évaluer en n'importe quel point , analyser automatiquement les singularités de , etc.

Dans [110, 119] nous avons introduit plusieurs notions de fonctions analytiques calculables. Commençons par la classe des fonctions analytiques localement calculables. La définition de est récursive : chaque est une fonction analytique en avec les méthodes suivantes :

1. calcule le développement en série de . La classe vient à son tour avec une méthode pour calculer les coefficients de .

2. calcule une borne inférieure pour le rayon de convergence de . Ici, .

3. fournit une borne supérieure pour , sous l'hypothèse que .

4. calcule le prolongement analytique de en , où l'on suppose .

On montre [110] qu'il existe des algorithmes pour les opérations de base dans , comme , , , , , , , , etc.

Il est à noter que le rayon de convergence calculable est autorisé à être strictement inférieur au vrai rayon de convergence. Cette souplesse est importante : dans le cas d'une fonction analytique de la forme , avec , on n'a pas forcément d'algorithme pour détecter l'annulation (voir le théorème 4.1). Il n'y a donc pas d'algorithme général pour détecter que . Le théorème d'indécidabilité suivant explique pourquoi on se contente de demander plutôt que :

Théorème 4.3. [29] Il n'y a pas d'algorithme général pour déterminer si la solution d'un problème de Cauchy polynomial sur vérifie .

Étant donnée une fonction analytique en , on appelle domaine cheminal de , l'ensemble des chemins avec , tels que , , etc. Étant donnée une fonction , on définit de manière analogue le domaine cheminal calculable de (en rajoutant éventuellement les chemins dont une subdivision est dans , comme dans [110]). On a le résultat positif suivant :

Théorème 4.4. [110, 119] Il existe un algorithme qui prend en entrée un problème de Cauchy polynomial sur et qui calcule une solution avec

En particulier, on peut évaluer au bout de chaque chemin dans .

L'approche locale aux fonctions analytiques calculables admet deux inconvénients majeurs : (1) elle ne fournit pas de moyens pour identifier des branches identiques de la surface de Riemann, (2) elle n'impose pas de cohérence globale sur la qualité des bornes effectives et au cours d'un processus de prolongement analytique (étant donnés avec ), on dit que est meilleur que (et on écrit ) si et si , chaque fois que est défini).

Pour ces raisons, nous avons introduit dans [119] la notion de fonction analytique calculable sur une surface de Riemann calculable . Une telle fonction est caractérisée par sa surface de Riemann calculable et une fonction permettant de localiser en n'importe quel point de . Ces localisations vérifient les relations de compatibilité suivantes :

1. est le rayon du plus grand disque avec centre et contenue dans .

2. pour tout et .

3. pour , où désigne le translaté de par sur .

Les conditions 1 et 2 expriment également le fait que les localisations ne peuvent plus être rendues meilleures de façon automatique. Souvent, on suppose également que est muni d'une origine . Un résultat théorique intéressant dit que toute fonction analytique localement calculable peut s'améliorer en une fonction analytique globalement calculable :

Théorème 4.5. Il existe une fonction calculable telle que

Dans [119] on peut trouver un certain nombre d'autres résultats concernant les fonctions analytiques effectives et des algorithmes efficaces pour calculer les bornes et . Dans le passé, nous avons également réalisé un prototype d'implantation ; voir les figures 4.2–4.5.

Figure 4.2. Un polynôme de degré .

Figure 4.3. .

Figure 4.4. Solution d'une é.d.o.

Figure 4.5. Solution de .

4.4.Tests effectifs de nullité

Un problème central de l'analyse effective est de savoir si une constante ou une fonction est identique à zéro. Le théorème 4.1 montre que cette question est indécidable quand on l'envisage en toute généralité. Malheureusement, la question reste difficile pour des classes de fonctions ou constantes plus spécifiques, comme les fonctions algébrico-différentielles régulières sur et leurs valeurs. Même quand tout reste algébrique, la complexité des calculs peut vite devenir grande.

De manière générale, remarquons d'abord que les tests de nullité sont de nature asymétrique : alors qu'il peut être extrêmement difficile de montrer qu'une constante (ou fonction ) est nulle, il est en général facile de montrer le contraire. Par exemple, pour démontrer , il suffit d'évaluer avec une précision suffisante. Par conséquent, il existe des algorithmes différents pour démontrer l'égalité et l'inégalité, et une bonne stratégie globale est de les faire tourner en parallèle.

Le problème des tests à zéro est aussi beaucoup plus difficile pour les constantes que pour les fonctions. Dans le cas des fonctions, leurs équations de définition fournissent généralement les relations à partir desquelles on démontre leur nullité. Dans le cas des constantes, il existe souvent des relations surprenantes supplémentaires, comme dans le cas des multi-zêtas [67, 39, 40, 41], à cause du phénomène de dimorphie. De façon symétrique, démontrer la non-nullité bute généralement sur des questions difficiles en théorie des nombres. Pour ces raisons, il est conseillé de commencer par les fonctions avant de s'attaquer aux constantes.

Enfin, il convient de rappeler qu'un test à zéro concerne spécifiquement une constante ou une fonction. Pour certaines classes, comme les fonctions exp-log ou les multi-zêtas, il existe des théorèmes de structure [76, 39, 40]. Lorsque cela est le cas, on peut souvent concevoir des tests à zéro très efficaces. En revanche, on n'a pas forcément besoin d'un théorème de structure général pour décider si une constante ou fonction particulière vaut zéro.

4.4.1.Conjectures de témoin

Afin de démontrer pour une constante donnée, il suffit de l'évaluer avec une précision suffisante. Une question naturelle est de trouver une borne explicite pour en fonction de la taille pour décrire . Un exemple artificiel comme

(4.3)

montre que cette précision peut devenir très grande pour des petites expressions. Nous conjecturons qu'une presque-identité de se genre est toujours la spécialisation d'un développement asymptotique dont les premiers termes s'annulent (voir aussi [9, 104]). Les conjectures de témoin visent à rendre cette assertion plus précise.

Considérons le cas des constantes exp-log, construites à partir de par les opérations , , , , et . Pour éviter le phénomène (4.3), on ne considérera que des constantes exp-log dont l'expression admet la propriété que pour chaque sous-expression de de la forme ). Pour différentes fonctions , il fut conjecturé [96, 75, 104] que si et seulement , où ) désigne la taille de en tant qu'expression. Malheureusement, on ne peut pas prendre polynomial :

Théorème 4.6. [113] Pour toute fonction polynomiale , il existe une constante exp-log avec , mais .

Démonstration. Nous montrons l'idée de la démonstration pour le cas particulier où . Considérons la fonction

La variable n'intervient que deux fois dans le membre droit, alors que admet un zéro d'ordre à l'origine. Par conséquent, admet une taille , alors que pour un certain .

Remarque 4.7. Même lorsque l'on sait qu'une constante n'est pas nulle, il peut être difficile de déterminer son signe, comme dans l'exemple .

4.4.2.Algorithmes

Au delà du cas algébrique, il existe peu de tests à zéro effectifs pour des constantes. La seule exception notable concerne les constantes élémentaires, qui sont définies par des systèmes d'équations exp-logs. Dans ce cas, il existe un algorithme [74] dont la terminaison dépend de la conjecture de Schanuel.

Il existe plus de travaux dans le cas des fonctions. Un cadre particulièrement intéressant est celui des séries algébrico-différentielles, où on rappelle (voir l'introduction et la section 4.3) que nos fonctions sont généralement données par des séries.

Soit un anneau différentiel effectif avec un test à zéro et . Une série différentiellement algébrique sur est la solution d'une équation (4.1) à coefficients dans . On dira que est régulière lorsque (4.2) est vérifiée. Même dans le cas où est irrégulière (ce qui est par exemple le cas si et est divergente), l'équation (4.1) fournit une relation de récurrence pour les coefficients de pour tout suffisamment grand. Par conséquent, est entièrement déterminée par un nombre fini de données, ce qui permet la construction d'un nouvel anneau effectif . On a le résultat suivant :

Théorème 4.8. [106] Il existe un test à zéro pour les éléments de .

Il existe d'autres approches intéressantes dans des cadres plus restreints [28, 29, 84, 71, 95, 72, 101] ; voir [106, Section 2] pour une discussion. Toutefois, par rapport à ces autres travaux, notre algorithme a l'avantage de combiner efficacité et généralité. Le résultat s'appuie sur de l'algèbre différentielle et généralise un précédent algorithme pour le cas d'ordre un [83, 120]. La complexité de cet algorithme plus particulier fut analysé dans [120] et nous nous attendons à ce que les méthodes employées s'étendent aux ordres supérieurs.

5 – Évaluation rapide de fonctions

Dans le but de développer des logiciels concrets pour calculer avec des fonctions analytiques, il ne suffit pas de montrer que l'on peut faire certains calculs en principe : il faut aussi concevoir des algorithmes efficaces.

Dans ce chapitre, nous considérons le problème fondamental de l'évaluation efficace d'une fonction analytique . Plus précisément, étant donné un nombre calculable , on dit que est de complexité si on peut trouver une -approximation avec en temps . De même, une fonction avec est de complexité si est de complexité pour tout tel que sont de complexité .

Il est classique [80, 54, 91, 23] que la multiplication de deux nombres naturels à chiffres peut s'effectuer en temps presque linéaire . Par conséquent, la multiplication est de complexité sur tout compact . D'autres opérations, comme la division et l'inversion fonctionnelle d'une fonction de complexité , peuvent également se faire en temps , en utilisant la méthode de Newton.

Beaucoup de fonctions spéciales (l'exponentielle, le logarithme, le sinus, toute fonction algébrique, les fonctions hypergéométriques, les fonctions de Bessel, etc.) tombent dans la classe des fonctions holonomes, ou sont facilement exprimables en termes de fonctions holonomes (fonction de Weierstrass, fonction de Lambert, etc.). Une grande partie de ce chapitre est consacrée à l'évaluation rapide de ce genre de fonctions, y compris dans des singularités.

Dans la dernière section, nous considérons l'évaluation rapide de fonctions analytiques plus générales. En particulier, nous présentons la technique de calcul détendu, qui permet la résolution efficace d'équations différentielles ou fonctionnelles à l'aide de séries formelles.

5.1.Fonctions holonomes

Une fonction holonome sur un corps est la solution d'une équation différentielle linéaire

(5.1)

à coefficients dans . Étant donnée une fonction analytique , elle est holonome si et seulement si

(5.2)

Ceci est encore équivalent à l'existence d'une équation matricielle de premier ordre

(5.3)

avec , et telle que est une des composantes de . La caractérisation (5.2) implique en particulier que la classe des fonctions holonomes est stable sous un grand nombre d'opérations comme l'addition, la multiplication, la dérivation, l'intégration, le produit de convolution, etc.

En réécrivant l'opérateur en fonction de , les substitutions et conduisent à une relation de récurrence

(5.4)

pour les coefficients de Taylor de en , et vice versa. Comme dans le cas différentiel, l'existence d'une relation de récurrence (5.4) équivaut à la condition

ainsi qu'à l'existence d'un système aux différences de premier ordre

(5.5)

avec , et tel que est une des composantes de .

5.2.Évaluation en des points algébriques

Soit un corps algébrique de nombres de dimension finie. On montre que deux nombres de tailles dans peuvent se multiplier en temps . Soit une fonction holonome sur d'ordre . Nous disons que admet des conditions initiales dans en un point régulier , si (et donc pour tout ). Pour simplifier les notations, supposons que , et notons par le rayon de convergence de .

Pour avec et , le calcul d'une -approximation de se divise en deux étapes :

1. Couper la série en deux parties et de façon que l'on puisse borner

   (5.6)

2. Calculer une -approximation de

   

Dans [98, 102, 119] nous décrivons différents algorithmes pour obtenir une majoration effective (5.6) tout en s'assurant que ). L'évaluation efficace de se fait moyennant deux remarques.

Premièrement, la série est également holonome, donc le problème se ramène au calcul efficace des coefficients d'une série holonome. Pour la suite, soit

une équation de récurrence matricielle, où est un vecteur avec comme première entrée et où est une matrice à coefficients dans .

Deuxièmement, le calcul de se ramène au calcul d'un produit de matrices

(puisque ), ce qui peut se faire par la stratégie dite « diviser pour régner » :

			(5.7)
			(5.8)

Dans le cas où , ceci peut s'illustrer par l'arbre suivant :

En analysant la procédure, on observe que la taille des entrées de chaque matrice est environ le double de la taille de . Donc, chaque fois que l'on monte un cran dans l'arbre, la taille des entrées des matrices double alors que le nombre de matrices à multiplier se divise par deux. En évaluant le coût des opérations, il s'ensuit que les multiplications sur chaque ligne ont grosso modo un coût constant, si on utilise une multiplication rapide. Par ailleurs, les nombres sur la dernière ligne sont de tailles . Ceci conduit au théorème suivant :

Théorème 5.1. [96, 98] Soit un corps algébrique de nombres et soit une fonction holonome sur , avec des conditions initiales en dans . Soit le rayon de convergence de et soit tel que . Alors on peut calculer avec une précision de chiffres en temps .

Remarque 5.2. La stratégie « diviser pour régner » pour l'évaluation de fonctions holonomes admet une longue histoire. Une première référence sur l'évaluation de et l'exponentielle en utilisant cette méthode est [14]. La généralisation aux fonctions holonomes est due aux frères Chudnovsky [20]. Nous avions redécouvert cet algorithme de façon indépendante dans [96, 98], avec quelques petites améliorations : peut être un corps algébrique de nombres plus général que ; par ailleurs, les bornes (5.6) sont calculées automatiquement. On peut aussi se demander si l'algorithme était connu des auteurs de [81]. Des cas particuliers de l'algorithme furent retrouvés indépendamment par différentes personnes [55, 47].

5.3.Continuation analytique

Une deuxième idée dans [20], que nous avions retrouvée dans [96, 98], est que l'on peut conserver une bonne complexité d'évaluation dans des points non nécessairement algébriques en faisant du prolongement analytique.

Considérons une fonction holonome d'ordre sur . Cette fonction est entièrement déterminée par l'opérateur avec et la condition initiale

dans un point non singulier . Étant donné un chemin en ligne brisée qui évite les singularités de , le prolongement de le long de dépend -linéairement de la condition initiale en . La matrice qui exprime cette dépendance

s'appelle la matrice de connection le long de . Nous avons

			(5.9)
			(5.10)

pour la composition et l'inversion de chemins.

Supposons maintenant que la ligne brisée n'admet que des sommets dans . D'après (5.9) et le théorème 5.1, il s'en suit que peut s'approximer avec une précision de chiffres en temps ). Il est intéressant d'étudier la façon que ce temps de calcul dépend du chemin . En notant par ) la distance de aux zéros de , une analyse plus fine donne :

Théorème 5.3. [96, 98] Soient donnés :

Notons par la somme des tailles de et de et . Alors on peut calculer une -approximation de en temps

(5.11)

uniformément en et en , sous la condition que .

Étant donné un chemin droit tel que et ne soient plus nécessairement dans , on peut approximer par un nouveau chemin

dont les sommets sont tous dans . Plus précisément, prenons pour et les troncatures des écritures binaires de et à chiffres après la virgule. Dans l'estimation (5.11) pour les matrices et , on aura alors simultanément ) et ). Le coût du calcul est donc plus ou moins indépendant de , alors que ) étapes suffissent pour garantir que . Prenant en compte que l'estimation (5.11) devient ) pour , on trouve :

Théorème 5.4. [96, 98] Soit un opérateur différentiel non nul sur un corps algébrique de nombres et soit un chemin en ligne brisée dont les sommets sont calculables. Alors une -approximation de peut être obtenue en temps , supposant que l'on fasse abstraction du coût pour approximer et .

Remarque 5.5. L'astuce de l'approximation de et par des nombres dont la précision double à chaque étape porte le nom « bit burst » dans [20]. Leur analyse de complexité plus grossière conduit à une borne de complexité légèrement moins bonne que la nôtre.

Plus généralement, on peut utiliser le théorème 5.3 pour approximer un chemin arbitraire par une ligne brisée adéquate, toujours dans l'optique de calculer efficacement. En dehors des extrémités du chemin, on a clairement intérêt à chercher des sommets de taille minimale dans , afin de minimiser dans (5.11). Parmi toutes les approximations de en ligne brisée , il s'agit ensuite de minimiser la somme

Cela peut s'interpréter comme un problème de recherche de « géodésiques discrètes ». Tant que la singularité (disons ) la plus proche ne change pas, la stratégie optimale consiste à prendre constant (en approximation). Écrivant avec , ceci conduit à minimiser

pour en fonction de . Pour , cela donne et pour , on obtient avec . Pour des chemins plus complexes, nous remarquons enfin la possibilité de précalculer les matrices de monodromie autour de chaque singularité pour un point de base fixe.

5.4.Singularités régulières

L'algorithme de la section 5.2 ne s'applique pas directement pour calculer un grand nombre de décimales de , bien que soit l'évaluation en du trilogarithme , qui est holonome. Le problème vient du fait que le trilogarithme admet des singularités en (dans un autre feuillet de la surface de Riemann) et en . Ceci conduit à s'interroger sur la manière de calculer la limite d'une fonction holonome dans une singularité lorsque celle-ci existe. Commençons par les singularités régulières.

Soit un opérateur différentiel, où . On rappelle que est régulier en si . Par exemple, l'opérateur est régulier en , et on a . Un opérateur régulier admet un système fondamental de solutions locales de la forme

(5.12)

où sont des séries convergentes dans et est algébrique sur . Une telle solution peut également s'interpréter comme une série généralisée dans (voir aussi la section 1.5), avec un monôme dominant de la forme ().

Fixons un ordre total sur le groupe des monômes , qui prolonge l'ordre naturel sur . Alors il existe un unique système fondamental, dit canonique, de solutions , vérifiant les propriétés suivantes :

SFC1

Les monômes dominants des vérifient .

SFC2

Pour tout , le coefficient de dans vaut .

SFC3

Pour tout et tout , on a .

Par dualité, l'existence d'un système fondamental canonique de solutions permet de définir la condition initiale d'une solution de en comme le vecteur colonne avec

Ceci permet de généraliser la notion de matrice de connection pour des chemins droits de à avec petit. Ici, l'angle de sortie est dans et non pas dans , afin de déterminer . En utilisant les relations (5.9) et (5.10), cette généralisation s'étend à des chemins en lignes brisées qui peuvent passer à la fois par des points non singuliers et singuliers réguliers, quitte à spécifier des angles de sortie et d'arrivée pour les singularités régulières rencontrées. Cette construction, et sa contre-partie géométrique de « surfaces de Riemann étendues », est expliquée en détail dans [102].

Venons en maintenant à l'évaluation efficace de solutions de type (5.12). Sans perdre de généralité, on peut supposer que et que toutes les solutions à dans )) sont dans . En généralisant les transformations et de la section 5.1, on montre [102, Section 3] qu'il existe un système de première ordre

(5.13)

avec à coefficients dans , et tel que le vecteur contient comme entrées. Par ailleurs, chaque entrée de est bornée pour , ce qui explique la convergence des séries . La seule différence avec le cas non singulier réside dans le fait que les dénominateurs des entrées de peuvent s'annuler pour un nombre fini de valeurs . Pour ces valeurs dégénérées, nous montrons [102, Section 3.2.3] comment trouver des matrices exceptionnelles pour lesquelles la relation (5.13) reste vraie. La stratégie « diviser pour régner » de (5.7) et (5.8) peut alors s'appliquer comme avant, ce qui nous amène au résultat suivant :

Théorème 5.6. [102] Soit un opérateur différentiel linéaire, régulier en . Alors il existe un nombre tel que pour tout avec , la matrice de transition peut être évaluée avec une précision de chiffres en temps .

Remarque 5.7. Dans un certain nombre de cas, les valeurs de fonctions holonomes dans des singularités régulières peuvent aussi être obtenues en utilisant des relations remarquables. Par exemple, dans [56, 47], l'algorithme « diviser pour régner » est appliqué plus directement pour l'évaluation de et , . Plus généralement, des coefficients de la série de Drinfel'd [34, 65, 66] peuvent se calculer de façon commode en utilisant une relation remarquable [102, Remarque 4.1].

Remarque 5.8. Le calcul des matrices de connection admet deux applications intéressantes [102, Section 4.2.4] : le calcul de valeurs renormalisées de fonctions holonomes et la résolution de problèmes de Sturm-Liouville (et leurs généralisations à plusieurs singularités et plusieurs conditions initiales).

5.5.Accéléro-sommation

Pour avoir un ensemble complet d'algorithmes pour l'évaluation de fonctions holonomes, il reste à traiter le cas des limites dans des singularités irrégulières. Par exemple, la constante d'Euler est le résultat d'une évaluation de ce type :

(5.14)

Une difficulté majeure des singularités irrégulières est que les solutions formelles en séries sont généralement divergentes. On ne peut leur donner un sens analytique que par des techniques de resommation [8, 50], ce qui rend les algorithmes nettement plus complexes que ceux des sections précédentes.

Dans l'article [121], nous montrons comment généraliser les matrices de connection aux chemins passant par des singularités irrégulières, en utilisant une version fine de la procédure d'accéléro-sommation d'Écalle [36, 37, 38, 13]. Nous montrons ensuite comment utiliser des algorithmes « diviser pour régner » pour le calcul efficace de ces matrices. Il est à noter que les matrices de Stokes sont un cas particulier de la théorie. Très brièvement, les idées principales sont les suivantes :

Conditions initiales généralisées

Les constructions des bases fondamentales canoniques de solutions et la notion duale des conditions initiales dans la singularité se généralisent, en considérant des solutions sous forme de transséries formelles, généralement divergentes.

Accéléro-sommation

Les transséries formelles dans la base fondamentale canonique des solutions sont transformées en véritables solutions analytiques via le procédé d'accéléro-sommation d'Écalle :

Ceci permet de définir des matrices de transition entre et des points dans un secteur au voisinage de ; outre l'angle de sortie, il faudra spécifier les angles utilisés lors des accélérations et de la transformation de Laplace finale.

Opérateurs d'annulation

Le processus d'accéléro-sommation peut s'effectuer sans sortir du cadre des fonctions holonomes. Nous montrons comment calculer des opérateurs d'annulation pour toutes les fonctions intermédiaires, y compris les majeurs. En outre, ces opérateurs sont suffisamment petits pour que la condition de croissance à l'infini (propre au processus d'accéléro-sommation) soit respectée pour toutes les solutions de l'opérateur.

Intégration

Moyennant tout ce qui précède, on se ramène au problème suivant : étant donnée une équation holonome dont le système fondamental des solutions admet une décroissance exponentielle à l'infini, comment calculer l'intégrale d'une solution particulière entre un point donné et l'infini ? On montrera comment calculer ce genre d'intégrales en utilisant la stratégie « diviser pour régner ».

Estimations automatiques des erreurs

Toutes les bornes d'erreur intervenant dans le processus peuvent se calculer de façon entièrement automatique en fonction de l'équation (5.1) et du chemin suivi.

Au final, ceci conduit au théorème suivant :

Théorème 5.9. [121] Soit un opérateur différentiel linéaire et soit un chemin en ligne brisée, pouvant passer par des singularités régulières ou irrégulières. Alors chiffres de la matrice de connection généralisée peuvent se calculer en temps .

Remarque 5.10. Dans certains cas [121, Annexe A], il est possible d'économiser un facteur en faisant de la sommation jusqu'au plus petit terme [73]. On peut économiser le même facteur lorsque l'intégrande est une fonction entière.

Remarque 5.11. Des algorithmes rapides pour le calcul rapide de la constante étaient déjà connus auparavant [90, 18, 57]. Plusieurs records du monde pour le calcul de ont été obtenus par X. Gourdon et P. Demichel en implantant des versions « diviser pour régner » de [90, 18].

Séries de type ,

Tableau 5.1. Récapitulatif des complexités pour évaluer différents types de séries holonomes. Nous supposons que et pour certains . Le cas divergent présuppose une procédure adéquate d'accéléro-sommation. La case en jaune corrige une erreur dans [121].

5.6.Algorithmes efficaces pour les séries

Considérons maintenant une fonction analytique plus générale en , avec un rayon de convergence . La stratégie la plus simple pour évaluer en un point avec consiste à calculer un nombre suffisant de coefficients avec une précision suffisante, et de prendre . Dans ce qui suit, on supposera que est la solution unique d'une équation différentielle ou fonctionnelle avec conditions initiales. Dès lors, on peut utiliser la technique des séries majorantes [19, 128, 110, 108] ou des opérateurs contractants [119, Sections 6.3 et 6.4] afin de trouver des bornes effectives pour le rayon et l'ordre . Cela nous ramène au problème de calcul efficace des coefficients d'une série.

Soit donc un anneau effectif de constantes. Pour nos études de complexité, on supposera que les opérations dans ont un coût . En réalité, si on calcule avec des nombres de chiffres, il faudrait donc multiplier nos complexités par . Ce facteur supplémentaire peut être réduit à en recourant à des FFT bivariées.

De manière générale, la plupart des algorithmes pour calculer avec des nombres admettent des variantes pour les polynômes et les séries tronquées. Par exemple, la multiplication de séries à l'ordre peut se faire en temps et la méthode de Newton permet le calcul des inverses, du logarithme et de l'exponentielle en temps .

Une observation importante [15, 16, 17] est que la méthode de Newton peut aussi être utilisée pour résoudre des équation différentielles et fonctionnelles. Pour cela, il est cependant nécessaire que la linéarisée de l'équation puisse se résoudre. Dans le cas d'une équation différentielle d'ordre supérieur, ceci peut se faire par la méthode de variation des constantes [17, 107]. Une meilleure méthode [82, 11] consiste à réécrire l'équation linéaire comme système de premier ordre et de calculer un système fondamental de solutions. Les deux approches permettent la résolution d'une équation différentielle ordinaire en temps .

Une autre idée pour la résolution d'équations implicites dans les séries est d'utiliser une variante de l'équation elle-même pour le calcul des coefficients. Par exemple, l'équation peut se réécrire , après quoi on obtient la relation de récurrence

pour les coefficients de . Le problème de cette stratégie est que le -ième terme du produit doit être disponible dès que les premiers termes de et le sont. Par conséquent, on ne peut plus recourir à des algorithmes asymptotiquement efficaces pour multiplier des séries tronquées.

Supposons toujours que l'on veut calculer le produit avec la contrainte que doivent être disponibles dès que et le sont. Dans [97, 107, 109, 122], nous avons introduit plusieurs algorithmes efficaces pour ce problème de multiplication détendue. L'idée majeure derrière ces algorithmes est d'anticiper le calcul des coefficients ultérieurs à l'étape . Nous avons illustré cette idée pour l'algorithme de [97, 107]. Dans la figure 5.1, la contribution de chaque carré au produit est calculée par un algorithme de multiplication rapide. Par exemple, à l'étape , lorsque et sont connus, le carré avec un dedans correspond au calcul de la contribution de . Une analyse de complexité conduit à l'estimation

(5.15)

Dans le cas où admet suffisamment de racines -ièmes d'unité, le meilleur algorithme de multiplication détendue actuel [122] admet une complexité

(5.16)

Par ailleurs, les algorithmes [15] pour la composition et l'inversion de séries formelles peuvent également être rendus détendus [107], conduisant à des algorithmes en temps . On peut améliorer cette complexité jusqu'à dans le cas d'une post-composition avec une fonction algébrique.

Figure 5.1. Illustration de l'algorithme rapide pour la multiplication détendue.

Dans les cas où l'on peut utiliser à la fois la méthode de Newton et la méthode détendue, il est intéressant de faire une comparaison plus détaillée. Le cas le plus important est la résolution d'équations différentielles ordinaires (seule la méthode détendue continue à marcher pour les équations aux dérivées partielles). Or, bien que la méthode de Newton en )) est théoriquement la plus efficace, sa complexité cache un facteur constant plus important et une dépendance moins bonne par rapport aux paramètres de l'équation, comme l'ordre . En effet, la complexité de la méthode de Brent et Kung dépend exponentiellement de . Même dans le cas de [82, 11], trouver une solution particulière de

conduit essentiellement à trouver une base de solutions et à perdre l'aspect creux de l'équation. Toutefois, dans [115], nous avons proposé quelques optimisations, qui permettent de réduire ces inconvénients. Dans le tableau 5.2, nous avons résumé l'état actuel des connaissances dans le cas d'un système d'équations linéaires.

Résolution d'un système -dimensionnel d'équations différentielles linéaires Algorithme Système fondamental Une solution Détendu [82] [115]

Tableau 5.2. Complexités pour la résolution d'un système -dimensionnel à l'ordre avec une condition initiale donnée. Le paramètre désigne le nombre de coefficients non nuls dans (on a toujours ). On suppose des coefficients flottants (longs ou pas) et .

6 – Théorie de Galois différentielle

Dans ce chapitre, nous présentons deux algorithmes pour la factorisation d'un opérateur différentiel linéaire à coefficients dans et le calcul de son groupe de Galois différentiel [118]. Le deuxième algorithme exige de calculer avec une précision suffisante (dont nous sommes à présent incapable de décider quand elle est atteinte).

Nos algorithmes introduisent de l'analyse dans des problèmes qui sont classiquement du ressort de techniques purement algébriques du calcul formel [89, 87, 68, 125, 126, 127, 21, 124]. Par ailleurs, notre façon de calculer avec des groupes algébriques diffère de la façon habituelle de faire en calcul formel : plutôt que de calculer avec les équations du groupe [30, 32], nous calculerons directement avec la variété.

Même s'il est tout à fait concevable que l'on puisse faire autrement, notre exemple met en lumière une philosophie plus générale :

1. L'analyse effective peut résoudre ou aider à résoudre plus efficacement des problèmes de nature algébrique en apparence (et vice versa). Il est grand temps que le status quo (considérer des méthodes numériques comme taboues et/ou manquer de courage pour implanter de tels algorithmes) soit dépassé.

2. Faire attention à ne jamais perdre la signification géométrique des objets avec lesquels on calcule : la manipulation d'équations par des techniques éprouvées (bases de Groebner, algèbre différentielle) n'est pas l'alpha et l'oméga du calcul formel.

6.1.Rappels

Soit un sous-corps algébriquement clos de et . Considérons un opérateur différentiel linéaire monique . Nous noterons par l'ensemble fini des singularités de (dans le cas de , on considère la transformation ). Une extension de Picard-Vessiot de est un corps différentiel tel que

PV1

est généré différentiellement par et un système fondamental de solutions à .

PV2

admet comme corps de constantes.

En prenant un système fondamental canonique de solutions dans un point non-singulier (ou singulier ; voir par exemple la section 5.4), on construit une extension de Picard-Vessiot.

Soit une extension de Picard-Vessiot de avec comme dans PV1. Le groupe de Galois différentiel de l'extension est le groupe des automorphismes différentiels qui laissent invariant point par point. Il est classique [59] que est indépendant (à isomorphisme près) du choix particulier de l'extension de Picard-Vessiot . Étant donné un automorphisme , toute solution de est envoyée vers une autre solution. En particulier, induit une matrice ) dans la base , conduisant à une présentation de dans ). On vérifie que est un groupe algébrique de matrices, fermé pour la topologie de Zariski. Par ailleurs, pour toute extension des scalaires.

La théorie de Galois différentielle admet de nombreuses analogies avec la théorie de Galois classique [53, 59, 124]. D'une part, il existe une contre-partie différentielle de la correspondance de Galois. Par ailleurs, les relations remarquables entre les solutions et l'existence de solutions d'un certain type peuvent se lire sur le groupe de Galois. Par exemple, l'existence de solutions Liouvilliennes est équivalente à l'existence d'une base dans laquelle est triangulaire. De même, l'existence d'une factorisation de est équivalente à l'existence d'un sous-espace invariant non trivial sous l'action de .

La théorie d'accéléro-sommation d'Écalle permet d'établir un lien entre la théorie de Galois différentielle et l'analyse. En effet, le théorème de densité de Martinet-Ramis [64] affirme que est engendré par les matrices de monodromie autour des singularités de , combinées avec les groupes exponentiels locaux, ainsi que les matrices de Stokes. Dans le cas Fuchsien, ce résultat est du à Schlesinger [77, 78]. Les algorithmes dans ce chapitre s'appuient sur notre version effective du théorème de densité :

Théorème 6.1. (Théorème effectif de densité). Il existe un algorithme qui prend en entrée, et qui calcule un nombre fini de matrices , tel que génère en tant que sous-groupe algébrique fermé de .

Démonstration. Combinaison de [118, Section 2.5] et le Théorème 5.6 (dans le cas où contient des nombres transcendants, le Théorème 5.6 s'applique encore, sauf que les -approximations se calculent en temps ) seulement).

6.2.Factorisation d'opérateurs différentiels

Il est classique que les factorisations de sont en correspondance avec les sous-espaces vectoriels non triviaux sous l'action de :

Proposition 6.2.

Combinant cette proposition avec le théorème 6.1, factoriser équivaut donc à trouver les sous-espaces invariants sous l'action de . Ces espaces sont encore les sous-espaces invariants sous l'action de l'algèbre engendrée par , ce qui réduit leur détermination à un problème d'algèbre linéaire de dimension . Dans [118, Sections 3.2 et 3.3], nous présentons un algorithme un peu plus fin pour la détermination des sous-espaces invariants.

Toutefois, notre présentation a fait abstraction d'un problème important : les entrées des matrices dans étant des constantes transcendantes (holonomes) dans , nous n'avons pas de test d'égalité dans . Par conséquent, l'algorithme pour déterminer les espaces invariants est incomplet : en utilisant une précision et un test heuristique d'égalité pour la précision , l'algorithme permet de démontrer la non-existence de sous-espaces invariants, mais pas leur existence éventuelle. Toutefois, on sait que l'algorithme est correct à partir d'une précision suffisamment grande , dont nous ignorons la valeur.

Heureusement, il existe un remède à ce problème épineux dans le cas de la factorisation : si on pense avoir trouvé un sous-espace invariant , alors la proposition 6.2 permet de trouver un candidat pour le facteur droit (ceci fait intervenir plusieurs techniques non-triviales, mais classiques, pour reconstruire les coefficients de à partir de — notamment l'algorithme LLL [61] et les approximations de Padé). En utilisant une division dans l'anneau , on peut enfin tester si le candidat facteur est effectivement un facteur de . Pour une précision suffisante, on obtiendra ainsi un véritable facteur, ou une preuve qu'un tel facteur n'existe pas.

Théorème 6.3. Soit un corps algébriquement clos effectif avec un test effectif de nullité. Alors il existe un algorithme de factorisation dans .

Remarque 6.4. L'intérêt de notre méthode réside dans sa bonne complexité potentielle : si la précision nécessaire pour obtenir une réponse reste petite, et si l'étape de reconstruction peut se faire vite, alors l'algorithme est essentiellement polynomial. Par ailleurs, la méthode permet de traiter aussi bien le cas où ou , bien que certains calculs sont plus rapides dans le cas algébrique (l'évaluation des fonctions et la phase de reconstruction par l'algorithme LLL).

6.3.Calcul du groupe de Galois différentiel

Un deuxième problème intéressant est le calcul explicite du groupe de Galois différentiel. En vertu du théorème 6.1, il suffit de pouvoir déterminer le plus petit sous-groupe algébrique engendré par un ensemble fini de matrices . À cause du problème des tests de nullité, nos algorithmes ne fonctionneront que pour une précision suffisante, que nous ne savons pas déterminer.

Plus généralement, le calcul de fait partie d'un programme pour calculer avec les groupes algébriques fermés de . Ceci comprend entre autres les problèmes suivants :

GA1

Passage de la composante connexe à l'algèbre de Lie et vice versa.

GA2

Test d'appartenance .

GA3

Calcul du groupe algébrique fermé engendré par .

GA4

Passage de aux invariants sous l'action de .

GA5

Identification de dans une classification des groupes algébriques.

La résolution de ces problèmes dépend fortement de la façon de représenter . Dans notre papier [118], nous travaillons systématiquement avec la décomposition

(6.1)

en produit de la composante connexe et d'un groupe fini modulo . En représentant l'algèbre de Lie par une base finie, tous les calculs avec la composante connexe se ramènent à de l'algèbre linéaire. Par ailleurs, il est théoriquement possible d'énumérer , ce qui rend les calculs concernant essentiellement triviaux.

Notre représentation admet l'avantage que GA1 est résolue par définition. La question GA2 est traitée dans [118, Section 4.4]. La question GA3 est classique [118, Sections 4.2 et 4.3] dans le cas d'une matrice et se réduit à de l'algèbre linéaire et GA2 dans le cas général. En utilisant une variante [118, Lemme 3] d'un résultat de Dixon [33, Théorème 9.2] pour des besoins de terminaison, ceci conduit au résultat suivant :

Théorème 6.5. [118] Il existe un algorithme qui prend un ensemble fini en entrée et qui, sous l'hypothèse de calculer avec une précision suffisante, retourne le plus petit sous-groupe algébrique fermé engendré par .

On peut également choisir de représenter par un système d'équations polynomiales. Dans ce cas, le problème GA2 devient trivial, il y a un travail à faire au niveau de GA1 [27] et GA3 se résout par des techniques de bases de Groebner [32]. En revanche, cette représentation est moins compacte, à la fois pour la composante connexe et la partie finie. En particulier, un groupe comme devient très désagréable à représenter, si on a fait un mauvais choix de coordonnées.

Bien sûr, le groupe est également trop grand pour être énuméré. Toutefois, en s'inspirant d'algorithmes classiques pour calculer avec des groupes finis [85, 86], on peut améliorer la façon de calculer avec le groupe fini modulo [118, Sections 4.6 et 4.7]. L'idée principale est de se ramener au cas où et d'observer qu'il existe des éléments dans qui sont proches de l'identité modulo , lorsque est grand. Ces éléments se comportent en réalité comme des générateurs infinitésimaux d'une composante continue. L'élément le plus proche de l'identité commute avec tous les autres modulo et en le remplaçant par un nouveau générateur infinitésimal dans , on obtient un groupe algébrique très similaire à , mais dont la partie discrète est plus petit. Par récurrence, on se ramène ainsi à un groupe fini de taille plus raisonnable. D'un point de vue effectif, on peut trouver les éléments proche de l'identité par une variante non commutative de l'algorithme LLL.

Remarque 6.6. En rédigeant ce rapport, on a retrouvé un théorème de Jordan [124, Section 4.3], dont une des conséquences semble être la suivante : il existe une constante qui ne dépend que de la dimension , telle que pour tout sous-groupe algébrique fermé de , il existe un sous-groupe distingué tel que soit commutatif et . Ce résultat permet de simplifier un peu plus [118, Sections 4.6 et 4.7]. On peut aussi espérer en déduire des équations creuses de taille raisonnable pour en tant que variété ou encore rendre effectif le théorème de Chevalley avec une complexité raisonnable.

6.4.Perspectives

En réalité, les algorithmes de ce chapitre soulèvent tout autant de questions qu'ils apportent de réponses. Avant tout, il serait intéressant de pouvoir enlever l'hypothèse sur la précision du théorème 6.5, en trouvant une condition d'arrêt pour tester si le « candidat à la précision » pour le groupe est correct, comme nous l'avions fait dans le cas de la factorisation. Cette fois-ci, les deux directions et posent des difficultés. Voici quelques pistes :

1. Trouver les invariants de [30, 52] et vérifier qu'elles soient effectivement vérifiées par un système fondamental de solutions, ou rendre effectif le théorème de Chevalley en étant guidé par .

2. Supposant , se débarrasser des constantes transcendantes en quotientant le prolongement analytique d'un système fondamental de solutions , disons en , par l'action de . En effet, étant donné un petit , le théorème des jauges [124] entraîne l'existence d'un point algébrique dans l'orbite (communication privée par M. Singer et G. Duval). On peut aussi examiner si, après application d'une transformation de jauge au système original, on peut tester plus directement si .

3. Borner le nombre de composantes connexes de comme dans [31, Section 3.2].

D'autres problèmes intéressants concernent les changements de représentation et en particulier la reconstruction des équations à partir d'une variété. Il devrait aussi être aisé d'étendre les techniques de la section 6.2 à toute une série de problèmes plus spécifiques, comme la détermination de solutions Liouvilliennes, décider si est diagonalisable ou si est commutatif, etc.

Enfin, on peut chercher à encoder des familles entières d'opérateurs ou systèmes différentiels à l'aide de séries non commutatives (comme pour les polylogarithmes), et voir dans quel mesure on peut obtenir des informations sur toute la famille, au lieu de faire une étude au cas par cas.

Conclusion

L'« algèbre différentielle ordonnée » ou « asymptotique » concerne les théories obtenues à partir de l'algèbre différentielle en rajoutant une relation ou . L'étude des différents types de corps de transséries, qui fournissent des modèles particulièrement riches, nous a permis de développer les résultats de base pour ce genre de théories. Nos méthodes ont l'avantage de se généraliser à des équations différentielles de composition souvent difficiles à apprivoiser par d'autres moyens.

Par ailleurs, nous sommes parvenu à relier la théorie purement formelle des transséries à l'analyse, même si un traitement par accéléro-sommation aurait sans doute été préférable à notre méthode moins constructive, basée sur des extensions successives de corps de Hardy transsériels. Au moins en ce qui concerne les solutions d'équations différentielles algébriques, on peut donc estimer que nous avons poursuivi aussi loin que possible le programme de Hardy pour formaliser le calcul asymptotique et classer les ordres de croissance à l'infini.

Toutefois, l'exigence de compatibilité entre la dérivation et la relation de dominance asymptotique exclut des équations aussi simples que du champ d'applications de la théorie. Prévoir le comportement d'un système dynamique arbitraire à l'infini nécessite d'autres outils, comme la désingularisation de champs de vecteurs, l'analyse en fréquence, etc.

Il est encore un peu tôt pour faire un bilan de notre projet de concevoir un système de calcul analytique. Nous espérons toutefois être parvenu à montrer que ce projet commence à être maîtrisé au niveau théorique, qu'une panoplie d'algorithmes concrets et de bonne complexité attendent d'être implantés, et qu'un tel système pourrait rendre des services à autre chose que lui-même. Il est donc grand temps de passer aux implantations.

Une dernière question pourra encore intriguer le lecteur : quel est le rapport entre les deux parties de ce mémoire ? En réalité, nous prévoyons des liens assez profonds : les fonctions analytiques étant très rigides, l'essentiel de leur comportement est concentré dans leurs singularités. Toutefois, avant de s'intéresser aux singularités, il nous a d'abord fallu maîtriser un certain nombre de techniques plus élémentaires concernant l'analyse complexe effective. La route pour combiner les deux parties est désormais ouverte ; voir [94, 111] pour quelques premiers résultats.

Bibliographie