\documentclass[12pt]{iopart}

\usepackage[dvips]{epsfig}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{pstricks}
%\textheight 240mm
%\textwidth 160mm
%\hoffset -14mm
%\voffset -26mm
%\parindent=0pt


%%%%%%%%%%%%%%%%%%%%%%
% Fonts
%%%%%%%%%%%%%%%%%%%%%%
 \font\tensym=msbm10
 \font\sevensym=msbm7
 \font\fivesym=msbm5

 \font\twelvegoth=eufb10 at 12pt
 \font\tengoth=eufb10
 \font\sevengoth=eufb7
 \font\fivegoth=eufb5

\newfam\symfam
\textfont\symfam=\tensym
\scriptfont\symfam=\sevensym
\scriptscriptfont\symfam=\fivesym
\def\sym{\fam\symfam\tensym}
\def\fns{\footnotesize}

\newfam\gothfam
\textfont\gothfam=\tengoth
\scriptfont\gothfam=\sevengoth
\scriptscriptfont\gothfam=\fivegoth
\def\goth{\fam\gothfam\tengoth}

%%%%%%%%%%%%%%%%%%%%%%
% Jumps
%%%%%%%%%%%%%%%%%%%%%%

\def\hs{\hbox to 3mm{}}
\def\hhs{\hbox to 5cm{}}
\def\ss{\smallskip}
\def\ms{\smallskip}
\def\bs{\bigskip}
\def\bbss{\vskip 6mm}

%%%%%%%%%%%%%%%%%%%%%%
% Images
%%%%%%%%%%%%%%%%%%%%%%

\def\JPicScale{0.8}\ifx\JPicScale\undefined\def\JPicScale{1}\fi

%%%%%%%%%%%%%%%%%%%%%%
% Miscellaneous
%%%%%%%%%%%%%%%%%%%%%%

%%% Letters et abbreviations %%%

\def\A{\mathcal{A}}
\def\Aa{\mathbb{A}}
\def\U{\mathcal{U}}
\def\TBD{\times_{BD}}
\def\C{\mathbb{C}}
\def\H{\mathcal{H}}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\D{\mathcal{D}}
\def\DWS{\Delta_{WS}}
\def\DBS{\Delta_{BS}}
\def\E{{\sym E}}
\def\HWS{{\cal H}_{WS}}
\def\1H{\mathbf{1}_{\HWS}}
\def\L{\mathbb{L}}
\def\V{\mathbb{V}}
\def\X{\mathbb{X}}
\def\Y{\mathbb{Y}}
\def\Q{{\sym Q}}
\def\SG{{\frak S}}
\def\al{\alpha}
\def\be{\beta}
\def\ep{\varepsilon}
\def\la{\lambda}
\def\Om{\Omega}
\def\om{\omega}
\def\MQSym{{\bf MQSym}}
\def\red{\stackrel{\small red}{\longrightarrow}}
\def\bd{\bar\Delta}
\def\card{\mathrm{card}}
%\def\2m#1#2{\pmatrix{#1\cr #2}}
%\def\3m#1#2#3{\pmatrix{#1\cr #2\cr #3}}
\def\2m#1#2{(#2 #1)}
\def\3m#1#2#3{(#3 #2 #1)}
\def\inf{\uparrow}

%%% Spaces %%%

\def\diag{\mathbf{diag}}
\def\ldiag{\mathbf{ldiag}}
\def\lbell{\mathbf{lbell}}
\def\LDIAG{\mathbf{LDIAG}}
\def\DIAG{\mathbf{DIAG}}
\def\BELL{\mathbf{BELL}}
\def\LBELL{\mathbf{LBELL}}
\def\MQS{\mathbf{MQSym}}
\def\ncp#1#2{#1\langle #2\rangle}

%%% Arrows %%%

\def\ra{\rightarrow}
\def\lar{\leftarrow}
\def\lra{\leftrightarrow}
\def\da{\downarrow}
\def\ua{\uparrow}
\def\sea{\searrow}
\def\swa{\swarrow}

%%% Signs %%%

\def\mod{{\rm\ mod\ }}
\def\quo{{\rm\ quo\ }}
\def\irem{{\rm\ rem\ }}
\def\peb#1{\lfloor #1\rfloor}
\def\peh#1{\lceil #1\rceil}
\def\adots{\mathinner{\mkern2mu\raise1pt\hbox{.}
\mkern3mu\raise4pt\hbox{.}\mkern1mu\raise7pt\hbox{.}}}
\def\binomial#1#2{\left(\,\begin{matrix}#1 \\ #2\end{matrix}\,\right)}
\def\pointir{\unskip . --- \ignorespaces}
\def\quest{{\bf Q\ }}
\def\rep{{\bf R\ }}
\def\up#1{\raise 1ex\hbox{\footnotesize#1}}
\def\cs{$\clubsuit$}
\def\sps{$\spadesuit$}
\def\hes{$\heartsuit$}
\def\ds{$\diamondsuit$}
\def\mref#1{{\footnotesize ({\ref{#1}})}}

