marked Dynkin diagrams

[vit-tucek]

This patch adds marked Dynkin diagrams and marked Cartan types. See #15948 comment:18 for details.

This convenient notation is used quite often in a certain subbranch of differential geometry, see e.g. http://arxiv.org/abs/1303.1307, and in Lie superalgebras, where markings denote the parity  of indices.

Moreover, there are two small bugfixes:

1. Documentation is misleading about our convention for arrows in Dynkin diagrams. We do follow Bourbaki convention for graphics (which is apparently the same as in Kac), but not the convention for the underlying Cartan matrix.
2. Dynkin diagrams for D and E series contain a special character in the node name of tikzpicture which TeX doesn't like.

Depends on #16380

CC: @nthiery @dwbump

Component: combinatorics

Author: Vít Tuček, Travis Scrimshaw

Branch/Commit: bf5e867

Reviewer: Travis Scrimshaw, Vít Tuček

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

[vit-tucek]

Branch: u/vittucek/ticket/15948

[sagetrac-git]

Commit: bf72707

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5da4183	Fix coding style in type A
d872d16	Node labels and crossed nodes for type B
356dde0	Bugfix for type B
56a74d5	Node labels and crossed nodes for type C
3a2d0cd	Node labels and crossed nodes for type D (plus nicer diagram)
7898620	Node labels and crossed nodes for type E
685addb	Node labels and crossed nodes for type F
bf72707	Node labels and crossed nodes for type G

[tscrim]

comment:4

I believe it is useful to have the ability to cross out particular nodes for Dynkin diagrams (I believe the same/similar convention is used for Lie superalgebras to denote even/odd indices).

However I think the node_label is redundant to the label and you are assuming your indexing set is 1, 2, ..., n, often which it is not. Similarly, I'm planning to make Dynkin diagrams more immutable (#15739), so I'd rather have it return a new DynkinDiagram when changing the crossed out nodes. One last point from a quick look-through, for comparisons with None you should do:

if x is None:
    pass

if x is not None:
    pass

I'll check against Kac tonight. Dan and Nicolas might have some more comments as well.

Best,

Travis

---

Last 10 new commits:

95ae5db	Add set_node_labels and set_crossed_nodes to DynkinDiagram
05b1b19	Node labels and crossed nodes for type A
5da4183	Fix coding style in type A
d872d16	Node labels and crossed nodes for type B
356dde0	Bugfix for type B
56a74d5	Node labels and crossed nodes for type C
3a2d0cd	Node labels and crossed nodes for type D (plus nicer diagram)
7898620	Node labels and crossed nodes for type E
685addb	Node labels and crossed nodes for type F
bf72707	Node labels and crossed nodes for type G

[nthiery]

comment:6

Hi Vít!

Thanks for your work on this. I agree with Travis. Furthermore the current implementation introduces quite some duplication, inside the type-specific latex methods and inbetween them. I guess this duplication could be avoided by factoring out a method, say _latex_node(node, x,y) that would handle the writing of the latex string for the node (label, crossing out, ...), and then make the type-specific latex methods use it. What do you think?

Cheers,
Nicolas

[vit-tucek]

comment:7

Replying to @tscrim:

I believe it is useful to have the ability to cross out particular nodes for Dynkin diagrams (I believe the same/similar convention is used for Lie superalgebras to denote even/odd indices).

I'm glad to hear that.

However I think the node_label is redundant to the label and you are assuming your indexing set is 1, 2, ..., n, often which it is not. Similarly, I'm planning to make Dynkin diagrams more immutable (#15739), so I'd rather have it return a new DynkinDiagram when changing the crossed out nodes. One last point from a quick look-through, for comparisons with None you should do:

if x is None:
    pass

if x is not None:
    pass

The labels which are implemented so far are intended for people who doesn't want to use Bourbaki convention. I think, this feature is not very well documented. My labels are purely a decoration of nodes, which can be used i.e. to denote a homogeneous vector bundle over $G/P$. So I guess the correct thing to do here is to change node_labels[i] to node_labels[label(i)], right?

