Ask Your Question

why can't I compute the zeros of an integer polynomial using solve()?

asked 2021-07-01 08:12:48 +0100

dantetante gravatar image

This works fine, producing complex roots:


this also works fine:


but this seems to run forever without error message and I don't understand why:


can anyone explain or tell me where to start reading to understand this behaviour?

edit retag flag offensive close merge delete


Instead of x = var('x', domain=ZZ), you can use z = solve(f==0, x, domain=ZZ). It should return an equation that it doesn't know how to solve in the integers — it will return [x==...].

John Palmieri gravatar imageJohn Palmieri ( 2021-07-02 01:50:32 +0100 )edit

1 Answer

Sort by » oldest newest most voted

answered 2021-07-02 00:27:42 +0100

FabianG gravatar image

The two methods use different approaches under the hood. The second method computes the factorization of the polynomial over $\mathbb{Z}$. Then the integral roots belong to the linear factors in this factorization.

The third method uses Sympy's univariate diophantine equation solver which apparently first computes the real solutions and then determines which of them are integral. This seems to be hard for Sympy in your example in which it calculates

Intersection(FiniteSet(-1/3 - 2/(9*(2707/54 + 11*sqrt(6729)/18)**(1/3)) + (2707/54 + 11*sqrt(6729)/18)**(1/3)), Integers)

and probably lacks the proper support for dealing well with elements of algebraic number fields (my guess)...

You can find this out by stopping the calculation with a keyboard interrupt (Ctrl-C) and looking at the stack trace; or by directly going through Sage's source code (and then Sympy's).

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-07-01 08:12:48 +0100

Seen: 87 times

Last updated: Jul 02 '21