%%%%%%%%%%%%%%%%%%%%%%
% Statements
%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{expl}{Exemple}[section]
\newtheorem{exercice}{Exercice}[section]
\newtheorem{nota}[expl]{Note}
\newtheorem{exo}[expl]{Exercice}
\newtheorem{exm}[expl]{Exerc. Machine}
%\newtheorem{theo}[expl]{Th\'eor\`eme}
\newtheorem{theorem}[expl]{Theorem}
\newtheorem{corollaire}[expl]{Corollaire}
\newtheorem{comm}[expl]{Comment}
\newtheorem{definition}[expl]{D\'efinition}
\newtheorem{proposition}[expl]{Proposition}
\newtheorem{prdef}[expl]{Proposition/D\'efinition}
\newtheorem{algorithme}[expl]{Algorithme}
\newtheorem{lemma}[expl]{Lemma}
\newtheorem{rem}[expl]{Remark}
\newtheorem{appli}[expl]{Applications}

\def\Proof{\medskip\noindent {\it Proof --- \ }}
\def\cqfd{\hfill $\Box$ \bigskip}

%%%%%%%%%%%%%%%%%%%%%%
% Affichage date et l'heure courante %\isodayandtime% 
%%%%%%%%%%%%%%%%%%%%%%
\begingroup
\count0=\time \divide\count0by60 % Hour
\count2=\count0 \multiply\count2by-60 \advance\count2by\time
% Min
\def\2#1{\ifnum#1<10 0\fi\the#1}
\xdef\isodayandtime{
%\centerline
{\2\day-\2\month-\the\year\space\2{\count0}:%
\2{\count2}}}
\endgroup


\begin{document}


\title[A Quantum Version of the Hopf Algebra of Feynman-like Diagrams]
{A Three Parameters Hopf Deformation of the Algebra of Feynman-like Diagrams}
\author{G H E Duchamp$^{a}$, A I Solomon$^{c,d}$, P Blasiak$^{b}$, K A Penson$^{c}$ and A Horzela$^{b}$\vspace{2mm}}

\address{$^a$ Institut Galil\'ee, LIPN, CNRS UMR 7030\linebreak
99 Av. J.-B. Clement, F-93430 Villetaneuse, France\vspace{2mm}}

\address
{$^b$ H. Niewodnicza\'nski Institute of
Nuclear Physics, Polish Academy of Sciences\\
ul. Eliasza-Radzikowskiego 152,  PL 31342 Krak\'ow, Poland\vspace{2mm}}

\address
{$^c$ Laboratoire de Physique Th\'eorique de la Mati\`{e}re Condens\'{e}e\\
Universit\'e Pierre et Marie Curie, CNRS UMR 7600\\
Tour 24 - 2i\`{e}me \'et., 4 pl. Jussieu, F 75252 Paris Cedex 05, France\vspace{2mm}}

\address
{$^e$ The Open University, Physics and Astronomy Department\\
Milton Keynes MK7 6AA, United Kingdom\vspace{2mm}}

\eads{\linebreak\mailto{ ghed@lipn-univ.paris13.fr}, 
\mailto{ a.i.solomon@open.ac.uk}
\mailto{ pawel.blasiak@ifj.edu.pl},
\mailto{ andrzej.horzela@ifj.edu.pl},
\mailto{penson@lptl.jussieu.fr},
}



\begin{abstract}
We build here a three parameters deformation of the Hopf algebra $\LDIAG$. This new Algebra is a true Hopf deformation, specializes to $\LDIAG$ on one side and to $\MQS$ on the other, relating $\LDIAG$ to the other Hopf algebras of contemporary Physics. Moreover its product law covers the algebra of polyzeta functions.\footnote[0]{Version du \isodayandtime}
\end{abstract}



\tableofcontents

\newpage

\section{Introduction}

Let us describe roughly the route from the product formula by Bender et al. \cite{BBM} and their related Feynman-like diagrams to the discovery of Hopf algebra structures \cite{GOF4} on the diagrams themselves compatible with their evaluations.\\
First, C. M. Bender, D. C. Brody, and B. K. Meister \cite{BBM} introduced a special field theory which proved to be particularly rich in combinatorial links and by-products.\\
Second, the Feynman-like diagrams produced by this theory label monomials and we had the surprise to see that they naturally combine in a way compatible with the monomial multiplication and co-addition. This is the Hopf algebra $\mathbf{DIAG}$.\\
Third, the natural noncommutative pull-back of this algebra, $\LDIAG$, has a basis (the labelled diagrams) which is
in one-to-one correspondence with that of the Matrix Quasi-Symmetric Fonctions (the packed matrices of $\MQS$), but their algebra and co-algebra structures are completely different. In particular, in this basis, the multiplication of $\MQS$ implies a sort of shifted shuffle with overlappings reminiscent to Hoffmann's shuffle used in the theory of polyzeta functions \cite{??}. The superpositions and overlappings involv ed there are not present in the (non-deformed) $\LDIAG$ and, moreover, the coproduct of $\LDIAG$ is co-commutative and the one of $\MQS$ is not.

\ss
The aim of this paper is to introduce some ``parametric algebra'' between the two Hopf algebras $\LDIAG$ and $\MQS$. The striking result is that, introducing parameters to count, in the most natural way, the crossings and overlappings of the shifted shuffle one can witness that the resulting law is associative (graded with unit). We also show how to interpolate with a coproduct which makes, at each stage, our algebra a Hopf algebra. The result is thus a three-parameters Hopf algebra deformation wich specialises to $\LDIAG$ at $(0,0,0)$ and to $\MQS$ at $(1,1,1)$. Moreover it appears that, for some set of parameters, the multiplication rule of $\LDIAG$ covers the one of Euler-Zagier sums.\\

{\sc Acknowkedgements} : The fist material of this paper was set during the staying of one of the authors at ``the firs'' (Exeter). Be its owner, Catherine Borgen, be thanked for her creative hospitality.

\ss
The structure of the paper is the following ...          


\section{How and why these Feynman-like Diagrams arise}

The beginning of the story was explained with full details in \cite{GOF2,GOF3,GOF5,GOF6,GOF7,GOF8}, and the Hopf algebra structure is made precise in \cite{GOF4,GOF10}. Here, we will make the beginning shorter but focus on the last part, where the algebraic structure constructed on the diagrams themselves arise.

\ss
The very starting point is the formula (product formula) of Bender and al. \cite{BBM}, which can be considered as an expression of the Hadamard product for exponential generating series. That is, with 

\begin{eqnarray}
F(z)=\sum_{n\geq 0} a_n\frac{z^n}{n!},\ G(z)=\sum_{n\geq 0} b_n\frac{z^n}{n!},\ 
\mathcal{H}(F,G):=\sum_{n\geq 0} a_nb_n\frac{z^n}{n!}
\end{eqnarray}

one can check that 

\begin{eqnarray}
\mathcal{H}(F,G)=\left.F\left(z\frac{d}{dx}\right)G(x)\right|_{x=0}.
\end{eqnarray}  

This product being bilinear, in the case when $F(0)$ and $G(0)$ are not zero, one can renormalize the functions so that $F(0)=G(0)=1$ and one is interested to obtain compact and generic formulas. If we write the functions as 

\begin{eqnarray}
F(z)=\exp\left(\sum_{n=1}^\infty L_n\frac{z^n}{n!}\right),\ \ \ \ \ \ \ 
G(z)=\exp\left(\sum_{n=1}^\infty V_n\frac{z^n}{n!}\right).
\end{eqnarray} 

that is as free exponentials, one gets, through the Bell polynomials in the sets of variables $\L, \V$ (see \cite{GOF4} for details)

\begin{eqnarray}
\mathcal{H}(F,G)=\sum_{n\geq 0} \frac{z^n}{n!} \sum_{P_1,P_2\in UP_n} \L^{Type(P_1)}\V^{Type(P_2)}
\end{eqnarray} 
where $UP_n$ is the set of unordered partitions of $[1\cdots n]$. An unordered partition $P$ of a set $X$, is a subset of $P\subset \frak{P}(X)-\{\emptyset\}$\footnote{The set of subsets of $X$ is denoted $\frak{P}(X)$ (this denotation \cite{B_ST} owes to the former german school).} (that is an unordered collection of blocks, i. e. non-empty subsets of $X$) such that 
\begin{itemize}
	\item the union $\bigcup_{Y\in P}Y=X$ ($P$ is a covering)
	\item $P$ consists of disjoint subsets, i. e.\\ 
	$Y_1,Y_2\in P\ and\ Y_1\cap Y_2\neq \emptyset \Longrightarrow Y_1=Y_2$.
\end{itemize}

The type of $P\in UP_n$ (denoted above $Type(P)$) is the multiindex $(\al_i)_{i\in \N^+}$ such that $\al_k$ is the number of $k$-blocks, that is 
the number of members of $P$ with cardinality $k$. 

\ss
Here is the point where the formula entangles and the diagrams of the theory arise.\\
The fundamental remarks are : 
\begin{itemize}
	\item the monomial $\L^{Type(P_1)}\V^{Type(P_2)}$ needs much less information than that which is contained in the individual partitions $P_1,\ P_2$ (for example, one can relabel the elements without changing the monomial),
	\item two partitions have an incidence matrix {\it from which it is still possible to recover the types of the partitions}
\end{itemize}

\ss 
Now, the construction goes as follows.
\begin{enumerate}
	\item Take two unordered partitions of $[1\cdots n]$, say $P_1,P_2$
	\item Build their incidence matrix $\left(\card(Y\cap Z)\right)_{(Y,Z)\in P_1\times P_2}$
	\item Build the diagram representing the multiplicities of the incidence matrix : for each block of $P_1$ draw a black spot (resp. for each block of $P_2$ draw a white spot)
	\item Draw lines between the black spot $Y\in P_1$ and the white spot $Z\in P_2$ as much as $\card(Y\cap Z)$
	\item Remove the information of the blocks $Y,Z,\cdots$.
\end{enumerate}

So doing, one obtains a bipartite graph with $p$ ($=\card(P_1)$) black spots, $q$ ($=\card(P_2)$) white spots, no isolated vertex and integer multiplicities. Their set will be denoted $\diag$.

\bs
\input{unlabelled2_1}

\bs
The product formula now reads 

\begin{eqnarray}
\mathcal{H}(F,G)=\sum_{n\geq 0} \frac{z^n}{n!} \sum_{d\in diag\atop |d|=n} mult(d)\L^{\al(d)}\V^{\be(d)}
\end{eqnarray}

where $\al(d)$ (resp. $\be(d)$) is the ``white spots type'' (resp. the ``black spots type'') i.e. the multiindex $(\al_i)_{i\in \N^+}$ (resp. $(\be_i)_{i\in \N^+}$) such that $\al_i$ (resp. $\be_i$) is the number of white spots (resp. black spots) of degree $i$ ($i$ lines connected to the spot) and $mult(d)$ is the number of pairs of unordered partitions of $[1\cdots |d|]$ (here $|d|=|\al(d)|=|\be(d)|$ is the number of lines of $d$) with associated diagram $d$.


\ss
Now the natural question arises : \\
{\it Q1) ``Is there a (graphically) natural multiplicative structure on $\diag$ such that the arrow 
\begin{equation}
	d \mapsto \L^{\al(d)}\V^{\be(d)}
\end{equation}
be a morphism ?''}

\ss
The answer is ``yes''. The desired product just consists in concatenating the diagrams (the result, i. e. the diagram obtained in placing $d_2$ at the right of $d_1$, will be denoted $[d_1|d_2]_D$). One must check that this product is compatible with the permutation (of white and black spots between themselves) equivalence, which is rather straightforward (see \cite{GOF4}). We have

\begin{proposition} Let $\diag$ be the set of diagrams (including the void one).\\
i) The law $(d_1,d_2)\mapsto [d_1|d_2]_D$ endows $\diag$ with the structure of a commutative monoid with the void diagram as neutral (this diagram will, therefore, be denoted $1_{\diag}$).\\
ii) The arrow $d \mapsto \L^{\al(d)}\V^{\be(d)}$ is a morphism of monoids, the codomain of this arrow being the monoid of (commutative) monomials in the alphabet $\L\cup \V$ i.e. 
$$\frak{MON}(\L\cup\V)=\{\L^\al \V^\be\}_{\al,\be\in (\N^+)^{(\N)}}=
\bigcup_{n,m\geq 1}\big\{L_1^{\al_1}L_2^{\al_2}\cdots L_n^{\al_n}V_1^{\be_1}V_2^{\be_2}\cdots V_m^{\be_m}\big\}_{\al_i,\be_j\in \N}.$$
iii) The monoid $(\diag,[-|-]_D,1_{\diag})$ is a free commutative monoid. Its letters are the connected (non void) diagrams.  
\end{proposition}  

\begin{rem} The reader which is not familiar with the algebraic structure of $\frak{MON}(\X)$ can find rigourous definitions in paragraph \mref{fcmon} where this structure is needed to prepare the proofs relating to deformations.
\end{rem}

\section{Non-commutative lifting (classical case)}

The ``classical'' construction of the Hopf algebra $\LDIAG$ was announced in \cite{GOF4}. We give below the proofs using a coding through ``lists of monomials'' which prepares the deformed (quantum) case. The entries of a list can be considered as ``coordinate functions'' for the diagrams (see introduction of section \mref{classical}).

\subsection{Free monoids}\label{fcmon}

We here recall the construction of the free and free commutative monoids generated by a given set of variables (i.e. an alphabet).\\
Let $\X$, be a set. We denote by $\X^*$ the set of lists of elements of $\X$, including the void one. In many works, and in the sequel, the list $[x_1,x_2,\cdots ,x_n]$ will be denoted as a word $x_1x_2\cdots x_n$ so that the concatanation of two lists  $[x_1,x_2,\cdots ,x_n],\ [y_1,y_2,\cdots ,y_m]$ is just the word 
$x_1x_2\cdots x_ny_1y_2\cdots y_m$. For this (associative) law, the void list $[\ ]$ is neutral and will therefore be denoted $1_{\X^*}$

\ss
Similarly, we denote $\N^{(\X)}$ \cite{B_Alg_III} the set of multisubsets of $\X$ (i.e. the set of - multiplicity - mappings with finite support $\X\mapsto \N$). Every element $\al$ of $\N^{(X)}$ can be written multiplicatively, following the classical multiindex notation 
\begin{equation}
	\X^{\al}=\prod_{x\in \X} x^{\al(x)}
\end{equation}
and the set $\frak{MON}(X)=\{\X^{\al}\}_{\al\in \N^{(X)}}$ is exactly the set of (commutative) monomials with variables in $\X$. It is a monoid, indeed a (multiplicative) copy of $\N^{(X)}$ as $\X^\al\X^\be=\X^{\al+\be}$. The subset of its non-unit elements is a semigroup which will be denoted by $\frak{MON}^+(X)$ ($=\frak{MON}(X)-\{\X^0\}$).

\subsection{Labelling the nodes}

There are (at least) two good reasons to look for non-commutative structures which may serve as a noncommutative pullback for $\diag$.
\begin{itemize}
	\item Rows and Columns of matrices are usually (linearly) ordered and we have seen that a diagram is not represented by a matrix but by a class of matrices
	\item The ``expressive power'' of $\diag$ and its algebra is not sufficient to connect it to other (non-commutative or non-cocommutative) algebras relevant in contemporary physics   
\end{itemize}

The solution (of the non-deformed problem \cite{GOF4}) is simple and consists in labelling the nodes from left to right and from ``$1$'' to the desired amount as follows.

\bs
\input{labelled2_1}

\bs
The set of these graphs (i.e. bipartite graphs on some product $[1..p]\times [1..q]$ with no isolated vertex) will be denoted $\ldiag$. The composition law is, as previously, the concatenation in the obvious sense. Explicitely, if $d_i,\ i=1,2$ are two diagrams of dimensions $[1..p_i]\times [1..q_i]$, one relabels the black (resp. white) spots of $d_2$ from $p_1+1$ to $p_1+p_2$ (resp. from $q_1+1$ to $q_1+q_2$) the result will be noted $[d_1|d_2]_L$. One has 

\begin{proposition} Let $\ldiag$ be the set of labelled diagrams (including the void one).\\
i) The law $(d_1,d_2)\mapsto [d_1|d_2]_L$ endows $\ldiag$ with a structure of noncommutative monoid with the void diagram ($p=q=0$) as neutral (which will, therefore, be denoted $1_{\ldiag}$).\\
ii) The arrow from $\ldiag$ to $\diag$, which consists in ``forgetting the labels of the vertices'' is a morphism of monoids.\\
iii) The monoid $(\ldiag,[-|-]_L,1_{\ldiag})$ is a free (noncommutative) monoid. Its letters are the irreducible diagrams (denoted, from now on $irr(\ldiag)$).  
\end{proposition}  

\begin{rem}
i) In a general monoid $(M,\star,1_M)$, the irreducible elements are the elements $x\neq 1_M$ such that $x=y\star z\Longrightarrow 1_M\in \{y,z\}$.\\
ii) It can happen that an irreducible of $\ldiag$ has an image in $\diag$ which splits as shows the simple example of the cross defined by the incidence matrix ${\tiny\pmatrix{0 & 1\cr 1 & 0}}$.
\end{rem}

\subsection{Coding $\ldiag$ with ``lists of monomials''}

One can code every labelled diagram by a ``list of (commutative) monomials'' in the following way. 
\begin{itemize}
	\item Let $\X=\{x_i\}_{i\geq 1}$ an infinite set of indeterminates and $d\in \ldiag_{p\times q}$ a diagram ($\ldiag_{p\times q}$ is the set of diagrams with $p$ black spots and $q$ white spots).
	\item Associate to $d$ the multiplicity function $[1..p]\times [1..q]\ra \N$ such that $d(i,j)$ is the number of lines from the black spot $i$ to the white spot $j$.
	\item The code associated to $d$ is $\varphi_{lm}(d)=[m_1,m_2,\cdots ,m_p]$ such that $m_i=\prod_{j=1}^q x_j^{m(i,j)}$
\end{itemize}
\noindent

\bs
\input{coding1} 
 
\bs
As a data structure, the lists of monomials are elements of $(\frak{MON}^+(X))^*$, the free monoid whose letters are $\frak{MON}^+(X)=\frak{MON}(X)-\{\X^0\}$, the semigroup of non-unit monomials over $\X$.

\ss
It is not difficult to see that, through this coding, the concatenation reflects according to the following formula
\begin{equation}\label{sconc}
	\varphi_{lm}([d_1|d_2]_L)=\varphi_{lm}(d_1)\ast T_{max(IndAlph(\varphi_{lm}(l_1)))}(\varphi_{lm}(d_2))
\end{equation}
where $T_{p}$ is the translation operator which changes the variables according to\\ 
$T_p(x_i)=x_{i+p}$ (which corresponds to the relabelling of the white spots) and $p_1$ is the number of black spots of $d_1$.\\
For example, one has
\begin{equation}
	T_2([x_2^2x_3,x_1x_2x_3^3,x_3x_4^2])=[x_4^2x_5,x_3x_4x_5^3,x_5x_6^2]\ ;\ T_6([x_1,x_2^2])=[x_7,x_8^2]
\end{equation}


\section{The (classical) Hopf algebra $\LDIAG$}\label{classical}

In \cite{GOF4}, we constructed a structure of Hopf algebra structure on the space of diagrams $\LDIAG$.
The aim of this section is to give complete proofs and details for this construction through the use of the special space of coordinates constructed above (the complete vector  of coordinates of a diagram being its code).   

\subsection{The monoid $(\frak{MON}^+(X))^*$ and the submonoid of codes of diagrams}

Formula \mref{sconc} can be witten with the lists 

\begin{equation}\label{lists_sconc}
l_1\bar\ast l_2=l_1\ast T_{max(IndAlph(l_1))}(l_2)
\end{equation}	

defines a structure of monoid on $(\frak{MON}^+(X))^*$ (the set of lists of non-unit monomials) with the empy list as neutral (i.e. $[\ ]$ which will, therefore, be denoted by ``$1_{(\frak{MON}^+(X))^*}$'' or simply ``$1$'' when the context is clear).\\  
We will return to this construction (called shifting \cite{FPSAC07}) later.\\
The alphabet of a list is the set of variables occuring in the list. Formally
\begin{equation}
	Alph([m_1,m_2,\cdots m_n])=\bigcup_{1\leq i\leq k} Alph(m_i)
\end{equation}
where, classically, for a monomial $m=\X^{\al}$, $Alph(m)=\{x_i\}_{\al(i)\not= 0}$.\\
Now, we can define the ``compacting operator'' on $\ncp{k}{\frak{MON}^+(X)}$ by its action on the lists. This operator actually removes the holes in the alphabet of a list by pushing to the left the indices which are at the right of a hole. For example (we denote $cpt$ the operator)

\begin{equation}
cpt([x_2^2x_{10},x_3x_4x_8^3,x_3x_4^2])=[x_1^2x_5,x_2x_3x_4^3,x_2x_3^2]
\end{equation}

the alphabet of the list in the LHS is $Alph(l)=Alph([x_2^2x_{10},x_3x_4x_8^3,x_3x_4^2])=\{x_2,x_3,x_4,x_8,x_{10}\}$, its indices are $IndAlph(l)=\{2,3,4,8,10\}$ and the reindexing function is the unique stictly increasing mapping from $\{2,3,4,8,10\}$ to $[[5]]$. The compacting operator is, here, just the substitution 
$$
x_1\leftarrow x_2;\ x_2\leftarrow x_3;\ x_3\leftarrow x_4;\ x_4\leftarrow x_8;\ x_5\leftarrow x_{10}
$$


The formal definitions are the following 
\begin{itemize}
	\item $IndAlph(l)=\{i\ |\ x_i\in Alph(l)\}$ 
	\item $l$ being given, let $\phi_l$ be the unique increasing mapping from $IndAlph(l)$ to $[[card(IndAlph(l))]]$ (in fact, $card(IndAlph(l))=card(Alph(l))$) 
	\item let $s_l$ be the substitution $x_i\leftarrow x_{\phi_l(i)}$ in the monomials.
	\item Then, if $l=[m_1,m_2,\cdots m_n]$, $cpt(l)=[s_l(m_1),s_l(m_2),\cdots s_l(m_n)]$.
\end{itemize}

\begin{definition}
The compacting operator $cpt\ :\ \ncp{k}{\frak{MON}^+(X)}\mapsto \ncp{k}{\frak{MON}^+(X)}$ is the extension by linearity of the mapping $cpt$ defined above. 
\end{definition}

\newpage
It can be checked easily that, for $l\in (\frak{MON}^+(X))^*$, the following are equivalent
\begin{enumerate}
\item $cpt(l)=l$
\item $IndAlph(l)=[[card(IndAlph(l))]]$
\item there is no hole in $Alph(l)$ that is there exists no $i\geq 1$ s.t. $x_i\notin Alph(l)$ and $x_{i+1}\in Alph(l))$
\item $l$ is the code of some (then unique) diagram $d$.
\end{enumerate}

\ss 
It follows from the preceding properties that $cpt$ is a projector with range the subspace $\mathcal{C}_{ldiag}$ of $\ncp{k}{\frak{MON}^+(\X)}$ generated by the codes of the diagrams. Formula \mref{sconc} proves that $\mathcal{C}_{ldiag}$ is closed under the shifted concatenation defined by \mref{lists_sconc}. More precisely

\begin{proposition}
The algebra $\mathcal{C}_{ldiag}$ is a free algebra on the set of the codes of irreducible diagrams.   	
\end{proposition}

These codes are also the non-empty lists $l$ which are compact (i.e. $cpt(l)=l$) and cannot be factorized into a product of two non-empty lists i.e. $l=l_1*l_2;\ l_i\not= [\ ]$ (one can check easily that, if $l_1*l_2$ is compact, so are $l_1$ and $l_2$). 

\subsection{The Hopf algebras $\mathcal{C}_{ldiag}$ and $\LDIAG$}

The algebra $\LDIAG$ is endowed with a structure of a bi-algebra by the comultiplication

\begin{equation}
	\Delta_{BS}(d)=\sum_{I+J=[1..p]} d[I]\otimes d[J]
\end{equation}
where $p$ is the number of black spots and $d[I]$ is the ``restriction'' of $d$ to the black spots selected by $I\subset [1..p]$.\\
On the other hand, we have the standard Hopf algebra structure on the Free algebra, expressed in terms of concatenation and subwords \cite{Ha,Re}. Let $\Aa$ be an alphabet (a set of letters) and $w\in \Aa^*$ a word, if we write $w$ a a sequence of letters $w=a_1a_2\cdots a_n;\ a_i\in \Aa$, the length $|w|$ of $w$ is $n$ and if $I=\{i_1,i_2,\cdots i_k\}\subset [1..n]$, the subword $w[I]$ is $a_{i_1}a_{i_2}\cdots a_{i_k}$ (this notation is slightly different from that of \cite{Re} where it is $w|_I$). Then, the free algebra $\ncp{k}{\Aa}$ is a Hopf algebra with comultiplication \cite{Re,Ha}.

\begin{equation}\label{liehopf}
	\Delta_{LieHopf}(w)=\sum_{I+J=[1..n]}w[I]\otimes w[J]. 
\end{equation}

One has the following relation between restrictions of diagrams and subwords
\begin{equation}
	\varphi_{lm}(d[I])=cpt(\varphi_{lm}(d)[I])
\end{equation}
this suggests that the coproduct
\begin{equation}
	\Delta_{list}(l)=\sum_{I+J=[1..n]} cpt(l[I])\otimes cpt(l[J])
\end{equation}
could be a Hopf algebra comultiplication for the shifted algebra $(\ncp{k}{\frak{MON}^+(\X)},\bar\ast,[\ ])$. Unfortunately, this fails due to the lack of counit (i and ii of the following Theorem), but the ``ground subalgebra''  $\mathcal{C}_{ldiag}$ is a genuine Hopf algebra (which is exactly what we do need here).

%\newpage
\begin{theorem}
Let $\A=(\ncp{k}{\frak{MON}^+(\X)},\bar\ast,[\ ])$ be the algebra of lists of (non-unit) monomials endowed with the shifted concatenation of formula \mref{lists_sconc}. Then\\ 
i) $\A$ is a free algebra.\\
ii) The coproduct $\Delta_{list}$ (recalled below) is co-associative and a morphism of algebras $\A\mapsto \A\otimes \A$ (i.e. $\A$ is a bi-algebra without counit).\\

\begin{equation}
	\Delta_{list}(l)=\sum_{I+J=[1..n]} cpt(l[I])\otimes cpt(l[J])
\end{equation}

iii) The algebra $\mathcal{C}_{ldiag}$ is a sub- algebra and coalgebra of $\A$ which is a Hopf algebra for the following co-unit and antipode.

\begin{itemize}
	\item {\sc Counit}
\begin{equation}
	\ep(l)=\delta_{l,[\ ]} \mathrm{\hspace{2cm }(Kronecker\ delta)}
\end{equation}
\item {\sc Antipode}
\begin{equation}
	S(l)=
\sum_{r\geq 0}\sum_{I_1+I_2+\dots I_r=[1..p]\atop I_j\not= \emptyset} (-1)^r cpt(l[I_1])cpt(l[I_2])\cdots cpt(l[I_r])
\end{equation}		
\end{itemize}
\end{theorem}

\Proof i) Throughout the proof, we will denote $\ast$ the concatenation between lists and $\bar\ast$ the shifted concatenation defined by formula \mref{lists_sconc}. Let's first remark that, if $l=l_1\bar\ast l_2$, then $max(IndAlph(l_1))<min(IndAlph(l_2))$. This leads us to define, for a (non-shifted) factorization 
$l=l_1\ast l_2=l[1..t]\ast l[t+1..p]$ ($p=|l|$) a gauge of the degree of overlapping of the intervals (of integers) $[1..max(IndAlph(l1))]$ and $[min(IndAlph(l2))..\infty[$, thus the function 

\begin{eqnarray}
\om_l(t)=card\bigg([1..max(IndAlph(l[1..t])]\cap [min(IndAlph(l[t+1..p])..\infty[\bigg)=\cr
\bigg(max(IndAlph(l[1..t]))-min(IndAlph(l[t+1..p]))+1\bigg)^+	
\end{eqnarray}
  
(we recall that, for a real number $x$, $x^+$ is its positive part i.e. $x^+=max(x,0)=\frac{1}{2}(|x|+x)$ \cite{B_Alg_VI}). It can be easily checked that the points $t$ where $\om_l(t)=0$ determine the (then unique) factorisation of $l$ in irreducibles. It follows that the monoid $((\frak{MON}^+(\X))^*,\bar\ast,[\ ])$ is free and so is its algebra $(\ncp{k}{\frak{MON}^+(\X)},\bar\ast,[\ ])$.

\ss
ii) If we denote $\Delta : \A\mapsto \A\otimes \A$ the standard coproduct given, for a list $l$ of length $p$, by formula \mref{liehopf}, one can remark that 

\begin{enumerate}
	\item $cpt(l_1)\bar\ast cpt(l_2)=cpt(l_1\bar\ast l_2)$
	\item $\Delta_{list}=(cpt\otimes cpt)\circ \Delta$
	\item $\Delta_{list}\circ cpt=\Delta_{list}$
	\item $(\forall n\in \N) (cpt(T_n(l))=cpt(l))$
	\item $(\forall n\in \N) (\Delta\circ T_n=(T_n\otimes T_n)\circ \Delta)$
\end{enumerate}
	
{\sc Coassociativity of $\Delta_{list}$}\pointir

\bs 
One has

\begin{eqnarray}
(\Delta_{list}\otimes Id)\circ\Delta_{list}=(\Delta_{list}\otimes Id)\circ (cpt\otimes cpt)\circ \Delta=`\cr
((\Delta_{list}\circ cpt)\otimes cpt)\circ \Delta=
(\Delta_{list}\otimes cpt)\circ \Delta=\cr
(((cpt\otimes cpt)\circ \Delta)\otimes cpt)\circ \Delta=\cr
(cpt\otimes cpt\otimes cpt)\circ (\Delta\otimes Id)\circ \Delta=
(cpt\otimes cpt\otimes cpt)\circ (Id\otimes \Delta)\circ \Delta\cr
(cpt\otimes ((cpt\otimes cpt)\circ \Delta))\circ \Delta=(cpt\otimes \Delta_{list})\circ \Delta=\cr
(cpt\otimes (\Delta_{list}\circ cpt))\circ \Delta=\cr
(Id\otimes \Delta_{list})\circ (cpt\otimes cpt)\circ \Delta=
(Id\otimes \Delta_{list})\circ \Delta_{list}
\end{eqnarray}

{\sc $\Delta_{list}$ is a morphism}\pointir
 
\bs 
For two lists $u,v\in$, let us compute $\Delta_{list}(u\bar\ast v)$. With $p=max(IndAlph(u))$, one has  

\begin{eqnarray}\label{morph_init}
\Delta_{list}(u\bar\ast v)=(cpt\otimes cpt)\circ \Delta(l_1\ast T_p(v))=\cr
(cpt\otimes cpt)(\Delta(u)\ast^{\otimes 2} \Delta(T_p(v)))=	\cr
(cpt\otimes cpt)(\Delta(u)\ast^{\otimes 2} (T_p\otimes T_p)\Delta (v)=	\cr
(cpt\otimes cpt) (\sum_{(1)(2)} u_{(1)}\otimes u_{(2)})\ast^{\otimes 2} (T_p\otimes T_p) 
(\sum_{(3)(4)} v_{(3)}\otimes v_{(4)})=\cr
(cpt\otimes cpt) (\sum_{(1)(2)(3)(4)} u_{(1)}\ast T_{p_1}(T_{p-p_1}(v_{(3)}))\otimes 
u_{(2)}\ast T_{p_2}(T_{p-p_2}(v_{(4)})))
\end{eqnarray}
with, for each term in the sum 
$$
p_1=max(IndAlph(u_{(1)}))\leq p\ ;\ p_2=max(IndAlph(u_{(2)}))\leq p
$$
so, the quantity in \mref{morph_init} is
\begin{eqnarray}
(cpt\otimes cpt) (\sum_{(1)(2)(3)(4)} u_{(1)}\bar\ast (T_{p-p_1}(v_{(3)}))\otimes 
u_{(2)}\bar\ast (T_{p-p_2}(v_{(4)})))=\cr
\sum_{(1)(2)(3)(4)} cpt(u_{(1)}\bar\ast (T_{p-p_1}(v_{(3)})))\otimes 
cpt(u_{(2)}\bar\ast (T_{p-p_2}(v_{(4)})))=\cr
\sum_{(1)(2)(3)(4)} \bigg(cpt(u_{(1)})\bar\ast cpt(T_{p-p_1}(v_{(3)}))\bigg)\otimes 
\bigg(cpt(u_{(2)})\bar\ast cpt(T_{p-p_2}(v_{(4)}))\bigg)=\cr
\sum_{(1)(2)(3)(4)} \bigg(cpt(u_{(1)})\bar\ast cpt(v_{(3)})\bigg)\otimes 
\bigg(cpt(u_{(2)})\bar\ast cpt(v_{(4)})\bigg)=\cr
\bigg(\sum_{(1)(2)} cpt(u_{(1)})\otimes cpt(u_{(2)})\bigg)\bar\ast^{\otimes 2}  
\bigg(\sum_{(3)(4)} cpt(v_{(3)})\otimes cpt(v_{(4)})\bigg)=\cr
\Delta_{list}(u)\bar\ast^{\otimes 2} \Delta_{list}(v)
\end{eqnarray}
 
\bs
iii) As $\mathcal{C}_{ldiag}$ is generated by the image of $cpt$ it is clear that this space is a sub-coalgebra of $\A$. Moreover, $cpt$ is a (multiplicative) morphism $\A\mapsto \A$ and thus its image $\mathcal{C}_{ldiag}$ is a subalgebra of $\A$. Let us prove what is missing to make complete the Hopf algebra structure.

\bs 
{\sc $\ep$ is a counit}\pointir
 
\ss 
Let $l=cpt(l)$ be a compact list. We remark that, for any list $u$, one has $cpt(u)=[\ ]\Longleftrightarrow u=[\ ]$. Then, with $\mu_l\ :\ k\otimes \A\mapsto \A$ the scaling operator

\begin{eqnarray}
\mu_l(\ep\otimes	Id)\Delta_{list}(l)=\sum_{I+J=[1..n]} \ep(cpt(l[I]))cpt(l[J])=\cr
\hspace{-2cm}\sum_{I+J=[1..n]\atop I=\emptyset} \ep(cpt(l[I]))cpt(l[J]) +
\sum_{I+J=[1..n]\atop I\not=\emptyset} \ep(cpt(l[I]))cpt(l[J])=cpt(l)+0=l
\end{eqnarray}

the proof of the fact that $\ep$ is a left counit is similar.

\bs
{\sc $S$ is the antipode}\pointir
 
\ss 
One has $\mathcal{C}_{ldiag}=k.1\oplus ker(\ep)$, let us denote $Id^+$ the projection 
$\mathcal{C}_{ldiag}\mapsto ker(\ep)$ according to this decomposition.\\ 
Then, for every list $l$, 
$$
\sum_{r\geq 0}\sum_{I_1+I_2+\dots I_r=[1..p]\atop I_j\not= \emptyset} (-1)^r cpt(l[I_1])cpt(l[I_2])\cdots cpt(l[I_r])
$$ 
is well defined as the first sum is locally finite. Thus, the operator 
$$
\sum_{r\geq 0}\sum_{I_1+I_2+\dots I_r=[1..p]\atop I_j\not= \emptyset} 
(-1)^r \underbrace{(Id^+*Id^+*\cdots *Id^+)}_{r\ times}
$$
is well defined and is the convolutional inverse of $Id$.

\subsection{Subalgebras of $\LDIAG$}
 
\subsubsection{Graphic primitive elements}\hspace{1mm}

\bs
The problem of Graphic Primitive Elements (GPE) is the following.\\
Let $\H$ be a Hopf algebra with (linear) basis $G$, a set of graphs. The GPE are the primitive elements $\Gamma\in G$ which are primitive i.e.
\begin{equation}
\Gamma	\textrm{ is a GPE} \Longleftrightarrow \Gamma\in G \textrm{ and } \Delta(\Gamma)=\Gamma\otimes 1+1\otimes \Gamma
\end{equation}
it is not difficult to check that, in any case, the subalgebra $\H^{\textrm{\tiny GPE}}$ generated by these elements is also a sub-coalgebra.\\
We do the extra hypothesis (which is often fulfilled) 
\begin{equation}\label{extrahyp}
	1_\H\in G \textrm{ and } (\Gamma\in G-\{1_\H\}\Longrightarrow \ep(\Gamma)=0). 
\end{equation}
Then (if \mref{extrahyp} is fulfilled) $\H^{\textrm{\tiny GPE}}$ is a sub-Hopf algebra as the antipode of a product $\Gamma_1\Gamma_2\cdots \Gamma_p$ of (GPE) is 
\begin{equation}
	S(\Gamma_1\Gamma_2\cdots \Gamma_p)=(-1)^p\ \Gamma_p\Gamma_{p-1}\cdots \Gamma_1.
\end{equation}
The following proposition helps to determine $\LDIAG^{\textrm{\tiny GPE}}$.

\begin{proposition} In $\LDIAG$ (with basis $G=\ldiag$), the following are equivalent\\
i) $d$ is a GPE\\
ii) $d$ has only one black spot.
\end{proposition}

Then, the Hopf algebra $\LDIAG^{\textrm{\tiny GPE}}$ is generated by the product of ``one-black-spot'' diagrams.

\bs
\input{GPE2}

\bs

\subsubsection{Level subalgebras}\hspace{1mm}

\bs
One can impose also limitations on the ingoing degrees of the white spots in a way compatible with the coproduct. In this case, one defines an infinity of Hopf-subalgebras of $\LDIAG$ which we will call ``level subalgebras''.\\
More precisely, given an integer $l>0$, one can ask for spaces generated by the diagrams $d$ for which every white spot has an ingoing degree $\leq l$. This amounts to say that the ``white spots type'' of every diagram $d$ is of the form 
$$
\al(d)=(\al_1,\al_2,\cdots \al_k,0,0\cdots 0,\cdots)\ ;\ (\textrm{ all the } \al_i\leq l\textrm{ for }i\leq k\textrm{ and }\al_i=0\textrm{ for }i>k)
$$ 
Let us denote $\LDIAG^{\leq l}$ the subspace generated by these diagrams. One has a chain of Hopf algebras

\begin{equation}
\hspace{-1.5cm}	\LDIAG^{\leq 1}\subset \LDIAG^{\leq 2}\subset \cdots 
\LDIAG^{\leq l}\subset \LDIAG^{\leq l+1}\subset\cdots  \subset\LDIAG  
\end{equation}

In the next paragraph, we will specially be interested by 
$$
\LBELL=\LDIAG^{\leq 1}\cap \LDIAG^{\textrm{\tiny GPE}}.
$$

\bs
\subsubsection{$\BELL$ and $\LBELL$}\hspace{1mm}

\bs
The algebras $\BELL$ and $\LBELL$ were defined in \cite{GOF9}.\\
{\tt be done : following Allan, explain the link with coherent states}.\\

The algebra $\LBELL$ is the intersection $\LDIAG^{\leq 1}\cap \LDIAG^{\textrm{\tiny GPE}}$ and then, as they are subspaces generated by subsets of $\ldiag$, $\LBELL$ is generated by diagrams that 
\begin{itemize}
	\item are concatenation of one-black-spot-diagrams
	\item the ingoing degree of every white spot is one.
\end{itemize}
Let $d_k$ be the diagram with code $[x_1,x_2,\cdots x_k]$. $\LBELL$ is generated by concatenations of these diagrams. Indeed, the diagrams $d_k$ are a subalphabet of the free monoid $\ldiag$ so that they generate a free submonoid which we will denote here $\lbell$.

\bs
\input{lbell}
 
\bs
As $\LDIAG$, $\LBELL$ is an envelopping algebra. It is generated by the primitive $d_k$ ($\Delta_{WS}(d_k)=d_k\otimes 1+ 1\otimes d_k$).
 

\section{The quantized case}
    
\subsection{Counting crossings ($q_c$) and superpositions ($q_s$)}

The preceding coding is particularly well adapted to the the deformation we want to construct here. The philosophy of the deformed product is expressed by the descriptive formula.
\begin{equation}
	[d_1|d_2]_{L(q_c,q_s)}=\sum_{cs(?)\ all\ crossing\ and\atop superpositions\ of\ black\ spots} 
	q_c^{nc\times weight}q_s^{weight\times weight} cs([d_1|d_2]_{L})
\end{equation}
where 
\begin{itemize}
	\item $q_c,q_s\in \C$ or $q_c,q_s$ formal. These and other cases being unified with considering the set of coefficients as taken in a ring $K$. 
	\item the exponent of $q_c^{nc\times weight}$ is the number of crossings of ``what crosses'' times its weight
	\item the exponent of $q_s^{weight\times weight}$ is the product of the weights of ``what is overlapped''  
	\item $cs(?)$ are the diagrams obtained from $[d_1|d_2]_L$ by the process of crossing and superposing the black spots of $d_2$ to those of $d_1$, the order and distinguishability of the black spots of $d_1$ (i.e. $d_2$) being preserved.
\end{itemize}

What is striking is that this law is associative. This result will be established after the following paragraph.

\bs
\input{cross1}

\bs
\input{detail2}

\subsection{Modified laws}

Introduction : Dual laws, shuffle, infiltration, Hoffmann.

\subsection*{$\bullet$ Twisting}

\begin{proposition} Let $A=(A_n)_{n\in \N}$ a graded semigroup and $A^*$ the set of lists 
(denoted $[a_1, a_2, \cdots a_k]$) with letters in $A$.\\
For convenience we define the operator $\ast$ (left append) $A\times A^*\mapsto A^*$ by
\begin{equation}
a\ast [b_1, b_2, \cdots b_n]:=[a,b_1, b_2, \cdots b_n]
\end{equation}

Let $q_c,q_s\in k$ be two elements in a ring $k$. We define on $k<A>=k[A^*]$ a new law $\ua$ by 
\begin{eqnarray}\label{infiltr}
\hspace{-15mm} w\ua 1_{A^*}=1_{A^*}\ua w=w\cr
\hspace{-15mm} a\ast u \ua b\ast v=a\ast (u\ua b\ast v)+ q_c^{|a\ast u||b|} b\ast (a\ast u\ua v)+ q_c^{|u||b|}q_s^{|a||b|} ab\ast (u\ua v)
%\nonumber
\end{eqnarray}
where the weights ($|x|=n$ if $x\in A_n$) are extended additively to lists by
$$
\Big|[a_1,a_2,\cdots ,a_k]\Big|=\sum_{i=1}^k |a_i|
$$
Then the new law $\ua$ is graded, associative with $1_{A^*}$ as unit.\\
\end{proposition}

\Proof 
It suffices to prove the identity $x\inf (y\inf z)=(x\inf y)\inf z$ ; $x,y,z$ being lists (as the two members are trilinear). It is obviously true when one of the factors is the void list. Let's show it when the three factors are non-void (throughout the computation, the law $*$ will have priority over other operators).

\begin{eqnarray}
(a\ast u\inf b\ast v)\inf c\ast w =\cr
\big(a\ast (u\inf b\ast v)+ q^{|u||b|}t^{|a||b|} \2m{b}{a}(u\inf v)+q^{|a\ast u||b|} b(a\ast u\inf v)\big)\inf c\ast w =\cr
\Big[a\ast ((u\inf b\ast v)\inf c\ast w)+q^{(|u|+|b\ast v|)|c|}t^{|a||c|}\2m{c}{a}((u\inf b\ast v)\inf w)\cr
+q^{(|a\ast u|+|b\ast v|)|c|}c\ast (a\ast (u\inf b\ast v)\inf w) \Big] +\cr
\Big[q^{|u||b|}t^{|a||b|} \2m{b}{a}(u\inf v\inf c\ast w) +q^{|u||b|+(|u|+|v|)|c|}t^{|a||b|}t^{(|a|+|b|)|c|}\3m{c}{b}{a}(u\inf v\inf\ w)+\cr
q^{|u||b|+(|a\ast u|+|b\ast v|)|c|}t^{|a||b|}c ((\2m{b}{a}(u\inf v))\inf w)\Big]+\cr
\Big[q^{|a\ast u||b|}b((a\ast u\inf v)\inf c\ast w)+q^{|a\ast u||b|+
(|a\ast u|+|v|)|c|}t^{|b||c|}\2m{c}{b}(au\inf v\inf w)+\cr 
q^{|a\ast u||b|+(|a\ast u|+|b\ast v|)|c|}c(b(a\ast u\inf v)\inf w)\Big]
\end{eqnarray} 

\begin{eqnarray}
a\ast u\inf (b\ast v\inf c\ast w)=\cr
a\ast u\inf \big(b\ast (v\inf c\ast w)+q^{|v||c|}t^{|b||c|} \2m{c}{b}(v\inf w)+q^{|b\ast v||c|} c(b\ast v\inf w)\big)=\cr
\Big[a\ast (u\inf b\ast (v\inf c\ast w))+ q^{|u||b|}t^{|a||b|}\2m{b}{a}(u\inf v\inf c\ast w)+q^{|a\ast u||b|}b(a\ast u\inf v\inf c\ast w)\Big]+\cr
\Big[q^{|v||c|}t^{|b||c|}a\ast (u\inf \2m{c}{b}(v\inf w)) +q^{|v||c|+|u|(|c|+|b|)}t^{|b||c|+|a|(|b|+|c|)}\3m{c}{b}{a}(u\inf v\inf w)+\cr
q^{|v||c|+|a\ast u|(|b|+|c|)}t^{|b||c|}\2m{c}{b}(a\ast u\inf v\inf w)\Big]+\cr
\Big[q^{|b\ast v||c|}a\ast (u\inf c(b\ast v\inf w))+q^{(|u|+|b\ast v|)|c|}t^{|a||c|}\2m{c}{a}(u\inf b\ast v\inf w)+\cr q^{(|a\ast u|+|b\ast v|)|c|}c\ast (a\ast u\inf b\ast v\inf w)\Big]
\end{eqnarray}

in the second expression, one gathers the three terms which we find first in the square brackets and we get   

\begin{eqnarray}
a\ast (u\inf b\ast (v\inf cw))+q^{|v||c|}t^{|b||c|}a\ast (u\inf \2m{c}{b}\ast (v\inf w))+\cr 
q^{|b\ast v||c|}a\ast (u\inf c\ast (b\ast v\inf w))=a\ast (u\inf b\ast v\inf c\ast w)
\end{eqnarray}

in the first expression, one gathers the three terms which we find last in the square brackets and we get   

\begin{eqnarray}
q^{(|a\ast u|+|b\ast v|)|c|}c\ast (a\ast (u\inf b\ast v)\inf w) +\cr 
q^{|u||b|+(|a\ast u|+|b\ast v|)|c|}t^{|a||b|} c \ast ((\2m{b}{a}\ast (u\inf v))\inf w) +\cr
q^{|a\ast u||b|+(|a\ast u|+|b\ast v|)|c|}c\ast (b\ast (a\ast u\inf v)\inf w)=\cr 
q^{(|au|+|bv|)|c|}c\ast (a\ast u \inf b\ast v \inf w)
\end{eqnarray}

and one finds the 7 terms expression

\begin{eqnarray}
a\ast (u\inf b\ast v \inf c\ast w) + q^{|a\ast u|}b\ast (a\ast u\inf v\inf c\ast w) +\cr 
q^{|a\ast u|+|b\ast v|}c\ast (a\ast u\inf b\ast v\inf w)+
 q^{|u||b|}t^{|a||b|} \2m{b}{a}\ast (u\inf v\inf c\ast w)+\cr 
 q^{(|u|+|b\ast v|)|c|}t^{|a||c|} \2m{c}{a}\ast (u\inf b\ast v\inf w)+\cr
 q^{|v||c|(|b|+|c|)|au|}t^{|b||c|} \2m{c}{b}\ast (a\ast u\inf v\inf w)\cr
+ q^{|v||c|+|u|(|c|+|b|)}t^{|b||c|+|a|(|b|+|c|)}\3m{c}{b}{a}\ast (u\inf v\inf w)
\end{eqnarray}

\cqfd

The framework with diagrams will need another proposition on shifted laws.

\subsection*{$\bullet$ Shifting}

We begin by the ``shifting lemma'' \cite{FPSAC07}.

\begin{lemma}
Let $\A$ be an associative algebra (which law will be denoted $\star$) and \\
$\A=\oplus_{n\in \N} \A_n$ a decomposition of $\A$ in direct sum. Let $T\in\mathrm{End}(\A)$ be an endomorphim of the algebra $\A$. We will denote $T^n=T\circ T\circ \cdots \circ T$ the n-th compositional power of $T$. 
We suppose that the shifted law 
\begin{equation}\label{shifted}
	a\ \bar\star\ b=a\star T^\al(b)
\end{equation}
for $a\in \A_\al$ is graded for the decomposition $\A=\oplus_{n\in \N} \A_n$.\\ 
Then, if the law $\star$ is associative so is the law $\bar\star$. 
\end{lemma}

\begin{rem} The hypothesis that the shifted law given by eq.\mref{shifted} be graded is automatically satisfied if $\A=\oplus_{n\in \N} \A_n$ is a graded algebra and if all the morphisms $T_n$ are of degree $0$.
\end{rem}


This lemma will be applied to the decomposition given by $n=sup(Alph(w))$ (the highest index of variables appearing in $w$) and the morphim given by $T(x_i)=x_{i+1}$.  

What does these statements mean for us ?\\
Here the graded semigroup is $\frak{MON}^+(X)$ and we do not forget the coding arrow $\varphi_{lm}: \ldiag \ra (\frak{MON}^+(X))^*$. The image of $\varphi_{lm}$ is exactly the set of lists of monomials 
$w=[m_1,m_2,\cdots ,m_k]$ such that the set of variables involved 
$Alph(w)$ is of the form $x_1\cdots x_l$ (the labelling of the white spots is without hole). By abuse of language we will say that a list of monomials ``is in $\ldiag$'' in this case. It is not difficult to see, from formulas (\ref{infiltr},\ref{shifted}) that if $w_i,\ i=1,2$ are in $\ldiag$ so are all the factors of $w_1\bar\ua w_2$, this defines a new law on $K[\ldiag]$ and this algebra will be called $\LDIAG(q_c,q_s)$. The properties of this algebra will be made precise in the following proposition.

\begin{proposition} Let $\mathcal{C}_{ldiag}$ be the subspace of $(K<\frak{MON}^+(\X)>,\bar\ua)$ generated by the codes of the diagrams (i.e. the lists $w\in \frak{MON}^+(\X)$ such that $Alph(w)$ is without hole). Then\\
i) $(\mathcal{C}_{ldiag},\bar\ua)$ is a unital subalgebra of $(K<\frak{MON}^+(\X)>,\bar\ua)$\\
ii) $(\mathcal{C}_{ldiag},\bar\ua)$ is a free algebra. More precisely, for any diagram decomposed in irreducibles 
$d=d_1.d_2\cdots d_k$
let 
\begin{equation}
B(d):=\varphi_{lm}(d_1)\bar\ua\varphi_{lm}(d_2)\cdots \bar\ua\varphi_{lm}(d_k)	
\end{equation}
then \\
$\al$) $(B(d))_{d\in ldiag}$ is a basis of $\mathcal{C}_{ldiag}$\\
$\be$) $B(d_1.d_2)=B(d_1)\bar\ua B(d_2)$
\end{proposition}

