Classification of finite and affine Coxeter groups

[stumpc5]

The bug here is two-fold:

1. The roots for a CoxeterGroup are constructed as in Humphreys "in the Coxeter sense, that all have the same norm". Therefore it seems more natural to not at all introduce a type C and to follow Humphrey's classification of finite Coxeter groups given on page 32.

2. The current implementation of types B/C (which I suggest to remove and to only keep type B) is also broken:

• First Sage start

  sage: W = CoxeterGroup(['B',4])
  sage: W.coxeter_matrix().coxeter_type()
  Coxeter type of ['B', 4]
  sage: W = CoxeterGroup(['C',4])
  sage: W.coxeter_matrix().coxeter_type()
  Coxeter type of ['B', 4]
  

• Second Sage start

  sage: W = CoxeterGroup(['C',4])
  sage: W.coxeter_matrix().coxeter_type()
  Coxeter type of ['C', 4]
  sage: W = CoxeterGroup(['B',4])
  sage: W.coxeter_matrix().coxeter_type()
  Coxeter type of ['C', 4]
  

[stumpc5]

And what to do with

sage: CoxeterGroup(CoxeterType(['B',2],['B',2]).coxeter_matrix()).coxeter_matrix().coxeter_type()
Coxeter type of G2xG2 relabelled by {1: 3, 2: 4}

[tscrim]

With 7.0.beta1, I get:

sage: CoxeterGroup(CoxeterType(['B',2],['B',2]).coxeter_matrix()).coxeter_matrix().coxeter_type()
Coxeter type of B2xB2

What are you using when you tested that? Although, that you got that in any situation is very frightening to me.

[stumpc5]

Hm, after restarting with 7.0.beta2 I also get this result, and I wasn't able to reproduce the bug even after retyping all comments that seemed to be related. So let's leave this aside for now.

[stumpc5]

At some point during that session I accidentally copied almost the complete source of subword_complex.py into the terminal. So it might also be that this caused the issue, though I wouldn't know how.)

[stumpc5]

@tscrim: And what to do with

sage: sage: W = CoxeterGroup(['B',3],index_set=['A','b','XX'])
sage: sage: W.index_set()
(1, 2, 3)

[stumpc5]

Sorry for adding more and more questions here: The documentation of the method roots states

These are roots in the Coxeter sense, that all have the
same norm. They are given by their coefficients in the
base of simple roots, also taken to have all the same
norm.

How is this true if the sum of the coefficients is not one? As in

sage: W = CoxeterGroup(['A',2])
sage: W.roots()
[(1, 0), (1, 1), (0, 1), (-1, 0), (-1, -1), (0, -1)]

[chapoton]

What ? Type A2 is simply laced, so the roots are just the roots in the Weyl sense..

[tscrim]

I am working on trying to fix the norm index set issue, which uncovered some other bugs/isues with the relabelling. I was somewhat inclined to say that passing a Coxeter (or Cartan) type and an index set was essentially double info, but after some more thought, I think it is a nice API to support.

[stumpc5]

@chapoton: My last comment on the root lengths was too quick, please forget about it and sorry for the noise!

[nthiery]

Replying to stumpc5:

Sorry for adding more and more questions here: The documentation of the method roots states

These are roots in the Coxeter sense, that all have the
same norm. They are given by their coefficients in the
base of simple roots, also taken to have all the same
norm.

How is this true if the sum of the coefficients is not one? As in

sage: W = CoxeterGroup(['A',2])
sage: W.roots()
[(1, 0), (1, 1), (0, 1), (-1, 0), (-1, -1), (0, -1)]

Isn't this just that the basis of the simple roots is not orthonormal? So one can't read of the norm of vectors expressed there right away.

[nthiery]

Oops, I was too quick and did not see your last comment :-)

[tscrim]

Here is a fix for relabelling issues that I came across. Although I think this might be better on a separate ticket.

@darij the previous test for checking for relabelled types gave false negatives. Consider F₄ under cyclic shift and under interchanging 1 and 3. These are the same type and our relabelling check does not distinguish between them (nor can any algorithm).

How do we want to handle Coxeter vs Dynkin classification of the affine types or the general case? I'm guessing for the affine types, we just use the untwisted types. Do we even want to consider the general case at this point?

---

New commits:

​d86d0ab

Improving support for relabelled Coxeter types.

[darij]

Oh gosh, I have literally no idea about anything beyond the classical types. Is this a bug in the algorithm I wrote? I thought very little of that algorithm is still in Sage?

[tscrim]

Replying to darij:

Oh gosh, I have literally no idea about anything beyond the classical types. Is this a bug in the algorithm I wrote? I thought very little of that algorithm is still in Sage?

Sorry, I meant the B/C issue in the ticket description.

[darij]

Oh, that!

I have to admit I don't know what the current recognition code is doing (the path-dependent output suggests some caching is going on), but my original code in #16630 never outputted a C_n. Maybe we should do the same?

[tscrim]

The B/C issue isn't so much having to do with type recognition (which won't result in a C_n), but instead what to do when we do things like CoxeterType(['C', 5]).