Opened 8 years ago

Closed 7 years ago

#16630 closed defect (fixed)

Fix category for finite Coxeter groups

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-6.6
Component: group theory Keywords: Coxeter, category
Cc: nthiery, chapoton, jipilab, vripoll Merged in:
Authors: Travis Scrimshaw, Frédéric Chapoton, Darij Grinberg Reviewers: Darij Grinberg, Frédéric Chapoton, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 49cc3bc (Commits, GitHub, GitLab) Commit: 49cc3bc1ecaba4b43f2ed426a8ebbfee6c77ddcd
Dependencies: #16633 Stopgaps:

Status badges

Description

Currently finite Coxeter groups don't know that they are finite.

sage: CG = CoxeterGroup(['D',4])
sage: CG.category()
Category of coxeter groups

Change History (45)

comment:1 Changed 8 years ago by tscrim

  • Branch set to public/groups/fix_category_finite_coxeter-16630
  • Commit set to 0f2941a9ec0dd54531a5349f10dc3c1a5ae5f1d0
  • Dependencies set to #16633 #16634
  • Status changed from new to needs_review

Okay, it's now up for review. It feels somewhat hacky to me (in particular, I had to catch an OverflowError), but it comes from Sage's somewhat lack of ability to compute positive definiteness of a matrix over a variety of fields. Although I do feel that checking for positive definiteness is better than doing the matrix comparisons, at least as a first try. meh *shrugs*


New commits:

02752c9Implement a bilinear_form method and use this to check finiteness.
484ae91Fixed _indefinite_factorization() for immutable matrix over fields.
6b01dd0Merge branch 'public/matrix/indefinite_factorization_immutable-16633' into public/groups/fix_category_finite_coxeter-16630
78cfb38Expanded conversions for real numbers.
383632bMerge branch 'public/rings/expand_RR_conversion-16634' into public/groups/fix_category_finite_coxeter-16630
cdf6d5dAdded doctests.
0f2941aSome fixes for doctests.

comment:2 Changed 8 years ago by darij

What does this have to do with real numbers?

comment:3 Changed 8 years ago by tscrim

It has to do with positive_definite trying to work over RR but the default for the matrices (for the Coexter groups) is over the universal cyclotomic field.

comment:4 Changed 8 years ago by darij

Ah, I see. Hmm, are these matrices bounded away from singularity well enough that we can trust this to work? Otherwise I'd rather take the irreducible decomposition of the matrix (Dijkstra's algorithm, should be fast) and check each of them for being a Coxeter-Dynkin diagram (now that can be annoying). I assume the two steps of this procedure (irreducible decomposition and Coxeter-Dynkin classification) are something we want to have anyway; or do we already?

comment:5 Changed 8 years ago by tscrim

As far as I've tested. The fallback (in case an error is raised) is to check by comparing Coxeter matrices under the standard labeling, but does not break it up into irreducible components. It probably is better to do the process entirely using graph comparisons (it feels like it should be slower, but maybe it's not...). Although no such check has been implemented for Coxeter diagrams/matrices, which currently don't have dedicated classes (#16126). (BTW there's only limited support for Dynkin diagrams.)

comment:6 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 8 years ago by git

  • Commit changed from 0f2941a9ec0dd54531a5349f10dc3c1a5ae5f1d0 to 27113957d53f5bf2c1efaa0107c142aa9c13a071

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

2a34029Merge branch 'public/groups/fix_category_finite_coxeter-16630' of git://trac.sagemath.org/sage into coxeter
2711395a first attempt at checking finiteness of coxeter groups without using reals

comment:8 Changed 8 years ago by darij

I thought this would be fun :/ Not really tested so far (I have added doctests checking that finite Coxeter groups are recognized as finite, but it is much harder to test that infinite Coxeter groups are not). But you can throw away the red #16634 dependency at least.

Can you check that my retraction of your base_ring.one() -> base_ring(2) edit was correct? Also, I was a bit worried about the slash in val(coxeter_matrix[i, j]) / base_ring(-2) getting reinterpreted as division-with-rest when base_ring is ZZ, but apparently this does not cause issues.

