Opened 8 months ago
Closed 3 months ago
#33640 closed defect (fixed)
sage fails to factor some easy expressions
Reported by:  Dave Morris  Owned by:  

Priority:  major  Milestone:  sage9.8 
Component:  symbolics  Keywords:  factor, polynomial 
Cc:  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  David LowryDuda 
Report Upstream:  N/A  Work issues:  
Branch:  b41c93f (Commits, GitHub, GitLab)  Commit:  b41c93f6e7d42c69684bcbaad3cbc0e822f76e51 
Dependencies:  Stopgaps: 
Description
As reported on sagedevel, sage fails to factor expressions that expand to something very easy, such as x^2
or 0
. Instead, it returns the original expression.
sage: ((x + 1)^2  2*x  1).factor() # bad (should be x^2) (x + 1)^2  2*x  1 sage: ((x + 1)^2  x^2  2*x  1).factor() # bad (should be 0) (x + 1)^2  x^2  2*x  1 sage: ((x + 2)^2  2*x  3).factor() # good (x + 1)^2
Change History (16)
comment:1 Changed 8 months ago by
comment:2 Changed 8 months ago by
Maybe a silly question, but I notice that symbolic.expression.Expression.factor()
says "If you are factoring a polynomial with rational coefficients (and dontfactor is empty) the factorization is done using Singular
instead of Maxima, so the following is very fast instead of dreadfully slow".
I'm just wondering, if it concerns a polynomial, why not using Polynomial
instead?
sage: P Multivariate Polynomial Ring in x, y, z over Rational Field sage: p 0 sage: p = (xy)^2*(yz)*(zx) + (yz)^2*(zx)*(xy) + (zx)^2*(xy)*(yz) sage: P.<x,y,z>=QQ[] sage: p = (xy)^2*(yz)*(zx) + (yz)^2*(zx)*(xy) + (zx)^2*(xy)*(yz) sage: p 0 sage: q = (x + 1)^2  2*x  1 sage: q x^2 sage: r = (x + 1)^2  x^2  2*x  1 sage: r 0 sage: s = (x + 2)^2  2*x  3 sage: s x^2 + 2*x + 1 sage: s.factor() (x + 1)^2
comment:5 Changed 6 months ago by
Branch:  → public/ticket/33640 

Commit:  → 80b2e688c5a6cad698fc50ea02355bda77e7c852 
Status:  new → needs_review 
let us see if this little change breaks nothing
New commits:
80b2e68  factorisation of symbolic polynomials

comment:6 Changed 6 months ago by
Commit:  80b2e688c5a6cad698fc50ea02355bda77e7c852 → b41c93f6e7d42c69684bcbaad3cbc0e822f76e51 

Branch pushed to git repo; I updated commit sha1. New commits:
b41c93f  adding doctest for 33640

comment:7 Changed 6 months ago by
apparently, this works. I have added a doctest. It may have consequences on the speed, altough this is not clear.
comment:8 Changed 5 months ago by
Reviewers:  → David LowryDuda 

Status:  needs_review → positive_review 
This works. I spent a while trying to determine if there was a good reason the function to return false if ginac determines that the numerator and denominator are "trivial" (as was morally done before), but I really can't find one.
I note that the boolean result of the changed function is also used in gamma_normalization, but this change seems to work well with that too.
comment:9 Changed 5 months ago by
I think the point of checking the boolean value is that if a polynomial is irreducible, then it should be returned unchanged, instead of expanded. However, this doesn't seem to work:
sage: ((x + 1)^100 + 2).factor() x^100 + 100*x^99 + 4950*x^98 + 161700*x^97 + 3921225*x^96 + <lots more terms>
It would be better to return (x + 1)^100 + 2
. If the user wants to expand this expression, they can apply expand
.
comment:11 Changed 4 months ago by
Status:  positive_review → needs_work 

Merge failure on top of:
381771d188 Trac #33636: replace loadable_module_extension() by importlib.machinery.EXTENSION_SUFFIXES
4c0f8481d2 Trac #33002: Method tikz of polyhedron class can now return an object of type TikzPicture?
c744d7c09c Trac #29097: build/make/Makefile.in: Rename make targets SPKGclean to SPKGuninstall
8312ee1e90 Trac #33530: Upgrade ipython to 8.x
067a66c7e9 Trac #33428: prompt_toolkit 3.0.25+ breaks CtrlC
79ed9e5ddb Trac #33160: update Singular to 4.3.1
4cc4817aeb Trac #32088: gfan testsuite hangs on 32bit
10247d5f2a Trac #31049: "setup.py develop" rewrites the installed sageversion.sh as if it is a Python script
7f7149489c Updated SageMath version to 9.7.beta6
author does not look right
comment:12 Changed 4 months ago by
Authors:  → Frédéric Chapoton 

Status:  needs_work → needs_review 
comment:14 Changed 3 months ago by
Status:  needs_review → positive_review 

I'm marking this as positive again. I don't know about the merge failure Volker mentioned, but if I recall correctly that is a separate issue. If I'm wrong, please let me know.
comment:15 Changed 3 months ago by
Milestone:  sage9.7 → sage9.8 

comment:16 Changed 3 months ago by
Branch:  public/ticket/33640 → b41c93f6e7d42c69684bcbaad3cbc0e822f76e51 

Resolution:  → fixed 
Status:  positive_review → closed 
Here is a tentative diagnosis from a quick look at the code. It seems that sagemath expands the expression into a polynomial (a linear combination of powers of
x
) before trying to factor it. If the expansion has only a single term (a constant times a power ofx
), then nothing needs to be done, since this expansion is already factored. Sagemath erroneously thinks nothing needed to be done from the beginning, and returns the original expression, instead of the expanded expression.