%\subsection{Thèmes de recherche}

%%%%%%%%%%%%%%%%%%
% Combinatoire et Physique
%%%%%%%%%%%%%%%%%%

L'activité du groupe de combinatoire au cours de la période 2003-2006 peut être répartie en deux pôles qui semblent disjoints et dont les multiples liens 
n'ont pas encore \'et\'e exploit\'es~: un pôle <<Combinatoire et Physique>> (G.~Duchamp, C.~Tollu, F.~Toumazet) et un pôle d'<<Informatique Th\'eorique>> 
(G.~Duchamp).

\medskip
Les interactions entre combinatoire, informatique et physique ont été, dès la création de notre groupe de travail en 2001, au c{\oe}ur de nos recherches. 
Les membres du groupe sont convaincus qu'un important effort en combinatoire se r\'ev\`elera extr\^emement profitable pour 
une approche algorithmique en physique. 

Il est en effet devenu courant de constater que la solution de nombreux 
probl\`emes en physique et chimie (classique et quantique) est \'etroitement li\'ee \`a la th\'eorie des repr\'esentations 
des groupes et des algèbres, par exemple des algèbres de Lie, c'est-\`a-dire \`a la fa\c{c}on dont ces derniers agissent sur des espaces de dimension finie ou infinie. 
Encore faut-il, dans des 
applications concr\`etes, \^etre en mesure de calculer des grandeurs pertinentes caract\'erisant ces repr\'esentations~: 
\'el\'ements matriciels, d\'ecompositions en irr\'eductibles de produits tensoriels de repr\'esentations, traces de 
repr\'esentations irr\'eductibles ({\em i.e.} caract\`eres), c{\oe}fficients de Clebsch-Gordan et de Racah. 

C'est \`a ce niveau que la combinatoire joue un r\^ole cl\'e, en permettant de décrire explicitement (<<combinatoirement>>) des 
actions de groupes et d'alg\`ebres (de dimension finie ou infinie) qui 
satisfont des contraintes pr\'ecises, physiquement pertinentes, ou en fournissant le param\'etrage des objets de 
l'alg\`ebre par des familles de structures combinatoires (diagrammes ou tableaux de 
Young, graphes, etc.) sujettes aux manipulations \'el\'ementaires, donc au calcul effectif. La th\'eorie des fonctions sym\'etriques 
({\em i.e.} invariantes par permutation des variables) en offre une brillante et classique illustration~: on travaille dans 
des bases orthogonales explicites\footnote{entre lesquelles des formules effectives de changement de base existent.} 
(par exemple les fonctions de Schur) param\'etr\'ees par des diagrammes de Young, et la combinatoire des tableaux 
de Young permet de mener des calculs sans de co\^uteux d\'eveloppements en mon\^omes. C'est d'ailleurs sur l'utilisation 
de telles familles de polyn\^omes (sym\'etriques) orthogonaux que reposent les algorithmes calculant les objets 
(facteurs irr\'eductibles, caract\`eres, etc.) mentionn\'es \`a la fin du paragraphe pr\'ec\'edent, quand ces algorithmes 
existent (essentiellement, dans le cas des groupes finis et des groupes de Lie compacts).

\subsubsection{M\'ecanique des matrices infinies}

Cette activit\'e, initi\'ee par la combinatoire de l'ordre normal bosonique, est fortement inspir\'ee par la <<m\'ecanique des matrices>> de Werner Heisenberg. 
En effet, il est connu qu'il n'existe aucune repr\'esentation (fid\`ele) de l'alg\`ebre de Weyl (m\^eme \`a deux dimensions) par des op\'erateurs born\'es 
(donc aucune représentation de dimension finie). La premi\`ere telle repr\'esentation est dans un espace de Fock de dimension infinie. C'est ce m\^eme espace 
de Fock qui est utilis\'e pour trouver l'ordre normal de puissances d'op\'erateurs homog\`enes, i.e.  du type

\begin{equation}
\Omega=\sum_{w\in W_2,\ |w|_{a^+}-|w|_a=e}\alpha_w w
\end{equation}

o\`u $w$ est un produit d'op\'erateurs $a^+,a\in W$ et $W$ est l'alg\`ebre de Weyl de dimension $2$.

On voit facilement que, selon que l'exc\`es (le degr\'e diraient les math\'ematiciens) $e=r-s$ est positif ou négatif, on a pour forme normale de $\Omega^n$, 

\begin{equation}\label{normal_form1}
(a^+)^{ne}\left(\sum_{k=0}^\infty S_\Omega(n,k) (a^+)^ka^k\right) \textrm{ ou } \left(\sum_{k=0}^\infty S_\Omega(n,k) (a^+)^ka^k\right)(a)^{n|e|}.
\end{equation}

L'\'etude des matrices infinies $S_\Omega(n,k)$ et de leurs implications combinatoires a occupé G. Duchamp et ses collaborateurs physiciens dans 
les travaux \cite{GOF1,GOF7,GOF4,GOF9}.

L'article \cite{GOF4} fait le lien entre les représentations de Bargmann-Fock d'opérateurs homogènes à une annihilation et les champs de vecteurs sur la droite. 
On a en fait l'action d'un groupe de Lie fréchetique sur les fonctions développables en série de Taylor. Les sous-groupes à un paramètre de ce groupe étant 
déterminés par leur vecteur tangent (qui est une <<fonction>>), on obtient le calcul des c{\oe}fficients des matrices associ\'ees par une intégration élémentaire. 
On voit alors que ces matrices sont stables par substitution et multiplication (propri\'et\'e dite <<de Sheffer>> par les combinatoristes \cite{GOF8,GOF9}), ce 
qui donne un éclairage analytique à la composition des graphes (de type <<Grafting>> \cite{GOF8,GOF2}).

\subsubsection{Alg\`ebres de Hopf, d\'eformations}

Dans une publication relativement récente, Bender, Brody et Meister introduisent une théorie des champs spéciale décrite par une formule du produit (un produit 
de Hadamard sur les fonctions génératrices exponentielles) pour montrer que certaines suites de nombres peuvent être décrites par des règles appliquées à 
des types de diagrammes de Feynman. Ces 
diagrammes étiquettent des monômes en deux alphabets, que l'on peut nommer potentiel et action, lorsque les fonctions génératrices couplées ont pour terme 
constant 1. Les structures discrètes mises au point par l'informatique théorique (combinatoire des mots) qui ont été employées pour développer la théorie des 
Fonctions Symétriques Non-Commutatives (NCSF III et VI) réinterviennent ici et la théorie des déformations d'algèbres de Hopf met en correspondance, 
comme l'ont montré G. Duchamp et ses collaborateurs physiciens,  
l'algèbre de Hopf déformée des diagrammes de type Feynman étiquetés ($LDIAG(q_c,q_s,t)$, dans laquelle on garde la trace des superpositions $q_s$ et des 
croisements $q_c$) avec les travaux récents de Connes et Kreimer par l'intermédiaire de l'algèbre des arbres planaires de Foissy.  

D'autre part, le fait que ces alg\`ebres sont libres a deux cons\'equences. La première est que l'on peut constuire une v\'eritable déformation de Hopf (le 
paramètre $t$ de $\LDIAG (q_c,q_s,t)$) entre $\LDIAG$ et $\MQS$ (fonctions symétriques non commutatives matricielles). La deuxième est que leurs duaux de 
Sweedler (souvent considérés comme trop gros par les spécialistes et malcommodes à manipuler) sont calculés à l'aide d'un théorème de Kleene-Schützenberger 
modifié. Ce théorème donne la structure des fonctions reconnues par des automates à multiplicités \cite{DC1,DHKL,DKB,BFCA05} lorsque l'alphabet de commande est 
infini. Ceci est le véritable lien entre ces structures de pure combinatoire algébrique et la théorie des automates. Un article sur ce sujet, "Sweedler's dual 
and Schützenberger's calculus", par G. Duchamp et C. Tollu, est prêt à être soumis à l'automne 2007.

L'algèbre $\LDIAG$ et sa déformation $\LDIAG(q_c,q_s)$ peuvent aussi, comme toute une famille d'algèbres de Hopf dont les bases sont indexées aux matrices 
tassées d'entiers ou d'ensembles d'entiers, être réalisées sur des bimots. Cette réalisation combinatoire permet de mettre en évidence une structure de bigèbre 
bidendriforme sur $\MQS$, de laquelle découlent nombre de propriétés de structure importantes~: liberté, co-liberté, structure de Lie des éléments primitifs 
\cite{DLNTT-fpsac}.

\subsubsection{Multiplicités et combinatoire des polytopes}

C. Tollu et F. Toumazet étudient, en collaboration étroite avec R.C. King (université de Southampton, Royaume-Uni), le comportement, sous l'action de 
transformations combinatoires, de nombres qui apparaissent \`a de multiples reprises en alg\`ebre (dimension de l'espace des vecteurs 
invariants du produit de trois repr\'esentations) en g\'eom\'etrie (calcul de Schubert) et en physique (\'etats d'\'energie 
r\'esultant de l'interaction de plusieurs oscillateurs harmoniques).

\medskip
En physique, les repr\'esentations irr\'eductibles (polynômiales) de dimension finie du groupe g\'en\'eral 
lin\'eaire $GL_n(\mathbb{C})$ ou du groupe unitaire $U(n)$ jouent un r\^ole de premier plan. Il est connu de longue 
date qu'elles sont param\'etr\'ees par les partitions contenant au plus $n$ parts, {\em i.e.} les suites d'entiers 
$\lambda_1\geq\cdots\geq\lambda_n\geq 0$. La combinatoire 
de ces repr\'esentations est intimement li\'ee \`a des nombres entiers positifs ou nuls, appel\'es c{\oe}fficients 
de Littlewood-Richardson. Ces nombres correspondent \`a des multiplicit\'es dans la d\'ecomposition en 
repr\'esentations irr\'eductibles du produit tensoriel de deux repr\'esentations polynômiales~; partant, ils 
apparaissent aussi comme constantes structurelles de l'alg\`ebre des fonctions sym\'etriques si la base choisie est 
celle des fonctions de Schur, qui <<sont" les caract\`eres irr\'eductibles de $GL_n(\mathbb{C})$. Les nombres de 
Littlewood-Richardson, not\'es $c_{\lambda, \mu}^{\nu}$, sont param\'etr\'es par trois partitions $\lambda$, 
$\mu$ et $\nu$~; dans de nombreux contextes, il est primordial, sinon de 
calculer exactement un (ou plusieurs) $c_{\lambda, \mu}^{\nu}$, du moins d'avoir des informations pr\'ecises 
(nullit\'e du c{\oe}fficient, encadrement pr\'ecis de sa valeur). La r\`egle de Littlewood-Richardson permet de 
calculer $c_{\lambda, \mu}^{\nu}$ pour tout triplet de partitions fix\'e, mais le 
co\^ut de cet algorithme devient prohibitif d\`es que la taille et le poids des partitions deviennent grands. 

\medskip
R\'ecemment, Knutson, Tao (et Woodward) ont fait des avanc\'ees spectaculaires\footnote{Voir A.~Knutson and T.~Tao, <<The honeycomb model 
of $GL_n(\mathbb{C})$ tensor products. I: Proof of the saturation conjecture", {\em J. Amer. Math. Soc.} \textbf{12} (1999) 1055-1090, et 
A.~Knutson, T.~Tao and C.~Woodward, <<The honeycomb model of $GL_n(\mathbb{C})$ tensor products. II: Puzzles determine facets of the 
Littlewood-Richardson cone", {\em J. Amer. Math. Soc.} \textbf{17} (2004) 19-48.} gr\^ace \`a deux nouveaux mod\`eles 
combinatoires pour les c{\oe}fficients de Littlewood-Richardson, celui des ruches ({\em hives}) et celui des nids 
d'abeilles ({\em honeycombs}), qui font clairement appara\^{\i}tre que les c{\oe}fficients de Littlewood-Richardson 
comptent les points \`a coordonn\'ees enti\`eres dans des polytopes (ensembles convexes born\'es de l'espace euclidien). 
Ils ont montr\'e d'une part, 
que $c_{\lambda, \mu}^{\nu} = 0$ si et seulement si la dilatation $c_{N\lambda, N\mu}^{N\nu}$ (ici, chaque part 
de $\lambda$, $\mu$ et $\nu$ est multipli\'ee par l'entier $N>0$) est nulle (conjecture de saturation), d'autre 
part, que $c_{\lambda, \mu}^{\nu} = 1$ si et seulement si $c_{N\lambda, N\mu}^{N\nu} = 1$ (conjecture de 
Fulton-Kirillov). Dans le prolongement de ces travaux, King, Tollu et Toumazet ont \'etudi\'e les relations entre 
$c_{\lambda, \mu}^{\nu}$ et $c_{N\lambda, N\mu}^{N\nu}$ quand le c{\oe}fficient de base 
$c_{\lambda, \mu}^{\nu}>1$. Ils ont accumul\'e assez de donn\'ees exp\'erimentales\footnote{Des calculs MAPLE et surtout SCHUR ont été effectués 
pour des valeurs de $N|\nu|$ de l'ordre de 500, ce 
qui repr\'esente plusieurs centaines d'heures de calcul. Auparavant, les calculs n'avaient \'et\'e men\'es que pour 
des donn\'ees \`a peu pr\`es dix fois plus petites.} 
pour proposer et \'etayer une nouvelle conjecture, qui g\'en\'eralise tous les r\'esultats des travaux d\'ecrits ci-dessus.

\begin{conjecture} \cite{KTT-crm}
Le nombre $c_{N\lambda, N\mu}^{N\nu}$ est un polyn\^ome en $N$ \`a c{\oe}fficients rationnels positifs dont le terme 
constant vaut $1$ et dont le degr\'e est donn\'e par la dimension d'un polytope associ\'e \`a $c_{\lambda, \mu}^{\nu}$.
\end{conjecture}

Dans \cite{KTT-crm}, cette conjecture est demontrée dans deux cas particuliers, (i) celui o\`u la longueur des partitions 
sp\'ecifiant $c_{\lambda, \mu}^{\nu}$ est inf\'erieure \`a $5$, et (ii) celui o\`u l'une des deux partitions 
$\lambda,\mu$ est une \'equerre.\footnote{La polynômialité des $c_{N\lambda, N\mu}^{N\nu}$ a été depuis démontrée par E. Rassart.} 
% <<A polynomiality property for Littlewood-Richardson coefficients", {\em J. Comb. Theory}, Series A \textbf{107} (2004), no. 2, 161-179.. 

Cette conjecture en entra\^{\i}ne une similaire portant sur d'autres nombres, les nombres de Kostka, 
$K_{\lambda\beta}$, qui donnent la multiplicit\'e de l'espace de poids $\beta$ dans la repr\'esentation irr\'eductible 
param\'etr\'ee par la partition $\lambda$. 

\begin{conjecture} \cite{KTT-crm}
Le nombre $K_{N\lambda, N\beta}$ est un polyn\^ome en $N$ \`a c{\oe}fficients rationnels positifs dont le terme 
constant vaut $1$ et dont le degr\'e est donn\'e par la dimension d'un polytope associ\'e \`a $K_{\lambda, \beta}$.
\end{conjecture}

En adaptant le mod\`ele des ruches aux nombres de Kostka, King, Tollu et Toumazet ont aussi montr\'e comment d\'ecomposer les polyn\^omes 
$P_{\lambda\beta}(t) = K_{t\lambda,t\beta}$ en facteurs <<primitifs>> et d\'eterminer une suite de facteurs lin\'eaires 
$(t+m)$. Quant au degr\'e de ces polyn\^omes, ils ont obtenu une formule close et ais\'ement calculable, qui donne un 
nouveau majorant, nettement plus bas que le majorant  
\'evident donn\'e par la dimension de l'espace ambiant dans lequel le polytope est plong\'e \cite{KTT-fpsac,KTT-Kostka-SLC}. Dans le 
cas o\`u $P_{\lambda\beta}(t)$ est un polyn\^ome primitif, ce majorant est toujours atteint\footnote{Cela a été confirmé par T. McAllister, 
<<Degrees of stretched Kostka coefficients", ArXiv:\texttt{math.RT/0603173}.}. 

Certains de ces r\'esultats ont \'et\'e g\'en\'eralis\'es aux c{\oe}fficients de Littlewood-Richardson (crit\`ere combinatoire 
pour la factorisation des polyn\^omes $P_{\lambda\mu}^{\nu}(t) = c_{t\lambda, t\mu}^{t\nu}$, d\'etermination d'une suite 
de facteurs lin\'eaires), m\^eme si d'autres g\'en\'eralisations semblent aujourd'hui hors de port\'ee \cite{KTT-crm,KTW-LR-SLC}. Une publication sur ce sujet, 
"The factorisation of Littlewood-Richardson coefficients" par R.C.~King, C.~Tollu et F.~Toumazet, est soumise à {\em J. Comb. Th. A}.

Tous ces r\'esultats sont actuellement exploit\'es pour le d\'eveloppement d'algorithmes distribu\'es permettant de calculer les 
nombres $K_{\lambda\beta}$ et $c_{\lambda, \mu}^{\nu}$. Les performances des protocoles mis au point au \acs{LIPN} se comparent favorablement \`a 
celles d'un syt\`eme comme \texttt{LaTTe} (UC Davis, \'Etats-Unis) \cite{NTB-Torun}. Les possibilit\'es de parall\'elisation sont 
prometteuses et m\'eritent d'\^etre mieux prises en compte, car il est vain d'esp\'erer des algorithmes s\'equentiels efficaces 
pour des nombres $K_{\lambda\beta}$ et $c_{\lambda, \mu}^{\nu}$ associ\'es \`a des partitions de grands poids~: le calcul de ces nombres 
est $\#P$-complet\footnote{Ce r\'esultat a \'et\'e publi\'e dans H.~Narayanan, <<The computation of Kostka numbers and Littlewood-Richardson 
coefficients is $\#P$-complete>>, ArXiv~:\texttt{math.CO/0501176}.}. 


\subsubsection{Invariants et information quantique}

%\textit{Participant~: F. Toumazet}

F. Toumazet, en collaboration avec J.-G. Luque et J.-Y. Thibon (Laboratoire d'informatique de l'Institut Gaspard Monge, université de Marne-la-Vallée) 
est engagé dans un projet de classification des états intriqués {\em via} le calcul d'invariants pour les hyperdéterminants.

\smallskip
L'intrication, propri\'et\'e des syst\`emes quantiques, a \'et\'e  \'etudi\'ee 
depuis longtemps, et remonte aux travaux de Schr\"odinger. 
Elle s'est r\'ecemment distingu\'ee avec 
l'av\`enement de travaux th\'eoriques sur le calcul quantique et 
d'autres  ph\'enom\`enes purement quantiques. Aujourd'hui, des mesures et 
des crit\`eres th\'eoriques  ne sont connus que pour les
syst\`emes les plus simples, bien que des progr\`es 
aient \'et\'e r\'ecemment accomplis dans cette
direction. 

En fait, il n'existe m\^eme aucune d\'efinition universellement
accept\'ee pour les syst\`emes de plus de deux particules,
et la recherche d'une bonne d\'efinition constitue un pr\'ealable
\`a la d\'etermination de mesures utilisables. En effet, l'intrication
 est l'une des caract\'eristiques fondamentales
qui distinguent les syst\`emes quantiques du monde classique,
et par l\`a m\^eme une propri\'et\'e physique importante \`a comprendre.
 
C'est aussi une ressource importante dans la th\'eorie de l'information
quantique, jouant un r\^ole vital dans la cryptographie quantique
et la communication quantique, par exemple.
 
Dans le calcul quantique par \'etats purs, il a \'et\'e montr\'e
qu'une acc\'el\'eration exponentielle pour certains
probl\`emes n'est possible qu'avec une intrication suffisante.
 
Toutefois, il reste de nombreuses questions ouvertes, concernant
en particulier les syst\`emes \`a \'etats mixtes.
 
Des travaux r\'ecents sur l'intrication d'unit\'es quantiques
de dimensions sup\'erieures (qudits), particuli\`erement
les qutrits, ont de plus montr\'e que de tels syst\`emes
peuvent exhiber de nouvelles propri\'et\'es telles que
la non-localit\'e quantique sans intrication, et de plus
fortes violations des in\'egalit\'es de Bell.
Les implications de ces travaux ne sont pas encore compl\`etement comprises.

Des m\'ethodes bas\'ees sur la th\'eorie des groupes peuvent
\^etre avantageusement utilis\'ees dans ce contexte, et c'est dans cet esprit que ce travail est mené.

Ainsi, depuis sa découverte théorique, en 1935 par Einstein, Podolsky et Rosen
l'intrication a fait l'objet de  nombreuses investigations. La connaissance d'une
classification des états intriqués devrait permettre de tirer profit des
propriétés des systèmes quantiques de particules afin de construire des
applications nouvelles.
L'idée de recourir à la théorie de Mumford dans ce contexte a été proposée
en Juin 2002 par Alexander Klyachko.
Le but de l'opération est d'identifier les invariants pertinents
susceptibles d'une définition uniforme, et d'évaluer l'utilité des critères
accessibles à la théorie géométrique des invariants de Hilbert et Mumford,
dont le but est de remédier à l'impossibilité des calculs explicites.

Luque, Thibon et Toumazet ont déjà obtenu des résultats sur les invariants des 4-qubits,
3-qutrits  et  5-qubits ainsi que sur les invariants unitaires des systèmes
purs de k-qubits (les invariants unitaires interviennent dans la
construction de mesures d'intrication) \cite{LTT-inv}.


\subsubsection{Calcul formel pour la physique}

%\textit{Participant~: F. Toumazet, F.~Butelle (LIPN, OCAD)}

\smallskip
L'étude systématique des propriétés des groupes et algèbres de Lie, leurs applications à la chimie, la physique, les mathématiques, a conduit 
à l'élaboration de nombreux outils de calculs symboliques dans différents types de langage de calcul formel (bibliothèques de John Stembridge 
sous MAPLE, bibliothèque \texttt{combinat} sous MUPAD etc). Une autre alternative fut le développement d'environnements spécifiques tels LIE ou encore GAP. 
Ces outils, très efficaces, sont aussi très lourds à mettre en {\oe}uvre et tout en se spécialisant dans leurs domaines mathématiques, ils n'offrent 
pas toujours les fonctions de base liées à l'utilisation des fonctions symétriques, très utiles dans l'étude systématique des représentations 
polynômiales des groupes et algèbres de Lie. Dans ce cadre, F. Butelle (\acs{LIPN}, équipe \acs{OCAD}) et F. Toumazet ont décidé (avec R.C. King, Université de 
Southampton) de poursuivre le développement du programme SCHUR, important outil de calcul permettant la 
manipulation des objets combinatoires les plus usuels. Ce programme, initialement développé à la fin des années 70 par B. G. Wybourne et ses 
étudiants du département de physique de l'université de Christchurch (Nouvelle-Zélande), a été commercialisé dans les années 80. Devenu 
confidentiel et à usage privé dans les années 90 (un très petit cercle autour de son auteur), il a subi d'importantes phases de changement 
comme sa traduction en C et l'addition de nombreuses fonctionnalités, ajoutées année par année suivant les derniers développements scientifiques 
dans le domaine de la combinatoire algébrique.

Après le décès de B.G. Wybourne, ses amis physiciens et combinatoristes ont souhaité continuer à faire vivre le programme SCHUR. Le logiciel SCHUR 
vient d'être diffusé en GPL sur le site Sourceforge (http://schur.sourceforge.net). Avant cette publication, le 
code C a été naturellement complètement remanié, rendu plus lisible et amendable par la communauté du logiciel libre. En outre, il est livré avec 
une importante documentation (environ 230 pages) et un ensemble d'exemples permettant de valider et de comprendre le fonctionnement du logiciel. 
Actuellement compilé pour Linux et Windows, une version pour MacOS X est en cours de préparation. Ce programme, de par sa taille modeste, peut 
s'exécuter sur de nombreuses machines et ne nécessite pas de configuration très importante pour fonctionner (du moins pour les fonctionnalités 
de base). Avec plus de 200 fonctions, il permet outre les manipulations standards sur les fonctions symétriques, de nombreux calculs sur les 
représentations des groupes et algèbres de Lie de tout type ainsi que sur les représentation du groupe symétrique et dans une moindre mesure des 
algèbres de Hecke.

Ainsi, SCHUR est un outil puissant, et malgré tout léger, spécialement efficace pour examiner de nouvelles conjectures en théorie des 
représentation des groupes (compacts comme non compacts). Il est aussi utile pour chercher de nouvelles identités sur les fonctions symétriques 
et valider ou invalider des conjectures. Pour citer quelques exemples, mentionnons que SCHUR a permis les premiers calculs pour chercher à établir 
de nouvelles récurrences permettant le calcul des puissance des $q$ déterminants de Vandermonde \cite{KTW-vdM}, d'obtenir les critères précis concernant 
les produits génériques pour les groupes symplectiques réels (produits de représentations de dimension finie par des représentations de dimension infinie) 
\cite{Tou-Torun} ou encore de trouver les premiers polynômes associés à la dilatation des c{\oe}fficients de Littlewood-Richardson ou des nombres de Kostka 
\cite{NTB-Torun,KTT-crm,KTT-fpsac}.

A ce sujet et pour terminer, à chaque prise en compte de nouveaux résultats, les algorithme sont amendés et il est prévu d'implémenter très prochainement 
le modèle des ruches de Knutson-Tao dans SCHUR, jusqu'à présent uniquement utilisé dans des programmes MAPLE, et de l'utiliser pour faire du calcul distribué.

%\subsection{Informatique Théorique}\label{Sw}

\subsubsection{Automates (\`a multiplicit\'es)}

%\textit{Participant~: G. Duchamp}

\smallskip
La th\'eorie des automates \`a multiplicit\'es telle qu'elle est exposée dans le livre de S. Eilenberg <<Automata, Languages and Machines>> est due 
essentiellement à Schützenberger et \`a son école. Il s'agit d'une véritable généralisation de la théorie classique puisqu'en variant les scalaires on 
peut obtenir les automates booléens, stochastiques (chaînes de Markov), plus courts chemins et transducteurs. Les scalaires les plus généraux doivent être 
pris dans un semi-anneau (généralisation des anneaux où on ne demande pas qu'il y ait une opération de <<passage à l'opposé>>). La structure de donnée 
adaptée au calcul dans les algèbres à c{\oe}oefficients dans les semi-anneaux est celle de table (avec les réécritures adéquates) \cite{DKB}. D'autre part, 
la structure de donn\'ees adaptée au calcul rationnel est celle de classe d'expressions rationnelles selon des congruences assez grossières pour permettre 
des résultats de décidabilité \cite{DC1}. Enfin, les phénomènes de chemins infinis (cycliques) sont concentrés dans les problèmes d'étoile qui se formulent 
naturellement dans les automates quand on a rajouté une transition dont le symbole ($\epsilon$) doit être supprimé dans l'étiquetage des chemins \cite{DHKL}. Enfin, 
lorsque le semi-anneau des scalaires est un corps (de caractéristique nulle ou positive), on peut minimiser les automates grâce à des arbres couvrant leur graphe. 
Ces arbres sont indexés par des codes suffixes. Ceci permet de casser les fonctions booléennes de la cryptographie de façon compatible avec la permutation de 
leurs variables \cite{BFCA05}.

\subsubsection{Systèmes Complexes} 

%\textit{Participant~: G. Duchamp}


Sans pouvoir donner une définition formelle des Systèmes Complexes, on peut essayer de donner une idée de cette théorie fascinante grâce à l'étymologie, 
comme le fait, par exemple, l'article <<Systèmes Complexes>> de Wikipédia.

\smallskip
{\tt http://fr.wikipedia.org/wiki/Système\_complexe}

\smallskip 
<<{\it Étymologiquement, compliqué (du latin cum pliare, empiler avec) signifie qu'il faut du temps et du talent pour comprendre l'objet d'étude, complexe 
(du latin cum plexus, attaché avec) signifie qu'il y a beaucoup d'intrications, que "tout est lié" et que l'on ne peut étudier une petite partie du système 
de façon isolée.}>> 

La th\'eorie des syst\`emes complexes a de multiples aspects. Le cadre de certains pans de celle-ci, comme la th\'eorie du chaos et celle des syst\`emes 
dissipatifs en physique (et encore quand la dissipation est une fonction lin\'eaire) sont relativement stabilis\'es. D'autre fragments de th\'eorie restent 
\`a construire ; il s'agit ici de {\it science descriptive} allant de la ph\'enom\'enologie pure (\cite{BaD}, en collaboration avec l'Inserm) \`a la 
description de dynamiques, d'espaces de phases et de m\'etriques sur ceux-ci \cite{BD2,BD4} ou \`a la proposition de changements de point de vue \cite{KBDO,BD3}.  

Ici, G. Duchamp s'est employé dans trois directions~: les algorithmes 
génétiques sur des populations d'automates à multiplicités \cite{BD1}, les structures de donn\'ees dynamiques \cite{BD2} et les bases de donnes géographiques 
\cite{KBDO,BD3}.


\subsection{Pespectives de recherche}

G. Duchamp intensifie sa collaboration avec les physiciens et poursuit ses travaux sur les déformations des algèbres de Hopf de diagrammes de Feynman. 
On espère en particulier des résultats nouveaux sur 
les liens qui existent entre algèbres de Hopf combinatoires qui apparaissent comme des spécialisations de $\LDIAG (q_c,q_s,t)$, leur combinatoire et 
leur algorithmique. Il espère aussi approfondir ses travaux sur les systèmes complexes et les connecter à ses autres axes de recherche. 

C. Tollu et F. Toumazet poursuivent leur collaboration avec R.C. King sur le thème <<Multiplicités et combinatoire des polytopes". Les méthodes qui ont permis 
les récents progrès sur la factorisation des c{\oe}fficients de Littlewood-Richardson vont être étendues à des multiplicités apparaissant dans la combinatoire 
des tours d'algèbres dont le diagramme de Bratteli (ou graphe de branchement) est proche du graphe de Young (diagramme de Hasse des partitions d'entiers ordonnées 
par l'inclusion). La combinatoire et l'analyse spectrale de ces graphes de branchement sera aussi un des thèmes de recherche d'Hayat Cheballah, qui commence une 
thèses de doctorat au LIPN, sous la direction de G. Duchamp et C. Tollu, en septembre 2007.

F. Toumazet se propose de continuer les investigations avec J.-G. Luque et J.-Y. Thibon sur le thème <<Calcul d'invariants pour l'information 
quantique". En
particulier, ils s'intéresseront aux liens existant entre la théorie des
invariants des petits systèmes et la notion d'algèbre de Lie graduée.  En
effet, des groupes de réflexions complexes apparaissent dans l'étude de
certains petits systèmes quantiques. Ce phénomène peut s'expliquer via la
notion de groupe de Weyl des algèbres de
Lie graduées découverte par Vinberg en 1975. Il est opportun d'appliquer
cette théorie  aux systèmes de 4-qubits.

Enfin, le développement du logiciel SCHUR occupera F. Toumazet (en collaboration avec F. Butelle).