Word algebra

From Polymath Wiki
Revision as of 17:59, 20 February 2009 by Teorth (talk | contribs) (New page: Some notes on the algebraic structures underlying words, combinatorial lines, combinatorial subspaces, IP-systems, etc. == Semigroupoid == A '''semigroupoid''' (or '''small category''') ...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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.