# A combinatorial PROP for bialgebras

Jorge Becerra  Bernouilli Institute, University of Groningen, The Netherlands
<EMAIL_ADDRESS>https://sites.google.com/view/becerra/

(Date: 27th August 2024)

###### Abstract.

It is a classical result that the category of finitely-generated free monoids
serves as a PROP for commutative bialgebras. Attaching permutations to fix the
order of multiplication, we construct an extension of this category that is
equivalent to the PROP for bialgebras.

###### Contents

  1. 1 Introduction
  2. 2 Bialgebras and PROPs
  3. 3 A PROP for bialgebras
  4. 4 Applications

##  1\. Introduction

Bialgebras are an important algebraic structure that one commonly finds in
many areas of mathematics, eg algebraic topology [MP12], homotopical algebra
[LV12], quantum groups theory [Kas95], knot theory [Hab06], etc. Therefore it
is sometimes useful to take one level of abstraction up and study their
structure maps on their own. A convenient setup to do this is given by
symmetric monoidal categories whose family of objects can be identified with
the set of non-negative integers, also known as PROPs. One could think of a
PROP as a gadget to study abstract algebraic operations, whereas an algebra
over a PROP is a concrete realisation of these operations. This realisation is
achieved by means of a strong monoidal functor
$\mathsf{P}\longrightarrow\mathcal{C}$, where $\mathsf{P}$ is a PROP and
$\mathcal{C}$ is a symmetric monoidal category.

In general, an algebraic structure is given by some structure maps that
satisfy certain compatibility conditions. A rather straightforward way to
describe a PROP for such an algebraic structure is given by setting the
structure maps as generators and taking the compatibility conditions as
relations. In this paper we focus on the PROP $\mathsf{B}$ for
(noncommutative, noncocomutative) bialgebras, monoidally generated by the maps
$\mu:2\longrightarrow 1$, $\eta:0\longrightarrow 1$, $\Delta:1\longrightarrow
2$ and $\varepsilon:1\longrightarrow 0$, subject to the usual relations that
define a bialgebra (see Figure 1). Though it may seem this gives rise to
complex combinations of these maps, it turns out that any morphism in
$\mathsf{B}$ has a unique normal form.

######  Theorem 1.1 (Theorem 3.5).

Every morphism $f:n\longrightarrow m$ in $\mathsf{B}$ factors in a unique way
as

$f=(\mu^{[q_{1}]}\otimes\cdots\otimes\mu^{[q_{m}]})\circ
P_{\sigma}\circ(\Delta^{[p_{1}]}\otimes\cdots\otimes\Delta^{[p_{n}]})$

for some (unique) integers $p_{1},\ldots,p_{n},q_{1},\ldots,q_{m},s\geq 0$ and
a permutation ${\sigma\in\Sigma_{s}}$, where the map
$\mu^{[k]}:k\longrightarrow 1$ (resp. $\Delta^{[k]}:1\longrightarrow k$)
stands for the iterated multiplication (resp. comultiplication).

…
---

…
---
…
---
$\Delta^{[p_{1}]}\otimes\cdots\otimes\Delta^{[p_{n}]}$
---
$P_{\sigma}$
---
$\mu^{[q_{1}]}\otimes\cdots\otimes\mu^{[q_{m}]}$
---

…
---

…
---

…
---

…
---

Even though this is an important step towards the understanding of the PROP
$\mathsf{B}$, computationally it does not present any advantage, as it gives
no information about how to determine the coefficients $p_{i},q_{i},s$. Thence
we would like to find an equivalent, computationally explicit description of
$\mathsf{B}$.

Let $\mathsf{fgFMon}$ be the category of finitely-generated free monoids and
let $\mathcal{C}$ be a symmetric monoidal category. It turns out that the
datum of a strong monoidal functor $\mathsf{fgFMon}\longrightarrow\mathcal{C}$
uniquely determines a commutative bialgebra $A$ in $\mathcal{C}$, where the
multiplication $\mu:A\otimes A\longrightarrow A$ is given by the image of the
monoid map $F(x,y)\longrightarrow F(z)$, $x,y\mapsto z$ and the
comultiplication $\Delta:A\longrightarrow A\otimes A$ is the image of the
monoid map $F(x)\longrightarrow F(y,z)$, $x\mapsto yz$ (Example 2.9). In a
similar fashion, if $\mathsf{fSet}$ denotes the category of finite sets, then
the datum of a strong monoidal functor
$\mathsf{fSet}\longrightarrow\mathcal{C}$ uniquely determines a commutative
algebra $A$ in $\mathcal{C}$, where this time the multiplication $\mu:A\otimes
A\longrightarrow A$ is given by the image of the unique map of sets
$\\{1,2\\}\longrightarrow\\{1\\}$ (Example 2.4). These define equivalence of
categories $\mathsf{ComA}\overset{\simeq}{\longrightarrow}\mathsf{fSet}$ and
$\mathsf{ComB}\overset{\simeq}{\longrightarrow}\mathsf{fgFMon}$, where
$\mathsf{ComA}$ and $\mathsf{ComB}$ are the PROPs for commutative algebras and
bialgebras, respectively (we think of these as described in terms of
generators and relations).

For instance, assume for simplicity $\mathcal{C}=\mathsf{Vect}_{k}$, the
category of vector spaces over some field $k$. Given a commutative bialgebra
$A$, consider the monoid maps

$f:F(x)\longrightarrow F(a),\quad x\mapsto a^{n}\qquad,\qquad
g:F(x)\longrightarrow F(a,b),\quad x\mapsto aba^{2}b.$

Under the previous equivalences, they correspond to the $k$-linear maps

$f^{\prime}:A\longrightarrow A,\ x\mapsto x_{(1)}\cdots x_{(n)}\quad,\quad
g^{\prime}:A\longrightarrow A\otimes A,\ x\mapsto x_{(1)}x_{(3)}x_{(4)}\otimes
x_{(2)}x_{(5)}$

where the order of the multiplication is arbitrary as $A$ is commutative. If
$A$ was noncommutative, we would be able to fix the order of the
multiplication by means of a permutation $\sigma\in\Sigma_{n}$ for
$f^{\prime}$ and a pair of permutations
$(\tau_{1},\tau_{2})\in\Sigma_{3}\times\Sigma_{2}$ for $g^{\prime}$. The
upshot of this observation is that by attaching these permutations to the
monoid maps $f$ and $g$, we can produce noncommutative bialgebras from free
monoids. A similar observation follows for finite set maps.

One question that arises here is if this attaching of permutations can be made
functorial in the following sense: the canonical faithful functor
$\mathsf{ComA}\lhook\joinrel\longrightarrow\mathsf{ComB}$ corresponds, under
the previous equivalences, to the free monoid functor, so that the diagram