comment:9 Changed 8 years ago by git

  • Commit changed from 27113957d53f5bf2c1efaa0107c142aa9c13a071 to dd22351c2c457e44f7b290fe9205a9decae1b813

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

dd22351better algorithm, is_finite method and some tests

comment:10 follow-up: Changed 8 years ago by darij

A few thoughts:

  • If the finiteness testing algorithm is slow, we might want to add an option to provide the necessary info right away.
  • The algorithm does a lot more than finiteness checking: it breaks the group into irreducibles, and (with some modification) should be able to build an explicit isomorphism of a finite Coxeter group to a direct product of classical Cartan-type groups. Methinks we should make use of this. Should this isomorphism be cached?
Last edited 8 years ago by darij (previous) (diff)

comment:11 Changed 8 years ago by git

  • Commit changed from dd22351c2c457e44f7b290fe9205a9decae1b813 to 727e3c62d5b1ca0b297091958133fa8edec92429

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

727e3c6undoing edits to real_mpfr.pyx

comment:12 Changed 8 years ago by darij

  • Dependencies changed from #16633 #16634 to #16633

comment:13 in reply to: ↑ 10 Changed 8 years ago by nthiery

Replying to darij:

A few thoughts:

  • If the finiteness testing algorithm is slow, we might want to add an option to provide the necessary info right away.
  • The algorithm does a lot more than finiteness checking: it breaks the group into irreducibles, and (with some modification) should be able to build an explicit isomorphism of a finite Coxeter group to a direct product of classical Cartan-type groups. Methinks we should make use of this. Should this isomorphism be cached?

A couple further thoughts:

Looking at ​dd22351, this indeed looks like an automatic type recognition starting from a Coxeter diagram or Dynkin diagram, as is implemented in GAP 3. That's been in the TODO list for a while [1], so it would be rather cool. If we go this way, this should really be a method of CartanType? and friends, and we should reuse the same algorithm for this method as in GAP3, except that we have fast graph isomorphism tests, so we can simplify it a bit. For the name, maybe this could be isomorphic_named_cartan_type. Although we probably want to return a relabelled Cartan type that exactly matches the original Cartan type.

This could then, in the long run, be used for any Coxeter group, be it defined by a Coxeter matrix or concretely by simple reflections and a product rule: first build the Coxeter diagram by computing the length of the braid relation between the simple reflections, and then get the canonical type. Single caveat: if, for a given Coxeter group, all we have available is the possibility to compute products of such simple reflections, then we can get stuck computing that order if there is an infinite braid relation.

For the record real positivity test is implemented, with guaranteed result, in UCF:

sage: x = UniversalCyclotomicField().an_element()
sage: x.is_real_positive()

Maybe this is a simpler way to go.

If the user knows right away that the groupe is finite (or infinite), then he should just pass that information on with a category=CoxeterGroups().Finite() argument.

Cheers,

Nicolas

[1] http://trac.sagemath.org/wiki/SageCombinatChevieStatusReport

comment:14 Changed 8 years ago by nthiery

  • Cc jipilab vripoll added

comment:15 Changed 8 years ago by tscrim

The only unbounded edges for finite Coxeter diagrams are the dihedral groups, so we just special case rank 2 (which are almost always finite and we should be able to check the infinite case easily enough) and then build the graph by checking (xy)m up to m = 5 (the finite check) or some specified user input.

comment:16 Changed 8 years ago by nthiery

True enough; for finiteness checking purposes, only rank 2 is an issue. In the case at hand, that's easy to handle. Gor Coxeter groups implepented differently, we might not be able to decide, but that's a narrow enough case that we can leave the responsability to the group implementer.

Cheers,

comment:17 Changed 8 years ago by tscrim

Notes for Darij from our discussion:

  • Make the finiteness check a separate static function.
  • Make the testing for #16630 more systematic using something like
    sage: all(CoxeterGroup(ct) in CoxeterGroups().Finite() for ct in some_list_of_types)
    True
    

