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.

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

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

f7eff26

Fixing last details.

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

Changed commit from dfb3384 to f7eff26

[tscrim]

comment:19

This should now pass the patchbot.

[tscrim]

Changed dependencies from #32324 to #33950

[kwankyu]

comment:21

I doubt if the code and examples around the attribute _is_free_module is worth to be added to [Graded]FreeResolution class so that the class is overloaded.

(1) As mentioned in :comment:11, no one is interested in computing the free resolution of a free module, because it is trivially defined by a free basis of the free module. Hence

(2) [Graded]FreeResolution is designed (and documented so) to work with modules over multivariate polynomial rings (via Singular). Moreover

(3) The added logic slows down the class, however slightly, for most useful cases just because of trivial cases no serious user of free resolutions would use.

If you want to support free resolutions for free modules for completeness (I understand this motivation because you are adding the method .[graded]free_resolution() to arbitrary modules), you define a new class FreeResolution_free_module (and may need renaming FreeResolution to FreeResolution_polynomial) and make the free_resolution() method dispatch for appropriate resolution class depending on the kind of the module (or the base ring).

[tscrim]

comment:22

(1) No, but it can easily happen that your computation ends up doing some corner case. You shouldn't have to special case that for something that I would expect to just work.

(1') Actually, in #33953, can you guarantee that the result of defining_ideal() is always over a multivariate polynomial ring? I should have asked that during my review of that ticket. If this cannot be promised, then you only get to remove one of the if's (the one in _maps; see below).

(2) Yes, but it can be extended.

(3) It is basically two fairly simple and fast if statements. If you are using it in a tight loop that that has a real impact on the performance (i.e., something not measured in microseconds or less than 1% of the computation time), then I will be extremely surprised.

That being said, I agree with you that it very reasonable to separate out this as a subclass as the main implementation (_maps) is quite different. I will need to think a bit about the best way to refactor this.

[kwankyu]

comment:23

Replying to @tscrim:

but it can easily happen that your computation ends up doing some corner case.

No. The base ring does not change during the computation.

(1') Actually, in #33953, can you guarantee that the result of defining_ideal() is always over a multivariate polynomial ring?

Yes. It is about projective morphisms. The smallest projective space is P^1, whose coordinate ring has two variables.

That being said, I agree with you that it is very reasonable to separate out this as a subclass as the main implementation (_maps) is quite different.

It was my mistake that I didn't name it FreeResolution_polynomial from the first.

I will need to think a bit about the best way to refactor this.

Thank you for working on this.

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

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

1e55368

Almost done with refactoring code to separate free module cases.

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

Changed commit from f7eff26 to 1e55368

[tscrim]

comment:25

Not quite done; still a few errors to quash. However, I wanted you to take a look at it with the conventions I chose. I can't work on it for the rest of tonight. Probably something stupid I did during the refactoring that are causing the current failures.

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

Changed commit from 1e55368 to 5403ee0

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

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

5403ee0

Finishing the migration to the methods for building free resolutions.

[tscrim]

comment:27

I have fixed them all; it is ready.

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

Changed commit from 5403ee0 to 3595e1f

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

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

3595e1f

Catching poly rings for ideals that are implemented via Singular.

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

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

b524b39

Catching poly rings for ideals that are implemented via Singular.

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

Changed commit from 3595e1f to b524b39

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

Changed commit from b524b39 to 494794d

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

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

494794d

Refactor

[kwankyu]

comment:31

The last commit is experimental. I separated a constructor (function) and the abstract base class (of free resolutions) from your FreeResolution class. Isn't this more clear?

[tscrim]

comment:32

From a strictly local perspective about the logic of the creation, I agree. However, I oppose (probably even strongly) these types of constructors as it disassociates the class from the construction. In particular, the result of FreeResolution is not isinstance(res, FreeResolution) and the creation documentation is either duplicated or separate from the class. This kind of construction/dispatch idiom is used all over Sage (usually with UniqueRepresentation).

[kwankyu]

comment:33

Replying to @tscrim:

In particular, the result of FreeResolution is not isinstance(res, FreeResolution)

I agree that this is unfortunate. But it seems that it is rather hard to find a case that this is true.

sage: F.<x> = FunctionField(QQ)
sage: isinstance(F, FunctionField)
TypeError...
sage: P.<x> = PolynomialRing(QQ)
sage: isinstance(P, PolynomialRing)
TypeError...
sage: C = EllipticCurve(QQ, [1,1])
sage: isinstance(C, EllipticCurve)
TypeError...

[kwankyu]

comment:34

I can't work on this in following days. Let me get back to you later, with other (perhaps minor) edits.

[tscrim]

comment:35

It helps to not look in old code:

sage: isinstance(Partitions(), Partitions)
True
sage: isinstance(Partitions(5), Partitions)
True
sage: isinstance(Tableaux(), Tableaux)
True
sage: isinstance(Tableaux(max_entry=5), Tableaux)
True
sage: isinstance(Tableaux(shape=[2,1], max_entry=5), Tableaux)
True

This isn't universal, and for very complicated implementations, like matrices and polynomial rings, the burden on developers (and sometimes because of the implementation choice) would be too great to have this feature.

No problem. There isn't a rush on this as this almost certainly won't get into 9.7.

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

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

b763155

Refactor with ConstructorBaseclassMetaclass

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

Changed commit from 494794d to b763155

[kwankyu]

comment:37

This is still experimental.

I introduced ConstructorBaseclassMetaclass slightly modified from ClasscallMetaclass. The idea is to separate the constructor definition from the base class definition but still manage so that isinstance(r, FreeResolution) holds.

For me, the separation is more important, but the isinstance feature is more visible. Hence this compromise.

[tscrim]

comment:38

I don't see the point in this added complexity. This paradigm puts the constructor code "far" (not necessarily literally) from the code that actually should be doing the construction. I would want to put the constructor as a method called __constructor__ instead of __classcall__/__classcall_private__. This also creates tension (to maybe even an outright conflict) with any UniqueRepresentation class, including those that do a combination of normalizing inputs and dispatching to subclasses. Basically, you can do the same thing but have __classcall_private__ = construction_function with no additional metaclass.

In either case, it would still require some justification for why it is not simply a method of the class. As mentioned, the separation is actually the problem: The programmer should find within the class called the method doing the construction. (Of course, this is not a hard rule as there can be good reasons, typically due to code complexity.) It is a standard idiom within Sage that __classcall_[private_]_ is called before __init__.

Here is also something I see as a roughly equivalent scenario. Suppose to have a class that in its __init__ instead changes its __class__ attribute based upon its input (rather than dispatching out to an appropriate subclass, which could be reasonable as the subclass would do nothing different with its input). Should that __init__ method be a separate construction function? NB: Parent does this with the category.

[kwankyu]

comment:39

Replying to @tscrim:

In either case, it would still require some justification for why it is not simply a method of the class. As mentioned, the separation is actually the problem: The programmer should find within the class called the method doing the construction. (Of course, this is not a hard rule as there can be good reasons, typically due to code complexity.)

Code complexity is the justification. The constructor involves all subclasses of the base class. The programmer expects to find the constructor outside of(even in a different file, but not within) one of those classes. The sole reason to put the constructor inside the class via __classcall_private__ is to make isinstance feature work. You agreed with this. No?

Moreover it is hard to realize that the code defined in the method __classcall_private__ actually serves as a constructor. The new metaclass is explicit about this.

Parent is unique in the whole sage library. It is irrelevant how Parent solves its own problem.