Opened 9 years ago
Last modified 4 years ago
#11187 closed enhancement
Implementation of finite reflection groups — at Version 83
Reported by:  stumpc5  Owned by:  tbd 

Priority:  major  Milestone:  sage7.2 
Component:  combinatorics  Keywords:  reflection group, days49, days64.5, days80 
Cc:  vripoll, kdilks, SimonKing, jmichel, hivert  Merged in:  
Authors:  Christian Stump  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/stumpc5/11187new (Commits)  Commit:  e3b047bff2bd12f99a3fbea87f5417cd2c012745 
Dependencies:  #18620  Stopgaps: 
Description (last modified by )
This patch implements reflection groups to work with finite (crystallographic, real, complex) reflection groups. It is based on the GAP3 package chevie.
sage: W = ReflectionGroup(['A',2],5,23); W Reducible complex reflection group of rank 7 and type A2 x ST5 x H3 sage: W.irreducible_components() [Irreducible real reflection group of rank 2 and type A2, Irreducible complex reflection group of rank 2 and type ST5, Irreducible real reflection group of rank 3 and type H3]
Change History (84)
comment:1 Changed 9 years ago by
 Component changed from PLEASE CHANGE to combinatorics
 Status changed from new to needs_work
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
 Status changed from needs_work to needs_review
Apply only trac_11187finite_reflection_groupscs.patch
comment:4 Changed 9 years ago by
 Dependencies set to 8327
 Description modified (diff)
comment:5 Changed 9 years ago by
 Status changed from needs_review to needs_work
comment:6 Changed 9 years ago by
Apply only trac_11187finite_reflection_groupscs.patch
comment:7 Changed 9 years ago by
 Dependencies changed from 8327 to #8327
comment:8 Changed 9 years ago by
 Milestone set to sage4.7.2
Changed 7 years ago by
comment:9 Changed 7 years ago by
+ class SubcategoryMethods: + + @cached_method + def Irreducible(self): + """ + Returns the full subcategory of the irreducible objects of ``self``. + + EXAMPLES:: + + sage: CoxeterGroups().Irreducible() + Category of irreducible coxeter groups + + TESTS:: + + sage: AffineWeylGroups().Irreducible.__module__ + 'sage.categories.complex_reflection_groups' + """ + return self._with_adjectives(('Irreducible',)) + + class Irreducible(AdjectiveCategory): + pass +
comment:10 Changed 7 years ago by
 Dependencies changed from #8327 to #8327 #14137
I've factored out the CartanMatrix
class into #14137.
comment:11 followup: ↓ 12 Changed 6 years ago by
 Keywords days49 added
comment:12 in reply to: ↑ 11 Changed 6 years ago by
Replying to tscrim:
I've rebased the patch and noticed that this will likely depend on #10963. I'll post a new version once I completely untangle what is going on with #10963.
I always made some minor changes on this patch locally  I would actually only start working on this patch after you guys are finished with #10963. If you want to actively work on this patch, ping me again, and we can discuss what is still needed to finilize this patch.
Cheers, Christian
comment:13 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:14 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:15 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:16 followup: ↓ 17 Changed 5 years ago by
Hello Christian
Do you have a git branch for this ticket somewhere ? or should I try to resurrect the patch ?
comment:17 in reply to: ↑ 16 Changed 5 years ago by
Do you have a git branch for this ticket somewhere ? or should I try to resurrect the patch ?
No, I don't. But I have a local old version of Sage containing that code and quite a bit more, so I wonder if I should/will try to organize it a bit and put it up here.
Do you need any from that code in particular (in which case I am more tempted to work on that), or is that just a general question?
comment:18 Changed 5 years ago by
Hello, no, no real need for this code, just asking a general question. Now that #10963 is over.
comment:19 Changed 5 years ago by
 Branch set to public/groups/finite_reflection_groups11187
 Commit set to 1f3fe1e0caa28a1cb6e2d17a61d94c89460e2bd4
