\section{Background}

\subsection{Cartier-Milnor-Moore theorems for Bidendriform bialgebras}

A bialgebra is a vector space over a field $K$, endowed with an unitary associative
product $\cdot$ and a counitary coassociative coproduct
$\Delta$ % (with the summation sign implied)
satisfying a compatibility relation called the Hopf relation
$\Delta(a\cdot b) = \Delta(a)\cdot\Delta(b)$.  In this paper all bialgebras are assumed to be graded
and connected (\emph{i.e.} the homogeneous component of degree $0$ is $K$). They
are therefore Hopf algebras, as the existence of the antipode is implied.

We now recall the elements of the definition of bidendriform bialgebras which are
useful for the comprehension of this paper. We refer to~\cite{foissy_2007} for
the full list of axioms.

First of all, a \emph{dendriform algebra} $A$ is a $K$-vector space,
endowed with two binary bilinear operations $\prec$, $\succ$ satisfying the
following axioms, for all $a, b, c\in A$:
\begin{align}
  \label{E1} (a \prec b) \prec c &= a \prec (b \prec c + b \succ c),\\
  \label{E2} (a \succ b) \prec c &= a \succ (b \prec c),\\
  \label{E3} (a \prec b + a \succ b) \succ c &= a \succ (b \succ c).
\end{align}
Adding together~\cref{E1,E2,E3} show that the product
$a \cdot b \eqdef a \prec b + a \succ b$ is associative. Adding a subspace of scalars,
this defines a unitary algebra structure on $K \oplus A$.  In this paper,
all the dendriform algebras are graded and have null $0$-degree component so
that the associated algebra is connected.

Dualizing, one gets a notion of \emph{co-dendriform co-algebra} which is a
$K$-vector space with two binary co-operations (\emph{i.e.}, linear maps
$A \to A\otimes A$) denoted by $\Delta_\prec$, $\Delta_\succ$ satisfying the
dual axioms of~\cref{E1,E2,E3}.  The sum of the two half
coproducts~$\tilde{\Delta}(a) \eqdef \Delta_\prec(a) + \Delta_\succ(a)$ is a
reduced coassociative coproduct. On $K \oplus A$, setting 
$\Delta(a) \eqdef 1 \otimes a + a \otimes 1 + \tilde{\Delta}(a)$ defines a
co-associative and co-unitary coproduct.

A \emph{bidendriform bialgebra} is a $K$-vector space which is both a dendriform
algebra and a co-dendriform co-algebra satisfying a set of four
relations~\cite{foissy_2007} relating respectively $\prec$ and $\succ$ with
$\Delta_\prec$, $\Delta_\succ$. Adding those four relations shows that $\cdot$ and
$\Delta$ as defined above defines a proper bi-algebra.

\bigskip

We recall here the relevant results of Foissy~\cite{foissy_2007} on the
rigidness of bidendriform bialgebras based on the works of Chapoton and
Ronco~\cite{ronco_2000,chapoton_2002}.

Let $A$ be a bidendriform bialgebra. We define~$\Prim(A)\eqdef
\Ker(\tilde{\Delta})$ as the set of \emph{primitive} elements of $A$. We also denote
by~$\SA(z)$ and~$\SP(z)$ the Hilbert series of $A$ and $\Prim(A)$ defined as
$\SA(z) \eqdef \sum_{n=1}^{+\infty}\dim(A_n)z^n$ and
$\SP(z) \eqdef \sum_{n=1}^{+\infty}\dim(\Prim(A_n))z^n$.
The present work is based on two analogues of the Cartier-Milnor-Moore
theorems~\cite{foissy_2007} which we present now.
The first one is extracted from the proof of~{\cite[Proposition~6]{foissy_2011}}:
\begin{prop} \label{left_prod} Let $A$ be a bidendriform bialgebra and let
  $p_1\dots p_n \in \Prim(A)$. Then the map
  \begin{equation}
    p_1 \otimes p_2 \otimes \ldots \otimes p_n
    \mapsto p_1 \prec (p_2 \prec (\ldots \prec p_n)\ldots).
  \end{equation}
  is an isomorphism of co-algebras from $T^+(\Prim(A))$ (the non trivial part
  of the tensor algebra with deconcatenation as
  coproduct) to $A$.  As a consequence, taking a basis $(p_i)_{i\in I}$ of
  $\Prim(A)$, the
  family~$(p_{w_1} \prec (p_{w_2} \prec (\dots \prec p_{w_n})\dots))_w$
  where $w=w_1\dots w_n$ is a non empty word on $I$ defines a basis of $A$.  This
  implies the equality of Hilbert series $\SA=\SP/(1-\SP)$.
