Opened 9 months ago

Last modified 3 months ago

#26929 needs_review defect

Quotients of polynomials rings over boolean rings

Reported by: nbruin Owned by:
Priority: critical Milestone: sage-8.9
Component: algebra Keywords:
Cc: saraedum, caruso, roed Merged in:
Authors: Martin Rubey Reviewers:
Report Upstream: N/A Work issues:
Branch: u/mantepse/quotients_of_polynomials_rings_over_boolean_rings (Commits) Commit: 8bfb308b9aa4ba1bfc6bbadd09aab53f12a92156
Dependencies: Stopgaps:

Description

We have a problem in 8.4 that didn't arise in 8.2:

sage: R.<a0,a1,a2>=BooleanPolynomialRing()
sage: P.<X>=R[]
sage: PQ.<t>=P.quo(X^4+X+1)
sage: (t^4+t+1)==0 #problem
False
sage: (t^4+t+1).is_zero() #correct
True

See https://groups.google.com/d/msg/sage-devel/JuxpFfaKYzA/wdfobJ3GCAAJ

Change History (49)

comment:1 Changed 9 months ago by mantepse

Seems to be the same in 8.3.

comment:2 Changed 9 months ago by mantepse

8.3.beta0 works. Next trying 8.3.beta4

comment:3 Changed 9 months ago by mantepse

8.3.beta4 works, next trying 8.3.beta8

comment:4 Changed 9 months ago by mantepse

8.3.beta8 works, next trying 8.3.rc2

comment:5 Changed 9 months ago by mantepse

8.3.rc2 fails, next trying 8.3.rc0

comment:6 Changed 9 months ago by mantepse

8.3.rc0 fails

comment:7 Changed 9 months ago by mantepse

Here are the commits inbetween:

