units in polynomial rings with prime power characteristic

[tdupu]

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

Depends on #22454

Component: algebra

Stopgaps: todo

Author: Mark Saaltink

Branch/Commit: u/vdelecroix/11537 @ 718b0e2

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

[tdupu]

Attachment: units_mod_p.sws.gz

[tdupu]

comment:1

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

[sagetrac-jakobkroeker]

Stopgaps: todo

[sagetrac-msaaltink]

Branch: u/msaaltink/units_in_polynomial_rings_with_prime_power_characteristic

[sagetrac-msaaltink]

Dependencies: #22454

[sagetrac-msaaltink]

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.

[sagetrac-msaaltink]

Commit: 6f53ed4

[sagetrac-msaaltink]

Author: Mark Saaltink

[tscrim]

comment:9

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

[sagetrac-msaaltink]

comment:10

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.

[tscrim]

comment:11

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

[sagetrac-msaaltink]

comment:12

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.

[sagetrac-git]

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

033f662

Improved the algorithm documentation for _inverse_of_unit_polynomial.

[sagetrac-git]

Changed commit from 6f53ed4 to 033f662

[sagetrac-msaaltink]

comment:14

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

[fchapoton]

comment:15

branch does not apply on latest beta

[videlec]

comment:28

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'

[videlec]

comment:29

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]
**********************************************************************

[sagetrac-msaaltink]

comment:30

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?

[videlec]

comment:31

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

[videlec]

comment:32

Replying to @sagetrac-msaaltink:

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

Yes!

[videlec]

comment:33

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.

[sagetrac-git]

Changed commit from 39709c4 to 4fa92cb

[sagetrac-git]

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

deb835c	Merge branch 'develop' into t/11537/units_in_polynomial_rings_with_prime_power_characteristic
4fa92cb	Fixed doctests for `inverse_of_unit_polynomial`.

[fchapoton]

comment:36

does not apply

[sagetrac-git]

Changed commit from 4fa92cb to 03bb954

[sagetrac-git]

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

[videlec]

comment:39

I added a commit to introduce constant_coefficient for infinite polynomial rings. Please review.

---

New commits:

718b0e2

11537: constant_coefficient for infinite polynomial

[videlec]

Changed commit from 03bb954 to 718b0e2

[videlec]

Changed branch from u/msaaltink/units_in_polynomial_rings_with_prime_power_characteristic to u/vdelecroix/11537

[sagetrac-msaaltink]

comment:40

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.

[videlec]

comment:41

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.

[videlec]

comment:42

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

[sagetrac-msaaltink]

comment:43

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.