\end{prop}

One can further analyze $\Prim(A)$ using the so-called \emph{totally primitive}
elements of $A$ defined as
$\TPrim(A) = \Ker(\Delta_\prec) \cap \Ker(\Delta_\succ)$ and
$\ST(z) = \sum_{n=1}^{+\infty}\dim(\TPrim(A_n))z^n$.  Recall that a brace algebra is a
$K$-vector space $A$ together with an $n$-multilinear operation denoted as
$\langle\ldots\rangle$ for all $n ≥ 2$ which satisfies certain relations (see \cite{ronco_2000} for
details).
\begin{theorem}[{\cite[Theorem~5]{foissy_2011}}] \label{brace} Let $A$ be a bidendriform
  bialgebra. Then $\Prim(A)$ is freely generated as a brace algebra by
  $\TPrim(A)$ with brackets given by
  \begin{multline*}
    \langle p_1, \dots, p_{n-1}; p_n\rangle \eqdef \sum_{i=0}^{n-1}\ (-1)^{n-1-i}\\
    (p_1 \prec (p_2 \prec (\cdots \prec p_i)\cdots)) \succ p_n \prec ((\cdots(p_{i+1} \succ p_{i+2}) \succ \cdots) \succ p_{n-1}).
  \end{multline*}
\end{theorem}

A basis of $\Prim(A)$ is described by ordered trees that are decorated with
elements of $\TPrim(A)$ where $p_n$ is the root and $p_1, \ldots, p_{n-1}$ are the
children (see \cite{ronco_2000,chapoton_2002,foissy_2011}). This is reflected on
their Hilbert series as~\cite[{Corollary~37}]{foissy_2007}:
$\ST = \SA / (1+\SA)^2$ or equivalently $\SP = \ST(1 + \SA)$.

Using \cref{left_prod,brace} together with a dimension argument, one can show the
following theorem:
\begin{theorem} [{\cite[Theorem~2]{foissy_2011}}] \label{prim_tot}
Let $A$ be a bidendriform bialgebra. Then $A$ is freely generated as a dendriform
  algebra by $\TPrim(A)$.
\end{theorem}

\subsection{The Hopf algebra of word-quasisymmetric functions~\texorpdfstring{$\WQSym$}{WQSym}}

The algebra $\WQSym$ is a Hopf algebra whose bases are indexed by
ordered set partitions or equivalently surjections or packed words. In
this paper, we use the latter which we define now.
\begin{defi} \label{packed_word} A word over the alphabet~$\NN_{>0}$ is
  \emph{packed} if all the letters from $1$ to its maximum $m$ appears at least
  once. By convention, the empty word~$\epsilon$ is packed.  For $n\in\NN$, we denote by
  $\PW_n$ the set of all packed words of length (also called size) $n$ and
  $\PW = \bigsqcup_{n\in\NN}\PW_n$ the set of all packed words.
\end{defi}

\begin{defi} The packed word~$u\eqdef pack(w)$ associated with a word over the
  alphabet~$\NN_{>0}$ is obtained by the following process: if
  $b_1< b_2< \dots < b_r$ are the letters occurring in $w$, then $u$ is the
  image of $w$ by the homomorphism $b_i\mapsto i$.
