Solving Quartic Equation with a Coefficient of 1 MB Space
 

I have an equation of 4 degree (Quartic equation)and a coefficient of this equation takes [B]1 megabyte space [/B]in a text file. I want to solve this Quartic equation using computer. If the the equation has rational solution, I want to [B]get rational solution with the exact numerator and the exact denominator (not the approximation)[/B]. Is it possible?


There are are programming languages (e.g. MAGMA), computer algebra systems (e.g. PARI/GP, SageMath etc, here PARI is C library, can be called from a high-level language application ,for instance, written in C, C++, Pascal, Fortran, Perl, or Python).

If possible, then which programming language or computer algebra systems or library or softaware will be best to solve the Quartic equation as described above? What are the additional issues (configurations of RAM, Processor)?

[QUOTE=Andrew99;540155]I have an equation of 4 degree (Quartic equation)and a coefficient of this equation takes [B]1 megabyte space [/B]in a text file. I want to solve this Quartic equation using computer. If the the equation has rational solution, I want to [B]get rational solution with the exact numerator and the exact denominator (not the approximation)[/B]. Is it possible?
[/QUOTE]

We need more information. Is the polynomial constant a prime number?
Is the lead coefficient a prime? [or monic]? If not, are these coefficients special in some way?

Please explain why you need/want to do this.

Also, please show us that you have some understanding of the problem by explaining
why I asked what I did. Why are these questions important?

Also, tell us what you want to do if there are no rational solutions. A full solution via Ferrari's
formula will be one total cluster f*ck.

[QUOTE=Andrew99;540155]I have an equation of 4 degree (Quartic equation)and a coefficient of this equation takes [B]1 megabyte space [/B]in a text file. I want to solve this Quartic equation using computer. If the the equation has rational solution, I want to [B]get rational solution with the exact numerator and the exact denominator (not the approximation)[/B]. Is it possible?[/QUOTE]

Yes.

Everything is possible if you have the know-how, the resources, and the patience.
Are all the coefficients integers? (if rationals, amplify to the LCM of denominators).
How many coefficients? (i.e. can you reduce to degree 2 or 3 by substitutions?)

Can you solve the equation in \(ℝ\) (to know approximations of solution?)
Can you apply Newton method (google-google) in the vicinity of the solutions to get to the rational solution? (or as better as needed rational approximation?) (you may keep those lines in the rational domain by some tricks, you can start rational, and store the numerator and denominator separate, like, in fact, pari does).

Edit: Ha!? :shock: It seems like AMS symbols don't work in matjax? I had to cheat that R by using UTF8 symbol :razz:

[QUOTE=LaurV;540208]Yes.

Everything is possible if you have the know-how, the resources, and the patience.
[/QUOTE]

False. Grossly false.
`
[QUOTE]
Are all the coefficients integers? (if rationals, amplify to the LCM of denominators).
How many coefficients? (i.e. can you reduce to degree 2 or 3 by substitutions?)
[/QUOTE]

(1) You should have waited until the O.P. answers my questions.
(2) You are wrong in your assertions. Reduction to lower degree [i]requires[/i]
that the equation [i]has[/i] rational solutions. The O.P. did not say that it does.
Indeed. Determining whether it does was part of the problem.
(3) You totally` missed the point of my questions!!!!!
(4) We don't even know if it has solutions in R. I would not want to compute a
Sturm sequence.

It depends how you look at it. I still assert that everything is possible, if you have enough resources, know how, and patience.

Sorry not to wait for the OP to reply to your questions, I know you had very good reasons to ask them (and I know [U]a part[/U] of those reasons, indeed not all of them), but I just went a step ahead and I assumed the OP wants to make a factorization. I went that way long time ago (and banged my head on the wall, because, of course, I am not enough clever nor I know enough math. etc etc).