4ea72a1 Updated SageMath version to 8.3.rc0
e79526a Trac #25686: UniversalCyclotomicField is not finite
20cfa9e Trac #25677: py3: normalize repr of bound methods in doctest results
1e8e585 Trac #25673: Add Young-Fibonacci to poset examples
c78836c Trac #25647: fixing invalid escape sequences in geometry
01f3896 Trac #25586: py3: adding hash function for orders and fraction fields
f95b598 Trac #25579: py3: towards docbuild, work on plot.py
418c1b3 Trac #25573: pyflakes cleanup in number fields
4caec5e Trac #25569: Speed up TorsionQuadraticModule creation
1a81fa5 Trac #25529: Implement Sieving to replace search enumeration
3b29678 Trac #25516: Huge delay introduced in SBox nonlinearity
6aa29cd Trac #25471: OEIS update (database format change, new entries, incorrect warning handling)
2f9e9a1 Trac #25320: Support older versions of backports.shutil_get_terminal_size
111bba1 Trac #25252: Doctest: Complex arithmetic/exponentiation hang (or very slow)
9ca6afb Trac #25251: Doctest: Certain products cause pynac to deadloop
7906ff7 Trac #23416: Provide a "sage -ipynb2rst" command
a55caf8 Trac #22983: polynomial quotient rings are unique parents
788b342 Trac #25731: sage-spkg-uninstall: global name 'cur_dir' is not defined
c513357 Trac #25771: Upgrade to Python 3.6.6
9bddfce Fix doctest due to more verbose python message
e4a4340 25529: corrected doc-build failure
79f6f2c Trac #24973: Univariate polynomial roots bug
50172dd fix uninstall script
966c36b Merge develop and 22983
1594f2d Upgrade to Python 3.6.6
d2dd232 trac 25579 fixing bad handling of error msg in plot.py
813da83 Merge branch 'public/25579' in 8.3.b8
321c9ee Trac #23580: Implement the Onsager and q-Onsager algebras
aae829b Trac #22453: A mistake in the mq.Sbox.polynomials
4f2c67c Trac #22344: Parent richcmp: never use id()
c4bbfd9 Trac #18514: Upgrade of p_group_cohomology spkg
46a4d40 Trac #24612: Move permutation groups to new coercion model
07c3add Trac #25665: Don't use installed_packages() for threejs URL
28aa801 Trac #25661: Primecount failures on 32-bit systems
05ae254 Adding comment in _element_constructor_.
5f39a40 Merge branch 'public/coercion/perm_groups_new_parent-24612' of git://trac.sagemath.org/sage into public/coercion/perm_groups_new_parent-24612
1815bc7 Minor fixes to permutation groups
4ea72a1 Updated SageMath version to 8.3.rc0
e79526a Trac #25686: UniversalCyclotomicField is not finite
20cfa9e Trac #25677: py3: normalize repr of bound methods in doctest results
1e8e585 Trac #25673: Add Young-Fibonacci to poset examples
c78836c Trac #25647: fixing invalid escape sequences in geometry
01f3896 Trac #25586: py3: adding hash function for orders and fraction fields
f95b598 Trac #25579: py3: towards docbuild, work on plot.py
418c1b3 Trac #25573: pyflakes cleanup in number fields
4caec5e Trac #25569: Speed up TorsionQuadraticModule creation
1a81fa5 Trac #25529: Implement Sieving to replace search enumeration
3b29678 Trac #25516: Huge delay introduced in SBox nonlinearity
6aa29cd Trac #25471: OEIS update (database format change, new entries, incorrect warning handling)
2f9e9a1 Trac #25320: Support older versions of backports.shutil_get_terminal_size
111bba1 Trac #25252: Doctest: Complex arithmetic/exponentiation hang (or very slow)
9ca6afb Trac #25251: Doctest: Certain products cause pynac to deadloop
7906ff7 Trac #23416: Provide a "sage -ipynb2rst" command
a55caf8 Trac #22983: polynomial quotient rings are unique parents
788b342 Trac #25731: sage-spkg-uninstall: global name 'cur_dir' is not defined
c513357 Trac #25771: Upgrade to Python 3.6.6
9bddfce Fix doctest due to more verbose python message
e4a4340 25529: corrected doc-build failure
79f6f2c Trac #24973: Univariate polynomial roots bug
50172dd fix uninstall script
966c36b Merge develop and 22983
1594f2d Upgrade to Python 3.6.6
d2dd232 trac 25579 fixing bad handling of error msg in plot.py
813da83 Merge branch 'public/25579' in 8.3.b8
321c9ee Trac #23580: Implement the Onsager and q-Onsager algebras
aae829b Trac #22453: A mistake in the mq.Sbox.polynomials
4f2c67c Trac #22344: Parent richcmp: never use id()
c4bbfd9 Trac #18514: Upgrade of p_group_cohomology spkg
46a4d40 Trac #24612: Move permutation groups to new coercion model
07c3add Trac #25665: Don't use installed_packages() for threejs URL
28aa801 Trac #25661: Primecount failures on 32-bit systems
05ae254 Adding comment in _element_constructor_.
5f39a40 Merge branch 'public/coercion/perm_groups_new_parent-24612' of git://trac.sagemath.org/sage into public/coercion/perm_groups_new_parent-24612
1815bc7 Minor fixes to permutation groups
fc2b6e9 Trac #25712: Typo in SageTimeit documentation
ba8da52 Trac #25655: Typo ticket
44e4061 Trac #25695: Miscellaneous code cleanup in sage.misc.dev_tools
71448bd Trac #21917: Binomial Random Uniform Hypergraph
b70f6ea Trac #25710: UnicodeDecodeError when plotting `graphs.AfricaMap()`
5927aea Trac #25707: Package cocoalib
5cc7435 25529: Corrected coerce issue
6e37aa2 #23416 : update cmdline doctest
f935b04 #23416 : has_pandoc doctest function
a3b8c87 merge develop
edab1bc look at .popcount % 2
30806a2 Merge branch 'u/tmonteil/provide_a__sage__ipynb2rst__command' of trac.sagemath.org:sage into HEAD
a59ea13 Correct docstring.
1e667df Element type to word.
9889222 Trac 25471 : fix warnings for dead sequences
6f15c06 Trac 25471 : the OEIS database format changed and does not make difference between signed and unsigned sequences anymore
e081bc5 Trac 25471 : fix the 20 trivial upstream changes
7292cf3 fix a bug with user defined generators
f051601 Avoid mutation of a torsion quadratic module after creation in submodule.
03055ab doctest error in _list_from_iterator fixed
52c99c2 Corrected Rational point logic
867e1ff trac 25665 fixing threejs URL
8b25b1c 25252: doctest
495e9f4 25251: doctest
6576915 Wrapping some long lines
10cdf0e Add optional package p_group_cohomology-3.0
7a120cb 25529: Removed Affine sieve and some clean up
cd9ce5b Merge branch 'develop' into t/23580/public/lie_algebras/onsager-23580
db8d0d8 Merge branch 'public/lie_algebras/onsager-23580' of git://trac.sagemath.org/sage into t/23580/public/lie_algebras/onsager-23580
7c88021 Trac #20407: Add Magma interface for orders and ideals of number fields
dc00f68 pyflakes cleanup in number fields
1b89e95 Fixing doctests.
344907e Moving permutation groups to the new coercion model and style parents.
d74a8da Merge remote-tracking branch 'origin/develop' into t/22453/a_mistake_in_the_mq_sbox_polynomials
3aadf60 fixed typo 'timit' to 'timeit'
73c5e18 trac 25710 fix unicode in Africa map
5a7b76a Empty lines after TESTS::
dd1a07d Use "make install" but don't ask questions
6806c37 trac 25586 adding comment
0e16142 #25707 package cocoalib
d1ef281 reformatted the tests
383b74a Improve speed of component_function to fix delay in walsh_hadamard_transform
d3b2c00 test added
de49d8c Typo, parameter checks and tests
e16a342 Merge remote-tracking branch 'origin/develop' into t/25516/huge_delay_introduced_in_sbox_nonlinearity
06ac820 add test for method if bug is fixed
1891333 miscellaneous minor code cleanup in sage.misc.dev_tools
ae0cbb8 correction of comment
16b48b5 correction
dab8b92 more doctests for hash
2b6b048 Random binomial uniform hypergraph
c91be02 Merge branch 'u/chapoton/25586' in 8.3.b7
65f09d3 Some small final tweaks.
a5673d1 remove meth is_finite from ring.pyx and universal_cyclotomic_field in order to fall back to the categorial framework
f90805f Merge branch 'public/lie_algebras/onsager-23580' of git://trac.sagemath.org/sage into public/lie_algebras/onsager-23580
8c32108 updated branch to honor recent changes to the sbox module
ad4059c Trac #25661: Fix doctests for 32bits platform
957548b 25529: Reference added
4c3e188 fix this doctest so that it's normalized properly
8fbc6a9 py3: support normalization of bound method reprs in the doctest result parser
042616c Change name.
c80678a Add to TOC.
a51b8a9 Add another poset example.
0b9fba4 25529: added some improvements
eff8c2a more typos
846f1f0 fixing some typos
b52c99d added long time to some doctests
1bab637 Merge tag '8.3.beta7' into t/25529/implement_sieving_to_replace_search_enumeration
ddf4a25 fixing escape sequences in geometry folder
97d8e09 py3: adding hash to orders and fraction fields + other details
96eafe4 Merge branch 'develop' into t/25516/huge_delay_introduced_in_sbox_nonlinearity
ed1ad6a Examples added
8a78906 Added Normalization to defining polynomials
420256c affine: initial version
359d179 some care for py3 doctests in plot/plot.py
b25a670 Added Sieve Algorithm for Projective Schemes
02f421e 24973: use flattening morphism in factor
d24dd41 Make the ZeroDivisionError format more flexible
9cf0503 fix
63badaf do not use id in parent comparison
c495d92 Replace ._gens by gens() to make things work.
44d39f9 set ._gens only if necessary to same time at creation. Further cleanup of unnecessary methods
c9d6272 Speed up. If check is false, then the _module_constructor uses the modulus of self.
2817d90 Fix delay introduced in the computation of walsh hadamard transform
7897736 #23416 : typo
5ed5ab1 #23416 : remove depedency test to pandoc
0785497 #23416 : command line doctest
03e157c Merge branch 'u/tmonteil/provide_a__sage__ipynb2rst__command' of trac.sagemath.org:sage into HEAD
aa75e08 #23416 : postprocessing
2af3bfc #23416 : let nbconvert write file and save images
d22357e #23416 : do not start with a blank line
697d02e Merge remote-tracking branch 'trac/u/saraedum/polynomial_quotient_rings_are_unique_parents' into HEAD
224cbeb Merge branch 'public/lie_algebras/onsager-23580' of git://trac.sagemath.org/sage into t/23580/public/lie_algebras/onsager-23580
40f5d38 Updates to documentation for clarity.
4ecef2f #23416 : better template (output correctly displayed)
79da2e7 fixed typo, rephrased a sentence
1edaf59 Merge branch 'u/tmonteil/provide_a__sage__ipynb2rst__command' of trac.sagemath.org:sage into HEAD
4c76b01 Merge branch 'public/lie_algebras/onsager-23580' of git://trac.sagemath.org/sage into t/23580/public/lie_algebras/onsager-23580
edf0bc7 Cache the product_on_basis.
cd47f94 Merge branch 'public/lie_algebras/onsager-23580' of trac.sagemath.org:sage into public/lie_algebras/onsager-23580
37c4050 Merge branch 'develop' into t/23580/public/lie_algebras/onsager-23580
e6d5ed7 Merge branch 'public/lie_algebras/onsager-23580' of git://trac.sagemath.org/sage into public/lie_algebras/onsager-23580
6498f58 Merge branch 'public/lie_algebras/onsager-23580' of git://trac.sagemath.org/sage into public/lie_algebras/onsager-23580
4660c18 Fix doctests
f1f2fa5 Merge remote-tracking branch 'trac/u/saraedum/polynomial_quotient_rings_are_unique_parents' into trac-22983
806d5af Pickling now works
272e7e3 Merge remote-tracking branch 'origin/develop' into HEAD
272e7e3 Merge remote-tracking branch 'origin/develop' into HEAD
3d8fcbf Merge branch 'develop' into public/lie_algebras/onsager-23580
6bc3ff8 Some doc fixes and uniformization.
4bc750b Merge branch 'develop' into public/lie_algebras/onsager-23580
75e97c6 Merge branch 'develop' into public/lie_algebras/onsager-23580
5040e90 Added some additional methods and tests.
90223dc Adding new file to the doc.
b094112 Implementing q-Onsager algebra.
fecf666 Initial version of Onsager algebra.
2ef220d #23416 : typo.
c18f853 #23416 sage -ipynb2rst command.
b04e7e9 Merge branch 'develop' into t/22983/polynomial_quotient_rings_are_unique_parents
19af059 Merge branch 'develop' into t/22983/polynomial_quotient_rings_are_unique_parents
f6a1cd8 Document normalization of modulus
054945d Make polynomial quotient rings unique parents
f6b0fae Add rank evaluation
ffdad84 Added Magma interface for orders and ideals of number fields.

