Length of a word

Question

I came across this definition on the length (say $L$) of the word. If $G$ is a group, and $S$ is a subset of $G$ then a word in $S$ is any expression of the form $W=s_1^{\epsilon_1}s_2^{\epsilon_2}\cdots s_n^{\epsilon_n}$ where each $\epsilon_i$ is either $+1$ or $-1$ and each $s_i$ belongs to $S$. The link says that the $n$ is said to be the length of the word. I wanted to know how is it well defined. As in, if I take $W_1=s_1s_2$ and $W_2=s_1s_3s_3^{-1}s_2$, then $W_1=W_2$ but $L(W_1)=2\neq L(W_2)=4$. So how is $L$ well defined? Is the link missing something, like including a reduced word in its definition? Can someone please give me a reference of a good group theory book which deals with word lengths?

Answer 1

A word in $S$ is nothing more than a special kind of sequence (often called a "string" to emphasize the connection with computer science). Perhaps a good way to write that sequence, to emphasize its "sequency" nature, is like this: $$W = (s_1^{\epsilon_1},s_2^{\epsilon_2},...,s_n^{\epsilon_n}) $$ What one does with words is to "evaluate" them, which simply means to evaluate the product of the terms of the word, using the group operation. To more formally distinguish between the word and its evaluation, one sometimes puts a bar over the word in order to represent the evaluation: $$\overline W = s_1^{\epsilon_1} s_2^{\epsilon_2} ... s_n^{\epsilon_n} $$ So, the length of $W$ is indeed well defined, because after all $W$ is a sequence of length $n$.

On the other hand, as you say, the length of a word representing a group element is not well-defined, because it is trivially easy to take one word represesnting a group element and convert it into a word of different length representing the same element, for example by inserting a subword $s_i s_i^{-1}$ anywhere in the middle, which of course makes a nonreduced word.

The way you get a well defined word length of a group element is by taking a minimum: given a group element $g$, the word length of $g$ is the minimum length of all words $W$ such that $\overline W = g$.

Having said all of that, it is a common convention in group theory to simplify notation, depending on the context, and to write the word without the delimiting parentheses and the separating commas: $$W = s_1^{\epsilon_1} s_2^{\epsilon_2} ... s_n^{\epsilon_n} $$ It is then up to the reader to beware of this simplification of notation, and to know when an expression like $s_1^{\epsilon_1} s_2^{\epsilon_2} ... s_n^{\epsilon_n}$ represents a string and when it represents an evaluated group element.

A good book which keeps track of these concepts with care is Word Processing in Groups by Epstein, Cannon, Holt, Levy, Paterson, and Thurston.

Answer 2

To complement Lee Mosher's fine answer, I thought I would briefly discuss the "cheat" you are using to make length ill-defined. This is relevant to free groups.

When we discuss words we usually assume them to be freely reduced, that is, we assume that they do not contain any subword of the form $a^{\epsilon}a^{-\epsilon}$, $\epsilon=\pm1$. So we simply don't consider the word $s_1s_3s_3^{-1}s_2$, but would first cancel the $s_3$-terms. We can therefore define a length function $L_{red}(W):=n$ where $n$ is the length of a freely reduced word $\overline{W}$ obtained from $W$ by iteratively deleting the illegal subwords $a^{\epsilon}a^{-\epsilon}$. This reduction process reduces length, so such a word $\overline{W}$ clearly exists, although may not be uniquely defined. Moreover, its length may not be uniquely defined! We therefore have an interesting question:

Is the length function $L_{red}: (X^{\pm1})^*\rightarrow\mathbb{N}\cup\{0\}$ well-defined?

The answer to this question is yes, and it follows from the stronger fact that the freely reduced word $\overline{W}$ is uniquely determined by $W$. That is, the order with which we perform the free reduction moves does not matter, and we end up with a unique word. This fact is the crucial, non-trivial step in viewing free groups as words over an alphabet. You can find a complete proof in Section 1.2 of the book Combinatorial group theory by Magnus, Karrass and Solitar.