Opened 2 years ago

# non commutative coercion for submodules and permutation subgroups

Reported by: Owned by: vdelecroix critical sage-9.5 coercion tscrim, SimonKing, nbruin N/A

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)

1. 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 than `P.conjugacy_class(p)`.
2. 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)]
**********************************************************************
```

### comment:1 Changed 2 years ago by vdelecroix

• Description modified (diff)

### comment:2 follow-up: ↓ 4 Changed 2 years ago by 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.
• over inexact rings does the element need to know its parent? is that a use case?
• the submodule is in general not contained in the ambient module, e.g. `span(ZZ,[vector([1/2,1])])`

I would be +1 for solution 1.

### comment:3 Changed 2 years ago by embray

• Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

### comment:4 in reply to: ↑ 2 Changed 22 months ago by vdelecroix

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 22 months ago by 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?

### comment:6 in reply to: ↑ 5 Changed 22 months ago by vdelecroix

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:8 Changed 22 months ago by vdelecroix

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?

works for me

### comment:10 Changed 21 months ago by sbrandhorst

this should also solve #23576

### comment:11 Changed 19 months ago by mkoeppe

• Milestone changed from sage-9.1 to sage-9.2

### comment:12 Changed 13 months ago by mkoeppe

• Milestone changed from sage-9.2 to sage-9.3

### comment:13 Changed 8 months ago by mkoeppe

• Milestone changed from sage-9.3 to sage-9.4

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review.

### comment:14 Changed 3 months ago by mkoeppe

• Milestone changed from sage-9.4 to sage-9.5
Note: See TracTickets for help on using tickets.