Make subword complexes compatible with real reflection groups

[stumpc5]

The subword complex code was written and optimized for real reflection groups, but then made its way into Sage for Coxeter groups. This ticket is to make it handle both.

Depends on #20521

CC: @tscrim @fchapoton @nthiery @sagetrac-vripoll

Component: combinatorics

Keywords: reflection group, coxeter group, subword complex, days80

Author: Christian Stump

Branch/Commit: 71eba72

Reviewer: Frédéric Chapoton, Travis Scrimshaw

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

[stumpc5]

Dependencies: #11187

[stumpc5]

Branch: u/stumpc5/20402

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

2d70fab	trac #11187 more doc tuning
a04b9c8	Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
9c96d33	added ST type casting for real groups + documentation of crg's
5b1f2b0	Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
d4e7a61	working through the doctests for complex groups
d7b8c7d	fixing all doctests
7c9d700	Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
85d0ce1	fixed a typo in the doc
521d50b	Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
5ae3b7f	marked a missing doctest + fixed a bug to show type C2

[sagetrac-git]

Commit: 5ae3b7f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

72082b1	fixed a bug in noncrossing partition lattice and reflection/absolute order
844f450	Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
d425669	Fixing failures and some other things.
87cd989	fixed one doctest in category complex reflection group
05a8ab4	11187: fixed trivial doctest failures
32bf1ae	11187: cleanup of the organization of the various axioms (WellGenerated, ...) for complex/generalized reflection groups + documentation improvements
73276ca	Merge branch 'u/tscrim/11187' of trac.sagemath.org:sage into t/11187/11187
e074050	merged
b572c74	fixed a missing doctest
df55cdd	merged the newest version of 11187

[sagetrac-git]

Changed commit from 5ae3b7f to df55cdd

[sagetrac-git]

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

1927151

fixed a bug in simple_root_index

[sagetrac-git]

Changed commit from df55cdd to 1927151

[stumpc5]

comment:6

This ticket seems to be ready once #11187 has positive review.

[fchapoton]

comment:7

This is failing:

sage: a3r=ReflectionGroup(['A',3], base_ring=QQ)
sage: sr=SubwordComplex([1,3,2,1,3,2,1,3,2],a3r.w0)
sage: fr=sr.greedy_facet()
sage: fr.extended_weight_configuration()

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

0becba3	Merge branch 'public/11187' of git://trac.sagemath.org/sage into u/stumpc5/20396
8927ab9	matrix action is on the right!
eb2ea75	cleaned the reduced word code
6fbba18	undo the change to repr methods
8497f5d	first try to skip elements in the iteration, too slow
def7015	reorganized the invariant form (still missing an improvement) + fixed two doctests
ab73bc3	Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
b5a2c8d	moved all examles back to ReflectionGroup
e36ddad	added fundamental_weight to coxetergroup implementation
d6bc459	made all doctests work, but I used a dirty hack to solve the weight configuration

[sagetrac-git]

Changed commit from 1927151 to d6bc459

[sagetrac-git]

Changed commit from d6bc459 to a1b3d3b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

dc01066	started to add 'optional - gap3'
fd0c9cc	added optional gap3
1537a79	added optional gap3
a60cf31	added some missing optional gap3
feebf97	finalized the invariant form
4955d68	added the missing optional gap3 in the cython file
c5c43bc	the next round of optional gap3 insertions
244e6ff	Merge branch 'public/11187' of trac.sagemath.org:sage into public/reflection_groups-11187
f541349	Some last little beautification.
a1b3d3b	Merge branch 'u/stumpc5/11187' into u/stumpc5/20402

[sagetrac-git]

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

0db28d6	fixed doctests that have not been run last week!
7afc02c	Fixing doctests in combinat/root_system/coxeter_group.py.
0269425	Blanket fix bare except block.
9b0ef92	Making it an AttributeError.
87cdde0	Merge branch 'public/11187' into u/stumpc5/20402
8d76520	using a cached version self._number_of_reflections to avoid computing it again and again, expecially important in has_descent
0b6d895	Merge branch 'develop' into public/11187
e63d2ec	Merge branch 'public/11187' into u/stumpc5/20402

[sagetrac-git]

Changed commit from a1b3d3b to e63d2ec

[sagetrac-git]

Changed commit from e63d2ec to 0b81cd6

[sagetrac-git]

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

4bacaea	trivial typo
fc8a0aa	replaced the wrongly assumed right action by a left action
ef6dbac	fixed the action on root indices with left and right version
308f26b	added optional gap3 everywhere
0b81cd6	added a few missing optional gap3

