search

sagemath / sage

Main repository of SageMath. Now open for Issues and Pull Requests.
https://www.sagemath.org
Other
1.21k stars 421 forks source link

kernel and inverse_image of (polynomial) ring homomorphisms #9792

Closed vbraun closed 4 years ago

vbraun commented 13 years ago

For polynomial ring homomorphisms, this ticket implements the methods

(This also works for homomorphisms of polynomial quotient rings, number fields and Galois fields.)

The implementation is based on the following:

Given a homomorphism f: K[x] -> K[y] of (multivariate) polynomial rings that respects the K-algebra structure, we can find preimages of y by computing normal forms modulo the graph ideal (x-f(x)) in K[y,x] with respect to an elimination order. More generally, this works for morphisms of quotient rings K[x]/I -> K[y]/J, which allows to handle many types of ring homomorphisms in Sage.

References: e.g. [BW1993] Propositions 6.44, 7.71; or Decker-Schreyer, Proposition 2.5.12 and Exercise 2.5.13.

See also #29723 (inverses of ring homomorphisms) and related posts on the mailing list and at Ask-Sagemath.

Example:

sage: R.<s,t> = PolynomialRing(QQ)
sage: S.<x,y,z,w> = PolynomialRing(QQ)
sage: f = S.hom([s^4, s^3*t, s*t^3, t^4],R)
sage: f.inverse_image(R.ideal(0))
Ideal (y*z - x*w, z^3 - y*w^2, x*z^2 - y^2*w, y^3 - x^2*z) of Multivariate Polynomial Ring in x, y, z, w over Rational Field
sage: f.inverse_image(s^3*t^4*(s+t))
x*w + y*w

Note that the inverse image of ideals (but not of elements) could also be computed using Singular as follows:

sage: singular.eval('''
....:         ring R=0,(s,t),dp;
....:         ring S=0,(x,y,z,w),dp;
....:         setring R;
....:         map f=S,ideal(s^4,s^3*t,s*t^3,t^4);
....:         setring S;
....:         ideal ker=kernel(R,f)
....:       ''');
sage: singular.get('ker')
'yz-xw,\nz3-yw2,\nxz2-y2w,\ny3-x2z'
sage: print(_)
yz-xw,
z3-yw2,
xz2-y2w,
y3-x2z

CC: @dimpase

Component: algebra

Author: Markus Wageringel

Branch/Commit: fd6dee6

Reviewer: Travis Scrimshaw

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

vbraun commented 13 years ago

Description changed:

--- 
+++ 
@@ -46,7 +46,7 @@
 Here is the corresponding Singular computation:

