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 [math]G = (V, (G(w \leftarrow v))_{w,v \in V}, \cdot)[/math] consists of the following objects:

1. A vertex set V;
2. A (possibly empty) collection [math]G( w \leftarrow v )[/math] of semigroupoid elements from v to w for each [math]v, w \in V[/math];
3. A multiplication operation [math]g, h \mapsto gh[/math] from [math]G( w \leftarrow v ) \times G( v \leftarrow u )[/math] to [math]G(w \leftarrow u)[/math] for all [math]u,v,w \in V[/math] which is associative in the sense that [math](fg)h = f(gh)[/math] whenever [math]f \in G(w \leftarrow v), g \in G(w \leftarrow u), h \in G(u \leftarrow t)[/math] and [math]u, v, w \in V[/math].

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

Example 2 If V is a collection of probability spaces, then we can form a semigroupoid [math]Mes(V)[/math] by declaring [math]Mes(V)(w \leftarrow v)[/math] 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 [math]InvMes(A)[/math].

Example 3 If V is a collection of Hilbert spaces, then one can form a semigroupoid [math]Unitary(V)[/math] by declaring [math]Unitary(V)(w \leftarrow v)[/math] 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 [math]Words(A)[/math] by declaring the vertex set to be the natural numbers [math]{\Bbb N} = \{0,1,2,\ldots\}[/math], and [math]Words(A)(i \leftarrow j)[/math] to be the space [math]A^{j-i}[/math] of words of length j-i if [math]j \gt i[/math], and to be the empty set otherwise, and with multiplication given by concatenation. It may help to view [math]G(i \leftarrow j)[/math] 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 [math]G(2 \leftarrow 5)[/math] might be ..231, with multiplication laws such as [math].3 \cdot ..231 = .3231[/math]. Note that this semigroup is generated by the single character words [math]G(i \leftarrow i+1) = \{ .^i a: a \in A \}[/math].

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

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

Definition 2 A homomorphism [math]\phi: G \to H[/math] between two semigroupoids [math]G = (V, (G(w \leftarrow v))_{w,v \in V}, \cdot)[/math] and [math]H = (W, (H(w \leftarrow v))_{w,v \in W}, \cdot)[/math] consists of the following objects:

1. A map [math]\phi: V \to W[/math] from the vertex set of G to the vertex set of H;
2. Maps [math]\phi: G( v \leftarrow v' ) \to H( \phi(v) \leftarrow \phi(v') )[/math] for each [math]v, v' \in V[/math] such that [math]\phi(gh) = \phi(g) \phi(h)[/math] whenever [math]g \in G(v \leftarrow v'), h \in G(v' \leftarrow v'')[/math] and [math]v, v', v'' \in V[/math].

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 [math]\pi_a: Words(A \cup \{*\}) \to Words(A)[/math] that preserves the vertex set [math]{\Bbb N}[/math] and replaces any occurrence of the wildcard * with a. For instance [math]\pi_2(..2*3**1) = ..223221[/math]. This is clearly a homomorphism. One can of course restrict [math]\pi_a[/math] to be a homomorphism from [math]Words_n(A \cup \{*\})[/math] to [math]Words_n(A)[/math] for any n.

Example 8 Let G be a group. Define an IP-system to be a tuple of group elements [math]u_\alpha \in G[/math], one for each finite set [math]\alpha[/math] of natural numbers, such that [math]u_\alpha u_\beta = u_{\alpha \beta}[/math] whenever the elements of [math]\alpha[/math] all lie to the left of the elements of [math]\beta[/math] (in particular, [math]u_\emptyset[/math] is the identity, and [math]u_{\{a_1,\ldots,a_n\}} = u_{a_1} \ldots u_{a_n}[/math] whenever [math]a_1 \lt \ldots \lt a_n[/math]). Then one can view this IP system as a homomorphism [math]u: IP \to G[/math], with the property that any copy of the empty set gets mapped to the identity element. Conversely, every homomorphism [math]u: IP \to G[/math] 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 [math]T: G \to Mes(X)[/math] 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 [math]U: G \to Mes({\mathcal X})[/math] of G to the groupoid of measure-preserving transformations for some collection [math]{\mathcal X}[/math] of probability spaces.

A unitary group representation of G is a homomorphism [math]U: G \to Unitary(H)[/math] from G to the unitary group of some Hilbert space H. More generally, a unitary groupoid representation of G is a homomorphism [math]U: G \to Unitary({\mathcal H})[/math] from G to the unitary groupoid [math]Unitary({\mathcal H})[/math] of some collection [math]{\mathcal H}[/math] of Hilbert spaces.

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

Example 10 Let [math]U: G \to Unitary({\mathcal H})[/math] 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 [math]R_v: H_0 \to Unitary(v)[/math] for every [math]v \in V[/math], then we can conjugate U by R to obtain a unitary group representation [math]U^R: G \to Unitary(H_0)[/math], defined by the formula

[math]U^R(g) := R_{v}^{-1} U(g) R_{w}[/math]

for all [math]g \in G(w \leftarrow v)[/math] (thus U(g) is a unitary map from [math]U(v)[/math] to [math]U(w)[/math]). 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 [math]U: IP \to Unitary({\mathcal H})[/math] of IP. We set [math]H_0 := U(0)[/math] and define [math]R_n: H_0 \to U(n)[/math] for every natural number n by the formula [math]R_n := U( \emptyset_{n \leftarrow 0} )[/math], where [math]\emptyset_{n \leftarrow 0} \in IP(n \leftarrow 0)[/math] is the copy of the empty set in [math]IP(n \leftarrow 0)[/math], then the unitary group representation [math]U^R: IP \to Unitary(H_0)[/math] maps every copy of the empty set to the identity, and so [math]U^R[/math] is essentially an IP system in [math]Unitary(H_0)[/math].

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

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

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

[math]\phi( .^i a_{i+1} \ldots a_{i'} ) = .^{j_i} \pi_{a_{i+1}}(w_{i+1}) \ldots \pi_{a_{i'}}(w_i).[/math]

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