[stumpc5]

comment:14

I think this is ready to go once the patchbots are happy!

[stumpc5]

Changed keywords from coxeter group, subword complex to reflection group, coxeter group, subword complex, days80

[sagetrac-git]

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

0ee1f3b

added a few more missing optional gap3

[sagetrac-git]

Changed commit from 0b81cd6 to 0ee1f3b

[tscrim]

comment:17

-1 to changing all of the examples to only using GAP3/reflection groups. Until GAP3 becomes an optional spkg, it means they become completely untested. Moreover, it is good to make sure the functionality works between different implementations.

I think there are a few things in here which need to be abstracted up to the category, root system code, and/or Coxeter type code. For example, is_crystallographic should be called on the Coxeter type, of which ReflectionGroup does not have and should (or perhaps the Coxeter matrix).

I also do not see the reason why this change is needed:

-                Lambda = {li: coeff[li] * Lambda[li] for li in Lambda}
+                Lambda = {li: coeff[li] * Lambda[li] for li in Lambda.keys()}

as the iteration for a dictionary is over its keys (and the former is faster and more memory efficient). With this change:

-                V_weights.append(pi * fund_weight)
+                # TODO: little hack to distinguish the implementations
+                #       for ReflectionGroups and CoxeterGroup
+                from sage.groups.perm_gps.permgroup_element import PermutationGroupElemen
+                if isinstance(pi,PermutationGroupElement):
+                    V_weights.append( sum(fund_weight[j]*Phi[ (~pi)(j+1)-1 ] for j in ran
+                else:
+                    V_weights.append(pi * fund_weight)

I think it would be better to have the fundamental weights handle the action of the reflection group element.

[stumpc5]

comment:52

I am still struggling with the left/right action -- here, we want left actions (i.e., matrix*vector), but the standard for reflection groups is right action. I know how to turn left to right action for real and for well-generated groups, but still don't get it right to have it for the badly generated groups.

Actually, this shouldn't hold this ticket of, but I haven't resorted things yet...

[sagetrac-git]

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

f0353a5

working out the left/right action

[sagetrac-git]

Changed commit from 619ba6e to f0353a5

[sagetrac-git]

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

5076f0b

Merge branch 'develop' into u/stumpc5/20402

[sagetrac-git]

Changed commit from f0353a5 to 5076f0b

[stumpc5]

Changed dependencies from #11187 to #11187, #20521

[sagetrac-git]

Changed commit from 5076f0b to 8ffeaf9

[sagetrac-git]

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

f25f5d6	take over the implementation from #20402
9e557e2	fixing a few doctests
c0ebcca	merged 20521
b5a56cc	added indirect doctest flags
8ffeaf9	Merge branch 'u/stumpc5/20521' into u/stumpc5/20402

[stumpc5]

Changed dependencies from #11187, #20521 to #20521

[sagetrac-git]

Changed commit from 8ffeaf9 to 03b1ae0

[sagetrac-git]

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

eaa9da0	Some minor reviewer changes.
e71529e	minor improvement of as_matrix + removal of todo note
03b1ae0	Merge branch 'u/stumpc5/20521' into u/stumpc5/20402

[stumpc5]

comment:59

I just rechecked -- beside the changes now moved to #20521 and the few changes in coxeter_groups.py, there are almost entirely newly added doctests for ReflectionGroup.

[tscrim]

comment:60

Instead of

print "Caution: the Minkowski summands are build with rational vertices."

(which it should be print("foo") to be Python3 compatible) you should use Sage's warning mechanism:

from warnings import warn
warn("foo", RuntimeWarning)

Otherwise LGTM.

[sagetrac-git]

Changed commit from 03b1ae0 to 71eba72

[sagetrac-git]

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

71eba72

using python warnings

[stumpc5]

comment:62

Done, thx also here! -- more improvements to come hopefully soon...

[stumpc5]

Reviewer: Frederic Chapoton, Travis Scrimshaw

[tscrim]

comment:63

Frédéric, Nicolas, anything else before setting this to a positive review?

[tscrim]

Changed reviewer from Frederic Chapoton, Travis Scrimshaw to Frédéric Chapoton, Travis Scrimshaw

[stumpc5]

comment:65

A quick ping here to check whether we can get this ticket merged...

[tscrim]

comment:66

If there is possibly anything else, then they can set this back from a positive review.

[vbraun]

Changed branch from u/stumpc5/20402 to 71eba72