Add method `is_integral_domain` for polynomial quotient rings

[schmittj]

We add a method is_integral_domain to the PolynomialQuotientRing class.

CC: @slel

Component: algebra

Author: Johannes Schmitt

Branch/Commit: 3173fbe

Reviewer: Vincent Delecroix

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

[schmittj]

Branch: u/gh-schmittj/is_integral_domain_for_quotients

[schmittj]

New commits:

3dc50ed

Added method is_integral_domain to PolynomialQuotientRing

[schmittj]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+Added method is_integral_domain to PolynomialQuotientRing

[schmittj]

Commit: 3dc50ed

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

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

8e9c272	Fixed some first doctests
579951a	Added test checking whether ring is already known to be integral domain

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

Changed commit from 3dc50ed to 579951a

[slel]

comment:4

Remember to add your name in the "authors" field and to set to "needs review" when ready.

[slel]

Description changed:

--- 
+++ 
@@ -1 +1,2 @@
-Added method is_integral_domain to PolynomialQuotientRing
+We add a method `is_integral_domain`
+to the `PolynomialQuotientRing` class.

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

Changed commit from 579951a to 5a617af

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

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

5a617af

Added some more doctests

[videlec]

comment:6

With respect to the documentation. Anything after a :: must be indented. The correct syntax for a TESTS or EXAMPLES block starting with a sentence is

        TESTS:

        Here is an example of a quotient ring which is not an integral
        domain, even though the base ring is integral and the modulus is
        irreducible::

            sage: B = ZZ.extension(x^2 - 5, 'a')

Instead of if IntegralDomains() in self.categories() you might want to do if self in IntegralDomains().

The test if self.base_ring() in GcdDomains would better be if self.base_ring() in GcdDomains(). I am surprised that it works the way you wrote it (as GcdDomains is a class).

When proof=False I am not sure that the shortcut NotImplementedError => False is desirable

            except NotImplementedError:
                if proof:
                    raise
                else:
                    ret = False

You indeed catch the raise NotImplementedError that could be raised few lines above but also any NotImplementedError that would come from irr = self.modulus().is_irreducible().

[schmittj]

comment:7

Thanks for taking a close look!

With respect to the documentation. Anything after a :: must be indented.

I'll change this.

Instead of if IntegralDomains() in self.categories() you might want to do if self in IntegralDomains().

Ok, I can do that, though one small comment: I believe in most cases this will mean that is_integral_domain will go into an infinite loop alternating with IntegralDomains().__contains__ until an exception is raised and the __contains__ method returns False. But maybe this is ok?

I only added this check since otherwise doctests about splitting algebras broke. There the problem was: one of these algebras was initialized knowing it is an integral domain, but then later it was also initialized as a quotient ring, and its previous is_integral_domain method (which just returned True) was overwritten with my method which couldn't find a proof and raised an exception. (See the doctest failures in 3dc50ed for reference)

The test if self.base_ring() in GcdDomains would better be if self.base_ring() in GcdDomains(). I am surprised that it works the way you wrote it (as GcdDomains is a class).

Yes, in retrospect I am also surprised - I'll change this.

When proof=False I am not sure that the shortcut NotImplementedError => False is desirable

            except NotImplementedError:
                if proof:
                    raise
                else:
                    ret = False

You indeed catch the raise NotImplementedError that could be raised few lines above but also any NotImplementedError that would come from irr = self.modulus().is_irreducible().

It's true that there are two sources where the NotImplementedError could come from, but I think in both cases there is nothing we can do mathematically - to confirm that we are an integral domain, the only path leading to True right now is that we can verify that self.modulus() is irreducible AND that the base ring is a GCD. If you know another sufficient condition, I am happy to include it.

In fact the previous method PolynomialQuotientRing.is_field, which I tried to emulate, specifically uses such a try: ... except NotImplementedError to catch a missing implementation of is_irreducible.

[videlec]

comment:8

Replying to @schmittj:

Thanks for taking a close look!

With respect to the documentation. Anything after a :: must be indented.

I'll change this.

Instead of if IntegralDomains() in self.categories() you might want to do if self in IntegralDomains().

