Implementation of quiver mutation type

[stumpc5]

The patch implements multiple mutation types of quivers. This classification contains in particular all finite and affine types of generalized Cartan types.

The patch contains multiple examples.

sage: mt = QuiverMutationType(['A',3]); mt
['A', 3]

Apply only

• trac_10527-quiver_mutation_type.patch

CC: @sagetrac-gmusiker @robertwb

Component: combinatorics

Keywords: quiver mutation type days38

Author: Christian Stump

Reviewer: Hugh Thomas

Merged: sage-5.5.beta0

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

[stumpc5]

Dependencies: #10349

[fchapoton]

comment:3

This one contains "attach" statements, which seems very strange and probably causes many problems.

The header is also bad.

And QuiverMutationType is not recognized as a global command.

[fchapoton]

comment:4

There also remains some "hyperbolic" that should really be "elliptic".

[stumpc5]

comment:5

Replying to @fchapoton:

There also remains some "hyperbolic" that should really be "elliptic".

done!

[stumpc5]

comment:6

Replying to @fchapoton:

This one contains "attach" statements, which seems very strange and probably causes many problems.

Somehow, all my changes belonging to this patch got into the next on cluster algebras and quivers...

On my computer, everything seems to be fine after moving all these changes into this patch, and all doctests pass.

[fchapoton]

comment:9

There seems to be some "trailing whitespace" problem to be solved. This should be easy enough, I guess.

[stumpc5]

comment:10

Replying to @fchapoton:

There seems to be some "trailing whitespace" problem to be solved. This should be easy enough, I guess.

should be fixed - thanks for looking at the ticket!

[hughrthomas]

comment:12

What did you mean by:

It appears that C(M) and C(M') are isomorphic Cartan types for mutation equivalent skew-symmetrizable matrices M and M'.

A3 is mutation equivalent to an oriented cycle, whose Cartan type is affine A2. Maybe this should be removed?

(I'm at Sage Days 38, and I'm planning to get a bunch of refereeing done this week, so I'll probably have more comments....)

[hughrthomas]

comment:13

It seems that this patch and 10538 depend on each other.

sage: QuiverMutationType('X',6,2).standard_quiver()

/home/hugh/sage-5.0.rc0/local/lib/python2.7/site-packages/sage/combinat/cluster_algebra_quiver/quiver_mutation_type.pyc in standard_quiver(self)
   1439             Quiver on 12 vertices of type [ ['A', 3], ['B', 3], ['X', 6, 2] ]
   1440         """
-> 1441         from quiver import Quiver
   1442         Q = Quiver( self._digraph )
   1443         Q._mutation_type = self

ImportError: No module named quiver

I could go ahead and (try to) review both together, unless you have a better suggestion.

[stumpc5]

comment:14

Replying to @hughrthomas:

What did you mean by:

It appears that C(M) and C(M') are isomorphic Cartan types for mutation equivalent skew-symmetrizable matrices M and M'.

A3 is mutation equivalent to an oriented cycle, whose Cartan type is affine A2. Maybe this should be removed?

(I'm at Sage Days 38, and I'm planning to get a bunch of refereeing done this week, so I'll probably have more comments....)

agreed.

[stumpc5]

comment:15

Replying to @hughrthomas:

It seems that this patch and 10538 depend on each other.
I could go ahead and (try to) review both together, unless you have a better suggestion.

Hi Hugh,

If I am not mistaken, this is the only dependency of this patch on #10538. What about the following:

• we take this method off this patch and add it to the other
• you can review of this patch (I guess, we might need some time for that already)
• you can spend more time on the other patch. It would be great, if we can get it reviewed this week, but this will be far from easy...

Thanks, Christian

[hughrthomas]

comment:16

Replying to @stumpc5:

Replying to @hughrthomas:

What did you mean by:

It appears that C(M) and C(M') are isomorphic Cartan types for mutation equivalent skew-symmetrizable matrices M and M'.

A3 is mutation equivalent to an oriented cycle, whose Cartan type is affine A2. Maybe this should be removed?

(I'm at Sage Days 38, and I'm planning to get a bunch of refereeing done this week, so I'll probably have more comments....)

agreed.

Okay. I'm working on a reviewer patch, so I can take it out there.

[stumpc5]

comment:17

Replying to @hughrthomas:

Replying to @stumpc5:

Replying to @hughrthomas:

Okay. I'm working on a reviewer patch, so I can take it out there.

could you please use the patches in the combinat queue, since I am certain that they are up-to-date, while I lost track over the months if I always updated the version on the trac server.

Thanks, Christian

[hughrthomas]

comment:18

Hi Christian--

Sure, I can use the combinat patches. Is that going to fix the dependency loop? I didn't quite gather what you wanted to move into the second patch: both plot() and show() use standard_quiver().

cheers,

Hugh

[stumpc5]

comment:19

Sure, I can use the combinat patches. Is that going to fix the dependency loop? I didn't quite gather what you wanted to move into the second patch: both plot() and show() use standard_quiver().

have you already touched the files? If you give me 15min, I will remove the dependency loop and push.

[hughrthomas]

comment:113

Yay! So far as I can tell, the only complaint the patchbot is making is that we're adding new modules, but since we're importing them lazily, it's not really a problem.

I had never reviewed Gregg's final patch. I've now looked at it and I'm afraid I have some minor issues with it. (And testing it has led to detecting some other non-optimal behaviour.)

Gregg, you said you wanted to fix QuiverMutationType('C',1,1) giving a cryptic message, but in fact it still does (it still says "'CC',1,1" is not valid).

I see you changed the error message to reflect the fact that in elliptic types, twists can have 2's in them, which is better than what was there before. But they can also have 3's in them (elliptic G's).

In fact, I suggest removing the last four lines of the error message, including the elliptics, and replacing them by "For correct syntax in other types, please consult the documentation." As it stands, it looks like it's purporting to be some kind of complete list, but in fact not every type is well-described (e.g., GR, which takes a single additional parameter which is a tuple/list blah, blah). In general, I don't think the goal of an error message should be to replace the documentation.

I still think it's pointless to include AE. If you want it, it definitely shouldn't have a twist of 3. And I think the documentation should explain the input format.

I'm not sure why we're allowing QuiverMutationType('GR',(n,k)) as well as (k,n). The Grassmannian of 3-planes in 2-space is just meaningless, and (in my view) it should return an error. I could be argued out of this.

QuiverMutationType('D',3,2) works, but QuiverMutationType('A',3,2) doesn't. But A_3 and D_3 are the same. I think both should yield what D,3,2 does now (namely, C,2,-1). There has to be some notation for it, and it's pretty peculiar to require people to think of the root system as derived from D,3 rather than A,3. (The reason this makes some sense is that it fits the pattern of D,n,2, not the pattern of A,2n+1,2, but I think that's okay.)

[sagetrac-gmoose05]

comment:114

I just uploaded a new patch which takes care of the issues that Hugh raised. Thanks for that. I also made one or two other changes that will be useful for patches 10538 going forward. Please see my comments below.

Replying to @hughrthomas:

Yay! So far as I can tell, the only complaint the patchbot is making is that we're adding new modules, but since we're importing them lazily, it's not really a problem.

Yay! Hopefully the patchbot will again be happy after it processes the new patch. Yes, this seems related to https://groups.google.com/forum/?fromgroups=#!searchin/sage-devel/patchbot$20plugin$20start-up$20modules/sage-devel/6LByB07Ks9c/gU1TCecUwwoJ

and yes, it is true that we import (although lazily) modules. So I agree that this plug-in is not an issue. To double-check, I just CC'ed Robert Bradshaw (who had also mentioned the lazy_import to us for #10538).

I had never reviewed Gregg's final patch. I've now looked at it and I'm afraid I have some minor issues with it. (And testing it has led to detecting some other non-optimal behaviour.)

Gregg, you said you wanted to fix QuiverMutationType('C',1,1) giving a cryptic message, but in fact it still does (it still says "'CC',1,1" is not valid).

Yes, this is fixed now. Thanks for catching that.

I see you changed the error message to reflect the fact that in elliptic types, twists can have 2's in them, which is better than what was there before. But they can also have 3's in them (elliptic G's).

In fact, I suggest removing the last four lines of the error message, including the elliptics, and replacing them by "For correct syntax in other types, please consult the documentation." As it stands, it looks like it's purporting to be some kind of complete list, but in fact not every type is well-described (e.g., GR, which takes a single additional parameter which is a tuple/list blah, blah). In general, I don't think the goal of an error message should be to replace the documentation.

Yes, you are correct I slightly changed the phrasing for Elliptic, and then followed your advice for the last three lines. Let me know if this looks okay.

I still think it's pointless to include AE. If you want it, it definitely shouldn't have a twist of 3. And I think the documentation should explain the input format.

I ensured that AE doesn't take a twist argument, updated the example, and added a comment to the documentation about the input format. I still vote to keep it, but don't feel too strongly if you and Christian want to get rid of it.

I'm not sure why we're allowing QuiverMutationType('GR',(n,k)) as well as (k,n). The Grassmannian of 3-planes in 2-space is just meaningless, and (in my view) it should return an error. I could be argued out of this.

I forget now why we allowed switching the order of k and n. Christian, do you remember? Anyway, Hugh I agree with you, and made the change. QuiverMutationType('GR',(5,2)) for instance now gives an error. But we still have QuiverMutationType('GR',(3,5)) = QuiverMutationType('GR',(2,5)).

QuiverMutationType('D',3,2) works, but QuiverMutationType('A',3,2) doesn't. But A_3 and D_3 are the same. I think both should yield what D,3,2 does now (namely, C,2,-1). There has to be some notation for it, and it's pretty peculiar to require people to think of the root system as derived from D,3 rather than A,3. (The reason this makes some sense is that it fits the pattern of D,n,2, not the pattern of A,2n+1,2, but I think that's okay.)

This was from following Kac's affine notation, which didn't allow A_3^(2).

However, coercing to ('D',3,2) might be a better choice than an error message here. Unfortunately, ('A',3,2) doesn't resemble ('A',2k+1,2) in this case, but perhaps this is okay. Christian, feel free to let us know if you have a different preference. By the way, I just ran

sage: CartanType(['A',3,2])
['B', 2, 1]^*
sage: CartanType(['D',3,2])
['C', 2, 1]^*
sage: CartanType(['A',4,2])
['BC', 2, 2]
sage: CartanType(['A',5,2])
['B', 3, 1]^*
sage: CartanType(['A',7,2])
['B', 4, 1]^*
sage: CartanType(['D',4,2])
['C', 3, 1]^*
sage: CartanType(['D',5,2])
['C', 4, 1]^*

as a sanity check, and it actually does differ from this choice. Should we make

sage: QuiverMutationType(['D',3,2])
['BB',2,1]
sage: QuiverMutationType(['A',3,2])
['CD',2,1]

instead?

[sagetrac-gmoose05]

comment:115

Also, in my most recent patch, I also did the following:

• I separated out the cases ['F', 4, [1,2]] and ['F', 4, [2,1]], as well as
  ['G', 4, [1,3]] and ['G', 4, [3,1]] in the class QuiverMutationType_Irreducible.

This is in preparation for changes I will be making to the ClusterQuiver class. These specific changes used to be in the ticket #10538, see item (8a) of #10538 comment:18, but since I was changing this patch anyway, this ticket was a more natural place to have these changes.

Once we have finalized this ticket, I will update #10538 accordingly to fix the impending patch conflict.

• I also added the coercions ['F',4,[2,1]] -> ['F',4,[1,2]] and ['G',2,[3,1]] -> ['G',2,[1,3]] up front in the Mutation Type Casting list to make this separation clearer. The point is that we can think of these four cases each as different quivers, even though the two quivers of type F listed here are mutation-equivalent, and same for the elliptic G quivers listed here.

Similarly, the values ['GR', [2,n]] and ['TR',1], ['TR',2] are now allowed as inputs to QuiverMutationType_Irreducible

• See also the discussion in comments 23-25 of Implementation of the class ClusterQuiver #10538. I also now allow the user to type in

sage: QuiverMutationType(['A',[0,7],1])
['D',7]

This will later allow the user to construct the cyclic quiver on n-vertices by specifying 0 clockwise arrows in a quiver of "type affine A". Note that such a quiver is actually of finite D type, not affine A.

[robertwb]

comment:116

Lazily importing * is preferred, as it avoids stat'ing a new directory and loading two new files (init.py and all.py). All this filesystem activity seems to be one of the primary reasons for slow Sage startup time (perhaps even more so than the execution of the .py files themselves) and if we're going to try to fix that it's important to be careful about what continues to be added.

That being said, I have know idea what's up with volker-desktop.stp.dias.ie . It's as if the file existed but was incomplete/empty. Let's see if that continues to be a problem.

[hughrthomas]

comment:117

Replying to @sagetrac-gmoose05:

I just uploaded a new patch which takes care of the issues that Hugh raised. Thanks for that.

Thanks!

I also made one or two other changes that will be useful for patches 10538 going forward. Please see my comments below.

It might actually be better to make such changes part of 10538 (I mean, in the cases that they aren't corrections of actual errors in 10527). This way, 10527 gets held up while we debate details which it might make more sense to resolve in the context of where you want to use them. (And perhaps with a more sympathetic referee:).)

On the whole, I don't think it's a good idea to introduce (A,(m,0), 1) as a synonym for D,m. It seems to me that introducing synonyms like this is a process which could go on for ever. There are also wierd corner cases. I think the only reasonable interpretation of A,(1,0),1 is a loop, and of A,(2,0),1 is a 2-cycle. So they just are not quiver mutation types. It also seems more confusing than beneficial to me that the quiver which results is not the quiver which you actually named.

Yes, you are correct I slightly changed the phrasing for Elliptic, and then followed your advice for the last three lines. Let me know if this looks okay.

Yes, it's fine.

I ensured that AE doesn't take a twist argument, updated the example, and added a comment to the documentation about the input format. I still vote to keep it, but don't feel too strongly if you and Christian want to get rid of it.

I'm not really arguing against it at this point.

I forget now why we allowed switching the order of k and n. Christian, do you remember? Anyway, Hugh I agree with you, and made the change. QuiverMutationType('GR',(5,2)) for instance now gives an error. But we still have QuiverMutationType('GR',(3,5)) = QuiverMutationType('GR',(2,5)).

I agree that (2,5) and (3,5) should be the same, certainly!

QuiverMutationType('D',3,2) works, but QuiverMutationType('A',3,2) doesn't. But A_3 and D_3 are the same. I think both should yield what D,3,2 does now (namely, C,2,-1). There has to be some notation for it, and it's pretty peculiar to require people to think of the root system as derived from D,3 rather than A,3. (The reason this makes some sense is that it fits the pattern of D,n,2, not the pattern of A,2n+1,2, but I think that's okay.)

This was from following Kac's affine notation, which didn't allow A_3^(2).

Interesting! He really writes D_3⁽²⁾ and not A_3⁽²⁾? I'm surprised. To me, it seems in some sense like a feature not a bug that you can ask for A_3⁽²⁾ and you will be confronted with the one thing it has to be, even if that wasn't what you were expecting.

However, coercing to ('D',3,2) might be a better choice than an error message here. Unfortunately, ('A',3,2) doesn't resemble ('A',2k+1,2) in this case, but perhaps this is okay. Christian, feel free to let us know if you have a different preference. By the way, I just ran

sage: CartanType(['A',3,2])
['B', 2, 1]^*
sage: CartanType(['D',3,2])
['C', 2, 1]^*
sage: CartanType(['A',4,2])
['BC', 2, 2]
sage: CartanType(['A',5,2])
['B', 3, 1]^*
sage: CartanType(['A',7,2])
['B', 4, 1]^*
sage: CartanType(['D',4,2])
['C', 3, 1]^*
sage: CartanType(['D',5,2])
['C', 4, 1]^*

as a sanity check, and it actually does differ from this choice.

In fact CartanType('B',2,1) and CartanType('C',2,1) only differ by a reordering of the roots. This is consistent with our current choice, to treat QuiverMutationType('B',2,1) as a synonym for QuiverMutationType('C',2,1). It's also consistent with letting CartanType('A',3,2) and CartanType('D',3,2) be the same (since QuiverMutationType orders roots differently from CartanType anyway).

Should we make

sage: QuiverMutationType(['D',3,2])
['BB',2,1]
sage: QuiverMutationType(['A',3,2])
['CD',2,1]

instead?

No. There is no diagram 'CD',2,1. (In the sense that it isn't drawable.)

[hughrthomas]

comment:118

Gregg, I'm not sure I understand what you're trying to do with the code for the non-simply-laced elliptics.

It seems to me that the code constructing the digraph for F,4,[2,1] is never called, because that input is automatically recast as F,4,[1,2] before that point in the code is reached.

But if that code were run, I think it would cause problems. As it stands, we have a quiver mutation type called F,4,[1,2]. It has certain attributes, including a digraph. If you could ask for F,4,[2,1] and get a mutation type that was also called F,4,[1,2] but which had a different digraph, I think that would be really confusing (and I think it would screw up the cached methods, too).

It is certainly natural for users to ask for a specific quiver. But if someone really wants to ask for a specific quiver, I don't think the right mechanism for them to do it is for them to ask for a QuiverMutationType by a synonym. They should just ask for the quiver they want, and get that quiver (as an actual quiver, not as a mutation type). And then, depending on the implementation, we either figure out right then or later what the mutation type of the quiver is that they asked for. I think we should think of QuiverMutationType(X) as just giving you a default quiver, on the assumption that the user hasn't really specified a particular quiver.

This is also my real issue with the synonyms you added.

[hughrthomas]

comment:119

Gregg, I've looked at #10538, so now I think I understand what the point of the elliptics code you introduced was (i.e., it wasn't actually supposed to change the QuiverMutationType at all, so, as I remarked, the code you introduced would never actually be used when called by any routine introduced by this patch), but I think it's a confusing way to code it.

If you want, you could define some private method which both ClusterQuiver and QuiverMutationType would call. Or, and maybe this makes even more sense, QuiverMutationType could call ClusterQuiver to build the quiver, but ClusterQuiver would know how to build other quivers that aren't the default quivers associated to any QuiverMutationType.

In either of these cases, I would leave things as they are on this ticket, and make the change of #10538.

[sagetrac-gmoose05]

comment:120

I have now rolled back my recent changes. I believe there are some advantages to making further changes to the quiver_mutation_type.py file, but these advantages only occur in conjunction with the quiver.py file. Thus, we still should discuss my ideas to see if there's possible bugs that I'm not foreseeing, but these no longer affect #10527, only #10538. I have moved those changes (except for the bugs you found) out of my recent patch.

The general point is that I don't want to add more quiver mutation types, I only want to allow more flexibility in the user building a quiver. Since quiver_mutation_type.py is where we define all the digraphs anyway, my default plan was to eventually define more digraphs in quiver_mutation_type.py through a private method that a user won't directly access. In fact, we already have this programmed, QuiverMutationType_Irreducible, which is not imported into the global name space. In #10538, I was planning to have a patch that will allow the ClusterQuiver class to call this command for certain user inputs. This is somewhat like the suggestion you just made, if I understood correctly.

Short summary: my patch now only takes care of the issues you recently raised.

[stumpc5]

comment:121

Replying to @sagetrac-gmoose05:

Short summary: my patch now only takes care of the issues you recently raised.

I applied them again, and it worked well -- I agree that it is better to leave the changes on constructing other quivers to the other patch, so we have some time for discussions on design issues...

Replying to @robertwb:

Lazily importing * is preferred, as it avoids stat'ing a new directory and loading two new files (init.py and all.py). All this filesystem activity seems to be one of the primary reasons for slow Sage startup time (perhaps even more so than the execution of the .py files themselves) and if we're going to try to fix that it's important to be careful about what continues to be added.
That being said, I have know idea what's up with volker-desktop.stp.dias.ie . It's as if the file existed but was incomplete/empty. Let's see if that continues to be a problem.

Thanks for your comments again. Are you suggesting to lazily importing * ? We first did that but the patchbot didn't like it (i.e. some tests failed, see Comments [comment:95] and [comment:97] above), that's why we then did it another way.

[robertwb]

comment:122

Replying to @robertwb:

Lazily importing * is preferred, as it avoids stat'ing a new directory and loading two new files (init.py and all.py). All this filesystem activity seems to be one of the primary reasons for slow Sage startup time (perhaps even more so than the execution of the .py files themselves) and if we're going to try to fix that it's important to be careful about what continues to be added.
That being said, I have know idea what's up with volker-desktop.stp.dias.ie . It's as if the file existed but was incomplete/empty. Let's see if that continues to be a problem.

Thanks for your comments again. Are you suggesting to lazily importing * ? We first did that but the patchbot didn't like it (i.e. some tests failed, see Comments [comment:95] and [comment:97] above), that's why we then did it another way.

Yeah, I looked at those patchbot errors and was wondering if they were something environmental, 'cause I don't see how they could come up. I tried to apply these patches myself to try it out, but I apparently didn't have a new enough pre-release. I was thinking of adding a patch to use import * again and seeing if the patchbots (after checking my own local copy) were still unhappy (and may get around to doing this once I build myself a 5.4 alpha, as 5.3rc0 is apparently too old).

[hughrthomas]

comment:123

Hi Gregg--

Thanks again for revising your patch. The current version looks fine. In the absence of the patchbot, I should make sure the patch applies properly and tests okay on the current development release, not that this is likely to be a problem. My laptop is building 5.4.beta1 now.

cheers,

Hugh

[stumpc5]

comment:125

Replying to @hughrthomas:

Thank god (and also Gregg and Hugh)!

[jdemeyer]

comment:126

Please clarify which patches have to be applied.

[stumpc5]

comment:127

Apply only

• trac_10527-quiver_mutation_type.patch

[hughrthomas]

comment:128

Perhaps this will unconfuse the patchbot.

Apply trac_10527-quiver_mutation_type.patch

[hughrthomas]

comment:129

Volker's patchbot's complaint was actually just that a test timed out -- so not something we need to worry about.

Christian, could you please remove the sixth line of the patch, and change the commit message to something more appropriate for the patch as a whole?

cheers,

Hugh

[stumpc5]

comment:130

Replying to @hughrthomas:

Christian, could you please remove the sixth line of the patch, and change the commit message to something more appropriate for the patch as a whole?

done.

[hughrthomas]

comment:131

Thanks, Christian. Sorry to be tedious about this -- I think it could have held the process up later, so I figured, better to ask you to fix it now.

[jdemeyer]

Attachment: trac_10527-quiver_mutation_type.patch.gz

[jdemeyer]

comment:132

Patch rebased to sage-5.4.rc1.

[jdemeyer]

Merged: sage-5.5.beta0