comment:8 Changed 9 months ago by mantepse

git diff --name-only 8.3.beta8 8.3.rc0 src/sage/rings/polynomial
src/sage/rings/polynomial/polynomial_element.pyx
src/sage/rings/polynomial/polynomial_quotient_ring.py

comment:9 Changed 9 months ago by mantepse

The offending commit is:

a55caf8 Trac #22983: polynomial quotient rings are unique parents

Before it works, afterward it fails.

The diff is not very long, see #22983 and affects only polynomial_quotient_ring.py, but debugging this is beyond me.

comment:10 Changed 9 months ago by mantepse

  • Cc saraedum caruso roed added

comment:11 Changed 9 months ago by mantepse

Is it intentional that the parent of x does not involve t?

sage: R.<a0,a1,a2>=BooleanPolynomialRing()
sage: P.<X>=R[]
sage: PQ.<t>=P.quo(X^4+X+1)
sage: x = (t^4+t+1)
sage: x.parent()
Quotient of Univariate Polynomial Ring in X over Boolean PolynomialRing in a0, a1, a2 by the ideal (X^4 + X + 1)

Apart from that, possibly the problem is that x.parent().defining_ideal() only has the default method reduce.

comment:12 Changed 9 months ago by saraedum

The parent does not print the t when you ask about the string representation but it knows about it. That's normal behaviour for many parents.

