Create a class for Coxeter matrices and types

[tscrim]

This is a partial step towards #16126, but carries the necessary information to speed up #16630 when the input is given as a finite !Cartan/Coxeter type.

It is possible to input numbers c<= -1 in the matrix to represent an infinite label, but with a different value in the bilinear form of the Tits representation.

The current implementation recognizes finite and affine types

Possible follow-up: -create an abstract class for Coxeter matrices and Cartan matrices? -Maybe change the name of CoxeterType.py could to type_coxeter.py -Recognize more types

Depends on #17990 Depends on #18152 Depends on #18743

CC: @sagetrac-sage-combinat @darijgr @fchapoton @jplab @sagetrac-vripoll @sagetrac-jmichel @nthiery @kevindilks

Component: group theory

Keywords: Coxeter groups, matrices, types, days64

Author: Travis Scrimshaw, Jean-Philippe Labbé

Branch: 5d188d4

Reviewer: Jean-Philippe Labbé, Travis Scrimshaw

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

[jplab]

comment:33

Test fails in /sage/src/sage/groups/matrix_gps/coxeter_group.py

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f2be73c to 3d73c0b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3d73c0b

Made tests pass in matrixcoxetergroup

[jplab]

comment:35

There were some failing tests in the Coxeter groups as Matrix groups. They are solved now.

[fchapoton]

comment:36

doc does not build