As $k[\ldiag]$ is isomorphic to $\mathcal{C}_{ldiag}$ as a linear space, we denote $\LDIAG (q_c,q_s)$ the new algebra structure of $k[\ldiag]$ inherited from $\mathcal{C}_{ldiag}$. one has 
\begin{equation}
	\LDIAG (0,0)\simeq \LDIAG;\ \LDIAG (1,1)\simeq \MQS
\end{equation}

\section{Coproducts}

Now, one has to define a parametrized (by, say, $t$) coproduct such that\\ 
$(\LDIAG(q_c,q_s),\ua, 1_{\ldiag},\Delta_t,\ep)$ be a graded bialgebra (the counity $\ep$, the same as in the non-deformed Hopf algebra in \cite{GOF4} is just the ``constant term'' linear form).\\
We will take advantage of the freeness of $\LDIAG(q_c,q_s)$ through the following lemma.

\begin{lemma}\label{coprodvar} Let $\Y$ be an alphabet, $k$ a ring and\\ 
$k<\Y>=k[\Y^*]$ be the free algebra constructed on $\Y$. For every mapping\\ 
$\Delta : A\ra k<\Y>\otimes k<\Y>$, we denote $\bd : k<\Y>\mapsto k<\Y>\otimes k<\Y>$ its extension as a morphism of algebras ($k<\Y>\otimes k<\Y>$ being endowed with its non-twisted structure of tensor product of algebras). Then, in order be coassociative, it is necessary and sufficient that 