comment:13 Changed 9 months ago by saraedum

I think the problem is that the type of PQ changed from a PolynomialQuotientRing to a QuotientRing, probably because some operation thrown an error and then the fallback is used.

comment:14 Changed 9 months ago by saraedum

The quotient by a principal ideal does not work anymore:

sage: P.quotient_by_principal_ideal(P.ideal(X^4+X+1))
AttributeError: 'sage.rings.polynomial.pbori.BooleanPolynomial' object has no attribute 'dict'

So, why do boolean polynomials not implement a dict() method that the generic polynomial code expects every polynomials to implement apparently?

sage: R.one().dict()
AttributeError: 'sage.rings.polynomial.pbori.BooleanPolynomial' object has no attribute 'dict'

Earlier that code path was not triggered, because the code asked the boolean polynomial ring isinstance(R, IntegralDomain) which it is not. This was however, the wrong question. Now it correctly asks R in IntegralDomains() which it is.

So, if you want to fix this, maybe just implement dict() like other polynomial rings do.

comment:15 Changed 9 months ago by nbruin

Just implementing dict breaks all kinds of other things. I put:

    def dict(self):
        R=self.parent()
        vars=R.gens()
        GF2=R.base_ring()
        one=GF2.one()
        return dict((ETuple(tuple(1 if v in s else 0 for v in vars)),one) for s in self.set())