-sage: sage: singular.eval(''' +sage: singular.eval(''' ....: ring R=0,(s,t),dp; ....: ring S=0,(x,y,z,w),dp; ....: setring R; @@ -54,9 +54,9 @@ ....: setring S; ....: ideal ker=kernel(R,f) ....: '''); -sage: sage: singular.get('ker') +sage: singular.get('ker') 'yz-xw,\nz3-yw2,\nxz2-y2w,\ny3-x2z' -sage: sage: print() +sage: print() yz-xw, z3-yw2, xz2-y2w,

mwageringel commented 4 years ago

Description changed:

--- 
+++ 
@@ -1,49 +1,39 @@
-It would be nice if kernels and inverse images of ring maps were implemented:
+For polynomial ring homomorphisms, this ticket implements the methods
+
+- `inverse_image` (of both ideals and individual elements)
+- `kernel`
+- `is_injective`
+- `_graph_ideal`
+
+(This also works for homomorphisms of polynomial quotient rings, number fields and Galois fields.)
+
+---
+
+The implementation is based on the following:
+
+Given a homomorphism `f: K[x] -> K[y]` of (multivariate) polynomial rings that respects the `K`-algebra structure, we can find preimages of `y` by computing normal forms modulo the graph ideal `(x-f(x))` in `K[y,x]` with respect to an elimination order. More generally, this works for morphisms of quotient rings `K[x]/I -> K[y]/J`, which allows to handle many types of ring homomorphisms in Sage.
+
+References: e.g. [BW1993] Propositions 6.44, 7.71; or [Decker-Schreyer](https://www.math.uni-sb.de/ag/schreyer/images/PDFs/teaching/ws1617ag/book.pdf), Proposition 2.5.12 and Exercise 2.5.13.
+
+See also #29723 (inverses of ring homomorphisms) and related posts on the [mailing list](https://groups.google.com/forum/#!topic/sage-support/aJn0T0jIfwU) and at [Ask-Sagemath](https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/).
+
+---
+
+Example:

-sage: R.<s,t>=PolynomialRing(QQ);R -Multivariate Polynomial Ring in s, t over Rational Field -sage: S.<x,y,z,w>=PolynomialRing(QQ);S -Multivariate Polynomial Ring in x, y, z, w over Rational Field -sage: f=S.hom([s^4,s^3t,st^3,t^4],R);f -Ring morphism:

-/home/vbraun/opt/sage-4.5.2/devel/sage-main/sage/libs/singular/ in () +---

-/home/vbraun/Sage/sage/local/lib/python2.6/site-packages/sage/rings/morphism.so in sage.rings.morphism.RingHomomorphism.inverse_image (sage/rings/morphism.c:4168)()

-NotImplementedError: -sage: kernel(f)

-AttributeError Traceback (most recent call last)

-/home/vbraun/opt/sage-4.5.2/devel/sage-main/sage/libs/singular/ in ()

-/home/vbraun/Sage/sage/local/lib/python2.6/site-packages/sage/misc/functional.pyc in kernel(x)

mwageringel commented 4 years ago

Branch: u/gh-mwageringel/9792

mwageringel commented 4 years ago

New commits:

ad0dc039792: ring homomorphism: inverse_image, kernel, is_injective
mwageringel commented 4 years ago

Commit: ad0dc03

mwageringel commented 4 years ago

Author: Markus Wageringel

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from ad0dc03 to 0484b3b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

0484b3b9792: fix a detail
tscrim commented 4 years ago
comment:5

In RingHomomorphism_cover._inverse_image_element, you forgot the EXAMPLES:: (and indentation).

Should we also implement a (lib)singular version of the kernel for ideals? Or did you do this already and saw that it was slower?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 0484b3b to fd6dee6

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

fd6dee69792: fix some details
mwageringel commented 4 years ago
comment:7

Replying to @tscrim:

Should we also implement a (lib)singular version of the kernel for ideals? Or did you do this already and saw that it was slower?

It would probably be good to wrap the Singular functions kernel and preimage, yes. I have not compared it in terms of speed yet, mainly because I thought that I needed to implement the graph ideal in Sage anyway in order to compute inverses of elements. However, I have just noticed that the Singular function algebra_containment can be used for that, which I had overlooked before. I will try to figure out how to call it from Sage and then report back.

Possibly this means that this branch can be refactored such that it only wraps Singular functions, instead of constructing the graph ideal in Sage, unless we want to keep it for more control over the Gröbner basis computations.

Here is Singular code for the example from the description:

> LIB "algebra.lib";
> ring S = 0, (s,t), dp;
> ideal A = ideal(s^4, s^3*t, s*t^3, t^4);
> poly p = s^3*t^4*(s+t);
> list L = algebra_containment(p, A, 1);
> L[1];
1
> def T = L[2]; setring T; check;
y(1)*y(4)+y(2)*y(4)
tscrim commented 4 years ago
comment:8

Replying to @mwageringel:

Replying to @tscrim:

Should we also implement a (lib)singular version of the kernel for ideals? Or did you do this already and saw that it was slower?

It would probably be good to wrap the Singular functions kernel and preimage, yes. I have not compared it in terms of speed yet, mainly because I thought that I needed to implement the graph ideal in Sage anyway in order to compute inverses of elements. However, I have just noticed that the Singular function algebra_containment can be used for that, which I had overlooked before. I will try to figure out how to call it from Sage and then report back.

Possibly this means that this branch can be refactored such that it only wraps Singular functions, instead of constructing the graph ideal in Sage, unless we want to keep it for more control over the Gröbner basis computations.

We will probably want to have both so we can have it for both generic polynomials (over more exotic base fields (integral domains?)) and specialized code for those implemented using Singular (and less back-and-forth between Singular and Sage).

mwageringel commented 4 years ago
comment:10

Implementing this via the libsingular interface is a lot more complicated than I anticipated. It is not currently possible to use Sage's singular_function with the Singular type qring, and quotient rings in Sage are not even backed by qrings in Singular. This means it is not currently possible to use the Singular function algebra_containment with quotient rings via libsingular, but only with polynomial rings.

The implementation of algebra_containment is essentially the same as on this branch. The main difference is that algebra_containment uses the Singular function std for Gröbner basis computations whereas Sage uses the general purpose function groebner, which does some preprocessing and then calls a suitable implementation. As such, the computation times can be quite different. The Singular version is often a bit faster, but when computing preimages of many elements, the caching in the Sage version seems to be more effective.

The implementation of the Singular function preimage is a bit less transparent to me, so it might be more interesting to wrap this. In this case, by switching to the ambient ring, one can work around the problem that the qring type is not supported. However, I still did not manage to call preimage via libsingular, as it requires the ideals passed as arguments to have names, which our ideals apparently do not have.

The other option is to use the Singular pexpect interface to wrap preimage and algebra_containment. Though, as the current branch is functional, I would prefer to not implement that on this ticket here, so I am setting this back to needs_review.

tscrim commented 4 years ago

Reviewer: Travis Scrimshaw

tscrim commented 4 years ago
comment:11

That is too bad. Thank you for trying. I agree that we should get this into Sage now, and we can revisit using libsingular later.

mwageringel commented 4 years ago
comment:12

Thank you.

vbraun commented 4 years ago

Changed branch from u/gh-mwageringel/9792 to fd6dee6