Sage: Ticket #9792: kernel and inverse_image of (polynomial) ring homomorphisms
https://trac.sagemath.org/ticket/9792
<p>
For polynomial ring homomorphisms, this ticket implements the methods
</p>
<ul><li><code>inverse_image</code> (of both ideals and individual elements)
</li><li><code>kernel</code>
</li><li><code>is_injective</code>
</li><li><code>_graph_ideal</code>
</li></ul><p>
(This also works for homomorphisms of polynomial quotient rings, number fields and Galois fields.)
</p>
<hr />
<p>
The implementation is based on the following:
</p>
<p>
Given a homomorphism <code>f: K[x] -> K[y]</code> of (multivariate) polynomial rings that respects the <code>K</code>-algebra structure, we can find preimages of <code>y</code> by computing normal forms modulo the graph ideal <code>(x-f(x))</code> in <code>K[y,x]</code> with respect to an elimination order. More generally, this works for morphisms of quotient rings <code>K[x]/I -> K[y]/J</code>, which allows to handle many types of ring homomorphisms in Sage.
</p>
<p>
References: e.g. [BW1993] Propositions 6.44, 7.71; or <a class="ext-link" href="https://www.math.uni-sb.de/ag/schreyer/images/PDFs/teaching/ws1617ag/book.pdf"><span class="icon"></span>Decker-Schreyer</a>, Proposition 2.5.12 and Exercise 2.5.13.
</p>
<p>
See also <a class="closed ticket" href="https://trac.sagemath.org/ticket/29723" title="enhancement: inverses of ring homomorphisms (closed: fixed)">#29723</a> (inverses of ring homomorphisms) and related posts on the <a class="ext-link" href="https://groups.google.com/forum/#!topic/sage-support/aJn0T0jIfwU"><span class="icon"></span>mailing list</a> and at <a class="ext-link" href="https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/"><span class="icon"></span>Ask-Sagemath</a>.
</p>
<hr />
<p>
Example:
</p>
<pre class="wiki">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
</pre><hr />
<p>
Note that the inverse image of ideals (but not of elements) could also be computed using Singular as follows:
</p>
<pre class="wiki">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
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/9792
Trac 1.1.6vbraunTue, 24 Aug 2010 12:05:23 GMTdescription changed
https://trac.sagemath.org/ticket/9792#comment:1
https://trac.sagemath.org/ticket/9792#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9792?action=diff&version=1">diff</a>)
</li>
</ul>
Ticketgh-mwageringelMon, 01 Jun 2020 16:00:23 GMTdescription, summary, milestone changed; author, branch, commit set; owner deleted
https://trac.sagemath.org/ticket/9792#comment:2
https://trac.sagemath.org/ticket/9792#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9792?action=diff&version=2">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Markus Wageringel</em>
</li>
<li><strong>summary</strong>
changed from <em>kernel and inverse_image of (polynomial) ring maps</em> to <em>kernel and inverse_image of (polynomial) ring homomorphisms</em>
</li>
<li><strong>branch</strong>
set to <em>u/gh-mwageringel/9792</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-feature</em> to <em>sage-9.2</em>
</li>
<li><strong>owner</strong>
changed from <em>AlexGhitza</em> to <em>(none)</em>
</li>
<li><strong>commit</strong>
set to <em>ad0dc039713e3664b89f198ae96d508697652dd6</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=ad0dc039713e3664b89f198ae96d508697652dd6"><span class="icon"></span>ad0dc03</a></td><td><code>9792: ring homomorphism: inverse_image, kernel, is_injective</code>
</td></tr></table>
Ticketgh-mwageringelMon, 01 Jun 2020 16:00:50 GMTstatus changed
https://trac.sagemath.org/ticket/9792#comment:3
https://trac.sagemath.org/ticket/9792#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketgitMon, 01 Jun 2020 16:44:58 GMTcommit changed
https://trac.sagemath.org/ticket/9792#comment:4
https://trac.sagemath.org/ticket/9792#comment:4
<ul>
<li><strong>commit</strong>
changed from <em>ad0dc039713e3664b89f198ae96d508697652dd6</em> to <em>0484b3bbd76ceb89af0f68305eccf9f17f06342a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=0484b3bbd76ceb89af0f68305eccf9f17f06342a"><span class="icon"></span>0484b3b</a></td><td><code>9792: fix a detail</code>
</td></tr></table>
TickettscrimTue, 02 Jun 2020 06:23:08 GMT
https://trac.sagemath.org/ticket/9792#comment:5
https://trac.sagemath.org/ticket/9792#comment:5
<p>
In <code>RingHomomorphism_cover._inverse_image_element</code>, you forgot the <code>EXAMPLES::</code> (and indentation).
</p>
<p>
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?
</p>
TicketgitTue, 02 Jun 2020 19:45:57 GMTcommit changed
https://trac.sagemath.org/ticket/9792#comment:6
https://trac.sagemath.org/ticket/9792#comment:6
<ul>
<li><strong>commit</strong>
changed from <em>0484b3bbd76ceb89af0f68305eccf9f17f06342a</em> to <em>fd6dee61ca094c0b34961f41d6ef357def6ead5e</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=fd6dee61ca094c0b34961f41d6ef357def6ead5e"><span class="icon"></span>fd6dee6</a></td><td><code>9792: fix some details</code>
</td></tr></table>
Ticketgh-mwageringelTue, 02 Jun 2020 19:49:52 GMTstatus changed
https://trac.sagemath.org/ticket/9792#comment:7
https://trac.sagemath.org/ticket/9792#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9792#comment:5" title="Comment 5">tscrim</a>:
</p>
<blockquote class="citation">
<p>
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?
</p>
</blockquote>
<p>
It would probably be good to wrap the Singular functions <code>kernel</code> and <code>preimage</code>, 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 <a class="ext-link" href="https://www.singular.uni-kl.de/Manual/4-1-3/sing_1215.htm#SEC1296"><span class="icon"></span>algebra_containment</a> 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.
</p>
<p>
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.
</p>
<p>
Here is Singular code for the example from the description:
</p>
<pre class="wiki">> 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)
</pre>
TickettscrimWed, 03 Jun 2020 04:06:56 GMT
https://trac.sagemath.org/ticket/9792#comment:8
https://trac.sagemath.org/ticket/9792#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9792#comment:7" title="Comment 7">gh-mwageringel</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9792#comment:5" title="Comment 5">tscrim</a>:
</p>
<blockquote class="citation">
<p>
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?
</p>
</blockquote>
<p>
It would probably be good to wrap the Singular functions <code>kernel</code> and <code>preimage</code>, 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 <a class="ext-link" href="https://www.singular.uni-kl.de/Manual/4-1-3/sing_1215.htm#SEC1296"><span class="icon"></span>algebra_containment</a> 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.
</p>
<p>
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.
</p>
</blockquote>
<p>
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).
</p>
TicketdimpaseThu, 04 Jun 2020 14:13:22 GMTcc set
https://trac.sagemath.org/ticket/9792#comment:9
https://trac.sagemath.org/ticket/9792#comment:9
<ul>
<li><strong>cc</strong>
<em>dimpase</em> added
</li>
</ul>
Ticketgh-mwageringelSat, 13 Jun 2020 14:25:22 GMTstatus changed
https://trac.sagemath.org/ticket/9792#comment:10
https://trac.sagemath.org/ticket/9792#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Implementing this via the libsingular interface is a lot more complicated than I anticipated. It is not currently possible to use Sage's <code>singular_function</code> with the Singular type <code>qring</code>, and quotient rings in Sage are not even backed by <code>qring</code>s in Singular. This means it is not currently possible to use the Singular function <code>algebra_containment</code> with quotient rings via libsingular, but only with polynomial rings.
</p>
<p>
The implementation of <a class="ext-link" href="https://github.com/Singular/Sources/blob/Release-4-1-3p2/Singular/LIB/algebra.lib#L59-L129"><span class="icon"></span>algebra_containment</a> is essentially the same as on this branch. The main difference is that <code>algebra_containment</code> uses the Singular function <code>std</code> for Gröbner basis computations whereas Sage uses the general purpose function <code>groebner</code>, 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.
</p>
<p>
The implementation of the Singular function <code>preimage</code> 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 <code>qring</code> type is not supported. However, I still did not manage to call <code>preimage</code> via libsingular, as it requires the ideals passed as arguments to have names, which our ideals apparently do not have.
</p>
<p>
The other option is to use the Singular pexpect interface to wrap <code>preimage</code> and <code>algebra_containment</code>. 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.
</p>
TickettscrimSat, 13 Jun 2020 22:28:53 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/9792#comment:11
https://trac.sagemath.org/ticket/9792#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Travis Scrimshaw</em>
</li>
</ul>
<p>
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.
</p>
Ticketgh-mwageringelSat, 13 Jun 2020 23:02:33 GMT
https://trac.sagemath.org/ticket/9792#comment:12
https://trac.sagemath.org/ticket/9792#comment:12
<p>
Thank you.
</p>
TicketvbraunMon, 22 Jun 2020 22:34:42 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/9792#comment:13
https://trac.sagemath.org/ticket/9792#comment:13
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/gh-mwageringel/9792</em> to <em>fd6dee61ca094c0b34961f41d6ef357def6ead5e</em>
</li>
</ul>
Ticket