sage fails to factor some easy expressions

[DaveWitteMorris]

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

Component: symbolics

Keywords: factor, polynomial

Author: Frédéric Chapoton

Branch/Commit: b41c93f

Reviewer: David Lowry-Duda

Issue created by migration from https://trac.sagemath.org/ticket/33640

[DaveWitteMorris]

comment:1

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.

[yuan-zhou]

comment:2

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

[yuan-zhou]

comment:3

[message deleted]

[mkoeppe]

comment:4

See also #32613

[fchapoton]

Branch: public/ticket/33640

[fchapoton]

comment:5

let us see if this little change breaks nothing

---

New commits:

80b2e68

factorisation of symbolic polynomials

[fchapoton]

Commit: 80b2e68

[sagetrac-git]

Changed commit from 80b2e68 to b41c93f

[sagetrac-git]

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

b41c93f

adding doctest for 33640

[fchapoton]

comment:7

apparently, this works. I have added a doctest. It may have consequences on the speed, altough this is not clear.

[davidlowryduda]

comment:8

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.

[davidlowryduda]

Reviewer: David Lowry-Duda

[DaveWitteMorris]

comment:9

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.

[mkoeppe]

comment:10

author name

[vbraun]

comment:11

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

c744d7c Trac #29097: build/make/Makefile.in: Rename make targets SPKG-clean to SPKG-uninstall

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

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

79ed9e5 Trac #33160: update Singular to 4.3.1

4cc4817 Trac #32088: gfan testsuite hangs on 32bit

10247d5 Trac #31049: "setup.py develop" rewrites the installed sage-version.sh as if it is a Python script

7f71494 Updated SageMath version to 9.7.beta6

author '' does not look right

[fchapoton]

Author: Frédéric Chapoton

[fchapoton]

comment:13

so, please give us again a positive review !

[davidlowryduda]

comment:14

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.

[vbraun]

Changed branch from public/ticket/33640 to b41c93f