Type inconsistencies in polynomial factorization

[vdelecroix]

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

[behackl]

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]

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

[vdelecroix]

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.

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

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]

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]

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

[vdelecroix]

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.

[vdelecroix]

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]

Replying to vdelecroix:

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.

[mmarco]

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

[vdelecroix]

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

[vdelecroix]

New commits:

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

[mmarco]

Some questions after a first quick look.

Why in this part of the code,

        elif universe is not None:
            x = [(universe(i),j) for i,j in x]
            if unit is None:
                try:
                    unit = universe(1)
                except (ValueError,TypeError):
                    pass

we don't include this first attempt?:

                 try:
                    unit = universe.one()

.

In the neg method we only allow negation of factorizations with unit (from what I have seen, it could happen in parents with no one method, and that doesn't allow to convert 1, not sure if they exist).

Otherwise it looks ok, but I still have to test it a bit more deeply.

[vdelecroix]

Replying to mmarco:

Some questions after a first quick look.

Why in this part of the code,

...

we don't include this first attempt?:

...

Right. It can be simplified a bit.

In the neg method we only allow negation of factorizations with unit (from what I have seen, it could happen in parents with no one method, and that doesn't allow to convert 1, not sure if they exist).

Right, there is a problem here. What should we do for -fac when there is no unit? Raise an error?

Otherwise it looks ok, but I still have to test it a bit more deeply.

Thanks for looking at it!

[mmarco]

Maybe for the -fac problem we could just change the sign to the first factor if there is no unit?

[vdelecroix]

Do you have concrete examples where there is no unit available but x -> -x is well defined (inside Sage of course)? I would rather raise a ValueError.

[mmarco]

Fair enough. Raise error it is.

[chapoton]

bad trac link, see patchbot report:

+inside file:  b/src/sage/structure/factorization.py
+@@ -1054,21 +1067,24 @@ class Factorization(SageObject):
++        Check that it only depends on the universe (trac:`20214`)::

[git]

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

​883e07b	Trac 20214: simpler constructor + error in negation
​91b40fc	Trac 20214: several fixes and doctests
​d7835a2	Trac 20214: doc formatting

[git]

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

​5003a38

Trac 20214: fix invert and pow for factorization

[git]

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

​b5dcece	Trac 20214: fix doctests
​e593605	Trac 20214: fixing doctests in sage/tests/

[chapoton]

one failing doctest

File "src/sage/tests/french_book/polynomes.py", line 144, in sage.tests.french_book.polynomes
Failed example:
    for A in [QQ, ComplexField(16), GF(5), QQ[sqrt(2)]]:
        print("{} :".format(A)); print(A['x'](p).factor())

[git]

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

​12ad059

Trac 20214: one more doctest

[vdelecroix]

ping?

[chapoton]

no longer applies

[slelievre]

This came up again at

• ​Ask Sage question 44764: LaurentPolynomial can't factor constants

Can the work done here be rebased to apply on the latest release?

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​7759218	Trac 20214: Enhancement of factorization
​63eeb9e	Trac 20214: Fix calls to Factorization and doctests

[vdelecroix]

Replying to slelievre:

This came up again at

• ​Ask Sage question 44764: LaurentPolynomial can't factor constants

Can the work done here be rebased to apply on the latest release?

Can you do the review now that it is rebased on your demand?

[git]

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

​4dde5ce

20214: doctest for 20607

[vdelecroix]

Replying to vdelecroix:

Replying to slelievre:

This came up again at

• ​Ask Sage question 44764: LaurentPolynomial can't factor constants

Can the work done here be rebased to apply on the latest release?

Can you do the review now that it is rebased on your demand?

How much time do you need Samuel for the review?

[chapoton]

red branch => needs work

[embray]

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

[embray]

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]

Ticket retargeted after milestone closed

[mkoeppe]

Possibly related: #29076

[vdelecroix]

Replying to mkoeppe:

Possibly related: #29076

it is not.

[mkoeppe]

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