Here's a git version of this patch with changes necessary to get Sage to start (I did not run any tests, so I am not saying things are working). There might be other changes to the files in question which need to be moved over too. Just as a general note from doing the rebasing, there are a bunch of methods missing doctests.
New commits:
3489e1c  #11187 Implementation of finite reflection groups using the GAP3 package chevie

1f3fe1e  Some other fixes from changes to Sage in order to get Sage to start.

comment:20 Changed 5 years ago by
 Commit changed from 1f3fe1e0caa28a1cb6e2d17a61d94c89460e2bd4 to b60e61b6695fb1cde48d867390d50c32569fc2b0
comment:21 Changed 5 years ago by
 Commit changed from b60e61b6695fb1cde48d867390d50c32569fc2b0 to 1de360ff9e9c4db57e7de8b4ea45bbc4807e243c
Branch pushed to git repo; I updated commit sha1. New commits:
1de360f  trac #11187 crystallo takes 2 l

comment:22 Changed 5 years ago by
 Commit changed from 1de360ff9e9c4db57e7de8b4ea45bbc4807e243c to deb13e3c50d259c1708aaa815300d94045a14b07
Branch pushed to git repo; I updated commit sha1. New commits:
deb13e3  trac #11187 trying to make doctest pass

comment:23 Changed 5 years ago by
 Commit changed from deb13e3c50d259c1708aaa815300d94045a14b07 to b6c1a6273f96f1b5d6103b3090eee3633b2f54b2
Branch pushed to git repo; I updated commit sha1. New commits:
b6c1a62  trac #11187 a few more corrections

comment:24 Changed 5 years ago by
 Commit changed from b6c1a6273f96f1b5d6103b3090eee3633b2f54b2 to becb1cab8eacec6e60661677fb2c1fcfe2429afe
Branch pushed to git repo; I updated commit sha1. New commits:
becb1ca  trac #11187 a few more changes, removing duplicate functions

comment:25 Changed 5 years ago by
 Commit changed from becb1cab8eacec6e60661677fb2c1fcfe2429afe to e97998c532abc75eec6b18fecff6769601a1bade
comment:26 Changed 5 years ago by
 Commit changed from e97998c532abc75eec6b18fecff6769601a1bade to 03111c8373909a6f4ac8e7c8b63625c74b4077a5
Branch pushed to git repo; I updated commit sha1. New commits:
03111c8  trac #11187 a little pyflakes cleanup

comment:27 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:28 Changed 5 years ago by
 Commit changed from 03111c8373909a6f4ac8e7c8b63625c74b4077a5 to 4a37eac384b296acde87af5bddbe39a4ba8addf0
comment:29 Changed 5 years ago by
 Commit changed from 4a37eac384b296acde87af5bddbe39a4ba8addf0 to 527cb502a4f3729472344a7fbb894502ddd03050
Branch pushed to git repo; I updated commit sha1. New commits:
527cb50  Merge branch 'public/groups/finite_reflection_groups11187' into 6.6.b1

comment:30 Changed 5 years ago by
 Cc vripoll added
comment:31 Changed 5 years ago by
 Commit changed from 527cb502a4f3729472344a7fbb894502ddd03050 to f2fbe0ad1c694936e6d15195055c261aadc17e1d
Branch pushed to git repo; I updated commit sha1. New commits:
f2fbe0a  merged in 6.8.beta2

comment:32 Changed 5 years ago by
 Branch changed from public/groups/finite_reflection_groups11187 to u/stumpc5/11187
comment:33 Changed 5 years ago by
 Commit changed from f2fbe0ad1c694936e6d15195055c261aadc17e1d to ba7b5f092f41da9bbdb18455ecc5af2623dc42cc
Branch pushed to git repo; I updated commit sha1. New commits:
ba7b5f0  made Sage not crash on startup

comment:34 Changed 5 years ago by
 Cc kdilks added
comment:35 Changed 5 years ago by
 Branch changed from u/stumpc5/11187 to u/stumpc5/11187new
