Generalize SubspaceFunctor to CombinatorialFreeModule

[mkoeppe]

It currently uses:

    def _apply_functor(self, ambient):
        return ambient.span_of_basis(self.basis)

The method span_of_basis is only defined for the free modules of sage.modules. We generalize it to CombinatorialFreeModule (and all ModulesWithBasis).

Follow up: Handle the case of tensor modules of a FiniteRankFreeModule: only detect whether the given basis is one of the submodules with prescribed symmetries from #30229; in all other cases, we raise NotImplementedError.

CC: @tscrim @egourgoulhon @simon-king-jena

Component: linear algebra

Author: Matthias Koeppe

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

[mkoeppe]

Description changed:

--- 
+++ 
@@ -4,4 +4,7 @@
     def _apply_functor(self, ambient):
         return ambient.span_of_basis(self.basis)

-The method span_of_basis is only defined for the free modules of sage.modules +The method span_of_basis is only defined for the free modules of sage.modules. + +For the case of tensor modules of a FiniteRankFreeModule, we only detect whether the given basis is one of the submodules with prescribed symmetries from #30229; in all other cases, we raise NotImplementedError. +

[mkoeppe]

comment:2

This is complicated by the special treatment of dense integer free modules in span_of_basis (vaguely related: #29315)

[mkoeppe]

Branch: u/mkoeppe/generalize_subspacefunctor_to_combinatorialfreemodule_and_finiterankfreemodule

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

bf5b2c9	src/sage/categories/modules_with_basis.py (ModulesWithBasis.Subobjects): Add construction
9414bc4	src/sage/categories/pushout.py (SubspaceFunctor): WIP add doctest

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: 9414bc4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9414bc4 to c1e771b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c1e771b

src/sage/categories/pushout.py (SubspaceFunctor): Generalize to ModulesWithBasis

[mkoeppe]

Author: Matthias Koeppe

[mkoeppe]

Description changed:

--- 
+++ 
@@ -4,7 +4,7 @@
     def _apply_functor(self, ambient):
         return ambient.span_of_basis(self.basis)

-The method span_of_basis is only defined for the free modules of sage.modules. +The method span_of_basis is only defined for the free modules of sage.modules. We generalize it to CombinatorialFreeModule (and all ModulesWithBasis).

-For the case of tensor modules of a FiniteRankFreeModule, we only detect whether the given basis is one of the submodules with prescribed symmetries from #30229; in all other cases, we raise NotImplementedError. +Follow up: Handle the case of tensor modules of a FiniteRankFreeModule: only detect whether the given basis is one of the submodules with prescribed symmetries from #30229; in all other cases, we raise NotImplementedError.

[mkoeppe]

Changed dependencies from #30229 to none

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c7b85db

ModulesWithBasis.ParentMethods.construction: Add doctest

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c1e771b to c7b85db

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c7b85db to 089188f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

089188f

src/sage/categories/modules_with_basis.py: Update doctest output

[tscrim]

comment:12

I am somewhat hesitant to have the construction be defined at the category level because it is such a universal method (mainly, construction as a what?; cf. gens()). For the tensor products, that carries functorial properties that subspaces do not do. Typically we add structure to submodules. In other words, it is common to have (mathematically) a specific algebra defined as a submodule of linear transformations (the classical Lie algebras are important examples). Of course, that is not how we have generally implemented them in Sage, but it wouldn’t be wrong to, say, have the Lie algebra sl_n of traceless n x n matrices be in the join category LieAlgebras(R) & Modules(R).Subobjects() (although this would lead to other conflicts with their relationship with their universal enveloping algebra and considering them as a Lie subalgebra of that (under the commutator bracket)). So the test suite would fail unless the user provides a constructor method.

For tensor/Cartesian products, they are almost always built from more fundamental objects as inputs that funnels into a few classes. In particular, one can easily identify what class should be used to make, e.g., tensor products. So I feel the trade off is in favor of doing it at the category level. This is in contrast to here, where we cannot have any such distinguished class.

[mkoeppe]

comment:13

Does this concern go away if I move this method to sage.modules.with_basis.subquotient.SubmoduleWithBasis?

[tscrim]

comment:14

Yes, it does. If it is done there, then it is a specific class with a specific implementation. Things at the category level should (generally) be implementation agnostic.

[mkoeppe]

comment:15

... except that the category does invoke that class in its submodule method.

[tscrim]

comment:16

It is a generic implementation and it is the best attempt at doing something without making it an @abstract_method(optional=True). The SubmoduleWithBasis should, in principle, work with anything in the category. Unfortunately I don’t think we are quite at that reality yet.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9f7d4fc

SubmoduleWithBasis.construction: Move here from ModulesWithBasis.Subobjects

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 089188f to 9f7d4fc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

2ad074d

SubmoduleWithBasis.construction: Move here from ModulesWithBasis.Subobjects

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9f7d4fc to 2ad074d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6536b72

FiniteDimensionalModulesWithBasis.Subobjects: New

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2ad074d to 6536b72

[mkoeppe]

comment:20

Is there a way to shorten "Category of subobjects of modules with basis over Integer Ring" to "Category of submodules with basis over Integer Ring"?

[mkoeppe]

comment:21

There a few failures of _test_construction tests. At least one of them is a case where the equality of a UniqueRepresentation is too strict:

sage: from sage.modules.with_basis.subquotient import SubmoduleWithBasis
sage: X = CombinatorialFreeModule(QQ, range(3), prefix="x"); x = X.basis()
sage: ybas = (x[0]-x[1], x[1]-x[2])
sage: Y = SubmoduleWithBasis(ybas, [0, 1, 2], X)
sage: Y.print_options(prefix='y')
sage: F, B = Y.construction()
sage: Y2 = F(B)
sage: Y2
Free module generated by {0, 1} over Rational Field
sage: Y
Free module generated by {0, 1} over Rational Field
sage: Y2.basis()
Finite family {0: B[0], 1: B[1]}
sage: Y.basis()
Finite family {0: y[0], 1: y[1]}
sage: Y == Y2
False
sage: Y.is_submodule(Y2)
True
sage: Y2.is_submodule(Y)
True

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6536b72 to 1ed6b44

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1ed6b44

SubspaceFunctor, SubmoduleWithBasis.construction: Handle support_order

[tscrim]

comment:24

Replying to Matthias Köppe:

Is there a way to shorten "Category of subobjects of modules with basis over Integer Ring" to "Category of submodules with basis over Integer Ring"?

Not generically, but you can override the name of the category. You could obviously write a _repr_(), but I forget offhand if there is some other way to just set the short name of the category (I believe there is though).

[tscrim]

comment:25

Replying to Matthias Köppe:

There a few failures of _test_construction tests. At least one of them is a case where the equality of a UniqueRepresentation is too strict:

This suggests to me that the functor construction is not preserving enough properties.

Furthermore == does not have to mean mathematical equality either (what if we chose different indexing sets for the submodules?). Dealing with equal-but-not-identical parents can offer up another set of painful and subtle issues with equality and coercion. Plus we aren’t able to utilize things cached with the submodule if we compute it a second time.

There are trade offs with any way we decide to implement them, but it is not fair to call it too strict.

[mkoeppe]

comment:26

Replying to Travis Scrimshaw:

it is not fair to call it too strict.

To be clear, I'm not criticizing UniqueRepresentation for its moral stance ;)

[tscrim]

comment:27

Of course, but I am still wondering what would be a reasonable way to define ==. Right now it is doing it the most conservative way, so things like the prefix and indexing set distinguish subspaces. However, unlike for a general module, the fact that it is a submodule means there is a canonical way to represent elements (as elements of the ambient space with its distinguished basis). I am still vary wary of effects of coercion (including coercions between the equal subspaces) with equal-but-not-identical, but that might take actually changing things to see what happens. It does make sense to downgrade the subspaces to a CachedRepresentation.

Actually, perhaps we can get a best of both worlds. We just need to extend the submodule class to somehow handle multiple indexing sets and just inform the users that the prefix is unique. In general, I expect this to a infrequently used feature, but it would be good to support the different indexing sets.

[tscrim]

comment:28

Either way, I still think the construction functor needs to better reconstruct the object too.

[mkoeppe]

Removed branch from Issue description; replaced by PR #37528.