Prefixes of a word multiplying to the identity in a free group

combinatorial-group-theorycombinatorics-on-wordsfree-groupsgroup-theorymonoid

Let $A$ be a finite alphabet, and let $w \in (A \cup A^{-1})^\ast$ be a freely reduced word over the alphabet $A$ and formal inverse symbols $A^{-1}$. Suppose $w$ is non-empty. Can there ever be non-empty prefixes $p_i \in (A \cup A^{-1})^\ast$ of the word $w$ such that $p_1 p_2 \cdots p_n = 1$ in the free group on $A$?

For example, if $w = abca^{-1}$ then it is easy to see that no product of elements from $\{ a, ab, abc, abca^{-1}\}$ ever equals $1$. Some "non-trivial" behaviour can happen: for example, if $w = aba^{-1}b^{-1}a^{-1}$ then we find the product $$aba^{-1}b^{-1}a^{-1} \cdot aba^{-1} \cdot ab = aba^{-1}b,$$ i.e. the word $aba^{-1}b$ is a product of three prefixes, but is not graphically a product of prefixes, of $w$. I don't see how this kind of cancellation could ever be enough to completely cancel such a product, however.

An equivalent formulation of the question is: let $X_w$ be the subsemigroup of a free group $F_A$ generated by the set of non-empty prefixes of a word $w \in F_A$. Can we ever have $1 \in X_w$?

Best Answer

I will argue that this is impossible by induction on $n$ and $|w|$.

Suppose $p_1 p_2 \cdots p_n = 1$, where $p_1, p_2, \dots, p_n$ are prefixes of $w$. Say the first letter of $w$ is $a$. First suppose that each of $p_1, \dots, p_n$ ends with $a^{-1}$. Then each $p_i^a = a^{-1} p_i a$ is a prefix of $a^{-1} w$ and $p_1^a p_2^a \cdots p_n^a = 1$. By induction on $|w|$ this is impossible, so at least one of the prefixes $p_1, \dots, p_n$ must end with something other than $a^{-1}$, say $b^{-1}$, where $b \neq a$ (possibly $b = a^{-1}$). Cycling the indices if necessary, suppose it is $p_n$ that ends with $b^{-1}$. Then when we reduce the product $p_1 \cdots p_n$, that $b^{-1}$ at the end of $p_n$ cancels some letter $b$ somewhere in $p_1\cdots p_{n-1}$, say in $p_k$. Let $p_k'$ be the prefix of $p_k$ up to and excluding that letter $b$. Then $p_1 \cdots p_{k-1} p'_k = 1$, and this is a contradiction by induction on $n$.

Comment: I find it really useful to visualize a cancellative product $w_1 \cdots w_n = 1$ by means of a 3-regular tree with $n$ leaves. The words are written around the perimeter of the tree, each starting from a different leaf, and they always cancel the letter on the opposite side of the edge. The tree is uniquely determined by $w_1, \dots, w_n$. For example for $n = 2$ one just has an edge with $w_1$ written below left-to-right and $w_2$ written above right-to-left; for $n = 3$ one has a star with 3 edges. I found the above proof using this sort of graphical calculus.

Related Question