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 vdelecroix)

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)]
**********************************************************************

Change History (12)

comment:1 Changed 13 months ago by vdelecroix

  • Description modified (diff)

comment:2 follow-up: Changed 10 months 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 10 months 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 8 months ago by vdelecroix

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

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 sbrandhorst

O.K. +1 please go ahead.

comment:8 Changed 8 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?

comment:9 Changed 8 months ago by sbrandhorst

works for me

comment:10 Changed 8 months ago by sbrandhorst

this should also solve #23576

comment:11 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

comment:12 Changed 10 hours ago by mkoeppe

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