on sage.rings.polynomial.pbori.BooleanPolynomial and it breaks the construction of the quotient ring. By providing a dict method, we do end up in the code path of P.quotient_by_principal_ideal but something there breaks (it ends up factorizing the modulus, but something breaks in the coercion framework). It looks a little wrong that it tries to factor the modulus just for constructing the quotient ring. It could just happily compute in the quotient ring without factoring!

It doesn't look like this is very easy to fix.

comment:16 follow-up: Changed 9 months ago by nbruin

There is a lot more wrong here:

sage: R.<a,b,c>=BooleanPolynomialRing()
sage: R.is_integral_domain()
True
sage: a*(a+1)
0

The problem: the method is_integral_domain is just inherited from generic polynomial rings, where it just returns whether the base ring is an integral domain. However, a BooleanPolynomialRing? is of course NOT a free polynomial ring, so this is completely wrong. I don't know what the right way is to override, because in a way the problem is much deeper: If we inherit from GenericPolynomialRing?, don't we end up with something that SHOULD be an integral domain? So should BooleanPolynomialRing? inherit from something else?

comment:17 Changed 9 months ago by mantepse

deleted comment because of nonsense.

Last edited 9 months ago by mantepse (previous) (diff)

comment:18 in reply to: ↑ 16 Changed 9 months ago by saraedum

Replying to nbruin:

There is a lot more wrong here:

sage: R.<a,b,c>=BooleanPolynomialRing()
sage: R.is_integral_domain()
True
sage: a*(a+1)
0

The problem: the method is_integral_domain is just inherited from generic polynomial rings, where it just returns whether the base ring is an integral domain. However, a BooleanPolynomialRing? is of course NOT a free polynomial ring, so this is completely wrong. I don't know what the right way is to override, because in a way the problem is much deeper: If we inherit from GenericPolynomialRing?, don't we end up with something that SHOULD be an integral domain? So should BooleanPolynomialRing? inherit from something else?

Well, when I wrote the things above, I had just assumed that boolean polynomial rings are free since they inherited from the generic implementation. Now that I read what they actually are, I agree that they should definitely not inherit from that class.

I guess they should probably just inherit from Parent and set the right category, see sage.structure.parent. There might be a better superclass though.

comment:19 Changed 9 months ago by mantepse

inherit from sage.rings.ring.CommutativeRing, just as MPolynomialRing_base does? (and then MPolynomial(CommutativeRingElement))

comment:20 Changed 9 months ago by saraedum

The documentation is a bit unclear here:

    Those classes, except maybe for the lowest ones like :class:`Ring`,
    :class:`CommutativeRing`, :class:`Algebra` and :class:`CommutativeAlgebra`,
    are being progressively deprecated in favor of the corresponding
    categories. which are more flexible, in particular with respect to multiple
    inheritance.

Note that all of these inherit from ParentWithGens which is deprecated.

comment:21 Changed 9 months ago by saraedum

Anyway, I guess whatever works is fine.

comment:22 Changed 9 months ago by mantepse

  • Branch set to u/mantepse/quotients_of_polynomials_rings_over_boolean_rings

comment:23 Changed 9 months ago by mantepse

  • Commit set to 984c6d98fa08520173ac583319a3bf10731bb430

I think it would be more correct to adapt polynomial_quotient_ring.py for multivariate polynomials.


New commits:

984c6d9naive fix

comment:24 Changed 9 months ago by mantepse

In fact, I would like to inherit from QuotientRing_nc, but it seems that this is not possible ('not an extension type'). What would be the proper way to do this? For the moment, I'll just duplicate the definitions, but that's stupid.

comment:25 Changed 9 months ago by git

  • Commit changed from 984c6d98fa08520173ac583319a3bf10731bb430 to 236f09677dba5124584096c535430ee01b8974ce

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

