Let $W$ be a Coxeter group (finite or infinite) with (finite) set $S$ of Coxeter generators, and let $I \subseteq S$ be some subset. If $w\in W$ then I call $m_I(w)$ the minimum total number of occurrences of elements of $I$ in some expression for $w$ as a product of elements of $S$, or formally: $$ m_I(w) := \min\{m : \exists x_1,\ldots,x_l\in S\; (w = x_1\cdots x_l \,\land\, m=\#\{i : x_i\in I\})\} $$ Evidently, $m_S$ is the usual length function on $W$, and also, $m_I(w)$ is the minimum total number of occurrences of elements of $I$ in some reduced expression for $w$ (since any expression for $w$ has a reduced subexpression).

I don't know anything else about $m_I$, including:

Question 0: Does this function have a standard name?

Now consider the would-be-Poincaré series associated to $m_I$, namely:

$$ P_I(q) := \sum_{w\in W} q^{m_I(w)} $$

This doesn't make sense in general, but if the ("parabolic") subgroup generated by $S\setminus I$ is finite, which I now assume, then there are only finitely many $w \in W$ having a given value of $m_I$, and $P_I \in \mathbb{Z}[[q]]$.

Question 1: Is this enumerating function rational? (I.e., does it belong to $\mathbb{Q}(q)$?)

Question 2: Assuming yes, how can I compute (a rational form for) it algorithmically?

I'm thinking maybe there's a standard reduced form for elements of $W$ that guarantees that they have the minimum number of elements of $I$, and maybe this standard form is recognizable by a finite automaton, which would be very much in line with other results about Coxeter groups, but I didn't find anything (presumably for lack of knowledge of the correct name for $m_I$). Of course, it would be even better to be able to compute $P_I$ without going through an automaton (along the lines of proposition 7.1.7 in Björner & Brenti's book Combinatorics of Coxeter Groups).

  • $\begingroup$ Is your assertion about $m_I(w)$ being realized by a reduced expression for $w$ clear? $\endgroup$ – Sam Hopkins Jul 20 '17 at 17:53
  • 1
    $\begingroup$ @SamHopkins Let $\bar w$ be any expression for $w$ with $m_I(w)$ generators from $I$. Then (Björner & Brenti, corollary 1.4.8(i)) there is a subword $\bar w'$ of $\bar w$ (in the sense that some letters have been removed from $\bar w$) that is a reduced expression for $w$; but the number of generators from $I$ cannot have decreased, by minimality of $m_I(w)$, so $\bar w'$ is a reduced expression for $w$ with $m_I(w)$ generators from $I$. $\endgroup$ – Gro-Tsen Jul 20 '17 at 18:38

Your Answer

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

Browse other questions tagged or ask your own question.