Nicolas M. THIÉRY Né le 28 mai 1973 à Paris XV^e (35 ans) Nationalité Française; dégagé des obligations militaires IUT d’Orsay, Plateau de Moulon, 91400 ORSAY Mél: nthiery@users.sourceforge.net (1), Web: http://Nicolas.Thiery.name/ ----------------------------------- (1) mailto:nthiery@users.sourceforge.net Études et fonctions *=*=*=*=*=*=*=*=*=*= Septembre 2008-Mars 2009 Délégation CNRS à l’Institut Gaspard Monge (1) (Marne-la-vallée) 2007-2008 Chercheur au Département de Mathématiques de l’Univ. de Californie à Davis (Détachement sur bourse NSF) 2004- Maître de conférence (section 25), Institut Universitaire de Technologie d’Orsay (2); Laboratoire de Mathématiques d’Orsay (3), Université Paris Sud (4); Février 2004-Juin 2004 Architecte Développeur Senior au département Sécurité d’IDEALX (5); Janvier 2001-Août 2004 Maître de conférence (section 27), Univ. Claude Bernard Lyon I (6) ; Titulaire depuis le 1er janvier 2002; membre associé de l’IGM (7) (Univ. Marne-la-vallée); Janvier 2000 Qualification dans les sections 25, 26 et 27 du CNU; 1999-2000 Enseignant-chercheur, Colorado School of Mines (8) (USA); (Coopérant du Service National) 1999 Thèse de mathématique-informatique, soutenue le 15 juin à l’UCBL (9) ; Sujet: Invariants algébriques de graphes et reconstruction, une étude expérimentale; Directeur: Maurice Pouzet (Univ. Claude Bernard Lyon I (10) ); Rapporteurs: Adriano Garsia (San Diego, California) et William Kocay (Winnipeg, Manitoba); Jury: Adrian Bondy (UCBL (11) ), Marc Giusti (École Polytechnique (12) ), Michel Habib (Univ. Montpellier), Daniel Krob (Univ. Paris VII) et Maurice Pouzet (UCBL (13) ). 1997 Agrégation de Mathématiques, option informatique (135^e ); 1996-1999 Allocataire Moniteur en informatique, UCBL (14) ; 1994 DEA IMA (Informatique et Mathématiques Appliquées) X (15) -ENS (16) ; 1993 Licence de Mathématiques, Maîtrise d’Informatique; 1992-1996 Élève à l’École Normale Supérieure (17) , Paris. Publications *=*=*=*=*=*= Articles dans des revues d’audience internationale avec comité de ==================================================================== rédaction =========== [unsrturl] [isil] Articles dans des actes de conférences internationales avec comité de ======================================================================= rédaction =========== [unsrturl] [isil] Articles soumis ================ [unsrturl] [isil] Thèse de doctorat et communications ===================================== [unsrturl] [isil] Invitations à des conférences *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= 1. AMS special session on Algebraic Combinatorics Claremont, California, USA, Mai 2008; 2. SAGE days 2007 (18), Los Angeles, USA, Février 2008; 3. AMS Joint Mathematics Meeting, Special Session on Applications of Computer Algebra in Enumerative and Algebraic Combinatorics , San Diego, USA, Janvier 2008; 4. Axiom Workshop 2007, RISC, Linz, Austria, Juin 2007; 5. Axiom Workshop 2006, RISC, Linz, Austria, Avril 2006; 6. Modular Invariants and Representations of Finite Groups: Theory and Computation, Canterbury (UK), septembre 2003; 7. Journées du LIPN, Combinatoire, Informatique et Physique (19), Villetaneuse, 2003; 8. Workshop on Invariant Theory, Kingston (Canada), 2002; Développement logiciel *=*=*=*=*=*=*=*=*=*=*=* - MuPAD-Combinat (20) (http://mupad-combinat.sourceforge.net): Je coordonne depuis sa création en décembre 2000 le développement de la bibliothèque officielle de combinatoire du système de calcul formel MuPAD (21) . Environ 130000 lignes, 600 pages de doc et une dizaine de contributeurs réguliers (IGM, Marne-la-vallée; LIFAR, Rouen; LAPCS (22) , Lyon; UPC Barcelone; Orsay; UC Davis; Toronto). Cette bibliothèque intègre les logiciels mu-EC (23)(IGM), CS (24)(INRIA, Nancy; LaBRI, Bordeaux; LRI, Orsay), Symmetrica (Bayreuth) et lrcalc (Rutgers, USA), Nauty (Canberra, Autralia). L’objectif est de fournir une plateforme de développement libre (licence LGPL) pour la combinatoire algébrique, en favorisant les contributions extérieures, et en réutilisant autant que possible des codes existants. Son utilisation a joué un rôle essentiel dans une cinquantaine de publications. Participation aux tâches collectives *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* - Organisateur des journées portes ouvertes de l’IUT d’Orsay, 4 Mars 2006 et 10 mars 2007; - Membre de la pré-commission de recrutement maître de conférences de l’IUT d’Orsay, 2006; - Coorganisateur de trois rencontres de développeurs de MuPAD-Combinat (25) juin 2004, juin et septembre 2007; - Président de jury de bac, session 2003, Vaux-en-Vellin; - Organisateur local de l’atelier Workshop on Open Source Computer Algebra (26) qui a réuni une cinquantaine de chercheurs et d’enseignants de sept pays différents à Lyon, du 21 au 23 mai 2002; - Organisateur du Workshop on Computational Invariant Theory of Permutation Groups and Applications (27), à Foljuif (sud de Paris) du 13 au 15 juin 2001; cet atelier a réuni une douzaine de chercheurs et de doctorants, originaires de six pays différents; - Webmestre et administrateur système du Laboratoire de Probabilités, Combinatoire et Statistiques (28) (UCBL (29) ) depuis mi-1997 (installation et maintenance de 40 postes sous UNIX: GNU/Linux, HP et Terminaux X); - Administrateur système du département de mathématiques et d’informatique de la Colorado School of Mines (30) , 1999-2000 (installation et maintenance de 25 postes sous UNIX: GNU/Linux); - Webmestre et co-administrateur-système élève à l’ENS (31) , 1993-1999 (UNIX: SunOS/Solaris). Séjours à l’étranger et dans l’industrie *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* 2007-2008 Un an à l’Université de Californie à Davis (USA) 2006 Un mois à l’UCSD (32) (San Diego, USA), avec A. Garsia; 2004 Quatre mois en tant qu’Architecte Développeur Sénior du département Sécurité d’IDEALX (http://www.idealx.com/): gestion de montée en charge et tests fonctionnels pour l’Infrastructure à Clef Publique IDX-PKI (logiciel libre en Perl/PHP); 1999-2000 Seize mois au Département de Mathématiques et d’Informatique de la Colorado School of Mines (Golden, Colorado). Enseignement (environ 1800 heures équivalent TD) *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= - Maître de conférence à l’ IUT d’Orsay (automne 2004-2007): L1: Calcul formel pour les Maths (Cours et TP), Projet Professionnel Personnalisé, Projets Tuteurés, L2: Maths, Algo et Langage C++, Java (TD); Recherche Opérationnelle (Cours et TD), M1: responsable de l’option Algèbre et Calcul Formel de la préparation à l’agrégation d’Orsay. - Intervenant chez Orsys (33), 2005-2006. Trois formations de 4 jours «Linux, Mise en Oeuvre»; - Maître de conférence à l’Univ. Claude Bernard Lyon I (34) (printemps 2001-2004): Recherche opérationnelle, Maîtrise de Maths et d’Ingénierie Mathématique (Cours, TD et TP, 3×80h), Optimisation discrète, Licence de Maths (TD, 2×27h); Remise à niveau informatique, Utilisation de l’outil informatique, Systèmes et réseaux informatiques, responsable de la thématique informatique du DESS SITN (35) (Cours, TD et TP, 3×90h), C++ 1ère Année, Filière Ingénieur 2000, Université de Marne-la-Vallée (TP, 20h); - Enseignant à la Colorado School of Mines (36) , Golden, Colorado (USA) (automne 1999 -2000): Programming concepts, in C++ (Cours et TPs, 50h), Algebraic structures and discrete math (Cours et TD, 3×50h). - Moniteur à l’Univ. Claude Bernard Lyon I (37) (1996-1999): Participation aux oraux blancs du CAPÈS de mathématiques (UCBL (38) , juin 1999), TD de combinatoire, UV d’informatique, DEUG deuxième année (UCBL (39) , 32h, printemps 1998, 20h, printemps 1999), TD d’algèbre et combinatoire, DEUG première année (UCBL (40) , 40h, printemps 1998), Stage d’initiation à Maple, Licence (ENS Lyon (41) , 16h, octobre 1997), TD de Mathématiques, DEUG première année (UCBL (42) , 60h, automne 1996), TP d’Informatique (Turbo-Pascal), DEUG première année (UCBL (43) , 32h, automne 1996). Encadrement d’activités de recherche *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* - Direction de la thèse de Nicolas Borie (automne 2008-) - Encadrement du stage de DEA de Nicolas Borie (printemps 2008) - Participation à deux jurys de thèse (François Descouens, 2007 et Xavier Molinero, 2005); - Encadrement de sept projets tutorés, L1, IUT d’Orsay; - Encadrement de deux TER, M1 de mathématiques, Université Paris Sud - Encadrement de deux TER, Maîtrise MMIM, UCBL (44) . - Encadrement de deux projets logiciel longs, L3, Colorado School of Mines. Langues Anglais: courant; Allemand: lu-écrit . Rapport de recherche *=*=*=*=*=*=*=*=*=*= Mon domaine de recherche est la combinatoire algébrique, dont le but est d’étudier les objets ayant des interprétations à la fois combinatoires et algébriques; ainsi par exemple la cardinalité d’un ensemble ou la dimension d’un espace vectoriel. Dans certains cas, l’interprétation combinatoire permet d’obtenir des informations algébriques, et réciproquement. La combinatoire algébrique existe implicitement au moins depuis Euler (en particulier dans ses travaux sur les partitions), mais ce n’est qu’à partir des années 60 que ses fondations ont été établies systématiquement, et elle connaît depuis une forte expansion. Plus spécifiquement, je cherche à établir de nouveaux liens entre la théorie des invariants, la théorie des fonctions symétriques et leurs nombreuses généralisations (algèbres de Hopf combinatoires), la théorie des représentations des tours d’algèbres, et la théorie des relations. La combinatoire y est plus souvent un outil pour comprendre des objets algébriques, et en ce sens, il s’agit plutôt d’algèbre combinatoire. J’utilise aussi de manière essentielle l’exploration informatique, typiquement via le calcul formel; aussi, les aspects algorithmiques et effectifs me tiennent particulièrement à coeur. Isomorphisme et de graphes et théorie des invariants ===================================================== J’ai effectué ma thèse au Laboratoire de Probabilités, Combinatoire et Statistiques (45) (Univ. Claude Bernard Lyon I (46) ) sous la direction de M. Pouzet. J’y ai étudié des problèmes d’isomorphie et de reconstruction de graphes au moyen de la théorie des invariants, et d’une utilisation intensive du calcul formel [, ]. La problématique et mes résultats font l’objet de quelques pages dans []. Ceci m’a amené à développer des outils (bibliothèque PerMuVAR (47) pour MuPAD (48) ) pour étudier les invariants de groupes de permutations et à m’intéresser aux aspects effectifs et aux applications de la théorie des invariants. D’une part j’ai mis au point un nouvel algorithme de calcul de systèmes générateurs de ces invariants [], basé sur des techniques d’élimination respectant les symétries (bases SAGBI-Gröbner). D’autre part, j’ai obtenu avec S. Thomassé un résultat structurel sur le comportement de ces invariants vis-à-vis de l’élimination [] (sauf cas triviaux, leurs bases SAGBI sont toujours infinies); nous citons un commentaire du référé anonyme: "[this result] has been desired for a while; thus it can be said that this paper closes one of the chapters in the book of invariant theory [...] the proof is very beautiful". J’ai depuis généralisé ce résultat au cas des groupes monomiaux et à de nombreuses algèbres d’age (voir plus loin). J’ai plus récemment repris les notions de reconstructibilité d’invariants de graphes introduites dans ma thèse, et les ai étendu dans le cadre général des invariants de groupes de permutations []; j’ai par exemple donné une caractérisation des cas où ces invariants reconstructibles sont finiment engendrés. Algèbres d’âge de structures relationnelles =============================================== Dans la lignée de ces travaux, j’ai cherché à étendre avec M. Pouzet [] les outils et propriétés des invariants de groupes de permutations (opérateur de symétrisation de Reynolds, génération finie, module de type fini sur les polynômes symétriques voire propriété de Cohen-Macaulay, série de Hilbert rationnelle, base formant un langage rationnel, base SAGBI infinie, ...) dans le contexte bien plus large des algèbres d’âge de structures relationnelles (l’âge d’une structure relationnelle est la collection de ses restrictions finies considérées à isomorphie près, et on s’intéresse à son profil f_n où f_n compte le nombre de telles restrictions de taille n [, Exercise 8 p. 113], []; on peut construire une algèbre commutative graduée connexe dont la base est indexée par cet âge [], de sorte que la série de Hilbert de cet algèbre est la série génératrice associée au profil). Nous avons montré que ce cadre permet de capturer, outre les invariants de groupes de permutations précités, de nombreuses algèbres combinatoires au coeur de travaux récents: en premier plan les polynômes quasi-symétriques qui sont au centre de la théorie des algèbres de Hopf combinatoires [], et de nombreuses variantes comme par exemple les polynômes quasi-symétriques de graphes que j’ai introduits et étudiés en 2004 avec J.-C. Novelli et J.-Y. Thibon []. Mais aussi par exemple l’algèbre des arbres planaires de Gerritzen [, , ]. L’objectif est de mettre à jour des liens entre propriétés combinatoires de la structure relationnelle et propriétés algébriques de l’algèbre. Ainsi, nous avons montré que, lorsque la structure relationnelle admet une décomposition monomorphe finie, l’algèbre se plonge dans les polynômes en un nombre fini de variables (ou un quotient simple de ceux-ci). Cela permet de démontrer en retour que le profil de la relation est toujours une fraction rationnelle; en fait l’âge est un langage rationnel. De plus, l’algèbre est finiment engendrée si et seulement si la décomposition monomorphe est récursivement minimale; dans ce cas, l’algèbre est un module de type fini sur une sous-algèbre jouant un rôle similaire à celle des polynômes symétriques. Les démonstrations reposent essentiellement sur des généralisations des techniques d’algèbres de Stanley-Reisner utilisées dans [] pour étudier les invariants de groupes de permutations. Complexité d’évaluation des fonctions symétriques ====================================================== D’un autre côté, suite à une courte collaboration entre F. Hivert et moi-même d’une part et P. Gaudry (LIX) et É. Schost (STIX) d’autre part, ces derniers ont pu utiliser des algorithmes sur les fonctions symétriques pour accélérer notablement leurs calculs sur les courbes hyper-elliptiques. Cela nous a amené à entreprendre une étude de complexité précise de l’évaluation de polynômes avec symétries dans le modèle SLP (Straight Line Programm) []. Nous avons ainsi montré comment, connaissant le coût d’évaluation d’un polynôme symétrique P(x_1,...,x_n) décrit par un SLP, on peut donner le coût d’évaluation de P en fonction des valeurs des n fonctions symétriques élémentaires en ces variables. La même technique permet d’obtenir le coût d’évaluation des coefficients de la décomposition d’un polynôme P dans une base des polynômes sur les polynômes symétriques (Schur-Schubert, ...). Algèbres de Hopf combinatoires =============================== Je collabore depuis 2001 avec l’équipe de combinatoire algébrique de l’Institut Gaspard-Monge de l’Université de Marne-la-Vallée. J’ai commencé par étudier avec F. Hivert une conjecture de R. M. W. Wood venant de la topologie algébrique. Cette conjecture met en parallèle certaines propriétés de l’algèbre de Steenrod S en caractéristique zéro, vue comme algèbre d’opérateurs non commutatifs sur les polynômes, avec les propriétés bien connues de l’algèbre des fonctions symétriques classiques []. Pour être spécifique, R. M. W. Wood conjecture [] que le quotient H_n:=Q[x_1,...,x_n]/S.Q[x_1,...,x_n] des polynômes par l’image de l’action de l’algèbre de Steenrod est une représentation régulière du groupe symétrique S_n. Cela suggère l’utilisation de techniques de combinatoire algébrique pour étudier l’algèbre de Steenrod. Par exemple, on peut donner une réalisation de H_n comme ensemble des polynômes harmoniques, solution d’un système de deux équations différentielles linéaires symétriques. Nous avons déjà publié ensemble des résultats partiels très encourageants, qui ouvrent de nouvelles perspectives []. Cette conjecture de R. M. W. Wood n’est pas un épiphénomène isolé, bien au contraire. Elle est fortement liée à toute une mouvance de problèmes où interviennent des polynômes harmoniques, problèmes que j’avais déjà rencontrés lors de mes travaux sur les algèbres d’invariants de groupes de permutations [, , ]. Algèbres de Hopf et représentations de tours d’algèbres ============================================================ Un thème récurrent de l’équipe est l’interprétation des algèbres de Hopf combinatoire comme groupes de Grothendieck des caractères de tour d’algèbres de dimensions finies [, , ]. L’exemple originel, dû à Frobenius est l’algèbre de Hopf des fonctions symétriques (cf [, ]): pour chaque partition lambda de n, la fonction de Schur s_lambda correspond à la représentation irréductible V_lambda du groupe symétrique sigma_n; le produit s_lambdas_µ de deux fonctions de Schur encode la décomposition en irréductibles de la représentation induite sur S_n+m par V_lambda et V_µ; réciproquement, le coproduit encode la restriction des modules irréductibles. Cela donne une interprétation en termes de représentation des coefficients de structures d’une algèbre de Hopf; pour donner un exemple trivial d’application cela peut permettre de prouver que ceux-ci sont positifs. Dans le cas général de tours d’algèbres non-semi-simples, il faut distinguer entre les représentations projectives et simples, ce qui donne en fait une paire d’algèbres en dualité. Ainsi, le rôle central joué par la paire d’algèbres duales Fonctions Symmétriques Non Commutatives / Fonctions Quasi-symétriques vient en particulier du fait qu’elles encodent la théorie des représentations des algèbres de Iwahori-Hecke dégénérées H_n(0) [] (H_n(q) étant une déformation de l’algèbre du groupe symétrique avec H_n(1) = C[S_n]). Par simple curiosité, nous avions en 2003 construit avec F. Hivert une algèbre d’opérateurs HS_n contenant simultanément S_n et H_n(0), et en fait toutes les H_n(q). Il s’est avéré par la suite que cette algèbre joue un rôle beaucoup plus important que prévu. Tout d’abord, suite à quelques calculs et une recherche dans le Sloane nous avons découvert que sa dimension comptait les paires de permutations n’ayant pas de descentes communes. Toutes nos tentatives de démonstration par règles de redressements sur les générateurs ont été soldées par un échec. En revanche, la démonstration est devenue élémentaire une fois mise à jour une caractérisation intrinsèque de HS_n comme algèbre d’opérateurs préservant certaines symétries (ou certaines anti-symétries). Nous avons ensuite analysé la théorie des représentations de cette tour d’algèbres; cela nous a donné le premier exemple d’anneau de caractères ne donnant pas une algèbre de Hopf, mais seulement une bigèbre (le produit d’induction n’étant pas compatible avec le coproduit de restriction). Pour cette étude, nous disposions depuis peu d’un outil mis au point par F. Hivert calculant automatiquement la théorie des représentations des premiers étages d’une tour d’algèbres. Pour expérimenter, nous avons alors considéré quelques tours d’algèbres jouets comme l’algèbre du monoïde des fonctions (de parking) croissantes. À notre grande surprise, celles-ci se sont naturellement intégrées dans le schéma, nous permettant de définir des représentations de (HS_n)_n et (H_n(q))_n sur les puissances extérieures de la représentation naturelle, et de retrouver comme cas particulier la tour d’algèbres de Temperley-Lieb. Ces résultats sont présentés dans []. Nous avons depuis généralisé la construction de HS_n à n’importe quel groupe de Coxeter fini, et découvert que la théorie des représentation reste essentiellement inchangée: dans tous les cas, elle est Morita-équivalente à celle de l’algèbre des chemins du treillis booléen []. Nous avons aussi résolu par l’affirmative une question d’Arun Ram en démontrant que pour tout groupe de Weyl fini notre algèbre est le quotient naturel de l’algèbre de Hecke affine via son action de niveau zero; cela permet de donner des informations sur les modules simples de cette dernière []; cela fait aussi apparaître un lien, en cours d’étude, avec les polynômes de MacDonald non symmétriques. Nous essayons aussi de généraliser les autres propriétés de HS_n (liens avec les fonctions de parking croissantes, les algèbres de Temperley-Lieb) à d’autres types. Cela a déjà fait apparaître des fonctions de parking croissantes de "type C" dont le monoïde est auto-injectif, ce qui pourrait donner une nouvelle algèbre de Hopf. Algèbres de Kac de dimension finie =================================== Pour terminer, j’ai entamé en 2005 une collaboration avec Marie-Claude David du Laboratoire de Mathématiques d’Orsay, avec laquelle j’étudie des algèbres de Kac de dimension finie. Nous considérons des familles connues d’exemples non triviaux (c’est-à-dire qui ne sont ni des algèbres de groupes, ni leur duales) de dimension 4n, n>=2 obtenus par déformation par un 2-pseudo cocycle soit de l’algèbre du groupe dihédral D_2n, soit du groupe des quaternions. À part en dimension 8 (un exemple) ou 12 (deux exemples), aucun d’entre eux n’a été étudié en profondeur, pour la simple raison que les calculs nécessaires à leur exploration seraient très lourds à la main. En revanche, l’exploration informatique nous a permis de rapidement conjecturer, puis de démontrer, que deux des familles connues étaient en fait isomorphes pour n pair. Nous avons aussi pu obtenir leurs groupes d’automorphismes, et montrer que pour n impair, ces algèbres sont autoduales. Notre objectif principal est de construire, pour des exemples de petite dimension, le treillis des sous-algèbres coidéales (analogue du treillis des sous-groupes d’un groupe), et bien entendu de les généraliser lorsque possible (le treillis complet est maintenant connu pour n premier). L’intérêt est que ce treillis est isomorphe à celui des facteurs intermédiaires de l’inclusion de profondeur 2 obtenue par produit croisé par l’algèbre de Kac. La connaissance du diagramme de Bratelli de la sous-algèbre coidéale dans l’algèbre de Kac renseigne sur le graphe principal d’une inclusion intermédiaire duale. Même à la machine, les calculs sont difficiles et nécessitent à la fois une réflexion algorithmique et une infrastructure d’un haut niveau d’abstraction. De fait, une bonne partie de la démarche pour construire ces treillis est encore très loin d’être automatisée. Un premier article présentant nos résultats est en cours de rédaction. Recherche expérimentale et développement ========================================== Toutes mes recherches ont en commun l’utilisation d’outils informatiques, et notamment du calcul formel, dans des domaines propices aux explosions combinatoires. L’exploration informatique sert de guide, suggérant des conjectures, ou au contraire produisant des contre-exemples. Elle permet d’étudier des exemples suffisamment conséquents pour être représentatifs; ces exemples sont le plus souvent intraitables à la main, et même hors de portée des algorithmes classiques. La difficulté est de trouver les outils mathématiques appropriés pour développer de nouveaux algorithmes, sachant que seule l’efficacité de l’implantation finale décide de la pertinence de ces outils. Bien entendu, mener à bien de tels calculs sous-entend un important travail de programmation, et requiert une large panoplie de techniques (fonctions symétriques, bases de Gröbner et autres techniques d’élimination, algèbre linéaire creuse, groupes et représentations, manipulations de classes combinatoires, séries génératrices, solveurs divers, ...). Lors du développement de PerMuVAR (49) j’ai regretté l’absence d’une plate-forme bien établie pour la recherche en combinatoire algébrique donnant un accès aisé à tous ces outils. Il est à noter qu’une telle plate-forme a vocation à être utilisée dans un cadre beaucoup plus large avec, par exemple, des applications potentielles en théorie des invariants, en physique mathématique (calculs dans les algèbres de Hopf venant des problèmes de renormalisation), opérades, ou en théorie des représentations modulaires des groupes finis. Cela m’a amené à lancer en décembre 2000 le projet MuPAD-Combinat (50) (une bibliothèque sous licence libre de combinatoire algébrique pour le système de calcul formel MuPAD (51) ) dont l’objectif affiché est de fédérer à terme les efforts de développement logiciel dans la communauté de la combinatoire algébrique []. L’important investissement initial que m’a demandé ce projet est en train de porter ces fruits (plus d’une vingtaine de publications en ont déjà bénéficié). L’équipe croît régulièrement (à ce jour une dizaine de contributeurs réguliers) et le projet est en train d’atteindre la masse critique nécessaire pour attirer nouveaux utilisateurs et participants. Ainsi, MuPAD-Combinat (52) a été choisi comme support logiciel pour le projet NSF "Focused Research Group: Affine Schubert Calculus" qui, entre autres, finance mon séjour actuel aux USA. Enfin, pour assurer sa diffusion à grande échelle et sa maintenance sur le long terme, nous collaborons étroitement avec l’équipe de MuPAD (53) (Université de Paderborn / Sciface GmbH); de fait, MuPAD-Combinat (54) est partie intégrante de la bibliothèque de MuPAD (55) depuis 2002. Projet de recherche *=*=*=*=*=*=*=*=*=* Mes recherches m’ont permis d’acquérir une solide expérience interdisciplinaire: combinatoire, algorithmique, combinatoire algébrique, calcul formel, théorie des invariants, représentations de groupes, exploitation des symétries des problèmes (autant d’un point de vue théorique que pour accélérer les calculs), et je souhaite commencer à partager cette expérience avec des étudiants. À court terme, le premier objectif de cette demande de délégation est donc de dégager du temps pour finir mon habilitation pour l’automne 2008. En parallèle, ma présence quotidienne (au lieu d’une fois par semaine) à l’IGM me permettra d’accélérer considérablement les travaux en cours avec l’équipe de combinatoire algébrique. Ainsi, nous venons de découvrir que la tour d’algèbre (HS_n)_n entretenait des liens très étroits avec les travaux récents de J.C. Novelli et J.-Y. Thibon; ils y ont par exemple démontré que l’analyse des représentations de H_n(0) sur les fonctions de parking amenait naturellement à la combinatoire de la formule d’inversion de Lagrange non commutative, et que l’introduction d’analogues non commutatifs de fonctions spéciales telles que les polynômes d’Abel, les séries binomiales de Lambert ou l’exponentielle d’Eisenstein permettait de réobtenir de manière immédiate et unifiée un grand nombre de formules énumératives [, ]. Or, l’algèbre HS_n agit naturellement à gauche sur les fonctions de parking, et surtout sa tour quotient des fonctions de parking croissantes, dans son action à droite, en est exactement le commutant. On peut donc présager qu’il existe des liens étroits, d’un point de vue de la théorie des représentations, entre ces algèbres et les fonctions de parking; cela mènera très certainement à des développements parallèles à ceux ci-dessus. De plus, leur étude du coproduit naturel de H_n(0) à montré qu’il sous-tendait la combinatoire des fonctions de Bessel, et qu’il permettait l’introduction d’analogues non commutatif. Ces analogues font immédiatement apparaître les paires de permutations sans descentes communes, et donc très probablement aussi HS_n. Une des approches favorites de l’équipe est de réaliser les algèbres de Hopf étudiées comme quotients ou sous-algèbres de l’algèbre des mots non-commutatifs. La combinatoire sous-jacente devient alors habituellement simple, ce qui permet de donner des démonstrations élémentaires de la plupart des propriétés algébriques. Cette approche se complète de plus bien avec l’approche opéradique de Loday consistant en particulier à casser les opérations (produit, coproduits) en plusieurs sous-opérations (algèbre dendriforme ou tridendriforme), de façon à faire apparaître les algèbres comme provenant de l’action d’une opérade libre sur un petit nombre de générateurs. Nous essayons avec J.-C. Novelli d’appliquer ces deux approches à l’algèbre des arbres planaires de Gerritzen [, , ]; cet exemple est intéressant car il est à la fois combinatoirement très proche des nôtres (j’ai montré que la base de cette algèbre est en bijection naturelle avec le quotient des fonctions de parking par les relations hypoplaxiques), tout en ayant des propriétés algébriques singulières (le seul coproduit connu n’est pas coassociatif). La réalisation que j’ai déjà obtenue en terme d’algèbre d’âge (autrement dit sur les ensembles) semble un bon premier pas vers cette réalisation sur les mots. Cela mène naturellement à des questions sur les algèbres d’âge, et en tout premier: quelles conditions doit-on imposer sur la structure relationnelle sous-jacente pour pouvoir définir naturellement un coproduit coassociatif sur l’algèbre d’un âge, et en faire ainsi une algèbre de Hopf? Un autre problème ouvert important est de caractériser sous quelles conditions ces algèbres sont de Cohen-Macaulay. En effet, s’il est connu depuis longtemps que les invariants de groupes de permutations sont Cohen-Macaulay en toute caractéristique, la démonstration pour les polynômes quasi-symétriques, même sur les rationnels, est récente [], et il reste a comprendre quelles sont les raisons combinatoires sous-jacentes. Je compte aussi mettre à profit cette délégation pour reprendre des travaux que j’ai dû mettre de côté par manque de temps. Pour commencer, il apparaît clairement que les techniques actuelles de calcul d’invariants [] buttent sur les limites intrinsèques de l’élimination. Aussi est-il essentiel d’y introduire d’autres points de vues (géométrie, techniques d’évaluation). Par exemple, une voie prometteuse, et à ma connaissance jamais explorée jusqu’ici, serait de spécialiser les variables aux racines de l’unité (transformée de Fourier): cela élimine deux des obstacles principaux actuels: calculs de produits (convolution sur le groupe) et calculs modulo les polynômes symétriques, tout en faisant apparaître des objets intéressants comme les spécialisations des polynômes de Schubert sur un alphabet de la forme 1/1−q. D’un autre côté, nos calculs dans les algèbres de Hopf requièrent l’utilisation de très nombreux types d’objets combinatoires. Il est alors essentiel de disposer d’outils génériques pour les manipuler; le cas le plus représentatif est celui des objets décomposables qui peuvent être définis récursivement au moyen de grammaires (notamment toutes les variantes d’arbres) [].Pour cela j’ai intégré en 2002 la bibliothèques CS [] de manipulation d’objets décomposables, et je l’ai depuis grandement étendu avec l’aide de F. Hivert (j’ai par exemple implanté les algorithmes les plus récents de X. Molinero (UPC, Barcelone) et au final j’ai participé au jury de soutenance de sa thèse "Ordered Generation of Classes of Combinatorial Structures"). Cela nous a amené à proposer plusieurs extensions à la théorie des objets décomposables permettant de traiter des classes plus larges d’objets. Un premier article est en préparation sur le sujet avec Conrado Martinez (UPC, Barcelone). Mais tout le travail de recherche et d’implantation reste à effectuer pour l’extension la plus intéressante et utile. Il s’agit d’étudier les objets décomposables dont la taille n’est plus seulement un entier (cas non étiqueté), ou un ensemble de labels tous distincts (cas étiqueté), mais un objet combinatoire plus général. Cela fait naturellement intervenir, en retour et via les séries génératrices, des algèbres de Hopf. En particulier, le cas le plus intéressant d’un ensemble de labels avec répétitions, fait intervenir les fonctions quasi-symétriques. Ce thème fournirait un excellent sujet de DEA, voire de thèse à encadrer. Pour finir, le projet MuPAD-Combinat (56) – même s’il a atteint une maturité suffisante pour que les contributeurs assurent eux-même le gros du développement des extensions périphériques – nécessite toujours un important travail de fond. Cela concerne en particulier l’extraction d’une solide bibliothèque de séries génératrices, des extensions au langage MuPAD (57) pour une plus grande expressivité (meilleur support des classes combinatoires, et en particulier des conteneurs, générateurs et continuations, amélioration de l’interface avec C++ par modules dynamique, amélioration de la syntaxe objet, refonte du système de surcharge), et des études de portabilité à d’autres plateformes (notamment SAGE)que MuPAD (58) afin d’en améliorer la diffusion et la pérennité. Je souhaite enfin profiter de cette période pour effectuer des séjours de moyenne durée chez des équipes travaillant sur des domaines proches à Montréal, Toronto et San-Diego.