\end{defi}
A word $u$ is packed if and only if $pack(u) = u$.
\begin{ex}
  The word $4152142$ is not packed because the letter $3$ does not appear while
  the maximum letter is $5 > 3$. Meanwhile $pack(4152142) = 3142132$ is a packed
  word. Here are all packed words of size $1$, $2$ and $3$ in lexicographic
  order:
  \[
    1,\quad 11\ 12\ 21,\quad
    111\ 112\ 121\ 122\ 123\ 132\ 211\ 212\ 213\ 221\ 231\ 312\ 321
  \]
\end{ex}
% \todo{maybe after example: "The ordered set partition corresponding to a packed
%   word $w_1,...w_n$ is obtained by placing the index i into the $w_i-th$ block." or
%   something similar.}  
We will use the following notations and operations on words over the alphabet
$\NN_{>0}$: First, $\max(w)$ is the maximum letter of the word $w$ with the
convention that $\max(\epsilon)=0$. Then $|w|$ is the length (or size) of the word
$w$. The concatenation of the two words $u$ and $v$ is denoted as $u\cdot v$.
Moreover, $u\gcdot v$ (resp. $u\dcdot v$) is the left-shifted
(resp. right-shifted) concatenation of the two words where all the letters of
the left (resp. right) word are shifted by the maximum of the right (resp. left)
word: $1121\gcdot 3112 = 44543112$ and $1121\dcdot 3112 = 11215334$.

% And $u\cdot v$ the concatenation of the two words (\textit{e.g.}
% $1121\cdot 33454 = 112133454$). Moreover, $u\gcdot v$ (resp. $u\dcdot v$) is the
% left-shifted (resp. right-shifted) concatenation of the two words where all
% the letters of the left (resp. right) word are shifted by the maximum of the
% right (resp. left) word: $1121\gcdot 3112 = 44543112$ and
% $1121\dcdot 3112 = 11215334$.

Finally $u\shuffle v$ is the shuffle product of the two words. It is
recursively defined as $u \shuffle \epsilon = \epsilon \shuffle u = u$ and
\begin{equation} \label{eq:shuffle}
  ua \shuffle vb = (u \shuffle vb)\cdot a + (ua \shuffle v)\cdot b
\end{equation}
where $u$ and $v$ are words and $a$ and $b$ are letters. Analogously to the
shifted concatenation, one can define the right shifted-shuffle $u\cshuffle v$
where all the letters of the right word $v$ are shifted by the maximum of the
left word $u$.

\begin{ex}
  $12\cshuffle \red{1}\red{1} =
  12\shuffle \red{3}\red{3} =
  12\red{3}\red{3} + 1\red{3}2\red{3} +
  1\red{3}\red{3}2 + \red{3}12\red{3} + \red{3}1\red{3}2 + \red{3}\red{3}12$.
\end{ex}

\paragraph*{Bidendriform bialgebra structure}

Novelli-Thibon~\cite{novthi_2006} proved that $\WQSym$ is a bidendriform
bialgebra. Their products and coproducts involve overlapping-shuffle. However it
will be easier for us to chose, among the various bases known in the literature
\cite{Hivert_thesis,berzag,novthi_2006,Vargas_thesis} a basis where the shuffle
are non-overlapping. Therefore, we take the dual basis denoted
$(\RR_w)_{w\in\PW}$ of \cite[Equation~23]{berzag}, using the classical bijection
between ordered partitions and packed words and redefine the bidendriform
structure. The Hopf algebra product and reduced coproduct are respectively
recovered as the sum of the half products (see~\cref{half_prod}) and half
coproducts (see~\cref{left_coprod,right_coprod}).

The recursive definition of the shuffle product (see \cref{eq:shuffle}) contains two
summands. We define them respectively as $\prec$ and $\succ$:
\begin{equation}
  ua \prec vb \eqdef (u \shuffle vb)\cdot a,
  \qquad\text{and}\qquad
  ua \succ vb \eqdef (ua \shuffle v)\cdot b.