236f096fix remaining doctests, remove unnecessary imports

comment:26 Changed 9 months ago by mantepse

  • Authors set to Martin Rubey
  • Status changed from new to needs_review

It's a stupid fix, but it seems to work, at least essentially.

comment:27 Changed 9 months ago by mantepse

  • Status changed from needs_review to needs_work

Actually, it doesn't work. There are failing doctests in sage.crypto.

comment:28 Changed 9 months ago by git

  • Commit changed from 236f09677dba5124584096c535430ee01b8974ce to 9bae43d1438c94005e7a168b75cfdf3d48682a20

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

9bae43dfix bad import, implement repr_long

comment:29 Changed 9 months ago by mantepse

  • Status changed from needs_work to needs_review

next try...

comment:30 Changed 9 months ago by git

  • Commit changed from 9bae43d1438c94005e7a168b75cfdf3d48682a20 to c68d2c1e0af31017f4f3f68cb08a6b539c30906b

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

c68d2c1remove unused imports reported by pyflakes

comment:31 Changed 9 months ago by git

  • Commit changed from c68d2c1e0af31017f4f3f68cb08a6b539c30906b to a3f33b72fba1c666f071fb09b18adee785ba95bc

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

a3f33b7add documentation and doctest for term_order

comment:32 Changed 9 months ago by git

  • Commit changed from a3f33b72fba1c666f071fb09b18adee785ba95bc to 8bfb308b9aa4ba1bfc6bbadd09aab53f12a92156

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

8bfb308fix doctest

comment:33 follow-up: Changed 9 months ago by gh-jvpeetz

Thanks for these fixes, Martin. I've tested your commits on top of 8.5. The example works now. Then I looked at another use case of mine which has an additional quotient ring. A coercion from one quotient ring to the other fails. Here is the expanded example:

varl = ['x0', 'x1', 'x2', 'x3']
B = BooleanPolynomialRing(names = varl)
B.inject_variables(verbose=False)
P.<p> = PolynomialRing(B)
Byte.<t> = P.quotient_ring( p^4 + p + 1 )
t^4 + t + 1 == 0   # o.k.
X = B.gens()
x = Byte(list(X))

Baff = P.quotient( p^4 + 1 )
xa = Baff(x)

The last statement fails. In version 8.2 and before it works with xa being x3*pbar^3 + x2*pbar^2 + x1*pbar + x0. Something is still missing?

Regards, Jörg.

comment:34 in reply to: ↑ 33 Changed 9 months ago by nbruin

Replying to gh-jvpeetz: [...]

The last statement fails. In version 8.2 and before it works with xa being x3*pbar^3 + x2*pbar^2 + x1*pbar + x0. Something is still missing?

I'm inclined to say the failure is justified and desirable. The rings Baff and Byte aren't canonically isomorphic, are they? It looks like previously, the conversion happened by arbitrarily lifting the element from Byte to P and then taking the image in Baff. You should still be able to do that by explicitly lifting:

xa=Baff(x.lift())

comment:35 follow-up: Changed 9 months ago by gh-jvpeetz

Yes, that works. This also works by using the list() method:

xa = Baff(x.list())

Previously, also something like this worked:

y = t^2 + t + 1
xint = ZZ(y.list(), 2)

which now fails. Any idea?

comment:36 follow-up: Changed 9 months ago by mantepse

