Opened 7 years ago
Last modified 15 months ago
#11537 needs_work defect
units in polynomial rings with prime power characteristic
Reported by:  tdupu  Owned by:  AlexGhitza 

Priority:  major  Milestone:  sage8.0 
Component:  algebra  Keywords:  
Cc:  Merged in:  
Authors:  Mark Saaltink  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/vdelecroix/11537 (Commits)  Commit:  718b0e2c0526e6000f1608ddfc2853f0c4bd19c0 
Dependencies:  #22454  Stopgaps:  todo 
Description
sage: p = 101 sage: S.<t> = PolynomialRing(ZZ.quotient_ring(p^3)) sage: f = 1+p*t^2 sage: f.is_unit() True
sage: S.<t> = PolynomialRing(ZZ.quotient_ring(p^3),1) sage: t = S.0 sage: f = 1+p*t^2 sage: f.is_unit() False sage: f.inverse_of_unit() ... ArithmeticError: Element is not a unit.
sage: S1.<t> = PolynomialRing(ZZ.quotient_ring(p^3),1) sage: S2.<tt> = PolynomialRing(ZZ.quotient_ring(p^3)) sage: S1 Multivariate Polynomial Ring in t over Ring of integers modulo 1030301 sage: S2 Univariate Polynomial Ring in tt over Ring of integers modulo 1030301 sage: S1 == S2 False
Attachments (1)
Change History (44)
Changed 7 years ago by
comment:1 Changed 7 years ago by
comment:2 Changed 5 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:3 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:4 Changed 4 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:5 Changed 4 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:6 Changed 3 years ago by
 Stopgaps set to todo
comment:7 Changed 20 months ago by
 Branch set to u/msaaltink/units_in_polynomial_rings_with_prime_power_characteristic
comment:8 Changed 20 months ago by
 Commit set to 6f53ed4c3378f757b4dfc51ed32240513329e41c
 Dependencies set to #22454
 Status changed from new to needs_review
New commits:
429dde8  Trac 22454  fixed is_unit and implemented is_nilpotent for multivariate and infinite polynomials.

c42072d  Small speedup in is_unit for multivariate polynomials

eed858d  Implemented inverse_of_unit for polynomials; fixes trac 11537.

6f53ed4  inverse_of_unit_polynomial: use inverse_of_unit when possible.