comment:36 Changed 5 years ago by
 Commit changed from ba7b5f092f41da9bbdb18455ecc5af2623dc42cc to 6ca40fa7459d11bf9c3564777d962a7493eb476c
comment:37 Changed 5 years ago by
 Commit changed from 6ca40fa7459d11bf9c3564777d962a7493eb476c to 33f93c6061d90dd3849525f63aa7ffaa21049492
Branch pushed to git repo; I updated commit sha1. New commits:
33f93c6  removed the magma iterator

comment:38 Changed 5 years ago by
 Commit changed from 33f93c6061d90dd3849525f63aa7ffaa21049492 to 08a782138c922172d901834b691a80ec850f9bb2
Branch pushed to git repo; I updated commit sha1. New commits:
08a7821  fixed all doctests in src/sage/combinat/root_system/complex_reflection_group.py

comment:39 Changed 5 years ago by
 Commit changed from 08a782138c922172d901834b691a80ec850f9bb2 to 014fec229c73bb16da7825d24633c47076f22c4c
Branch pushed to git repo; I updated commit sha1. New commits:
014fec2  got the doctests of complex reflection group category pass

comment:40 Changed 5 years ago by
 Commit changed from 014fec229c73bb16da7825d24633c47076f22c4c to d3198f92cb72fd0ca67c4118ddcb00289143bd62
Branch pushed to git repo; I updated commit sha1. New commits:
d3198f9  fixing a few bugs on coxeter number and fundamental invariants

comment:41 Changed 5 years ago by
 Commit changed from d3198f92cb72fd0ca67c4118ddcb00289143bd62 to 8db1deeed4893580fd7c88d42d2fb9366a895bcf
comment:42 Changed 5 years ago by
 Commit changed from 8db1deeed4893580fd7c88d42d2fb9366a895bcf to 425ca38c084a51fa56c301153165269031fb5e0d
Branch pushed to git repo; I updated commit sha1. New commits:
425ca38  first version of coxeter groups from chevie with all tests passing!

comment:43 Changed 5 years ago by
 Cc SimonKing added
comment:44 Changed 5 years ago by
The current code gives
sage: C = ComplexReflectionGroups() sage: C.Irreducible() Category of complex reflection groups sage: C.Irreducible() is C True
Is that what you intended? Perhaps the "irreducible" axiom should be defined on ComplexReflectionGroups().Finite()
, not on ComplexReflectionGroups()
.
comment:45 Changed 5 years ago by
To summarise the discussion Christian and I just had: I believe WellGenerated
should be an axiom. Christian said that the general notion of wellgenerated is a bit tricky for infinite groups. Hence, he actually only wants to take into account wellgeneratedness for finite complex reflection groups.
Hence, the aim would be to define WellGeneratedComplexReflectionGroups
as application of an axiom to ComplexReflectionGroups.Finite
. However, I believe that the name should contain the word "finite" if we really want to focus on finite wellgenerated groups. Alternatively, it should be implemented as a nestednested class WellGenerated
within the nested class ComplexReflectionGroups.Finite
.
I also think that WellGeneratedComplexReflectionGroups
should provide a parent method _test_well_generated
that tests whether self
is wellgenerated. Such method would automatically be executed when running the test suite.
comment:46 Changed 5 years ago by
We have discussed already that in order to fix the Irreducible
axiom, it is needed (in addition to the nested class) to have a SubcategoryMethod
called Irreducible
.
Note that if we define WellGeneratedComplexReflectionGroups
as a subcategory of ComplexReflectionGroups.Finite()
, we should probably remove its subcategorymethods Finite
and Irreducible
, since both axioms have already been defined in the supercategory.
comment:47 Changed 5 years ago by
The iterators currently cache the list of all elements of the group. Is that (always) a good idea?
comment:48 Changed 5 years ago by
 Branch changed from u/stumpc5/11187new to u/SimonKing/11187new
comment:49 Changed 5 years ago by
 Commit changed from 425ca38c084a51fa56c301153165269031fb5e0d to c0a036b2e2f01b1be6a7d004373fafe0c399e14d
