Implement a hook to access free (graded) resolutions

[tscrim]

In #33950, free (graded) resolutions for modules over polynomial rings were added. However, one needs to import a top-level function to do the construction. The goal of this ticket is to add a method, such as free_resolution(), to these (sub)modules (and ideals) to ease access.

Depends on #33950

CC: @kwankyu

Component: user interface

Author: Travis Scrimshaw

Branch/Commit: 6dba5e5

Reviewer: Kwankyu Lee

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

[tscrim]

comment:1

@kwankyu How broadly is Singular's functionality for free (graded) resolutions support to work? I can't seem to find anything definitive in the online documentation. Will it work for any commutative ring? How about any integral domain, such as

sage: R.<x,y> = QQ[]
sage: I = R.ideal([x^2 - y^2 - 1])
sage: Q = R.quo(I)
sage: Q.is_integral_domain()
True

The submodule code currently does not quite do this. (I am doing #34380 to be able to make submodules over more arbitrary integral domains.)

[kwankyu]

comment:2

Replying to @tscrim:

How broadly is Singular's functionality for free (graded) resolutions supposed to work?

Only quotients of free modules over multivariate polynomial rings.

I can't seem to find anything definitive in the online documentation.

This is pretty definitive:

https://www.singular.uni-kl.de/Manual/4-3-1/sing_988.htm#SEC1047

Will it work for any commutative ring?

Definitely not. Singular uses Groebner bases, which do not apply to arbitrary commutative rings. Or do I misunderstand your question?

[tscrim]

comment:3

Replying to @kwankyu:

Replying to @tscrim:

How broadly is Singular's functionality for free (graded) resolutions supposed to work?

Only quotients of free modules over multivariate polynomial rings.

I can't seem to find anything definitive in the online documentation.

This is pretty definitive:

https://www.singular.uni-kl.de/Manual/4-3-1/sing_988.htm#SEC1047

I don't find it so clear. What R is there? Is it a quotient of a polynomial ring like for the syzygies? The invocation of the Hilbert Syzygy Theorem does suggest that it is only for polynomial rings, but it might also be saying that it might not work for some quotients (but it might try).

Will it work for any commutative ring?

Definitely not. Singular uses Groebner bases, which do not apply to arbitrary commutative rings. Or do I misunderstand your question?

I am not an expert in (computational) commutative algebras; thank you for the explanation.

So I will likely have to raise NotImplementedError in a number of cases, but at least it will be more publicly visible.

[kwankyu]

comment:4

Replying to @tscrim:

I don't find it so clear. What R is there? Is it a quotient of a polynomial ring like for the syzygies? The invocation of the Hilbert Syzygy Theorem does suggest that it is only for polynomial rings, but it might also be saying that it might not work for some quotients (but it might try).

I agree that it is vague. It says that R is a quotient of K[x]_> where K[x] is a multivariate polynomial ring.

In Singular, a monomial order > can be global, local, or mixed. Depending on this, K[x]_> may define just K[x], a localization of K[x], or something more complicated.

So according to the above definition, R can be something far from the plain K[x].

I never worked in Singular with a monomial order other than global, the usual monomial orders. As far as I know, Sage also uses Singular's functionality limited to global monomial orders.

For (graded) free resolutions imported into Sage in a recent ticket, R is definitely the plain K[x].

I just looked over Singular manual, and I found no example of computing a free resolution for a module where R is other than the plain K[x], though I might be just unlucky.

Will it work for any commutative ring?

free_resolution() could be attached to at least

• quotients of polynomial rings
• ideals of polynomial rings
• quotients of free modules over polynomial rings
• submodules of free modules over polynomial rings

[tscrim]

comment:5

It seems that #33950 doesn't handle the univariate case either:

sage: R.<x> = QQ[]
sage: I = R.ideal([x^4 + 3*x^2 + 2])
sage: FreeResolution(I)
<repr(<sage.homology.free_resolution.FreeResolution at 0x7fb357e0f9d0>) failed: TypeError: unknown argument type '<class 'sage.rings.polynomial.ideal.Ideal_1poly_field'>'>

sage: M = R^3
sage: v = M([x^4 + 3*x^2 + 2, x^3 + x - 2, x + 1])
sage: w = M([x^3 + 2*x + 4, x^2 + 3*x + 2, 2*x + 3])
sage: S = M.submodule([v, w])
sage: S
Free module of degree 3 and rank 2 over Univariate Polynomial Ring in x over Rational Field
Echelon basis matrix:
[                                                 1 -3/17*x^4 - 11/68*x^3 - 9/34*x^2 + 31/68*x + 11/34  -2/17*x^4 - 5/34*x^3 - 7/34*x^2 + 11/68*x + 49/68]
[                                                 0           3*x^5 + 2*x^4 + 7*x^3 + 6*x^2 + 6*x + 12            2*x^5 + 2*x^4 + 5*x^3 + 7*x^2 - 2*x + 2]
sage: FreeResolution(S)
<repr(<sage.homology.free_resolution.FreeResolution at 0x7fb357ef4700>) failed: TypeError: unknown argument type '<class 'sage.matrix.matrix_polynomial_dense.Matrix_polynomial_dense'>'>

Is this expected?

From the Singular documentation, I am guessing it also requires the polynomial ring to be over a field (mainly Z is not allowed either)?

[tscrim]

Dependencies: #32324

[tscrim]

comment:6

Of course, I can trick Sage into making the univariate polynomial ring believe it is a multivariate one implemented in Singular. Although I would hope there would be an easier mechanism for doing this.

[tscrim]

comment:7

For example

sage: R.<x> = PolynomialRing(QQ, implementation="singular")
sage: type(R)
<class 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingular'>
sage: I = R.ideal([x^4 + 3*x^2 + 2])
sage: FreeResolution(I)
S^1 <-- S^1 <-- 0
sage: M = R^3
sage: v = M([x^4 + 3*x^2 + 2, x^3 + x - 2, x + 1])
sage: w = M([x^3 + 2*x + 4, x^2 + 3*x + 2, 2*x + 3])
sage: S = M.submodule([v, w])
sage: FreeResolution(S)
S^3 <-- S^2 <-- 0

[tscrim]

comment:8

Another way of asking the above is there an easy way to make the univariate case work without converting everything to the Singular implementation?

[tscrim]

comment:9

Univariate polynomial rings over fields are PIDs and submodules of free modules over PIDs are free, right? So perhaps we should just handle this case within Sage?

[tscrim]

comment:10

A very minor typographical bug:

sage: GradedFreeResolution(I, degrees=[2,1], shifts=[-3])
S(--3) <-- S(--2)⊕S(-1) <-- S(-2) <-- 0

[kwankyu]

comment:11

Replying to @tscrim:

You meant #33950.

Univariate polynomial rings over fields are PIDs and submodules of free modules over PIDs are free, right?

Right.

So perhaps we should just handle this case within Sage?

Perhaps Singular requires K of K[x] to be a field. With R univariate polynomial ring, there is nothing interesting with free resolutions, as all submodules are free as you said.

[tscrim]

comment:12

Replying to @kwankyu:

Replying to @tscrim:

You meant #33950.

Yes; I fixed this above.

So perhaps we should just handle this case within Sage?

Perhaps Singular requires K of K[x] to be a field. With R univariate polynomial ring, there is nothing interesting with free resolutions, as all submodules are free as you said.

It actually doesn't seem to be too hard to have a check for this and tweak the code to handle these cases.

[kwankyu]

comment:13

Replying to @tscrim:

A very minor typographical bug:

sage: GradedFreeResolution(I, degrees=[2,1], shifts=[-3])
S(--3) <-- S(--2)⊕S(-1) <-- S(-2) <-- 0

How did you get this? What is I?

[tscrim]

comment:14

I am using I from comment:7. The point is that positive shifts are represented by double negatives.

[kwankyu]

comment:15

Replying to @tscrim:

I am using I from comment:7.

I is not homogeneous, and the size of degrees is not the number of variables. So it is a wrong input.

The point is that positive shifts are represented by double negatives.

I see. Please fix this here.

[tscrim]

comment:16

Replying to @kwankyu:

Replying to @tscrim:

I am using I from comment:7.

I is not homogeneous, and the size of degrees is not the number of variables. So it is a wrong input.

Actually, there is no way it is the one from comment:7...I just forgot which one I used in my haste. ^^;;

The point is that positive shifts are represented by double negatives.

I see. Please fix this here.

Will do.

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Commit: dfb3384

[tscrim]

Branch: public/rings/free_gr_res_hook-34379

[tscrim]

comment:17

Okay, it is finally all ready. It took me a bit of time to figure out that when the matrix over-determines the system over a PID, then we should compute the echelon form.

One point of controversy might be the repr for the multigraded cases. My change effects the prints (0,...,0) and (-a, -b) instead of 0 and -(a, b), respectively. I think this is better to indicate the multigrading by being verbose here. I can also change it so that M((0,0)) gets printed as M(0, 0) instead, which might also be better.

---

New commits:

0232e9e	Add free resolutions
bdbb479	Merge branch 'develop' into t/33950/free-resolution
736d448	Moving the main computation to be done on demand.
5285e67	Moving Singular conversion code to libs/singular; converting resoltuion files to Python files.
5917129	Changing the doc for clarity and to add some more descriptions.
3f1d1c3	Merge branch 'develop' into t/33950/public/rings/free_multigraded_resolutions-33950
ab725f2	Fix spaces
89fc91c	Adding hooks for (graded) free resolutions and handling cases when given a free module.
dfb3384	Rewriting the _repr_module() of graded resolutions to negate the grading.

[sagetrac-git]

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

f7eff26

Fixing last details.

[sagetrac-git]

Changed commit from dfb3384 to f7eff26

[tscrim]

comment:19

This should now pass the patchbot.

[tscrim]

Changed dependencies from #32324 to #33950

[sagetrac-git]

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

250c5cb

Some edits

[kwankyu]

comment:60

In FreeModule, why do you check if the module is a free module only when module is a matrix? You wanted to provide free resolutions for free modules.

In sage.rings.ideal, you provided free_resolution() hook. In this context, an ideal is of a general commutative ring, but your code seems to assume that the ring is a univariate polynomial ring over a field. You need to check this first. If the ring is other than that, raise a NotImplemented error.

[tscrim]

comment:61

Replying to Kwankyu Lee:

In FreeModule, why do you check if the module is a free module only when module is a matrix? You wanted to provide free resolutions for free modules.

This is what we agreed on: special check for matrices because you wanted the code to handle it but not add a method to the matrix classes. Thus, the main entry point needs to process it. Everything else is delegated to free_resolution().

In sage.rings.ideal, you provided free_resolution() hook. In this context, an ideal is of a general commutative ring, but your code seems to assume that the ring is a univariate polynomial ring over a field. You need to check this first. If the ring is other than that, raise a NotImplemented error.

I require the ideal is principal, which is automatically free because it has a single generator. This case holds for all commutative rings, right? All other cases will raise an NotImplementedError either via the is_principal() call or from the result being False.

[kwankyu]

comment:62

Replying to Travis Scrimshaw:

In sage.rings.ideal, you provided free_resolution() hook. In this context, an ideal is of a general commutative ring, but your code seems to assume that the ring is a univariate polynomial ring over a field. You need to check this first. If the ring is other than that, raise a NotImplemented error.

I require the ideal is principal, which is automatically free because it has a single generator. This case holds for all commutative rings, right?

Yes.

All other cases will raise an NotImplementedError either via the is_principal() call or from the result being False.

I see. Okay.

[tscrim]

comment:63

If you’re good with my changes and the patchbot comes back green (or you are confident with the appropriate tests being run), then positive review?

[kwankyu]

comment:64

Replying to Travis Scrimshaw:

Replying to Kwankyu Lee:

In FreeModule, why do you check if the module is a free module only when module is a matrix? You wanted to provide free resolutions for free modules.

This is what we agreed on: special check for matrices because you wanted the code to handle it

No. I wanted that the matrix input is kept in (__init__() of) free resolution subclasses.
But I even agreed to remove it if you want because of maintenance burden.

For FreeResolution dispatcher, I think that not accepting matrix input is the right way. I think I agreed upon this...

[kwankyu]

comment:65

You removed

        if isinstance(module, Ideal_generic):
            S = module.ring()
            if len(module.gens()) == 1 and S in IntegralDomains():
                is_free_module = True
        elif isinstance(module, Module_free_ambient):
            S = module.base_ring()
            if (S in PrincipalIdealDomains()
                or isinstance(module, FreeModule_generic)):
                is_free_module = True 

from FreeResolution dispatcher, are these cases handled in free_resolution()? Or you decided not to handle those cases?

[tscrim]

comment:66

Replying to Kwankyu Lee:

Replying to Travis Scrimshaw:

Replying to Kwankyu Lee:

In FreeModule, why do you check if the module is a free module only when module is a matrix? You wanted to provide free resolutions for free modules.

This is what we agreed on: special check for matrices because you wanted the code to handle it

No. I wanted that the matrix input is kept in (__init__() of) free resolution subclasses.
But I even agreed to remove it if you want because of maintenance burden.

This isn't really that much of a burden, especially since we don't fundamentally want to work with the module but the underlying matrix. We have a good justification for the special case of matrices.

For FreeResolution dispatcher, I think that not accepting matrix input is the right way. I think I agreed upon this...

If the class accepts a matrix, then the dispatcher should be able to handle the matrix. I think it would be really strange to have this discrepancy. Plus the constructor does some things to sanitize the input; in particular, it makes sure the matrix is immutable as this can lead to some very subtle bugs that are very hard to track down. (For example, you pass a mutable matrix into the constructor, compute the resolution, mutate the matrix; now the resolution does not necessarily match the input matrix.)

Actually, this makes me think of a case it should also handle: a free resolution input (where it would just return the input up to maybe stripping/adding the grading).

[tscrim]

comment:67

Replying to Kwankyu Lee:

You removed

        if isinstance(module, Ideal_generic):
            S = module.ring()
            if len(module.gens()) == 1 and S in IntegralDomains():
                is_free_module = True
        elif isinstance(module, Module_free_ambient):
            S = module.base_ring()
            if (S in PrincipalIdealDomains()
                or isinstance(module, FreeModule_generic)):
                is_free_module = True 

from FreeResolution dispatcher, are these cases handled in free_resolution()? Or you decided not to handle those cases?

These are handled by the respective free_resolution() methods in, e.g., ideal.

[kwankyu]

comment:69

Replying to Travis Scrimshaw:

Actually, this makes me think of a case it should also handle: a free resolution input (where it would just return the input up to maybe stripping/adding the grading).

Why? This is strange. PolynomialRing(PolynomialRing(QQ)) does not work in that way.

[kwankyu]

comment:70

trac is buggy...

[tscrim]

comment:71

Replying to Kwankyu Lee:

Replying to Travis Scrimshaw:

Actually, this makes me think of a case it should also handle: a free resolution input (where it would just return the input up to maybe stripping/adding the grading).

Why? This is strange. PolynomialRing(PolynomialRing(QQ)) does not work in that way.

Right, that was dumb of me. I was thinking it was more Element-like (e.g., Partition), but it is Parent-like (or function-like).

Do you think it would be useful to implement a method in graded free resolutions like as_ungraded() that forgets the grading?

[kwankyu]

comment:72

Replying to Travis Scrimshaw:

Do you think it would be useful to implement a method in graded free resolutions like as_ungraded() that forgets the grading?

No as far as I know. Let's leave that as a future work for who needs it.

[kwankyu]

comment:73

Now let this go.

[sagetrac-git]

Changed commit from 250c5cb to 6dba5e5

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

6dba5e5

Hot fixes

[tscrim]

comment:76

Thank you. This improved the code from my original proposal.

It took me a minute to realize that this is equivalent to the way I am used to seeing the definition of a resolution with 0 <- M <- F_1 <- .... However, this is definitely the better way to present this given the string representation.

[kwankyu]

comment:77

Replying to Travis Scrimshaw:

Thank you. This improved the code from my original proposal.

Thank you for the work.

If we want to be more mathematical, matrix input may be entirely removed. But we may regard matrix input as an added conveniency feature. I am happy in either way.

It took me a minute to realize that this is equivalent to the way I am used to seeing the definition of a resolution with 0 <- M <- F_1 <- .... However, this is definitely the better way to present this given the string representation.

A resolution of M is also said to be a resolution of F_1/M. See pages 22-23 of

https://faculty.math.illinois.edu/Macaulay2/Book/ComputationsBook/book/book.pdf

It seems that "resolution of M" is more conventional, but I think "resolution of F_1/M" is more reasonable. If you want to augment F_1 <- ... <- 0 at the left to get an exact sequence, that should be

0 <- F_1/M <- F_1 <- ... <- 0

where the canonical map F_1/M <- F_1 is our 0-th differential map and F_1/M is our target().

[vbraun]

Changed branch from public/rings/free_gr_res_hook-34379 to 6dba5e5