Implementation of the SubwordComplex as defined by Knutson and Miller

stumpc5 commented 13 years ago

This patch provides an implementation of the subword complex:

Fix a Coxeter system (W,S). Let Q = be a finite word in S and pi in W.

The subword complex Delta(Q,pi) is then defined to be the simplicial complex with vertices being {0,...,n-1}, (n = len(Q), one vertex for each letter in Q) and with facets given by all (indices of) subwords Q' of Q for which Q\Q' is a reduced expression for pi.

    sage: W = CoxeterGroup(['A',2],index_set=[1,2])
    sage: w = W.from_reduced_word([1,2,1])
    sage: C = SubwordComplex([2,1,2,1,2],w); C
    Subword complex of type ['A', 2] for Q = [2, 1, 2, 1, 2] and pi = 121
    sage: C.facets()
    {(1, 2), (3, 4), (0, 4), (2, 3), (0, 1)}

Component: combinatorics

Keywords: subword complex, simplicial complex

Author: Christian Stump

Branch/Commit: 17518c1

Reviewer: Frédéric Chapoton

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 0468798 to 2d84a4b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`518eb3c`	`Merge branch 'u/chapoton/11010' into 6.10.rc0`
`3f10491`	`trac #11010 more doc`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 2d84a4b to 3f10491

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

cf864bd trac #11010 trying to add more doc (but alas blindly)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 3f10491 to cf864bd

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

1447f4b trac #11010 a lot of work, still some parts are broken

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from cf864bd to 1447f4b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

004f8a8 trac #11010 caching the positive roots

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 1447f4b to 004f8a8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 004f8a8 to 8b5db7a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

8b5db7a trac 11010 more caching

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

4e50eec trac #11010 more work on doc and code of subword complexes

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 8b5db7a to 4e50eec

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

567a767 trac #11010 almost working now (but plot is broken)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 4e50eec to 567a767

fchapoton commented 8 years ago

comment:45

Ok, guys. We are almost there. Most of the things are working and hopefully not too slow. I have worked hard for two days, so please react !

Just 2 small remaining problems (unless the bot reveals some others):

the "plot" code is broken, maybe we can remove that for the moment ? unless somebody wants to repair it ?
the "root_polytope" method is not documented, any objection to its removal ? unless you can provide a working example ?

cheers,

Frederic

fchapoton commented 8 years ago

Changed dependencies from #12774, #11187 to none

fchapoton commented 8 years ago

Changed work issues from coverage to plot and root_polytope

stumpc5 commented 8 years ago

comment:48

Hi Frederic -- thanks a lot for all your work here! I am still too busy to contribute, but I can promise to have had a closer look by the end of the week, together with my opinion on how to proceed and a few speed tests... Cheers, Christian

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 567a767 to d0a5f71

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

d0a5f71 trac #11010 some details

stumpc5 commented 8 years ago

comment:50

Okay, things seem to work, great!

Root polytope: all this patch was basically parked on trac for my own research. And this method is stuff for which nothing is proven so far, so it should not be part of the ticket anymore.
Plot: what do you have in mind outside of types A and B?
Here are a few timings:

This patch:

sage: W = WeylGroup(['A',6])
sage: c = list(W.index_set()); Q = c + W.w0.coxeter_sorting_word(c)
sage: %time S = SubwordComplex(Q,W.w0)
CPU times: user 23.6 s, sys: 36 ms, total: 23.6 s
Wall time: 23.6 s
sage: len(S)
429

The same patch based on the Coxeter group implementation:

sage: W = CoxeterGroup(['A',6])                                    
sage: c = list(W.index_set()); Q = c + W.w0.coxeter_sorting_word(c)
sage: %time S = SubwordComplex(Q,W.w0)                             
CPU times: user 0.41 s, sys: 0.00 s, total: 0.41 s
Wall time: 0.41 s
sage: len(S)                                                       
429

stumpc5 commented 8 years ago

Changed branch from u/chapoton/11010 to u/stumpc5/11010

stumpc5 commented 8 years ago

Changed commit from d0a5f71 to 6b65d70

stumpc5 commented 8 years ago

Changed work issues from plot and root_polytope to none

stumpc5 commented 8 years ago

comment:52

I removed some experimental code that is not supposed to be merged (this includes the root polytope), and fixed the plot. This file's tests pass locally, so let's see what the patchbot says...

New commits:

`5c93cd4`	`Merge branch 'u/chapoton/11010' of git://trac.sagemath.org/sage into 11010-new`
`6b65d70`	`removed a few experimental methods, fixed the plot`

fchapoton commented 8 years ago

comment:53

I think one should put a large Warning about

To be used only with Coxeter groups in the implementation='reflection'

In fact, it is not only slow but mostly broken with Weyl groups.

Side remark : it seems that one cannot use the quadratic fields Q(sqrt2) for type B and Q(sqrt5) for type H. To be fixed in another ticket, maybe.

stumpc5 commented 8 years ago

comment:54

In fact, it is not only slow but mostly broken with Weyl groups.

Oh yes, the doctests were written for implementation='reflection' so it does not show that it is broken for Weyl groups.

I will have a quick look whether I can fix that!

tscrim commented 8 years ago

comment:55

I'm not too surprised WeylGroup is slower; it goes through the GAP interface (in particular, for multiplication) whereas the reflection implementation (of Coxeter groups) does not. However because of this, it can't get things like conjugacy classes. There is probably quite a bit we can improve with (GAP) matrix groups, but that is an issue for another ticket.