maybe because you need to use r""" when using latex command such as \infty or \ZZ

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3d73c0b to 19846a0

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

19846a0

Fixed documentation

[jplab]

comment:38

Should be fine now...

[jplab]

comment:39

There seems to be a test failing in the Coxeter group Category. I'll take care of that.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 19846a0 to 32f2168

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

32f2168

Made test pass in Category of Coxeter groups

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

522f9a4

Added doctest coverage to __repr__

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 32f2168 to 522f9a4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 522f9a4 to df35a43

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9afb736	Merge branch 'public/combinat/coxeter_matrices-17798' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798
df35a43	Implement a better API for pickling/classcall for Cartan/Coxeter matrices.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from df35a43 to eab7426

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

20bd15d	Added support for _repr_option('ascii_art').
56307d7	Merge branch 'public/interfaces/repr_option_ascii_art-18743' into public/combinat/coxeter_matrices-17798
eab7426	Fixing doctest from #18743.

[tscrim]

comment:44

I've made my round of changes. If your happy with my changes, then we can set a positive review (since we've done a cross-review, unless of course someone has any objections).

[tscrim]

Changed dependencies from #17990, #18152 to #17990, #18152, #18743

[tscrim]

Reviewer: Jean-Philippe Labbé, Travis Scrimshaw

[jplab]

comment:45

Hi Travis,

Thanks for the recent changes! They look good to me.

The patchbot should check if everything is ok and then we could set it to positive review.

[jplab]

comment:46

Hi,

I have difficulty reading what the failure in "startup-module" really is.

What is wrong?

[tscrim]

comment:47

So it is saying that we are importing 5 new modules at startup. I think we should lazily import the coxeter_matrix and coxeter_type. The other option is to change this to a lazy import: from sage.graphs.generators.basic import CycleGraph.

Also the test failures in src/sage/interfaces/psage.py are due to an old version of #18743, but we have to figure why the CoxeterGroup element doesn't work properly. It might be an issue with comparisons, but it might be with the pickling...

[tscrim]

comment:48

So the problem is that the type recognition does not support relabelings:

sage: M = CoxeterMatrix([[1,3,2],[3,1,6],[2,6,1]])
sage: M
[1 3 2]
[3 1 6]
[2 6 1]
sage: M.coxeter_type()
Coxeter type of ['G', 2, 1]
sage: loads(dumps(M))
[1 2 3]
[2 1 6]
[3 6 1]

The type should be relabeled to (1, 2, 3) and does not necessarily correspond to (0, 1, 2).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from eab7426 to c9125e1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f0ee04a	Merge branch 'public/combinat/coxeter_matrices-17798' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798
6285150	Merge branch 'public/interfaces/repr_option_ascii_art-18743' of trac.sagemath.org:sage into public/interfaces/repr_option_ascii_art-18743
7bc49f5	Adding `_repr_option` to the interface element to avoid __getattr__.
27a2847	Merge branch 'public/interfaces/repr_option_ascii_art-18743' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798
c9125e1	Implement better type recognition using (di)graph isomorphism testing.

[tscrim]

comment:50

As per my discussion with Jean-Philippe at FPSAC, I've implemented type-checking using graph isomorphism testing, which fixes the relabeling issue (it feels more efficient). Just needs a quick check (and the remaining dependency should be a trivial review, but it needs a reviewer).

[jplab]

comment:51

It seems that there was an error when building sage.

I looked at the crash report and there is an ImportError:

"ImportError: No module named inherit_comparison"

Which seems to be the source of the problem.

Any idea?

[tscrim]

comment:52

I don't get this error, and I have no idea what's going on with your build (the error occurs before startup, right?). You only get it with this patch? What is the output of git diff --name-status develop?

[jplab]

comment:53

I pulled the latest version of develop and it compiled fine. (make distclean && make). Then, I checked out the branch and pulled the latest changes and then built.

The output of git diff --name-status develop gives my a relatively long list of (python, rst, txt, etc.) files. Are you looking for something in particular? It may be difficult to track.

I'll just make distclean and compile again.

I'll report about the latest changes in the ticket then.

[tscrim]

comment:54

git diff --name-status develop shows the files which are different compared to develop, so assuming you have merged in the latest develop to both branches, it should give a comprehensive list of changes.

However I'm not quite sure what you're saying. Did you already merge in the latest develop and tested this branch on top of that and it didn't work?

[jplab]

comment:55

I just went directly on the branch (without merging the very latest version of develop) and compiled. Now I get an error in building the doc, because some folder does not exist.

I will just do a merge with the latest develop and compile again. This seems to be a reasonable option now.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c9125e1 to cd7d946

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cd7d946

Merge branch 'sage6.8.rc0' into cox_matrices_trac

[jplab]

comment:57

All test passed on sage6.8.rc0

If the bot is happy I would set the patch to positive review. I am satisfied with the changes in the type recognition algorithm.

[tscrim]

comment:58

Thank you for your work on this. The bot seems to be down for the time being, but it did pass on the previous version. Do you think you could also give a quick review of the dependency too?

Let me know when the followups are ready for review.

[1adc0eef-8957-46d9-975b-2dd71dfbd9ba]

comment:60

Patchbot says this code now causes some sort of infinite recursion on crystals.

[jplab]

comment:61

Dear Kevin,

Could you give some minimal not-working example of the problem?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from cd7d946 to e2ad156

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

86a3c73	Merge branch 'public/combinat/coxeter_matrices-17798' of trac.sagemath.org:sage into ticket17798
e2ad156	Made two tests pass

[tscrim]

comment:64

Kevin and I tried it out and couldn't reproduce the patchbot results.

[jplab]

comment:65

All tests seem to pass on sage-6.9 on my computer right now...

There were two tests failing on 6.9 that I fixed in the last commit.

[1adc0eef-8957-46d9-975b-2dd71dfbd9ba]

comment:66

Tests on the files you changed pass, but it's causing some sort of infinite recursion on crystals. It's also causing some doctests to fail in cluster_seed().

sage -t --long src/sage/combinat/rigged_configurations/kr_tableaux.py  # 5 doctests failed
sage -t --long src/sage/combinat/rigged_configurations/rigged_configurations.py  # 7 doctests failed
sage -t --long src/sage/combinat/crystals/littelmann_path.py  # 3 doctests failed
sage -t --long src/sage/combinat/crystals/kirillov_reshetikhin.py  # 34 doctests failed
sage -t --long src/sage/combinat/cluster_algebra_quiver/cluster_seed.py  # 3 doctests failed
sage -t --long src/sage/combinat/rigged_configurations/rigged_configuration_element.py  # 1 doctest failed
sage -t --long src/sage/combinat/crystals/kyoto_path_model.py  # 3 doctests failed
sage -t --long src/sage/combinat/crystals/tensor_product.py  # 6 doctests failed
sage -t --long src/doc/en/thematic_tutorials/lie/affine_finite_crystals.rst  # 9 doctests failed
sage -t --long src/sage/combinat/root_system/cartan_type.py  # 1 doctest failed
sage -t --long src/sage/combinat/root_system/dynkin_diagram.py  # 1 doctest failed
sage -t --long src/sage/combinat/crystals/subcrystal.py  # 2 doctests failed
sage -t --long src/sage/combinat/crystals/virtual_crystal.py  # 4 doctests failed

You can ignore two failing doctests in root system, since I believe you just fixed those.

[jplab]

comment:67

Excellent! On it...!

[1adc0eef-8957-46d9-975b-2dd71dfbd9ba]

comment:68

Travis is working on the issue with crystals now.

The tests that are failing in cluster_seed.py are under universal_extension(), which mentions that it gets the almost positive co-roots in a non-elegant way and non-standard order, so it may have to be rewritten.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e6971e7

Make sure that indexing sets are passed along by subtype.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e2ad156 to e6971e7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e6971e7 to 4ca4345

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

4ca4345

Making KR crystals more robust against relabeling.

[tscrim]

comment:71

Okay, so the issue which caused the crystals to infinitely recurse is that the type recognition via subtype() did not pass along the appropriate labels (I'm not 100% sure what was calling subtype()...). In particular, classical types got relabeled by [0, 1, ...], and KR crystals were sensitive to the labellings. I fixed this (which was indicated by the fact that we now had to add the relabel to the subtype test) and in a separate commit I made the KR crystals less sensitive to relabellings (but fixing them altogether is an entirely different issue and would deserve a separate ticket). What had changed from our previous version was that our type recognition system did not support relabelling, but now using Dynkin diagrams it does.

Unfortunately this did not fix the issue for cluster seeds.