What should the last statement do? (I've never seen a two-parameter call to ZZ)

comment:37 in reply to: ↑ 36 Changed 9 months ago by gh-jvpeetz

The second parameter gives a base for the transformation of the list of digits given as the first argument. In the example y.list() is [1, 1, 1, 0] which should be interpreted as bits to give decimal 7 (big endian). See ZZ?.

comment:38 Changed 9 months ago by mantepse

OK, a bit simpler:

sage: B.<x> = BooleanPolynomialRing(1)
sage: ZZ(B(1))
TypeError: unable to coerce <type 'sage.rings.polynomial.pbori.BooleanPolynomial'> to an integer
sage: 

comment:39 Changed 9 months ago by mantepse

This problem is not specific to the Boolean polynomial ring:

sage: R.<x> = PolynomialRing(QQ)
sage: S = R.quotient(x^2+x)
sage: S(1)
1
sage: ZZ(S(1))
TypeError: unable to coerce <class 'sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic_with_category.element_class'> to an integer

I am not familiar enough with the coercion model to decide whether there should be a coercion or not. I don't even know how

sage: ZZ(R(1))
1

works.

comment:40 follow-up: Changed 9 months ago by mantepse

There seems to be a bug. Quotients of multivariate polynomial rings do coerce to integers, quotients of univariate rings don't:

sage: R.<x,y> = QQ[]; S.<a,b> = R.quo(x^2 + y^2); type(a)
<class 'sage.rings.quotient_ring.QuotientRing_generic_with_category.element_class'>
sage: ZZ(S(-3))
-3
sage: R1.<x1> = QQ[]; S1.<a1> = R1.quo(x1^2 + x1); type(a1)
<class 'sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic_with_category.element_class'>
sage: ZZ(S1(-3))
TypeError: unable to coerce <class 'sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic_with_category.element_class'> to an integer

comment:41 in reply to: ↑ 40 Changed 9 months ago by nbruin

Replying to mantepse:

There seems to be a bug. Quotients of multivariate polynomial rings do coerce to integers

These are conversions, not coercions. The idea is that a coercion is only considered if there is a canonical, mathematically motivated, morphism available. Coercions are performed automatically (for instance in 1 + a and things like that).

Conversions are explicit: ZZ(...), and are allowed to perform a "best effort" attempt at creating an appropriate element, with the basic rule that if a coercion is available to create such an element, then the result should be compatible with that.

It is definitely desirable to reduce inconsistencies in conversions, but since they are inherently allowed to be a bit ill-defined (or partial, as with conversion from QQ to ZZ), inconsistencies are going to be unavoidable.

I would therefore propose to move the request that conversions from univariate quotient rings to subrings of the base ring get harmonized with those of multivariate quotient rings to another ticket, so that this (critical!) ticket can be closed.

On that ticket, relevant information might be:

sage:  R.<x,y> = QQ[]; S.<a,b> = R.quo(x^2 + y^2);
sage: ZZ.coerce_map_from(S) is None
True
sage: ZZ.convert_map_from(S)
Conversion via _integer_ method map:
  From: Quotient of Multivariate Polynomial Ring in x, y over Rational Field by the ideal (x^2 + y^2)
  To:   Integer Ring

In the univariate case another map gets picked up; one that apparently always fails.

sage: R.<x>=QQ[]; S.<a>=R.quo(x^2+1)
sage: m=ZZ.convert_map_from(S); m
Conversion map:
  From: Univariate Quotient Polynomial Ring in a over Rational Field with modulus x^2 + 1
  To:   Integer Ring

This map simply ends up calling ZZ._element_constructor_(<argument>), which fails.

So the difference seems to be whether an _integer_ method is available on the elements.

Last edited 9 months ago by nbruin (previous) (diff)

comment:42 Changed 9 months ago by mantepse

done! (#26970)

comment:43 in reply to: ↑ 35 Changed 9 months ago by gh-jvpeetz

Just for completeness, I want to add that the conversion in the second line of

y = t^2 + t + 1
ZZ(y.list(), 2)

works in 7.6 and 8.2, but is broken in 8.5 and 8.5 with Martin's fixes. On the other side, this conversion

ZZ(y.lift().list(), 2)

works in 7.6, 8.2. and 8.5. Only with Martin's fixes it fails.

comment:44 Changed 9 months ago by mantepse

Yes, I think that's a consequence of the problems with conversion. The elements of y.lift().list() are Boolean polynomials, and with my fix they lost the conversion to ZZ.

It's great and helpful that you tested all this!

comment:45 Changed 8 months ago by embray

  • Milestone changed from sage-8.6 to sage-8.7

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

comment:46 Changed 8 months ago by rburing

This bug was also encountered on Ask SageMath. The workaround to restore the old behavior is

from sage.rings.polynomial.polynomial_quotient_ring import PolynomialQuotientRing_generic
PQ = PolynomialQuotientRing_generic(P, X^4+X+1, 't')
t = PQ.gen()

but of course the underlying issue should be addressed.

comment:47 Changed 7 months ago by mantepse

Is there any interest in this ticket? Should I rebase?

comment:48 Changed 6 months ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Moving all blocker/critical issues from 8.7 to 8.8.

comment:49 Changed 3 months ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

Note: See TracTickets for help on using tickets.