Add modules over integral domain

[kwankyu]

Modules over integral domain lack basic functionality:

sage: S.<x,y,z,w> = PolynomialRing(QQ)
sage: A = S**2
sage: A
Ambient free module of rank 2 over the integral domain Multivariate Polynomial Ring in x, y, z, w over Rational Field
sage: A.submodule([vector([x-y,z-w]), vector([y*z, x*w])])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-7-cabbcc8d5285> in <module>
----> 1 A.submodule([vector([x-y,z-w]), vector([y*z, x*w])])

~/GitHub/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/categories/modules_with_basis.py in submodule(self, gens, check, already_echelonized, unitriangular, support_order, category, *args, **opts)
    876             support_order = self._compute_support_order(gens, support_order)
    877             if not already_echelonized:
--> 878                 gens = self.echelon_form(gens, unitriangular, order=support_order)
    879 
    880             from sage.modules.with_basis.subquotient import SubmoduleWithBasis

~/GitHub/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/categories/finite_dimensional_modules_with_basis.py in echelon_form(self, elements, row_reduced, order)
    367             order = self._compute_support_order(elements, order)
    368             from sage.matrix.constructor import matrix
--> 369             mat = matrix(self.base_ring(), [g._vector_(order=order) for g in elements])
    370             # Echelonizing a matrix over a field returned the rref
    371             if row_reduced and self.base_ring() not in Fields():

~/GitHub/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/categories/finite_dimensional_modules_with_basis.py in <listcomp>(.0)
    367             order = self._compute_support_order(elements, order)
    368             from sage.matrix.constructor import matrix
--> 369             mat = matrix(self.base_ring(), [g._vector_(order=order) for g in elements])
    370             # Echelonizing a matrix over a field returned the rref
    371             if row_reduced and self.base_ring() not in Fields():

~/GitHub/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/free_module_element.pyx in sage.modules.free_module_element.FreeModuleElement._vector_ (build/cythonized/sage/modules/free_module_element.c:9892)()
   1141         return hash(tuple(self))
   1142 
