# Algorithm to determine if a vector in the geometric representation of a Coxeter group is proportional to a root

Let $$W$$ be a Coxeter group, and let $$V$$ be its geometric representation (as defined for instance in Section 5.3 of Humphreys' book Reflection groups and Coxeter groups). Let $$v\in V\backslash\{0\}$$ (in the case in which I am interested one may assume that $$v$$ is a $$\mathbb{Q}$$-linear combination of positive roots).

Is there an algorithm allowing one to determine in finite time if $$v$$ is proportional to a root ?

If $$W$$ is finite this is clear (one can write down the matrix of the reflection sending $$v$$ to $$-v$$ and preserving the Tits form, and compare with the matrices of reflections in $$W$$), but I am interested in the case where $$W$$ is infinite.

• You have to be a little bit careful about how things are encoded here. I guess $\mathbb{Q}$-linear combination of positive roots is okay though. Feb 22, 2021 at 16:50
• Yes, sure ! I also think that $\mathbb{Q}$-linear combination of roots is OK and that's why I specified... But maybe further restrictions are necessary. For arbitrary $v$ in $V$ I guess that one indeed has incoding problems and the answer is probably "no". :) Feb 22, 2021 at 17:01
• Can you clarify what the encoding problems might be? Is it because $V$ might be larger than the linear span of the roots (something I like to avoid, but standard in Kac-Moody Lie theory, I guess). Or is it something else? Feb 22, 2021 at 18:04
• @NathanReading: I just meant that it does not make sense, using the standard interpretation of algorithms in terms of Turing machines, to feed an arbitrary element of a real vector space into an algorithm. Of course with $\mathbb{Q}$-linear combinations of positive roots there is no issue (in fact since the question only cares about proportionality you may as well clear denominators and assume it's a $\mathbb{Z}$-linear combination of positive roots). Feb 22, 2021 at 18:10
• @SamHopkins: Thanks, I see. The point is $\mathbb{Q}$, not that it's in the span of the roots. Feb 22, 2021 at 20:29

To avoid repetition, I'll just say $$v$$ "is a root" instead of $$v$$ "is proportional to a root", because the algorithm won't care about scaling much.

Here is how I would try to program this. (I have a "bad" habit of putting simple roots and fundamental weights in spaces dual to each other, contrary to the usual Lie theory construction. There are good reasons for this, IMHO, but this is not the place for that discussion.) In any case, I'll have my simple roots $$\alpha_1,\ldots,\alpha_n$$ in a vector space $$V$$ and my fundamental weights $$\rho_1,\ldots,\rho_n$$ in $$V^*$$. Let $$\langle\cdot,\cdot\rangle$$ be the pairing between $$V^*$$ and $$V$$.

I will assume $$v\neq0$$ is a nonnegative $$\mathbb{Q}$$-linear combination of the $$\alpha_1,\ldots,\alpha_n$$. (If it's not either this or a nonpositive combination, we already know it's not a root.)

The main point of the algorithm will be to look at $$v^\perp=\{x\in V^*:\langle x,v\rangle=0\}$$ and decide if its intersection with the Tits cone is correct for $$v$$ to be a root (or equivalently whether $$v^\perp$$ is a reflecting hyperplane in the dual representation $$V^*$$).

We should first test if $$v^\perp$$ intersects the Tits cone. If not, then $$v$$ is not a root and also the algorithm I'm about to describe will not terminate. (So we had better test it separately.) I think, however, that this is easy: For any root $$\beta$$ (for example, we could take $$\beta$$ to be a simple root), consider the line segment connecting $$v$$ to $$\beta$$. Then $$v^\perp$$ fails to intersect the Tits cone if and only if somewhere along that line segment there is a vector whose squared length is zero, possibly only $$v$$ itself. (That's the part that I think is true... but surely we know this, don't we?)

So, we will assume $$v^\perp$$ intersects the Tits cone. Let's choose a point $$p$$ on $$v^\perp$$ in the Tits cone. For this, I think we can just take the point on $$v^\perp$$ closest to $$\rho_1+\cdots+\rho_n$$. Since the Tits cone is convex and $$\rho_1+\cdots+\rho_n$$ is in the Tits cone, this should work. (Sitting here, I don't see why it wouldn't work in the Euclidean sense of "closest point", but maybe we need to think about the metric on the Tits cone.) We need $$p$$ as a linear combination of $$\rho_1,\ldots,\rho_n$$.

We will now apply a sequence of simple reflections (in the dual representation $$V^*$$) to move $$p$$ into the fundamental chamber (the cone spanned by $$\rho_1,\ldots,\rho_n$$). At each step, we look for an index $$i$$ such that the $$\rho_i$$ coordinate of $$p$$ is negative, and apply $$s_i$$ to $$p$$. We also apply $$s_i$$ to $$v$$. When we can't do that any more, call the new vector $$v'$$ and the new point $$p'$$. (Why does this terminate? Because $$p$$ is contained in $$xD$$ fro $$D$$ the fundamental chamber and $$x\in W$$. At every step, the length of $$x$$ decreases.)

There are 3 cases: If $$p'$$ is in the interior of the fundamental chamber (i.e. has all $$\rho_i$$-coordinates strictly positive), then $$v'$$ is not a root because $$(v')^\perp$$ cuts through the fundamental chamber, and also $$v$$ is not a root. If $$p'$$ is in the relative interior of a facet (i.e. if $$p'$$ has exactly $$n-1$$ positive $$\rho_i$$-coordinates), then $$v'$$ is a simple root, so $$v$$ is a root.

If $$p'$$ has more than one $$\rho_i$$-coordinate zero, then we have identified a standard parabolic sub root-system ("root subsystem"?) where $$v'$$ must live if it is to be a root. (Namely, the subsystem spanned by the $$\alpha_i$$ such that the $$\rho_i$$-coordinate of $$p'$$ is zero.) We can run the whole procedure again using $$v'$$ and that sub root-system.

But it is probably best to try to avoid having to run the procedure again inductively. This could be accomplished by making a random perturbation of the initial $$p$$ within $$v^\perp$$, so that $$v'$$ does not live on any lower-dimensional faces of the fundamental chamber. This doesn't actually save any steps in the process, but may make programming simpler. Alternatively, after getting stuck with $$p'$$ in a lower-dimensional face of the fundamental chamber, we could perturb $$p'$$ within $$(v')^\perp$$ and keep going.

• Whatever the place is for the discussion of why simple roots and fundamental weights live in dual spaces, I'd like to go there. Feb 22, 2021 at 20:39
• Thank you very much for your very detailed answer ! I am not convinced yet that every step which you describe can be turned into an algorithm (for instance, checking that there is a point on a real line segment that has squared length equal to zero), but I'll think about it. Anyway this is very helpful ! Feb 23, 2021 at 17:50
• @ThomasGobet: If you parametrize the line segment with one real parameter, then the squared length is a quadratic function of the parameter, I think. So you're just checking whether some piece of a parabola has a zero. Feb 23, 2021 at 20:28
• @LSpice: Probably this isn't the place, but I can't resist, given that you (and one upvoter of your comment) want to hear. First, I take no position on why Lie theorists want to put roots and weights in the same space. There are probably good reasons. But here's what I want: A Cartan matrix $A$ defines a group $W$ of reflections, and this is a group of isometries of a bilinear form on the vector space $V$ where the roots live (the usual form defined by the Cartan matrix). Feb 23, 2021 at 21:22
• (The simple co-roots are not in the dual space, but rather they are scalings of the simple roots that make sense of the symmetrizability of $A$.) So there is a geometry of roots and reflections in $V$. On the other hand, $W$ has a dual representation in $V^*$ (dual in the usual sense). This defines a group of isometries of some other bilinear form. In $V^*$ we have the geometry of fundamental weights and reflecting hyperplanes, the Tits cone, etc. These two geometries are very different sometimes. Feb 23, 2021 at 21:22