Finitely presented modules over the Steenrod algebra

[catanzaromj]

This package implements finitely presented modules over the mod p Steenrod algebra. We define classes for such finitely presented modules, their elements, and morphisms between them. Methods are provided for doing some homological algebra, e.g., computing kernels and images of morphisms, and finding free resolutions of modules.

Depends on #32505 Depends on #33275 Depends on #33323

CC: @sverre320 @sagetrac-kvanwoerden @jhpalmieri @tscrim @rrbruner @cnassau

Component: algebra

Keywords: Steenrod algebra, modules, homological algebra

Author: Bob Bruner, Michael Catanzaro, Sverre Lunøe-Nielsen, Koen van Woerden

Branch/Commit: 7035ae5

Reviewer: John Palmieri, Travis Scrimshaw

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

[catanzaromj]

Branch: u/gh-catanzaromj/finitely_presented_modules_over_the_steenrod_algebra

[catanzaromj]

Author: Bob Bruner, Michael Catanzaro, Sverre Lunøe-Nielsen, Koen van Woerden

[catanzaromj]

Changed branch from u/gh-catanzaromj/finitely_presented_modules_over_the_steenrod_algebra to none

[catanzaromj]

Changed keywords from none to Steenrod algebra, modules, homological algebra

[catanzaromj]

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
+This package implements finitely presented modules over the mod p Steenrod algebra. We define classes for such finitely presented modules, their elements, and morphisms between them. Methods are provided for doing some homological algebra, e.g., computing kernels and images of morphisms, and finding free resolutions of modules.

+**An example**
+
+

[catanzaromj]

Description changed:

--- 
+++ 
@@ -1,5 +1,2 @@
 This package implements finitely presented modules over the mod p Steenrod algebra. We define classes for such finitely presented modules, their elements, and morphisms between them. Methods are provided for doing some homological algebra, e.g., computing kernels and images of morphisms, and finding free resolutions of modules.

-**An example**
-
-

[catanzaromj]

Commit: cc69ed5

[catanzaromj]

Branch: u/gh-catanzaromj/finitely_presented_modules_over_the_steenrod_algebra

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

Changed commit from cc69ed5 to 81fb0c1

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

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

81fb0c1

Replace `_cmp_` with _richcmp_

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

Changed commit from 81fb0c1 to 190da7f

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

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

e78ca19	Replace overset with xrightarrow and remove unused imports
190da7f	Remove additional unused imports

[tscrim]

comment:8

This is quite a project and looks good on a first lookover. Thank you for the contribution. I have some immediate questions/comments before delving too much into the code:

1. Could this be split up into smaller tickets? This would make the review much easier.
2. I think you could rename finitely_presented_over_the_steenrod_algebra to fp_over_steenrod_algebra in order to make the file paths shorter to type.
3. I think the module elements should be Cythonized as this is generally where the majority of the computations happen and it is good to be faster here.
4. Use the Sage default latex commands of \ZZ, \GF{p}, etc. so the documentation is standardized.
5. Check your use of :: and :. If there is going to be a docstring after, then it should be ::, otherwise it should be : (with exceptions for, e.g., .. NOTE::).
6. Errors should be of the form raise TypeError("a message without a capital letter or period") to follow Python's conventions. Also, you should not raise a RuntimeError unless you have a very good reason to; NotImplementedError, TypeError, and ValueError are usually much better.
7. I think it is better to have class level documentation explaining stuff about input, descriptive information, and use-case doctests. The __init__ can then have a simple docstring with a test that basically does TestSuite(foo).run(). This is also a common pattern in Sage.

[sverre320]

comment:9

tscrim,

Thanks for the quick follow-up. Here are some preliminary answers:

1. There are (essentially) three new classes introduced in this ticket: a) free graded modules over F_p-algebras b) f.p. graded modules over F_p-algebras, and c) f.p. graded modules over the Steenrod algebra.

   The class structure is so that f.p. modules (b) have a morphism of free modules (a) as internal data to represent the finite presentation of itself, while a f.p. module over the Steenrod algebra (c) is derived from the class b).

   It would be possible to split the ticket into perhaps two or three tickets: either a), b) and c), or a)+b) and c). The classes in (b) contain all the functionality which does not depend on features special for the Steenrod algebra. Thus, they might be of more general interest.

   However, as they are written, classes a)+b) are privately used by c) and was not intended for public use (yet). As a consequence, the examples and tests in a) + b) only consider modules over the Steenrod algebra.