\begin{equation}
	(\bd\otimes I)\circ \Delta\textrm{ and } (I\otimes \bd)\circ \Delta
\end{equation}
 coincide on $\Y$.
\end{lemma}

The preceding lemma expresses that, for a free algebra, the ``phase space'' of the possible coproducts is a linear subspace. This will be transparent in formula \mref{tline}. 

\ss
Now, we consider the structure constants of the coproduct of $\MQS$ \cite{DHT} expressed with respect to the family of free generators
$$
	\{MS_P\}_{P\in \mathcal{PM}^c}
$$
where $\mathcal{PM}^c$ is the set of connex packed matrices (similarly, $\mathcal{PM}$ is the set of packed matrices).

\begin{equation}
\Delta_{\MQS}(MS_P)=\sum_{Q,R\in \mathcal{PM}}\al_P^{Q,R}\ MS_Q\otimes MS_R
\end{equation}

For $d$, irreducible diagram, set 

\begin{equation}
	\Delta_1(d)=\sum_{d_1,d_2\in irr(\ldiag)} \al_{\varphi_{lm}(d)}^{\varphi_{lm}(d_1),\varphi_{lm}(d_2)} d_1\otimes d_2
\end{equation}

and $\Delta_0(d)=\Delta_{WS}(d)$. Then proposition \mref{coprodvar} proves that 