After discussion with Christian, the iterator of a complex reflection group is a lot faster. What we did was to keep ._reduced_word
as a list, and only transform it into an actual word when needed (i.e., in the .reduced_word()
method).
Before:
sage: G = ComplexReflectionGroup([2,1,4]) sage: %timeit L = list(G); G._elements=None The slowest run took 6.02 times longer than the fastest. This could mean that an intermediate result is being cached 1 loops, best of 3: 66.4 ms per loop
After:
sage: G = ComplexReflectionGroup([2,1,4]) sage: %timeit L = list(G); G._elements=None The slowest run took 66.44 times longer than the fastest. This could mean that an intermediate result is being cached 1 loops, best of 3: 5.56 ms per loop
New commits:
c0a036b  Avoid creation of _reduced_word during iteration

comment:50 Changed 5 years ago by
 Branch changed from u/SimonKing/11187new to u/stumpc5/11187new
comment:51 Changed 5 years ago by
 Commit changed from c0a036b2e2f01b1be6a7d004373fafe0c399e14d to 0639665e4f6ac2bee4a4cc9dfcaed5963d910155
 Milestone changed from sage6.4 to sage6.8
comment:52 Changed 5 years ago by
 Commit changed from 0639665e4f6ac2bee4a4cc9dfcaed5963d910155 to 28f8abd2eb45700978592f1781a1f87e3c4d5e69
Branch pushed to git repo; I updated commit sha1. New commits:
28f8abd  added a test for well generated

comment:53 Changed 5 years ago by
Hi Christian,
This is not how the tests work:
def _test_well_generated(self, **options): tester = self._tester(**options) return self.is_well_generated()
Instead, do
def _test_well_generated(self, **options): tester = self._tester(**options) tester.assert_(self.is_well_generated())
or something similar.
comment:54 Changed 5 years ago by
see patchbot reports :
 some doctests should be marked with
# optional  chevie
or whatever  doctest continuation is now
....:
and not...
 raise statements should use py3 syntax
raise Error('message')
comment:55 Changed 5 years ago by
 Commit changed from 28f8abd2eb45700978592f1781a1f87e3c4d5e69 to 697cd3f3077ef749bee642e0281b24fc66c3cbeb
comment:56 followup: ↓ 58 Changed 5 years ago by
@Simon and Nicolas: The category for complex reflection groups (with axioms finite/irreducible/wellgenerated) is now sort of ready. I would now like to make ComplexReflectionGroups().Finite().WellGenerated()
a super category of FiniteCoxeterGroups
.
 Is that what I should do?
 If I simply add a method
supercategories
toFiniteCoxeterGroups
, its string repr changes in a not desired way. How should I treat that?
Thanks, Christian
comment:57 Changed 5 years ago by
 Commit changed from 697cd3f3077ef749bee642e0281b24fc66c3cbeb to 92ab198593eb2d772c48c4cfb80408d6da1daaa9
Branch pushed to git repo; I updated commit sha1. New commits:
92ab198  made the category of coxeter groups a subcategory of complex reflection groups

comment:58 in reply to: ↑ 56 Changed 5 years ago by
Replying to stumpc5:
@Simon and Nicolas: The category for complex reflection groups (with axioms finite/irreducible/wellgenerated) is now sort of ready. I would now like to make
ComplexReflectionGroups().Finite().WellGenerated()
a super category ofFiniteCoxeterGroups
.
 Is that what I should do?
 If I simply add a method
supercategories
toFiniteCoxeterGroups
, its string repr changes in a not desired way. How should I treat that?
It sounds more like you want to add ComplexReflectionGroups().WellGenerated()
as a supercategory to CoxeterGroups
, in particular to replace Groups().FinitelyGenerated()
by ComplexReflectionGroups().WellGenerated()
. I also think ComplexReflectionGroups()
should be a subcategory of Groups().FinitelyGenerated()
(otherwise the additional axiom should go on the supercategory for CoxeterGroups()
). The finite part will take care of itself by the CategoryWithAxiom
magic.
comment:59 Changed 5 years ago by
 Commit changed from 92ab198593eb2d772c48c4cfb80408d6da1daaa9 to abc690c06e9f6b60bde44f689259d3787d5681ea
