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]\displaystyle{ 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]\displaystyle{ G( w \leftarrow v ) }[/math] of semigroupoid elements from v to w for each [math]\displaystyle{ v, w \in V }[/math];
3. A multiplication operation [math]\displaystyle{ g, h \mapsto gh }[/math] from [math]\displaystyle{ G( w \leftarrow v ) \times G( v \leftarrow u ) }[/math] to [math]\displaystyle{ G(w \leftarrow u) }[/math] for all [math]\displaystyle{ u,v,w \in V }[/math] which is associative in the sense that [math]\displaystyle{ (fg)h = f(gh) }[/math] whenever [math]\displaystyle{ f \in G(w \leftarrow v), g \in G(w \leftarrow u), h \in G(u \leftarrow t) }[/math] and [math]\displaystyle{ u, v, w \in V }[/math].

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

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

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

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

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

1. A map [math]\displaystyle{ \phi: V \to W }[/math] from the vertex set of G to the vertex set of H;
2. Maps [math]\displaystyle{ \phi: G( v \leftarrow v' ) \to H( \phi(v) \leftarrow \phi(v') ) }[/math] for each [math]\displaystyle{ v, v' \in V }[/math] such that [math]\displaystyle{ \phi(gh) = \phi(g) \phi(h) }[/math] whenever [math]\displaystyle{ g \in G(v \leftarrow v'), h \in G(v' \leftarrow v'') }[/math] and [math]\displaystyle{ 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]\displaystyle{ \pi_a: Words(A \cup \{*\}) \to Words(A) }[/math] that preserves the vertex set [math]\displaystyle{ {\Bbb N} }[/math] and replaces any occurrence of the wildcard * with a. For instance [math]\displaystyle{ \pi_2(..2*3**1) = ..223221 }[/math]. This is clearly a homomorphism. One can of course restrict [math]\displaystyle{ \pi_a }[/math] to be a homomorphism from [math]\displaystyle{ Words_n(A \cup \{*\}) }[/math] to [math]\displaystyle{ 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]\displaystyle{ u_\alpha \in G }[/math], one for each finite set [math]\displaystyle{ \alpha }[/math] of natural numbers, such that [math]\displaystyle{ u_\alpha u_\beta = u_{\alpha \beta} }[/math] whenever the elements of [math]\displaystyle{ \alpha }[/math] all lie to the left of the elements of [math]\displaystyle{ \beta }[/math] (in particular, [math]\displaystyle{ u_\emptyset }[/math] is the identity, and [math]\displaystyle{ u_{\{a_1,\ldots,a_n\}} = u_{a_1} \ldots u_{a_n} }[/math] whenever [math]\displaystyle{ a_1 \lt \ldots \lt a_n }[/math]). Then one can view this IP system as a homomorphism [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ U: G \to Mes({\mathcal X}) }[/math] of G to the groupoid of measure-preserving transformations for some collection [math]\displaystyle{ {\mathcal X} }[/math] of probability spaces.

A unitary group representation of G is a homomorphism [math]\displaystyle{ 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]\displaystyle{ U: G \to Unitary({\mathcal H}) }[/math] from G to the unitary groupoid [math]\displaystyle{ Unitary({\mathcal H}) }[/math] of some collection [math]\displaystyle{ {\mathcal H} }[/math] of Hilbert spaces.

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

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

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

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

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

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

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

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