inverses of ring homomorphisms

[mwageringel]

Ticket #9792 implements inverse_image and is_injective for polynomial ring homomorphisms. Based on that, this ticket implements the methods

• inverse
• is_invertible
• is_surjective

This works for morphisms of polynomial rings, quotient rings, number fields and Galois fields. Several classes of ring homomorphisms are covered.

Example:

sage: R.<x,y,z> = QQ[]
sage: sigma = R.hom([x - 2*y*(z*x+y^2) - z*(z*x+y^2)^2, y + z*(z*x+y^2), z], R)
sage: tau = sigma.inverse(); tau
Ring endomorphism of Multivariate Polynomial Ring in x, y, z over Rational Field
  Defn: x |--> -y^4*z - 2*x*y^2*z^2 - x^2*z^3 + 2*y^3 + 2*x*y*z + x
        y |--> -y^2*z - x*z^2 + y
        z |--> z
sage: (tau * sigma).is_identity()
True

See #9792 for more details.

Depends on #9792

CC: @rburing @nbruin @dimpase @yuan-zhou

Component: commutative algebra

Author: Markus Wageringel

Branch/Commit: ab60c40

Reviewer: Travis Scrimshaw

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

[mwageringel]

Commit: 13e8980

[mwageringel]

Author: Markus Wageringel

[mwageringel]

Dependencies: #9792

[mwageringel]

comment:1

It turns out to be more convenient to implement inverse_image first, so this branch is now based on #9792 (kernel and inverse_image of (polynomial) ring homomorphisms).

I would appreciate if someone could give these tickets a review.

---

New commits:

ad0dc03	9792: ring homomorphism: inverse_image, kernel, is_injective
13e8980	29723: ring homomorphism: inverse, is_invertible, is_surjective

[mwageringel]

Description changed:

--- 
+++ 
@@ -1,8 +1,24 @@
-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.
+Ticket #9792 implements `inverse_image` and `is_injective` for polynomial ring homomorphisms. Based on that, this ticket implements the methods

-This ticket constructs the graph ideal and implements the method `inverse` for ring homomorphisms. This functionality can then be used for related computations such as inverse images, kernels and subalgebra membership tests, which will be implemented on another ticket.
+- `inverse`
+- `is_invertible`
+- `is_surjective`

-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.
+This works for morphisms of polynomial rings, quotient rings, number fields and Galois fields. Several classes of ring homomorphisms are covered.

-See also #9792 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.<x,y,z> = QQ[]
+sage: sigma = R.hom([x - 2*y*(z*x+y^2) - z*(z*x+y^2)^2, y + z*(z*x+y^2), z], R)
+sage: tau = sigma.inverse(); tau
+Ring endomorphism of Multivariate Polynomial Ring in x, y, z over Rational Field
+  Defn: x |--> -y^4*z - 2*x*y^2*z^2 - x^2*z^3 + 2*y^3 + 2*x*y*z + x
+        y |--> -y^2*z - x*z^2 + y
+        z |--> z
+sage: (tau * sigma).is_identity()
+True
+```
+
+See #9792 for more details.
+

[mwageringel]

Branch: u/gh-mwageringel/29723

[tscrim]

comment:2

Is there a particular reason why you raise a ZeroDivisionError if the inverse doesn't exist? I feel like it would be better as a ValueError (or maybe a TypeError).

[mwageringel]

comment:3

Mainly for consistency with morphisms between vector spaces:

sage: f = (QQ^2).hom([[1,1], [1,1]], QQ^2)
sage: f.inverse()
...
ZeroDivisionError: matrix morphism not invertible

Morphisms can be composed using the multiplication operator, so with respect to that operation, a ZeroDivisionError sort of makes sense. Another option would be to raise an ArithmeticError. I do not have a strong opinion about this matter, though.

This reminds me that we should probably add an alias __invert__ for ring homomorphisms as well, so that the syntax ~f can be used.

[tscrim]

comment:4

Replying to @mwageringel:

Mainly for consistency with morphisms between vector spaces:

sage: f = (QQ^2).hom([[1,1], [1,1]], QQ^2)
sage: f.inverse()
...
ZeroDivisionError: matrix morphism not invertible

Morphisms can be composed using the multiplication operator, so with respect to that operation, a ZeroDivisionError sort of makes sense. Another option would be to raise an ArithmeticError. I do not have a strong opinion about this matter, though.

I see, and I agree that it sort of makes sense. Then let us keep it as a ZeroDivisionError.

This reminds me that we should probably add an alias __invert__ for ring homomorphisms as well, so that the syntax ~f can be used.

Please do so. Once that is done, this will be a positive review.

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

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

fd6dee6	9792: fix some details
5bf9893	29723: ring homomorphism: inverse, is_invertible, is_surjective
85d94d2	29723: add `__invert__` for ring homomorphisms

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

Changed commit from 13e8980 to 85d94d2

[mwageringel]

comment:6

Thank you. I have rebased the branch and implemented __invert__ -- not as an alias though, as it would not work well with inheritance.

[tscrim]

comment:7

Thanks. Looks good overall, but the patchbot reports some failures:

sage -t --long src/sage/rings/polynomial/skew_polynomial_ring.py  # 1 doctest failed
sage -t --long src/sage/rings/polynomial/skew_polynomial_element.pyx  # 3 doctests failed

Once fixed, you can set a positive review.

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

Changed commit from 85d94d2 to 081f79d

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

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

081f79d

29723: fix doctests of skew polynomials

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:9

LGTM.

[vbraun]

comment:10

Merge conflict

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

Changed commit from 081f79d to ab60c40

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

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

7216bac	29723: Merge tag '9.2.beta2' into #29723
ab60c40	29723: fix doctests of skew polynomials

[mwageringel]

comment:12

I have resolved the conflict. Let us see what the bot says.

[tscrim]

comment:14

LGTM.

[vbraun]

Changed branch from u/gh-mwageringel/29723 to ab60c40