Word rings #
Definition #
The word ring, written \( \wordRingSymbol \), is the so-called group ring of the word group \( \wordGroupSymbol \): the ring of formal \( \ring{\mathbb{Z}} \)-linear combinations of elements of the group \( \wordGroupSymbol \). We will explain this idea with examples.
Examples #
Example: one cardinal #
For the word group \( \bindCards{\wordGroupSymbol }{\reFo{\card{r}}} \), we can only form words from the single cardinal \( \reFo{\card{r}} \). All of these words \( \elemOf{\groupElement{w}}{\bindCards{\wordGroupSymbol }{\reFo{\card{r}}}} \) can be described by simply counting how many times the cardinal \( \reFo{\card{r}} \) is repeated in \( \groupElement{w} \) (negative counts indicate that we are repeating \( \reFo{\inverted{\card{r}}} \) instead):
\[ \groupElement{ \omega } = \overRepeated{\concat{\reFo{\card{r}} \reFo{\card{r}} \elSy \reFo{\card{r}}}}{\sym{p}} = \groupPower{\reFo{\card{r}}}{\sym{p}} \]Therefore we can write the set of elements compactly as :
\[ \bindCards{\wordGroupSymbol }{\reFo{\card{r}}} = \setConstructor{\groupPower{\reFo{\card{r}}}{\sym{p}}}{\elemOf{\sym{p}}{\group{\mathbb{Z}}}} \]Word concatenation simply adds these exponents:
\[ \groupPower{\reFo{\card{r}}}{\sym{p}}\gdot \groupPower{\reFo{\card{r}}}{\sym{q}} = \overRepeated{\concat{\reFo{\card{r}} \elSy \reFo{\card{r}}}}{\sym{p}}\gdot \overRepeated{\concat{\reFo{\card{r}} \elSy \reFo{\card{r}}}}{\sym{q}} = \overRepeated{\concat{\concat{\reFo{\card{r}} \elSy \reFo{\card{r}}}\,\concat{\reFo{\card{r}} \elSy \reFo{\card{r}}}}}{\sym{p} + \sym{q}} = \groupPower{\reFo{\card{r}}}{\sym{p} + \sym{q}} \]Therefore \( \bindCards{\wordGroupSymbol }{\reFo{\card{r}}} \) is isomorphic to the group \( \group{\mathbb{Z}} \), the integers under addition.
The word ring \( \bindCards{\wordRingSymbol }{\reFo{\card{r}}} \) consists of integer-weighted sums of elements of \( \bindCards{\wordRingSymbol }{\reFo{\card{r}}} \). It is the simplest answer to the question: "how do we define addition and subtraction of group elements?". Once we allow these new operations, we can add a given group element \( \groupElement{w} \) to itself any number of times. We can keep track of the number of times we have added (or subtracted) a group element from the zero element with an integer coefficient:
\[ \overRepeated{\groupElement{w} + \groupElement{w} + \elSy + \groupElement{w}}{\sym{n}} = \linearCombinationCoefficient{n} \, \groupElement{w} \]Similarly, we can add two differing group elements to each other; since they are different, these two terms of a sum remain separate:
\[ \overRepeated{\groupElement{w} + \elSy + \groupElement{w}}{\sym{m}} + \overRepeated{\groupElement{v} + \elSy + \groupElement{v}}{\sym{n}} = \linearCombinationCoefficient{m} \, \groupElement{w} + \linearCombinationCoefficient{n} \, \groupElement{v} \]Therefore, a general element of \( \bindCards{\wordRingSymbol }{\reFo{\card{r}}} \) can be written as an integral linear combination of words. We'll write the coefficients with the same symbol as the ring element to make keeping track of these easier, but we'll gray the coefficient symbol to distinguish it:
\[ \wordRingElement{w} = \indexSum{\linearCombinationCoefficient{w_p} \, \groupPower{\reFo{\card{r}}}{\sym{p}}}{\elemOf{\sym{p}}{\group{\mathbb{Z}}}}{} \]Sum #
To add two elements \( \wordRingElement{w},\wordRingElement{v} \) of the word ring, we take formally add the two sums. Since addition is commutative, we can re-arrange the terms to group like powers of \( \reFo{\card{r}} \), and we obtain a sum whose coefficients are the sums of the coefficients of \( \wordRingElement{w}\textAnd \wordRingElement{v} \):
\[ \wordRingElement{w} + \wordRingElement{v} = \indexSum{\paren{\linearCombinationCoefficient{w_{\orFo{\sym{p}}}} + \linearCombinationCoefficient{v_{\orFo{\sym{p}}}}} \, \groupPower{\reFo{\card{r}}}{\orFo{\sym{p}}}}{\elemOf{\orFo{\sym{p}}}{\group{\mathbb{Z}}}}{} \]Product #
To multiply two elements \( \wordRingElement{w},\wordRingElement{v} \) of the word ring, we multiply them as sums in the normal way:
\[ \begin{aligned} \wordRingElement{w}\gDot \wordRingElement{v}&= \paren{\indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{p}}}} \, \groupPower{\reFo{\card{r}}}{\orFo{\sym{p}}}}{\orFo{\sym{p}}}{}}\gDot \paren{\indexSum{\linearCombinationCoefficient{v_{\piFo{\sym{q}}}} \, \groupPower{\reFo{\card{r}}}{\piFo{\sym{q}}}}{\piFo{\sym{q}}}{}}\\ &= \indexSum{\paren{\linearCombinationCoefficient{w_{\orFo{\sym{p}}}} \, \groupPower{\reFo{\card{r}}}{\orFo{\sym{p}}}}\gDot \paren{\linearCombinationCoefficient{v_{\piFo{\sym{q}}}} \, \groupPower{\reFo{\card{r}}}{\piFo{\sym{q}}}}}{\substack{\orFo{\sym{p}},\;\piFo{\sym{q}}}}{}\\ &= \indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{p}}}} \, \linearCombinationCoefficient{v_{\piFo{\sym{q}}}} \, \paren{\groupPower{\reFo{\card{r}}}{\orFo{\sym{p}}}\gdot \groupPower{\reFo{\card{r}}}{\piFo{\sym{q}}}}}{\substack{\orFo{\sym{p}},\;\piFo{\sym{q}}}}{}\\ &= \indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{p}}}} \, \linearCombinationCoefficient{v_{\piFo{\sym{q}}}} \, \groupPower{\reFo{\card{r}}}{\orFo{\sym{p}} + \piFo{\sym{q}}}}{\substack{\orFo{\sym{p}},\;\piFo{\sym{q}}}}{}\end{aligned} \]If we "gather like powers of \( \reFo{\card{r}} \)" we obtain:
\[ \begin{aligned} \wordRingElement{w}\gDot \wordRingElement{v}&= \indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{p}}}} \, \linearCombinationCoefficient{v_{\piFo{\sym{q}}}} \, \groupPower{\reFo{\card{r}}}{\orFo{\sym{p}} + \piFo{\sym{q}}}}{\substack{\orFo{\sym{p}},\;\piFo{\sym{q}}}}{}\\ &= \indexSum{\paren{\indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{p}}}} \, \linearCombinationCoefficient{v_{\piFo{\sym{q}}}}}{\substack{\orFo{\sym{p}},\;\piFo{\sym{q}}}}{\orFo{\sym{p}} + \piFo{\sym{q}} = \teFo{\sym{n}}}} \, \groupPower{\reFo{\card{r}}}{\teFo{\sym{n}}}}{\teFo{\sym{n}}}{}\\ &= \indexSum{\paren{\indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{p}}}} \, \linearCombinationCoefficient{v_{\teFo{\sym{n}} - \orFo{\sym{p}}}}}{\orFo{\sym{p}}}{}} \, \groupPower{\reFo{\card{r}}}{\teFo{\sym{n}}}}{\teFo{\sym{n}}}{}\end{aligned} \]Sums (or integrals) of this form are generally known as convolutions.
An alternate way of presenting this result is to write \( \groupElement{w}\gDot \groupElement{v} \) "coefficientwise", that is, to define the coefficient of \( \groupPower{\reFo{\card{r}}}{\teFo{\sym{n}}} \) in the product \( \groupElement{w}\gDot \groupElement{v} \) in terms of \( \groupElement{w}\textAnd \groupElement{v} \):
\[ \coefficient(\wordRingElement{w}\gDot \wordRingElement{v},\groupPower{\reFo{\card{r}}}{\teFo{\sym{n}}}) = \indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{p}}}} \, \linearCombinationCoefficient{v_{\teFo{\sym{n}} - \orFo{\sym{p}}}}}{\orFo{\sym{p}}}{} \]Example: two cardinals #
Like before, we'll start with the word group \( \wordGroupSymbol [\reFo{\card{r}},\blFo{\card{b}}] \), whose elements look like this:
\[ \bindCards{\wordGroupSymbol }{\reFo{\card{r}},\blFo{\card{b}}} = \list{\word{1},\word{\reFo{\card{r}}},\word{\reFo{\ncard{r}}},\word{\blFo{\card{b}}},\word{\blFo{\ncard{b}}},\word{\reFo{\card{r}}}{\reFo{\card{r}}},\word{\reFo{\ncard{r}}}{\reFo{\ncard{r}}},\word{\reFo{\card{r}}}{\blFo{\card{b}}},\word{\reFo{\card{r}}}{\blFo{\ncard{b}}},\word{\reFo{\ncard{r}}}{\blFo{\card{b}}},\word{\reFo{\ncard{r}}}{\blFo{\ncard{b}}},\word{\blFo{\card{b}}}{\reFo{\card{r}}},\word{\blFo{\card{b}}}{\reFo{\ncard{r}}},\word{\blFo{\ncard{b}}}{\reFo{\card{r}}},\word{\blFo{\ncard{b}}}{\reFo{\ncard{r}}},\word{\blFo{\card{b}}}{\blFo{\card{b}}},\word{\blFo{\ncard{b}}}{\blFo{\ncard{b}}},\word{\reFo{\card{r}}}{\reFo{\card{r}}}{\reFo{\card{r}}},\word{\reFo{\card{r}}}{\reFo{\card{r}}}{\blFo{\card{b}}},\elSy} \]Therefore, the word ring \( \wordRingSymbol [\reFo{\card{r}},\blFo{\card{b}}] \) consists of any \( \mathbb{Z} \)-linear combination of elements from \( \wordGroupSymbol [\reFo{\card{r}},\blFo{\card{b}}] \). An element of \( \elemOf{\groupElement{w}}{\wordRing{\quiver{2}}} \) can be written as:
\[ \wordRingElement{w} = \indexSum{\linearCombinationCoefficient{w_i} \, \wordRingBasisElement{\sym{i}}}{\sym{i}}{} \]Here, \( \wordSymbol{e} = \list{\word{1},\word{\reFo{\card{r}}},\word{\reFo{\ncard{r}}},\word{\blFo{\card{b}}},\word{\blFo{\ncard{b}}},\word{\reFo{\card{r}}}{\reFo{\card{r}}},\word{\reFo{\ncard{r}}}{\reFo{\ncard{r}}},\word{\reFo{\card{r}}}{\blFo{\card{b}}},\elSy} \) is a sequence that enumerates the elements of \( \wordRingSymbol [\reFo{\card{r}},\blFo{\card{b}}] \) in some order. This serves as an (infinite) basis for the word ring, and effectively allows us to model elements of the ring as infinite-dimensional integer-valued "vectors" with respect to this basis.
Sum #
The sum is defined by adding the coefficients elementwise, as before:
\[ \wordRingElement{w} + \wordRingElement{v} = \indexSum{\paren{\linearCombinationCoefficient{w_{\orFo{\sym{i}}}} + \linearCombinationCoefficient{v_{\orFo{\sym{i}}}}} \, \wordRingBasisElement{\orFo{\sym{i}}}}{\orFo{\sym{i}}}{} \]Product #
The product in the group ring is defined by expanding the product-of-sums into a sum-of-products. Each individual product is then an ordinary group multiplication, which we know how to do. We "gather the like terms" here: the coefficient of each word in the product \( \groupElement{w}\gDot \groupElement{v} \) is, by definition, the sum of the ways it can be formed as products of terms in the sums for \( \groupElement{w}\textAnd \groupElement{v} \):
\[ \begin{aligned} \wordRingElement{w}\gDot \wordRingElement{v}&= \paren{\indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{i}}}} \, \wordRingBasisElement{\orFo{\sym{i}}}}{\orFo{\sym{i}}}{}}\gDot \paren{\indexSum{\linearCombinationCoefficient{v_{\piFo{\sym{j}}}} \, \wordRingBasisElement{\piFo{\sym{j}}}}{\piFo{\sym{j}}}{}}\\ &= \indexSum{\paren{\linearCombinationCoefficient{w_{\orFo{\sym{i}}}} \, \wordRingBasisElement{\orFo{\sym{i}}}}\gDot \paren{\linearCombinationCoefficient{v_{\piFo{\sym{j}}}} \, \wordRingBasisElement{\piFo{\sym{j}}}}}{\substack{\orFo{\sym{i}},\;\piFo{\sym{j}}}}{}\\ &= \indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{i}}}} \, \linearCombinationCoefficient{v_{\piFo{\sym{j}}}} \, \paren{\wordRingBasisElement{\orFo{\sym{i}}}\gdot \wordRingBasisElement{\piFo{\sym{j}}}}}{\substack{\orFo{\sym{i}},\;\piFo{\sym{j}}}}{}\end{aligned} \]Again, we can gather like terms, in other words, those group elements \( \wordRingBasisElement{\teFo{\sym{k}}} \) for which \( \wordRingBasisElement{\orFo{\sym{i}}}\gdot \wordRingBasisElement{\piFo{\sym{j}}} = \wordRingBasisElement{\teFo{\sym{k}}} \):
\[ \begin{aligned} \wordRingElement{w}\gDot \wordRingElement{v}&= \indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{i}}}} \, \linearCombinationCoefficient{v_{\piFo{\sym{j}}}} \, \paren{\wordRingBasisElement{\orFo{\sym{i}}}\gdot \wordRingBasisElement{\piFo{\sym{j}}}}}{\substack{\orFo{\sym{i}},\;\piFo{\sym{j}}}}{}\\ &= \indexSum{\paren{\indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{i}}}} \, \linearCombinationCoefficient{v_{\piFo{\sym{j}}}}}{\substack{\orFo{\sym{i}},\;\piFo{\sym{j}}}}{\wordRingBasisElement{\orFo{\sym{i}}}\gdot \wordRingBasisElement{\piFo{\sym{j}}} = \wordRingBasisElement{\teFo{\sym{k}}}}} \, \wordRingBasisElement{\teFo{\sym{k}}}}{\teFo{\sym{k}}}{}\end{aligned} \]Enumeration of basis elements #
To define the 2-cardinal word ring \( \wordRing{\quiver{2}} \), we made use of the set of possible words \( \wordRingBasisElement{\sym{i}} \) as a basis. It was enough that it was defined in some linear order so that we could index over it in the sum.
In the case of the 1-cardinal ring \( \wordRingSymbol [\reFo{\card{r}}] \) we could use as basis the bi-infinite sequence \( \list{\elSy,\repeatedPower{\reFo{\card{r}}}{-2},\repeatedPower{\reFo{\card{r}}}{-1},\repeatedPower{\reFo{\card{r}}}{0},\repeatedPower{\reFo{\card{r}}}{1},\repeatedPower{\reFo{\card{r}}}{2},\elSy} \), indexed by \( \mathbb{Z} \). This order allowed us to use the condition \( \orFo{\sym{i}} + \piFo{\sym{j}} = \teFo{\sym{k}} \) to solve for \( \piFo{\sym{j}} \) explicitly, turning the conditional inner sum \( \indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{i}}}} \, \linearCombinationCoefficient{v_{\sym{j}}}}{\substack{\orFo{\sym{i}},\;\piFo{\sym{j}}}}{\orFo{\sym{i}} + \piFo{\sym{j}} = \teFo{\sym{k}}} \) into the unconditional sum \( \indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{i}}}} \, \linearCombinationCoefficient{v_{\teFo{\sym{k}} - \orFo{\sym{i}}}}}{\orFo{\sym{i}}}{} \), yielding the simpler expression:
\[ \wordRingElement{w}\gDot \wordRingElement{v} = \indexSum{\paren{\indexSum{\linearCombinationCoefficient{w_{\orFo{\sym{i}}}} \, \linearCombinationCoefficient{v_{\teFo{\sym{k}} - \orFo{\sym{i}}}}}{\orFo{\sym{i}}}{}} \, \wordRingBasisElement{\teFo{\sym{k}}}}{\teFo{\sym{k}}}{} \]But for 2 or more cardinals, a linear enumeration of the basis elements is both complicated to define, and doesn't allow for such a neat arithmetic form for the inner sum. The larger point is that this linear enumeration of basis elements is a kind of holdover from traditional mathematics, where questions of computation and notation aren't usually primary, and it is useful to think about ring elements as being infinite-dimensional integer "vectors". Luckily, it turns out there is a more combinatorial and computational way of thinking about group rings that builds them on a different interpretation, that of the multiset, which we'll see in the next section.
Connection to polynomials #
The elements of the word ring \( \wordRingSymbol [\reFo{\card{r}}] \) look awfully similar to how one adds and multiply polynomials (where \( \reFo{\card{r}} \) plays the role of the indeterminate), except in this case we allow negative powers. Indeed \( \wordRingSymbol [\reFo{\card{r}}] \) is a so-called polynomial ring:
\[ \wordRingSymbol [\reFo{\card{r}}]\isomorphicSymbol \polynomialRing{\ring{\mathbb{Z}}}{\reFo{\card{r}},\inverse{\reFo{\card{r}}}} \]This recalls the Laurent polynomials, although the coefficients appearing in the elements of the word ring are valued in \( \mathbb{Z} \) rather than \( \mathbb{C} \).
The word ring \( \wordRing{\quiver{\sym{k}}} \) for \( \sym{k}>1 \) can be thought of as consisting of multivariate, non-commutative polynomials, with negative powers allowed.
Word rings as multisets #
A concrete interpretation of an element \( \elemOf{\ringElement{ \omega }}{\wordRingSymbol } \) can be given when the integer coefficients are all positive. In this case, we can see \( \ringElement{ \omega } \) as representing a [[[multiset:Multisets]]] of words, where the number of times a given word \( \elemOf{\groupElement{w}}{\wordGroupSymbol } \) is present in the multiset is represented by the coefficient of \( \groupElement{w} \) in the sum \( \ringElement{ \omega } \). The zero element of the ring is then just the empty multiset. But since coefficients can be negative, it is natural to extend our interpretation to see a general element \( \ringElement{ \omega } \) as representing a signed multiset in which paths may appear in their ordinary form, or in a negated form, with the total multiplicity being described by the coefficient.
From now on, whenever we use the term multiset, it should be interpreted as signed multiset. This elision makes for less clunky language, but more importantly it sets up a simple and useful combinatorial interpretation of the constructions we'll consider. In each case we can still extend this interpretation to the setting of signed multisets, but doing this explicitly would bog us down for no real reward.