About your point 2, well, [U]that [/U]is false. Reduction to lower degree does NOT require the solutions to be rational. Think about X^4-2=0, it has no rational solution, and still it can be written as Y^2-2=0, by substituting X^2=Y. Also think about how people few centuries ago used to solve (a subset of) cubic equations, making clever substitutions to reduce them to quadratics (I could point you to some Mathologer/Numberphile videos, hihi, but I am sure you know that already better than me, you just brainfarted or made a typo :razz:).

It is not clear to me that the question is even being posed seriously. I will assume, for the sake of discussion, that it is.

I wonder where the coefficients [i]came[/i] 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 [i]one[/i] of the coefficients, or do they[i]all[/i] 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?

In addition to [b]LaurV[/b]'s suggestion of approximate solution, there is also (assuming integer coefficients) the possibility of reducing the polynomial (mod p) for small prime numbers p. Assuming the coefficients are integers, and the reduction is not the zero polynomial in F[sub]p[/sub][x], it can easily be factored in F[sub]p[/sub][x]. If any of these mod p factorizations have no linear factors, you have the answer to your rational zeroes question -- there aren't any.

[QUOTE=LaurV;540223]

About your point 2, well, [U]that [/U]is false. Reduction to lower degree does NOT require the solutions to be rational. Think about X^4-2=0, it has no rational solution, and still it can be written as Y^2-2=0, by substituting X^2=Y.
[/QUOTE]

The roots are still degree 4. And the substitution does not help find any rational roots. And determining if the quartic is
reducible runs into the same questions that I asked, as well as making any linear transforms.

There's a closed algebraic form for the solutions of a quartic, so you can just substitute away and be done. The solutions mightl be, say, 20 MB each before simplification, but that shouldn't be a problem. You can then simplify and check if they're rational as desired.

[QUOTE=CRGreathouse;540243]There's a closed algebraic form for the solutions of a quartic, so you can just substitute away and be done. The solutions mightl be, say, 20 MB each before simplification, but that shouldn't be a problem. You can then simplify and check if they're rational as desired.[/QUOTE]

I am pretty sure that the solution will be a lot bigger. The discriminant alone
contains 6th degree terms. The solution contains many terms expressed in terms
of the resolvent cubic which itself has many terms in its solution.

I am also unsure whether it CAN be "simplified". Casus irreducibilis says that Cardano's
formula for the resolvent cubic can [i]not[/i] be simplified.

I may, of course, be missing something.

[QUOTE=CRGreathouse;540243]There's a closed algebraic form for the solutions of a quartic, so you can just substitute away and be done. The solutions mightl be, say, 20 MB each before simplification, but that shouldn't be a problem. You can then simplify and check if they're rational as desired.[/QUOTE]

No, the rational roots will be shorter, due to [url]https://en.wikipedia.org/wiki/Rational_root_theorem[/url]

