Solving Quartic Equation with a Coefficient of 1 MB Space

[Andrew99]

I have an equation of 4 degree (Quartic equation)and a coefficient of this equation takes 1 megabyte space in a text file. I want to solve this Quartic equation using computer. If the the equation has rational solution, I want to get rational solution with the exact numerator and the exact denominator (not the approximation). 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)?

[R.D. Silverman]

Originally Posted by Andrew99

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

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.

[LaurV]

Originally Posted by Andrew99

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

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!? It seems like AMS symbols don't work in matjax? I had to cheat that R by using UTF8 symbol

[R.D. Silverman]

Originally Posted by LaurV

Yes.

Everything is possible if you have the know-how, the resources, and the patience.

False. Grossly false.
`

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

(1) You should have waited until the O.P. answers my questions.
(2) You are wrong in your assertions. Reduction to lower degree requires
that the equation has 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.

[LaurV]

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 a part 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, that 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 ).

[Dr Sardonicus]

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 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?

In addition to LaurV'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_p[x], it can easily be factored in F_p[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.

[R.D. Silverman]

Originally Posted by LaurV

About your point 2, well, that 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.

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.

[CRGreathouse]

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.

[R.D. Silverman]

Originally Posted by CRGreathouse

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.

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 not be simplified.

I may, of course, be missing something.

[R. Gerbicz]

Originally Posted by CRGreathouse

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.

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

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:

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

[xilman]

Originally Posted by R.D. Silverman

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 not be simplified.

I may, of course, be missing something.

We've already established that Bob is an engineer, not a mathematician

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