exceptional and reducible type branching rules

[dwbump]

Patch summary for trac_5794.revised:

- new branching rules, including exceptional and reducible types
- all new rules have tests but slower F4 tests are # long time
- bugfix: reducible root system methods simple_roots etc. return families
- Cartan Types B, C and D allow low rank cases such as D2, B1 and C1
- WeylCharacterRings: new style="coroots" option gives output similar to published tables
- WeylCharacterRings: methods for rank, simple_roots etc.
- doc revision in weyl_characters.py

This patch contains #5831. If this patch is merged, that ticket may be closed.

The patch trac_5794-continued.patch goes on top of trac_5794-revised.patch. Together, the two patches
give complete coverage of branching rules from
classical root systems to maximal subgroups.

Highlights of the second patch:

New WeylCharacter methods is_reducible and frobenius_schur_indicator
Revised tensor rule handles all classical Cartan types
powerful new branching_rule_from_plethysm handles unusual cases
doc revision

The file at
http://sporadic.stanford.edu/bump/branch.sage contains additional tests demonstrating every branching rule in Patera and McKay's book of tables for Cartan types A,B,C,D. This verifies the completeness of the patch for nonexceptional types.

The patch trac_5794-exceptional.patch adds some more F4 and E6 branching rules. It also adds dynkin_diagram and extended_dynkin_diagram methods to WeylCharacterRings. It goes on top of the other two patches.

The last patch trac_5794-more-exceptional.patch adds E6, E7 and E8 branching rules.

CC: @sagetrac-sage-combinat

Component: group theory

Keywords: lie groups

Author: Daniel Bump

Reviewer: Brant Jones

Merged: sage-4.3.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/5794

[dwbump]

Changed keywords from none to lie groups

[dwbump]

comment:2

The last change indicates that I changed the owner from tbd to joyner. I don't
remember doing that, and I don't see how I could have done it accidentally.
Maybe someone else changed the owner, presumably wdj or mabshoff, but then
trac shouldn't show that I did. I am puzzled by this.

Here are some comments about the G2=>A1 Levi branching rule. There is a
branching rule G2=>A1xA1 (rule = "extended"). This is not implemented yet.
Currently Weyl character rings are broke for reducible root systems. (I have a
patch for that but it is not posted on trac yet.) I intend to implement branching
to reducible root systems but first I want to do a few exceptional branching
rules first before tackling the many cases of branching to reducible root systems.

So G2=>A1xA1 will come in a later patch but it is relevant here so I will discuss it.

In the branching rule G2=>A1xA1, the second A1 is almost but not
quite the A1 in the G2=>A1 Levi branching rule. (The short root A1.) So it might
seem that one should implement G2=>A1xA1 and then you would get the G2=>A1
(rule = "levi") branching rule. However this is not quite true. The A1 in the G2=>A1
branching rule is GL(2) and the A1 in A1xA1 is SL(2).

[dwbump]

comment:3

I uploaded a second patch trac_5794-f4.patch which goes on top of
the first. It implements branching rules F4=>B3 (levi), F4=>C3 (levi)
and F4=>B4 (extended).

There is another extended rule F4=>C3xA1 (not implemented yet,
but hopefully to be implemented later).

In contrast with G2, for F4, both Levi branching rules are redundant
since the Levi subgroups are not maximal. They factor through branching
rules F4=>B4=>B3 and F4=>C3xA1=>C3. However I implemented them
for convenience. You can check directly that
F4(x).branch(B3,rule="levi") and
F4(x).branch(B4,rule="extended").branch(B3,rule="levi") return the
same thing for x in F4.fundamental_weights().

I compared the output for these rules against those that I could find in a book,
Patera and Sankoff, Branching rules for representations of simple Lie algebras.

[sagetrac-mabshoff]

comment:7

Hi Dan,

the change in ownership happend because you changed the component to "group_thoery". For every ticket you work on and post patches you should accept it (see the bottom left), that way ownership stays with you.

Cheers,

Michael

[dwbump]

Attachment: trac_5794-revised.patch.gz

[dwbump]

comment:10

I'm taking the liberty of changing the milestone to 4.0 in case there
is a chance of getting this merged. It is quite a substantial enhancement.

[dwbump]

comment:11

Here are some tests supplementing those implemented in the doctests:

http://sporadic.stanford.edu/bump/branch.sage

[dwbump]

comment:12

Attachment: trac_5794-continued.patch.gz

[dwbump]

comment:13

