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: sage-9.8
Component: symbolics Keywords: factor, polynomial
Cc: Merged in:
Authors: Frédéric Chapoton Reviewers: David Lowry-Duda
Report Upstream: N/A Work issues:
Branch: b41c93f (Commits, GitHub, GitLab) Commit: b41c93f6e7d42c69684bcbaad3cbc0e822f76e51
Dependencies: Stopgaps:

Status badges

Description

As reported on sage-devel, 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 Dave Morris

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 of x), 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.

comment:2 Changed 8 months ago by Yuan Zhou

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 = (x-y)^2*(y-z)*(z-x) + (y-z)^2*(z-x)*(x-y) + (z-x)^2*(x-y)*(y-z)
sage: P.<x,y,z>=QQ[]
sage: p = (x-y)^2*(y-z)*(z-x) + (y-z)^2*(z-x)*(x-y) + (z-x)^2*(x-y)*(y-z)
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
Last edited 8 months ago by Yuan Zhou (previous) (diff)

comment:3 Changed 8 months ago by Yuan Zhou

[message deleted]

Last edited 8 months ago by Yuan Zhou (previous) (diff)

comment:4 Changed 8 months ago by Matthias Köppe

See also #32613

comment:5 Changed 6 months ago by Frédéric Chapoton

Branch: public/ticket/33640
Commit: 80b2e688c5a6cad698fc50ea02355bda77e7c852
Status: newneeds_review

let us see if this little change breaks nothing


New commits:

80b2e68factorisation of symbolic polynomials

comment:6 Changed 6 months ago by git

Commit: 80b2e688c5a6cad698fc50ea02355bda77e7c852b41c93f6e7d42c69684bcbaad3cbc0e822f76e51

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

b41c93fadding doctest for 33640

comment:7 Changed 6 months ago by Frédéric Chapoton

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 David Lowry-Duda

Reviewers: David Lowry-Duda
Status: needs_reviewpositive_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 Dave Morris

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:10 Changed 5 months ago by Matthias Köppe

author name

comment:11 Changed 4 months ago by Volker Braun

Status: positive_reviewneeds_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 SPKG-clean to SPKG-uninstall

8312ee1e90 Trac #33530: Upgrade ipython to 8.x

067a66c7e9 Trac #33428: prompt_toolkit 3.0.25+ breaks Ctrl-C

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 sage-version.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 Frédéric Chapoton

Authors: Frédéric Chapoton
Status: needs_workneeds_review

comment:13 Changed 3 months ago by Frédéric Chapoton

so, please give us again a positive review !

comment:14 Changed 3 months ago by David Lowry-Duda

Status: needs_reviewpositive_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 Frédéric Chapoton

Milestone: sage-9.7sage-9.8

comment:16 Changed 3 months ago by Volker Braun

Branch: public/ticket/33640b41c93f6e7d42c69684bcbaad3cbc0e822f76e51
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.