As for immutability issue, will it be OK, if I just add crossed_nodes and node_labels to the constructor and get rid of the setters?

I'll check against Kac tonight. Dan and Nicolas might have some more comments as well.

Best,

Travis

[vit-tucek]

comment:8

Replying to @nthiery:

Hi Vít!

Thanks for your work on this. I agree with Travis. Furthermore the current implementation introduces quite some duplication, inside the type-specific latex methods and inbetween them. I guess this duplication could be avoided by factoring out a method, say _latex_node(node, x,y) that would handle the writing of the latex string for the node (label, crossing out, ...), and then make the type-specific latex methods use it. What do you think?

Cheers,
Nicolas

The duplication was always there. I just made it more apparent. ;) I myself thought about creating such a method when I was coding type E. I'll make that change now.

[sagetrac-git]

Changed commit from bf72707 to 454c0ac

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

454c0ac

Refactor node drawing

[tscrim]

comment:10

Replying to @vit-tucek:

The labels which are implemented so far are intended for people who doesn't want to use Bourbaki convention. I think, this feature is not very well documented. My labels are purely a decoration of nodes, which can be used i.e. to denote a homogeneous vector bundle over $G/P$. So I guess the correct thing to do here is to change node_labels[i] to node_labels[label(i)], right?

As for immutability issue, will it be OK, if I just add crossed_nodes and node_labels to the constructor and get rid of the setters?

If you feel the label is not well documented, then you should document it better. However the best thing to do would be to override the Dynkin diagram's relabel as

def relabel(self, relabeling):
    return DynkinDiagram(self._cartan_type.relabel(relabeling))

This would result in:

sage: D = DynkinDiagram(['A',4,1])
sage: DL = DynkinDiagram(D._cartan_type.relabel([2,-1,-2,-3,4])) # This would be D.relabel([2,-1,-2,-3,4])
sage: DL
2
O-----------+
|           |
|           |
O---O---O---O
-1   -2   -3   4
A4~ relabelled by {0: 2, 1: -1, 2: -2, 3: -3, 4: 4}
sage: latex(_)
\begin{tikzpicture}[scale=0.5]
\draw (-1,0) node[anchor=east] {$A_{4}^{(1)} \text{ relabelled by } \left\{0 : 2, 1 : -1, 2 : -2, 3 : -3, 4 : 4\right\}$};
\draw (0 cm,0) -- (6 cm,0);
\draw (0 cm,0) -- (3.0 cm, 1.2 cm);
\draw (3.0 cm, 1.2 cm) -- (6 cm, 0);
\draw[fill=white] (0 cm, 0) circle (.25cm) node[below=4pt]{$-1$};
\draw[fill=white] (2 cm, 0) circle (.25cm) node[below=4pt]{$-2$};
\draw[fill=white] (4 cm, 0) circle (.25cm) node[below=4pt]{$-3$};
\draw[fill=white] (6 cm, 0) circle (.25cm) node[below=4pt]{$4$};
\draw[fill=white] (3.0 cm, 1.2 cm) circle (.25cm) node[anchor=south east]{$2$};
\end{tikzpicture}

I agree that we should add the following semantic to CartanType:

sage: CartanType(['A',2], labels=[-1,-2])

(or perhaps label or labeling or...) and for crossed_nodes. Yet we should also have an additional method which allows us to set the crossed nodes.

I feel like we should add type_crossed.py which keeps/prints this data and uses the same mechanic that the relabeled Cartan types use. Nicolas, do you agree?