Branch pushed to git repo; I updated commit sha1. New commits:
ec94ae3  added a few more doctests for CoxeterGroupsChevie

1878996  work in progress: new implementations are presumably correct, but existing bug discovered

5716df5  Fixed according to Travis's suggestions

4404133  Fixed according to Travis's suggestions, and now actually running I think

8fe1bb8  Tab fixed

a6dcb8b  merged with nowresolved conflicts

c37a5ef  things appear to work in the sense that all tests have passed.

1862325  removed trailing whitespace.

1f29ae6  reordered documentation, as requested by chapoton

abc690c  many doctests, and merged #18597

comment:60 followup: ↓ 62 Changed 5 years ago by
Hello,
 once again: doctest continuation is now
....:
and not...
 could you please put a positive review on the duplicate #9288 ?
comment:61 Changed 5 years ago by
 Commit changed from abc690c06e9f6b60bde44f689259d3787d5681ea to 742c0df5916cdd39d843553858f295df9a1ed18e
Branch pushed to git repo; I updated commit sha1. New commits:
742c0df  replaced '... ' by '....:'

comment:62 in reply to: ↑ 60 Changed 5 years ago by
Hi
 once again: doctest continuation is now
....:
and not...
done
 could you please put a positive review on the duplicate #9288 ?