${\mathsf{ComA}}$${\mathsf{ComB}}$${\mathsf{fSet}}$${\mathsf{fgFMon}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{F}$

commutes (Lemma 2.10). One would like to lift this diagram to a noncommutative
context along the canonical full functors
$\mathsf{A}\longrightarrow\mathsf{ComA}$ and
$\mathsf{B}\longrightarrow\mathsf{ComB}$, where $\mathsf{A}$ is the PROP for
(noncommutative) algebras.

Our main result states that the attaching of permutations gives an affirmative
answer to the previous question.

######  Theorem 1.2 (Theorem 4.5).

There exist symmetric monoidal categories $\widehat{\mathsf{fSet}}$ and
$\widehat{\mathsf{fgFMon}}$, together with full and essentially surjective
functors

$\widehat{\mathsf{fSet}}\longrightarrow\mathsf{fSet}\qquad,\qquad\widehat{\mathsf{fgFMon}}\longrightarrow\mathsf{fgFMon},$

monoidal equivalences

$\mathsf{A}\overset{\simeq}{\longrightarrow}\widehat{\mathsf{fSet}}\qquad,\qquad\mathsf{B}\overset{\simeq}{\longrightarrow}\widehat{\mathsf{fgFMon}}$

and a strong monoidal functor between them

$\widehat{F}:\widehat{\mathsf{fSet}}\longrightarrow\widehat{\mathsf{fgFMon}}$

making the following cube commutative,

${\widehat{\mathsf{fSet}}}$${\widehat{\mathsf{fgFMon}}}$${\mathsf{A}}$${\mathsf{B}}$${\mathsf{fSet}}$${\mathsf{fgFMon}}$${\mathsf{ComA}}$${\mathsf{ComB}}$$\scriptstyle{\simeq}$$\scriptstyle{\widehat{F}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{F\phantom{holaaa}}$$\scriptstyle{\simeq}$
(1.1)

where $F$ is the free monoid functor.

The composite law in $\widehat{\mathsf{fgFMon}}$ gives an explicit formula
that keeps track of the changes of indices that arise when iterating the
structure maps of a bialgebra, and that might be of interest in computational
algebra, see (3.1). The category $\widehat{\mathsf{fSet}}$ is a suitable
modification of the category $\widetilde{\mathsf{fSet}}$ of finite sets and
maps of sets with a total order on fibres (Proposition 2.8) originally
described by Pirashvili [Pir02] under the name of $\mathcal{F}(\mathrm{as})$.
On the other hand, the category $\widehat{\mathsf{fgFMon}}$ can be viewed as a
combinatorial, explicit description of the Quillen $Q$-construction
$\mathcal{Q}\mathcal{F}(\mathrm{as})$ carried out by Pirashvili. In
particular, the composite law of $\widehat{\mathsf{fgFMon}}$ encodes an
expression for the bialgebra maps $1\longrightarrow 1$ from [Pir02, 5.3] as a
special case.

### Outline of the paper

The paper is structured as follows: in Section 2 we recall the definition of a
bialgebra and fix notation. We also recall the notion of PROP and algebra over
a PROP and a general construction via generators and relations. Examples 2.4
and 2.9 make explicit the equivalences $\mathsf{ComA}\simeq\mathsf{fSet}$ and
$\mathsf{ComB}\simeq\mathsf{fgFMon}$, and in Proposition 2.8 we lift the
previous equivalence for algebras to the noncommutative setting, showing that
$\widehat{\mathsf{fSet}}\simeq\mathsf{A}$.

In Section 3 we start by a few motivating examples showing the necessity to
choose some permutations to fix the order of multiplication. Next we briefly
detour to prove Theorem 1.1, which will be needed to construct a PROP
equivalent to $\mathsf{B}$. We later define the category
$\widehat{\mathsf{fgFMon}}$ and show the equivalence
$\widehat{\mathsf{fgFMon}}\simeq\mathsf{B}$ in Theorem 3.10. The key step is
to define properly the composite law in $\widehat{\mathsf{fgFMon}}$, for which
we will need a few constructions relating permutations and elements of a free
monoid. These are carried out in pages 3.13 – 3.17. We end the section with a
couple of examples illustrating our construction.

Lastly, in Section 4 we include several rather immediate applications of the
equivalence $\widehat{\mathsf{fgFMon}}\simeq\mathsf{B}$ and prove Theorem 1.2.

### Acknowledgments

The author would like to thank Roland van der Veen for helpful discussions and
valuable comments.

##  2\. Bialgebras and PROPs

For this section we fix $(\mathcal{C},\otimes,\mathds{1},P)$ a symmetric
monoidal category, where $\otimes$ stands for the monoidal product,
$\mathds{1}$ stands for the unit object and
$P:\otimes\overset{\cong}{\Longrightarrow}\otimes^{op}$ stands for the
symmetry, so $P_{Y,X}\circ P_{X,Y}=\mathrm{Id}_{X\otimes Y}$. We will
implicitly use MacLane’s coherence theorem [ML98] to remove the associativity
and unit constrains from the formulae. For an introduction to monoidal
categories see [TV17].

###  2.1. Algebras, coalgebras and bialgebras

An algebra in $\mathcal{C}$ (more precisely, an algebra object in
$\mathcal{C}$) is an object $A\in\mathcal{C}$ together with two arrows
$\mu:A\otimes A\longrightarrow A$ and $\eta:\mathds{1}\longrightarrow A$,
called the multiplication and the unit, satisfying the associativity and unit
conditions

$\mu(\mu\otimes\mathrm{Id})=\mu(\mathrm{Id}\otimes\mu)\qquad,\qquad\mu(\mathrm{Id}\otimes\eta)=\mathrm{Id}=\mu(\eta\otimes\mathrm{Id}).$
(2.1)

If $\mu\circ P_{A,A}=\mu$, we say that $A$ is commutative.

A coalgebra in $\mathcal{C}$ is an algebra in $\mathcal{C}^{op}$, that is, an
object $A\in\mathcal{C}$ endowed with two arrows $\Delta:A\longrightarrow
A\otimes A$ and $\varepsilon:A\longrightarrow\mathds{1}$, called the
comultiplication and the counit, satisfying the coassociativity and counit
conditions

$(\Delta\otimes\mathrm{Id})\Delta=(\mathrm{Id}\otimes\Delta)\Delta\qquad,\qquad(\mathrm{Id}\otimes\varepsilon)\Delta=\mathrm{Id}=(\varepsilon\otimes\mathrm{Id})\Delta.$
(2.2)

If $P_{A,A}\circ\Delta=\Delta$, we say that $A$ is cocommutative. It should be
clear that a (co)algebra morphism between (co)algebras should be an arrow in
$\mathcal{C}$ that respects the structure maps.

If $A,A^{\prime}$ are algebras in $\mathcal{C}$, the monoidal product
$A\otimes A^{\prime}$ is naturally an algebra with structure maps
$(\mu\otimes\mu^{\prime})(\mathrm{Id}\otimes
P_{A,A^{\prime}}\otimes\mathrm{Id})$ and $\eta\otimes\eta^{\prime}$. The same
observation with reversed arrows follows for coalgebras. A bialgebra in
$\mathcal{C}$ is an object $A\in\mathcal{C}$ which is both an algebra and a
coalgebra and whose structure maps are compatible in the sense that the
coalgebra structure maps are algebra morphisms (alternatively, the algebra
structure maps are coalgebra morphisms). Explicitly,

$\begin{gathered}\Delta\mu=(\mu\otimes\mu)(\mathrm{Id}\otimes
P_{A,A}\otimes\mathrm{Id})(\Delta\otimes\Delta)\\\
\Delta\eta=\eta\otimes\eta\quad,\quad\varepsilon\mu=\varepsilon\otimes\varepsilon\quad,\quad\varepsilon\eta=\mathrm{Id}_{\mathds{1}}.\end{gathered}$
(2.3)

It will be convenient to depict the previous maps as some planar diagrams,

$\mu=$, $\eta=$, $\Delta=$, $\varepsilon=$

whereas the symmetry will be represented as

$P_{A,A}=$

By doing this, we can represent the bialgebra axioms graphically as in Figure
1.

$=$
---
(a)

$=$
---
$=$
---
(b)

$=$
---
(c)

$=$
---
$=$
---
(d)

$=$
---
(e)

$=$
---
(f)

.

$=$
---
(g)

$=$
---
(h)

.

Figure 1.  The bialgebra axioms are represented graphically. (1(a)), (1(b))
represent (2.1); (1(c)), (1(d)) represent (2.2), and
(1(e)),(1(f)),(1(g)),(1(h)) represent (2.3). Note that the right-hand side of
(1(h)) stands for the empty diagram.

In the following we will adhere to Habiro’s notation [Hab16]: for $k\geq 0$ we
define the iterated multiplication and comultiplication

$\mu^{[k]}:A^{\otimes k}\longrightarrow
A\qquad,\qquad\Delta^{[k]}:A\longrightarrow A^{\otimes k}$

as follows:

$\displaystyle\mu^{[0]}:=\eta,\quad\mu^{[1]}:=\mathrm{Id}\quad,\quad\mu^{[k]}:=\mu\circ(\mu^{[k-1]}\otimes\mathrm{Id}),\quad
k\geq 2$
$\displaystyle\Delta^{[0]}:=\varepsilon,\quad\Delta^{[1]}:=\mathrm{Id}\quad,\quad\Delta^{[k]}:=(\Delta^{[k-1]}\otimes\mathrm{Id})\circ\Delta,\quad
k\geq 2$

For integers $p>0$ and $k_{1},\ldots,k_{p}\geq 0$ let us write

$\mu^{[k_{1},\ldots,k_{p}]}:=\mu^{[k_{1}]}\otimes\cdots\otimes\mu^{[k_{p}]}\qquad,\qquad\Delta^{[k_{1},\ldots,k_{p}]}:=\Delta^{[k_{1}]}\otimes\cdots\otimes\Delta^{[k_{p}]}.$

The associativity and coassociativity axioms imply the following generalised
relations:

$\mu^{[p]}\circ\mu^{[k_{1},\ldots,k_{p}]}=\mu^{[k_{1}+\cdots+k_{p}]}\qquad,\qquad\Delta^{[k_{1},\ldots,k_{p}]}\circ\Delta^{[p]}=\Delta^{[k_{1}+\cdots+k_{p}]}.$

###  2.2. PROPs and their algebras

A (classical, monocoloured) PROP is a symmetric monoidal category monoidally
generated by a single object. By MacLane’s coherence theorem, every PROP is
monoidally equivalent to another that has the set of non-negative integers as
objects and the monoidal product is given by the sum.

PROPs are useful to study structural morphisms of large classes of algebraic
structures. Let us sketch here the general construction [BSZ17]: let
$(\mathcal{G},\mathcal{E})$ be a pair of sets, where $\mathcal{G}$ contains
generators, a set formal arrows $g:n\longrightarrow m$ between non-negative
integers, which includes special arrows $\mathrm{Id}:1\longrightarrow 1$ and
$P:2\longrightarrow 2$. The set of $\mathcal{G}$-terms is obtained by
(formally) combining the generators with the operations “composition” $\circ$
and “monoidal product” $\otimes$. The set $\mathcal{E}$ contains equations,
pairs of $\mathcal{G}$-terms $(t,t^{\prime}:n\longrightarrow m)$ with the same
arity and coarity.

Any such pair $(\mathcal{G},\mathcal{E})$ induces a PROP
$\mathsf{P}=\mathsf{P}_{(\mathcal{G},\mathcal{E})}$ by letting
$\mathrm{Hom}_{\mathsf{P}}(n,m)$ be the set of $\mathcal{G}$-terms
$n\longrightarrow m$ modulo the least congruence relation (with respect to the
composition and the monoidal product) that contains the laws of strict
symmetric categories and the equations $t=t^{\prime}$ for every pair
$(t,t^{\prime})\in\mathcal{E}$.

Whereas a PROP encodes algebraic operations abstractly, an algebra over a PROP
is an evaluation of these operations on a concrete object. More precisely, a
$\mathsf{P}$-algebra in a symmetric monoidal category $\mathcal{C}$ is a
strong monoidal functor ${A:\mathsf{P}\longrightarrow\mathcal{C}}$. The class
of $\mathsf{P}$-algebras on $\mathcal{C}$ forms a category
$\mathsf{Alg}_{\mathsf{P}}(\mathcal{C})$ in the obvious way, where morphisms
are monoidal natural transformations between functors
$\mathsf{P}\longrightarrow\mathcal{C}$.

The following observation will be useful:

######  Lemma 2.1.

Let $\mathsf{P}$, $\mathsf{P}^{\prime}$ be PROPs. If there is a natural
bijection

$\mathsf{Alg}_{\mathsf{P}}(\mathcal{C})\overset{\cong}{\longrightarrow}\mathsf{Alg}_{\mathsf{P}^{\prime}}(\mathcal{C})$

for any symmetric monoidal category $\mathcal{C}$, then $\mathsf{P}$ and
$\mathsf{P}^{\prime}$ are monoidally equivalent.

###### Proof.

This is a direct consequence of the Yoneda lemma. ∎

Let us illustrate the above construction with a few examples:

######  Example 2.2.

Let $\mathcal{G}$ consist of two arrows $\mu:2\longrightarrow 1$ and
$\eta:0\longrightarrow 1$, that we can think of as the planar diagrams
depicted in the previous section. If $\mathcal{E}$ is the set given by the two
equations depicted in Figure 1(a) and 1(b), then the resulting PROP is denoted
by $\mathsf{A}$ and $\mathsf{Alg}_{\mathsf{A}}(\mathcal{C})$ is equivalent to
the category of algebras in $\mathcal{C}$. In this case, one says that
$\mathsf{A}$ is a PROP for algebras. If the relation $P\circ\mu=\mu$ is added,
then the corresponding category $\mathsf{ComA}$ is a PROP for commutative
algebras.

A similar note can be made for the categories of coalgebra or bialgebras,
perhaps with the (co)commutative axiom included. If $\mathcal{G}$ contains
$\mu:2\longrightarrow 1$, $\eta:0\longrightarrow 1$, $\Delta:1\longrightarrow
2$ and $\varepsilon:1\longrightarrow 0$ and $\mathcal{E}$ consists of the
equations given in Figure 1, then the resulting PROP for bialgebras will be
denoted as $\mathsf{B}$. If the equation $P\circ\mu=\mu$ is added, then we
will denote the resulting PROP for commutative bialgebras as $\mathsf{ComB}$.

An important drawback of the previous construction is that it might seem ad-
hoc or artificial, being produced by generators and relations. A sensible
question is the following:

######  Question 2.3.

Is it possible to describe the PROPs for ((co)commutative) algebras,
coalgebras or bialgebras without using generators and relations?

The answer for ((co)commutative) (co)algebras is quite simple. Before
addressing this case let us introduce some notation: for $n\geq 0$, let
$\Sigma_{n}$ be the symmetric group of order $n$ (if $n=0$ we set
$\Sigma_{0}=\emptyset$). Given an object $X\in\mathcal{C}$, any element
$\sigma\in\Sigma_{n}$ induces an arrow

$P_{\sigma}:X^{\otimes n}\longrightarrow X^{\otimes n}$

determined by $P_{(i,i+1)}=\mathrm{Id}^{\otimes(i-1)}\otimes
P_{X,X}\otimes\mathrm{Id}^{n-i-1}$ and the property that the passage
$\Sigma_{n}\longrightarrow\mathrm{Hom}_{\mathcal{C}}(X^{\otimes n},X^{\otimes
n})$ is a monoid homomorphism.

######  Example 2.4 (essentially [Pir02]).

Let $\mathsf{fSet}$ be the category of finite sets. Up to monoidal
equivalence, we can view it as a PROP with the ordinals
$[n]=\\{1<\cdots<n\\}$, $n\geq 0$, as objects and the sum of ordinals
(disjoint union) as the monoidal product ($[0]$ is by definition the empty
set).

For any $k\geq 0$, there is a unique map $[k]\longrightarrow[1]$, in the same
way that there is a unique map $\mu^{[k]}:A^{\otimes k}\longrightarrow A$ for
a commutative algebra $A$ in $\mathcal{C}$.111Homotopy theorists will
recognise the commutative operad $\mathsf{Com}(n)=*$ here. This suggests the
following: given a strong monoidal functor
$F:\mathsf{fSet}\longrightarrow\mathcal{C}$, let $X:=F([1])$ and let
$\mu^{[k]}:=F([k]\longrightarrow[1])$. This determines a structure of a
commutative algebra object on $X$. Conversely, if $A\in\mathcal{C}$ is a
commutative algebra, we define a strong monoidal functor
$F:\mathsf{fSet}\longrightarrow\mathcal{C}$ as follows: first set $F([1]):=A$.
For a map of sets $f:[n]\longrightarrow[m]$, let $k_{i}:=\\#f^{-1}(i)\geq 0$
for every $i\in[m]$. If $\sigma\in\Sigma_{n}$ is any permutation that maps the
subset $\\{k_{1}+\cdots+k_{i-1}+1,\ldots,k_{1}+\cdots+k_{i}\\}$ to
$f^{-1}(i)$, then define

$Ff:=\mu^{[k_{1},\ldots,k_{m}]}\circ P_{\sigma},$

where $P_{\sigma}:A^{\otimes n}\longrightarrow A^{\otimes n}$ is as above. The
commutativity of $A$ ensures that any choice of $\sigma\in\Sigma_{n}$ yields
the same arrow. This shows, by 2.1, that $\mathsf{fSet}$ is equivalent to the
PROP $\mathsf{ComA}$ for commutative algebras.

Let us illustrate the previous construction in the case
$\mathcal{C}=\mathsf{Vect_{k}}$, the category of vector spaces over a field
$k$. If $A$ is an algebra and $f:[n]\longrightarrow[m]$ then

$(Ff)(a_{1}\otimes\cdots\otimes a_{n})=\left(\prod_{i\in
f^{-1}(1)}a_{i}\right)\otimes\cdots\otimes\left(\prod_{i\in
f^{-1}(m)}a_{i}\right),$

where an empty product stands for $1\in A$.

By reversing arrows, we have that $\mathsf{fSet}^{op}$ is equivalent to the
PROP $\mathsf{CocomC}$ for cocomutative coalgebras.

######  Example 2.5 ([Pir02]).

Now suppose we want to refine the previous example to obtain the PROP
$\mathsf{A}$ for (noncommutative) algebras. If the order of multiplication
matters, we are forced to impose an order on the fibres $f^{-1}(i)$, which in
turn determines a unique permutation.

More concretely, define $\widetilde{\mathsf{fSet}}$ as the following category:
its objects are the ordinals $[n]$, $n\geq 0$. An arrow
$f:[n]\longrightarrow[m]$ is the data of a map of sets
$f:[n]\longrightarrow[m]$ together with a total order of $f^{-1}(i)$ for every
$i\in[m]$. Given arrows $f:[n]\longrightarrow[m]$ and
$g:[m]\longrightarrow[p]$, the composite $g\circ f$ is defined as the
composite of the underlying maps of sets together with the following order on
fibres: for $i\in[p]$, let

$(g\circ f)^{-1}(i):=f^{-1}(j_{1})\amalg\cdots\amalg f^{-1}(j_{r})$ (2.4)

where $g^{-1}(i)=\\{j_{1}<\cdots<j_{r}\\}$ and the disjoint union carries the
order imposed by the writing from left to right. The disjoint union makes it a
symmetric monoidal category in the obvious way. Reasoning as in the previous
example, we see that given a map $f$ there is a unique $\sigma\in\Sigma_{n}$
mapping the ordered set
$\\{k_{1}+\cdots+k_{i-1}+1<\cdots<k_{1}+\cdots+k_{i}\\}$ to $f^{-1}(i)$ in an
order-preserving way222This is another way of saying that the associative
operad $\mathsf{Ass}(n)$ equals $\Sigma_{n}$., and therefore
$\widetilde{\mathsf{fSet}}$ is equivalent to the PROP for algebras.

As a concrete instance of this construction, let

$\displaystyle f:[5]\longrightarrow[4]\quad$ $\displaystyle,\quad
f^{-1}(1)=\\{4<2\\}\quad,\quad f^{-1}(3)=\\{1<3\\}\quad,\quad
f^{-1}(4)=\\{5\\},$ $\displaystyle g:[4]\longrightarrow[2]\quad$
$\displaystyle,\quad g^{-1}(1)=\\{4<3\\}\quad,\quad g^{-1}(2)=\\{1<2\\}.$

Then the composite is determined by

$(g\circ f)^{-1}(1)=\\{5<1<3\\}\quad,\quad(g\circ f)^{-1}(2)=\\{4<2\\}.$

The order on fibres that $f$ determines yields a unique permutation
$\sigma=(143)\in\Sigma_{5}$ such that $Ff=\mu^{[2,0,2,1]}\circ P_{\sigma}$.
Likewise, $g$ determines a unique $\tau=(1423)\in\Sigma_{4}$ such that
$Fg=\mu^{[2,2]}\circ P_{\tau}$. If $\mathcal{C}=\mathsf{Vect_{k}}$, then
$(Ff)(a_{1}\otimes\cdots\otimes a_{5})=a_{4}a_{2}\otimes 1\otimes
a_{1}a_{3}\otimes a_{5}$ and $(Fg)(b_{1}\otimes\cdots\otimes
b_{4})=b_{4}b_{3}\otimes b_{1}b_{2}$.

What we learned from this example is that by adding extra data to the PROP for
commutative algebras, we were able to “fix the order of multiplication” and
obtain a PROP for algebras. We also see that the data of a total order on
fibres is equivalent to the datum of a permutation, since for
$f:[n]\longrightarrow[m]$ and $\sigma$ as before

$f^{-1}(i)=\\{\sigma(k_{1}+\cdots+k_{i-1}+1)<\cdots<\sigma(k_{1}+\cdots+k_{i})\\}.$

We can then replace the data of one by the data of the other.

######  Construction 2.6.

Let $\alpha\in\Sigma_{m}$ and let $k_{1},\ldots,k_{m}\geq 0$ be a sequence of
$m$ non-negative integers. If $n=\sum_{i}k_{i}$, then $\alpha$ induces a
permutation $\langle\alpha\rangle_{k_{1},\ldots,k_{m}}\in\Sigma_{n}$ which
permutes the $m$ consecutive blocks of $[n]$ with sizes $k_{1},\ldots,k_{m}$.
More precisely, for $i\in[m]$, define
$\langle\alpha\rangle_{k_{1},\ldots,k_{m}}$ as the unique permutation that
sends
$\\{k_{\alpha(1)}+\cdots+k_{\alpha(i-1)}+1,\ldots,k_{\alpha(1)}+\cdots+k_{\alpha(i)}\\}$
to $\\{k_{1}+\cdots+k_{\alpha(i)-1}+1,\ldots,k_{1}+\cdots+k_{\alpha(i)}\\}$ in
a order-preserving way.

A schematic of this construction is shown in Figure 2. It is immediate to
check that

$\langle\alpha\rangle_{1,\overset{m}{\ldots},1}=\alpha\qquad,\qquad\langle\mathrm{Id}_{m}\rangle_{k_{1},\ldots,k_{m}}=\mathrm{Id}_{n}$

for any $\alpha\in\Sigma_{m}$ and $k_{1},\ldots,k_{m}\geq 0$.

$\underbrace{\bullet\
\bullet\quad\cdots\quad\bullet}_{k_{\alpha^{-1}(1)}}\quad\underbrace{\bullet\quad\cdots\quad\bullet}_{k_{\alpha^{-1}(2)}}\qquad\cdots\qquad\underbrace{\bullet\quad\cdots\quad\bullet}_{k_{\alpha^{-1}(m)}}$$\overbrace{\bullet\
\bullet\quad\cdots\quad\bullet}^{k_{1}}\quad\overbrace{\bullet\quad\cdots\quad\bullet}^{k_{2}}\qquad\cdots\qquad\overbrace{\bullet\quad\cdots\quad\bullet}^{k_{m}}$
Figure 2. Illustration of the construction of
$\langle\alpha\rangle_{k_{1},\ldots,k_{m}}$. If we label the bullets of the
upper row with the sequence $1,\ldots,n$, and we take each of the blocks to
the row below according to $\alpha$, that is, identifying in the two rows
blocks with the same index $k_{i}$, then the resulting labelling of the lower
row contains, from left to right, the values
$\langle\alpha\rangle_{k_{1},\ldots,k_{m}}(1),\ldots,\langle\alpha\rangle_{k_{1},\ldots,k_{m}}(n)$.

We also introduce the following notation: given two permutations
$\alpha\in\Sigma_{n}$, ${\beta\in\Sigma_{m}}$, we denote by
$\alpha\otimes\beta\in\Sigma_{n+m}$ the block product of $\alpha$ and $\beta$,
that is, the image of the the pair $(\alpha,\beta)$ under the “block
inclusion”

$\Sigma_{n}\times\Sigma_{m}\lhook\joinrel\longrightarrow\Sigma_{n+m}.$

Concretely,

$(\alpha\otimes\beta)(i)=\begin{cases}\alpha(i),&i=1,\ldots,n\\\
\beta(i-n)+n,&i=n+1,\ldots,n+m.\end{cases}$

######  Definition 2.7.

Let $\widehat{\mathsf{fSet}}$ be the following category: its objects are the
ordinals. An arrow is a pair $(f,\sigma)$ where $f$ is a map of sets
$f:[n]\longrightarrow[m]$ and $\sigma\in\Sigma_{n}$ is a permutation. Given
pairs $(f,\sigma)$ and $(g,\tau)$ with $f$ as before and
$g:[m]\longrightarrow[p]$, define the composite as

$(g,\tau)\circ(f,\sigma):=(g\circ
f,\sigma\circ\langle\tau\rangle_{k_{1},\ldots,k_{m}})$

where $k_{i}:=\\#f^{-1}(i)$ for every $i\in[m]$. The identity is the pair
$(\mathrm{Id},\mathrm{Id})$. Furthermore there is a monoidal product given by

$(f_{1},\sigma_{1})\otimes(f_{2},\sigma_{2}):=(f_{1}\amalg
f_{2},\sigma_{1}\otimes\sigma_{2}).$

######  Proposition 2.8.

The categories $\widehat{\mathsf{fSet}}$ and $\widetilde{\mathsf{fSet}}$ are
monoidally equivalent, so $\widehat{\mathsf{fSet}}$ is also equivalent to
$\mathsf{A}$.

###### Proof.

We have already described how giving an order on fibres amounts to giving a
permutation. Hence to see that this defines a functor
$\widetilde{\mathsf{fSet}}\longrightarrow\widehat{\mathsf{fSet}}$ all is left
to check is that under this correspondence the composite is mapped to the
composite.

Let $f:[n]\longrightarrow[m]$, $g:[m]\longrightarrow[p]$ be composable arrows
in $\widetilde{\mathsf{fSet}}$ with $\sigma\in\Sigma_{n}$, $\tau\in\Sigma_{m}$
the permutations that arise from the order of the fibres as explained in 2.5,
respectively. If $\delta$ is the permutation associated to the composite, then
it is determined by the following equality of ordered sets:

$\displaystyle\\{\delta(1)<\cdots<\delta(n)\\}$ $\displaystyle=(g\circ
f)^{-1}(1)\amalg\cdots\amalg(g\circ f)^{-1}(p)$ $\displaystyle=\coprod_{j\in
g^{-1}(1)\amalg\cdots\amalg g^{-1}(p)}f^{-1}(j)$
$\displaystyle=\coprod_{j\in\\{\tau(1)<\cdots<\tau(m)\\}}\\{\sigma(k_{1}+\cdots+k_{j-1}+1)<\cdots<\sigma(k_{1}+\cdots+k_{j})\\}.$

This expresses that $\delta$ is given by a block permutation of the set
$\\{\sigma(1)<\cdots<\sigma(n)\\}$, where the blocks have sizes
$k_{1},\ldots,k_{m}$ and the order of the block permutation is determined by
$\tau$. This exactly says that
$\delta=\sigma\circ\langle\tau\rangle_{k_{1},\ldots,k_{m}}$. ∎

###  2.3. Finitely generated free monoids

Recall that there is a free - forgetful adjunction

${\mathsf{Set}}$${\bot}$${\mathsf{Mon}}$$\scriptstyle{F}$$\scriptstyle{U}$

between the category of sets and the category of monoids, where
$F(X):=\coprod_{n\geq 0}X^{\times n}$ is given by “words on the alphabet $X$”.
We denote by $\mathsf{fgFMon}$ the category of finitely-generated free
monoids, that is, the full subcategory of $\mathsf{Mon}$ on the objects
$F([n])$, $n\geq 0$.

For the sake of clarity let us label $[n]=\\{x_{1}<\cdots<x_{n}\\}$ with
“$x$’s” or any other letter so that

$F(x_{1},\ldots,x_{n}):=F([n])=F(\\{x_{1},\ldots,x_{n}\\}).$

Observe that by the adjunction,

$\displaystyle\mathrm{Hom}_{\mathsf{Mon}}(F(x_{1},\ldots,x_{n}),F(y_{1},\ldots,y_{m}))$
$\displaystyle\cong\mathrm{Hom}_{\mathsf{Set}}(\\{x_{1},\ldots,x_{n}\\},UF(y_{1},\ldots,y_{m}))$
$\displaystyle\cong\prod_{i=1}^{n}\mathrm{Hom}_{\mathsf{Set}}(\\{x_{i}\\},UF(y_{1},\ldots,y_{m}))$
$\displaystyle\cong\prod_{i=1}^{n}UF(y_{1},\ldots,y_{m}),$

so any monoid map between free monoids is completely determined by a tuple of
words (the images of the elements $x_{i}$).

The category $\mathsf{fgFMon}$ has finite coproducts given by the free product
of monoids,

$F(x_{1},\ldots,x_{n})*F(y_{1},\ldots,y_{m})\cong
F(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}),$

which turns it into a cocartesian monoidal category, where the initial object
$\mathbf{1}:=F([0])$ (the trivial monoid) serves as the unit of the monoidal
product.

######  Example 2.9 ([Hab16]).

The object $F(x)=F([1])\in\mathsf{fgFMon}$ is a bialgebra object: the
multiplication and multiplication are given by

$\displaystyle\mu:F(x,y)\longrightarrow F(z)\qquad,\qquad x,y\mapsto z,$
$\displaystyle\Delta:F(x)\longrightarrow F(y,z)\qquad,\qquad x\mapsto yz,$

and the unit and counit are the unique maps $\eta:\mathbf{1}\longrightarrow
F(x)$ and $\varepsilon:F(x)\longrightarrow\mathbf{1}$. It is straightforward
to check that the bialgebra axioms (2.1) – (2.3) hold. For instance, both
sides of the associativity axiom from Figure 1(1(a)) are the map $x,y,z\mapsto
x$; from Figure 1(1(c)) they are the map $x\mapsto xyz$; and from Figure
1(1(e)) they are the map $x,y\mapsto ab$. The rest of axioms can be similarly
checked.

Therefore there is a functor

$T:\mathsf{ComB}\longrightarrow\mathsf{fgFMon}.$

It is a well-know result that the above functor is a monoidal equivalence.
Habiro [Hab16] showed this directly333Actually, Habiro showed the more general
result that the PROP for commutative Hopf algebras is equivalent to the
category of finitely generated free groups, but his construction easily
restricts to the bialgebra case., but it can also be proven using Lawvere
theories [Pir02].

######  Lemma 2.10.

The free monoid functor $F:\mathsf{fSet}\longrightarrow\mathsf{fgFMon}$ makes
the following diagram commutative,

${\mathsf{ComA}}$${\mathsf{ComB}}$${\mathsf{fSet}}$${\mathsf{fgFMon}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{F}$

where the upper arrow is the natural inclusion.

###### Proof.

This is immediate: the generator $\mu^{[k]}:k\longrightarrow 1$ of
$\mathsf{ComA}$, $k\geq 0$, is mapped under the two possible composites to the
monoid map $F(x_{1},\ldots,x_{k})\longrightarrow F(y)$ determined by
$x_{i}\mapsto y$ for all $1\leq i\leq k$, the iterated multiplication in
$\mathsf{fgFMon}$. ∎

######  Remark 2.11.

The non-existence of a right-adjoint for the free functor
$F:\mathsf{fSet}\longrightarrow\mathsf{Mon}$ can be seen as the failure of the
inclusion $\mathsf{ComA}\lhook\joinrel\longrightarrow\mathsf{ComB}$ to have a
right-adjoint.

##  3\. A PROP for bialgebras

The main question we want to address is whether it is possible to obtain a
PROP for (non)commutative bialgebras out of $\mathsf{fgFMon}$ by adding extra
data, as we did in the algebra case. We would like to start with some
motivating examples:

######  Example 3.1.

Let $A$ be a commutative algebra in $\mathsf{Vect}_{k}$, and let
$\mathsf{fgFMon}\longrightarrow\mathsf{Vect}_{k}$ be the functor making the
diagram

${\mathsf{ComB}}$${\mathsf{fgFMon}}$${\mathsf{Vect}_{k}}$$\scriptstyle{\simeq}$$\scriptstyle{A}$

commutative (up to natural isomorphism), so that we can view $A$ as a functor
$A:\mathsf{fgFMon}\longrightarrow\mathsf{Vect}_{k}$. Let us investigate this
point of view: the noncocomutativity of the comultiplication
$\Delta:A\longrightarrow A\otimes A$,

$\sum_{(a)}a_{(1)}\otimes a_{(2)}\neq\sum_{(a)}a_{(2)}\otimes a_{(1)},$

can be seen as a consequence of the non-equality of the monoid maps
$F(x)\longrightarrow F(y,z)$ given by $(x\mapsto yz)$ and $(x\mapsto zy)$.

Similarly, the commutativity of the multiplication $\mu:A\otimes
A\longrightarrow A$, $ab=ba$, can be seen as a consequence of the
commutativity of the following diagram:

${F(x,y)}$${F(x,y)}$${F(z)}$$\scriptstyle{P}$$\scriptstyle{\mu}$$\scriptstyle{\mu}$

where $P=(x\mapsto y,y\mapsto x)$. So producing noncommutative bialgebras
amounts to being able to distinguish $\mu$ and $\mu\circ P$. One way to
achieve this is as follows: note that the ordinals $[n]=\\{1<\cdots<n\\}$
carry a canonical order, which induces an order444Usually we write
$\\{x_{1},x_{2},x_{3},\ldots\\}=\\{a,b,c,\ldots\\}$. In the latter case the
order will always be alphabetical. on the subset
$\\{x_{1},\ldots,x_{n}\\}\subset F(x_{1},\ldots,x_{n})$. In particular, there
is a “canonically ordered” word $x_{1}\cdots x_{n}\in F(x_{1},\ldots,x_{n})$.
For the multiplication ${\mu:F(x,y)\longrightarrow F(z)}$, this element $xy$
maps to $z^{2}$. This corresponds to $a\otimes b\mapsto ab=ba$ one we pass to
the algebra. If we are interested in fixing the order of multiplication, we
could associate the permutation $\mathrm{Id}_{2}\in\Sigma_{2}$ to the first
option $a\otimes b\mapsto ab$ and $(12)\in\Sigma_{2}$ to the second one,
$a\otimes b\mapsto ba$. At the level of the free monoids, this corresponds to
associating $\mathrm{Id}_{2}$ to $\mu$ and $(12)$ to $\mu\circ P$.

######  Example 3.2.

Let $f:F(x)\longrightarrow F(y)$ be a monoid map, which necessarily must be
$x\mapsto y^{n}$ for some $n\geq 0$. Given a strong monoidal functor
$A:\mathsf{fgFMon}\longrightarrow\mathsf{Vect}_{k}$, this map will be sent to
the map $A\longrightarrow A$, $a\mapsto a_{(1)}\cdots a_{(n)}$ (one way to see
this is that $f$ factors as $f=\mu^{[k]}\Delta^{[k]}$). Since $A$ is a
commutative algebra, then $a_{(1)}\cdots a_{(n)}=a_{(\sigma(1))}\cdots
a_{(\sigma(n))}$ for any $\sigma\in\Sigma_{n}$. If we want to lift this
correspondence to the non-commutative case, we are forced to fix the
indeterminacy that the assignment $x\mapsto y^{n}$ carries for the order of
multiplication. If we fix $\sigma\in\Sigma_{n}$, then we also fix the order of
multiplication.

The above two examples suggest that to extend $\mathsf{fgFMon}$ to a PROP for
(noncommutative) bialgebras, we have to add the extra data of some
permutations that will determine the order of multuplication once we evaluate
in a algebra.

######  Notation 3.3.

Let $A$ be a bialgebra in $\mathsf{Vect}_{k}$ and let $f:n\longrightarrow m$
be an arrow in $\mathsf{B}$. If $A:\mathsf{B}\longrightarrow\mathsf{Vect}_{k}$
as a functor, then it is possible to read off $Ff$ (and hence $f$) from the
expression of $(Af)(a_{1}\otimes\cdots\otimes a_{n})\in A^{\otimes m}$. For
instance, if $(a\otimes b\mapsto\varepsilon(a_{(2)})b_{(1)}\otimes 1\otimes
b_{(2)}a_{(1)})$ then $Af$ must be

$Af=(\varepsilon\otimes\mathrm{Id}\otimes\eta\otimes\mu)\circ
P_{(1234)}\circ(\Delta\otimes\Delta)$

(obviously $f$ has the same expression). Therefore, for a algebra object $A$
of a symmetric monoidal category $\mathcal{C}$, we will adopt the convention
of writing maps $Af$ with the symbols that are used for $k$-algebras. Thence
when convenient we will denote a map in $\mathcal{C}$ as eg $(a\otimes
b\mapsto\varepsilon(a_{(2)})b_{(1)}\otimes 1\otimes b_{(2)}a_{(1)})$ keeping
in mind that there is no underlying set in $A$ and the expressing is purely
notational.

###  3.1. A unique normal form in $\mathsf{B}$

On our way to obtain an equivalent PROP for bialgebras it will become
essential to have control over the arrows we can find in $\mathsf{B}$. The
main result of this section ensures that any such an arrow has a unique
“normal form”. The main tool to show this will be the so-called “diamond
lemma”. Let us recall the setup.

Let $S$ be a set. A reduction on $S$ is a strictly antisymmetric relation of
$S$, that we denote as $\rightarrow$. A reduction chain on $S$ is a sequence
$x_{1}\rightarrow x_{2}\rightarrow x_{3}\rightarrow\cdots$. We say that the
relation $\rightarrow$ satisfies the descending chain condition if every
reduction chain is finite. An element $x\in S$ is said to be in normal form if
it is minimal with respect to $\rightarrow$, that is, if there is no $y\in S$
such that $x\rightarrow y$. Given a reduction $\rightarrow$ on $S$, its
transitive-reflexive closure is the order relation $\twoheadrightarrow$
defined as $x\twoheadrightarrow y$ if and only if there is a reduction chain
connecting $x$ and $y$. More formally, $x\twoheadrightarrow y$ if and only if
there exist $x_{0},\ldots,x_{n}\in S$ such that $x=x_{0}\rightarrow
x_{1}\rightarrow\cdots\rightarrow x_{n}=y$. Finally, we say that $\rightarrow$
satisfies the diamond condition if given $y\leftarrow x\rightarrow z$, there
exists $w\in S$ such that $y\twoheadrightarrow w$ and $z\twoheadrightarrow w$.

######  Lemma 3.4 (Diamond lemma).

Let $\rightarrow$ be a reduction on a non-empty set $S$. If $\rightarrow$
satisfies the descending chain condition and the diamond condition, then every
element in $S$ has a unique normal form.

We refer the reader to [BNDvdV21, 4.6] or [BW93, 4.47] for a proof of the
lemma.

######  Theorem 3.5.

Every morphism $f:n\longrightarrow m$ in $\mathsf{B}$ factors in a unique way
as

$f=\mu^{[q_{1},\ldots,q_{m}]}\circ
P_{\sigma}\circ\Delta^{[p_{1},\ldots,p_{n}]}$

for some (unique) integers $p_{1},\ldots,p_{n},q_{1},\ldots,q_{m}\geq 0$ such
that $\sum_{i}p_{i}=\sum_{i}q_{i}=:s$, and a (unique) permutation
$\sigma\in\Sigma_{s}$.

Graphically, we can represent this factorisation as depicted in Figure 3.

…
---

…
---
…
---
$\Delta^{[p_{1},\ldots,p_{n}]}$
---
$P_{\sigma}$
---
$\mu^{[q_{1},\ldots,q_{m}]}$
---

…
---

…
---

…
---

…
---

Figure 3.

The observation that ignites the proof is that in the relations that define
the bialgebra PROP $\mathsf{B}$, depicted in Figure 1, with the exception of
(a) and (c) (since in the statement of the above theorem the iterated
(co)multiplication appears), only one of the sides of the equations are in the
normal form that the theorem suggests.

Following the construction described in subsection 2.2, let $\mathcal{B}$ be
the PROP arising from a set of generators $\mathcal{G}$ containing
$\mu:2\longrightarrow 1$, $\eta:0\longrightarrow 1$, $\Delta:1\longrightarrow
2$ and $\varepsilon:1\longrightarrow 0$ and a set of equations $\mathcal{E}$
containing the equations appearing in Figure 1(a),(c). Next we are going to
define a reduction on the set

$\mathrm{arr}(\mathcal{B}):=\coprod_{n,m\geq
0}\mathrm{Hom}_{\mathcal{B}}(n,m).$

Let

$\displaystyle\mu(\mathrm{Id}\otimes\eta)\rightarrow\mathrm{Id}\leftarrow\mu(\eta\otimes\mathrm{Id})\qquad$
$\displaystyle,\qquad(\mathrm{Id}\otimes\varepsilon)\Delta\rightarrow\mathrm{Id}\leftarrow(\varepsilon\otimes\mathrm{Id})\Delta$
$\displaystyle\Delta\mu\rightarrow(\mu\otimes\mu)(\mathrm{Id}\otimes
P_{A,A}\otimes\mathrm{Id})(\Delta\otimes\Delta)\qquad$
$\displaystyle,\qquad\Delta\eta\rightarrow\eta\otimes\eta$
$\displaystyle\varepsilon\mu\rightarrow\varepsilon\otimes\varepsilon\qquad$
$\displaystyle,\qquad\varepsilon\eta\rightarrow\mathrm{Id}_{\mathds{1}}$

be the elementary reductions, and extend $\rightarrow$ to
$\mathrm{arr}(\mathcal{B})$ in way compatible with the composite and the
monoidal product, that is, if $f\rightarrow g$ is an elementary reduction then

$h_{4}\circ(h_{2}\otimes f\otimes h_{3})\circ h_{1}\rightarrow
h_{4}\circ(h_{2}\otimes g\otimes h_{3})\circ h_{1}$

for any arrows $h_{1},\ldots,h_{4}\in\mathrm{arr}(\mathcal{B})$ (so long as
the composite makes sense).

######  Lemma 3.6.

The subset of elements of $\mathrm{arr}(\mathcal{B})$ in normal form with the
reduction described above equals the set

$\\{\mu^{[q_{1},\ldots,q_{m}]}\circ
P_{\sigma}\circ\Delta^{[p_{1},\ldots,p_{n}]}:p_{1},\ldots,p_{n},q_{1},\ldots,q_{m}\geq
0,\sum_{i}p_{i}=\sum_{i}q_{i}=:s,\sigma\in\Sigma_{s}\\}.$

###### Proof.

It is clear that the elements of this set are in normal form, since there is
no (elementary) reduction possible. Conversely, suppose an element of
$\mathrm{arr}(\mathcal{B})$ is in normal form. Then it must be some (not any)
monoidal product and composite of the following “building blocks”:

$P_{\sigma}\quad,\quad\mu^{[q]}\quad,\quad\Delta^{[p]}\quad,\quad(\mu\otimes\mu)(\mathrm{Id}\otimes
P_{A,A}\otimes\mathrm{Id})(\Delta\otimes\Delta)\quad,\quad\eta\otimes\eta\quad,\quad\varepsilon\otimes\varepsilon$

(note any of the three first morphisms includes the identity). By the
naturality of the symmetry $P$, any monoidal product and composite of arrows
$P_{\sigma}$ and iterated multiplications $\mu^{[q]}$ equals (in the category
$\mathcal{B}$) $\mu^{[q_{1},\ldots,q_{m}]}\circ P_{\sigma^{\prime}}$ for some
$\sigma^{\prime}\in\Sigma_{q_{1}+\cdots+q_{m}}$ and some $m\geq 0$. Similarly,
any monoidal product and composite of arrows $P_{\sigma}$ and iterated
comultiplications $\mu^{[q]}$ equals
$P_{\sigma^{\prime}}\circ\Delta^{[p_{1},\ldots,p_{n}]}$ for some $n\geq 0$.
Furthermore, we can get the three latter arrows by means of the three first
arrows, setting $p=0=q$ and using the monoidal product. Hence we are left to a
monoidal product and composite of the three first arrows. But in that
composite we cannot find a $\mu^{[q]}$ before a $\Delta^{[p]}$ since it would
violate the normal form hypothesis. So we are left to the elements of the
given set, as required. ∎

###### Proof of Theorem 3.5.

By the previous lemma, it suffices to check that the reduction $\rightarrow$
on $\mathrm{arr}(\mathcal{B})$ satisfies the conditions of the Diamond lemma,
since there is a canonical full functor
$\pi:\mathcal{B}\longrightarrow\mathsf{B}$ with the property that reduction
chains map to chains of equalities.

That the relation $\rightarrow$ satisfies the descending chain condition
follows since any element of $\mathrm{arr}(\mathcal{B})$ is a finite composite
of finite many generators, there are finitely many elementary reductions,
there are no reduction loops (if $f\rightarrow g$ then no reduction chain
starting from $g$ can hit $f$, as $\mathcal{B}$ arises as a free category
where only the (co)associativity relation is modded out) and the identity
morphism is in normal form.

To check the diamond condition, let $f_{1}\leftarrow f\rightarrow f_{2}$. If
either $f_{1}$ or $f_{2}$ is in normal form, then so is the other and
$f_{1}=f_{2}$. For if $f_{2}$ is in formal form then $f$ must only differ from
it in one reduction. This means that there is no other reduction possible in
$f$, so if $f\rightarrow f_{1}$ then $f_{1}=f_{2}$. For the general case, if
$f_{1}\leftarrow f\rightarrow f_{2}$, then $f_{1}$ and $f_{2}$ differ from $f$
by two (possibly different) reductions. But then we can always apply the
elementary reduction that induces $f\rightarrow f_{2}$ to $f_{1}$, and
similarly to $f_{2}$, which by construction must yield the same element,
$f_{2}\rightarrow g\leftarrow f_{1}$, hence the diamond. ∎

######  Corollary 3.7.

Every morphism $f:n\longrightarrow m$ in $\mathsf{A}$ factors in a unique way
as

$f=\mu^{[q_{1},\ldots,q_{m}]}\circ P_{\sigma}$

for some (unique) integers $q_{1},\ldots,q_{m}\geq 0$ and
$\sigma\in\Sigma_{n}$.

######  Remark 3.8.

The existence of the factorisation of 3.5 is shown in [Hab16, Lemma 2] in a
more general context (namely for the PROP for commutative Hopf algebras) using
a different approach, yet the arguments used there are essentially the same as
the ones used in 3.6. We prefer to use an argument involving the diamond lemma
to get existence and uniqueness at once. Also note that for the PROP for
(commutative) Hopf algebras, uniqueness is not possible, by the antipode
axiom.

###  3.2. The main theorem

Let us write $\mathbb{N}$ for the monoid of non-negative integers. Recall that
the forgetful functor $U:\mathsf{CMon}\longrightarrow\mathsf{Mon}$ from
commutative monoids to monoids has a left-adjoint
$(-)^{ab}:\mathsf{Mon}\longrightarrow\mathsf{CMon}$ given by the
abelianisation of the monoid, that is, the quotient by the smallest congruence
relation containing the relations $mn\sim nm$. In particular, we have

$F(x_{1},\ldots,x_{n})^{ab}\cong\mathbb{N}x_{1}\oplus\cdots\oplus\mathbb{N}x_{n}$

where $\oplus$ is the biproduct (both product and coproduct) of the category
$\mathsf{CMon}$.

Denote by $\pi_{i}$ the composite

$F(x_{1},\ldots,x_{n})\longrightarrow\mathbb{N}x_{1}\oplus\cdots\oplus\mathbb{N}x_{n}\longrightarrow\mathbb{N}x_{i}$

where the first map is the natural map to the abelianisation and the second
map is the $i$-th projection. Likewise, we will denote as $\pi$ the composite

$F(x_{1},\ldots,x_{n})\longrightarrow\mathbb{N}x_{1}\oplus\cdots\oplus\mathbb{N}x_{n}\longrightarrow\mathbb{N}$

where the first map is as before and the second map is the unique map coming
from the coproduct such that the composites
$\mathbb{N}x_{i}\longrightarrow\mathbb{N}x_{1}\oplus\cdots\oplus\mathbb{N}x_{n}\longrightarrow\mathbb{N}$
are the identity maps (this is the “sum” map). For $w\in
F(x_{1},\ldots,x_{n})$, it should be clear that $\pi_{i}(w)$ counts how many
times the letter $x_{i}$ appears in $w$, whereas $\pi(w)$ counts the total
number of letters $w$ contains.

######  Definition 3.9.

Let $\widehat{\mathsf{fgFMon}}$ be the following category: its objects are the
free monoids $F([n])=F(x_{1},\ldots,x_{n})$, $n\geq 0$. An arrow is a pair
$(f,\bm{\sigma})$, where

$f:F(x_{1},\ldots,x_{n})\longrightarrow F(y_{1},\ldots,y_{m})$

is a monoid map and $\bm{\sigma}=(\sigma_{1},\ldots,\sigma_{m})$ is a tuple of
$m$ permutations $\sigma_{i}\in\Sigma_{k_{i}}$, where
$k_{i}:=\pi_{i}(f(x_{1}\cdots x_{n}))$. The identity of an object
$F(x_{1},\ldots,x_{n})$ is given by the identity monoid homomorphism and $n$
copies of the unique element $\mathrm{Id}_{1}\in\Sigma_{1}$. Moreover, this
category is symmetric monoidal (hence a PROP) where the monoidal product is
given by the free product $*$ of monoids on objects and

$(f,\bm{\sigma})\otimes(g,\bm{\tau}):=(f*g,\bm{\sigma\tau})$

on morphisms. In the above expression, $\bm{\sigma\tau}$ stands for the
concadenation of the two tuples of permutations. The unit is the trivial
monoid $\bm{1}=F([0])$.

We still have to describe the composite law in $\widehat{\mathsf{fgFMon}}$.
Setting up a formula for the composite is a highly non-trivial task and
requires several constructions that we describe in the next subsection. Yet we
would like to place the expression here for future reference. Given arrows
$(f,\bm{\sigma}):F(x_{1},\ldots x_{n})\longrightarrow F(a_{1},\ldots,a_{m})$
and $(g,\bm{\tau}):F(a_{1},\ldots,a_{m})\longrightarrow
F(s_{1},\ldots,s_{\ell})$, the composite
$(g,\bm{\tau})\circ(f,\bm{\sigma})=:(g\circ f,\bm{\tau}\circ\bm{\sigma})$ will
consist of $\ell$ permutations

$\bm{\tau}\circ\bm{\sigma}:=((\bm{\tau}\circ\bm{\sigma})_{1},\ldots,(\bm{\tau}\circ\bm{\sigma})_{\ell})$

where $(\bm{\tau}\circ\bm{\sigma})_{i}\in\Sigma_{\pi_{i}(gf(x_{1}\cdots
x_{n}))}$. These permutations are uniquely determined by the following
formula:

$\displaystyle\begin{split}(\bm{\tau}\circ\bm{\sigma})_{1}\otimes\cdots\otimes(\bm{\tau}\circ\bm{\sigma})_{\ell}&=\xi_{(g\circ
f)(x_{1}\cdots x_{n})}\circ\rho_{f,\mu^{[m]}\circ
g}\circ(\gamma_{(k_{1},p_{1})}\otimes\cdots\otimes\gamma_{(k_{m},p_{m})})\\\
&\circ(\sigma_{1}^{\otimes p_{1}}\otimes\cdots\otimes\sigma_{m}^{\otimes
p_{m}})\circ\langle\Psi(g(a_{1}\cdots a_{m}),\bm{\tau})\rangle_{k_{1}^{\times
p_{1}},\ldots k_{m}^{\times p_{m}}}\end{split}$ (3.1)

where $p_{i}:=\pi(g(a_{i}))$ and $k_{i}:=\pi_{i}(f(x_{1}\cdots x_{n}))$ for
$1\leq i\leq m$. The symbols used here are explained in 3.13, 3.15 and 3.16.

Although strange, the previous composite law yields the following

######  Theorem 3.10.

The categories $\widehat{\mathsf{fgFMon}}$ and $\mathsf{B}$ are monoidally
equivalent. In other words, they are equivalent PROPs.

The proof of this theorem consists of a long construction and will carried out
in next subsection. Part of this construction will consist of establishing the
expression (3.1).

######  Remark 3.11.

Informally, we would like to convince the reader that the previous theorem is
true. Starting from the base that there is an equivalence
$\mathsf{ComB}\simeq\mathsf{fgFMon}$ as explained in 2.9, the permutations
that we added to the monoid maps will fix the order of the multiplication.
More concretely, $(\mu,\mathrm{Id})\circ(P,\bm{\mathrm{Id}})=(\mu,(12))$,
compare with 3.1. Yet these permutations do not add extra data to the rest of
structure maps: for the iterated comultiplication
$\Delta^{[m]}:F(x)\longrightarrow F(y_{1},\ldots,y_{m})$, $x\mapsto
y_{1}\cdots y_{m}$, we have that $\pi_{i}(y_{1}\cdots y_{m})=1$, so the $m$
permutations that accompany $\Delta^{[m]}$ must be the trivial ones,
$\mathrm{Id}_{1}\in\Sigma_{1}$. For the unit $\eta:\bm{1}\longrightarrow F(y)$
and the counit $\varepsilon:F(x)\longrightarrow 1$ this is even more vacuous,
since there cannot be any permutation attached. Thence the permutations only
add extra data for the multiplication map, which is precisely what we want to
refine.

###  3.3. Proof of Theorem 3.10

Our strategy consists of constructing, for any symmetric monoidal category
$\mathcal{C}$, a bijection

$\mathsf{Alg}_{\widehat{\mathsf{fgFMon}}}(\mathcal{C})\overset{\cong}{\longrightarrow}\mathsf{Alg}_{\mathsf{B}}(\mathcal{C})$

natural on $\mathcal{C}$ and appeal to 2.1. The hardest part of the proof will
be to check (or rather, to define) that the cumbersome composite law (3.1)
models the order of multiplication in a bialgebra. The first step in the
construction is the following

######  Lemma 3.12.

The object $F([1])=F(x)\in\widehat{\mathsf{fgFMon}}$ is a bialgebra object. It
has structure maps $\mu,\eta,\Delta,\varepsilon$ whose underlying monoid maps
are the same as in 2.9 and whose attached permutations are the identities.

The proof of the lemma requires to handle the composition law of
$\widehat{\mathsf{fgFMon}}$, that we agreed we will describe later. Thus we
defer this proof until page 3.3.

This gives rise to a functor

$T:\mathsf{B}\longrightarrow\widehat{\mathsf{fgFMon}},$

which by precomposition defines a map

$\mathsf{Alg}_{\widehat{\mathsf{fgFMon}}}(\mathcal{C})\longrightarrow\mathsf{Alg}_{\mathsf{B}}(\mathcal{C})$
(3.2)

natural on $\mathcal{C}$.

We aim to define an inverse for the previous map (3.2). For that purpose a key
point will be to understand how we can get large permutations from smaller
ones “patched” according to a certain element of a free monoid.

Recall that a partition in $m\geq 0$ blocks on a set $S$ is a collection of
$m$ pairwise disjoint subsets $S_{1},\ldots,S_{m}\subseteq S$ (some of them
possibly empty) such that $\cup_{i}S_{i}=S$. If $S$ is ordered, so are the
subsets $S_{i}$. We denote by $\mathrm{Part}_{m}(S)$ the set of partitions in
$m$ blocks on $S$.

######  Construction 3.13.

Let $m\geq 0$. Given a word $w\in F(y_{1},\ldots,y_{m})$, we will construct a
partition of the set $[\pi(w)]$ given by $m$ subsets $S_{i}$, each of them
with $\pi_{i}(w)$ elements. Write $w$ as a product of the elements $y_{i}$
with no powers (this is a product of $\pi(w)$ letters). Then $S_{i}$ is the
ordered subset containing the positions, from left to right, where the letter
$y_{i}$ appears in $w$. Denote by $\Phi(w)$ the partition defined this way.

######  Lemma 3.14.

Let $m\geq 0$. The previous construction defines a bijection

$\Phi:F(y_{1},\ldots,y_{m})\overset{\cong}{\longrightarrow}\coprod_{N\geq
0}\mathrm{Part}_{m}([N]).$ (3.3)

###### Proof.

The obvious inverse is defined as the map taking a partition
$S_{1},\ldots,S_{m}$ of $[N]$ to the word $w$ product of $N$ letters $y_{i}$
according to the order specified by the subsets $S_{i}$. This establishes the
bijection. ∎

######  Construction 3.15.

Given a word $w\in F(y_{1},\ldots,y_{m})$ and $\Phi(w)=(S_{1},\ldots,S_{m})$,
let $\xi_{w}\in\Sigma_{\pi(w)}$ be the unique permutation mapping $S_{i}$ to

$\left\\{\sum_{j=1}^{i-1}\pi_{j}(w)+1<\cdots<\sum_{j=1}^{i}\pi_{j}(w)\right\\}$

in a order-preserving way. We can think of this permutation as “turning” the
word $a_{1}^{\pi_{1}(w)}\cdots a_{m}^{\pi_{m}(w)}$ into $w$. A schemantic of
this permutation is depicted in Figure 4. A special instance of this
construction is the case where $w_{0}=(y_{1}\cdots
y_{m})\overset{p}{\cdots}(y_{1}\cdots y_{m})$. In this case we denote

$\gamma_{(m,p)}:=\xi_{w_{0}}^{-1}\in\Sigma_{mp}.$

Explicitly,

$\gamma_{(m,p)}(lm+r):=(r-1)p+(l+1)$

for $0\leq l\leq p-1$ and $1\leq r\leq m$. It is straightforward to check that
$\gamma_{(m,1)}=\mathrm{Id}_{m}$ and $\gamma_{(1,p)}=\mathrm{Id}_{p}$.

Note that if

$w=y_{1}^{k_{1,1}}y_{2}^{k_{2,1}}\cdots
y_{m}^{k_{m,1}}y_{1}^{k_{1,2}}y_{2}^{k_{2,2}}\cdots y_{m}^{k_{m,p}}\in
F(y_{1},\ldots,y_{m})$ (3.4)

for some $k_{i,j}\geq 0$, then we have

$\xi_{w}=\langle\xi_{w_{0}}\rangle_{k_{1,1},k_{1,2},\ldots,k_{p,m}}\in\Sigma_{\pi(w)}.$

$\overbrace{\underbrace{k_{1,1}}\
\underbrace{k_{1,2}}\quad\cdots\quad\underbrace{k_{1,p}}}^{p}\quad\overbrace{\underbrace{k_{2,1}}\quad\cdots\quad\underbrace{k_{2,p}}}^{p}\qquad\cdots\qquad\overbrace{\underbrace{k_{m,1}}\quad\cdots\quad\underbrace{k_{m,p}}}^{p}$$\underbrace{\overbrace{k_{1,1}}\
\overbrace{k_{2,1}}\quad\cdots\quad\overbrace{k_{m,1}}}_{m}\quad\underbrace{\overbrace{k_{1,2}}\quad\cdots\quad\overbrace{k_{m,2}}}_{m}\qquad\cdots\qquad\underbrace{\overbrace{k_{1,p}}\quad\cdots\quad\overbrace{k_{m,p}}}_{m}$
Figure 4. Schemantic of the permutation $\xi_{w}\in\Sigma_{\pi(w)}$. Given an
arbitrary word $w\in F(y_{1},\ldots,y_{m})$ of the form (3.4), if we divide
$\\{1<\cdots<\pi(w)\\}$ in $mp$ blocks of sizes $k_{i,j}$, then $\xi_{w}$
shuffles them placing the blocks $k_{1,1},\ldots,k_{m,1}$ in the first
position, after that the blocks $k_{1,2},\ldots,k_{m,2}$, etc. If $k_{i,j}=1$
for all $i,j$, then this illustration represents $\gamma_{(m,p)}^{-1}$.

If $f:F(x)\longrightarrow F(y_{1},\ldots,y_{m})$ with $f(x)=w$ and
$g:F(y_{1},\ldots,y_{m})\longrightarrow F(s)$, with $f(y_{i})=s^{p_{i}}$,
$p_{i}\geq 0$, we define

$\rho_{f,g}:=(\langle\xi_{w}\rangle_{p_{1}^{\times k_{1}},\ldots,p_{m}^{\times
k_{m}}})^{-1}$ (3.5)

where $k_{i}:=\pi_{i}(w)$ and $p_{1}^{\times k_{1}}$ stands for a sequence
$p_{i},\ldots,p_{i}$ with $k_{i}$ times $p_{i}$.

######  Construction 3.16.

Let $k_{1},\ldots k_{m}\geq 0$ and let $n=\sum_{i}k_{i}$. Write

$\mathcal{W}(k_{1},\ldots,k_{m}):=\\{w\in
F(y_{1},\ldots,y_{m}):\pi_{i}(w)=k_{i},\ 1\leq i\leq m\\}.$

We define a map

$\Psi_{k_{1},\ldots,k_{m}}=\Psi:\mathcal{W}(k_{1},\ldots,k_{m})\times\Sigma_{k_{1}}\times\cdots\times\Sigma_{k_{m}}\longrightarrow\Sigma_{n}$

as follows:

$\Psi(w,\sigma_{1},\ldots,\sigma_{m}):=\xi_{w}^{-1}\circ(\sigma_{1}\otimes\cdots\otimes\sigma_{m}).$

######  Lemma 3.17.

The previous map

$\Psi:\mathcal{W}(k_{1},\ldots,k_{m})\times\Sigma_{k_{1}}\times\cdots\times\Sigma_{k_{m}}\overset{\cong}{\longrightarrow}\Sigma_{n}$

is a bijection. Furthermore, it is “monoidal” in the sense that the diagram

${\mathcal{W}(k_{1},\ldots,k_{m})\times\prod_{i=1}^{m}\Sigma_{k_{i}}\times\mathcal{W}(k_{1}^{\prime},\ldots,k^{\prime}_{r})\times\prod_{i=1}^{r}\Sigma_{k^{\prime}_{i}}}$${\Sigma_{n}\times\Sigma_{n^{\prime}}}$${\mathcal{W}(k_{1},\ldots,k_{m},k^{\prime}_{1},\ldots,k^{\prime}_{r})\times\prod_{i=1}^{m}\Sigma_{k_{i}}\times\prod_{i=1}^{r}\Sigma_{k^{\prime}_{i}}}$${\Sigma_{n+n^{\prime}}}$$\scriptstyle{\Psi_{k_{1},\ldots,k_{m}}\times\Psi_{k^{\prime}_{1},\ldots,k^{\prime}_{r}}}$$\scriptstyle{\otimes}$$\scriptstyle{\Psi_{k_{1},\ldots,k_{m},k^{\prime}_{1},\ldots,k^{\prime}_{r}}}$

commutes, where $n^{\prime}=\sum_{i}k^{\prime}_{i}$ and the left-hand arrow
concadenates the words and acts as the identity on the symmetric groups.

###### Proof.

Observe that the cardinality of $\mathcal{W}(k_{1},\ldots,k_{m})$ is the
multinomial coefficient $\binom{n}{k_{1},\ldots,k_{m}}$, which means that the
source and target of $\Psi$ have the same cardinality since

$\binom{n}{k_{1},\ldots,k_{m}}=\frac{n!}{k_{1}!\ldots k_{m}!}.$

Hence it suffices to check that $\Psi$ is surjective: given
$\alpha\in\Sigma_{n}$, turn the formal word $z_{1}\cdots z_{n}$ into a word
$w\in F(y_{1},\ldots,y_{m})$ by the following rule:

$z_{i}:=\begin{cases}y_{1},&1\leq\alpha^{-1}(i)\leq k_{1}\\\
y_{2},&k_{1}+1\leq\alpha^{-1}(i)\leq k_{2}\\\ \vdots\\\
y_{m},&\sum_{j=1}^{m-1}k_{j}+1\leq\alpha^{-1}(i)\leq\sum_{j=1}^{m}k_{j}\end{cases}$

It is clear that $w\in\mathcal{W}(k_{1},\ldots,k_{m})$. By construction,
$\xi_{w}\circ\alpha$ is of the form $\sigma_{1}\otimes\cdots\otimes\sigma_{m}$
for some (unique) permutations $\sigma_{i}\in\Sigma_{k_{i}}$, what establishes
the bijection.

The commutativity of the diagram follows from the observation that the block
product of permutations is compatible with the group law of the symmetric
group555A more concise way to restate this is by saying that if we view
$\Sigma_{n}$ as a groupoid in the usual way, then the block product $\otimes$
makes $\Sigma_{n}$ a monoidal category. in the sense that

$(\sigma\otimes\sigma^{\prime})\circ(\tau\otimes\tau^{\prime})=(\sigma\circ\tau)\otimes(\sigma^{\prime}\circ\tau^{\prime}).$

Then we have

$\displaystyle\Psi_{k_{1},\ldots,k_{m}}(w,\sigma_{1},\ldots,\sigma_{m})$
$\displaystyle\otimes\Psi_{k^{\prime}_{1},\ldots,k^{\prime}_{r}}(w^{\prime},\sigma^{\prime}_{1},\ldots,\sigma^{\prime}_{m})$
$\displaystyle=[\xi_{w}^{-1}\circ(\sigma_{1}\otimes\cdots\otimes\sigma_{m})]\otimes[\xi_{w^{\prime}}^{-1}\circ(\sigma^{\prime}_{1}\otimes\cdots\otimes\sigma^{\prime}_{r})]$
$\displaystyle=(\xi_{w}^{-1}\otimes\xi_{w^{\prime}}^{-1})\circ(\sigma_{1}\otimes\cdots\otimes\sigma_{m}\otimes\sigma^{\prime}_{1}\otimes\cdots\otimes\sigma^{\prime}_{r})$
$\displaystyle=\xi_{ww^{\prime}}^{-1}\circ(\sigma_{1}\otimes\cdots\otimes\sigma_{m}\otimes\sigma^{\prime}_{1}\otimes\cdots\otimes\sigma^{\prime}_{r})$
$\displaystyle=\Psi_{k_{1},\ldots,k_{m},k^{\prime}_{1},\ldots,k^{\prime}_{r}}(ww^{\prime},\sigma_{1},\ldots,\sigma_{m},\sigma^{\prime}_{1},\ldots,\sigma^{\prime}_{m})$

which concludes. ∎

Now we are ready to define an inverse for (3.2). Given a bialgebra
$A\in\mathcal{C}$, define a functor

$\widehat{A}:\widehat{\mathsf{fgFMon}}\longrightarrow\mathcal{C}$

as follows: on objects, $\widehat{A}(F(x_{1},\ldots,x_{n})):=A^{\otimes n}$.
On morphisms, given an arrow
$(f,\bm{\sigma}):F(x_{1},\ldots,x_{n})\longrightarrow F(y_{1},\ldots,y_{m})$,
let

$p_{i}:=\pi(f(x_{i}))\quad,\quad q_{j}:=\pi_{j}(f(x_{1}\cdots
x_{n}))\quad,\quad\sigma:=\Psi(f(x_{1}\cdots x_{n}),\bm{\sigma})$

for $1\leq i\leq n$ and $1\leq j\leq m$ and define

$\widehat{A}(f,\bm{\sigma}):=\mu^{[q_{1},\ldots,q_{m}]}\circ
P_{\sigma}\circ\Delta^{[p_{1},\ldots,p_{n}]}.$ (3.6)

Let us illustrate the above assignment.

######  Example 3.18.

Let $(f,\bm{\sigma}):F(x,y)\longrightarrow F(a,b)$ be the map in
$\widehat{\mathsf{fgFMon}}$ determined by

$f(x):=a^{2}b\quad,\quad
f(y):=abab\quad,\quad\sigma_{1}:=(4321)\quad,\quad\sigma_{2}:=(13),$

where $\bm{\sigma}=(\sigma_{1},\sigma_{2})$. Note that
$\sigma_{1}\in\Sigma_{4}$ as $4=\pi_{1}(f(xy))=\pi_{1}(a^{2}babab)$ and
similarly $\sigma_{2}\in\Sigma_{3}$. We easily see that $p_{1}=3$, $p_{2}=4$,
$q_{1}=4$, $q_{2}=3$. Then

$\displaystyle\sigma$
$\displaystyle=\Psi(a^{2}babab,(4321),(13))=\xi_{ab^{2}abab}^{-1}\circ[(4321)\otimes(13)]$
$\displaystyle=(3456)(4321)(57)=(165732)\in\Sigma_{7}.$

Alternatively, this can also be computed as follows: consider the ordered sets
$A:=\\{z_{1},z_{2},z_{3},z_{4}\\}$ and $B:=\\{z_{5},z_{6},z_{7}\\}$, and let
$\sigma_{1}$ act on $A$ and $\sigma_{2}$ on $B$, which yields
$\sigma_{1}A=\\{z_{4},z_{1},z_{2},z_{3}\\}$ and
$\sigma_{2}B=\\{z_{7},z_{6},z_{5}\\}$. Next consider the ordered union
$\sigma_{1}A\amalg\sigma_{2}B=\\{z_{4},z_{1},z_{2},z_{3},z_{7},z_{6},z_{5}\\}$.
Now for $1\leq i\leq 4$, we replace the letter $z_{i}$ by $z_{o(i)}$ where
$o(i)$ is the position of the $i$-th letter $a$ in the pattern $aababab$.
Similarly for $1\leq i\leq 3$ replace $z_{i+4}$ by $z_{o^{\prime}(i)}$ where
$o^{\prime}(i)$ is the position of the $i$-th letter $b$ in the pattern,
according to the order from left to right. This yields the pattern
$z_{6}z_{1}z_{2}z_{4}z_{7}z_{5}z_{3}$. Then $\sigma$ is the permutation such
that the previous pattern equals $z_{\sigma(1)}\cdots z_{\sigma(7)}$, that is,
$\sigma=(165732)$, as above.

Following 3.3 we conclude that $\widehat{A}(f,\bm{\sigma})$ is the map

$x\otimes y\mapsto y_{(2)}x_{(1)}x_{(2)}x_{(4)}\otimes y_{(3)}y_{(1)}x_{(3)}.$

Let us continue with the proof of 3.10. The key point will be to set the
expression (3.1), which has to model all changes of indices that take place
when applying a combination of multiplication and comultiplication maps to an
element of a bialgebra. In other words, we have to set (3.1) so that
$\widehat{A}$ actually defines a functor.

######  Proposition 3.19.

Given a bialgebra $A\in\mathcal{C}$, we have that

$\widehat{A}((g,\bm{\tau})\circ(f,\bm{\sigma}))=\widehat{A}(g,\bm{\tau})\circ\widehat{A}(f,\bm{\sigma}),$
(3.7)

so that $\widehat{A}:\widehat{\mathsf{fgFMon}}\longrightarrow\mathcal{C}$ is
indeed a functor.

###### Proof.

Rather than a verification that (3.7) holds using (3.1), the proof will
construct the composite law (3.1) of $\widehat{\mathsf{fgFMon}}$ by imposing
the equality (3.7) and the associativity of the composite. We will subdivide
the proof in several steps, increasing the complexity of the maps at hand.

Step 1. We start by composing maps between the objects $F([1])$. Let
$(f,\sigma):F(x)\longrightarrow F(a)$, $x\mapsto a^{k}$ and
$(g,\tau):F(a)\longrightarrow F(s)$, $a\mapsto s^{p}$ for integers $k,p\geq
0$. If $\sigma=\mathrm{Id}_{k}\in\Sigma_{k}$ and
$\tau=\mathrm{Id}_{p}\in\Sigma_{p}$, then their images under $\widehat{A}$
correspond to the maps $x\mapsto x_{(1)}\cdots x_{(k)}$ and $a\mapsto
a_{(1)}\cdots a_{(p)}$. Their composite
$\widehat{A}(g,\mathrm{Id}_{p})\circ\widehat{A}(f,\mathrm{Id}_{k})$ is

$x\mapsto(x_{(1)}\cdots x_{(k)})_{(1)}\cdots(x_{(1)}\cdots
x_{(k)})_{(p)}=\prod_{i=1}^{p}x_{(i)}x_{(p+i)}\cdots x_{((n-1)p+i)}.$ (3.8)

This implies that the permutation associated to the composite is given by the
element ${\gamma_{(k,p)}\in\Sigma_{kp}}$, which was already defined in 3.15.
If $\sigma,\tau$ are not the identity permutations, then the left-hand side of
the above expression becomes

$x\mapsto(x_{(\sigma 1)}\cdots x_{(\sigma k)})_{(\tau 1)}\cdots(x_{(\sigma
1)}\cdots x_{(\sigma k)})_{(\tau p)}.$

This says that $\tau$ acts on (3.8) permuting blocks of size $k$, whereas
$\sigma$ acts inside each of the $p$ blocks. In total, the permutation
associated to the composite $\widehat{A}((g,\tau)\circ(f,\sigma))$ must be

$\gamma_{(k,p)}\circ(\sigma\otimes\overset{p}{\cdots}\otimes\sigma)\circ\langle\tau\rangle_{k,\overset{p}{\cdots},k}\in\Sigma_{kp}.$
(3.9)

Step 2. We want to study now the case where
$(f,\bm{\sigma}):F(x)\longrightarrow F(a_{1},\ldots,a_{m})$, $x\mapsto w$,
$\bm{\sigma}=(\sigma_{1},\ldots,\sigma_{m})$ and
$(g,\tau):F(a_{1},\ldots,a_{m})\longrightarrow F(s)$, $a_{i}\mapsto
s^{p_{i}}$, $p_{i}\geq 0$. Let us start from the base case where
$\sigma_{i}=\mathrm{Id}$ , $\tau=\mathrm{Id}$ and $w=a_{1}^{k_{1}}\cdots
a_{m}^{k_{m}}$. Here the situation is almost identical to the first part of
Step 1: $\widehat{A}(f,\bm{\sigma})$ corresponds to the map $x\mapsto
x_{(1)}\cdots x_{(k_{1})}\otimes x_{(k_{1}+1)}\cdots x_{(k_{2})}\otimes\cdots$
whereas $\widehat{A}(g,\tau)$ corresponds to $a_{1}\otimes\cdots\otimes
a_{m}\mapsto(a_{1})_{(1)}\cdots(a_{1})_{(p_{1})}\cdots(a_{m})_{(1)}\cdots(a_{m})_{(p_{m})}$,
so it follows reasoning with each of the “monoidal blocks” of
$\widehat{A}(f,\bm{\sigma})$ that the composite gets as permutation

$\gamma_{(k_{1},p_{1})}\otimes\cdots\otimes\gamma_{(k_{m},p_{m})}\in\Sigma_{N}$

where $N=k_{1}p_{1}+\cdots+k_{m}p_{m}$. Now suppose that $f(x)=w\in
F(a_{1},\ldots,a_{m})$ is a general element. We want to show that if
$\rho_{f,g}$ is defined from $\Phi(w)$ as above, the permutation associated to
the composite $\widehat{A}((g,\tau)\circ(f,\bm{\sigma}))$ is

$\rho_{f,g}\circ(\gamma_{(k_{1},p_{1})}\otimes\cdots\otimes\gamma_{(k_{m},p_{m})})\in\Sigma_{N}.$

For observe that the permutation $\xi_{w}$ is designed to keep track of the
“reordering” of the word $a_{1}^{\pi_{1}(w)}\cdots a_{m}^{\pi_{m}(w)}$ turning
into $w$. When passing to $\langle\xi_{w}\rangle_{p_{1}^{\times
k_{1}},\ldots,p_{m}^{\times k_{m}}}=\rho_{f,g}^{-1}$, we extend this
permutation to a block permutation according to the $p_{i}$’s. Taking the
inverse is needed (just as with $\gamma_{(m,p)}$) to match the indices and not
the positions. Lastly, if $\bm{\sigma}$ and $\tau$ are not trivial, then the
situation is again similar to the one in Step 1: we have that each of the
$\sigma_{i}$ acts inside $p_{i}$ blocks (of size $m_{i}$), whereas $\tau$ acts
permuting these blocks. An illustration of this is in Figure 5.

$(s\ \overset{k_{1}}{\cdots}\ s)\quad\overset{p_{1}}{\cdots}\quad(s\
\overset{k_{1}}{\cdots}\ s)\quad(s\ \overset{k_{2}}{\cdots}\
s)\quad\overset{p_{2}}{\cdots}\quad(s\ \overset{k_{2}}{\cdots}\
s)$$\circlearrowleft$$\sigma_{1}$$\circlearrowleft$$\sigma_{1}$$\circlearrowleft$$\sigma_{2}$$\circlearrowleft$$\sigma_{2}$$\underbrace{\phantom{(s\
\overset{k_{1}}{\cdots}\ s)}}$$\underbrace{\phantom{(s\
\overset{k_{1}}{\cdots}\ s)}}$$\cdots$$\cdots$$\underbrace{\phantom{(s\
\overset{k_{1}}{\cdots}\ s)}}$$\underbrace{\phantom{(s\
\overset{k_{1}}{\cdots}\ s)}}$$\circlearrowleft$$\tau$ Figure 5. Illustration
of the action of $\bm{\sigma}$ and $\tau$, for $m=2$.

In total, we conclude the permutation associated to the composite
$\widehat{A}((g,\tau)\circ(f,\bm{\sigma}))$ must be

$\rho_{f,g}\circ(\gamma_{(k_{1},p_{1})}\otimes\cdots\otimes\gamma_{(k_{m},p_{m})})\circ(\sigma_{1}^{\otimes
p_{1}}\otimes\cdots\otimes\sigma_{m}^{\otimes
p_{m}})\circ\langle\tau\rangle_{k_{1}^{\times p_{1}},\ldots k_{m}^{\times
p_{m}}}\in\Sigma_{N}$ (3.10)

where $k_{i}=\pi_{i}(w)$ and $N=k_{1}p_{1}+\cdots+k_{m}p_{m}.$

Step 3. Next we consider the case where
$(f,\bm{\sigma}):F(x_{1},\ldots,x_{n})\longrightarrow F(a_{1},\ldots,a_{m})$,
$x_{i}\mapsto w_{i}$, $\bm{\sigma}=(\sigma_{1},\ldots,\sigma_{m})$ and
$(g,\tau):F(a_{1},\ldots,a_{m})\longrightarrow F(s)$, $a_{i}\mapsto
s^{p_{i}}$, $p_{i}\geq 0$ as before. In this case, the claim is that the
formula (3.10) obtained in Step 2 still holds, taking $w:=f(x_{1}\cdots
x_{n})=w_{1}\cdots w_{n}$. Vaguely speaking, the reason is that in this case
$(f,\bm{\sigma})$ models a map $A^{\otimes n}\longrightarrow A^{\otimes m}$,
which is determined by the image of elements $x_{1}\otimes\cdots\otimes
x_{n}$.

More precisely, let us show that if we impose (3.7), then the equation

$(f,\bm{\sigma})\circ(\Delta^{[n]},\bm{\mathrm{Id}})=(f\circ\Delta^{[n]},\bm{\sigma})$
(3.11)

must hold. We have that

$\displaystyle\widehat{A}(f,\bm{\sigma})\circ\widehat{A}(\Delta^{[n]},\bm{\mathrm{Id}})$
$\displaystyle=(\mu^{[q_{1},\ldots,q_{m}]}\circ
P_{\sigma}\circ\Delta^{[p_{1},\ldots,p_{n}]})\circ\Delta^{[n]}$
$\displaystyle=\mu^{[q_{1},\ldots,q_{m}]}\circ
P_{\sigma}\circ\Delta^{[p_{1}+\cdots+p_{n}]}.$

Since we want the equation

$\widehat{A}(f,\bm{\sigma})\circ\widehat{A}(\Delta^{[n]},\bm{\mathrm{Id}})=\widehat{A}(f\circ\Delta^{[n]},\bm{\sigma}\circ\bm{\mathrm{Id}})$

to hold and $\sigma=\Psi(f(x_{1}\cdots
x_{n}),\bm{\sigma})=\Psi((f\circ\Delta^{[n]})(x),\bm{\sigma})$, then
$\bm{\sigma}\circ\bm{\mathrm{Id}}$ must be $\bm{\sigma}$. By associativity of
the composite, we must have

$\displaystyle(g\circ(f\circ\Delta^{[n]}),\tau\circ\bm{\sigma})$
$\displaystyle=(g,\tau)\circ[(f,\bm{\sigma})\circ(\Delta^{[n]},\bm{\mathrm{Id}})]$
$\displaystyle=[(g,\tau)\circ(f,\bm{\sigma})]\circ(\Delta^{[n]},\bm{\mathrm{Id}})$
$\displaystyle=(g\circ
f,\tau\circ\bm{\sigma})\circ(\Delta^{[n]},\bm{\mathrm{Id}})$
$\displaystyle=((g\circ f)\circ\Delta^{[n]},\tau\circ\bm{\sigma})$

where we have applied (3.11) in the first and third equality. Since the left-
hand side of the equation is computable in terms of the formula given in Step
2, the claim follows.

Step 4. Let us finally deal with the general case where
$(f,\bm{\sigma}):F(x_{1},\ldots x_{n})\longrightarrow F(a_{1},\ldots,a_{m})$
and $(g,\bm{\tau}):F(a_{1},\ldots,a_{m})\longrightarrow
F(s_{1},\ldots,s_{\ell})$, $a_{i}\mapsto w^{\prime}_{i}$ and
$\bm{\tau}=(\tau_{1},\ldots,\tau_{\ell})$. By Step 3, it is enough to consider
$(f,\bm{\sigma}):F(x)\longrightarrow F(a_{1},\ldots,a_{m})$, $x\mapsto w$,
$\bm{\sigma}=(\sigma_{1},\ldots,\sigma_{m})$. As explained before, the
composite $(g,\bm{\tau})\circ(f,\bm{\sigma})=(gf,\bm{\tau}\circ\bm{\sigma})$
will have $\ell$ associated permutations that are denoted as
$(\bm{\tau}\circ\bm{\sigma})_{1},\ldots,(\bm{\tau}\circ\bm{\sigma})_{\ell}$.

The strategy we follow is “dual” to the one of Step 3, where we read off the
composite with $(\Delta^{[n]},\bm{\mathrm{Id}})$. This time we want to show
that if $(f,\bm{\sigma}):F(x_{1},\ldots,x_{n})\longrightarrow
F(a_{1},\ldots,a_{m})$ then the equation

$(\mu^{[m]},\bm{\mathrm{Id}})\circ(f,\bm{\sigma})=(\mu^{[m]}\circ
f,\Psi(f(x_{1}\cdots x_{n}),\bm{\sigma}))$ (3.12)

must hold. Indeed for any bialgebra $A\in\mathcal{C}$ we have

$\displaystyle\widehat{A}(\mu^{[m]},\bm{\mathrm{Id}})\circ\widehat{A}(f,\bm{\sigma})$
$\displaystyle=\mu^{[m]}\circ(\mu^{[q_{1},\ldots,q_{m}]}\circ
P_{\sigma}\circ\Delta^{[p_{1},\ldots,p_{n}]})$
$\displaystyle=\mu^{[q_{1}+\cdots+q_{m}]}\circ
P_{\sigma}\circ\Delta^{[p_{1},\ldots,p_{n}]}$

where $\sigma=\Psi(f(x_{1}\cdots x_{n}),\bm{\sigma})$. Since we want the
equation

$\widehat{A}(\mu^{[m]},\bm{\mathrm{Id}})\circ\widehat{A}(f,\bm{\sigma})=\widehat{A}(\mu^{[m]}\circ
f,\bm{\mathrm{Id}}\circ\bm{\sigma})$

to hold, then $\bm{\mathrm{Id}}\circ\bm{\sigma}$ must be666Alternatively, we
could use (3.10), which yields the same result. $\sigma=\Psi(f(x_{1}\cdots
x_{n}),\bm{\sigma})=\xi_{f(x_{1}\cdots
x_{n})}^{-1}\circ(\sigma_{1}\otimes\cdots\otimes\sigma_{m})$. In particular,
this says that $\bm{\sigma}$ is determined by $\sigma$, since

$\sigma_{1}\otimes\cdots\otimes\sigma_{m}=\xi_{f(x_{1}\cdots
x_{n})}\circ\sigma$ (3.13)

and the map

$\Sigma_{k_{1}}\times\cdots\times\Sigma_{k_{m}}\lhook\joinrel\longrightarrow\Sigma_{k_{1}+\cdots+k_{m}}\quad,\quad(\sigma_{1},\ldots,\sigma_{m})\mapsto\sigma_{1}\otimes\cdots\otimes\sigma_{m}$

is injective. Therefore, for the composite
$(g,\bm{\tau})\circ(f,\bm{\sigma})$, using the associativity of the composite,
we must have

$\displaystyle((\mu^{[m]}\circ g)\circ f,\Psi(g(a_{1}\cdots
a_{m}),\bm{\tau})\circ\bm{\sigma})$
$\displaystyle=[(\mu^{[m]},\bm{\mathrm{Id}})\circ(g,\bm{\tau})]\circ(f,\bm{\sigma})$
$\displaystyle=(\mu^{[m]},\bm{\mathrm{Id}})\circ[(g,\bm{\tau})\circ(f,\bm{\sigma})]$
$\displaystyle=(\mu^{[m]},\bm{\mathrm{Id}})\circ(g\circ
f,\bm{\tau}\circ\bm{\sigma}).$

The first term is computable in terms of Step 2: if $p_{i}=\pi(g(a_{i}))$ and
$k_{i}=\pi_{i}(f(x))$ for $1\leq i\leq m$, then

$\displaystyle\Psi(g(a_{1}\cdots a_{m}),\bm{\tau})\circ\bm{\sigma}$
$\displaystyle=\rho_{f,\mu^{[m]}\circ
g}\circ(\gamma_{(k_{1},p_{1})}\otimes\cdots\otimes\gamma_{(k_{m},p_{m})})$
$\displaystyle\circ(\sigma_{1}^{\otimes
p_{1}}\otimes\cdots\otimes\sigma_{m}^{\otimes
p_{m}})\circ\langle\Psi(g(a_{1}\cdots a_{m}),\bm{\tau})\rangle_{k_{1}^{\times
p_{1}},\ldots k_{m}^{\times p_{m}}}$

Hence by (3.13), we conclude that

$\displaystyle(\bm{\tau}\circ\bm{\sigma})_{1}\otimes\cdots\otimes(\bm{\tau}\circ\bm{\sigma})_{\ell}$
$\displaystyle=\xi_{(g\circ f)(x)}\circ\rho_{f,\mu^{[m]}\circ
g}\circ(\gamma_{(k_{1},p_{1})}\otimes\cdots\otimes\gamma_{(k_{m},p_{m})})$
$\displaystyle\circ(\sigma_{1}^{\otimes
p_{1}}\otimes\cdots\otimes\sigma_{m}^{\otimes
p_{m}})\circ\langle\Psi(g(a_{1}\cdots a_{m}),\bm{\tau})\rangle_{k_{1}^{\times
p_{1}},\ldots k_{m}^{\times p_{m}}}$

as we wanted to show. ∎

###### Proof (of Lemma 3.12).

As in 2.9 all we need to check is that the maps

$\displaystyle(\mu,\mathrm{Id}):F(x,y)\longrightarrow F(z)\qquad,\qquad
x,y\mapsto z,$ $\displaystyle(\Delta,\bm{\mathrm{Id}}):F(x)\longrightarrow
F(y,z)\qquad,\qquad x\mapsto yz,$ $\displaystyle\eta:\bm{1}\longrightarrow
F(x)$ $\displaystyle\varepsilon:F(x)\longrightarrow\bm{1}$

satisfy the bialgebra axioms (2.1) – (2.3) (note that both $\eta$ and
$\varepsilon$ do not have any associated permutation as $\Sigma_{0}$ is
empty). We already checked in 2.9 that the equalities hold for the underlying
free monoid maps, so we are left to check that the associated permutations
coincide. For instance, for the associativity axiom from Figure 1(1(a)) we
have that both sides of the equation yield $\mathrm{Id}_{3}\in\Sigma_{3}$,
since $\langle\mathrm{Id}\rangle_{k_{1},\ldots}=\mathrm{Id}$,
$\gamma_{(k,1)}=\mathrm{Id}$ and $\xi_{y^{2}z}=\mathrm{Id}$. Perhaps the less
obvious verification is the bialgebra axiom from Figure 1(1(e)). In this case
$x,y\mapsto ab$ and the two associated permutations are given by the pair
$\bm{\mathrm{Id}}=(\mathrm{Id}_{2},\mathrm{Id}_{2})$. For both left- and
right-hand sides this follows since
$(23)(23)=\mathrm{Id}_{4}=\mathrm{Id}_{2}\otimes\mathrm{Id}_{2}$. The rest of
axioms are also easy to check and are left to the reader. ∎

We can now wrap up the proof of 3.10. We are left to check that the “hat”
construction (3.6) defines a two-sided inverse for (3.2). If $A\in\mathcal{C}$
is a bialgebra, then the composite

$\mathsf{B}\longrightarrow\widehat{\mathsf{fgFMon}}\overset{\widehat{A}}{\longrightarrow}\mathcal{C}$

defines the same bialgebra as $A$. This follows at once from 3.5 and the
functoriality of $\widehat{A}$. Conversely, if
$G:\widehat{\mathsf{fgFMon}}\longrightarrow\mathcal{C}$ is a functor, let
$A\in\mathcal{C}$ be the bialgebra determined by the composite

$\mathsf{B}\longrightarrow\widehat{\mathsf{fgFMon}}\overset{G}{\longrightarrow}\mathcal{C}.$

By construction, the structure maps of $A$ are given by
$G(\mu,\bm{\mathrm{Id}})$, $G(\Delta,\bm{\mathrm{Id}})$, $G(\eta)$ and
$G(\varepsilon)$. Given an arrow $(f,\bm{\sigma})$ in
$\widehat{\mathsf{fgFMon}}$, we have that

$\displaystyle\widehat{A}(f,\bm{\sigma})$
$\displaystyle=G(\mu^{[q_{1},\ldots,q_{m}]},\bm{\mathrm{Id}})\circ
G(P_{\sigma},\bm{\mathrm{Id}})\circ
G(\Delta^{[p_{1},\ldots,p_{n}]},\bm{\mathrm{Id}})$
$\displaystyle=G((\mu^{[q_{1},\ldots,q_{m}]},\bm{\mathrm{Id}})\circ(P_{\sigma},\bm{\mathrm{Id}})\circ(\Delta^{[p_{1},\ldots,p_{n}]},\bm{\mathrm{Id}}))$

so to check that $\widehat{A}=G$ it is enough to show that

$(f,\bm{\sigma})=(\mu^{[q_{1},\ldots,q_{m}]},\bm{\mathrm{Id}})\circ(P_{\sigma},\bm{\mathrm{Id}})\circ(\Delta^{[p_{1},\ldots,p_{n}]},\bm{\mathrm{Id}})$
(3.14)

where $p_{i},q_{i}$ and $\sigma$ are as described in (3.6). The equality for
the underlying monoid map holds since $\Delta^{[p_{1},\ldots,p_{n}]}$ produces
as many letters (counting multiplicities) as letters $f(x_{1}\cdots x_{n})$
has, $P_{\sigma}$ shuffles them according to the pattern $f(x_{1}\cdots
x_{n})$ and $\bm{\sigma}$ (via $\Psi$) and $\mu^{[q_{1},\ldots,q_{m}]}$
evaluates the variables producing the pattern. For the equiality at the level
of the permutations, by (3.11) and (3.12) we have that the equality (3.14)
holds if and only if it holds after precomposition with
$(\Delta^{[n]},\bm{\mathrm{Id}})$ and composition with
$(\mu^{[m]},\bm{\mathrm{Id}})$. For the left-hand side this yields

$(\mu^{[m]}\circ f\circ\Delta^{[n]},\sigma),$

where $\sigma=\Psi(f(x_{1}\cdots x_{n}),\bm{\sigma})$ as above. For the right-
hand side, we have

$\displaystyle(\mu^{[m]},\bm{\mathrm{Id}})$
$\displaystyle\circ(\mu^{[q_{1},\ldots,q_{m}]},\bm{\mathrm{Id}})\circ(P_{\sigma},\bm{\mathrm{Id}})\circ(\Delta^{[p_{1},\ldots,p_{n}]},\bm{\mathrm{Id}})\circ(\Delta^{[n]},\bm{\mathrm{Id}})$
$\displaystyle=(\mu^{[q_{1}+\cdots+q_{m}]},\bm{\mathrm{Id}})\circ(P_{\sigma},\bm{\mathrm{Id}})\circ(\Delta^{[p_{1}+\cdots+p_{n}]},\bm{\mathrm{Id}})$
$\displaystyle=(\mu^{[q_{1}+\cdots+q_{m}]},\bm{\mathrm{Id}})\circ(P_{\sigma}\circ\Delta^{[p_{1}+\cdots+p_{n}]},\bm{\mathrm{Id}})$
$\displaystyle=(\mu^{[q_{1}+\cdots+q_{m}]}P_{\sigma}\circ\Delta^{[p_{1}+\cdots+p_{n}]},\Psi((P_{\sigma}\circ\Delta^{[p_{1}+\cdots+p_{n}]})(x),\bm{\mathrm{Id}}))$
$\displaystyle=(\mu^{[q_{1}+\cdots+q_{m}]}P_{\sigma}\circ\Delta^{[p_{1}+\cdots+p_{n}]},\xi^{-1}_{(P_{\sigma}\circ\Delta^{[p_{1}+\cdots+p_{n}]})(x)})$
$\displaystyle=(\mu^{[q_{1}+\cdots+q_{m}]}P_{\sigma}\circ\Delta^{[p_{1}+\cdots+p_{n}]},\xi^{-1}_{x_{\sigma(1)}\cdots
x_{\sigma(p_{1}+\cdots+p_{n})}})$
$\displaystyle=(\mu^{[q_{1}+\cdots+q_{m}]}P_{\sigma}\circ\Delta^{[p_{1}+\cdots+p_{n}]},\sigma)$

as required. This shows that the map (3.2) is indeed a bijection. By 2.1, we
obtain the equivalence of categories
$\widehat{\mathsf{fgFMon}}\simeq\mathsf{B}$. This concludes the proof of 3.10.

###  3.4. A few illustrative examples

To finish off this section, we would like to illustrate the composite law of
$\widehat{\mathsf{fgFMon}}$ with a couple of examples.

######  Example 3.20.

Let $(f,\bm{\sigma}):F(x)\longrightarrow F(a,b)$ and
$(g,\tau):F(a,b)\longrightarrow F(s)$ determined by the following data:

$f(x)=a^{2}bab\quad,\quad\bm{\sigma}=((132),(12))\quad,\quad g(a)=s\quad,\quad
g(b)=s^{2}\quad,\quad\tau=\mathrm{Id}.$

For any bialgebra $A\in\mathcal{C}$, the map $(f,\bm{\sigma})$ induces the map

$x\mapsto x_{(4)}x_{(1)}x_{(2)}\otimes x_{(5)}x_{(3)}$

since

$\Psi(a^{2}bab,(132),(12))=\xi_{a^{2}bab}^{-1}\circ[(132)\otimes(12)]=(34)(132)(45)=(14532).$

Similarly $(g,\tau)$ induces $a\otimes b\mapsto ab_{(1)}b_{(2)}$. Therefore
$\widehat{A}(f,\bm{\sigma})\circ\widehat{A}(g,\tau)$ must be

$x\mapsto
x_{(4)}x_{(1)}x_{(2)}(x_{(5)}x_{(3)})_{(1)}(x_{(5)}x_{(3)})_{(1)}=x_{(5)}x_{(1)}x_{(2)}x_{(6)}x_{(3)}x_{(7)}x_{(4)}.$

Let us check that we obtain the same result computing $\widehat{A}(g\circ
f,\tau\circ\bm{\sigma})$ applying the composite law (3.1) (or rather its
slightly simplified version (3.10)). We compute as

$\displaystyle\tau\circ\bm{\sigma}$
$\displaystyle=\rho_{f,g}\circ(\gamma_{(3,1)}\otimes\gamma_{(2,2)})\circ(\sigma_{1}\otimes\sigma_{2}^{\otimes
2})\circ\langle\mathrm{Id}_{3}\rangle_{3,2,2}$
$\displaystyle=(\langle\xi_{a^{2}bab}\rangle_{1,1,1,2,2})^{-1}\circ[\mathrm{Id}_{3}\otimes(23)]\circ[(132)\otimes(12)\otimes(12)]$
$\displaystyle=(435)(56)(132)(45)(67)$ $\displaystyle=(1532)(467),$

which yields the same result as above.

######  Example 3.21.

Let $(f,\bm{\sigma}):F(x)\longrightarrow F(a,b)$, $f(x)=abab$ with
$\bm{\sigma}=(\mathrm{Id},(12))$ and $(g,\bm{\tau}):F(a,b)\longrightarrow
F(s,t)$, $g(a)=s,g(b)=ts$ with $\bm{\tau}=((12),\mathrm{Id})$. Let us compute
the composite $(g,\bm{\tau})\circ(f,\bm{\sigma})$ in
$\widehat{\mathsf{fgFMon}}$. To start with, write

$\tau=\Psi(g(ab),(12),\mathrm{Id})=\Psi(sts,(12),\mathrm{Id})=\xi_{sts}^{-1}\circ(12)=(23)(12)=(132).$

Provided $k_{1}=\pi_{1}(abab)=2=\pi_{1}(abab)=k_{2}$ and $p_{1}=\pi(s)=1$,
$p_{2}=\pi(ts)=2$, we have

$\displaystyle(\bm{\tau}\circ\bm{\sigma})_{1}\otimes(\bm{\tau}\circ\bm{\sigma})_{2}$
$\displaystyle=\xi_{sts^{2}ts}\circ\rho_{f,\mu
g}\circ(\gamma_{(2,1)}\otimes\gamma_{(2,2)})\circ(\sigma_{1}\otimes\sigma_{2}\otimes\sigma_{2})\circ\langle\tau\rangle_{2,2,2}$
$\displaystyle=(25643)\circ(\langle(23)\rangle_{1,1,2,2})^{-1}\circ(\mathrm{Id}_{2}\otimes(23))$
$\displaystyle\phantom{--}\circ(\mathrm{Id}_{2}\otimes(12)\otimes(12))\circ\langle(132)\rangle_{2,2,2}$
$\displaystyle=(25643)(432)(45)(34)(56)(153)(264)$
$\displaystyle=(25643)(1623)\hskip 142.26378pt(*)$ $\displaystyle=(143)(56)$
$\displaystyle=(143)\otimes(12).$

thence $(\bm{\tau}\circ\bm{\sigma})_{1}=(143)$ and
$(\bm{\tau}\circ\bm{\sigma})_{2}=(12)$.

A bialgebra $A\in\mathcal{C}$ induces the map $\widehat{A}(f,\bm{\sigma})$
mapping $x\mapsto x_{(1)}x_{(3)}\otimes x_{(4)}x_{(2)}$, and similarly
$\widehat{A}(g,\bm{\tau})$ maps $a\otimes b\mapsto b_{(2)}a\otimes b_{(1)}$.
Therefore, their composite
$\widehat{A}(g,\bm{\tau})\circ\widehat{A}(f,\bm{\sigma})$ is the map

$x\mapsto(x_{(4)}x_{(2)})_{(2)}x_{(1)}x_{(3)}\otimes(x_{(4)}x_{(2)})_{(1)}=x_{(6)}x_{(3)}x_{(1)}x_{(4)}\otimes
x_{(5)}x_{(2)}.$

We can already see that this agrees with our previous calculation: the
rightmost permutation in the equality marked as $(*)$ above is precisely the
one that dominates the order of the “elements” of the image of
$\widehat{A}(g,\bm{\tau})\circ\widehat{A}(f,\bm{\sigma})$, according to the
definition of $\Psi$.

##  4\. Applications

We would like to give a few consequences which follow in a rather
straightforward way from theorem 3.10.

######  Corollary 4.1.

For any symmetric monoidal category $\mathcal{C}$, there is an equivalence of
categories

$\mathsf{Alg}_{\mathsf{B}}(\mathcal{C})\simeq\mathsf{Alg}_{\widehat{\mathsf{fgFMon}}}(\mathcal{C}).$

###### Proof.

This is immediate from 3.10. ∎

######  Theorem 4.2.

Every morphism $(f,\bm{\sigma}):F(x_{1},\ldots,x_{n})\longrightarrow
F(y_{1},\ldots,y_{m})$ in $\widehat{\mathsf{fgFMon}}$ factors in a unique way
as

$f=\mu^{[q_{1},\ldots,q_{m}]}\circ
P_{\sigma}\circ\Delta^{[p_{1},\ldots,p_{n}]}$

for some (unique) integers $p_{1},\ldots,p_{n},q_{1},\ldots,q_{m}\geq 0$ such
that $\sum_{i}p_{i}=\sum_{i}q_{i}=:s$, and a (unique) $\sigma\in\Sigma_{s}$.
In particular, these elements are determined as follows:

$p_{i}=\pi(f(x_{i}))\quad,\quad q_{i}=\pi_{i}(f(x_{1}\cdots
x_{n}))\quad,\quad\sigma=\Psi(f(x_{1}\cdots x_{n}),\bm{\sigma}).$

###### Proof.

This is again immediate from 3.5, 3.10 and (3.6). ∎

######  Proposition 4.3.

The following diagram is commutative:

${\mathsf{B}}$${\widehat{\mathsf{fgFMon}}}$${\mathsf{ComB}}$${\mathsf{fgFMon}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$

where the left vertical functor is the natural inclusion and the right
vertical functor forgets the permutations.

###### Proof.

This follows directly from 3.5 and 3.10. ∎

######  Proposition 4.4.

There is a strong monoidal functor

$\widehat{F}:\widehat{\mathsf{fSet}}\longrightarrow\widehat{\mathsf{fgFMon}}$

defined as

$\widehat{F}(f,\sigma):=(Ff,\bm{\sigma})$

where $Ff$ is the monoid map induced by $f$ via the free monoid functor $F$
and $\bm{\sigma}$ is the image of $\sigma$ under the composite

$\Sigma_{N}\overset{\Psi^{-1}}{\longrightarrow}\mathcal{W}(k_{1},\ldots,k_{m})\times\Sigma_{k_{1}}\times\cdots\times\Sigma_{k_{m}}\overset{pr}{\longrightarrow}\Sigma_{k_{1}}\times\cdots\times\Sigma_{k_{m}}$

where $(f,\sigma):[n]\longrightarrow[m]$ and $k_{i}:=\\#f^{-1}(i)$, which
makes the following diagram commutative,

${\mathsf{A}}$${\mathsf{B}}$${\widehat{\mathsf{fSet}}}$${\widehat{\mathsf{fgFMon}}}$${\mathsf{fSet}}$${\mathsf{fgFMon}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{\widehat{F}}$$\scriptstyle{F}$

where the functors $\widehat{\mathsf{fSet}}\longrightarrow\mathsf{fSet}$ and
$\widehat{\mathsf{fgFMon}}\longrightarrow\mathsf{fgFMon}$ are the ones that
forget the associated permutations.

###### Proof.

Let us check in first place that the assignment indeed defines a functor. This
is certainly true for the underlying monoid maps since
$F:\mathsf{fSet}\longrightarrow\mathsf{fgFMon}$ is already a functor. For
$(f,\sigma):[n]\longrightarrow[m]$ and $(g,\tau):[m]\longrightarrow[\ell]$ in
$\widehat{\mathsf{fSet}}$, let us write for convenience
$\delta:=\sigma\circ\langle\tau\rangle_{k_{1},\ldots,k_{m}}$ for the
permutation associated to the composite $(g,\tau)\circ(f,\sigma)$, and let
$\bm{\delta}=(pr\circ\Psi^{-1})(\delta)$. Then

$\displaystyle(\bm{\tau}\circ\bm{\sigma})_{1}\otimes\cdots\otimes(\bm{\tau}\circ\bm{\sigma})_{\ell}$
$\displaystyle=\xi_{F(g\circ f)(x_{1}\cdots
x_{n})}\circ(\langle\xi_{(Ff)(x_{1}\cdots x_{n})}\rangle_{1,\ldots,1})^{-1}$
$\displaystyle\phantom{--}\circ(\sigma_{1}\otimes\cdots\otimes\sigma_{m})\circ\langle\tau\rangle_{k_{1},\ldots,k_{m}}$
$\displaystyle=\xi_{x_{gf(1)}\cdots x_{gf(n)}}\circ\xi_{x_{f(1)}\cdots
x_{f(n)}}^{-1}\circ(\sigma_{1}\otimes\cdots\otimes\sigma_{m})$
$\displaystyle\phantom{--}\circ\langle\tau\rangle_{k_{1},\ldots,k_{m}}$
$\displaystyle=\xi_{x_{gf(1)}\cdots
x_{gf(n)}}\circ\sigma\circ\langle\tau\rangle_{k_{1},\ldots,k_{m}}$
$\displaystyle=\xi_{x_{gf(1)}\cdots x_{gf(n)}}\circ\delta$
$\displaystyle=\delta_{1}\otimes\cdots\otimes\delta_{\ell},$

where in the third and fifth equality we have used that for a map
$(f,\sigma):[n]\longrightarrow[m]$, the word in $\Psi^{-1}(\sigma)$ can be
described as $x_{f(1)}\cdots x_{f(n)}$, as can be easily seen. That
$\widehat{F}(\mathrm{Id},\mathrm{Id})=(\mathrm{Id},\bm{\mathrm{Id}})$ is
straightforward. The fact that $\widehat{F}$ is strong monoidal follows
directly from $F$ being monoidal and the commutative diagram of 3.17, which
implies that

$(pr\circ\Psi^{-1})(\sigma\otimes\tau)=((pr\circ\Psi^{-1})\sigma,(pr\circ\Psi^{-1})\tau),$

which is precisely the required condition for the associated permutations.
Finally, the upper square commutes since the image of
$([k]\longrightarrow[1],\mathrm{Id})$ under $\widehat{F}$ is precisely
$(\mu^{[k]},\mathrm{Id})$ The commutativity of the lower diagram is obvious. ∎

Putting all the pieces together, we finally have

######  Theorem 4.5.

The following cube is commutative:

${\widehat{\mathsf{fSet}}}$${\widehat{\mathsf{fgFMon}}}$${\mathsf{A}}$${\mathsf{B}}$${\mathsf{fSet}}$${\mathsf{fgFMon}}$${\mathsf{ComA}}$${\mathsf{ComB}}$$\scriptstyle{\simeq}$$\scriptstyle{\widehat{F}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{F\phantom{holaaa}}$$\scriptstyle{\simeq}$
(4.1)

###### Proof.

This follows at once from 2.10, 3.10, 4.3 and 4.4. ∎

If $\mathsf{C}$ (resp. $\mathsf{CocomC}$) is the PROP for (cocommutative)
coalgebras, by reversing arrows we directly obtain

######  Corollary 4.6.

There are monoidal equivalences

$\mathsf{C}\overset{\simeq}{\longrightarrow}\widehat{\mathsf{fSet}}^{op}\qquad,\qquad\mathsf{B}\overset{\simeq}{\longrightarrow}\widehat{\mathsf{fgFMon}}^{op}$

making the following cube commutative,

${\widehat{\mathsf{fSet}}^{op}}$${\widehat{\mathsf{fgFMon}}^{op}}$${\mathsf{C}}$${\mathsf{B}}$${\mathsf{fSet}^{op}}$${\mathsf{fgFMon}^{op}}$${\mathsf{CocomC}}$${\mathsf{CocomB}}$$\scriptstyle{\simeq}$$\scriptstyle{\widehat{F}^{op}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{F^{op}\phantom{holaaa}}$$\scriptstyle{\simeq}$
(4.2)

###  4.1. Related work

Our work could be seen as the bialgebra case of what is called in the
literature as the acyclic Hopf word problem [Tho12]. It gives a complete
answer to the question of whether two different combinations of the bialgebra
structure maps represent the same morphism in $\mathsf{B}$. More precisely, it
asks whether given two arrows $f_{1},f_{2}:n\longrightarrow m$ in the PROP
$\mathcal{B}$ as defined just before 3.6, it is true that
$\pi(f_{1})=\pi(f_{2})$, where $\pi:\mathcal{B}\longrightarrow\mathsf{B}$ is
the canonical projection. Indeed if $(f_{1}^{\prime},\bm{\sigma})$,
$(f_{2}^{\prime},\bm{\tau})$ are the images of $\pi(f_{1}),\pi(f_{2})$ under
the equivalence
$\mathsf{B}\overset{\simeq}{\longrightarrow}\widehat{\mathsf{fgFMon}}$, then
4.2 ensures that $\pi(f_{1})=\pi(f_{2})$ if and only if the following
equalities hold:

$\pi(f_{1}^{\prime}(x_{i}))=\pi(f_{2}^{\prime}(x_{i}))\quad,\quad\pi_{j}(w_{1})=\pi_{j}(w_{2})\quad,\quad\Psi(w_{1},\bm{\sigma})=\Psi(w_{2},\bm{\tau})$

for all $1\leq i\leq n$, $1\leq j\leq m$, where
$w_{1}:=f_{1}^{\prime}(x_{1}\cdots x_{n})$ and
$w_{2}:=f_{2}^{\prime}(x_{1}\cdots x_{n})$.

In [Tho12] (and in [Kup91] in a different context) this problem is used to
produce an invariant of decorated 3-manifolds.

###  4.2. Future work

The commutative cube from 1.2 is only a part of the larger solid diagram shown
below.

${\widehat{\mathsf{fSet}}}$${\widehat{\mathsf{fgFMon}}}$${\widehat{\mathsf{fgFGp}}}$${\mathsf{A}}$${\mathsf{B}}$${\mathsf{H}}$${\mathsf{fSet}}$${\mathsf{fgFMon}}$${\mathsf{fgFGp}}$${\mathsf{ComA}}$${\mathsf{ComB}}$${\mathsf{ComH}}$${\mathsf{fgFCMon}}$${\mathsf{fgFAb}}$${\mathsf{ComCocomB}}$${\mathsf{ComCocomH}}$$\scriptstyle{\simeq}$$\scriptstyle{\widehat{F}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{F\phantom{holaaa}}$$\scriptstyle{\simeq}$$\scriptstyle{G\phantom{holaaa}}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{K\phantom{holaaa}}$$\scriptstyle{\simeq}$
(4.3)

Let us say a few words about the this diagram. Here $\mathsf{H}$ (resp.
$\mathsf{ComH}$) stands for the PROP for (commutative) Hopf algebras. All
functors in the diagram are bijective-on-objects. Horizontal functors are
faithful, vertical functors are full, and perpendicular (with respect to the
page) functors are equivalences of categories. The functor $K$ is the
restriction of the Grothendieck construction
$K:\mathsf{CMon}\longrightarrow\mathsf{Ab}$, that is, the left-adjoint to the
forgetful $\mathsf{Ab}\longrightarrow\mathsf{CMon}$, that topologists should
be familiar with. The functor $G$ is its noncommutative counterpart, the
restriction of the left-adjoint to the forgetful
$\mathsf{Gp}\longrightarrow\mathsf{Mon}$, which is known as the group
completion or universal enveloping group of a monoid,
$G:\mathsf{Mon}\longrightarrow\mathsf{Gp}$. The vertical functors
$\mathsf{Mon}\longrightarrow\mathsf{CMon}$ and
$\mathsf{Gp}\longrightarrow\mathsf{Ab}$ are the abelianisation functors.

In this situation, we conjecture the existence of a category
$\widehat{\mathsf{fgFGp}}$ built out of $\mathsf{fgFGp}$ in an analogous way
to our construction of $\widehat{\mathsf{fgFMon}}$, together with a monoidal
equivalence $\mathsf{H}\simeq\widehat{\mathsf{fgFGp}}$, a functor
$\widehat{G}:\widehat{\mathsf{fgFMon}}\longrightarrow\widehat{\mathsf{fgFGp}}$
lifting $G$ and a full (forgetful) functor
$\widehat{\mathsf{fgFGp}}\longrightarrow\mathsf{fgFGp}$. This will be the
subject of a forthcoming paper.

## References

  * [BNDvdV21] Dror Bar-Natan, Zsuzsanna Dancso, and Roland van der Veen.  Over then under tangles, 2021.
  * [BSZ17] Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi.  Interacting Hopf algebras.  J. Pure Appl. Algebra, 221(1):144–184, 2017.
  * [BW93] Thomas Becker and Volker Weispfenning.  Gröbner bases, volume 141 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1993.  A computational approach to commutative algebra, In cooperation with Heinz Kredel.
  * [Hab06] Kazuo Habiro.  Bottom tangles and universal invariants.  Algebr. Geom. Topol., 6:1113–1214, 2006.
  * [Hab16] Kazuo Habiro.  On the category of finitely generated free groups, 2016.
  * [Kas95] Christian Kassel.  Quantum groups, volume 155 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1995.
  * [Kup91] Greg Kuperberg.  Involutory Hopf algebras and $3$-manifold invariants.  Internat. J. Math., 2(1):41–66, 1991.
  * [LV12] Jean-Louis Loday and Bruno Vallette.  Algebraic operads, volume 346 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer, Heidelberg, 2012.
  * [ML98] Saunders Mac Lane.  Categories for the working mathematician, volume 5 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 1998.
  * [MP12] J. P. May and K. Ponto.  More concise algebraic topology.  Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 2012.  Localization, completion, and model categories.
  * [Pir02] Teimuraz Pirashvili.  On the PROP corresponding to bialgebras.  Cah. Topol. Géom. Différ. Catég., 43(3):221–239, 2002\.
  * [Tho12] Rohit Parathundyil Thomas.  Decorated 3-manifolds and invariants of Hopf words.  ProQuest LLC, Ann Arbor, MI, 2012.  Thesis (Ph.D.)–University of California, Davis.
  * [TV17] Vladimir Turaev and Alexis Virelizier.  Monoidal categories and topological field theory, volume 322 of Progress in Mathematics.  Birkhäuser/Springer, Cham, 2017.