To find "only" the rational roots, you could (fully) factorize the polynom, an easier/faster way (could be well known, found yesterday) :
Let the polynom in Z[x]: a(n)*x^n+...+a(1)*x+a(0)=0
approximate the (real) roots with better than 1/(2*abs(a(n))) absolute difference.
and for each x0 approximated root test the r=g/a(n) rational number as a root, where g=round(x0*a(n)).
You'll get all rational solutions, and this works for every n.
(you can simplify r by computing gcd(g,a(n)) ,

Ok, small (trivial) example:
[CODE]
f(x)=10*x^2 - 17*x - 63
let x0=-1.801 approx. solution, then a(2)=10, g=round(-1.801*10)=-18, and
r=-18/10=-9/5 is indeed a rational root.
(and the other root of f(x) is also rational
[/CODE]

[QUOTE=R.D. Silverman;540263]I am pretty sure that the solution will be a lot bigger. The discriminant alone
contains 6th degree terms. The solution contains many terms expressed in terms
of the resolvent cubic which itself has many terms in its solution.

I am also unsure whether it CAN be "simplified". Casus irreducibilis says that Cardano's
formula for the resolvent cubic can [i]not[/i] be simplified.

I may, of course, be missing something.[/QUOTE]We've already established that Bob is an engineer, not a mathematician :wink:

Bob doubtless remembers the last time I cracked this gag. Something to do with running the LL test backwards.

[QUOTE=R.D. Silverman;540263]<snip>
I am also unsure whether it CAN be "simplified". Casus irreducibilis says that Cardano's
formula for the resolvent cubic can [i]not[/i] be simplified.

I may, of course, be missing something.[/QUOTE]When a [i]casus irreducibilis[/i] cubic has a rational zero, the required complex cube roots "come out exact." See, e.g. [url=https://www.mersenneforum.org/showthread.php?p=527020]this thread[/url]

[QUOTE=R. Gerbicz;540266]No, the rational roots will be shorter, due to [url]https://en.wikipedia.org/wiki/Rational_root_theorem[/url]
[/QUOTE]


The rational roots can be twice the size of the coefficients. This is indeed
shorter than the formula given by (say) Euler's or Ferrari's method. But if one
expresses the roots using these formulae the result will be a lot larger.

[Note: twice the size is by adding the size of the lead coefficient and the constant; their
ratio can be the root]

I do not know if Ferrari's [or Euler's] formulae can be simplified.
I asked this earlier. Casus irreducibilis gets in the way. Or does it? I've never
looked at this. [Nor have I bothered to memorize e.g. Ferrari's method]




[QUOTE]

To find "only" the rational roots, you could (fully) factorize the polynom,
[/QUOTE]

Which in turn requires factoring a(0) and a(n). I'd like to see anyone
factor 8 million bit numbers..:smile: [I want the algorithm!!!] Which is why I asked if these
coefficients were prime.

[QUOTE]
an easier/faster way (could be well known, found yesterday) :
Let the polynom in Z[x]: a(n)*x^n+...+a(1)*x+a(0)=0
approximate the (real) roots with better than 1/(2*abs(a(n))) absolute difference.
and for each x0 approximated root test the r=g/a(n) rational number as a root, where g=round(x0*a(n)).
You'll get all rational solutions, and this works for every n.
(you can simplify r by computing gcd(g,a(n)) ,

Ok, small (trivial) example:
[CODE]
f(x)=10*x^2 - 17*x - 63
let x0=-1.801 approx. solution, then a(2)=10, g=round(-1.801*10)=-18, and
r=-18/10=-5/4 is indeed a rational root.
[/CODE][/QUOTE]

Neatly sidestepping using an exact formula for the roots or factoring the
coefficients. Nice.

OTOH I must be stupid. :smile: How is -18/10 = -5/4???? I get -9/5..
Note also that -5/4 violates the rational roots thm.

[QUOTE=LaurV;540223]It depends how you look at it. I still assert that everything is possible, if you have enough resources, know how, and patience.
[/QUOTE]

Oh? Please tell me two integers that lie between 1 and 2. Please solve x = x+1 over C.
Please find positive integers (x,y,z) such that z^3 = x^3 + y^3.

Anything is clearly [b] NOT [/b] possible.

[QUOTE=R.D. Silverman;540273]OTOH I must be stupid. :smile: How is -18/10 = -5/4???? I get -9/5..
Note also that -5/4 violates the rational roots thm.[/QUOTE]

Corrected, there were multiple typos in the post.

[QUOTE=R. Gerbicz;540266]No, the rational roots will be shorter, due to [url]https://en.wikipedia.org/wiki/Rational_root_theorem[/url][/QUOTE]

Oh of course, silly me.

So 'all' that's needed is to factor some megabit numbers and test them in a polynomial.

[QUOTE=R.D. Silverman;540274]Oh? Please tell me two integers that lie between 1 and 2. Please solve x = x+1 over C.
Please find positive integers (x,y,z) such that z^3 = x^3 + y^3.

Anything is clearly [b] NOT [/b] possible.[/QUOTE]I believe that you should interpret LaurV's statement within the context of the OP, where it was clearly stated [B]if[/B] solutions exist.

[QUOTE=Dr Sardonicus;540269]When a [i]casus irreducibilis[/i] cubic has a rational zero, the required complex cube roots "come out exact." See, e.g. [url=https://www.mersenneforum.org/showthread.php?p=527020]this thread[/url][/QUOTE]

Thank you! I did not know this result.

[QUOTE=xilman;540287]I believe that you should interpret LaurV's statement within the context of the OP, where it was clearly stated [B]if[/B] solutions exist.[/QUOTE]

Aha!

A = A.

Anything is possible only if Anything has a solution...
A math problem has a solution if it has a solution.

One learns something new every day!

[QUOTE=R.D. Silverman;540296]Aha!

A = A.

Anything is possible only if Anything has a solution...
A math problem has a solution if it has a solution.

One learns something new every day![/QUOTE]

Note that even if a solution does exist it may not be possible to find it because
it is beyond our resources. For example, find the 17'th prime greater than
F1000000.

I say again: Anything is not possible. Even when a solution exists.

[QUOTE=R.D. Silverman;540296]Aha!

A = A.

Anything is possible only if Anything has a solution...
A math problem has a solution if it has a solution.

One learns something new every day![/QUOTE]You got it!

[QUOTE=R.D. Silverman;540298]Note that even if a solution does exist it may not be possible to find it because
it is beyond our resources. For example, find the 17'th prime greater than
F1000000.

I say again: Anything is not possible. Even when a solution exists.[/QUOTE]Once more, you are demonstrating that you are an engineer.

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.

[QUOTE=Dr Sardonicus;540227]

I wonder where the coefficients [i]came[/i] 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 [i]one[/i] of the coefficients, or do they[i]all[/i] 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?
[/QUOTE]


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.

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

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

[QUOTE=Andrew99;540341]- If the equation has no rational solution, we don't need the solution.[/QUOTE]You might want to multiply through by the LCM of the denominators to get all integer coefficients, then proceed as [b]R. Gerbicz[/b] 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 [i]all complex[/i] 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 [i]a priori[/i] 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 [i]which do not divide any of the denominators[/i]. 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.

[QUOTE=Dr Sardonicus;540365]You might want to multiply through by the LCM of the denominators to get all integer coefficients, then proceed as [b]R. Gerbicz[/b] suggests. [/QUOTE]

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

[QUOTE=Dr Sardonicus;540365]I will mention that the Pari function polroots() [at least, in my ancient version] returns [i]all complex[/i] 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).[/QUOTE]

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

[QUOTE=Dr Sardonicus;540365]Another option is to try to reduce the polynomial (mod p) for small primes p [i]which do not divide any of the denominators[/i]. 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.[/QUOTE]

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.

[QUOTE=CRGreathouse;540378]Yes! If you can factor the resulting leading and constant terms, you'll be essentially done.[/QUOTE]
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 [b]R. Gerbicz[/b] 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.

[QUOTE=Dr Sardonicus;540384]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 [b]R. Gerbicz[/b] 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.[/QUOTE]

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.

[QUOTE=R.D. Silverman;540386]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........
[/QUOTE]
(my emphasis)
[quote=Andrew99;540342]
[quote=Dr Sardonicus;540227]<snip>
Assuming the coefficients are integers, one could also ask what is actually known about them. Are they of some special form?[/quote]
It comes from elliptic curve, [b]they are either integers or fraction[/b], 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.[/quote]
So it seems to me that, although the polynomial as given is monic, the coefficients might not be integers.

[QUOTE=Dr Sardonicus;540388](my emphasis)

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

Ah. Of course.

[QUOTE=R.D. Silverman;540386]It would be nice to know where the problem comes from.[/QUOTE]
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[sup]2[/sup] = 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[sup]2[/sup] = f(x) could have some rational point with y <> 0.

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

[QUOTE=R.D. Silverman;540348]Rational roots thm. Is the constant (say) a perfect power so that it can be factored?
Is it a factorial?[/QUOTE]
We have no such information.