done
Thanks for looking at this (and all the other tickets!
Christian
comment:63 Changed 5 years ago by
 Commit changed from 742c0df5916cdd39d843553858f295df9a1ed18e to df37b7e9dbec9913ad652826e165e7f534ded0d3
Branch pushed to git repo; I updated commit sha1. New commits:
ab914f5  first version of the subword complexes as of 2015

cb3ca9c  improve the subword complex, in particular its documentation

f105602  Merge branch 'u/stumpc5/11010' into u/stumpc5/11187new

8618845  playing, I hopefully can reorganize this again

ab4999f  more intelligent fix a la stump

df37b7e  Merge branch 't/18610/bug__circular_descent_check_in_weylgroups' into u/stumpc5/11187new

comment:64 Changed 5 years ago by
 Dependencies changed from #8327 #14137 to #8327 #14137 #18590
comment:65 Changed 5 years ago by
 Dependencies changed from #8327 #14137 #18590 to #8327 #14137 #18590 #18597
comment:66 Changed 5 years ago by
 Commit changed from df37b7e9dbec9913ad652826e165e7f534ded0d3 to e180c3133fb8c90f941b3f6f4be8a10e0bb15065
Branch pushed to git repo; I updated commit sha1. New commits:
e180c31  Revert "improve the subword complex, in particular its documentation"

comment:67 Changed 5 years ago by
 Commit changed from e180c3133fb8c90f941b3f6f4be8a10e0bb15065 to 450dadd370f2a8b1e6d05630d669742df3a1beef
Branch pushed to git repo; I updated commit sha1. New commits:
450dadd  Revert "first version of the subword complexes as of 2015"

comment:68 Changed 5 years ago by
I took out the subword complex stuff which is handled in #11010, and which is depending on this one.
comment:69 Changed 5 years ago by
 Commit changed from 450dadd370f2a8b1e6d05630d669742df3a1beef to e8e0d9ae9e5770b2088d6fb9ee6db412d21353a2
Branch pushed to git repo; I updated commit sha1. New commits:
e8e0d9a  added two doctests

comment:70 Changed 5 years ago by
 Dependencies changed from #8327 #14137 #18590 #18597 to #8327 #14137 #18590 #18597 #18620
comment:71 Changed 5 years ago by
 Dependencies changed from #8327 #14137 #18590 #18597 #18620 to #18620
comment:72 Changed 5 years ago by
 Commit changed from e8e0d9ae9e5770b2088d6fb9ee6db412d21353a2 to 80b9a54c6f35f6204fd226df8e95df45b05435d3
comment:73 Changed 5 years ago by
 Commit changed from 80b9a54c6f35f6204fd226df8e95df45b05435d3 to d98ee4ecfcdc337ba74ec9a008dd58a17239cfde
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
a89a90f  removed trailing whitespace.

ce30faf  reordered documentation, as requested by chapoton

21abe06  replaced '... ' by '....:'

4121914  improve the subword complex, in particular its documentation

b2b7f68  more intelligent fix a la stump

d662af6  Revert "improve the subword complex, in particular its documentation"

1ef2de7  Revert "first version of the subword complexes as of 2015"

03b60e2  added two doctests

2a34bef  added more doctests

d98ee4e  added more doctests, many more to come

comment:74 Changed 5 years ago by
 Commit changed from d98ee4ecfcdc337ba74ec9a008dd58a17239cfde to 294d5f8f513b74bae5de22221b069a21df1ed6f4
Branch pushed to git repo; I updated commit sha1. New commits:
294d5f8  fixed a docstring

comment:75 Changed 4 years ago by
 Commit changed from 294d5f8f513b74bae5de22221b069a21df1ed6f4 to eddaef5ada286366d9dc8d1f5af329f915c9da76
comment:76 Changed 4 years ago by
 Commit changed from eddaef5ada286366d9dc8d1f5af329f915c9da76 to fb852f57be8fe8897ee2c2bad7b4847c865476e8
Branch pushed to git repo; I updated commit sha1. New commits:
fb852f5  added back the references to __init__

comment:77 Changed 4 years ago by
 Commit changed from fb852f57be8fe8897ee2c2bad7b4847c865476e8 to 3783ea23dc6a102eea745f59cd2a6b48fb87d5ca
Branch pushed to git repo; I updated commit sha1. New commits:
3783ea2  added some stuff that got lost during rebasing

comment:78 Changed 4 years ago by
 Commit changed from 3783ea23dc6a102eea745f59cd2a6b48fb87d5ca to 43f1dcedca38ef310502c66f4bc9147040d2972a
Branch pushed to git repo; I updated commit sha1. New commits:
c07e76e  moved from ComplexReflectionGroup/CoxeterGroupChevie to ReflectionGroup

f845089  change in irreducible components

bbe138f  Merge branch 't/18620/9a3e5cdacac40b505f7aad0a62b9e1bec76d8f3a' into u/stumpc5/11187new

43f1dce  reflection groups in the reference

comment:79 Changed 4 years ago by
 Commit changed from 43f1dcedca38ef310502c66f4bc9147040d2972a to 2f737ce0ee193dc7de8b89586dc3939f2686c161
Branch pushed to git repo; I updated commit sha1. New commits:
2f737ce  got the documentation run again as expected

comment:80 Changed 4 years ago by
 Commit changed from 2f737ce0ee193dc7de8b89586dc3939f2686c161 to 9df16f6d63f7107669e9229211f9520aeb39a7ad
Branch pushed to git repo; I updated commit sha1. New commits:
9df16f6  cleaned the documentation of the complex reflection group category

comment:81 Changed 4 years ago by
 Commit changed from 9df16f6d63f7107669e9229211f9520aeb39a7ad to bfd9aa684127059d97777ad55432772322a78ebc
Branch pushed to git repo; I updated commit sha1. New commits:
bfd9aa6  added some references to ComplexReflectionGroups

comment:82 Changed 4 years ago by
 Commit changed from bfd9aa684127059d97777ad55432772322a78ebc to e3b047bff2bd12f99a3fbea87f5417cd2c012745
Branch pushed to git repo; I updated commit sha1. New commits:
e3b047b  added some references to ComplexReflectionGroups

comment:83 Changed 4 years ago by
 Description modified (diff)
 Keywords days 64.5 added
Apply only trac_11187finite_reflection_groupscs.patch