# Word algebra

Some notes on the algebraic structures underlying words, combinatorial lines, combinatorial subspaces, IP-systems, etc.

## Semigroupoid

A semigroupoid (or small category) G is like a semigroup, except that the operations are only partially defined (or like a groupoid, except that we do not assume invertibility). More formally:

Definition 1 A semigroupoid $G = (V, (G(w \leftarrow v))_{w,v \in V}, \cdot)$ consists of the following objects:
1. A vertex set V;
2. A (possibly empty) collection $G( w \leftarrow v )$ of semigroupoid elements from v to w for each $v, w \in V$;
3. A multiplication operation $g, h \mapsto gh$ from $G( w \leftarrow v ) \times G( v \leftarrow u )$ to $G(w \leftarrow u)$ for all $u,v,w \in V$ which is associative in the sense that $(fg)h = f(gh)$ whenever $f \in G(w \leftarrow v), g \in G(w \leftarrow u), h \in G(u \leftarrow t)$ and $u, v, w \in V$.

Example 1 Every semigroup $G = (G,\cdot)$ can be viewed as a semigroupoid on a single vertex $V = pt$.

Example 2 If V is a collection of probability spaces, then we can form a semigroupoid $Mes(V)$ by declaring $Mes(V)(w \leftarrow v)$ to be the collection of measure-preserving transformations from v to w, with the multiplication law being compositions. If we restrict attention to invertible measure-preserving transformations, then the semigroupoid becomes a groupoid $InvMes(A)$.

Example 3 If V is a collection of Hilbert spaces, then one can form a semigroupoid $Unitary(V)$ by declaring $Unitary(V)(w \leftarrow v)$ to be the collection of all unitary maps from v to w.

Example 4 If A is an alphabet, then we can form a semigroupoid $Words(A)$ by declaring the vertex set to be the natural numbers ${\Bbb N} = \{0,1,2,\ldots\}$, and $Words(A)(i \leftarrow j)$ to be the space $A^{j-i}$ of words of length j-i if $j \gt i$, and to be the empty set otherwise, and with multiplication given by concatenation. It may help to view $G(i \leftarrow j)$ as words of length j, in which the first i positions are "blank", e.g. if A = {1,2,3}, then a typical element of $G(2 \leftarrow 5)$ might be ..231, with multiplication laws such as $.3 \cdot ..231 = .3231$. Note that this semigroup is generated by the single character words $G(i \leftarrow i+1) = \{ .^i a: a \in A \}$.

Example 5 If A is an alphabet, and n is a natural number, we can define the semigroupoid $Words_n(A)$ to be the subsemigroupoid of A formed by restricting the vertex set V to just $\{0,1,\ldots,n\}$.

Example 6 Form the semigroupoid $IP$ by declaring the vertex set to be the natural numbers ${\Bbb N}$, and $IP(i \leftarrow j)$ to be the collection of all subsets of $\{i+1,\ldots,j\}$ if $j \gt i$, and the empty set otherwise, with multiplication given by union. We also form $IP_n$ by restricting the vertex set to $\{0,1,\ldots,n\}$. Note that as subsets of a set S can be identified with elements of $\{0,1\}^S$, that IP is isomorphic to $Words(\{0,1\})$, and similarly $IP_n$ is isomorphic to $Words_n(\{0,1\})$.