\begin{equation}\label{tline}
	\Delta_t=\overline{(1-t)\Delta_0+t\Delta_1}
\end{equation}
is a coproduct of graded bialgebra for $(\LDIAG(q_c,q_s),\ua,1_{\ldiag})$.

\ss
We sum up the results 

\begin{proposition}
i) With the operations defined above 
$$
\LDIAG(q_c,q_s,t)=\left(\LDIAG(q_c,q_s),\ua,1_{\ldiag},\Delta_t,\ep\right)
$$
is a Hopf algebra.\\ 
ii) At parameters $(0,0,0)$, one has $\LDIAG(0,0,0)\simeq \LDIAG$\\  
iii) At parameters $(1,1,1)$, one has $\LDIAG(1,1,1)\simeq \MQS$  
\end{proposition}

\begin{comm} {\tt (The following comment could apprear as ``concluding remarks'' what do you think ?)}\\ 
For a diagram $d$ with $r$ black spots, the code $[m_1,m_2,\cdots ,m_r]$ can be temporarily seen as a ``vector of coordinates'' for the given diagram, but we prefered to stick to the structure of list as, firstly, the dimension of the vector varies with the diagram and secondly, we had to concatenate the codes. The coordinate functions of the diagram $d$ are therefore the family $(a_i)_{i>0}$ defined by $a_i(d)=m_i$ for $i\leq r$ and $a_i(d)=0$ for $i>r$. In this perspective the ``$t$'' of our three parameters deformation is a quantization in the sense of Moyal's deformed products \cite{BFFLS} on the algebra of coordinate functions (but without first order condition, see also the introduction of \cite{CP}), by the formula
\begin{equation}
	a_{i_1}*a_{i_1}\cdots *a_{i_k}(d)=\mu(a_{i_1}\otimes a_{i_1}\otimes \cdots \otimes a_{i_k}(\Delta_t^{[k]}(d)))