2. Indeed there are performance bottlenecks here. In particular, a lot of time is spent just creating instances of the free modules (class a mentioned above). The current implementation was motivated by readability, and a performance optimization was planned as a second step. Preliminary measurements indicate that even a Python version using tighter data structures would increase performance by x10 already.

   However -- we have not considered Cython because neither of us have used it before. This may be the best option though, and I am looking into it now. One concern I have is that we use derived classes (fpa modules are e.g. derived from fp modules). Would this complicate using Cython, in your opinion?

Thanks for your input so far. These are certainly valid points. There should be an update addressing 2. 4. 5. 6. and 7. coming soon.

[tscrim]

comment:10

1. It actually would be better to run the tests on the classes themselves rather than through an intermediary because it makes errors easier to find. You will just have to import the relevant classes in each of the doctests.

2. I would look more to optimization before accepting this. This first version is good for setting up the testing and code framework, but 10x is a huge gain and worth doing before merging it into Sage IMO. Using Cython shouldn't complicate things too much if you only have single inheritance. However, the main things you should use Cython on are the element classes (not the parents, which usually have multiple inheritance because you want them to also inherit from UniqueRepresentation) and time-critical computations. I am happy to help in translating things into Cython too.

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

Changed commit from 190da7f to de83eea

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

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

fbe9446	Bugfix.
74ff9e4	Renamed project directory.
d115e0c	Use standard Sage latex macros.
21c5995	Double :'s when docstring is wanted.
064e085	Standardized error messages
bd8697c	Moved docstring from `__init__` to class doc.
de83eea	Made import paths relative

[sverre320]

Performance of the original Python code.

[sverre320]

Attachment: python_perf_res.csv.gz

Performance of the cythonized code.

[sverre320]

Attachment: cython_perf_res.csv.gz

Attachment: perf.png

visualization of the performance data combined

[sverre320]

visualization of total time (green colors) and accounted time (red colors) for both python and cythonized code.

[sverre320]

Attachment: perf_accounted_time.png

Visualization of performance data where only time spent in external modules are shown

[sverre320]

Attachment: perf_comp.png

Attachment: perf_cython.png

Visualization of performance data for cython code only.

[sverre320]

Visualization of performance data for python code only.

[sverre320]

comment:14

Attachment: perf_python.png

We have pushed updates to this package which addresses tscrim's above comments 2, 4, 5, 6, and 7.

With regards to comment 3, we have tried to use Cython to optimize certain parts of the package but without experiencing any significant speedups. I commented earlier that "Preliminary measurements indicate that even a Python version using tighter data structures would increase performance by x10 already." Unfortunately, this comment was based on a too simple example (constructing a free module on one generator). The performance tests we now have conducted are based on a real world use case which is much more relevant for the typical user.

We have therefore come to the conclusion that we want to keep the code as it is, all in Python.

We have conducted performance measurements of both the original Python code as well as a version of it using Cython. Our analysis points to two facts:

1. There is virtually no difference in computing time when comparing our original all-Python code to a version where fp_element.py and free_element.py have been turned into .pyx-files and "cythonized".

2. Approximately 70% of the time used computing the resolution is spent in either the SteenrodAlgebra module or doing linear algebra (subspace spanning, vector space quotients, etc.) These are modules that are external to our package, so Cythonizing our code will not have an effect on this chunk of time. We stopped looking when we could account for 70%-80% of the time consumed, and we are certain that we are not spending the remaining time in a loop somewhere which can benefit from Cythonizing. We imagine various memory allocations and overhead due to the dynamic nature of Python accounts for at least some of the remaining 30%.

The code to reproduce these performance measurements is available in the two experimental branches:

origin/u/gh-sverre320/fp_over_steenrod_algebra_cython_test

origin/u/gh-sverre320/fp_over_steenrod_algebra_performance_test

The first branch contains a version of our package where the two modules fp_element.py and free_element.py have been turned into .pyx-files and "cythonized".

Both branches contain a sage script called 'performance_test.sage' which run the same performance test. It can be used like this:

> ./sage performance_test.sage

The test produces a CSV formatted output, and we have included the results from running it on our system to this comment.

Here's a quick explanation of their contents:

