Add support for sub-root-systems

[fingolfin]

Discussed things with @lgoettgens and @frankluebeck today: it would be useful to have support for sub-root-system (root-sub-systems?)

Concretely, the idea would be to have something like this pseudocode:

julia> rs = root_system([(:A, 2), (:F, 4)])
Root system of rank 6
  of type A2 x F4

julia> sr = simple_roots(rs)
6-element Vector{RootSpaceElem}:
 a_1
 a_2
 a_3
 a_4
 a_5
 a_6

julia> sub_rs, emb = sub(rs, [sr[1], sr[3]])
...

where sub_rs would be a root system and emb a function sub_rs -> rs which allows effective computation of images and preimages.

CC @felix-roehrich @lgoettgens @TWiedemann

[frankluebeck]

It should also work for arbitrary subsets of roots(rs) and compute the set of simple roots of the generated subsystem.

[TWiedemann]

Just to clarify: By "subsystem generated by a subset $S$ of the root system $R$" we mean "intersection of $R$ with the vector subspace spanned by $S$"? In my experience, this is what people usually mean, but I am not aware of any standard textbook reference which actually introduces what a "root subsystem" should be (maybe someone can correct me). While
Humphreys "Introduction to Lie algebras and Representatation Theory",
Humphreys "Reflection groups and Coxeter groups",
Bourbaki "Groupes et algèbres de Lie 4-6"
talk about "root subsystems" in a small number of casual remarks, they never define this notion.

I like to call subsystems in the above sense "parabolic subsystems" because their Coxeter/Dynkin diagram is always a subset of the bigger diagram. However, this is not at all standard terminology.

For those curious, the following non-equivalent notions of subsystems can be useful in certain contexts:

A subset $S$ of a root system $R$ in a Euclidean space $V$ is called...
(a) subsystem if it is itself a root system. That is, $S$ is invariant under the reflection $\sigma_\alpha$ for all $\alpha \in S$.
(b) crystallographically closed subsystem if it is a subsystem such that the crystallographic root interval $[\alpha, \beta] := R \cap \{ a\alpha+b\beta \mid 0<a, b \in \mathbb{Z}\}$ is contained in $S$ for all non-proportional $\alpha, \beta \in S$.
(c) closed subsystem if it is a subsystem such that the root interval $[\alpha, \beta] := R \cap \{ a\alpha+b\beta \mid 0<a, b \in \mathbb{R} \}$ is contained in $S$ for all non-proportional $\alpha, \beta \in S$.

Then "parabolic" implies "closed" implies "crystallographically closed" implies "subsystem". (b) and (c) are interesting in the context of root groups with commutator relations (but probably not that interesting outside of that; and certainly no one means (b) or (c) when they simply say "root subsystem"). (a) is interesting because it is the most general definition one can think of, and because it induces an embedding of the corresponding Weyl groups. I remember that I once talked to someone who used "root subsystem" in the sense of (a).

Examples: $D_n \subset C_n$ and $A_1^n \subset B_n$ are subsystems that are not crystallographically closed. $D_n \subset B_n$ is a crystallographically closed subsystem that is not closed. The set of long roots in $BC_1$ is a closed subsystem of $BC_1$ that is not parabolic.

[fingolfin]

Thank @TWiedemann that's some excellent points. Perhaps @frankluebeck can clarify which definition of sub-system he in mind?

[frankluebeck]

Thanks to @TWiedemann for this precise description.

What I had in mind with "subsystem generated by a subset S of the root system R " is definition (a).

So, an algorithm could be to compute the orbits of the given roots under the group generated by the reflections along the given roots. There is a unique set of simple roots for this subsystem which is contained in the positive roots of $R$.

Of course, computing the closure of a subsystem (the intersection of its $\mathbb{Q}$-span with $R$) is also an interesting functionality, which gives the smallest parabolic subsystem containing $S$.

[fingolfin]

Very nice, thank you all.

@TWiedemann would you be interested in working on this?

[TWiedemann]

Sure, I can do that.

My thoughts (where R is the big root system):