comment:9 Changed 20 months ago by
1 on removing the specialized code that uses Singular; at least I strongly suspect that is faster. You should be able to specify quickly in which cases you should punt up to the generic code. Also, don't use $x$
for latex, instead use `x`
.
comment:10 Changed 20 months ago by
Re: "1 on removing the specialized code that uses Singular": Yes, it is fast, but does not get the correct answers. The same goes for libsingular's p_IsUnit. For some reason I am having trouble finding the documentation in libsingular that explains these two functions so do not know if they are even supposed to work in these nonintegral domains. I think the safest thing for now is to use the generic code to get the correct answer.
I'll look into the latex issue and push something soon.
comment:11 Changed 20 months ago by
As I said, I would probably send it up to the generic case when the base ring is not something nice. Probably a good condition is if the domain is known to be an integral domain, then use the specialized code. You should also post a bug report to Singular if using this in general is expected to work (provided you can find such information).
comment:12 Changed 20 months ago by
I asked about the Singular functions used here, in the Singular forum, post 2582 (https://www.singular.unikl.de/forum/viewtopic.php?f=10&t=2582). The answer (from "hannes") is quite clear:
p_Invers: is only a helper routine for the 3argument forms of jet [...] It should not be used otherwise: is a static routine in newer releases Furthermore, the coefficients must be from a field. p_IsUnit: is currently only used to simplify ideals, and currently defined as: p is a constant polynomial and the constant is a unit. I will try to extend that.....but it is of low priority.
So I think the specialized code in multi_polynomial_libsingular canniot be relied on, and we should stick with the generic code. The Singular documentation offers no other functions that look useful here.
comment:13 Changed 20 months ago by
 Commit changed from 6f53ed4c3378f757b4dfc51ed32240513329e41c to 033f662f22e68c01e804936f18a0e329e0aeff51
Branch pushed to git repo; I updated commit sha1. New commits:
033f662  Improved the algorithm documentation for _inverse_of_unit_polynomial.

comment:14 Changed 19 months ago by
I have made the change from $x$ to x
in the above commit. This makes the documentation look better in the interactive console, which is not something I knew after reading the developer guide's section on Latex (http://doc.sagemath.org/html/en/developer/coding_basics.html#sectionlatextypeset).
comment:15 Changed 17 months ago by
 Status changed from needs_review to needs_work
branch does not apply on latest beta
comment:16 Changed 17 months ago by
 Commit changed from 033f662f22e68c01e804936f18a0e329e0aeff51 to ccd4ec574747204901ccd06460d906e2b55d15f3
Branch pushed to git repo; I updated commit sha1. New commits:
ccd4ec5  Merged to resolve conflicts with latest development version

comment:17 Changed 17 months ago by
 Status changed from needs_work to needs_review
Merged in the latest 'develop' branch, as suggested in the "advanced git" section of the developer guide for this situation. I would have thought a rebase would be easier.
comment:18 Changed 17 months ago by
 Commit changed from ccd4ec574747204901ccd06460d906e2b55d15f3 to c2b5f08e9e8c1d1ea0cc16afebdff774dd20af72
Branch pushed to git repo; I updated commit sha1. New commits:
c2b5f08  Fixed up some whitespace errors

comment:19 Changed 17 months ago by
1) Because it is private, the function _inverse_of_unit_polynomial
and its documentation will not appear in the reference manual. I would prefer to have it public and have pointers from the various methods (via :func:XXX
) to this function. These are implementation details but which might be of importance for advanced users. The algorithm in only explained in the function.
2) Wouldn't be easy to fix the following?
sage: R(5).inverse_of_unit() Traceback (most recent call last): ... AttributeError: <class 'sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial_sparse'> has no attribute constant_coefficient
3) As far as I understand, singular call works in some cases. If this is the case, you would better keep it. You can easily make something like the following that is also done in other places in Sage
def inverse_of_unit(self, algorithm=None): if algorithm is None: ... set algorithm to what is best ... if algorithm == 'singular': if self.base_ring().is_not_appropriate(): raise ValueError('does not work') ... singular imple ... elif algorithm == 'generic': ... what is provide in the branch ... else: raise ValueError('unknown algorithm %s' %algorithm)
comment:20 followup: ↓ 21 Changed 17 months ago by
1) Good idea; I'll make those changes.
2) The fix is not as easy as I had hoped. I have a branch open on ticket 22514 to fix this, but the way these constant infinite polynomials get created is hard to pin downthere are strange coercion things happening. I'll get back at it and hope to have a fix soon.
3) The singular call works only when the polynomial is constant, so that all we do is invert the constant coefficient in the base ring. I don't see this as worth going to singular for.
comment:21 in reply to: ↑ 20 Changed 17 months ago by
Replying to msaaltink:
3) The singular call works only when the polynomial is constant, so that all we do is invert the constant coefficient in the base ring. I don't see this as worth going to singular for.
Indeed. So if Singular is that bad, remove the code. Do not put comments everywhere. You can keep a line or two of explanations
# Singular seems not able to invert nonconstant polynomial. # We use the generic function created in trac ticket #11537
comment:22 Changed 17 months ago by
 Commit changed from c2b5f08e9e8c1d1ea0cc16afebdff774dd20af72 to 87495bf6bc9376914a972fffa0830b18ad839d62
Branch pushed to git repo; I updated commit sha1. New commits:
87495bf  Implemented changes suggested by vdelecroix.

comment:23 Changed 17 months ago by
 Milestone changed from sage6.4 to sage8.0
 Status changed from needs_review to needs_work
4) Could you add some checks that the parent is indeed correct, e.g.
sage: R.<x> = Zmod(32)[] sage: inverse_of_unit_polynomial(1 + 4*x) 16*x^2 + 28*x + 1 sage: inverse_of_unit_polynomial(1 + 4*x) is R True
5) I do not see where the following error is tested
except AttributeError: v = ~u # many rings don't implement inverse_of_unit if v.parent() is not p.base_ring(): raise NotImplementedError
6) In order to avoid coercion, it would be better to define mp1 = m + 1
and use it in the loop. In the same veine, change while p*i != 1
to while not (p * i).is_one()
comment:24 followup: ↓ 25 Changed 17 months ago by
4) Do you mean that I should add a runtime check of some sort, or did you mean I should add an EXAMPLE or TEST?
5) In context, that code is
try: v = u.inverse_of_unit() except AttributeError: v = ~u # many rings don't implement inverse_of_unit
Perhaps the comment is misplaced; the except block is executed in cases where v = u.inverse_of_unit()
is not implemented  which is for many rings. Perhaps I should also check for NotImplementedError
. The fallback is to use ~v
if it is in the correct ringsometimes it is in the fraction field. I will try clarifying the comment.
 Good idea; I'll do that.
comment:25 in reply to: ↑ 24 Changed 17 months ago by
Replying to msaaltink:
4) Do you mean that I should add a runtime check of some sort, or did you mean I should add an EXAMPLE or TEST?
Not at runtime. Only inside EXAMPLES
or/and TESTS
(but it can still be rather exhaustive).
5) In context, that code is
try: v = u.inverse_of_unit() except AttributeError: v = ~u # many rings don't implement inverse_of_unitPerhaps the comment is misplaced; the except block is executed in cases where
v = u.inverse_of_unit()
is not implemented  which is for many rings. Perhaps I should also check forNotImplementedError
. The fallback is to use~v
if it is in the correct ringsometimes it is in the fraction field. I will try clarifying the comment.
It was not my point. My comment was about the two lines
if v.parent() is not p.base_ring(): raise NotImplementedError
This NotImplementedError
does not appear in doctests.
comment:26 Changed 16 months ago by
 Commit changed from 87495bf6bc9376914a972fffa0830b18ad839d62 to 39709c46a116c2413033360dc62e366ed3461201
