Opened 8 months ago

Closed 3 months ago

# sage fails to factor some easy expressions

Reported by: Owned by: Dave Morris major sage-9.8 symbolics factor, polynomial Frédéric Chapoton David Lowry-Duda N/A b41c93f b41c93f6e7d42c69684bcbaad3cbc0e822f76e51

### 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
```

### 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:5 Changed 6 months ago by Frédéric Chapoton

Branch: → public/ticket/33640 → 80b2e688c5a6cad698fc50ea02355bda77e7c852 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 git

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

 ​b41c93f `adding 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 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 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`.

author name

### comment:11 Changed 4 months ago by Volker Braun

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 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 needs_work → needs_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_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 Frédéric Chapoton

Milestone: sage-9.7 → sage-9.8

### comment:16 Changed 3 months ago by Volker Braun

Branch: public/ticket/33640 → b41c93f6e7d42c69684bcbaad3cbc0e822f76e51 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.