Type inconsistencies in polynomial factorization

[videlec]

This ticket fixes a lot of inconsistencies with factorization (structure/factorization.py). For example the unit was not forced to belong to the universe of the factorization

sage: R.<x> = ZZ[]
sage: parent((x+1).factor().unit())
Univariate Polynomial Ring in x over Integer Ring
sage: parent(R.one().factor().unit())
Integer Ring

Also fixes #20607

CC: @slel

Component: algebra

Keywords: factor, polynomial, Laurent polynomial

Author: Vincent Delecroix

Branch/Commit: u/vdelecroix/20214 @ 4dde5ce

Reviewer: Miguel Marco

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

[behackl]

comment:1

I've fixed this to return the unit as an element of the base ring, as it is done for the rationals or by the factorization with Pari.

---

New commits:

fea118f	fix inconsistency
6b865e3	add doctests

[behackl]

Author: Benjamin Hackl

[behackl]

Commit: 6b865e3

[behackl]

Branch: u/behackl/polynomial/unit-parent-inconsistent

[behackl]

comment:2

... the doctest failures show that fixing this does require more effort than that. ;-)

[videlec]

comment:3

Factorization is aimed to be a generic class, not only polynomials. I am a little bit worried about your one line change (and patchbot as well). For example the free group has no base ring and matrix groups (GL or SL) have no multiplication defined with element of the base ring.

Note that some of the patchbot issue is just because _repr_ of Factorization is bad. I will add a commit for that.

[videlec]

Changed commit from 6b865e3 to none

[videlec]

Changed branch from u/behackl/polynomial/unit-parent-inconsistent to u/vdelecroix/20214

[sagetrac-git]

Commit: d1583d8

[sagetrac-git]

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

fea118f	fix inconsistency
6b865e3	add doctests
d1583d8	Trac 20214: better `_repr_` for Factorization

[tscrim]

comment:6

The biggest issue seems to be that the matrix group code was relying on the current behavior for its factorization. Although I am somewhat more inclined to think the current behavior is the correct way to go because the units do not have to live in the base ring in general. Also from looking at the code, I don't see this fixing things if you work over QQ[].

BTW, you should use .one(). It is usually cached, making construction of units in more non-trivial rings much faster and doesn't have to use the coercion framework.

[behackl]

Changed commit from d1583d8 to e7d04c2

[behackl]

Changed branch from u/vdelecroix/20214 to u/behackl/polynomial/unit-parent-inconsistent

[behackl]

comment:7

With the changes to the representation string and by fixing a silly error I made earlier (pushed one commit), there's just one failure remaining. It seems that the action from a finite field onto the general linear group is not implemented; I think that should be possible. E.g.:

sage: G = GL(3,5); F = G.base_ring()
sage: F(2) * G.one()
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '*': 'Finite Field of size 5' and 'General Linear Group of degree 3 over Finite Field of size 5'

Should this be handled on this ticket as well or should we open a separate ticket? (Personally, I'm for a separate ticket...)

---

New commits:

e7d04c2

fix calling base_ring

[tscrim]

comment:8

I think that is a separate bug that does need to be fixed. +1 to a separate ticket (but it might be needed as a dependency).

[videlec]

comment:9

It is not that trivial to fix. The thing is that you can not multiply by 0 in GL and there are much more restriction in SL... So the action should not go through a coercion.

[videlec]

comment:10

And still the free group has no base ring... you would better do

try:
    unit = self.__universe.base_ring().one()
except XXX:
    try:
        unit = self.__universe.one()
    except XXX
        unit = Integer(1)

And as Travis mentionned in comment:6 it is not clear to me either if this is the way to go.

[behackl]

comment:11

Replying to @videlec:

It is not that trivial to fix. The thing is that you can not multiply by 0 in GL and there are much more restriction in SL... So the action should not go through a coercion.

I'd propose to implement _lmul_ and _rmul_; I agree that embedding via coercion is not practicable.

Regarding the base_ring and the fact that there might not be one: yes, that has to be taken care of. I haven't thought of that because I was implementing the original version with #20086 in mind. I can't really contribute to the discussion which approach is the most suitable; it just has to be consistent.

[miguelmarco]

comment:12

My two cents: factoring makes sense in rings (more precisely, in UFD's), so the factors and the unit should be in the corresponding ring.

So, I think that the correct behaviour should be the opposite of what you propose. That is, we should have:

sage: R.<x> = ZZ[]
sage: parent((x+1).factor().unit())
Univariate Polynomial Ring in x over Integer Ring
sage: parent(R.one().factor().unit())
Univariate Polynomial Ring in x over Integer Ring

There might be rings (e.g. Laurent polynomials) with units that are not in the rings base ring. So the only possible consistent behaviour is to have the units in the ring (and not in its base ring).

[videlec]

comment:13

Of course. But in some cases, the units live in a well identified subgring. And it makes sense to keep them here. For me it would still be acceptable if the parent of the unit only had a coercion to the main ring. But of course this should be done consistently for a given ring. Hence the creation of this ticket.

I agree that it is much simpler to enforce the unit to belong in the same ring (or more generally multiplicative semigroup).

[videlec]

New commits:

d9fb575	Trac 20214: Enhancement of factorization
ee6ac00	Trac 20214: Fix doctests

[videlec]

Changed branch from u/behackl/polynomial/unit-parent-inconsistent to u/vdelecroix/20214

[videlec]

Changed commit from e7d04c2 to ee6ac00

[embray]

comment:39

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

comment:40

Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).

[embray]

comment:41

Ticket retargeted after milestone closed

[mkoeppe]

comment:42

Possibly related: #29076

[videlec]

comment:43

Replying to @mkoeppe:

Possibly related: #29076

it is not.

[mkoeppe]

comment:44

Moving tickets to milestone sage-9.2 based on a review of last modification date, branch status, and severity.

[mkoeppe]

comment:46

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:47

Setting a new milestone for this ticket based on a cursory review.