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.



Algorithm to determine if a vector in the geometric representation of a Coxeter group is proportional to a root
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.