The output is CSV-formatted and measures how much time various parts of the code spends during the computation of one (homological) step of a certain free resolution. This computation is done one (internal) degree at a time, and each line in the CSV file corresponds to a single degree.

Each row contains the following measurements:

"total time": This is the number of seconds it takes to complete one step of the free resolution in one homogeneous degree.

"accounted time": The number of seconds which are accounted for (We only measured the time spent in certain parts which we suspected were most time consuming).

"SteenrodAlgebra": The number of seconds spent calling the SteenrodAlgebra module.

"linear algebra": The number of seconds spent running external linear algebra code.

For each line, the two last values should add up to "accounted time" (or close to it. We left out some more measurements which were tiny in comparison to the two already mentioned.)

The attached images visualize these data.

[mkoeppe]

comment:15

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[tscrim]

comment:17

Sorry for the massive delay in getting back to this.

Thank you for looking into Cythonization. I would have thought there would be more of an advantage going to/from the linear algebra in Sage than dealing with the Steenrod algebra from a quick look through the code.

I have some quick comments before going into a deeper review:

It should be INPUT: and OUTPUT: with single quotes. If there is code afterwards (such as Sage doctests, which are indented one level), then it should be EXAMPLES:: and TESTS::.

Every method needs a doctest. Good ones for __init__ are to create an instance foo and run TestSuite(foo).run().

The author bullet points should not be indented.

Input items should not end is a period/full-stop.

For _richcmp_, it is already guaranteed the elements have the same parent.

I would not do an import at the class level (see from .fp_element import FP_Element), but instead at the module level.

I would set ModuleClass and HomSpaceClass at the class level rather than during the __init__.

