Opened 13 months ago
Last modified 10 hours ago
#28544 new defect
non commutative coercion for submodules and permutation subgroups
Reported by: | vdelecroix | Owned by: | |
---|---|---|---|
Priority: | critical | Milestone: | sage-9.3 |
Component: | coercion | Keywords: | |
Cc: | tscrim, SimonKing, nbruin | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The current coercion models try to be smart with submodules and permutation subgroups. More precisely, given an ambient free module
sage: V = QQ^4
and two submodules
sage: U1 = V.submodule([[1,3,2,4]]) sage: U2 = V.submodule([[0,1,0,1], [2,0,-1,-1]])
binary +
between U1
and U2
is allowed and belongs to the "smallest" possible submodule
sage: parent(U1.an_element() + U2.an_element()) Vector space of degree 4 and dimension 3 over Rational Field User basis matrix: [ 1 0 0 -1/5] [ 0 1 0 1] [ 0 0 1 3/5]
The same holds for permutation groups
sage: S = SymmetricGroup(5) sage: P1 = S.subgroup(['(1,2)', '(3,4)']) sage: P2 = S.subgroup(['(3,4,5)']) sage: parent(P1.an_element() * P2.an_element()) Permutation Group with generators [(3,4), (3,4,5), (1,2)]
In both examples above the coercion is commutative
sage: parent(U1.an_element() + U2.an_element()) is \ ....: parent(U2.an_element() + U1.an_element()) True sage: parent(P1.an_element() * P2.an_element()) is \ ....: parent(P2.an_element() * P1.an_element()) True
Beyond the fact that computing this submodule is computationally expensive and most probably useless, it leads to the following non-commutativity when the two submodules are equal but not identical
sage: U1 = V.subspace([[1,2,3,4]]) sage: U2 = V.subspace([[1,2,3,4]]) False sage: U1 is U2 False sage: U1 == U2 True sage: parent(U1.an_element() + U2.an_element()) is U1 True sage: parent(U2.an_element() + U1.an_element()) is U2 True
The exact same problem is happening with permutation groups
sage: P1 = S.subgroup(['(3,4)', '(1,2,3)(4,5)']) sage: P2 = S.subgroup(['(3,4)', '(1,2,3)(4,5)']) sage: parent(P1.one() * P2.one()) is P1 True sage: parent(P1.an_element() * P2.an_element()) is P1 True sage: parent(P2.an_element() * P1.an_element()) is P2 True
There are at least two ways to solve the problem (that would also solve avoid the computation of the minimal parent)
- make submodules facade (ie the elements would have parent the ambient module). This might not be desirable since the user might want to use something such as
p.conjugacy_class()
rather thanP.conjugacy_class(p)
. - when operation is performed between element of non-identical submodules, both elements are promoted to the ambient submodule
Note: I stumbled upon this while working on #28539 from which I suddenly obtained some
********************************************************************** File "categories/group_algebras.py", line 398, in sage.categories.group_algebras.GroupAlgebras.ElementMethods.central_form Failed example: sum(i for i in QG.basis()).central_form() Exception raised: Traceback (most recent call last): File "/opt/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 681, in _run self.compile_and_execute(example, compiler, test.globs) File "/opt/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute exec(compiled, globs) File "<doctest sage.categories.group_algebras.GroupAlgebras.ElementMethods.central_form[7]>", line 1, in <module> sum(i for i in QG.basis()).central_form() File "/opt/sage/local/lib/python3.7/site-packages/sage/categories/group_algebras.py", line 409, in central_form return sum(self[i] * Z.basis()[i] for i in Z.basis().keys()) File "/opt/sage/local/lib/python3.7/site-packages/sage/categories/group_algebras.py", line 409, in <genexpr> return sum(self[i] * Z.basis()[i] for i in Z.basis().keys()) File "sage/modules/with_basis/indexed_element.pyx", line 656, in sage.modules.with_basis.indexed_element.IndexedFreeModuleElement.__getitem__ (build/cythonized/sage/modules/with_basis/indexed_element.c:7365) res = self._monomial_coefficients.get(m) File "sage/structure/element.pyx", line 1093, in sage.structure.element.Element.__richcmp__ (build/cythonized/sage/structure/element.c:9946) return coercion_model.richcmp(self, other, op) File "sage/structure/coerce.pyx", line 1931, in sage.structure.coerce.CoercionModel.richcmp (build/cythonized/sage/structure/coerce.c:19587) x, y = self.canonical_coercion(x, y) File "sage/structure/coerce.pyx", line 1291, in sage.structure.coerce.CoercionModel.canonical_coercion (build/cythonized/sage/structure/coerce.c:11670) self._coercion_error(x, x_map, x_elt, y, y_map, y_elt) File "sage/structure/coerce.pyx", line 1989, in sage.structure.coerce.CoercionModel._coercion_error (build/cythonized/sage/structure/coerce.c:20330) raise RuntimeError("""There is a bug in the coercion code in Sage. RuntimeError: There is a bug in the coercion code in Sage. Both x (=()) and y (=()) are supposed to have identical parents but they don't. In fact, x has parent 'Permutation Group with generators [(3,4), (1,2,3)(4,5)]' whereas y has parent 'Permutation Group with generators [(3,4), (1,2,3)(4,5)]' Original elements () (parent Permutation Group with generators [(3,4), (1,2,3)(4,5)]) and () (parent Permutation Group with generators [(3,4), (1,2,3)(4,5)]) and maps <class 'NoneType'> None <class 'sage.structure.coerce_maps.DefaultConvertMap_unique'> (map internal to coercion system -- copy before use) Coercion map: From: Permutation Group with generators [(3,4), (1,2,3)(4,5)] To: Permutation Group with generators [(3,4), (1,2,3)(4,5)] **********************************************************************
Change History (12)
comment:1 Changed 13 months ago by
- Description modified (diff)
comment:2 follow-up: ↓ 4 Changed 10 months ago by
comment:3 Changed 10 months ago by
- Milestone changed from sage-9.0 to sage-9.1
Ticket retargeted after milestone closed
comment:4 in reply to: ↑ 2 Changed 8 months ago by
Replying to sbrandhorst:
In principle I agree with you that submodules are bad parents for elements when the ambient is nice and they are represented as ambient elements anyways. It means that one has to do tons of trivial coercions when calculating with elements different submodules.
Here are some thoughts in the case of modules:
- it seems to be a big design change to make submodules facades and break a lot of code. For instance the result of e.parent() will changes and probably that is used often.
Fixing the issue is to my mind more important than breaking code.
- over inexact rings does the element need to know its parent? is that a use case?
Submodules are just broken for inexact ring. I think we should just disallow (or redesign) them.
sage: V = VectorSpace(RDF,3) sage: v1 = V([1.1, 2.3, 2.3**50]) sage: v2 = V([5.3**10, -1.1, 3.9]) sage: M = V.submodule([v1, v2]) sage: v1 in M True sage: v2 in M False
- the submodule is in general not contained in the ambient module, e.g.
span(ZZ,[vector([1/2,1])])
This is not a submodule but a submodule of V ⊗ 𝑸
(note that you explicitely used span
). But you are right, the result of span(ZZ, [vector([1/2,1])])
needs a proper parent.
I would be +1 for solution 1.
comment:5 follow-up: ↓ 6 Changed 8 months ago by
One last thought in the case of permutation groups: Is containment checking fast/ easy? Because if it is not then we are really forgetting information and solution 2 seems better. For free modules over PIDs that is trivial ofcourse. How are other computeralgebra systems doing this? Gap, Magma?
comment:6 in reply to: ↑ 5 Changed 8 months ago by
Replying to sbrandhorst:
One last thought in the case of permutation groups: Is containment checking fast/ easy? Because if it is not then we are really forgetting information and solution 2 seems better. For free modules over PIDs that is trivial ofcourse. How are other computeralgebra systems doing this? Gap, Magma?
For permutation groups containment is reasonably fast (Schreier-Sims).
comment:7 Changed 8 months ago by
O.K. +1 please go ahead.
comment:8 Changed 8 months ago by
A smoother transition would be to implement 2 in this ticket. And then, in a further ticket, implement a "facade" option for these substructures. Would that be ok?
comment:9 Changed 8 months ago by
works for me
comment:10 Changed 8 months ago by
this should also solve #23576
comment:11 Changed 6 months ago by
- Milestone changed from sage-9.1 to sage-9.2
comment:12 Changed 10 hours ago by
- Milestone changed from sage-9.2 to sage-9.3
In principle I agree with you that submodules are bad parents for elements when the ambient is nice and they are represented as ambient elements anyways. It means that one has to do tons of trivial coercions when calculating with elements different submodules.
Here are some thoughts in the case of modules:
span(ZZ,[vector([1/2,1])])
I would be +1 for solution 1.