Various ideas for algebraic Lie theory

[fingolfin]

We discussed a lot of things yesterday. Ideally I'd write separate issues for each, but since I don't have the time, I am just going to collect a bunch of things here and we can later split off additional issues if needed.

• add "root data" as a data type

  • (a refinement of root systems and Cartan matrices)
  • can e.g. be represented by a factorized Cartan matrix (ideally via integral factors)
  • relevant Magma documentation: https://magma.maths.usyd.edu.au/magma/handbook/root_data
  • Max has some relevant GAP code somewhere

• alternative multiplication for Weyl group elements?

  • our current approach to always store words in shortlex normal form does not have best performance
  • one can represent elements also via automate which can speed up things
  • see e.g. Bill Casselman's course notes: https://personal.math.ubc.ca/~cass/coxeter/crm2.html
  • record holder in many ways was/is code by Fokko du Cloux (RIP), see http://www.liegroups.org/coxeter/coxeter3/english/
  • perhaps use lazy normal forms?
  • could also internally use different strategies for different types (e.g. perm rep for A_n)? Though this would make the code a lot more complicated

• Further possibly relevant references:

  • Bring & Howlett 93, "A finiteness property an an automatic structure for Coxeter groups", https://doi.org/10.1007/BF01445101
  • Casselman 94, Machine calculations in Weyl groups, https://doi.org/10.1007/BF01231558
  • Casselman 2002, Computation in Coxeter Groups—I. Multiplication, https://doi.org/10.37236/12156
  • Casselman Computation in Coxeter groups II. Constructing minimal roots https://doi.org/10.1090/S1088-4165-07-00319-6
    (see also https://arxiv.org/abs/math/0209020)
  • Bill Casselman course notes: https://personal.math.ubc.ca/~cass/coxeter/crm2.html#top
  • http://www.liegroups.org/AIM_E8/technicaldetails.html
  • ChevLie von Meinolf Geck: https://msp.org/jsag/2020/10-1/jsag-v10-n1-p05-p.pdf

• feature request: a function taking w::WeylGroupElem, i::Int (or so?) which tells you if w*s_i is shorter (resp. longer) than w

  • trivial to implement using e.g explain_rmul
  • main question is: what should this be called?

• feature request: a function which takes W::WeylGroup, N::Int and returns all reduced words of length N

• support for affine Weyl groups:

  • representation as action of the finite Weyl group on a lattice is of interest

• Max of course would like Kac-Moody root data/systems/WeylGroups/LieAlgebras 😂

• many things that are or used to be in libraries can be recomputed "on the fly" these days.
  The one valuable things libraries of still have is that they label things in a way compatible
  with major text books or papers, which often is very helpful

  • thus it would be good to provide labels for things which match what is used in the literature
  • e.g. allowing to identify partitions with certain group elements in the A_n case

• provide WJ, emb = parabolic_closure([w_1, ..., w_k]) which computes the parabolic
  closure of the given elements, and return a new Weyl group isomorphic to that, with an injective
  homomorphism emb from WJ into W

• improve iteration over E6, E7, E8

  • compare to performance of an isomorphic PermGroup
  • see these snippets which iterate over $W(E_8)$ in six different ways

  julia> W = weyl_group(:E,7)
  Weyl group
    of root system of rank 7
      of type E7
  
  julia> order(W)
  2903040
  
  julia> i= 0; @time for _ in W i += 1 end
    9.202553 seconds (103.32 M allocations: 4.982 GiB, 36.79% gc time)
  
  julia> G = PermGroup(W)
  Permutation group of degree 126 and order 2903040
  
  julia> i= 0; @time for _ in G i += 1 end
    2.677503 seconds (14.80 M allocations: 1.078 GiB, 13.62% gc time)
  
  julia> i= 0; @time for _ in GapObj(G) i += 1 end
    2.440968 seconds (11.89 M allocations: 1014.752 MiB, 8.85% gc time)
  
  julia> myfoo(x) = begin i=0; for _ in x i += 1 end ; nothing ; end;
  
  julia> @time myfoo(W)
    7.239804 seconds (91.71 M allocations: 4.636 GiB, 24.13% gc time)
  
  julia> @time myfoo(G)
    2.377275 seconds (6.08 M allocations: 881.869 MiB, 13.48% gc time)
  
  julia> @time myfoo(GapObj(G))
    2.312901 seconds (8.99 M allocations: 970.462 MiB, 9.12% gc time)
  

  • Optimize some Lie theory code #4655 already improves this a lot, what's still missing is a way to get a non-copying Weyl group elem iterator (it already exists as WeylIteratorNoCopy, but you cannot easily get it as a user).