Le Calcul formel vise à algorithmiser le calcul sur des représentations finies d’objets mathématiques. Calculer, c’est en fait construire une telle représentation, en respectant une mécanique fixée à l’avance et uniforme sur toute une classe d’objets. Au contraire des objets des mathématiques traditionnelles qui existent « en soi », un objet du calcul formel n’a d’existence que par sa représentation. La notion d’égalité ne peut donc plus être la même notion que celle des mathématiques traditionnelles. Pour affirmer l’égalité de deux objets, le calcul formel doit au contraire établir l’identité de leurs représentations, ou encore montrer qu’ils peuvent être obtenus par une même construction. Le calcul revêt alors une importance de premier plan. Ce n’est plus une activité triviale ; par le biais de l’algorithmisation, il acquiert un statut de preuve.

Une classe d’objets du calcul formel n’est donc vraiment satisfaisante que lorsque l’identité de deux de ses membres y est décidable algorithmiquement. Dans cette perspective, l’objectif de ma thèse est l’introduction dans le calcul formel de nouvelles classes de suites et fonctions qui sont solutions de systèmes d’équations fonctionnelles linéaires et le développement d’une algorithmique effective correspondante, rendant le test d’égalité et les propriétés essentielles de ces classes décidables. Dans cette thèse, je fais en particulier l’étude algorithmique de classes de fonctions et de suites qui sont solutions d’équations aux dérivées partielles linéaires ou de récurrences multiples linéaires, et qui vérifient certaines propriétés de finitude. Cet objectif va de pair avec l’implantation des algorithmes découverts, permettant leur validation et la mise en lumière de leurs faiblesses et de leurs forces.

De nombreuses fonctions issues de la physique mathématique et des sciences de l’ingénieur ainsi que de nombreuses suites apparaissant en analyse de performances d’algorithmes, en mathématiques discrètes et en combinatoire sont régies par des équations différentielles ou des équations de récurrence linéaires à coefficients polynomiaux. Un cadre mathématique adapté à l’étude de ces objets est celui des fonctions holonomes. Au début des années 1990, Doron Zeilberger a montré l’intérêt de cette classe de fonctions pour le calcul formel [113] : de nombreux calculs sur les fonctions spéciales, les suites combinatoires ou leurs q-analogues peuvent se réaliser par l’utilisation d’opérateurs linéaires et d’arguments simples sur la dimension d’espaces vectoriels adéquats ; de façon plus frappante, des méthodes d’élimination polynomiale dans un cadre non commutatif m’ont permis d’incorporer dans ce calcul une algorithmique de sommation et d’intégration symboliques, fondée sur une représentation finie et exacte.

Le cadre holonome et la sommation hypergéométrique définie. L’approche que Doron Zeilberger a introduite au début des années 1990 pour le calcul sur les fonctions et les suites qu’il a appelées « holonomes » procède de la théorie des D modules . Dans cette théorie, une équation différentielle linéaire est vue comme un module sur une algèbre d’opérateurs différentiels linéaires. Cette approche remonte aux travaux de Bernard Malgrange sur les équations différentielles linéaires à coefficients constants et a été ensuite systématisée dans la thèse de Masaki Kashiwara pour le cas d’équations à coefficients analytiques. La théorie de l’holonomie est une branche de la théorie des D-modules dont l’étude a débuté dans les années 1970 par les travaux de Joseph Bernstein .

Dans son article fondateur [113] de la méthode holonome pour la sommation et l’intégration symboliques, Zeilberger étudie l’action de certaines algèbres d’opérateurs linéaires différentiels ou aux différences afin de déterminer des opérateurs particuliers qui caractérisent la somme ou l’intégrale à calculer. Là encore, une équation linéaire différentielle ou aux différences peut être vue comme un module sur une algèbre d’opérateurs linéaires respectivement différentiels ou aux différences. Une définition simple (mais incomplète) de l’holonomie dans les cas continu et discret est la suivante : une fonction f(x1, . . . , xr) est holonome lorsque ses dérivées engendrent un espace vectoriel de dimension finie sur le corps des fractions rationnelles en les xi ; une suite est alors définie comme étant holonome lorsque sa série génératrice en plusieurs variables est holonome. Selon l’usage de Zeilberger, j’emploie dans cette thèse l’expression « fonction holonome » pour faire référence à chacun de ces cas.