Definition 2 A homomorphism $\phi: G \to H$ between two semigroupoids $G = (V, (G(w \leftarrow v))_{w,v \in V}, \cdot)$ and $H = (W, (H(w \leftarrow v))_{w,v \in W}, \cdot)$ consists of the following objects:
1. A map $\phi: V \to W$ from the vertex set of G to the vertex set of H;
2. Maps $\phi: G( v \leftarrow v' ) \to H( \phi(v) \leftarrow \phi(v') )$ for each $v, v' \in V$ such that $\phi(gh) = \phi(g) \phi(h)$ whenever $g \in G(v \leftarrow v'), h \in G(v' \leftarrow v'')$ and $v, v', v'' \in V$.

Of course, the composition of two homomorphisms is again a homomorphism.

Example 7 If A is an alphabet, * is a wildcard not in A, and a is an element of A, then there is a substitution map $\pi_a: Words(A \cup \{*\}) \to Words(A)$ that preserves the vertex set ${\Bbb N}$ and replaces any occurrence of the wildcard * with a. For instance $\pi_2(..2*3**1) = ..223221$. This is clearly a homomorphism. One can of course restrict $\pi_a$ to be a homomorphism from $Words_n(A \cup \{*\})$ to $Words_n(A)$ for any n.

Example 8 Let G be a group. Define an IP-system to be a tuple of group elements $u_\alpha \in G$, one for each finite set $\alpha$ of natural numbers, such that $u_\alpha u_\beta = u_{\alpha \beta}$ whenever the elements of $\alpha$ all lie to the left of the elements of $\beta$ (in particular, $u_\emptyset$ is the identity, and $u_{\{a_1,\ldots,a_n\}} = u_{a_1} \ldots u_{a_n}$ whenever $a_1 \lt \ldots \lt a_n$). Then one can view this IP system as a homomorphism $u: IP \to G$, with the property that any copy of the empty set gets mapped to the identity element. Conversely, every homomorphism $u: IP \to G$ that maps every copy of the empty set to the identity element comes from an IP system in this fashion.

Definition 4 Let G be an semigroupoid. A measure-preserving group action of G is a homomorphism $T: G \to Mes(X)$ of G to the group of invertible measure-preserving transformations on some probability space X; more generally, a measure-preserving groupoid action of G is a homomorphism $U: G \to Mes({\mathcal X})$ of G to the groupoid of measure-preserving transformations for some collection ${\mathcal X}$ of probability spaces.
A unitary group representation of G is a homomorphism $U: G \to Unitary(H)$ from G to the unitary group of some Hilbert space H. More generally, a unitary groupoid representation of G is a homomorphism $U: G \to Unitary({\mathcal H})$ from G to the unitary groupoid $Unitary({\mathcal H})$ of some collection ${\mathcal H}$ of Hilbert spaces.

Example 9 Every measure-preserving groupoid action $U: G \to Mes({\mathcal X})$ induces a corresponding unitary groupoid representation $U: G \to Unitary({\mathcal H})$, where ${\mathcal H} := \{ L^2(X): X \in {\mathcal X} \}$ are the Hilbert spaces associated to ${\mathcal X}$, and each measure-preserving transformation $U(g): X \to Y$ induces a unitary map $U(g): L^2(X) \to L^2(Y)$ by the formula $U(g)f := f \circ U(g)^{-1}$. [One can think of this operation as that of composing $U: G \to Mes({\mathcal X})$ with the canonical homomorphism from $Mes({\mathcal X})$ to $Unitary({\mathcal H})$.]

Example 10 Let $U: G \to Unitary({\mathcal H})$ be a unitary groupoid representation, and let V be the vertex set of G. If H_0 is another Hilbert space, and one has unitary maps $R_v: H_0 \to Unitary(v)$ for every $v \in V$, then we can conjugate U by R to obtain a unitary group representation $U^R: G \to Unitary(H_0)$, defined by the formula

$U^R(g) := R_{v}^{-1} U(g) R_{w}$

for all $g \in G(w \leftarrow v)$ (thus U(g) is a unitary map from $U(v)$ to $U(w)$). One easily verifies that this is still a homomorphism. [R here is essentially playing the role of a natural transformation in category theory.]

Example 11 One application of the renormalisation construction in Example 10 arises when considering a unitary groupoid representation $U: IP \to Unitary({\mathcal H})$ of IP. We set $H_0 := U(0)$ and define $R_n: H_0 \to U(n)$ for every natural number n by the formula $R_n := U( \emptyset_{n \leftarrow 0} )$, where $\emptyset_{n \leftarrow 0} \in IP(n \leftarrow 0)$ is the copy of the empty set in $IP(n \leftarrow 0)$, then the unitary group representation $U^R: IP \to Unitary(H_0)$ maps every copy of the empty set to the identity, and so $U^R$ is essentially an IP system in $Unitary(H_0)$.

Definition 3 Let A be an alphabet. An A-semigroupoid $G = (G, G^*, (\pi_a)_{a \in A})$ is a semigroupoid $G^*$, together with a subsemigroupoid $G^*$ (with the same vertex set V as $G^*$), together with morphisms $\pi_a: G^* \to G$ for each $a \in A$, which are the identity on the vertex set V, and which are the identity on G. An A-homomorphism $\phi: G \to H$ between two A-semigroupoids $G = (G, G^*, (\pi^G_a)_{a \in A}), H = (H, H^*, (\pi^H_a)_{a \in A})$ is a homomorphism $\phi: G^* \to H^*$ which restricts to a homomorphism $\phi: G \to H$, and also maps $G^* \backslash G$ to $H^* \backslash H$, and is such that $\pi^H_a \circ \phi = \phi \circ \pi^G_a$ for all $a \in A$.

Example 12 Example 7 shows that $Words(A)$ and $Words_n(A)$ are A-semigroupoids, with $Words(A)^* = Words(A \cup \{*\})$ and $Words_n(A)^* = Words_n(A \cup \{*\})$.

Example 13 Suppose we have an A-homomorphism $\phi: Words_m(A) \to Words_n(A)$, which maps the vertices $0,1,\ldots,m$ to $j_0=0,j_1,\ldots,j_m = n$. Then we must have $j_0 \lt j_1 \lt \ldots \lt j_m$ (and hence $m \leq n$), and $\phi$ maps each wildcard generator $.^i *$ to some word $.^{j_i} w_i$, with $w_i\lt/a\gt having length \ltmath\gtj_{i+1} - j_i$ and containing at least one wildcard, and one has

$\phi( .^i a_{i+1} \ldots a_{i'} ) = .^{j_i} \pi_{a_{i+1}}(w_{i+1}) \ldots \pi_{a_{i'}}(w_i).$

Thus the image $\phi(Words_m(A))$ is essentially an m-dimensional combinatorial subspace of $A^n$, with the property that the positions of the $(i+1)^{th}$ wildcard all lie to the right of the positions of the $i^{th}$ wildcard. Conversely, any combinatorial subspace with this wildcard ordering property can be represented as an A-homomorphism.