Furthermore, I don't like the current state of your printing method. Your iteration of the string is wrong because your assuming your labeling is nice (i.e. [0, 1, ..., k]). However that is somewhat moot because I think you should only have one method for printing the individual nodes, as per Nicolas' suggestion, because it is overkill (it's basically just a for loop).

Thanks for your work on this,

Travis

[vit-tucek]

comment:11

Replying to @tscrim:

Replying to @vit-tucek:

The labels which are implemented so far are intended for people who doesn't want to use Bourbaki convention. I think, this feature is not very well documented. My labels are purely a decoration of nodes, which can be used i.e. to denote a homogeneous vector bundle over $G/P$. So I guess the correct thing to do here is to change node_labels[i] to node_labels[label(i)], right?

As for immutability issue, will it be OK, if I just add crossed_nodes and node_labels to the constructor and get rid of the setters?

If you feel the label is not well documented, then you should document it better. However the best thing to do would be to override the Dynkin diagram's relabel as

def relabel(self, relabeling):
    return DynkinDiagram(self._cartan_type.relabel(relabeling))

This would result in:

sage: D = DynkinDiagram(['A',4,1])
sage: DL = DynkinDiagram(D._cartan_type.relabel([2,-1,-2,-3,4])) # This would be D.relabel([2,-1,-2,-3,4])
sage: DL
2
O-----------+
|           |
|           |
O---O---O---O
-1   -2   -3   4
A4~ relabelled by {0: 2, 1: -1, 2: -2, 3: -3, 4: 4}
sage: latex(_)
\begin{tikzpicture}[scale=0.5]
\draw (-1,0) node[anchor=east] {$A_{4}^{(1)} \text{ relabelled by } \left\{0 : 2, 1 : -1, 2 : -2, 3 : -3, 4 : 4\right\}$};
\draw (0 cm,0) -- (6 cm,0);
\draw (0 cm,0) -- (3.0 cm, 1.2 cm);
\draw (3.0 cm, 1.2 cm) -- (6 cm, 0);
\draw[fill=white] (0 cm, 0) circle (.25cm) node[below=4pt]{$-1$};
\draw[fill=white] (2 cm, 0) circle (.25cm) node[below=4pt]{$-2$};
\draw[fill=white] (4 cm, 0) circle (.25cm) node[below=4pt]{$-3$};
\draw[fill=white] (6 cm, 0) circle (.25cm) node[below=4pt]{$4$};
\draw[fill=white] (3.0 cm, 1.2 cm) circle (.25cm) node[anchor=south east]{$2$};
\end{tikzpicture}

I agree that we should add the following semantic to CartanType:

sage: CartanType(['A',2], labels=[-1,-2])

(or perhaps label or labeling or...) and for crossed_nodes. Yet we should also have an additional method which allows us to set the crossed nodes.

There are two problems. First that I do not understand current labeling mechanism properly (code nor use cases -- does anybode use label at all?) and second that the semantics here are really different. My node_labels represent some other object that has a priori nothing to do with how we label the basis of our Cartan algebra. In reality these node_labels denote a highest weight of the Levi part of a standard parabolic subalgebra and thus it should really be a mapping that assigns natural numbers to labels. So perhaps node_labels should really be a dictionary with keys label(i) for i in self.index_set() What about this?

def set_node_labels(self, node_labels):
    if isinstance(node_labels, list):
        self.node_labels = {i : node_labels[label(i)-1] for i in self.index_set()}
    else:
         self.node_labels = node_labels

I feel like we should add type_crossed.py which keeps/prints this data and uses the same mechanic that the relabeled Cartan types use. Nicolas, do you agree?

As with label I am not sure what is the use case here. What is wrong with CartanType having labels, node_labels and crossed out nodes as instance variables?

Furthermore, I don't like the current state of your printing method. Your iteration of the string is wrong because your assuming your labeling is nice (i.e. [0, 1, ..., k]). However that is somewhat moot because I think you should only have one method for printing the individual nodes, as per Nicolas' suggestion, because it is overkill (it's basically just a for loop).

Did you look at my last commit? (sagemath/sagetrac-mirror@454c0ac)

Thanks for your work on this,

Travis

Thanks for feedback. ;)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2233007

BUGFIX: latex() of affine types work again

[sagetrac-git]

Changed commit from 454c0ac to 2233007

[vit-tucek]

comment:13

Replying to @sagetrac-git:

Branch pushed to git repo; I updated commit sha1. New commits:

2233007

BUGFIX: latex() of affine types work again

I don't understand why that waning gets printed twice.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

91981c1

Refactor and fix the docstrings

[sagetrac-git]

Changed commit from 2233007 to 91981c1

[vit-tucek]

comment:15

OK. I've fixed some bugs and now the patch doesn't cause any breakage and works in fulfilling my needs.

There is still some work to be done. Namely:

1. Modify repr so that it prints also node_labels and crossed nodes. (I don't see a point in doing ascii graphics; two simple prints after the current output should do just fine.)
2. Add doctests illustrating the new funcionality.
3. Get rid of setters and move thiese features to __init__ in order to helpDynkinDiagram become immutable.

Is there an interest in getting this patch into sage? Are there some remaining issues that I missed?

[tscrim]

comment:16

Yes there is, but finals week trumps Sage work. However from looking at the code, I think there is significant issues when dealing with non-standard indexing sets (which we should support).

I'm going to cannibalize your branch into a new one where I'm going to create a new class in type_marked.py for types with marked nodes and add a proper relabel to DynkinDiagram. I should have it done in an hour or so.

EDIT - So basically we want relabellings and markings to act as decorator classes (as per the design pattern). This will take some (moderate) refactoring, but it will simplify the resulting code and make it easier for similar future additions.

[vit-tucek]

comment:17

Replying to @tscrim:

Yes there is, but finals week trumps Sage work. However from looking at the code, I think there is significant issues when dealing with non-standard indexing sets (which we should support).

Would it help to refactor node_labelsandcrossed_nodes` into dictionaries as I suggested in comment 11?

I'm going to cannibalize your branch into a new one where I'm going to create a new class in type_marked.py for types with marked nodes and add a proper relabel to DynkinDiagram. I should have it done in an hour or so.

EDIT - So basically we want relabellings and markings to act as decorator classes (as per the design pattern). This will take some (moderate) refactoring, but it will simplify the resulting code and make it easier for similar future additions.

Great. Thank you. I am just not sure how do we accomplish crossed nodes and weight labels at the same time. Multiple inheritance?

By the way, last week I've stumbled upon some articles about nilpotent orbits where they use Dynkin diagrams with labels and call them Weighted Dynking diagrams. So maybe use WeightedCartanType and WeightedDynkinDiagram for the guys with labels and MarkedCartanType & MarkedDynkinDiagram for crossed nodes? I can imagine that someone would want to use different markings than crosses which would amount to another round of digging into the TikZ documentation and parameter tweaking in all those _latex_... methods.

[tscrim]

comment:18

Okay, done with the refactor and creating the type_marked. I couldn't get your latex to work, so I just implemented a custom help for the marks (cross outs). It's now setup so it's easy enough to add additional functionality if anyone wants it.

I've also done some fixing up of the way we print the Dynkin diagram ascii art, so with labels up to length 3 (almost 4 really), it looks nice. I refactored type_dual and type_relabeled to inherit from a common class CartanType_decorator which acts as a decorator class and redirects most methods to the base Cartan type. I've set the (implicit) order of the decorators as

dual <- relabelled <- marked

where the first one was what was there previously. I also gave a relabel method to Dynkin diagrams and Cartan matrices. I think that's all, but I might be forgetting something. If we're happy with my changes, then it's a positive review.

---

New commits:

c655d51	Implemented marked Cartan types and refactored common code.
80684be	Fixed last doctests and added to full coverage.
612db21	Fixed last failing doctest.

[tscrim]

Changed author from Vít Tuček to Vít Tuček, Travis Scrimshaw

[tscrim]

Changed branch from u/vittucek/ticket/15948 to public/combinat/root_systems/marked_types-15948

[tscrim]

Changed commit from 91981c1 to 612db21

[vbraun]

comment:33

Various doctests fail...

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

05aa053

Implemented basic_untwisted for marked affine types

[sagetrac-git]

Changed commit from da0fc02 to 05aa053

[tscrim]

comment:35

I'm taking care of this - the non-symmetric Macdonalds are strangely sensitive to the class heirarchy.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

674fabf	Merge branch 'public/combinat/root_systems/marked_types-15948' of trac.sagemath.org:sage into public/combinat/root_systems/marked_types-15948
17e64c5	Merge branch 'u/vbraun/improve_startup_time_of_libgap' of trac.sagemath.org:sage into public/combinat/root_systems/marked_types-15948
7ce8285	Added some better doctests and fixed type_marked ambient space.
66ad2bb	Removed type() from decorator which fixes tests.
1cfe9b8	Merge branch 'public/combinat/root_systems/marked_types-15948' of trac.sagemath.org:sage into public/combinat/root_systems/marked_types-15948

[sagetrac-git]

Changed commit from 05aa053 to 1cfe9b8

[tscrim]

Dependencies: #16380

[tscrim]

comment:37

Fixed - I had accidentally changed the behavior of .type() for dual types. I also merged in #16380 in order to speed up testing. I also fixed an issue with the ambient space for marked Cartan types and implemented the basic_untwisted. It needs another look-over.

[jdemeyer]

comment:39

I know you didn't introduce this bug, but could you by chance fix this to raise a proper exception?

sage: CartanType(['H',3]).dual()
...
AssertionError: 

(note: I don't really care about this ticket, I just hate it when people abuse assert)

[tscrim]

comment:40

Replying to @jdemeyer:

I know you didn't introduce this bug, but could you by chance fix this to raise a proper exception?

sage: CartanType(['H',3]).dual()
...
AssertionError: 

(note: I don't really care about this ticket, I just hate it when people abuse assert)

I've created #17084 for this and will upload a branch there later today.

[sagetrac-git]

Changed commit from 1cfe9b8 to bf5e867

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

bf5e867

Merge branch 'public/combinat/root_systems/marked_types-15948' of trac.sagemath.org:sage into public/combinat/root_systems/marked_types-15948

[tscrim]

comment:42

Rebased. Could someone do the last little bit of review of commits 7ce8285 and 66ad2bb?

[vit-tucek]

comment:43

Thanks for keeping this branch alive!

I've tried to doctest this on cloud.sagemath.org and it behaves rather strangely. The parallel doctests (e.g. ./sage -tp 12 src/sage/combinat/root_system/) run just fine but when I try to doctest a single file such as ./sage -t src/sage/combinat/root_system/cartan_type.py it spews

7 items had failures:
   1 of   2 in sage.combinat.root_system.cartan_type.CartanType_abstract._ascii_art_node
   1 of   2 in sage.combinat.root_system.cartan_type.CartanType_abstract._latex_draw_node
   1 of   2 in sage.combinat.root_system.cartan_type.CartanType_abstract.marked_nodes
   1 of   5 in sage.combinat.root_system.cartan_type.CartanType_affine._ascii_art_node
   1 of   4 in sage.combinat.root_system.cartan_type.CartanType_affine._latex_draw_node
   1 of   2 in sage.combinat.root_system.cartan_type.CartanType_crystallographic.i
   2 of   3 in sage.combinat.root_system.cartan_type.CartanType_crystallographic.index_set_bipartition
    [432 tests, 8 failures, 1.89 s]

with errors such as

    AttributeError: 'CartanType_with_superclass' object has no attribute '_ascii_art_node'

I guess I must be doing something wrong.

[tscrim]

comment:44

Hmmm...that's very strange. I tested the single files on my machine and it works okay. Unfortunately I don't know enough about how SMC does things to be able to help (which might be based on your specific config). Even stranger is that I don't think I changed anything that would cause such a failure. Since it passes in parallel, I'm tempted to say it's based on your current setup, but let me see the full output from the test.

[vit-tucek]

comment:45

Actually, it seems I've just forgotten ./ in front of sage. Sorry!

[tscrim]

comment:46

Thank you for your work on this!

[vbraun]

Changed branch from public/combinat/root_systems/marked_types-15948 to bf5e867