Opened 7 years ago

Last modified 17 months ago

#11537 needs_work defect

units in polynomial rings with prime power characteristic

Reported by: tdupu Owned by: AlexGhitza
Priority: major Milestone: sage-8.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)

units_mod_p.sws (1.9 KB) - added by tdupu 7 years ago.

Download all attachments as: .zip

Change History (44)

Changed 7 years ago by tdupu

comment:1 Changed 7 years ago by tdupu

--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.

comment:2 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 3 years ago by jakobkroeker

  • Stopgaps set to todo

comment:7 Changed 22 months ago by msaaltink

  • Branch set to u/msaaltink/units_in_polynomial_rings_with_prime_power_characteristic

comment:8 Changed 22 months ago by msaaltink

  • Authors set to Mark Saaltink
  • Commit set to 6f53ed4c3378f757b4dfc51ed32240513329e41c
  • Dependencies set to #22454
  • Status changed from new to needs_review

New commits:

429dde8Trac 22454 - fixed is_unit and implemented is_nilpotent for multivariate and infinite polynomials.
c42072dSmall speedup in is_unit for multivariate polynomials
eed858dImplemented inverse_of_unit for polynomials; fixes trac 11537.
6f53ed4inverse_of_unit_polynomial: use inverse_of_unit when possible.

comment:9 Changed 21 months ago by tscrim

-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 21 months ago by msaaltink

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 non-integral 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 21 months ago by tscrim

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 21 months ago by msaaltink

I asked about the Singular functions used here, in the Singular forum, post 2582 (https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=2582). The answer (from "hannes") is quite clear:

p_Invers: is only a helper routine for the 3-argument 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 21 months ago by git

  • Commit changed from 6f53ed4c3378f757b4dfc51ed32240513329e41c to 033f662f22e68c01e804936f18a0e329e0aeff51

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

033f662Improved the algorithm documentation for _inverse_of_unit_polynomial.

comment:14 Changed 21 months ago by msaaltink

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#section-latex-typeset).

comment:15 Changed 19 months ago by chapoton

  • Status changed from needs_review to needs_work

branch does not apply on latest beta

comment:16 Changed 19 months ago by git

  • Commit changed from 033f662f22e68c01e804936f18a0e329e0aeff51 to ccd4ec574747204901ccd06460d906e2b55d15f3

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

ccd4ec5Merged to resolve conflicts with latest development version

comment:17 Changed 19 months ago by msaaltink

  • 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 19 months ago by git

  • Commit changed from ccd4ec574747204901ccd06460d906e2b55d15f3 to c2b5f08e9e8c1d1ea0cc16afebdff774dd20af72

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

c2b5f08Fixed up some whitespace errors

comment:19 Changed 19 months ago by vdelecroix

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 follow-up: Changed 19 months ago by msaaltink

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 down---there 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 19 months ago by vdelecroix

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 non-constant polynomial.
# We use the generic function created in trac ticket #11537

comment:22 Changed 19 months ago by git

  • Commit changed from c2b5f08e9e8c1d1ea0cc16afebdff774dd20af72 to 87495bf6bc9376914a972fffa0830b18ad839d62

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

87495bfImplemented changes suggested by vdelecroix.

comment:23 Changed 19 months ago by vdelecroix

  • Milestone changed from sage-6.4 to sage-8.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 follow-up: Changed 19 months ago by msaaltink

4) Do you mean that I should add a run-time 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 ring---sometimes it is in the fraction field. I will try clarifying the comment.

  1. Good idea; I'll do that.

comment:25 in reply to: ↑ 24 Changed 19 months ago by vdelecroix

Replying to msaaltink:

4) Do you mean that I should add a run-time 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_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 ring---sometimes 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 18 months ago by git

  • Commit changed from 87495bf6bc9376914a972fffa0830b18ad839d62 to 39709c46a116c2413033360dc62e366ed3461201

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

39709c4A few more tests and a small optimization

comment:27 Changed 18 months ago by msaaltink

  • 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 18 months ago by vdelecroix

Matrices form a non-commutative 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 18 months ago by vdelecroix

  • Status changed from needs_review to needs_work

and doctest failure

sage -t --long --warn-long 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 follow-up: Changed 18 months ago by msaaltink

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 18 months ago by vdelecroix

Note that I did the testing on top of beta12 which might explain the changes.

comment:32 in reply to: ↑ 30 Changed 18 months ago by vdelecroix

Replying to msaaltink:

Would it be cheating for me to create such a ring in the doctest?

Yes!

comment:33 Changed 18 months ago by vdelecroix

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 18 months ago by git

  • Commit changed from 39709c46a116c2413033360dc62e366ed3461201 to 4fa92cb75fb00e71a91f3653b44323ea043e44b0

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

deb835cMerge branch 'develop' into t/11537/units_in_polynomial_rings_with_prime_power_characteristic
4fa92cbFixed doctests for `inverse_of_unit_polynomial`.

comment:35 Changed 18 months ago by msaaltink

  • Status changed from needs_work to needs_review

comment:36 Changed 18 months ago by chapoton

  • Status changed from needs_review to needs_work

does not apply

comment:37 Changed 17 months ago by git

  • Commit changed from 4fa92cb75fb00e71a91f3653b44323ea043e44b0 to 03bb9542c14c8f1aec14460e84ecd22054519477

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

03bb954Merge branch 'develop' into t/11537/units_in_polynomial_rings_with_prime_power_characteristic

comment:38 Changed 17 months ago by msaaltink

  • Status changed from needs_work to needs_review

comment:39 Changed 17 months ago by vdelecroix

  • 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:

718b0e211537: constant_coefficient for infinite polynomial

comment:40 Changed 17 months ago by msaaltink

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 17 months ago by vdelecroix

  • 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 17 months ago by vdelecroix

Note that many methods would be simplified if the attribute _p would consistently be a polynomial...

comment:43 Changed 17 months ago by msaaltink

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.

Note: See TracTickets for help on using tickets.