Do you want j to be a public attribute of FP_Module? If so (which I don't think is a good idea though), it needs a better name.

The name FP_Module doesn't follow Python naming conventions. Also, it is a bit too generic IMO.

You should add a method for creating the modules to the Steenrod algebra so it is both more discoverable and natural for the user.

I will likely have more comments later as I go deeper into the code.

[dimpase]

comment:18

Perhaps needless to mention, but Cython gets you big speedups only with some care, i.e. you'd need to avoid using Python types (anything untyped in Cython code would be Python, and may render the effort of cythonising useless).

[sverre320]

comment:19

tscrim: Great, you're back!

The name FP_Module doesn't follow Python naming conventions. Also, it is a bit too generic IMO.

About the naming, we have struggled a bit in the past getting names for these classes. They tend to grow rather long when we put in too many descriptive words.

But could this work?

FP_Module -> FinitelyPresentedModule

FPA_Module -> FinitelyPresentedSteenrodAlgebraModule

Personally, if we are to make the class names more descriptive, I would prefer to go all the way, like so:

FP_Module -> FinitelyPresentedModule

FPA_Module -> FinitelyPresentedModuleOverTheSteenrodAlgebra

Also, what about directory path names, does this mean that they have to grow too?

[sverre320]

comment:20

dimpase: Yes, that makes sense. Also, since the performance analysis points to the fact that most of the heavy lifting is performed by other libraries, I saw no point in optimizing our internal data structures.

[tscrim]

comment:21

I have some more consecutitive free time now to devote to a larger patch review. Sorry again for taking so long to get to it.

I would suggest the folder being fp_steenrod_repr the files being fp_graded_* and gp_steenrod_* and the classes being FinitelyPresentedGradedAlgebraModule and FinitelyPresentedSteenrodRepresentation. Shortening FinitelyPresented to FP is also good, but no underscore _ after it.

If the FP_Module is really more general, then the elements should be Cythonized and put in a different folder. I think it would be good if the corresponding documentation stated a bit about what assumptions you have on the algebra's implementation.

In the morphism implementation, you should instead implement the single underscore version of the algebraic operations, e.g. _add_. Then you can assume compatible maps (in terms of domain and codomain) as the coercion framework will take care of the rest.

Do you need the implementation of free modules? In particular, I am wondering if you could use what is currently in Sage (with perhaps some renaming of methods and/or adding stuff to an appropriate category)?

[mkoeppe]

comment:22

Setting a new milestone for this ticket based on a cursory review.

[jhpalmieri]

Changed branch from u/gh-catanzaromj/finitely_presented_modules_over_the_steenrod_algebra to u/jhpalmieri/finitely_presented_modules_over_the_steenrod_algebra

[jhpalmieri]

comment:24

Here is a small patch. It fixes some documentation syntax, and it also moves the documentation from "algebras" to "modules". It fixes two doctest failures, probably due to a change in another component of Sage.

---

Last 10 new commits:

4d15e87	Replace overset with xrightarrow and remove unused imports
8febd53	Remove additional unused imports
a13d0f6	Bugfix.
c1a84da	Renamed project directory.
ff32fa2	Use standard Sage latex macros.
bc3516b	Double :'s when docstring is wanted.
723ce71	Standardized error messages
848bd91	Moved docstring from `__init__` to class doc.
4c920c8	Made import paths relative
6a617ff	trac 30680: fix docstrings, move documentation from "algebras" to "modules"

[jhpalmieri]

Changed commit from de83eea to 6a617ff

[jhpalmieri]

comment:25

I also echo tscrim's comments. For example, the module sage.combinat.free_module is may be a good replacement for your free module implementation, or a good class to use for inheritance (where you might add generator_degrees, etc.).

Using long names (like FinitelyPresentedGradedAlgebraModule or FPGradedAlgebraModule) is pretty typical in Sage, and it's typically not a burden because you either don't need to type the name much or when you do, then at least in an interactive session, you can use tab completion. So the preference is to use more descriptive names.

[jhpalmieri]

comment:26

The function mod_p_log can be replaced by the method exact_log (defined for Sage Integers).

[jhpalmieri]

comment:27

Actually, mod_p_log(a, p) is 1+a.exact_log(p). Here is a potential patch:

diff --git a/src/sage/modules/fp_over_steenrod_algebra/profile.py b/src/sage/modules/fp_over_steenrod_algebra/profile.py
index 95f8277e1c..a12b454c40 100755
--- a/src/sage/modules/fp_over_steenrod_algebra/profile.py
+++ b/src/sage/modules/fp_over_steenrod_algebra/profile.py
@@ -37,32 +37,7 @@ from sage.algebras.steenrod.steenrod_algebra import SteenrodAlgebra
 from copy import copy

-#import sage.modules.fp_over_steenrod_algebra.utility as Utility
-def mod_p_log(n,p):
-    r"""
-    Input an integer $n$ and a prime $p$
-    Output the $k$ so that $p^{k-1} < n <= p^k$
-
-    EXAMPLES::
-
-        sage: from sage.modules.fp_over_steenrod_algebra.profile import *
-        sage: mod_p_log(1,4)
-        1
-        sage: mod_p_log(8,3)
-        2
-        sage: mod_p_log(9,3)
-        3
-
-    """
-    k=0
-    pow=1
-    while n >= pow:
-        k += 1
-        pow *= p
-    return k
-
-
-def profile_ele(alist,char=2):
+def profile_ele(alist, char=2):
     """
     Finds the smallest sub-Hopf algebra containing the element passed.
     `alist' is assumed to be an element of the Steenrod Algebra, (the only other
@@ -91,32 +66,33 @@ def profile_ele(alist,char=2):
         alist2 = [e[0] for e in alist]
         maxlength = max([0]+[len(e) for e in alist2])
         alist2 = [list(e) + (maxlength-len(e))*[0] for e in alist2]
-        minprofile = [max([alist2[i][j] for i in range(len(alist2))]) \
+        minprofile = [max([alist2[i][j] for i in range(len(alist2))])
                                                 for j in range(maxlength)]
-        minprofile = tuple(map(lambda xx: mod_p_log(xx,char),minprofile))
+        minprofile = tuple(map(lambda xx: xx.exact_log(char)+1, minprofile))
         return find_min_profile(minprofile,char)
-    if char != 2:
-        alistQ = [e[0][0] for e in alist]
-        alistP = [e[0][1] for e in alist]
-        maxlengthQ = max([0]+[len(e) for e in alistQ])
-        maxlengthP = max([0]+[len(e) for e in alistP])
-        alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
-        alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
-        minprofileQ = [max([alistQ[i][j] for i in range(len(alistQ))]) \
-                                            for j in range(maxlengthQ)]
-        minprofileP = [max([alistP[i][j] for i in range(len(alistP))]) \
-                                            for j in range(maxlengthP)]
-        minprofileP = tuple(map(lambda xx: mod_p_log(xx,char),minprofileP))
-        if not minprofileQ:
-            minpQ=[]
-        else:
-            minpQ = [1]*(max(minprofileQ)+1)
-            for j in minprofileQ:
-                minpQ[j] = 2
-        return find_min_profile((minprofileP,minpQ),char=char)
+
+    # odd primes
+    alistQ = [e[0][0] for e in alist]
+    alistP = [e[0][1] for e in alist]
+    maxlengthQ = max([0]+[len(e) for e in alistQ])
+    maxlengthP = max([0]+[len(e) for e in alistP])
+    alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
+    alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
+    minprofileQ = [max([alistQ[i][j] for i in range(len(alistQ))])
+                                        for j in range(maxlengthQ)]
+    minprofileP = [max([alistP[i][j] for i in range(len(alistP))])
+                                        for j in range(maxlengthP)]
+    minprofileP = tuple(map(lambda xx: xx.exact_log(char)+1, minprofileP))
+    if not minprofileQ:
+        minpQ=[]
+    else:
+        minpQ = [1]*(max(minprofileQ)+1)
+        for j in minprofileQ:
+            minpQ[j] = 2
+    return find_min_profile((minprofileP,minpQ),char=char)

-def enveloping_profile_elements(alist,char=2):
+def enveloping_profile_elements(alist, char=2):
     """
     Finds the profile function for the smallest sub-Hopf algebra containing
     the list of elements passed. Entries of `alist' are elements of the Steenrod
@@ -145,26 +121,27 @@ def enveloping_profile_elements(alist,char=2):
              return (0,)
         maxlength = max([len(e) for e in alist2])
         alist2 = [list(e) + (maxlength-len(e))*[0] for e in alist2]
-        minprofile = tuple(max([alist2[i][j] for i in range(len(alist2))]) \
+        minprofile = tuple(max([alist2[i][j] for i in range(len(alist2))])
                                                 for j in range(maxlength))
         return find_min_profile(minprofile)
-    else:
-        masterlist = [profile_ele(x,char) for x in alist if x != 0]
-        alistP = [x[0] for x in masterlist]
-        alistQ = [x[1] for x in masterlist]
-        if not alistP and not alistQ:
-            return ((0,),(0,))
-        maxlengthQ = max([len(e) for e in alistQ])
-        maxlengthP = max([len(e) for e in alistP])
-        alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
-        alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
-        minprofileQ = tuple(max([alistQ[i][j] for i in range(len(alistQ))]) \
-                                                for j in range(maxlengthQ))
-        minprofileP = tuple(max([alistP[i][j] for i in range(len(alistP))])\
-                                                for j in range(maxlengthP))
-        return find_min_profile((minprofileP,minprofileQ),char=char)
-
-def enveloping_profile_profiles(alist,char=2):
+
+    # odd primes
+    masterlist = [profile_ele(x,char) for x in alist if x != 0]
+    alistP = [x[0] for x in masterlist]
+    alistQ = [x[1] for x in masterlist]
+    if not alistP and not alistQ:
+        return ((0,),(0,))
+    maxlengthQ = max([len(e) for e in alistQ])
+    maxlengthP = max([len(e) for e in alistP])
+    alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
+    alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
+    minprofileQ = tuple(max([alistQ[i][j] for i in range(len(alistQ))])
+                                            for j in range(maxlengthQ))
+    minprofileP = tuple(max([alistP[i][j] for i in range(len(alistP))])
+                                            for j in range(maxlengthP))
+    return find_min_profile((minprofileP,minprofileQ),char=char)
+
+def enveloping_profile_profiles(alist, char=2):
     """
     Finds the profile function for the smallest sub-Hopf algebra containing
     the sub-algebras corresponding the list of profile functions passed. Accepts
@@ -190,24 +167,25 @@ def enveloping_profile_profiles(alist,char=2):
         alist2 = list(copy(alist))
         maxlength = max([len(e) for e in alist2])
         alist2 = [list(e) + (maxlength-len(e))*[0] for e in alist2]
-        minprofile = tuple(max([alist2[i][j] for i in range(len(alist2))]) \
+        minprofile = tuple(max([alist2[i][j] for i in range(len(alist2))])
                                                 for j in range(maxlength))
         return find_min_profile(minprofile)
-    else:
-        alistP = [copy(alist[i][0]) for i in range(len(alist))]
-        alistQ = [copy(alist[i][1]) for i in range(len(alist))]
-        maxlengthQ = max([len(e) for e in alistQ])
-        maxlengthP = max([len(e) for e in alistP])
-        alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
-        alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
-        minprofileQ = tuple(max([alistQ[i][j] for i in range(len(alistQ))]) \
-                                                for j in range(maxlengthQ))
-        minprofileP = tuple(max([alistP[i][j] for i in range(len(alistP))]) \
-                                                for j in range(maxlengthP))
-        return find_min_profile((minprofileP,minprofileQ),char=char)
-
-
-def valid(LL,char=2):
+
+    # odd primes
+    alistP = [copy(alist[i][0]) for i in range(len(alist))]
+    alistQ = [copy(alist[i][1]) for i in range(len(alist))]
+    maxlengthQ = max([len(e) for e in alistQ])
+    maxlengthP = max([len(e) for e in alistP])
+    alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
+    alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
+    minprofileQ = tuple(max([alistQ[i][j] for i in range(len(alistQ))])
+                                            for j in range(maxlengthQ))
+    minprofileP = tuple(max([alistP[i][j] for i in range(len(alistP))])
+                                            for j in range(maxlengthP))
+    return find_min_profile((minprofileP,minprofileQ),char=char)
+
+
+def valid(LL, char=2):
     """
     Determines if the list passed is a valid profile.
     ## When checking at odd primes, the `P`-part must be the 0th entry in LL,
@@ -235,20 +213,21 @@ def valid(LL,char=2):
             for i in range(1,r):
                 value = value and ((L[r] >= L[r-i] - i) or (L[r] >= L[i]))
         return value
-    else:
-        (alistP,alistQ) = (LL[0],LL[1])
-        M = [0] + list(alistP) + [0]*len(alistP)
-        L = list(alistQ) + [1]*(len(alistQ)+1)
-        M = M + [0]*abs(len(M)-len(L))  # Pad so they're the same length
-        L = L + [1]*abs(len(M)-len(L))
-        value = valid(alistP,char=2)  # P part must satisfy same conditions, regardless of prime.
-        for r in range(len(L)): # \tau's indexed at 0, unlike \xi 's
-            if (L[r] == 1) and value:
-                for i in range(r+1):
-                    value = value and ((M[i] <= r -i) or (L[r-i] == 1))
-        return value

-def nextprof(p,n,char=2):
+    # odd primes
+    (alistP,alistQ) = (LL[0],LL[1])
+    M = [0] + list(alistP) + [0]*len(alistP)
+    L = list(alistQ) + [1]*(len(alistQ)+1)
+    M = M + [0]*abs(len(M)-len(L))  # Pad so they're the same length
+    L = L + [1]*abs(len(M)-len(L))
+    value = valid(alistP,char=2)  # P part must satisfy same conditions, regardless of prime.
+    for r in range(len(L)): # \tau's indexed at 0, unlike \xi 's
+        if (L[r] == 1) and value:
+            for i in range(r+1):
+                value = value and ((M[i] <= r -i) or (L[r-i] == 1))
+    return value
+
+def nextprof(p, n, char=2):
     """
     Takes a possible profile `p' and a base profile `n'. Returns the next
     profile in lexicographic order. After all valid profiles `p' of
@@ -292,22 +271,23 @@ def nextprof(p,n,char=2):
                 else:                          # inside n still, so reset to n
                     p[i] = n[i]
         return n + [0]*(len(p)-len(n)) + [1]    # fell off the end
-    else:  # odd primes
-        pQ = list(p[1])
-        nQ = list(n[1])
-        for i in range(len(pQ)):
-            if pQ[i] < 2:
-                pQ[i] += 1
-                return pQ
+
+    # odd primes
+    pQ = list(p[1])
+    nQ = list(n[1])
+    for i in range(len(pQ)):
+        if pQ[i] < 2:
+            pQ[i] += 1
+            return pQ
+        else:
+            if i > len(nQ) -1:
+                pQ[i] = 1
             else:
-                if i > len(nQ) -1:
-                    pQ[i] = 1
-                else:
-                    pQ[i] = nQ[i]
-        return nQ + [1]*(len(pQ)-len(nQ)) +[1]
+                pQ[i] = nQ[i]
+    return nQ + [1]*(len(pQ)-len(nQ)) +[1]

-def find_min_profile(prof,char=2):
+def find_min_profile(prof, char=2):
     """
     Given a tuple of integers (a pseudo-profile), this function will
     output the smallest legal profile function containing it. This
@@ -346,11 +326,11 @@ def find_min_profile(prof,char=2):
         while not valid(p,char):
             p = nextprof(p,n,char)
         return tuple(p)
-    else:
-        pP,pQ = list(prof[0]), list(prof[1])
-        P = find_min_profile(pP,char=2)
-        Q = copy(pQ)
-        while not valid([P,Q],char):
-            Q = nextprof([P,Q],[P,pQ],char)
-        return (P,Q)
+
+    pP,pQ = list(prof[0]), list(prof[1])
+    P = find_min_profile(pP,char=2)
+    Q = copy(pQ)
+    while not valid([P,Q],char):
+        Q = nextprof([P,Q],[P,pQ],char)
+    return (P,Q)

[sverre320]

comment:28

Thanks for making concrete suggestions, like using sage.combinat.free_module. I am just not sure it's worth it. When I look at the existing code, I see a lot of reference to the degree of elements. All that code has to be put back into the class that inherits from combinat (which has no concept of gradings). And so I am not convinced it's going to be saving a lot of lines of code in the end.

I think of the free module class as part of the private implementation of this package, and not an addition to Sage in itself. Replacing it or letting it inherit from combinat would have implications on the rest of the code. Since these kinds of changes usually take longer to implement than what one usually expects, I am hesitant about trying this out.

Am I just being too negative here, or are there any obvious benefits I am missing?

[jhpalmieri]

comment:29

Well, I find it annoying that there are two different implementations of free modules already, and adding another would only add to that. In general, the pieces of Sage should build on each other, rather than each developer building their own version of each thing they want.

When I first wrote the chain complex and simplicial complex code in Sage, I used the existing code for matrices and linear algebra (for the boundary maps), and as a result, I found a bunch of bugs in that code. The more the pieces of Sage are tied together, the stronger the pieces are, because they're used and tested in more different ways.

I will try to take a look to see how much work would need to be done to have your code inherit from sage.combinat.free_module.

[dimpase]

comment:30

maybe sage.combinat.free_module ought to be extended to accommodate for the needs of this ticket?

I find it surprising that sage.combinat.free_module has no concept of grading.

[sverre320]

comment:31

Back when I started refactoring the original code for this package, I tried to find a suitable class to build (free) graded modules on. I failed to find one, and decided to write my own and make it an internal component of this package.

However, @jhpalmieri, I absolutely agree with what you are saying: Ideally, I would have liked to open a separate ticket with the goal of adding a more general class for free graded modules.

This seemed to me like a bigger task, and so I compromised. It's a task I necessarily cannot do myself, as there are many opinions about what a graded module should be. It is e.g. not clear to me that a class for representing free graded modules should inherit from the ungraded module class. For example, I guess this relates directly to the question about allowing sums of elements of different degrees or not.

One option for the current ticket has always been to integrate the free module code into the class of the finitely presented modules (FP_xxx) and avoid the problem we are facing now. However, it always made much more sense to me, in terms of code readability, to separate the code for free module representation.

So to conclude: If we to open a ticket and do graded modules in Sage correctly, I am willing to help out. Otherwise, I suggest we accept the solution in this ticket and postpone the cleanup.

Of course, if I am wrong and this

I will try to take a look to see how much work would need to be done to have your code inherit from sage.combinat.free_module.

turns out to make more sense, I am happy to take this path.

[jhpalmieri]

comment:32

My current plan is the following, time-permitting:

• move the files fp_... into a new directory sage/modules/fp_graded/, in the hopes that they will be of more general use.
• rewrite those files to base them on existing free module implementations.
• then see what's left after that.

I think this fits into tscrim's suggestion. Assuming there are no objections, then once I've made some progress, I will open a ticket for general finitely presented graded modules over graded rings, and we can rebase this ticket on top of that one.

[jhpalmieri]

comment:33

By the way, I don't see any reason to forbid sums of elements of different degrees; people can decide depending on their uses. It's unusual but not unheard of for the Steenrod algebra, and someone might try something strange and make a great new discovery.

[jhpalmieri]

comment:34

I have questions and comments:

• first, in other parts of Sage that use gradings, the zero element has no degree, and in fact zero.degree() raises an error rather than returning None as it does here. So I am changing the behavior here to raise an error.

• I'm not sure what to do with homsets and morphisms. Some people would insist that Hom(M, N) should contain only degree 0 maps; others (especially in algebraic topology, in my experience) allow maps of any degree. (Fortunately no one allows maps that do not preserve degrees, when considering categories of graded modules.) How do we handle this? Should there be two different structures, one for degree 0 maps, one for maps of arbitrary degree? Or just degree 0 maps, and then people can consider Hom(Sigma^i M, Sigma N) if they want maps of degree i from M to N?

[jhpalmieri]

comment:35

This may be more a question for Travis. Should the category be GradedModules or GradedModulesWithBasis? Maybe if we're working over an algebra with a distinguished basis, the module should inherit that basis, at least in the case of a free module. I'm not sure, though, and I really don't know what to do about non-free modules. (I haven't gotten that far in my modifications: I've just been dealing with free modules.)

I'm a little puzzled by the category setup in this context. Does "with basis" refer to a basis over the algebra over which we're working, or over the base field for that algebra? Consider this:

sage: R.<x> = QQ[]                                                                       
sage: R                                                                                  
Univariate Polynomial Ring in x over Rational Field
sage: M = FreeModule(R, ['a', 'b'])                                                      
sage: M.category()                                                                       
Category of finite dimensional modules with basis over Univariate Polynomial Ring in x over Rational Field

The "finite dimensional" part of that sounds odd unless you interpret it as meaning "free and finitely generated".

sage: M.basis()
Finite family {'a': B['a'], 'b': B['b']}

So this is viewing the basis as being over the polynomial ring.

On the other hand:

sage: A = GradedModulesWithBasis(QQ).example()                                           
sage: A                                                                                  
An example of a graded module with basis: the free module on partitions over Rational Field
sage: A.homogeneous_component_basis(4)                                                   
Lazy family (Term map from Partitions to An example of a graded module with basis: the free module on partitions over Rational Field(i))_{i in Partitions of the integer 4}
sage: list(A.homogeneous_component_basis(4))                                             
[P[4], P[3, 1], P[2, 2], P[2, 1, 1], P[1, 1, 1, 1]]

So homogeneous_component_basis(...) allows access to the vector space basis.

It looks like "with basis" means over the ring or algebra connected to the module, not the ground field. So maybe it should be in the categories

• GradedModulesWithBasis(A) only in the case of free modules
• GradedModulesWithBasis(A.base_ring()) for all modules, assuming we can determine a basis of each homogeneous piece, and this should be possible as long as the algebra has a distinguished basis. Does that make sense?

[sverre320]

comment:36

@jhpalmieri: I think your plan is perfect, and totally in tune with what I hoped could be done. (I even think there is a comment about this in the beginning of fp_module.py.)

At any rate, I am happy about this turn and would gladly help out if I can.

[jhpalmieri]

comment:37

For degrees of morphisms, I propose:

• we allow construction of morphisms of any degree, but
• Hom(M,N) should consist only of morphisms of degree 0.

Comments?

[rrbruner]

comment:38

Replying to @jhpalmieri:

For degrees of morphisms, I propose:

• we allow construction of morphisms of any degree, but
• Hom(M,N) should consist only of morphisms of degree 0.

Comments?

If Hom(M,N) is to contain morphisms of any degree, then it should be a graded vector space, and would not be of finite type, in general. This suggests Hom(M,N) should contain morphisms of degree 0 only.

Counter-argument: a cochain representing an element of Ext^s,t(M,N) is a homomorphism of degree t from M _s (the s^th stage in your free resolution of M) to N, or a homomorphism of degree 0 from Ms to \Sigma^t N. Then, lifting this to a chain map, you'll need degree 0 morphisms from M{s+i} to \Sigma^t Ni (where N* is your resolution of N).

You end up needing to construct all (well, many of) the suspensions of every term in any resolution you create, which seems to be a lot of extra baggage. Morphisms of any degree obviate this.

If you have morphisms of any degree, but Hom(M,N) only includes those of degree 0, where do the others live?

[jhpalmieri]

comment:39

Yesterday I browsed the internet, and a majority of places viewed Hom as containing only degree 0 maps. This agrees with my impression that many people view the category of graded modules as having degree 0 maps as the morphisms.

I think that computationally, constructing a suspension of a graded module should not be a burden. On the other hand, inheriting from UniqueRepresentation may mean that Sage will never truly forget a graded module once it's been constructed, so maybe constructing lots of suspensions would be a burden. If this becomes a concern, we can create a new class for the suspension of a module: the input would be an already existing module (no new resources required there) and an integer.