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.

  • $\begingroup$ 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. $\endgroup$ – Craig Apr 10 at 18:19
  • $\begingroup$ 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. $\endgroup$ – LSpice Apr 10 at 18:28
  • $\begingroup$ I did really mean all pairs have order 3, and the Coxeter diagram is a simplex. $\endgroup$ – Craig Apr 10 at 18:35
  • 2
    $\begingroup$ 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. $\endgroup$ – Craig Apr 10 at 18:48
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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: \begin{equation} E_{2N} = kE_{2N-2} + \sum_{p=1}^{N-1} (k-1) E_{2p-2} E_{2N-2p} - \sum_{0<p_1<p_2<N} (k-1)/k E_{2p_1 -2} E_{2p_2 -2p_1} E_{2N-2p_2} + \ldots \end{equation} Writing this as a generating function equation, we get: \begin{equation} E(x) = \sum_n E_{2n} x^n \end{equation} \begin{equation} 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 \end{equation} or \begin{equation} E(x) = 1 + xE(x) * [k + (k-1) (E(x)-1) / (1 + (E(x)-1)/k)] \,. \end{equation} 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 \begin{equation} 0 = (k-1) - (k-2)E(x) + (k^2x -1) E(x)^2 \end{equation} or \begin{equation} E(x) = \frac{k \sqrt{1-4(k-1)x} - (k-2)}{2(1-k^2x)} \,. \end{equation} I would greatly appreciate it if people were to check my math.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.