Solving Quartic Equation with a Coefficient of 1 MB Space

[Andrew99]

1. Is the polynomial constant a prime number?
-No
2. Is the lead coefficient a prime? [or monic]?
-monic
3.If not, are these coefficients special in some way?
-Don't understand this question
Please explain why you need/want to do this.
4. tell us what you want to do if there are no rational solutions.
- If the equation has no rational solution, we don't need the solution.

[Andrew99]

Originally Posted by Dr Sardonicus

I wonder where the coefficients came from. Are they integers? Exact fractions? What?

The clause "a coefficient of this equation takes 1 megabyte space in a text file" is ambiguous. Does it only apply to one of the coefficients, or do theyall require that much space? Or is, perhaps, the polynomial monic?

Assuming the coefficients are integers, one could also ask what is actually known about them. Are they of some special form?

It comes from elliptic curve, they are either integers or fraction, there are 4 coefficients which has huge number, if you save them, each of them will take 1 MB in a text file, it is that simple, the polynomial is monic, thanks.

[R.D. Silverman]

Originally Posted by Andrew99

3.If not, are these coefficients special in some way?
-Don't understand this question
Please explain why you need/want to do this.

Rational roots thm. Is the constant (say) a perfect power so that it can be factored?
Is it a factorial?

[Dr Sardonicus]

Originally Posted by Andrew99

- If the equation has no rational solution, we don't need the solution.

You might want to multiply through by the LCM of the denominators to get all integer coefficients, then proceed as R. Gerbicz suggests. In Pari-GP you would have to set realprecision high enough to accommodate your integers first. This approach has the obvious merit that it is guaranteed to work. I will mention that the Pari function polroots() [at least, in my ancient version] returns all complex values, so you have to be a bit careful about distinguishing real from complex roots of the equation (real roots have a "small-as-possible" nonzero complex part).

If you have any a priori knowledge about how many pairs of complex-conjugate roots the equation has, use it. For example, if you know the equation always has only real roots, just take the real part of what polroots() gives you.

Another option is to try to reduce the polynomial (mod p) for small primes p which do not divide any of the denominators. If a mod p factorization does not have any linear factors, neither does the given polynomial, and you're done. Each such mod p reduction and factorization can be done fairly quickly, but, alas I can offer no guarantee this method will work for any really small primes p. It also is of no help in finding a rational root if one exists.

[CRGreathouse]

Originally Posted by Dr Sardonicus

You might want to multiply through by the LCM of the denominators to get all integer coefficients, then proceed as R. Gerbicz suggests.

Yes! If you can factor the resulting leading and constant terms, you'll be essentially done.

Originally Posted by Dr Sardonicus

I will mention that the Pari function polroots() [at least, in my ancient version] returns all complex values, so you have to be a bit careful about distinguishing real from complex roots of the equation (real roots have a "small-as-possible" nonzero complex part).

Newer versions also have polrootsreal() which return only those roots which are (exactly) real.

Originally Posted by Dr Sardonicus

Another option is to try to reduce the polynomial (mod p) for small primes p which do not divide any of the denominators. If a mod p factorization does not have any linear factors, neither does the given polynomial, and you're done. Each such mod p reduction and factorization can be done fairly quickly, but, alas I can offer no guarantee this method will work for any really small primes p. It also is of no help in finding a rational root if one exists.

Absolutely. You can use this method to rule out a rational root: if the polynomial mod p is irreducible, or is the product of two irreducible quadratics, then the original polynomial it does not have a rational root.

[Dr Sardonicus]

Originally Posted by CRGreathouse

Yes! If you can factor the resulting leading and constant terms, you'll be essentially done.

No -- you don't have to factor them! Good thing, too, since we're talking about coefficients with possibly millions of decimal digits.

The method R. Gerbicz outlined for a poly with integer coefficients only requires computing real roots r to within 1/(2*a(n)) where a(n) is the lead coefficient, and then checking whether round(r*a(n))/a(n) is a root.

That's still potentially a lot of real precision, along with the large coefficients, but that should be no problem. Since we're only dealing with quartics, this approach seems quite practicable.

[R.D. Silverman]

Originally Posted by Dr Sardonicus

No -- you don't have to factor them! Good thing, too, since we're talking about coefficients with possibly millions of decimal digits.

The method R. Gerbicz outlined for a poly with integer coefficients only requires computing real roots r to within 1/(2*a(n)) where a(n) is the lead coefficient, and then checking whether round(r*a(n))/a(n) is a root.

That's still potentially a lot of real precision, along with the large coefficients, but that should be no problem. Since we're only dealing with quartics, this approach seems quite practicable.

Very practical since the OP said the polynomial is monic. But there is something
that I don't understand. The OP seems to know at least some math since he/she is
playing with elliptic curves. However, it puzzles me why he/she would ask for
rational roots when he/she would know that the root is an integer........

It would be nice to know where the problem comes from.

[Dr Sardonicus]

Originally Posted by R.D. Silverman

Very practical since the OP said the polynomial is monic.
But there is something that I don't understand. The OP seems to know at least some math since he/she is playing with elliptic curves. However, it puzzles me why he/she would ask for rational roots when he/she would know that the root is an integer........

(my emphasis)

Originally Posted by Andrew99

It comes from elliptic curve, they are either integers or fraction, there are 4 coefficients which has huge number, if you save them, each of them will take 1 MB in a text file, it is that simple, the polynomial is monic, thanks.

So it seems to me that, although the polynomial as given is monic, the coefficients might not be integers.

[R.D. Silverman]

Originally Posted by Dr Sardonicus

(my emphasis)

So it seems to me that, although the polynomial as given is monic, the coefficients might not be integers.

Ah. Of course.

[Dr Sardonicus]

Originally Posted by R.D. Silverman

It would be nice to know where the problem comes from.

Indeed. With my very limited knowledge of elliptic curves, only one possibility occurs to me: If the quartic f(x) has a rational zero r, then (0, r) is a ready-made rational point on the curve

y² = f(x)

which can be used to transform the curve into an elliptic curve

y^2 = F(x), F cubic.

If f(x) has no rational zero, there is no rational point (0, r) on the curve.

Of course if f(x) has no rational zeroes, it is still possible AFAIK that y² = f(x) could have some rational point with y <> 0.

EDIT: Of course, with y <> 0 , there would be two rational points (y, r) and (-y, r) whereas with y = 0 you only get one ratonal point.

[Andrew99]

Originally Posted by R.D. Silverman

Rational roots thm. Is the constant (say) a perfect power so that it can be factored?
Is it a factorial?

We have no such information.