Opened 8 years ago

Closed 8 years ago

Last modified 11 months ago

#5794 closed enhancement (fixed)

exceptional and reducible type branching rules

Reported by: bump Owned by: bump
Priority: major Milestone: sage-4.3
Component: group theory Keywords: lie groups
Cc: sage-combinat Merged in: sage-4.3.alpha0
Authors: Daniel Bump Reviewers: Brant Jones
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by bump)

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.

Attachments (6)

trac_5794-revised.patch (71.4 KB) - added by bump 8 years ago.
trac_5794-continued.patch (23.9 KB) - added by bump 8 years ago.
trac_5794-exceptional.patch (8.9 KB) - added by bump 8 years ago.
trac_5794-more-exceptional.patch (33.2 KB) - added by bump 8 years ago.
trac_5794-reviewer-nt.patch (5.9 KB) - added by bump 8 years ago.
trac_5794-long-time-nt.patch (10.1 KB) - added by nthiery 8 years ago.
Annotates the long tests with their time, and disables one which took 160s.

Download all attachments as: .zip

Change History (40)

comment:1 Changed 8 years ago by bump

  • Cc sage-combinat added
  • Component changed from algebra to group_theory
  • Keywords lie groups added
  • Owner changed from tbd to joyner

comment:2 Changed 8 years ago by bump

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).

comment:3 Changed 8 years ago by bump

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.

comment:4 Changed 8 years ago by bump

  • Summary changed from [with patch, needs review] G2 branching rules to [with patch, needs review] G2 and F4 branching rules

comment:5 Changed 8 years ago by bump

  • Description modified (diff)

comment:6 Changed 8 years ago by bump

  • Description modified (diff)

comment:7 Changed 8 years ago by mabshoff

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

comment:8 Changed 8 years ago by bump

  • Owner changed from joyner to bump
  • Status changed from new to assigned

comment:9 Changed 8 years ago by bump

  • Description modified (diff)
  • Summary changed from [with patch, needs review] G2 and F4 branching rules to [with patch, needs review] exceptional and reducible type branching rules

Changed 8 years ago by bump

comment:10 Changed 8 years ago by bump

  • Milestone changed from sage-combinat to sage-4.0

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.

comment:11 Changed 8 years ago by bump

Here are some tests supplementing those implemented in the doctests:

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

Changed 8 years ago by bump

comment:12 Changed 8 years ago by bump

  • Description modified (diff)

comment:13 Changed 8 years ago by bump

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

Changed 8 years ago by bump

comment:14 Changed 8 years ago by bump

  • Description modified (diff)

comment:15 Changed 8 years ago by bump

  • Description modified (diff)

comment:16 Changed 8 years ago by bump

  • Description modified (diff)

Changed 8 years ago by bump

comment:17 Changed 8 years ago by bump

  • Description modified (diff)

comment:18 Changed 8 years ago by mvngu

Since I don't know the order in which patches should be applied, let alone which one to apply, I skimmed through all 4 patches. Most docstrings adhere to the ReST format, but some don't. I'm merely enforcing proper ReST formatting, not reviewing the patches.

comment:19 follow-up: Changed 8 years ago by bump

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.

comment:20 Changed 8 years ago by boothby

  • Summary changed from [with patch, needs review] exceptional and reducible type branching rules to [with patch, needs work] exceptional and reducible type branching rules

comment:21 in reply to: ↑ 19 Changed 8 years ago by mvngu

Replying to bump:

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

Changed 8 years ago by bump

comment:22 Changed 8 years ago by bump

  • Summary changed from [with patch, needs work] exceptional and reducible type branching rules to [with patch, needs review] exceptional and reducible type branching rules

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.)

comment:23 Changed 8 years ago by sage-combinat

  • Summary changed from [with patch, needs review] exceptional and reducible type branching rules to [with patch, postive review, depends on #4326] exceptional and reducible type branching rules

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

comment:24 Changed 8 years ago by mvngu

  • Authors set to Dan Bump
  • Reviewers set to Brant Jones
  • Summary changed from [with patch, postive review, depends on #4326] exceptional and reducible type branching rules to [with patch, postive review] exceptional and reducible type branching rules

This depends on #4326.

comment:25 Changed 8 years ago by nthiery

  • Summary changed from [with patch, postive review] exceptional and reducible type branching rules to [with patch, positive review] exceptional and reducible type branching rules

Changed 8 years ago by nthiery

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

comment:26 Changed 8 years ago by nthiery

  • Status changed from positive_review to needs_work

comment:27 follow-up: Changed 8 years ago by nthiery

  • Status changed from needs_work to needs_review

comment:28 in reply to: ↑ 27 Changed 8 years ago by nthiery

  • Status changed from needs_review to positive_review

Positive review from Dan on sage-combinat-devel

comment:29 Changed 8 years ago by mhansen

  • Merged in set to sage-4.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:30 Changed 8 years ago by AlexGhitza

  • Report Upstream set to N/A

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]

comment:31 Changed 8 years ago by mhansen

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

comment:32 Changed 7 years ago by mvngu

  • Summary changed from [with patch, positive review] exceptional and reducible type branching rules to exceptional and reducible type branching rules

comment:33 Changed 4 years ago by jdemeyer

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

comment:34 Changed 11 months ago by chapoton

  • Authors changed from Dan Bump to Daniel Bump
Note: See TracTickets for help on using tickets.