Branch pushed to git repo; I updated commit sha1. New commits:
39709c4  A few more tests and a small optimization

comment:27 Changed 16 months ago by
 Status changed from needs_work to needs_review
The last set of comments have been addressed in this latest commit:
4) has been done, with 3 more test cases
5) this condition is now tested.
6) m + 1
cannot be pulled out of the loop because m
is changed on every iteration. I did however make the change from p*i != 1
to not (p*i).is_one()
.
comment:28 Changed 16 months ago by
Matrices form a noncommutative ring... you expect your algorithm to work in this case? Anyway, I am not sure it is good idea to use this in tests as it is completely broken
sage: M=MatrixSpace(QQ, 2, 2); S.<y> = M[] sage: p = M.one() + y * M([0,2,0,0]) sage: inverse_of_unit_polynomial(p) Traceback (most recent call last): ... AttributeError: 'MatrixSpace_with_category' object has no attribute 'is_integral_domain'
comment:29 Changed 16 months ago by
 Status changed from needs_review to needs_work
and doctest failure
sage t long warnlong 75.4 rings/polynomial/polynomial_element.pyx ********************************************************************** File "rings/polynomial/polynomial_element.pyx", line 9680, in sage.rings.polynomial.polynomial_element.inverse_of_unit_polynomial Failed example: inverse_of_unit_polynomial(S(1)) Expected: Traceback (most recent call last): ... NotImplementedError: Base ring, Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in x over Integer Ring, does not implement inverse_of_unit. Got: [1 0] [0 1] **********************************************************************
comment:30 followup: ↓ 32 Changed 16 months ago by
That is strange; the doctest succeeds for me. However, as you point out, it is not good to use a noncommutative base ring. I do not think I then have a test for the condition triggering the NotImplementedError
, as the place this situation used to occur was in polynomial rings, and is fixed by this patch. Still, I'm reluctant to take the untested code out, as a ring could be added in future that also has this feature (no inverse_of_unit
and ~
taking us to a different ring). Would it be cheating for me to create such a ring in the doctest?
comment:31 Changed 16 months ago by
Note that I did the testing on top of beta12 which might explain the changes.
comment:32 in reply to: ↑ 30 Changed 16 months ago by
comment:33 Changed 16 months ago by
When I try to build a complicated base ring, is_nilpotent
or is_unit
is not implemented.
Keep the code the way it is, but merge with beta12 and fix the doctest.
comment:34 Changed 16 months ago by
 Commit changed from 39709c46a116c2413033360dc62e366ed3461201 to 4fa92cb75fb00e71a91f3653b44323ea043e44b0
comment:35 Changed 16 months ago by
 Status changed from needs_work to needs_review
comment:37 Changed 16 months ago by
 Commit changed from 4fa92cb75fb00e71a91f3653b44323ea043e44b0 to 03bb9542c14c8f1aec14460e84ecd22054519477
Branch pushed to git repo; I updated commit sha1. New commits:
03bb954  Merge branch 'develop' into t/11537/units_in_polynomial_rings_with_prime_power_characteristic

comment:38 Changed 16 months ago by
 Status changed from needs_work to needs_review
comment:39 Changed 16 months ago by
 Branch changed from u/msaaltink/units_in_polynomial_rings_with_prime_power_characteristic to u/vdelecroix/11537
 Commit changed from 03bb9542c14c8f1aec14460e84ecd22054519477 to 718b0e2c0526e6000f1608ddfc2853f0c4bd19c0
I added a commit to introduce constant_coefficient
for infinite polynomial rings. Please review.
New commits:
718b0e2  11537: constant_coefficient for infinite polynomial

comment:40 Changed 16 months ago by
While this is a straightforward change that makes an additional test case work, I had really hoped for a more comprehensive answer to the problems identified in trac #22514. In my opinion, the right fix is to ensure that the _p
attribute on an infinite polynomial is always in fact a polynomial, which would fix the constant coefficient
problem as well as the many others identified in #22514. That fix, if made, would make this new method unnecessary.
comment:41 Changed 16 months ago by
 Status changed from needs_review to needs_work
I would be happy to have it the other way around, but then you should first fix #22514. Your branch attached to this ticket introduces a regression which is not good.
comment:42 Changed 16 months ago by
Note that many methods would be simplified if the attribute _p
would consistently be a polynomial...
comment:43 Changed 15 months ago by
I have pushed a proposed fix for #22514; if accepted it will make commit 718b0e2 unnecessary and will allow the test case for constant elements of an InfinitePolynomialRing
to be successful.
There are lots of "inverse_of_unit" methods one should implement while they are fixing this the attached notebook shows one way this can be done from prime power characteristic.