Opened 10 years ago

# units in polynomial rings with prime power characteristic

Reported by: Owned by: tdupu AlexGhitza major sage-8.0 algebra Mark Saaltink N/A u/vdelecroix/11537 718b0e2c0526e6000f1608ddfc2853f0c4bd19c0 #22454 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
```

### comment:1 Changed 10 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 8 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:3 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:4 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:5 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:6 Changed 6 years ago by jakobkroeker

• Stopgaps set to todo

### comment:7 Changed 4 years ago by msaaltink

• Branch set to u/msaaltink/units_in_polynomial_rings_with_prime_power_characteristic

### comment:8 Changed 4 years 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:

 ​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 4 years 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 4 years 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 4 years 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 4 years 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 4 years ago by git

• 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 4 years 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 4 years ago by chapoton

• Status changed from needs_review to needs_work

branch does not apply on latest beta

### comment:16 Changed 4 years ago by git

• 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 4 years 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 4 years ago by git

• 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 4 years 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: ↓ 21 Changed 4 years 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 4 years ago by vdelecroix

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 4 years ago by git

• 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 4 years 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: ↓ 25 Changed 4 years 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 4 years ago by vdelecroix

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 4 years ago by git

• 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 4 years 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 4 years 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 4 years 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: ↓ 32 Changed 4 years 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 4 years 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 4 years ago by vdelecroix

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

Yes!

### comment:33 Changed 4 years 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 4 years ago by git

• Commit changed from 39709c46a116c2413033360dc62e366ed3461201 to 4fa92cb75fb00e71a91f3653b44323ea043e44b0

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

### comment:35 Changed 4 years ago by msaaltink

• Status changed from needs_work to needs_review

### comment:36 Changed 4 years ago by chapoton

• Status changed from needs_review to needs_work

does not apply

### comment:37 Changed 4 years ago by git

• 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 4 years ago by msaaltink

• Status changed from needs_work to needs_review

### comment:39 Changed 4 years 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:

 ​718b0e2 `11537: constant_coefficient for infinite polynomial`

### comment:40 Changed 4 years 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 4 years 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 4 years ago by vdelecroix

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

### comment:43 Changed 4 years 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.