Opened 4 years ago

Last modified 3 months ago

#20214 needs_work defect

Type inconsistencies in polynomial factorization

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-8.9
Component: algebra Keywords: factor, polynomial, Laurent polynomial
Cc: slelievre Merged in:
Authors: Vincent Delecroix Reviewers: Miguel Marco
Report Upstream: N/A Work issues:
Branch: u/vdelecroix/20214 (Commits) Commit: 4dde5ce2b4ab02530e4e6bdfe7df0cace8c122b0
Dependencies: Stopgaps:

Description (last modified by 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

Change History (40)

comment:1 Changed 3 years ago by behackl

  • Authors set to Benjamin Hackl
  • Branch set to u/behackl/polynomial/unit-parent-inconsistent
  • Commit set to 6b865e3f00584a1320055d1c479b56d56b8973b6
  • Status changed from new to needs_review

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:

fea118ffix inconsistency
6b865e3add doctests

comment:2 Changed 3 years ago by behackl

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

comment:3 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to needs_work

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.

comment:4 Changed 3 years ago by vdelecroix

  • Branch changed from u/behackl/polynomial/unit-parent-inconsistent to u/vdelecroix/20214
  • Commit 6b865e3f00584a1320055d1c479b56d56b8973b6 deleted

comment:5 Changed 3 years ago by git

  • Commit set to d1583d8cedac98c38e0fdad3e4dc083161cf0242

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

fea118ffix inconsistency
6b865e3add doctests
d1583d8Trac 20214: better _repr_ for Factorization

comment:6 Changed 3 years ago by 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.

comment:7 Changed 3 years ago by behackl

  • Branch changed from u/vdelecroix/20214 to u/behackl/polynomial/unit-parent-inconsistent
  • Commit changed from d1583d8cedac98c38e0fdad3e4dc083161cf0242 to e7d04c28ada863dd70b254707848bb57d3e65a35

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:

e7d04c2fix calling base_ring

comment:8 Changed 3 years ago by 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).

comment:9 follow-up: Changed 3 years ago by 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.

comment:10 Changed 3 years ago by 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.

comment:11 in reply to: ↑ 9 Changed 3 years ago by 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.

comment:12 Changed 3 years ago by 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).

comment:13 Changed 3 years ago by 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).

comment:14 Changed 3 years ago by vdelecroix

  • Branch changed from u/behackl/polynomial/unit-parent-inconsistent to u/vdelecroix/20214
  • Commit changed from e7d04c28ada863dd70b254707848bb57d3e65a35 to ee6ac003dfcfd5fbc53cb83f42c6e094a45d59d3
  • Milestone changed from sage-7.1 to sage-7.3

New commits:

d9fb575Trac 20214: Enhancement of factorization
ee6ac00Trac 20214: Fix doctests

comment:15 Changed 3 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:16 Changed 3 years ago by vdelecroix

  • Authors changed from Benjamin Hackl to Vincent Delecroix

comment:17 follow-up: Changed 3 years ago by 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.

comment:18 in reply to: ↑ 17 Changed 3 years ago by 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!

comment:19 Changed 3 years ago by mmarco

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

comment:20 Changed 3 years ago by 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.

comment:21 Changed 3 years ago by mmarco

  • Reviewers set to Miguel Marco

Fair enough. Raise error it is.

comment:22 Changed 3 years ago by 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`)::

comment:23 Changed 3 years ago by git

  • Commit changed from ee6ac003dfcfd5fbc53cb83f42c6e094a45d59d3 to d7835a2f3b6076920316786a252a24c2c9164f47

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

883e07bTrac 20214: simpler constructor + error in negation
91b40fcTrac 20214: several fixes and doctests
d7835a2Trac 20214: doc formatting

comment:24 Changed 3 years ago by git

  • Commit changed from d7835a2f3b6076920316786a252a24c2c9164f47 to 5003a3880a792071fecebaab0a6d64a8a72958b1

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

5003a38Trac 20214: fix invert and pow for factorization

comment:25 Changed 3 years ago by git

  • Commit changed from 5003a3880a792071fecebaab0a6d64a8a72958b1 to e593605befca1728288dacb0d08a7414ade012df

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

b5dceceTrac 20214: fix doctests
e593605Trac 20214: fixing doctests in sage/tests/

comment:26 Changed 3 years ago by 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())

comment:27 Changed 3 years ago by git

  • Commit changed from e593605befca1728288dacb0d08a7414ade012df to 12ad05922d1df8b27db452d6116bb91632bdafc6

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

12ad059Trac 20214: one more doctest

comment:28 Changed 3 years ago by vdelecroix

ping?

comment:29 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

no longer applies

comment:30 follow-up: Changed 9 months ago by slelievre

This came up again at

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

comment:31 Changed 9 months ago by slelievre

  • Cc slelievre added
  • Keywords factor polynomial Laurent polynomial added
  • Milestone changed from sage-7.3 to sage-8.6

comment:32 Changed 9 months ago by git

  • Commit changed from 12ad05922d1df8b27db452d6116bb91632bdafc6 to 63eeb9e3030672d9e248b6ac7e6a4771fdf74aab

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

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

comment:33 Changed 9 months ago by vdelecroix

  • Description modified (diff)
  • Milestone changed from sage-8.6 to sage-8.7
  • Status changed from needs_work to needs_review

comment:34 in reply to: ↑ 30 ; follow-up: Changed 9 months ago by vdelecroix

Replying to slelievre:

This came up again at

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?

comment:35 Changed 9 months ago by git

  • Commit changed from 63eeb9e3030672d9e248b6ac7e6a4771fdf74aab to 4dde5ce2b4ab02530e4e6bdfe7df0cace8c122b0

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

4dde5ce20214: doctest for 20607

comment:36 Changed 9 months ago by vdelecroix

  • Description modified (diff)

comment:37 in reply to: ↑ 34 Changed 8 months ago by vdelecroix

Replying to vdelecroix:

Replying to slelievre:

This came up again at

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?

comment:38 Changed 7 months ago by chapoton

  • Status changed from needs_review to needs_work

red branch => needs work

comment:39 Changed 6 months ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

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

comment:40 Changed 3 months ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

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

Note: See TracTickets for help on using tickets.