\end{equation}
We define $\prec$, $\succ$, $\Delta_\prec$ and $\Delta_\succ$ on
$(\WQSym)_+ = Vect(\RR_u \mid u \in \PW_n, n \geq 1)$ in the following way:
for all $u = u_1\cdots u_n\in \PW_{n\geq1}$ and $v \in \PW_{m\geq1}$,
\begin{equation} \label{half_prod}
  \RR_u \prec \RR_v \eqdef \sum_{w \in u \prec v} \RR_w,
  \qquad\text{and}\qquad
  \RR_u \succ \RR_v \eqdef \sum_{w \in u \succ v} \RR_w.
\end{equation}
\begin{align} 
  \label{left_coprod}  \Delta_\prec(\RR_u) &\eqdef \sum_{\stackrel{i=k}{\stackrel{\{u_1, \dots, u_i\} \cap \{u_{i+1}, \dots, u_n\} = \emptyset}{u_k = \max(u)}}}^{n-1}
                                    \RR_{pack(u_1\cdots u_i)} \otimes \RR_{pack(u_{i+1}\cdots u_n)},\\
  \label{right_coprod}  \Delta_\succ(\RR_u) &\eqdef \sum_{\stackrel{i=1}{\stackrel{\{u_1, \dots, u_i\} \cap \{u_{i+1}, \dots, u_n\} = \emptyset}{u_k = \max(u)}}}^{k-1}
               \RR_{pack(u_1\cdots u_i)} \otimes \RR_{pack(u_{i+1}\cdots u_n)}.
\end{align}
\begin{ex}
  \begin{align*}
    \RR_{211} \prec \RR_{\red{12}} &= \RR_{21\red{3}\red{4}1} + \RR_{2\red{3}1\red{4}1} + \RR_{2\red{3}\red{4}11} + 
                                 \RR_{\red{3}21\red{4}1} + \RR_{\red{3}2\red{4}11} + \RR_{\red{3}\red{4}211},\\
    \RR_{221} \succ \RR_{\red{12}} &= \RR_{211\red{3}\red{4}} + \RR_{21\red{3}1\red{4}} + \RR_{2\red{3}11\red{4}}
                                 + \RR_{\red{3}211\red{4}},\\
    \Delta_\prec(\RR_{2125334}) &= \RR_{2123} \otimes \RR_{112} + \RR_{212433} \otimes \RR_{1},\\
    \Delta_\succ(\RR_{2125334}) &= \RR_{212} \otimes \RR_{3112}. 
  \end{align*}
\end{ex}

% The proof of this theorem is similar to the proof of \cite[{Theorem~38}]{foissy_2007}.

\begin{theorem} {\cite[{Theorem~2.5}]{novthi_2006}}
  $(\WQSym)_+, \prec, \succ, \Delta_\prec, \Delta_\succ)$ is a bidendriform bialgebra.
\end{theorem}
From now on $\Prim(\WQSym)$ and $\TPrim(\WQSym)$ are respectively abbreviated
to $\Prim$ and $\TPrim$. Moreover, we denote homogeneous components using
indices as in $\Prim_n$.
We give the first values of the dimensions~$a_n\eqdef\dim(\WQSym_n)$, $p_n\eqdef\dim(\Prim_n)$ and
$t_n\eqdef\dim(\TPrim_n)$:
\[
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c||l|}
  \hline
  $n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & OEIS \\
  \hline
  $a_n$ & 1 & 3 & 13 & 75 & 541 & 4 683 & 47 293 & 545 835 & 7 087 261 & A000670 \\
  \hline
  $p_n$ & 1 & 2 & 8 & 48 & 368 & 3 376 & 35 824 & 430 512 & 5 773 936 & A095989 \\
  \hline
  $t_n$ & 1 & 1 & 4 & 28 & 240 & 2 384 & 26 832 & 337 168 & 4 680 272 &  \\
  \hline
\end{tabular} 
\]

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "primitive_wqsym"
%%% End:
