Absolute length returning wrong value in affine type

[thecaligarmo]

Steps To Reproduce

When trying to get the absolute length of an element in an Affine Coxeter group, we get the wrong value.

sage: W = CoxeterGroup(["A",2,1])
sage: (r, s, t) = W.simple_reflections()
sage: (r * s * r * t).absolute_length()
1

Mathematical Background: Given an affine Coxeter group $W$ generated by a set $S$, the set $R$ (of reflections) is the conjugates of $S$. In other words, $R = \cup_{w \in W} wSw^{-1}$. The absolute length of an element $w$ is the minimal length of words which represent $w$ over the generating set $R$.

In the above case, $S = \left\{ r, s, t\right\}$ and $rsr$ and $t$ are both reflections in $R$ implying that $rsrt$ has absolute length $2$. (Reflections always have an odd number of generators and so $rsrt$ must have an even absolute length).

Expected Behavior

sage: W = CoxeterGroup(["A",2,1])
sage: (r, s, t) = W.simple_reflections()
sage: (r * s * r * t).absolute_length()
2

Actual Behavior

sage: W = CoxeterGroup(["A",2,1])
sage: (r, s, t) = W.simple_reflections()
sage: (r * s * r * t).absolute_length()
1

Additional Information

No response

Environment

- **OS: Ubuntu 22.04**:
- **Sage Version: 9.8 and 10.0**:

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[fchapoton]

This is using the definition as (M-1).rank(), maybe not valid outside of finite type ?

[thecaligarmo]

Yeah, I think (M-1).rank() only works for finite type. The rank in affine cases is sometimes smaller than the absolute length (as can be seen in the example above). The rank in $\tilde{A_2}$ is at most $2$, but there are elements of absolute length 3 and 4.
In affine case you can get around it using the paper by Lewis, McCammond, Peterson and Schwer (https://arxiv.org/abs/1710.06920) where they basically state that in an affine Coxeter group, the absolute length is equal to $2 \cdot dim(w) - dim(p(w))$ where $p(w)$ is a projection of $w$ to its finite part.

[fchapoton]

feel free to propose a pull request

[thecaligarmo]

I'm trying to get it to work. The main issue I'm currently running into is that the extended affine weyl groups give translations in terms of the coweight lattice. The dimension from the article gives it based off the root lattice. So I just need to convert things properly and make sure things are going ok between types.

[thecaligarmo]

Update on this ticket:
In order to get the correct dimension, I need to expand the basis by one dimension (similar to what Kac did in his Lie algebra's book in Section 6). I've gotten it so that the absolute length now gives the correct value in affine type, but this had unintended consequences. In particular, plotting is now plotting in 1 dimension too high. Additionally, the Pieri factors seem to be having issues (haven't looked into what's causing the issues though).

There are some additional changes in the docs that will need to change since matrices are now 1 dimension bigger in order to compensate for this higher dimension.

The current state of this ticket can be found on my branch:
https://github.com/thecaligarmo/sage/tree/absolute_length

(Note that I still need to add some documentation/tests to the new code so it's still not 100%, but it's at least in a working state now).

[thecaligarmo]

@fchapoton I might need some help on this ticket if you're available?

I think the main issue is that I'm not fully understanding how the current model for affine Coxeter/Weyl groups is working. It seems to be adding delta and deltacheck, but there's no documentation as to what these are. I'm following Kac's book on affine Weyl groups and in that he's adding the simple roots + an additional parameter which he calls d. In this book, he defines a delta and a deltacheck, but he mentions that the basis should be the simple roots together with d. (I think this is potentially the Lambda_0^v that is defined in the docs?)

I tried to add the d as a basis element, and I got it to work, but the documentation/tests are having problems which means I'm doing something wrong. Either I'm doing it wrong programmatically (in that I'm adding things in the wrong place because I'm not understanding the underlying structure) or I'm not understanding it mathematically (which is a little harder as there's not much documentation in the code to show where the basis/etc. is coming from so it's a little hard to follow exactly what is being done or what method is being used mathematically.

If you have time/space can you look over what I've done so far and see potentially where I'm going wrong?

I think @nthiery also was the one who initiated most of this stuff so I'm cc'ing him in case he might have some guidance on this.

[tscrim]

So this might fix things for affine Coxeter groups, but what about the general case? I might have been the one who did this implementation, but it was too long ago for me to remember too well what I looked at.

However, this paper of Dyer seems to propose a reasonable solution: Remove simple reflections in sequence until you get the empty word. So in code, it would be something like this:

import itertools
P = self.parent()
w = self.reduced_word()
s = P.simple_reflections()
one = P.one()
for ell in range(len(w)-1, -1, -1):
    for wd in itertools.combinations(w, ell):
        if P.prod(s[i] for i in wd) == one:
            return ell

which would be done outside of finite type.

[thecaligarmo]

This seems to be correct for all types! (I hadn't seen that article. It's super nice!) I think the code you have would only need to be changed in the last line:

import itertools
P = self.parent()
w = self.reduced_word()
s = P.simple_reflections()
one = P.one()
n = len(w)
for ell in range(n-1, -1, -1):
    for wd in itertools.combinations(w, ell):
        if P.prod(s[i] for i in wd) == one:
            return n - ell

The theorem which you're using is (I'm writing it down just to have a source without having to look it up again):
Theorem 1.1 Let $w = s_1 \ldots s_n$ such that $\ell(w) = n$. Then $\ell'(w) = \min \{ p \in \mathbb{N} \;:\; 1 \leq i_1 < \ldots i_p \leq n,\, e = s_1 \cdots \hat{s_{i_1}} \cdots\hat{s_{i_p}} \cdots s_n \}$
where $\ell$ is standard length, $\ell'$ is reflection/absolute length, and hat implies omission.

So if I'm understanding the code and theorem correctly, we don't want the number of letters remaining, but $n$ minus the number of letters remaining, giving us $p$. (I'll go ahead and implement this. If there's an error or something in my logic, or I missed something, let me know)

[tscrim]

Ah, right, yes. Thanks for fixing it. Once I saw the statement, I was like “of course that should be true by the strong exchange condition.” It also gives you a sequence of reflections too if you are careful about what generators cancel.

Thank you. Cc me and I will do the review. I was going to do this myself but forgot about it. I can also provide an implementation to obtain a sequence reflections (as a separate method) if you don’t want to do this yourself.

[thecaligarmo]

Ok, as long as I didn't screw up the styles, then it should be good to go now. I added a test and also bibliography to state precisely where the information is coming from for future reference.