-> 1143     def _vector_(self, R=None):
   1144         r"""
   1145         Return self as a vector.

TypeError: _vector_() got an unexpected keyword argument 'order'

We improve the situation by adding modules over integral domains. Thus we can do at least

sage: S.<x,y,z,w> = PolynomialRing(QQ)
sage: A = S**2
sage: A
Ambient free module of rank 2 over the integral domain Multivariate Polynomial Ring in x, y, z, w over Rational Field
sage: N = A.submodule([vector([x-y,z-w]), vector([y*z, x*w])])
sage: N
Submodule of Ambient free module of rank 2 over the integral domain Multivariate Polynomial Ring in x, y, z, w over Rational Field
Generated by the rows of the matrix:
[x - y z - w]
[  y*z   x*w]
sage: Q = A.quotient(N)
sage: Q
Quotient module by Submodule of Ambient free module of rank 2 over the integral domain Multivariate Polynomial Ring in x, y, z, w over Rational Field
Generated by the rows of the matrix:
[x - y z - w]
[  y*z   x*w]

Depends on #33985
Depends on #34040

CC: @tscrim @jhpalmieri

Component: algebra

Author: Kwankyu Lee, Travis Scrimshaw

Branch/Commit: f58d2f3

Reviewer: Travis Scrimshaw, Kwankyu Lee

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

[kwankyu]

comment:1

I see many module-related methods accept this order argument. It is not immediately clear what is the role of this argument. I guess it gives an "order" to the basis...

[jhpalmieri]

comment:3

As dimpase pointed out on sage-devel, many things are just not implemented for modules over infinite-dimensional rings. The recently added modules/fp_graded (finitely presented modules over graded connected rings) implements some things, but only in a graded setting.

[kwankyu]

comment:4

Replying to @jhpalmieri:

As dimpase pointed out on sage-devel, many things are just not implemented for modules over infinite-dimensional rings. The recently added modules/fp_graded (finitely presented modules over graded connected rings) implements some things, but only in a graded setting.

I see. I forgot that... Anyway I will think of a way to raise an exception less surprising in such cases, or provide a simple implementation of submodules of such ambient modules.

I was working with morphisms between modules over multivariate polynomial rings, and tried to get the image and the kernel of a morphism. I did't know even submodules are not in place...

[kwankyu]

comment:5

Replying to @jhpalmieri:

The recently added modules/fp_graded (finitely presented modules over graded connected rings) implements some things, but only in a graded setting.

Actually what I need is submodules of free modules (of finite rank) over graded multivariate polynomial rings. The grading may be multigrades, that is, by integer vectors. Then are these modules included in fp_graded modules?

[tscrim]

comment:6

Replying to @kwankyu:

Replying to @jhpalmieri:

The recently added modules/fp_graded (finitely presented modules over graded connected rings) implements some things, but only in a graded setting.

Actually what I need is submodules of free modules (of finite rank) over graded multivariate polynomial rings. The grading may be multigrades, that is, by integer vectors. Then are these modules included in fp_graded modules?

I don't know how well tested the code is for multigradings, but in principle it should work. The biggest issue I think is polynomial rings do not know they are multigraded. We can hack around this with an appropriate subclass of CombinatorialFreeModule that uses a free monoid as its indexing set. However, do not expect algebraic operations to be fast, or have some other polynomial features like division, Gröbner bases, etc.

The easiest fix for this issue would probably be to just modify the _vector_ to take order and ignore it. I can't promise there won't be another compatibility issue, but we can fix those as we encounter them.

[kwankyu]

comment:7

Replying to @tscrim:

I don't know how well tested the code is for multigradings, but in principle it should work. The biggest issue I think is polynomial rings do not know they are multigraded. We can hack around this with an appropriate subclass of CombinatorialFreeModule that uses a free monoid as its indexing set. However, do not expect algebraic operations to be fast, or have some other polynomial features like division, Gröbner bases, etc.

Moreover, these modules like fp_graded seem intended for modules over algebras and these algebras are not primarily commutative. I see "graded commutative" in sage.algebras.commutative_dga, but this is not "graded" + "commutative".

These seem to be not proper tools to work with the usual graded polynomials rings and modules needed for computational commutative algebra and algebraic geometry.

The easiest fix for this issue would probably be to just modify the _vector_ to take order and ignore it.

Okay. I thought of that, but was not sure if that is a right way. Thanks.

[tscrim]

comment:8

Replying to @kwankyu:

Replying to @tscrim:

I don't know how well tested the code is for multigradings, but in principle it should work. The biggest issue I think is polynomial rings do not know they are multigraded. We can hack around this with an appropriate subclass of CombinatorialFreeModule that uses a free monoid as its indexing set. However, do not expect algebraic operations to be fast, or have some other polynomial features like division, Gröbner bases, etc.

Moreover, these modules like fp_graded seem intended for modules over algebras and these algebras are not primarily commutative.

That is true. They are meant to work with general (likely associative unital) algebras. It does not have the linear algebra quite so close at hand, but they might fair a bit better when moving outside of free modules. We need to have more native support for non-free modules, some of which for commutative base rings can be pulled from singular.

These seem to be not proper tools to work with the usual graded polynomials rings and modules needed for computational commutative algebra and algebraic geometry.

I don't quite know what you are hoping to compute as it is a bit too far outside of my area. The code here can do some homological algebra. John might know more about how it could be applied.

PS - The order argument is for free modules that do not necessarily have a fixed/well-defined ordering of the basis elements. However, to (efficiently) do the linear algebra, we need to chose an ordering of the basis to manipulate the matrices. Thus this is used to convert to/from the implementation with a fixed ordering.

[kwankyu]

comment:9

Replying to @tscrim:

I don't quite know what you are hoping to compute as it is a bit too far outside of my area. The code here can do some homological algebra. John might know more about how it could be applied.

I am working on graded free resolutions of graded modules over polynomial rings, pulling the resolution machinery of Singular. Hence I really don't need to compute with the modules in Sage, but just need the framework. As it is not there, perhaps I can work with matrices instead.

PS - The order argument is for free modules that do not necessarily have a fixed/well-defined ordering of the basis elements. However, to (efficiently) do the linear algebra, we need to choose an ordering of the basis to manipulate the matrices. Thus this is used to convert to/from the implementation with a fixed ordering.

Thanks for explanation.

[kwankyu]

Branch: u/klee/33868

[kwankyu]

Author: Kwankyu Lee

[sagetrac-git]

Commit: f5865c4

[sagetrac-git]

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

f5865c4

Add modules over integral domain

[kwankyu]

comment:12

I decided to follow Dima's idea, to implement modules over domain. This just amount to insert a class for "modules over domain" between "modules over ring" and "modules over pid". Refactoring thus gives some (trivial) functions to modules over domain.

[sagetrac-git]

Changed commit from f5865c4 to 4334794

[sagetrac-git]

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

4334794

Fix some super() to avoid errors

[kwankyu]

comment:19

As submodules of modules over domain may lack a (linearly independent) basis, the "quick fix" code needs more thought...

[kwankyu]

Changed branch from u/tscrim/modules_integral_domain-33868 to public/33868

[sagetrac-git]

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

4f047a4	Trying to streamline the quotient module implementation.
24b3384	Better use of submodules and some other fixes.
bc89b63	Merge branch 'u/tscrim/modules_integral_domain_noquo-33868' into u/tscrim/modules_integral_domain-33868
b63957a	Better handling of submodule checking.
8585adb	Submodules of submodules should respect the defining module.
9bd6f89	Revert change to quotient modules.
568097b	Standardizing submodules as subquotients.
280e8a7	Adding support for quotients of quotients.
1ca0d64	Removing code duplication of span() and submodule().
1baa006	Rename subquotient back to submodule

[sagetrac-git]

Commit: 1baa006

[sagetrac-git]

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

4a9446c

Fix a title

[sagetrac-git]

Changed commit from 1baa006 to 4a9446c

[kwankyu]

comment:100

I am also happy overall with the new design.

I did minor edits. I renamed Subquotient_free_module back to Submodule_free_quotient as subquotients are also submodules of the ambient module, which is a quotient module in this case. This name also matches with the filename. I reverted back the domain argument of QuotientModule_free_ambient to module as domain may be misunderstood as integral domain.

[kwankyu]

comment:101

Ah, I removed the degree 1 case in is_submodule test. It is trivial case and the test is wrong. Your test would give false for M.is_submodule(N) with N=(3,5), M=(2)overZZ`.

[tscrim]

comment:102

Replying to @kwankyu:

Ah, I removed the degree 1 case in is_submodule test. It is trivial case and the test is wrong. Your test would give false for M.is_submodule(N) with N=(3,5), M=(2) over ZZ.

Right, it is not an if-and-only-if due to linear combinations... This really should have been checking for general cases if we can scale the generators by checking the divisibility of the leading coefficients and only return True if that was the case. Anyways, it isn't so important for now.

[tscrim]

comment:103

Replying to @kwankyu:

I am also happy overall with the new design.

Thank you for dealing with me as I worked on it.

I did minor edits. I renamed Subquotient_free_module back to Submodule_free_quotient as subquotients are also submodules of the ambient module, which is a quotient module in this case. This name also matches with the filename.

These are good.

I reverted back the domain argument of QuotientModule_free_ambient to module as domain may be misunderstood as integral domain.

I am 99% okay with this. I just have a very slight reservation that it doesn't make the free module version. Yet, it is not public facing and the classes are currently separate (although IMO they should not be), so this is okay with me.

If everything else is good, then I think we can set a positive review once a patchbot takes a look at it.

[sagetrac-git]

Changed commit from 4a9446c to 0b3b860

[sagetrac-git]

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

0b3b860

Fix a doctest

[sagetrac-git]

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

cd28605

Some more edits

[sagetrac-git]

Changed commit from 0b3b860 to cd28605

[kwankyu]

comment:107

Replying to @tscrim:

Replying to @kwankyu:

I am also happy overall with the new design.

Thank you for dealing with me as I worked on it.

This ticket achieved much more than I first envisioned. It laid a groundwork to elevate Sage as an alternative platform for commutative algebra computations.

[tscrim]

comment:108

Thank you for the changes. There is still work that can be done; in particular things for modules over polynomial rings (possibly using, e.g., singular to do the computations). However, that is all good for followup tickets.

[vbraun]

comment:109

Merge failure on top of:

8f2fe518a7 Trac #33708: make elliptic-curve isogenies compute Montgomery codomains

86ddb48e2f Trac #33144: Remove some py2 tags in explain_pickle

30ecff9f6d Trac #34085: fix some details in braid groups

3755f58519 Trac #34082: Add an option up_to_isomorphism for is_subgraph

92c75af48c Trac #34080: pycodestyle cleanup in src/sage/graphs/digraph.py

ca49485d88 Trac #34062: enhance our conversion system

1da48e72af Trac #34052: tweaking the giac / libgiac interface

21a14a9dce Trac #34049: fix wrong use of Path inside libgap.Read

d73e3d7af7 Trac #34045: OpenSSL 3.0.4 security update

b617c66a07 Trac #34040: fix W605 in all pyx files inside matrix/

ca041b6034 Trac #34039: fix pycodestyle E306 in categories and part of combinat

2c9b6f0230 Trac #34029: bug in elliptic curve saturation: update to eclib bugfix release 20220621 required.

b2b107f016 Trac #34006: Fix the Killing form and generators for a Lie subalgebra

963b374cb1 Trac #33995: make test: Log to a common log file test.log

e3ceba0a60 Trac #33928: phitigra error with hold_canvas

b5d0423a3f Trac #33866: Make jupyter_packaging standard; add hatchling, editables, pathspec, poetry_core, tomlkit, deprecation; update tomli, flit_core, setuptools, pip, wheel

dd6e379e27 Trac #33821: Remove use of SAGE_LIB in sage.misc

2bd081ee38 Trac #33409: Size of docker images has increased in 9.5

1f77ce0ac9 Trac #33295: Refactor sage_conf

3b0dc53967 Trac #33029: Feature and doctest tag for runtime cython

226f4353c3 Trac #29779: pkgconf: Update to 1.8.0, remove runtime dep on environment variable SAGE_LOCAL

548795354e Trac #29549: bootstrap: Clean up use of gettextize

c02edcb Trac #25374: Upgrade cryptominisat to 5.8.0, fix build on Cygwin

e22b33a Trac #34017: Fix tox-docker builds after #29941

c4236d0 Trac #34008: pycodestyle cleanup in sage.graphs.generic_graph_pyx.pyx

6f961ff Trac #34007: Allow start parameter in Python's sum

c59c86c Trac #33996: ascii_art fail in jupyter notebook

c40983a Trac #33991: remove some unused imports

b02c408 Trac #33978: various details about typing in combinat

6fb1e3f Trac #34037: Make doctest from #25626 more robust

4169d7d Trac #34035: Add __reversed__ method to FrozenBitsets

45c963e Trac #34030: move supercommutator to superalgebras

d4706f9 Trac #34019: minor code details in combinat

3d336f0 Trac #34014: Clean src/sage/graphs/pq_trees.py

c9aa34b Trac #33957: Manifold.options.omit_function_arguments ineffective for arguments not in alphabetic order

0b2741d Trac #33619: clean up ell_curve_isogeny.py

c0e5925 Trac #34036: fix the linter

2b36879 Trac #34025: Fix doctest in sage/modular/overconvergent/hecke_series.py

c0abe3f Trac #33213: Replace SAGE_TMP by the system location in the sage library

7ab174a Trac #32340: document behavior of .is_prime() for number fields

c69f4af Trac #28263: Degree for Affine Morphism or Affine Dynamical System

e516392 Trac #34001: Add flag to avoid OrePolynomialRing cast to PolynomialRing

01b8bcb Trac #33993: pep cleanup for words/morphism.py

716c5ce Trac #33992: remove class inheritance of object in remaining places

de375bc Trac #33990: Subset_s _an_element_

0593e83 Trac #33987: modernize super() in structure, symbolic, doctest, databases

d9a45e2 Trac #33985: modernize super() in monoids,modules,modular

7ed4046 Trac #33984: modernize super() in schemes,libs,sets,quivers

1df260e Trac #33979: .roots() does not always return elements of the base ring

c6c2b85 Trac #33974: Documentation addition for symmetric functions - Cauchy identity

f92916e Trac #33840: bool(matrix) ignores exceptions raised while comparing entries

f8df808 Updated SageMath version to 9.7.beta3

merge was not clean: conflicts in src/sage/modules/free_module.py

[sagetrac-git]

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

b3481c3	modernize super() in monoids and modules
7155fd8	modernize super() in modular
ece5a61	fix pyflakes warnings
eaa5938	Merge branch 'u/chapoton/33985' of https://github.com/sagemath/sagetrac-mirror into public/33868
8286432	fix pycodestyle W605 in pyx files inside matrix/
29a2f15	Merge branch 'u/chapoton/34040' of https://github.com/sagemath/sagetrac-mirror into public/33868
f58d2f3	Merge branch 'public/33868' of https://github.com/sagemath/sagetrac-mirror into public/33868

[sagetrac-git]

Changed commit from cd28605 to f58d2f3

[tscrim]

Dependencies: #33985, #34040

[tscrim]

comment:111

Only a trivial conflict with #33985, but I also merged in #34040 just to make sure there was not a conflict there.

[vbraun]

Changed branch from public/33868 to f58d2f3