However, it surprises me a little bit that it is broken for Weyl groups because the reflection implementation was fairly minimal (up to what comes from the category).

stumpc5 commented 8 years ago

comment:56

First, the definition of subword complexes is for Coxeter groups (finite or infinite), but many of its properties (see my paper with Vincent referenced in the header) come from understanding roots and weights. (This means that the construction works, but many methods don't.)

Second, I think the current failure is only because the method WeylGroup.roots is missing, as is the method WeylGroupElement.action_on_root_indices.

Do you know how I can get the list of (simple, positive, almost positive, all) roots of a root system when I only have the Weyl group W at hand? It seems that I have to build a root system from the Cartan type, though it seems more natural to have a method WeylGroup.root_system or at least WeylGroup.cartan_matrix, wouldn't it?

fchapoton commented 8 years ago

Changed commit from 6b65d70 to f4bc87f

fchapoton commented 8 years ago

Changed branch from u/stumpc5/11010 to u/chapoton/11010

fchapoton commented 8 years ago

comment:57

New branch, where I have added a warning.

Do you really want this to work for Weyl groups ?

You can build roots for Weyl groups just as I did for the Coxeter groups, using a reduced word for w0. But it will not be enough..

New commits:

`59e9e2d`	`Merge branch 'u/stumpc5/11010' into 6.10`
`f4bc87f`	`trac #11010 some doc details, and pep8`

stumpc5 commented 8 years ago

comment:58

Replying to @fchapoton:

Do you really want this to work for Weyl groups ?

I just want to quickly see if I can get the method root_configuration working since many others only depend on this one. And many people do use Weyl groups...

stumpc5 commented 8 years ago

comment:59

Replying to @stumpc5:

Do you know how I can get the list of (simple, positive, almost positive, all) roots of a root system when I only have the Weyl group W at hand? It seems that I have to build a root system from the Cartan type, though it seems more natural to have a method WeylGroup.root_system or at least WeylGroup.cartan_matrix, wouldn't it?

Ah, WeylGroup.domain does it...

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

e252db3 trac #11010 bad unicode character removed

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from f4bc87f to e252db3

stumpc5 commented 8 years ago

comment:61

Do you really want this to work for Weyl groups ?

Okay, I give up on this -- I tried the past hours to get it done for Weyl groups, but I basically have to fix every single method, and even have to implement my own fundamental weights in order to make this work for Weyl groups. If this is crucial at some point, we can still get back to this...

stumpc5 commented 8 years ago

comment:62

The patchbot is happy, so I think this is ready to go -- or do you see any remaining problems?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`7d9f5e8`	`Merge branch 'u/chapoton/11010' into 7.10.b2`
`8b79780`	`trac #11010 one typo`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from e252db3 to 8b79780

fchapoton commented 8 years ago

comment:64

I am not quite satisfied with the custom naive type A/B recognition in the plot method. Travis, is there a better way ? or even a way to have the correct type printed in the repr ?

tscrim commented 8 years ago

comment:65

Replying to @fchapoton:

I am not quite satisfied with the custom naive type A/B recognition in the plot method. Travis, is there a better way ? or even a way to have the correct type printed in the repr ?

You can use the (relatively recent) Coxeter matrices and types:

sage: W = CoxeterGroup(['C',4])
sage: T = W.coxeter_matrix().coxeter_type(); T
Coxeter type of ['C', 4]

The current implementation for Coxeter types essentially wraps the Cartan types, so there is a "different" type for B and C. (This was done because there was a lot of information that could be pulled from the Cartan type, as there is a lot of hard-coded data, and I didn't want to have to try and decide on a naming scheme. I fully take the blame for the hacks involved.)

However, the information you're after is inside the wrapped type:

sage: T.cartan_type()
['B', 4]
sage: T.cartan_type().type()
'B'
sage: T.cartan_type().rank()
4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

1b10c95 trac #11010 re-introducing Cartan types

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 8b79780 to 1b10c95

fchapoton commented 8 years ago

comment:67

ok, thanks Travis. I have done the needed changes, I think.

fchapoton commented 8 years ago

Reviewer: Frédéric Chapoton

fchapoton commented 8 years ago

comment:68

ok, I think that this can go. Christian, if you agree, set to positive.

tscrim commented 8 years ago

comment:70

Does the plotting also work for type C, being that it is the dual of type B (and we are dealing with Cartan types)?

stumpc5 commented 8 years ago

comment:71

I am rather confused now:

First Sage start

sage: W = CoxeterGroup(['B',4])
sage: W.coxeter_matrix().coxeter_type()
Coxeter type of ['B', 4]
sage: W = CoxeterGroup(['C',4])
sage: W.coxeter_matrix().coxeter_type()
Coxeter type of ['B', 4]

Second Sage start

sage: W = CoxeterGroup(['C',4])
sage: W.coxeter_matrix().coxeter_type()
Coxeter type of ['C', 4]
sage: W = CoxeterGroup(['B',4])
sage: W.coxeter_matrix().coxeter_type()
Coxeter type of ['C', 4]

In particular, the root systems W.roots() are not correct in the two second calls of CoxeterGroup.

Also, the plotting now assumes that the first index is the type B/C special one. This is, it is expected that

sage: s0 = W.simple_reflection(W.index-set()[0])
sage: s1 = W.simple_reflection(W.index-set()[1])
sage: (s0*s1).order()
4

I doubt that this is correct in the current implementation of Coxeter groups where the last index is expected to be special. If so, I will add some magic to figure out the proper labelling...

sagemath / sage

Implementation of the SubwordComplex as defined by Knutson and Miller #11010