comment:18 Changed 7 years ago by git

  • Commit changed from 727e3c62d5b1ca0b297091958133fa8edec92429 to 3940b318a6a422b5b1e359aefe764752898551b6

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

91c71b0Merge branch 'public/groups/fix_category_finite_coxeter-16630' into 6.5.rc3
3940b31trac #16630 separating the finite recognition algorithm

comment:19 Changed 7 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.5

comment:20 Changed 7 years ago by git

  • Commit changed from 3940b318a6a422b5b1e359aefe764752898551b6 to 10a9b7c7d29d265822a1996bca5670e35b4f22a3

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

10a9b7ctrac #16630 correction of a typo in the doc

comment:21 Changed 7 years ago by git

  • Commit changed from 10a9b7c7d29d265822a1996bca5670e35b4f22a3 to d719c7e54c632d1a5e745449571e6cf316d4c93d

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

d719c7etrac #16630 trying to simplify type recognition

comment:22 Changed 7 years ago by git

  • Commit changed from d719c7e54c632d1a5e745449571e6cf316d4c93d to 26ab1c9275f326964b88b87f14db7775a18fe346

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

26ab1c9Conflicts:

comment:23 Changed 7 years ago by chapoton

  • Branch changed from public/groups/fix_category_finite_coxeter-16630 to public/ticket/16630
  • Commit changed from 26ab1c9275f326964b88b87f14db7775a18fe346 to d719c7e54c632d1a5e745449571e6cf316d4c93d

Hmm, I am having some git problems.. Let me try with this branch

public/ticket/16630

comment:24 Changed 7 years ago by git

  • Commit changed from d719c7e54c632d1a5e745449571e6cf316d4c93d to 02c4161a5a5eae6c5bff3aeee3e857ff22c9b422

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3034dccImplement a bilinear_form method and use this to check finiteness.
e4e9322Expanded conversions for real numbers.
6b93710Added doctests.
c969265Some fixes for doctests.
09441b9a first attempt at checking finiteness of coxeter groups without using reals
d01cbb3better algorithm, is_finite method and some tests
19c40bdundoing edits to real_mpfr.pyx
1f3011ctrac #16630 separating the finite recognition algorithm
d48ef8btrac #16630 correction of a typo in the doc
02c4161trac #16630 trying to simplify type recognition

comment:25 Changed 7 years ago by chapoton

Ok, I think this is good to go. Can somebody review my commits ?

comment:26 Changed 7 years ago by tscrim

  • Authors changed from Travis Scrimshaw to Travis Scrimshaw, Frederic Chapoton
  • Reviewers set to Darij Grinberg, Frederic Chapoton, Travis Scrimshaw

LGTM modulo one minor change: when constructing self._bilinear, could we divide by base_field(-2) instead of base_ring(-2) (since this coercion will happen anyways)? Once this change is made, then you can set a positive review on my behalf.

comment:27 Changed 7 years ago by darij

A git question: When this branch gets merged, will the branch in #16634 become invisible (i.e., appear to do nothing)? This is one of those corner cases where I'm worried about git doing the wrong thing, because I reverted the changes from #16634 in a followup commit here.

comment:28 Changed 7 years ago by darij

Also, I suggest we do allow the user to pass a boolean is_finite parameter to sidestep finiteness recognition. I reckon that lots of Coxeter groups constructed will be A_n and B_n for high n.

comment:29 Changed 7 years ago by tscrim

It should be okay. If it doesn't work, the commits from #16634 are still in the history which we can pull out.

For the flag thing, because of pickling and how UniqueRepresentation works, we are better off doing a partial version of #16126 by making a class for CoxeterMatrix, which is now #17798 and should be easy enough to do (and will be high on my todo list).

comment:30 Changed 7 years ago by darij

Oh wait, I see that I actually already rebased #16634. Forget about it then.

Will #17798 mean that Coxeter groups given via their types will be tested for finiteness directly rather than using my matrix-analysis code? That would indeed be a solution.

