# Number of reduced decompositions of the longest element of the Weyl group

Let $$R$$ be a reduced root system, $$W$$ the associated Weyl group, and $$w_0 \in W$$ the longest element of $$W$$. In general $$w_0$$ admits more than one reduced decomposition into a product of reflections, a number which we denote by $$d_R$$. Where can one find a list of values of $$d_R$$ for low-dimensional root systems?

For example are the explicit values of $$d_R$$ known for the exceptional root systems?

• For Types A and B(=C) there are product formulas for these numbers: see the famous paper math.mit.edu/~rstan/pubs/pubfiles/56.pdf and math.stackexchange.com/questions/2271510/…. I'm pretty sure for Type D there is not a product formula (as Stanley mentions there is a big prime, 193, in the factorization of the number of reduced words of the longest word in Type $D_4$). As for exceptionals I don't know of a list but this is in principle something a computer can do. – Sam Hopkins Aug 28 at 16:36
• In the linked stackexchange webpage the B-series formula in the answer gives, for low values of $n$, a product with negative limits. Is this an error or is this an example of some convention I am not familar with? For example, what is the value for $B_2$? – Bas Winkelman Aug 28 at 17:07
• Maybe the formula Zach wrote is not quite right. For $B_2$ the answer should be 2. It is the same as the number of linear extensions of the root poset (poset of positive roots whereby $\alpha \leq \beta$ if $\beta-\alpha$ is a nonnegative sum of simple roots). This poset is the same as the shifted trapezoid shape $(2n-1,2n-3,...,1)$ poset. This number also happens to be the same as the number of SYTs of $n\times n$ square shape. – Sam Hopkins Aug 28 at 17:14
• You can see Corollary 5.2 of the paper of Stanley linked above for another way of writing the product formula for the Type B # of reduced decompositions (he lists it as a conjecture but it has been proven). – Sam Hopkins Aug 28 at 17:16
• The basic thing that's going on here is that there's an Edelman-Greene style bijection in Types A and B (and also the non-Weyl types $I_2(m)$ and $H_3$- sometimes these types are called the 'coincidental types'). The other types don't have such a bijection. – Sam Hopkins Aug 28 at 17:18

This is easy to do in SageMath. E.g. the following code

G = WeylGroup("F4")
w = G.long_element_hardcoded()
print(w)
rw = w.reduced_words()
len(rw)


outputs 2144892. If you want to look at some of these reduced words just examine the list rw. To create a list for classical types of different rank do

res = {}
for n in range(2,5):
G = WeylGroup(["A", n])
w = G.long_element_hardcoded()
print("Calculating rank ", n)
res[n] = len(w.reduced_words())

• Note 2144892 = 2^2 x 3 x 47 x 3803, again suggesting lack of product formula. – Sam Hopkins Aug 28 at 19:34
• I created findstat.org/StatisticsDatabase/St001585. If you have enough power to do E6 that would be great! – Martin Rubey Aug 28 at 19:44
• @MartinRubey I will try some computer in Prague's Charles University to which I have remote access. But I am pessimistic. This algorithm actually generates and stores all the reduced words so it eats all available memory rather quickly. – Vít Tuček Aug 28 at 19:54
• Counting reduced words is the same as counting directed paths between two vertices in a certain directed graph (the weak order graph), so it's possible you could write code by hand that does this faster than what's in Sage. – Sam Hopkins Aug 28 at 19:59
• @SamHopkins, indeed, this is much faster! I added corresponding code to the findstat entry. $D_5$ is now easy. Unfortunately, FindStat has a limitation on the size of statistic values, so anything beyond $A_6$ is too large. – Martin Rubey Aug 28 at 20:20

Around the time Fomin and I wrote this paper, Tao Kai Lam applied the technique to type $$D_n$$. It emerged that it was "natural" to weight a reduced decomposition $$\rho$$ by $$2^{d(\rho)}$$, where $$d(\rho)$$ is the number of simple reflections in $$\rho$$ that correspond to the $$n-2$$ "nonbranch nodes" in the Coxeter diagram for $$D_n$$. Using this weighting, there is a nice product formula for the number of weighted reduced decompositions of the longest element, which I unfortunately have forgotten. I hope someone can redo this work.

• Is this weighted sum related to linear extensions in some way? – Sam Hopkins Aug 28 at 19:09
• @SamHopkins: I have a hazy recollection that it is a power of 2 times the number of SYT of the shifted shape $(2n-2,2n-4,\dots,4,2)$ (for which there is a nice product formula). – Richard Stanley Aug 28 at 19:41
• That would make a lot of sense! In conservancy.umn.edu/bitstream/handle/11299/159973/… Williams calls the poset you're talking about the "flattened root poset" of $D_n$. – Sam Hopkins Aug 28 at 19:44
• Actually, the result you mention might follow from this paper of Billey and Haiman: math.berkeley.edu/~mhaiman/ftp/schubert/schubert.pdf (see also the discussion on pg. 46 of the thesis of Williams linked above) – Sam Hopkins Aug 28 at 19:46