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:  sage8.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 )
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
 Branch set to u/behackl/polynomial/unitparentinconsistent
 Commit set to 6b865e3f00584a1320055d1c479b56d56b8973b6
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
... the doctest failures show that fixing this does require more effort than that. ;)
comment:3 Changed 3 years ago by
 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
 Branch changed from u/behackl/polynomial/unitparentinconsistent to u/vdelecroix/20214
 Commit 6b865e3f00584a1320055d1c479b56d56b8973b6 deleted
comment:5 Changed 3 years ago by
 Commit set to d1583d8cedac98c38e0fdad3e4dc083161cf0242
comment:6 Changed 3 years ago by
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 nontrivial rings much faster and doesn't have to use the coercion framework.
comment:7 Changed 3 years ago by
 Branch changed from u/vdelecroix/20214 to u/behackl/polynomial/unitparentinconsistent
 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:
e7d04c2  fix calling base_ring

comment:8 Changed 3 years ago by
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 followup: ↓ 11 Changed 3 years ago by
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
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
Replying to vdelecroix:
It is not that trivial to fix. The thing is that you can not multiply by
0
inGL
and there are much more restriction inSL
... 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
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
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
 Branch changed from u/behackl/polynomial/unitparentinconsistent to u/vdelecroix/20214
 Commit changed from e7d04c28ada863dd70b254707848bb57d3e65a35 to ee6ac003dfcfd5fbc53cb83f42c6e094a45d59d3
 Milestone changed from sage7.1 to sage7.3
comment:15 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:16 Changed 3 years ago by
comment:17 followup: ↓ 18 Changed 3 years ago by
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
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
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
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:22 Changed 3 years ago by
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
 Commit changed from ee6ac003dfcfd5fbc53cb83f42c6e094a45d59d3 to d7835a2f3b6076920316786a252a24c2c9164f47
comment:24 Changed 3 years ago by
 Commit changed from d7835a2f3b6076920316786a252a24c2c9164f47 to 5003a3880a792071fecebaab0a6d64a8a72958b1
Branch pushed to git repo; I updated commit sha1. New commits:
5003a38  Trac 20214: fix invert and pow for factorization

comment:25 Changed 3 years ago by
 Commit changed from 5003a3880a792071fecebaab0a6d64a8a72958b1 to e593605befca1728288dacb0d08a7414ade012df
comment:26 Changed 3 years ago by
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
 Commit changed from e593605befca1728288dacb0d08a7414ade012df to 12ad05922d1df8b27db452d6116bb91632bdafc6
Branch pushed to git repo; I updated commit sha1. New commits:
12ad059  Trac 20214: one more doctest

comment:28 Changed 3 years ago by
ping?
comment:30 followup: ↓ 34 Changed 9 months ago by
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
 Cc slelievre added
 Keywords factor polynomial Laurent polynomial added
 Milestone changed from sage7.3 to sage8.6
comment:32 Changed 9 months ago by
 Commit changed from 12ad05922d1df8b27db452d6116bb91632bdafc6 to 63eeb9e3030672d9e248b6ac7e6a4771fdf74aab
comment:33 Changed 9 months ago by
 Description modified (diff)
 Milestone changed from sage8.6 to sage8.7
 Status changed from needs_work to needs_review
comment:34 in reply to: ↑ 30 ; followup: ↓ 37 Changed 9 months ago by
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
 Commit changed from 63eeb9e3030672d9e248b6ac7e6a4771fdf74aab to 4dde5ce2b4ab02530e4e6bdfe7df0cace8c122b0
Branch pushed to git repo; I updated commit sha1. New commits:
4dde5ce  20214: doctest for 20607

comment:36 Changed 9 months ago by
 Description modified (diff)
comment:37 in reply to: ↑ 34 Changed 8 months ago by
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
 Status changed from needs_review to needs_work
red branch => needs work
comment:39 Changed 6 months ago by
 Milestone changed from sage8.7 to sage8.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
 Milestone changed from sage8.8 to sage8.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).
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:
fix inconsistency
add doctests