\end{equation}
 where $\mu$ is the ordinary multiplication of polynomials.\\
 The crossing parameter $q_c$ is also a quantization parameter as, for $q_s=0$, one has
 
\begin{equation}
	code(d_1*d_2)=code(d_1)\sqcup_{q_c}T(code(d_2))
\end{equation}
 where $T$ is a suitable tranlation of the variables and $\sqcup_{q_c}$ is the quantum shuffle \cite{Ro} for the braiding on $V=\C[x_i;\ i\geq 1]$ defined by 
 
\begin{equation}
\hspace{-1.7cm} B(x_{i_1}^{\al_1}x_{i_2}^{\al_2}\cdots x_{i_k}^{\al_k}\otimes y_{j_1}^{\be_1}y_{j_2}^{\be_2}\cdots y_{j_l}^{\be_l})=
q_c^{(\sum \al_i)(\sum \be_j)}\ y_{j_1}^{\be_1}y_{j_2}^{\be_2}\cdots y_{j_l}^{\be_l}\otimes x_{i_1}^{\al_1}x_{i_2}^{\al_2}\cdots x_{i_k}^{\al_k}	
\end{equation}

Let us add that $q_s$ and $q_c$ are structurally different as $q_s$ is the coefficient of a perturbation of the shuffle product (better seen on the coproduct). This kind of perturbation occurs in various domains as : computer science by means of the infiltration product introduced by Ochsenschl\"ager \cite{Oc} (see also \cite{DL} and \cite{DFLL}), algebra of the Euler-Zagier sums \cite{Ho} and noncommutative symmetric functions \cite{DHT}. The mathematics of this dual aspect is of geometrical nature and will be developped in \cite{DKPTT}.
 