Is it possible to remove the first two patches:

trac_5794.patch
trac_5794-f4.patch

They are superceded by the other patches. I am going to be adding some
more patches to this series, and I think it would be less confusing if the
first two patches are removed. I don't think I can do this without help
from admin.

Dan

[sagetrac-mvngu]

comment:21

Replying to @dwbump:

Apply all four patches in order.

trac_5794-revised.patch
trac_5794-continued.patch
trac_5794-exceptional.patch
trac_5794-more-exceptional.patch

Most docstrings adhere to the ReST format, but some don't.

If you find nonconforming docstrings, please cite them by line number.
There is a lot of doc in these patches.

Note that I'm not qualified to review the mathematical content of the patch. However, I would like to point out that the following patches and line numbers don't conform to ReST formatting:

In trac_5794-revised.patch:

• Patching against the file sage/combinat/root_system/type_A.py, the examples section starting from line 117.
• Patching against the file sage/combinat/root_system/type_reducible.py, the examples section starting from line 249.
• Patching against the file sage/combinat/root_system/weyl_characters.py, the examples section starting from line 458, the example starting from line 1202, the examples section starting from line 1211, the example starting from line 1227, the examples section starting from line 1235, the example starting from line 1280, the example section starting from line 1299.
  In trac_5794-continued.patch:
• Patching against the file sage/combinat/root_system/weyl_characters.py, the example starting from line 1431, the example starting from line 1443, the example starting from line 1452, the example starting from line 1831, the example starting from line 1842.
  The following files are not in the reference manual. You might want to consider exposing their features by adding them to the reference manual:

1. sage/combinat/root_system/type_A.py
2. sage/combinat/root_system/type_reducible.py

[dwbump]

comment:22

Attachment: trac_5794-reviewer-nt.patch.gz

Nicolas Thiery wrote the patch trac_5794-reviewer-nt.patch.
It is in the combinat patch queue. I took the liberty of uploading
it.

It addresses at least some of the ReST complaints.

I am changing the title back to [with patch, needs review] since
apart from the issue of the ReST formatting, the patches still
needs a technical review. The following remark is addressed
to whoever does the technical review. (Brant Jones was suggested.)

The patches as posted differ slightly from the versions in the combinat queue.
The reason for the difference is that the meaning of the is_reducible
Cartan type attribute is changed by #4326. After #4326 (which preceed
these patches in the queue) the root system D2 is not reducible. See

http://groups.google.com/group/sage-combinat-devel/msg/8b3569b4e2f2b7e1?hl=en

and thread for discussion. (Note: the patch cartan_type_temporary-1.patch
mentioned in that message was qfolded shortly afterwards.)

[sagetrac-sage-combinat]

comment:23

Patch review: trac_5794

The patch author is a widely acknowledged expert in the area, having written a textbook which includes a discussion of the root systems and branching rules implemented here. Although we did not check all of the details of the algorithms, the root system code has been used by the reviewer to implement the alcove path model for crystals of Lenart and Postnikov, and the branching code has computed some verified data in type E_6. This patch implements useful mathematics and the extensive documentation includes references to relevant mathematical literature.

There are currently two warnings for the reference manual (sage -docbuild reference html); these require help from Sage developers to be fixed. The Sage library test passes, and all methods have doctests which pass.

-- Brant Jones

[sagetrac-mvngu]

Reviewer: Brant Jones

[sagetrac-mvngu]

comment:24

This depends on #4326.

[sagetrac-mvngu]

Author: Dan Bump

[nthiery]

Attachment: trac_5794-long-time-nt.patch.gz

Annotates the long tests with their time, and disables one which took 160s.

[nthiery]

comment:28

Positive review from Dan on sage-combinat-devel

[mwhansen]

Merged: sage-4.3.alpha0

[aghitza]

comment:30

Did trac_5794-long-time-nt.patch actually get merged? I don't see these changes in sage-4.3.rc0, and therefore running long doctests on weyl_characters.py still takes forever:

[ghitza@sage root_system]$ sd -t -long weyl_characters.py 
sage -t -long "devel/sage-main/sage/combinat/root_system/weyl_characters.py"
         [242.2 s]

[mwhansen]

comment:31

Thanks for picking that up. I've merged that one patch in 4.3.rc1.

[jdemeyer]

comment:33

I seems the patches here on Trac are not the ones which were actually merged 4 years ago, which was discovered in #15279.

[fchapoton]

Changed author from Dan Bump to Daniel Bump