# Number of words of length N that reduce to the identity in a specific Coxeter group

Suppose we have a Coxeter group whose diagram is given by a simplex. In other words, $$G=\langle g_1,\ldots ,g_k\mid(g_i)^2=e,\,(g_ig_j)^3=e \rangle$$. How many words of length $$N$$ simplify to the identity? What is the recursion/generating function? The case $$k=2$$ is easy, because the group is finite; the corresponding generating function is $$E(x)=\frac{1}{3}[2/(1−x^2)+1/(1−4x^2)]$$. I expect $$k=3$$ is likewise readily doable. Is there a general solution? What if we change the relations to $$(g_ig_j)^m=e \,\,\forall i,j$$?

More generally, if I give a group element in this group whose shortest word is $$g_{i_1}\cdots g_{i_p}$$, how many words of length $$N$$ are equivalent to it?

Keeping in mind the word problem is solvable for Coxeter groups.

• The case when $m=\infty$ is also doable; the answer is then (I think) $k^{N/2} C_{N/2}$ for even $N$, with $C_n$ being the $n$th Catalan number -- this comes from treating the problem as counting strings of $k$-colored parentheses. – Craig Apr 10 at 18:19
• Did you really mean all pairs $g_i g_j$ to have order 3? Probably you meant just some pairs, and then, of course, the answer will have to be phrased in terms of the associated graph (but I don't know what it will look like in terms of that). I only mean to emphasise that this is actually a huge family of questions. – LSpice Apr 10 at 18:28
• I did really mean all pairs have order 3, and the Coxeter diagram is a simplex. – Craig Apr 10 at 18:35
• Sorry, my comment about the $m=\infty$ case is incorrect since we do not have a distinction between "left" and "right" parentheses. The number is much larger than that. – Craig Apr 10 at 18:48
• I count all words; see the example case of $k=2$. $E(x)$ expands to $1 + 2x^2 + 6x^4 +\ldots$, which corresponds to $\{e\}, \{(g_1)^2, (g_2)^2\}, \{(g_1)^4, (g_1)^2(g_2)^2, g_1g_2g_2g_1, g_2g_1g_1g_2, (g_2)^2(g_1)^2, (g_2)^4\} \ldots$. – Craig Apr 11 at 18:45

This is not an answer, but rather an attempt at working out the $$m=\infty$$ case properly.
Let's assume we want to know the number of words of length $$2N$$ ($$g_{i_1}\ldots g_{i_{2N}}$$) that reduce to the identity, and let's call this quantity $$E_{2N}$$. Let's break into two cases: $$i_1 = i_{2N}$$ and $$i_1 \neq i_{2N}$$. Obviously the first case contributes $$kE_{2N-2}$$. In the second case, there must be some index $$2p$$ such that $$i_{2p} = i_1$$ and the initial subword $$g_{i_1}\ldots g_{i_{2p}} = e = g_{i_{2p+1}} \ldots g_{i_{2N}}$$. This would give us a contribution of $$kE_{2p-2} * (k-1)/k E_{2N-2p}$$ (from the requirement that $$i_{2N} \neq i_1$$). Except that we've overcounted these words -- there could be multiple indices $$p$$ that qualify.
Fortunately, we can use simple inclusion-exclusion to get the correct count. These words look like $$g_{i_1}\ldots g_{i_{2p_1-1}} g_{i_1} g_{i_{2p_1+1}} \ldots g_{i_{2p_n -1}} g_{i_1} g_{i_{2p_n +1}} \ldots g_{i_{2N}}$$, with each subword $$g_{i_{2p_j+1}} \ldots g_{i_{2p_{j+1}-1}} g_{i_1}$$ equal to the identity. We get a count $$kE_{2p_1 - 2} * (1/k E_{2p_2 - 2p_1}) * \ldots * (1/k E_{2p_n - 2p_{n-1}}) * ((k-1)/k E_{2N-2p_n}$$. Each factor of $$1/k$$ comes from the requirement that the terminal end of the subword is $$i_1$$; the factor of $$(k-1)/k$$ comes from the fact that $$i_{2N} \neq i_1$$, and the initial factor of $$k$$ comes from summing over possible values of $$i_1$$.
So we have the following recursion: $$$$E_{2N} = kE_{2N-2} + \sum_{p=1}^{N-1} (k-1) E_{2p-2} E_{2N-2p} - \sum_{0 Writing this as a generating function equation, we get: $$$$E(x) = \sum_n E_{2n} x^n$$$$ $$$$E(x) = 1 + kxE(x) + (k-1)x E(x)(E(x)-1) - \frac{k-1}{k} x E(x)(E(x)-1)^2 + \frac{k-1}{k^2} x E(x)(E(x)-1)^3 -\ldots$$$$ or $$$$E(x) = 1 + xE(x) * [k + (k-1) (E(x)-1) / (1 + (E(x)-1)/k)] \,.$$$$ The extra $$1$$ term at the beginning is to account for $$E_0$$, and the $$(E(x)-1)$$ terms are to account for the fact that the subwords cannot be 0-length. Multiplying both sides by $$k-1+E$$ we get $$$$0 = (k-1) - (k-2)E(x) + (k^2x -1) E(x)^2$$$$ or $$$$E(x) = \frac{k \sqrt{1-4(k-1)x} - (k-2)}{2(1-k^2x)} \,.$$$$ I would greatly appreciate it if people were to check my math.