\end{comm}


\section{$\LDIAG(q_c,q_s,t)$ and its specializations}

Graphic primitive elements, BELL, LBELL, Zagier, Foissy and the general picture.

\section{Conclusion}

Discuss the self-dual deformation. 

\section*{References}
\begin{thebibliography}{ABC}
\bibitem{BR} {\sc J. Berstel, C. Reutenauer}, {\it Rational series and their 
languages EATCS Monographs on Theoretical Computer Science}, Springer (1988).
%
\bibitem{BDK} {\sc C. Bertelle, G. H. E. Duchamp, K. Khatatneh}, {\it Tables, 
Memorized Semirings and Applications}, arXiv: {\tt cs.MA/0502081}.
%
\bibitem{BBM} {\sc C. M. Bender, D. C. Brody, and B. K. Meister}, 
Quantum field theory of partitions, J. Math. Phys. Vol 40 (1999)
%
\bibitem{B_Alg_III} {\sc Bourbaki N.}, {\it Algebra, chapter III}, Springer
%
\bibitem{B_Alg_VI} {\sc Bourbaki N.}, {\it Algebra, chapter VI}, Springer
%
\bibitem{B_ST} {\sc Bourbaki N.}, {\it Theory of sets}, Springer
%
\bibitem{Ca} {\sc Cartier P.}, {\it S\'eminaire ``Sopus Lie'', 2\`eme ann\'ee}, Facult\'e des Sciences de Paris (1955-56)
%
\bibitem{CP} {\sc V. Chari, A. Pressley}, A guide to quantum groups. 
Cambridge (1994).
%
\bibitem{Co1} {\sc L. Comtet}, Analyse Combinatoire, PUF, Tome 1 (1970)
%
\bibitem{Co2} {\sc L. Comtet}, Analyse Combinatoire, PUF, Tome 2 (1970)
%
\bibitem{F1} {\sc P. Flajolet}, http://algo.inria.fr/flajolet/
%
\bibitem{Fo1} {\sc L. Foissy}, {\it Isomorphisme entre l'alg\`ebre des fonctions quasi-sym\'etriques libres et une alg\`ebre de Hopf des 
arbres enracin\'es d\'ecor\'es plans}, personal communication.
%
\bibitem{Fo2} {\sc L. Foissy}, {\it Les alg\`ebres de Hopf des arbres enracin\'es decor\'es}, PhD Memoir, Reims University (2002). 
%
\bibitem{GOF2} {\sc A.I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K.A. Penson}, {\it Combinatorial Physics, 
Normal Order and Model Feynman Graphs}, Proceedings of the Symposium 'Symmetries in Science XIII', Bregenz, 
Austria, 2003, B. Gruber, G. Marmo and N. Yoshinaga (eds.), p.527 (Kluwer Academic
Publishers 2004)\\
arXiv : {\tt quant-ph/0310174}
%
\bibitem{GOF3} {\sc A.I. Solomon, G. Duchamp, P. Blasiak, A. Horzela
and K.A. Penson}, {\it Normal Order: Combinatorial Graphs
Quantum Theory and Symmetries}, Proceedings of the 3rd International Symposium
P.C. Argyres, T.J. Hodges, F. Mansouri, J.J. Scanio, P. Suranyi, and L.C.R.
Wijewardhana (eds.), p.398 (World Scientific Publishing 2004)\\
arXiv:{\tt quant-ph/0402082}
%
\bibitem{GOF4} {\sc G. H. E. Duchamp, P. Blasiak, A. Horzela, K. A. Penson, A. I. Solomon, Feynman graphs and related Hopf algebras}, Journal of Physics: Conference Series, SSPCM'05, Myczkowce, Poland.
arXiv : cs.SC/0510041
%
\bibitem{OPM} {\sc G. Duchamp, A.I. Solomon, K.A. Penson, A. Horzela
and P. B lasiak}, {\it One-parameter groups and combinatorial physics}, 
Proceedings of the Symposium Third International Workshop on
Contemporary Problems in Mathematical Physics (COPROMAPH3)
(Porto-Novo, Benin, Nov. 2003),  J. Govaerts, M. N. Hounkonnou and A. Z. Msezane (eds.), p.436 (World Scientific Publishing 2004)\\
arXiv: {\tt quant-ph/04011262}
%
\bibitem{GOF5} {\sc A.I. Solomon, G. Duchamp, P. Blasiak, A. Horzela
and K. A. Penson}, {\it Partition functions and graphs: A combinatorial approach}, 
Proceedings of the XI International Conference on Symmetry Methods
in Physics (SYMPHYS-11) (Prague, Czech Republic, June 2004), C. Burdik, O. Navratil, and S. Posta (eds.) (JINR Publishers, Dubna, 2004)\\
arXiv:{\tt quant-ph/0409082}
%
\bibitem{GOF6} {\sc A. Horzela, P. Blasiak, G. Duchamp, K. A. Penson
and A.I. Solomon}, {\it A product formula and combinatorial field theory}, 
Proceedings of the XI International Conference on Symmetry Methods
in Physics (SYMPHYS-11) (Prague, Czech Republic, June 2004), C. Burdik, O. Navratil, and S. Posta (eds.) (JINR Publishers, Dubna)\\ 
arXiv:{\tt quant-ph/0409152}
%
\bibitem{GOF7} {\sc P. Blasiak, A. Horzela, K. A. Penson, G. H. E. Duchamp, 
A.I. Solomon}, {\it Boson normal ordering via substitutions and Sheffer-Type Polynomials}, 
Phys. Lett. A {\bf 338} (2005) 108
%
\bibitem{GOF8} {\sc P. Blasiak,  K. A. Penson, A.I. Solomon,  
A. Horzela, G. H. E. Duchamp}, 
{\it Some useful formula for bosonic operators}, Jour. Math. Phys.
 {\bf 46} 052110 (2005).
%
\bibitem{GOF9} Allan's NY
%
\bibitem{GOF10} Gerard's NY
%
\bibitem{DHT} {\sc G. Duchamp, F. Hivert, J. Y. Thibon}, {\it Non commutative 
functions VI: Free quasi-symmetric functions and related algebras}, 
International Journal of Algebra and Computation Vol 12, No 5 (2002).
%
\bibitem{FPSAC07} {\sc G. H. E. Duchamp, J. -G. Luque, J. -C. Novelli, C. Tollu, F. Toumazet}, {\it Hopf algebras of diagrams}, submitted to FPSAC07.
%
\bibitem{JR} {\sc S. A. Joni, G.-C.Rota}, {\it Colgebras and Bialgebras in Combinatorics}, Studies in Applied Mathematics 
{\bf 61}, 93-139 (1979).
%
\bibitem{K1} {\sc D. Knuth}, {\it The art of computer programming} Tome I.
Addison-Wesley (1981)
%
\bibitem{MM} {\sc J. Milnor, J. Moore}, {\it On the structure of Hopf Algebras}, Ann. of Math. 81 (1965), 211-264. 
%
\bibitem{St2} {\sc R. P. Stanley}, {\it Enumerative Combinatorics}, vol. {\bf 2}, Cambridge Univ. Press (2004).
%
\bibitem{Weinzierl:2003ub} {\sc S. Weinzierl}, {\it Hopf algebra structures in particle physics}, Eur. Phys. J. C {\bf 33} (2004)
arXiv: {\tt hep-th/0310124}
%
\bibitem{Varvak} {\sc A. Varvak}, Rook numbers and the normal ordering problem, {\it Preprint} arXiv: {\tt math. CO/0402376} 
%
\bibitem{Ro} {\sc M. Rosso}, [Ro2] , Quantum groups and quantum shuffles, Inventiones Math. 133 (1998).
%
\bibitem{BFFLS} {\sc Bayen (F.), Flato (M.), Fronsdal (C.), Lichnerowicz (A.) and Sternheimer (D.)}, {\it Deformation and Quantization}, Ann. of Phys. 111 (1978), pp. 61-151.
%
\bibitem{Oc} {\sc P. Ochsenschl\"ager}, Binomialkoeffitzenten und Shuffle-Zahlen, Technischer
Bericht, Fachbereich Informatik, T. H. Darmstadt,1981.
%
\bibitem{DFLL} {\sc Duchamp G., Flouret M., Laugerotte E., Luque J-G.}, 
{\it Direct and dual laws for automata with multiplicities}\\
{\tt arXiv} : math.CO\/0607412
%
\bibitem{DL} {\sc Duchamp G., Luque J-G.}, 
{\it Congruences Compatible with the Shuffle Product}\\
{\tt arXiv} : math.CO\/0607419 
%
\bibitem{Ho} {\sc M.E.Hoffman}, {\it Quasi-shuffle products}, J. Algebraic Combin. (2000), 49-68
%
\bibitem{DKPTT} {\sc G. H. E. Duchamp, G. Koshevoy, K. A. Penson, C. Tollu, F. Toumazet}, {\it Geometric combinatorial twisting and shifting}, S\'eminaire Lotharingien (in preparation).
%
\bibitem{Re} {\sc Reutenauer C.}, {\it Free Lie algebras}, Oxford University Press (1993).
%
\bibitem{Ha} {\sc M. Hazewinkel}, {Hopf algebras of endomorphisms of Hopf algebras}, (Oct 2004) 
{\tt ArXiv : math.QA/0410364}



\end{thebibliography}
\end{document}
