Opened 11 years ago
Closed 10 months ago
#9792 closed enhancement (fixed)
kernel and inverse_image of (polynomial) ring homomorphisms
Reported by:  vbraun  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  algebra  Keywords:  
Cc:  dimpase  Merged in:  
Authors:  Markus Wageringel  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  fd6dee6 (Commits, GitHub, GitLab)  Commit:  fd6dee61ca094c0b34961f41d6ef357def6ead5e 
Dependencies:  Stopgaps: 
Description (last modified by )
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 (xf(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 DeckerSchreyer, 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 AskSagemath.
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') 'yzxw,\nz3yw2,\nxz2y2w,\ny3x2z' sage: print(_) yzxw, z3yw2, xz2y2w, y3x2z
Change History (13)
comment:1 Changed 11 years ago by
 Description modified (diff)
comment:2 Changed 11 months ago by
 Branch set to u/ghmwageringel/9792
 Commit set to ad0dc039713e3664b89f198ae96d508697652dd6
 Description modified (diff)
 Milestone changed from sagefeature to sage9.2
 Owner changed from AlexGhitza to (none)
 Summary changed from kernel and inverse_image of (polynomial) ring maps to kernel and inverse_image of (polynomial) ring homomorphisms
comment:3 Changed 11 months ago by
 Status changed from new to needs_review
comment:4 Changed 11 months ago by
 Commit changed from ad0dc039713e3664b89f198ae96d508697652dd6 to 0484b3bbd76ceb89af0f68305eccf9f17f06342a
Branch pushed to git repo; I updated commit sha1. New commits:
0484b3b  9792: fix a detail

comment:5 followup: ↓ 7 Changed 11 months ago by
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?
comment:6 Changed 11 months ago by
 Commit changed from 0484b3bbd76ceb89af0f68305eccf9f17f06342a to fd6dee61ca094c0b34961f41d6ef357def6ead5e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
fd6dee6  9792: fix some details

comment:7 in reply to: ↑ 5 ; followup: ↓ 8 Changed 11 months ago by
 Status changed from needs_review to needs_work
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)
comment:8 in reply to: ↑ 7 Changed 11 months ago by
Replying to ghmwageringel:
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
andpreimage
, 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 backandforth between Singular and Sage).
comment:9 Changed 11 months ago by
 Cc dimpase added
comment:10 Changed 10 months ago by
 Status changed from needs_work to needs_review
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 qring
s 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.
comment:11 Changed 10 months ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
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.
comment:12 Changed 10 months ago by
Thank you.
comment:13 Changed 10 months ago by
 Branch changed from u/ghmwageringel/9792 to fd6dee61ca094c0b34961f41d6ef357def6ead5e
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
9792: ring homomorphism: inverse_image, kernel, is_injective