1. Compute the set S of the roots in the root subsystem in the way suggested by @frankluebeck
2. Compute the unique set of simple roots in S consisting of positive roots w.r.t R. This is less straightforward. I think the following approach is reasonable:

sub_basis = []
A = S \cap positive_roots(R) # Set of roots in S not contained in the positive span of basis
while not is_empty(A)
  r = Root in A of lowest height (w.r.t simple_roots(R))
  Append r to sub_basis
  Remove all roots from A which are (necessarily positive) linear combinations of the roots in sub_basis
end

Then I think sub_basis is a set of simple roots of S.

3. Compute the Cartan matrix sub_cm of S from basis. This is straightforward. Now we can define sub_rs = root_system(sub_cm).
4. Define the embedding emb from sub_rs to R which sends simple_roots(sub_rs) to sub_basis. Mathematically, this is straightforward.

I think it would be nice if emb in 4. were defined on the whole root space of sub_rs (with its image contained in the root space of R), but I think the root space is currently not explicitly available in Oscar as a domain (I can only find RootSpaceElem but not the whole space itself)? Maybe RootSystem should store its root space as a vector/matrix space?

In a similar vein, I am not sure if/how the standard linear algebra functionality can/should be applied in 2. to compute the span of sub_basis. It seems to me that something like sub(matrix_space(QQ, 1, rank(R)), [coefficients(a) for a in sub_basis]) would work (did not test this), but the doc of coefficients warns me that "The return type may not be relied on", and it does not seem right to explicitly construct the matrix space (which is, in fact, the root space in this context).

Bottom line: It would be nice to do linear algebra with root space elements, but right now coefficients seems to be the only way to do this, and the documentation suggests that I shouldn't.

[frankluebeck]

For step 2.: You only need the big root system R to find the set of positive roots S^+ in S for the same ordering as used for R (the intersection of R^\+ with S; alternatively you can use a vector which defines R^+).

To find the set of simple roots in S^+ you do not need R or the roots written with respect to a specific basis: r in S^+ is simple if and only if the reflection along r leaves the set S^+ \ {r} invariant (that is, r is the only positive root mapped to a negative one by this reflection).

In CHEVIE we mostly represent elements in the Weyl group by its permutation on the set of roots. In this setup, both steps 1. and 2. are very easy and efficient.

Yes, when you have the set of simple roots you can compute the corresponding Cartan matrix. I don't know what the policy in your setup is. Maybe you then want to determine the type of the subsystem S, and maybe you then want to reorder the set of simple roots according to some convention.

In applications it is useful to know the embedding of S into R for the whole set.

[fingolfin]

@TWiedemann regarding technical details, I suggest you talk with @lgoettgens on gather or zoom at a time convenient for both of you

[TWiedemann]

To find the set of simple roots in S^+ you do not need R or the roots written with respect to a specific basis: r in S^+ is simple if and only if the reflection along r leaves the set S^+ \ {r} invariant (that is, r is the only positive root mapped to a negative one by this reflection).

Ah, I see. That would also work and only uses functionality that we certainly have. Thanks!

In CHEVIE we mostly represent elements in the Weyl group by its permutation on the set of roots. In this setup, both steps 1. and 2. are very easy and efficient.

Yes, when you have the set of simple roots you can compute the corresponding Cartan matrix. I don't know what the policy in your setup is. Maybe you then want to determine the type of the subsystem S, and maybe you then want to reorder the set of simple roots according to some convention.

In applications it is useful to know the embedding of S into R for the whole set.

In the OSCAR setup, the Cartan matrix (or the type) is the ingredient that has to be provided to define a new root system. Hence we first compute the Cartan matrix of S (as a subset of R), then create a brand new root system sub_rs from this Cartan matrix and then define an embedding which identifies the roots of sub_rs with the subset S of R.

I had not yet given thought to the ordering of the simple roots of the subsystem. OSCAR supports arbitrary orderings of the root base, so we can in principle do what we want. In the case that the root base of the subsystem is a subset of the large root base, it would make sense to keep the order of the large root base. However, it can also happen that the two root bases do not intersect, and then it would make sense to choose a "canonical" ordering on the root base of the subsystem. In general there is no obvious ordering to choose.