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

This works fine, producing complex roots:

x=var('x')
f=x+x**2+x**3-100
z=solve(f==0,x)


this also works fine:

R.<x>=ZZ[]
f=x+x**2+x**3-100
f.roots()


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

  x=var('x',domain=ZZ)
f=x+x**2+x**3-100
z=solve(f==0,x)


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

edit retag 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==...].

Sort by » oldest newest most voted

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).

more