Speaker
Mr
Alin Bostan
(INRIA Saclay)
Description
Si une suite de nombres rationnels est donnée par une récurrence linéaire à coefficients polynomiaux et suffisamment de termes initiaux, il est naturel de
s'intéresser à la transcendance de la série génératrice associée. Plusieurs
critères de transcendance existent, mais aucun ne permet de couvrir tous les
cas. En outre, il existe des exemples concrets venant d'applications où aucun
critère ne s'applique. Se pose ainsi la question de l'existence d'un
algorithme permettant de prouver la transcendance d'une série formelle
différentiellement finie, c'est-à-dire vérifiant une équation différentielle
linéaire à coefficients polynomiaux. Le problème est non-trivial même lorsque
la récurrence est de premier ordre. Un algorithme dû à Michael Singer suffit,
en principe, à traiter le cas général. Toutefois, l'algorithme a une
complexité trop élevée pour être efficace en pratique. Nous présenterons une
nouvelle méthode que nous avons utilisée pour prouver la transcendance de
plusieurs séries génératrices provenant de la combinatoire énumérative. Le
nouvel algorithme repose sur le calcul d'une équation différentielle d'ordre
minimal, via des bornes obtenues par l'analyse des possibles singularités apparentes. On ramène ainsi la question de la transcendance à un problème d'algèbre linéaire structurée.