Ok, I can do that, though one small comment: I believe in most cases this will mean that is_integral_domain will go into an infinite loop alternating with IntegralDomains().__contains__ until an exception is raised and the __contains__ method returns False. But maybe this is ok?

The method self in IntegralDomains() ought to be a faster equivalent of IntegralDomains() in self.categories()... which is not the case. Could you simply add a comment in the code? There is a note at the end of the documentation of IntegralDomains.__contains__ mentionning that this method should disappear (in favour of the generic one being equivalent to IntegralDomains() in self.categories()).

When proof=False I am not sure that the shortcut NotImplementedError => False is desirable

            except NotImplementedError:
                if proof:
                    raise
                else:
                    ret = False

You indeed catch the raise NotImplementedError that could be raised few lines above but also any NotImplementedError that would come from irr = self.modulus().is_irreducible().

It's true that there are two sources where the NotImplementedError could come from, but I think in both cases there is nothing we can do mathematically - to confirm that we are an integral domain, the only path leading to True right now is that we can verify that self.modulus() is irreducible AND that the base ring is a GCD. If you know another sufficient condition, I am happy to include it.

In fact the previous method PolynomialQuotientRing.is_field, which I tried to emulate, specifically uses such a try: ... except NotImplementedError to catch a missing implementation of is_irreducible.

I think my misunderstanding comes from the weird semantic of the keyword proof=True/proof=False. I thought that proof=False meant "the answer assumes some standard conjecture such as the generalized Riemann hypothesis" (as in https://doc.sagemath.org/html/en/reference/structure/sage/structure/proof/proof.html). What your proof=False means is rather "do not raise NotImplementedError but return False instead".

[videlec]

comment:9

Replying to @videlec:

Replying to @schmittj:

Thanks for taking a close look!

With respect to the documentation. Anything after a :: must be indented.

I'll change this.

Instead of if IntegralDomains() in self.categories() you might want to do if self in IntegralDomains().

Ok, I can do that, though one small comment: I believe in most cases this will mean that is_integral_domain will go into an infinite loop alternating with IntegralDomains().__contains__ until an exception is raised and the __contains__ method returns False. But maybe this is ok?

The method self in IntegralDomains() ought to be a faster equivalent of IntegralDomains() in self.categories()... which is not the case. Could you simply add a comment in the code? There is a note at the end of the documentation of IntegralDomains.__contains__ mentionning that this method should disappear (in favour of the generic one being equivalent to IntegralDomains() in self.categories()).

You might want to use what the generic __contains__ does

self.category().is_subcategory(IntegralDomains())

(see sage/categories/category.py).

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

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

3173fbe

Made suggested changes to documentation and details in code

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

Changed commit from 5a617af to 3173fbe

[schmittj]

comment:11

I really like the proposal with self.category().is_subcategory(IntegralDomains()). I made all corresponding changes

[schmittj]

Author: Johannes Schmitt

[videlec]

comment:12

Are you sure about the semantic of proof=False that I mentioned in my comment:8? For Zmod(n) this does turns on/off random primality tests (which is very different from NotImplementedError becomes False). See the file in sage/rings/finite_rings/integer_mod_ring.py. To my mind, the method should always raise NotImplementedError when it is not able to decide.

[videlec]

Reviewer: Vincent Delecroix

[schmittj]

comment:14

In the documentation of Ring.is_integral_domain it says

   Return "True" if this ring is an integral domain.

   INPUT:

   * "proof" -- (default: "True") Determines what to do in unknown
     cases

   ALGORITHM:

   If the parameter "proof" is set to "True", the returned value is
   correct but the method might throw an error.  Otherwise, if it is
   set to "False", the method returns "True" if it can establish that
   self is an integral domain and "False" otherwise.

My impression is: if the primality tests have a nonzero chance of returning a false positive, then the implementation in Zmod(n) is not strictly speaking conforming to this specification in Ring.is_integral_domain.

[videlec]

comment:15

Thanks for the reference. I don't like very much this specification but changing it is definitely not the goal of this ticket.

[vbraun]

Changed branch from u/gh-schmittj/is_integral_domain_for_quotients to 3173fbe