 mersenneforum.org Solving Quartic Equation with a Coefficient of 1 MB Space
 Register FAQ Search Today's Posts Mark Forums Read  2020-03-21, 03:25 #23 Andrew99   Aug 2019 11 Posts 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.   2020-03-21, 03:30   #24
Andrew99

Aug 2019

11 Posts Quote:
 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.   2020-03-21, 04:16   #25
R.D. Silverman

Nov 2003

1CFC16 Posts Quote:
 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?   2020-03-21, 12:55   #26
Dr Sardonicus

Feb 2017
Nowhere

3,251 Posts Quote:
 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.   2020-03-21, 15:32   #27
CRGreathouse

Aug 2006

22×5×293 Posts Quote:
 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.

Quote:
 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.

Quote:
 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.   2020-03-21, 16:34   #28
Dr Sardonicus

Feb 2017
Nowhere

3,251 Posts Quote:
 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.   2020-03-21, 17:01   #29
R.D. Silverman

Nov 2003

22·5·7·53 Posts Quote:
 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.   2020-03-21, 17:19   #30
Dr Sardonicus

Feb 2017
Nowhere

3,251 Posts Quote:
 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)
Quote:
Quote:
 Originally Posted by Dr Sardonicus 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.
So it seems to me that, although the polynomial as given is monic, the coefficients might not be integers.   2020-03-21, 17:23   #31
R.D. Silverman

Nov 2003

22·5·7·53 Posts Quote:
 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.   2020-03-21, 18:07   #32
Dr Sardonicus

Feb 2017
Nowhere

3,251 Posts Quote:
 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

y2 = 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 y2 = 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.

Last fiddled with by Dr Sardonicus on 2020-03-21 at 18:13 Reason: As indicated   2020-03-21, 19:36   #33
Andrew99

Aug 2019

138 Posts Quote:
 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.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post aein Factoring 3 2017-02-25 16:42 fivemack Factoring 6 2011-12-12 05:08 Unregistered Homework Help 2 2009-03-03 19:56 R.D. Silverman Factoring 9 2009-02-18 23:24

All times are UTC. The time now is 17:32.

Sat Jun 6 17:32:41 UTC 2020 up 73 days, 15:05, 1 user, load averages: 1.54, 2.17, 2.19