comment:31 Changed 7 years ago by git

  • Commit changed from 02c4161a5a5eae6c5bff3aeee3e857ff22c9b422 to ad1d4cc48582a7596b6bc61f47a5c796e771efe6

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

685e866Merge branch 'public/ticket/16630' of trac.sagemath.org:sage into 16630
ad1d4cctrac #16630 replace base_ring by base_field

comment:32 Changed 7 years ago by chapoton

So is this ok now ?

comment:33 Changed 7 years ago by chapoton

  • Authors changed from Travis Scrimshaw, Frederic Chapoton to Travis Scrimshaw, Frédéric Chapoton
  • Reviewers changed from Darij Grinberg, Frederic Chapoton, Travis Scrimshaw to Darij Grinberg, Frédéric Chapoton, Travis Scrimshaw

comment:34 Changed 7 years ago by tscrim

  • Authors changed from Travis Scrimshaw, Frédéric Chapoton to Travis Scrimshaw, Frédéric Chapoton, Darij Grinberg
  • Status changed from needs_review to positive_review

@darij Yes, that's correct, or at least what I'm planning to do on #17798. (I added your name to the authors list since you wrote the first version of the recognition algorithm.)

@Frederic Yes. Thank you.

comment:35 Changed 7 years ago by chapoton

  • Milestone changed from sage-6.5 to sage-6.6

comment:36 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long --warn-long 39.8 src/sage/groups/matrix_gps/coxeter_group.py  # 2 doctests failed

comment:37 Changed 7 years ago by chapoton

Damn.. Now that they are recognized to be finite, an iterator seems to be required.. or at least a cardinality method maybe..

sage: W = CoxeterGroup([[1,3,2],[3,1,4],[2,4,1]], base_ring=QQbar)
sage: W.is_finite()
True
sage: W.cardinality()
BOOM

comment:38 Changed 7 years ago by git

  • Commit changed from ad1d4cc48582a7596b6bc61f47a5c796e771efe6 to d1b9211eb55403bbfad3fb23adf127a92447ffb1

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

c10b8d4Merge branch 'public/ticket/16630' into 6.6.beta0
d1b9211trac #16630 adding a cardinality method.

comment:39 Changed 7 years ago by chapoton

  • Status changed from needs_work to needs_review

Ok, adding a cardinality method seems to work.

I have also added the word "Finite" to the repr when the Coxeter group is finite.

comment:40 Changed 7 years ago by tscrim

  • Branch changed from public/ticket/16630 to public/groups/fix_category_finite_coxeter-16630
  • Commit changed from d1b9211eb55403bbfad3fb23adf127a92447ffb1 to 49cc3bc1ecaba4b43f2ed426a8ebbfee6c77ddcd

I renamed this method order, which is the real cause of the issue why cardinality from FiniteEnumeratedSets isn't working properly (and order raises a NotImplementedError where it shouldn't either). I also refined the category to Infinite if the group is not finite.

Note that I cherry-picked your commits into this branch (since I don't want to upgrade my copy of Sage today).


New commits:

3597e2fMerge branch 'public/groups/fix_category_finite_coxeter-16630' of trac.sagemath.org:sage into public/groups/fix_category_finite_coxeter-16630
0f5d819trac #16630 replace base_ring by base_field
be4cdbftrac #16630 adding a cardinality method.
49cc3bcChanged cardinality() to order() and added Infinite refinement.

comment:41 Changed 7 years ago by chapoton

Looks good to me. If you agree, you can set a positive review.

comment:42 Changed 7 years ago by tscrim

I'm good with things; Darij?

comment:43 Changed 7 years ago by darij

From a quick glance at it, yes. But I haven't been keeping track of this ticket too closely, so I hope someone has reviewed Francois's edits too?

comment:44 Changed 7 years ago by tscrim

  • Status changed from needs_review to positive_review

I have been looking at Frederic's changes, so (back to) positive review.

comment:45 Changed 7 years ago by vbraun

  • Branch changed from public/groups/fix_category_finite_coxeter-16630 to 49cc3bc1ecaba4b43f2ed426a8ebbfee6c77ddcd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.