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:  sage6.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: 
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
 Branch set to public/groups/fix_category_finite_coxeter16630
 Commit set to 0f2941a9ec0dd54531a5349f10dc3c1a5ae5f1d0
 Dependencies set to #16633 #16634
 Status changed from new to needs_review
comment:2 Changed 8 years ago by
What does this have to do with real numbers?
comment:3 Changed 8 years ago by
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
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 CoxeterDynkin diagram (now that can be annoying). I assume the two steps of this procedure (irreducible decomposition and CoxeterDynkin classification) are something we want to have anyway; or do we already?
comment:5 Changed 8 years ago by
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
 Milestone changed from sage6.3 to sage6.4
comment:7 Changed 8 years ago by
 Commit changed from 0f2941a9ec0dd54531a5349f10dc3c1a5ae5f1d0 to 27113957d53f5bf2c1efaa0107c142aa9c13a071
comment:8 Changed 8 years ago by
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 divisionwithrest when base_ring
is ZZ, but apparently this does not cause issues.
comment:9 Changed 8 years ago by
 Commit changed from 27113957d53f5bf2c1efaa0107c142aa9c13a071 to dd22351c2c457e44f7b290fe9205a9decae1b813
Branch pushed to git repo; I updated commit sha1. New commits:
dd22351  better algorithm, is_finite method and some tests

comment:10 followup: ↓ 13 Changed 8 years ago by
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 Cartantype groups. Methinks we should make use of this. Should this isomorphism be cached?
comment:11 Changed 8 years ago by
 Commit changed from dd22351c2c457e44f7b290fe9205a9decae1b813 to 727e3c62d5b1ca0b297091958133fa8edec92429
Branch pushed to git repo; I updated commit sha1. New commits:
727e3c6  undoing edits to real_mpfr.pyx

comment:12 Changed 8 years ago by
 Dependencies changed from #16633 #16634 to #16633
comment:13 in reply to: ↑ 10 Changed 8 years ago by
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 Cartantype 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
 Cc jipilab vripoll added
comment:15 Changed 8 years ago by
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
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
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
 Commit changed from 727e3c62d5b1ca0b297091958133fa8edec92429 to 3940b318a6a422b5b1e359aefe764752898551b6
comment:19 Changed 7 years ago by
 Milestone changed from sage6.4 to sage6.5
comment:20 Changed 7 years ago by
 Commit changed from 3940b318a6a422b5b1e359aefe764752898551b6 to 10a9b7c7d29d265822a1996bca5670e35b4f22a3
Branch pushed to git repo; I updated commit sha1. New commits:
10a9b7c  trac #16630 correction of a typo in the doc

comment:21 Changed 7 years ago by
 Commit changed from 10a9b7c7d29d265822a1996bca5670e35b4f22a3 to d719c7e54c632d1a5e745449571e6cf316d4c93d
Branch pushed to git repo; I updated commit sha1. New commits:
d719c7e  trac #16630 trying to simplify type recognition

comment:22 Changed 7 years ago by
 Commit changed from d719c7e54c632d1a5e745449571e6cf316d4c93d to 26ab1c9275f326964b88b87f14db7775a18fe346
Branch pushed to git repo; I updated commit sha1. New commits:
26ab1c9  Conflicts:

comment:23 Changed 7 years ago by
 Branch changed from public/groups/fix_category_finite_coxeter16630 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
 Commit changed from d719c7e54c632d1a5e745449571e6cf316d4c93d to 02c4161a5a5eae6c5bff3aeee3e857ff22c9b422
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3034dcc  Implement a bilinear_form method and use this to check finiteness.

e4e9322  Expanded conversions for real numbers.

6b93710  Added doctests.

c969265  Some fixes for doctests.

09441b9  a first attempt at checking finiteness of coxeter groups without using reals

d01cbb3  better algorithm, is_finite method and some tests

19c40bd  undoing edits to real_mpfr.pyx

1f3011c  trac #16630 separating the finite recognition algorithm

d48ef8b  trac #16630 correction of a typo in the doc

02c4161  trac #16630 trying to simplify type recognition

comment:25 Changed 7 years ago by
Ok, I think this is good to go. Can somebody review my commits ?
comment:26 Changed 7 years ago by
 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
comment:28 Changed 7 years ago by
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
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
comment:31 Changed 7 years ago by
 Commit changed from 02c4161a5a5eae6c5bff3aeee3e857ff22c9b422 to ad1d4cc48582a7596b6bc61f47a5c796e771efe6
comment:32 Changed 7 years ago by
So is this ok now ?
comment:33 Changed 7 years ago by
 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
 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
 Milestone changed from sage6.5 to sage6.6
comment:36 Changed 7 years ago by
 Status changed from positive_review to needs_work
sage t long warnlong 39.8 src/sage/groups/matrix_gps/coxeter_group.py # 2 doctests failed
comment:37 Changed 7 years ago by
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
 Commit changed from ad1d4cc48582a7596b6bc61f47a5c796e771efe6 to d1b9211eb55403bbfad3fb23adf127a92447ffb1
comment:39 Changed 7 years ago by
 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
 Branch changed from public/ticket/16630 to public/groups/fix_category_finite_coxeter16630
 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 cherrypicked your commits into this branch (since I don't want to upgrade my copy of Sage today).
New commits:
3597e2f  Merge branch 'public/groups/fix_category_finite_coxeter16630' of trac.sagemath.org:sage into public/groups/fix_category_finite_coxeter16630

0f5d819  trac #16630 replace base_ring by base_field

be4cdbf  trac #16630 adding a cardinality method.

49cc3bc  Changed cardinality() to order() and added Infinite refinement.

comment:41 Changed 7 years ago by
Looks good to me. If you agree, you can set a positive review.
comment:42 Changed 7 years ago by
I'm good with things; Darij?
comment:43 Changed 7 years ago by
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
 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
 Branch changed from public/groups/fix_category_finite_coxeter16630 to 49cc3bc1ecaba4b43f2ed426a8ebbfee6c77ddcd
 Resolution set to fixed
 Status changed from positive_review to closed
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:
Implement a bilinear_form method and use this to check finiteness.
Fixed _indefinite_factorization() for immutable matrix over fields.
Merge branch 'public/matrix/indefinite_factorization_immutable16633' into public/groups/fix_category_finite_coxeter16630
Expanded conversions for real numbers.
Merge branch 'public/rings/expand_RR_conversion16634' into public/groups/fix_category_finite_coxeter16630
Added doctests.
Some fixes for doctests.