Analogie avec les nombres algébriques. En suivant l’approche proposée par Zeilberger, au lieu de chercher à résoudre une équation fonctionnelle linéaire, je m’intéresse à manipuler ses solutions. Pour bien marquer cette différence de point de vue entre des méthodes du type recherche de formes closes et les méthodes de calculs à la Zeilberger, procédons à une analogie avec les nombres et fonctions algébriques. On distingue deux types de calculs :
(1) la manipulation de nombres et fonctions algébriques, et plus généralement de zéros de systèmes algébriques ;
(2) la résolution par radicaux d’équations ou de systèmes algébriques. Dans le premier cas, le point de vue adopté est de manipuler ensemble toutes les solutions d’un système au moyen d’un zéro générique. Les calculs s’interprètent alors comme des opérations sur des variétés algébriques. Dans le cadre de la géométrie algébrique, des outils puissants d’élimination ont été développés, au nombre desquels le résultant et les bases de Gröbner.

D’un autre point de vue, la résolution par radicaux vise à déterminer si un nombre algébrique admet une forme close dans une tour d’extensions de corps de nombres vérifiant une certaine condition technique, et la théorie adaptée est la théorie de Galois. En ce qui concerne les fonctions et suites, la similitude formelle est frappante. En effet, on distingue respectivement :
(1) la manipulation de fonctions et suites solutions de systèmes d’équations linéaires fonctionnelles ;
(2) la résolution des équations différentielles linéaires ordinaires en solutions liouvilliennes et plus récemment celle des équations de récurrence linéaires ordinaires.

Dans le cadre différentiel, la résolution en solutions liouvilliennes consiste à déterminer si une solution existe dans une tour d’extensions de corps de fonctions stables par dérivation et vérifiant une condition technique formellement semblable au cas de la résolution par radicaux. Une théorie de Galois différentielle, puis une théorie de Galois aux différences ont d’ailleurs été développées en s’inspirant du cas classique, mais en l’étendant de manière non triviale. Concernant la manipulation de fonctions et suites, le même point de vue de « géométrie algébrique non commutative » et les mêmes outils d’élimination ont été développés pour le calcul sur des solutions génériques d’équations fonctionnelles linéaires. En particulier, on retrouve une théorie des bases de Gröbner non commutatives dont je ferai constamment usage dans cette thèse .

Pour finir avec cette analogie, de même que la manipulation d’expressions faisant intervenir des radicaux peut être vue comme le calcul sur des fonctions algébriques en tenant compte d’une information numérique — les conditions initiales — pour permettre les choix de branches, la manipulation d’expressions en des suites et fonctions spéciales peut être vue comme un calcul sur des solutions génériques de systèmes fonctionnels linéaires qui tiennent compte de conditions initiales — le plus souvent sous forme numérique — pour distinguer entre les solutions concrètes.

Un carrefour de domaines. Le sujet de mon étude est à un carrefour de domaines, à l’intérieur et à l’extérieur du calcul formel. En premier lieu, la combinatoire et l’analyse d’algorithmes, car un grand nombre de problèmes issus de ces domaines mettent en jeu des récurrences holonomes [48, 47, 49, 93]. C’est le cas par exemple dans l’analyse de certaines structures de données, comme les arbres de recherche récursifs multidimensionnels. D’autre part, nombre d’identités sur les coefficients binomiaux qui sont habituellement démontrées péniblement à la main deviennent prouvables automatiquement [84]. Par ailleurs, la théorie des fonctions spéciales, en particulier celle des fonctions hypergéométriques, et le calcul déjà mentionné d’intégrales ou de sommes relèvent de la théorie de l’holonomie. Mentionnons encore le q-calcul, qui ouvre les portes de la combinatoire des partitions et de certaines parties de la physique statistique [13]. Enfin, ma thèse comporte un important travail d’implantation, car les algorithmes, mêmes élémentaires, nécessaires à la manipulation d’opérateurs différentiels et de récurrence n’étaient en général pas disponibles dans un langage de haut niveau tel que Maple il y a encore peu.